{"id":218,"date":"2022-10-16T20:28:03","date_gmt":"2022-10-16T20:28:03","guid":{"rendered":"https:\/\/metareal.net\/blog\/?p=218"},"modified":"2022-10-16T20:28:03","modified_gmt":"2022-10-16T20:28:03","slug":"polygon-shape-filling","status":"publish","type":"post","link":"http:\/\/metareal.net\/blog\/?p=218","title":{"rendered":"Polygon Shape Filling"},"content":{"rendered":"\n

This entry describes a little spinoff (spun-in?) project that happened during game development.<\/p>\n\n\n\n

For all kinds of reasons, I needed a utility bitmap class. Just a place to load and save bitmaps and move them around. For example, on their way to become texture maps or font.<\/p>\n\n\n\n

Easy enough, for my purposes 8 bits each of RGBA is fine.<\/p>\n\n\n\n

class OmImageRgba8 : OmObjectBase\n{\npublic:\n    int width = 0;\n    int height = 0;\n    uint32_t *pixels = 0; \/\/ malloc'd, disposed with instance\n    OmImageRgba8(int width, int height);\n   ~OmImageRgba8();\n    void setPixel(int x, int y, uint32_t pixel);\n    uint32_t getPixel(int x, int y);\n\n    bool writeFile(std::string filePath);\n    static OmImageRgba8 *readFile(std::string filePath);\n}<\/code><\/pre>\n\n\n\n
So about ReadFile and WriteFile. I do love writing everything myself\u2026 up to a point. I\u2019m often put off my the complexity of using Other People\u2019s Code, when it becomes mired in a tangle of still more Library Dependencies. Makes it hard to build my project.<\/p>\n\n\n\n
Happily, I found \u201cplain old code\u201d libraries for PNG and JPG. By \u201cplain old code\u201d I mean, it\u2019s a small number of source code files that just work on a normal compiler.<\/p>\n\n\n\n
LODEPNG<\/a> <\/strong>by Lode Vandevenne for reading and writing PNG files. <\/p>\n\n\n\n
JPEG-COMPRESSOR<\/a><\/strong> by Rich Geldreich, for reading and writing JPG files.\u00a0 <\/p>\n\n\n\n
These were both very easy to integrate. The ::readFile() and ::writeFile() methods on OmImageRgba8 simply look at the file extension to choose which, and only work if it\u2019s .jpg or .png.<\/p>\n\n\n\n
More features crept in over time. Some images arrive Y-up, others Y-down, so ::flipY() was added.<\/p>\n\n\n\n
For debugging, it\u2019s handy to imprint text information onto a bitmap, so ::drawF(uint32_t color, const char *fmt, \u2026) was added. It uses a simple 8×8 pixel font. I came across this handy font some years ago, and must share its origin. The link is http:\/\/overcode.yak.net\/12. It was a small image which I decomposed into static C data.<\/p>\n\n\n\n
char font8x8[] = \n{\n\u2026\n0x08,0x49,0x2a,0x1c,0x2a,0x49,0x08,0x00,   \/\/ 0x2a '*'\n\/\/   . . . . @ . . . \n\/\/   . @ . . @ . . @ \n\/\/   . . @ . @ . @ . \n\/\/   . . . @ @ @ . . \n\/\/   . . @ . @ . @ . \n\/\/   . @ . . @ . . @ \n\/\/   . . . . @ . . . \n\/\/   . . . . . . . . \n0x08,0x08,0x08,0x7f,0x08,0x08,0x08,0x00,   \/\/ 0x2b '+'\n\/\/   . . . . @ . . . \n\/\/   . . . . @ . . . \n\/\/   . . . . @ . . . \n\/\/   . @ @ @ @ @ @ @ \n\/\/   . . . . @ . . . \n\/\/   . . . . @ . . . \n\/\/   . . . . @ . . . \n\/\/   . . . . . . . . \n\u2026\n};<\/code><\/pre>\n\n\n\n
The font was designed by John Hall, and on the website above, he also documents some other code and tech work, and some aeronautical items, and his descent and demise due to skin cancer. So I always think a few kind words of thanks to this unknown and lost fellow coder and this one part of his legacy that I use. Thanks John.<\/p>\n\n\n\n
And somewhere along the way I wanted to do some generative art, so added a basic antialiased Rectangle Fill method. Handles the edges and corners special for partial coverage, and fills the broad interior. Fun enough.<\/p>\n\n\n\n
\"\"<\/a>
(generative art)<\/sub><\/figcaption><\/figure>\n\n\n\n
But that slippery slope let up to September 2022 when I thought, All the cool kids have implemented a scanline polygon fill, it\u2019s time for me.<\/p>\n\n\n\n
Filling polygons is kind-of a big bother, keeping track of edge lists and numbers and stuff. Oh well! Computers and programmers love that kind of thing. Here\u2019s the basic approach.<\/p>\n\n\n\n
I\u2019ll define polygon as one or more closed loops of straight edges. The polygon is defined by the vertices, and each vertex is shared by two edges.<\/p>\n\n\n\n
For a simple polygon fill, we fill each pixel if and only if the center of the pixel is within the polygon. <\/p>\n\n\n\n
\"\"<\/a>
(A polygon with two paths)<\/sub><\/figcaption><\/figure>\n\n\n\n
(We\u2019ll discuss partial coverage later, I promise.)<\/p>\n\n\n\n
Essentially, we want to ask each and every pixel, \u201cIs the center of this pixel within the polygon.\u201d<\/p>\n\n\n\n
\"\"<\/a>
(Scanlines and centerpoints)<\/sub><\/figcaption><\/figure>\n\n\n\n
For each row (or \u201cscanline\u201d) we determine which edges encompass the something-point-5 part of the row. There will always be an even number. Then find the x-position of each of these. Then we fill in pairs, only those pixels within an x-pairs span.<\/p>\n\n\n\n
Some simple optimizations include:<\/p>\n\n\n\n
\u2022 presorting all the edges by lower-y value, so you just look at the next one to see if its in Y range<\/p>\n\n\n\n
\u2022 using an x-step value for each active edge, as we step down each scanline, because we do render the scanlines sequentially<\/p>\n\n\n\n
\u2022 discard horizontal edges, or any edge that doesn\u2019t traverse a Y-point-five boundary<\/p>\n\n\n\n
At first it did seem like a bother, but it all became easy to implement.<\/p>\n\n\n\n
What about antialiasing? The output looks pretty blocky without it. You can always render bigger and scale down, perfectly respectable solution.<\/p>\n\n\n\n
One easy thing I was tempted to try was, incorporate the x-position of each edge for partial coverage.<\/p>\n\n\n\n
\"\"<\/a>
[A simplistic and flawed anti-aliasing approach]<\/sub><\/figcaption><\/figure>\n\n\n\n
Alas this would only help the side edges, and not the top edges, and just look funny<\/p>\n\n\n\n
But\u2026 look closely at these illustrations. Go ahead, zoom in. They were all drawn using OmImageRgba8 and OmPolygon filling. And they\u2019re antialiased very nicely! Next post will demonstrate a nice antialiasing technique that builds on this edge-sorting, and doesn\u2019t involve downscaling.<\/p>\n","protected":false},"excerpt":{"rendered":"
This entry describes a little spinoff (spun-in?) project that happened during game development. For all kinds of reasons, I needed a utility bitmap class. Just a place to load and save bitmaps and move them around. For example, on their way to become texture maps or font. Easy enough, for my purposes 8 bits each […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[4],"class_list":["post-218","post","type-post","status-publish","format-standard","hentry","category-3","tag-engine"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"http:\/\/metareal.net\/blog\/index.php?rest_route=\/wp\/v2\/posts\/218","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/metareal.net\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/metareal.net\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/metareal.net\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/metareal.net\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=218"}],"version-history":[{"count":3,"href":"http:\/\/metareal.net\/blog\/index.php?rest_route=\/wp\/v2\/posts\/218\/revisions"}],"predecessor-version":[{"id":225,"href":"http:\/\/metareal.net\/blog\/index.php?rest_route=\/wp\/v2\/posts\/218\/revisions\/225"}],"wp:attachment":[{"href":"http:\/\/metareal.net\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=218"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/metareal.net\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=218"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/metareal.net\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=218"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}