Exact expected shape of draw.polygon? (644)

[GalacticEmperor1]

Issue №644 opened by e1000 at 2018-11-27 20:39:29

Investigating # 90 I found some y-axis-asymetry when drawing a rhombus (or diamond) shapes; we generate following shapes :

This was done with following code :

def pxl_to_rect(x, y, size=20):
    return (100 + size * x, size * y, size, size)

def large_map(surface, bg_col, left, right, top, bottom, size=20):
    '''enlarge a piece of the image for immediate vizualization'''
    for x in range(left, right):
        for y in range(top, bottom):
            col = surface.get_at((x, y))
            if col != bg_col:
                pg.draw.rect(surface, col, pxl_to_rect(x, y, size), 0)

def main():
    surface = pg.display.set_mode((800, 600))
    surface.fill(BLACK)

    pg.draw.polygon(surface, GREEN, [(1, 3), (4, 5), (7, 3), (4, 1)])
    pg.draw.polygon(surface, RED, [(11, 4), (13, 7), (15, 4), (13, 1)])
    large_map(surface, BLACK, 0, 20, 0, 20)

So the polygon has a tendency to emphasize lower pixel. The reason is probably some (int)-casting in the polygon algorithm... So what's the expected shape ? Should we keep it like that or search some top-down-symetric solution ?

Related Docs: https://www.pygame.org/docs/ref/draw.html# pygame.draw.polygon

---

Comments

*e1000 commented at 2018-11-27 20:44:26*

Btw, the current Python and C drawing algorithm do not generate the same shape, so it would be nice to fix this with respect to @illume's remark in # 90 to have a library of drawing algorithms... I would give it a try to see if some usage of round could make things symetric.

---

*snoyes commented at 2020-06-19 13:46:54*

Note also that it is only filled polygons which do this.

Top is polygon with width 0. Middle is polygon with width=1. Bottom is draw.lines.

---

*snoyes commented at 2020-06-19 16:11:24*

Filled polygons are created by drawing horizontal lines. The algorithm to figure out where the horizontal line should start and stop is:

https://github.com/pygame/pygame/blob/4562396964cca81bceb2d12d3f09aa96746cb3fa/src_c/draw.c# L1856

Integer division truncates towards 0.

For the top left line, (x1, y1) = (4, 1); (x2, y2) = (1, 3) The second horizontal line starts at the x-coordinate: (y - y1) (x2 - x1) / (y2 - y1) + x1 = (2 - 1) (1 - 4) / (3 - 1) + 4 = -3 / 2 + 4 = -1 + 4 = 3

For the bottom left line, (x1, y1) = (1, 3); (x2, y2) = (4, 5) The fourth horizontal line starts at the x-coordinate: (y - y1) (x2 - x1) / (y2 - y1) + x1 = (4 - 3) (4 - 1) / (5 - 3) + 1 = 3 / 2 + 1 = 1 + 1 = 2

Hence the asymmetry. Lines with positive slope will round to the pixel on the right; lines with negative slope will round to the pixel on the left.

---

*snoyes commented at 2020-06-22 00:04:15*

Also note that just adjusting the rounding will not fix this. When the Bresenham line algorithm would draw several horizontal pixels, this scanline method starts in the middle of those. As the edge becomes closer to horizontal, that difference will be increasingly exaggerated. Here the top and bottom rows of the filled polygon are only one pixel when they ought to be seven. Likewise the second row misses three pixels on each side:

I'd be more inclined to make a call to the outlined polygon code, and then do some sort of floodfill.

[Conz3D]

I was going to write my own issue about it. Not sure how exactly this is all related. I'm trying to line up aalines with polys for weeks now. (pygame-ce 2.3.1 (SDL 2.26.5, Python 3.11.3)) At first: As it was pointed out the drawing for lines and polys are different in regards of converting floats to ints. If you draw the same points list (floats) with polys and lines (not aalines) they don't line up. (posted this on discord)

Related problem is to line up aalines with polygons. Since aalines can use floats, there would be the need for a clear defined rounding to line up aalines with poligons, or a flag in aalines to round the same way as lines and polys.. It seems all related. Discussed this problem in discord, too.

https://discord.com/channels/772505616680878080/772507247540437032/1140633526476210286

Ragarding the flood fill. I have tried this solution in my test app here: https://discord.com/channels/772505616680878080/822265298085347368/1131624995932614697

But since I try to fill aalines, there are additional problems how to handle partial transparent pixels with flood fill.

Should I open my own issue or is this one related complex and can be handled with this issue here?

[dr0id]

@Conz3D I went through the trouble of getting this PR running locally (left corrected, right before):

Does that help?

[Conz3D]

@dr0id Thank you for your efforts. In my example, that you have used, I can see only very few changes. But there I have trunkated the floats for the polys by hand. Would you be so kind and do this test again, but with this version: https://gist.github.com/Conz3D/98828245d5d41a26261340b11820a99e There I use the floats without conversion for the polys. (please the same comparison) I would like to see a test with a poly and non AA lines. If they line up with the same float point list. Should I write a test for it?

[dr0id]

sure, here it is:

[Conz3D]

Thank you very much. But I'm sorry to say that it doesn't look like the fix I have hoped for. The polys are overshooting to -x and -y. So it seems it is still simply trunkated. Will investigate further. I'll write a bit more meaningful test in the next days.