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

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.