Bug about pygame.draw.polygon() about pygame HOT 9 OPEN

I believe I found the issue within src_c/draw.c on line 2399
x_intersect[n_intersections++] = (y - y1) * (x2 - x1) / (y2 - y1) + x1;
An overflow occurs in (y - y1) * (x2 - x1) and causes the incorrect value to be added to x_intersect.

I'd like to contribute to this issue so I'm going to work on writing a unit test. This will be my first contribution so any feedback or guidance is appreciated

from pygame.

Nice detective work!

It should be pretty easy to convert the example by @xiaobbl into a test.

See test/draw_test.py class DrawPolygonMixin
Look at the other tests for a bit of inspiration in how things are done.

def test_polygon_large_issue_4191(self):
    # drawing...
    self.assertEquals(...)

To run the test:
python test/draw_test.py

from pygame.

Thank you very much for the report.

The next step towards solving this issue is to write a unit test.

from pygame.

more information:
the point below cant be rendered at all:
[[1499.7091001686845, 418.2422325741588], [1801.1540549091812, -1058.862888101421], [11834.893501438004, -880867.9030648664], [682.7704452436077, 1247.8114930617442]]

from pygame.

And more:draw a polygon without filling doesn't seem to occur this bug

from pygame.

I believe I found the issue within src_c/draw.c on line 2399 x_intersect[n_intersections++] = (y - y1) * (x2 - x1) / (y2 - y1) + x1; An overflow occurs in (y - y1) * (x2 - x1) and causes the incorrect value to be added to x_intersect.

I'd like to contribute to this issue so I'm going to work on writing a unit test. This will be my first contribution so any feedback or guidance is appreciated

An example in gdb of the overflow

from pygame.

When going to write the test, I found a test case commented out referencing Issue #3989 and I believe these are the same issue. I was able to uncomment the test and get it working. It fails before fixing the overflow issue and passes after fixing. The fix I used was changing:
x_intersect[n_intersections++] = (y - y1) * (x2 - x1) / (y2 - y1) + x1;
to
x_intersect[n_intersections++] = x1 + (int)(((double)(y - y1) * (x2 - x1)) / (y2 - y1));

I'm not sure if this is the best solution, I was thinking that you could check for overflow before the calculation and only cast in that case. I've got the test case added for #3989 as follows:

def test_polygon_large_coords(self):
  """
  Ensures draw polygon works correctly with large points.
  Testing the drawings of filled polygons
  """
  point_a = (600, 50)
  point_b = (50, 600)
  extreme_points_coords = (58000, 100000)
  extreme_negative_coords = (-58000, -100000)
  extreme_negative_x = (-58000, 100000)
  extreme_negative_y = (58000, -100000)
  
  surf_w = surf_h = 650
  surface = pygame.Surface((surf_w, surf_h))
  
  green = (0, 255, 0)
  white = (0, 0, 0, 255)
  
  # Draw white background
  pygame.draw.rect(surface, white, (0, 0, surf_w, surf_h), 0)
  
  # Extreme points case
  def extreme_points(self):
      self.assertEqual(surface.get_at((640, 50)), white)
      self.assertEqual(surface.get_at((50, 640)), white)
  
  # Extreme negative points case
  def extreme_negative_pass(self):
      self.assertEqual(surface.get_at((600, 25)), white)
  
  def extreme_negative_fail(self):
      self.assertNotEqual(surface.get_at((5, 5)), white)
  
  # Extreme negative x case
  def extreme_x_pass(self):
      self.assertEqual(surface.get_at((600, 600)), white)
  
  def extreme_x_fail(self):
      self.assertNotEqual(surface.get_at((100, 640)), white)
  
  # Extreme negative y case
  def extreme_y_pass(self):
      self.assertEqual(surface.get_at((600, 600)), white)
  
  def extreme_y_fail(self):
      self.assertNotEqual(surface.get_at((300, 300)), white)
  
  # Checks the surface point to ensure the polygon has been drawn correctly.
  # Uses multiple passing and failing test cases depending on the polygon
  self.draw_polygon(surface, green, (point_a, point_b, extreme_points_coords))
  extreme_points(self)
  
  pygame.draw.rect(surface, white, (0, 0, surf_w, surf_h), 0)        
  self.draw_polygon(surface, green, (point_a, point_b, extreme_negative_coords))
  extreme_negative_pass(self)
  extreme_negative_fail(self)
  
  pygame.draw.rect(surface, white, (0, 0, surf_w, surf_h), 0)
  self.draw_polygon(surface, green, (point_a, point_b, extreme_negative_x))
  extreme_x_pass(self)
  extreme_x_fail(self)
  
  pygame.draw.rect(surface, white, (0, 0, surf_w, surf_h), 0)
  self.draw_polygon(surface, green, (point_a, point_b, extreme_negative_y))
  extreme_y_pass(self)
  extreme_y_fail(self)

I was thinking I'll add this case (#4191) to the same function as well, but am not sure if it is necessary since it is the same overflow issue

from pygame.

Nice find. I think you have enough for a PR now.

You could try if there’s any speed difference on your machine with timeit.timeit(“draw()”). But I don’t there would be much of a difference.

Did you look at bumping the size of those types up? I don’t know if they are already large?

But yeah, sounds like you already have a fix, so feel free to open a PR with that. Then CI can run the test on all sorts of different CPUs and compilers.

from pygame.

@illume request for review

from pygame.