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".

See the wikipedia entries for:

• non-zero winding rule
• 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

You can check out the polygon fill routine in Pygame. Look at the draw_fillpoly function.

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.

Answer 3

• 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 4

For a robust implimentation of the "even-odd rule"

See Darel Rex Finley's Efficient Polygon Fill, or Blender's version of it.

This is an odd/even filling method which supports self intersecting lines, without needing complex code to detect such situations, and doesn't depend on winding (the polygon can be reversed and yield the same results).

---

Update, I made an optimized version of Darel Rex's method that avoids looping over all coordinates for each y-pixel.

Stand alone implementations:

• C99.
• Rust (with tests).

While speedup will likely be exponential, From a quick test, its around 7.5x faster (11x when removing round call), using an arbitrary hand drawn scribble over a 2540x1600 region, YMMV.