Rasterizing a 2D polygon

Question

I need to create a binary bitmap from a closed 2D polygon represented as a list of points. Could you please point me to efficient and sufficiently simple algorithms to do that, or, even better, some C++ code?

Thanks a lot!

PS: I would like to avoid adding a dependency to my project. However if you suggest an open-source library, I can always look at the code, so it can be useful too.

Answer 1

The magic google phrase you want is either "non-zero winding rule" or "even odd polygon fill".

Both are very easy to implement and sufficiently fast for most purposes. With some cleverness, they can be made antialiased as well.

Answer 2

• Triangulate your polygon
• Raster each of the triangles (if you are using a GPU then it can do it for you instead, it's a primitive operation of GPUs)
  • If the triangle doesn't have a segment that is parallel to the x axis, then break it into two triangles with a line that is parallel to the x axis and goes through it's point with the median-y
  • Now the remaining task is to draw a triangle which has a segment that is parallel to the x axis. Such a triangle has a left-side segment and a right-side segment
  • Iterate the triangle's scan-lines (min-y to max-y). For each y calculate the left and right segments' points in that scanlines. Fill the scanline segment these two points (a simple memset).

Complexity is O(Area in pixels)

Answer 3

You can check out the polygon fill routine in Pygame. Look at the draw_fillpoly function near the end. http://www.seul.org/viewcvs/viewcvs.cgi/trunk/src/draw.c?rev=2617&root=PyGame&view=auto

The algorithm is pretty simple. It finds all the positions that each segment intersects along the Y axis. These intersections are sorted, and then horizontally fills each pair of intersections.

This will handle complex and intersecting shapes, but obviously you could crush this algorithm with large amounts of segments.