This continues from the previous images blog. After creating a simple set and line function, the next step is a polygon. A polygon is an enclosed shape made of three or more points. There are open polygons, where the exterior is drawn, and filled polygons.
Open polygons are the simplest. The line algorithm already exists, so just connect the various points. Just remember to connect the last point with the first point.
for (int i = 0; i < length - 1; i++) line_safe(point[i], point[i+1], color); line_safe(point[length-1],point[0],color);
Filled polygons are a touch more complex. The simplest idea is to draw an open polygon then use a fill algorithm to fill the interior. However how do you determine where to fill? Consider the following two polygons:
For polygon A, you can average the points and use that as a fill point. However, that algorithm would fail for polygon B. To solve this, use a scan line algorithm. Scan line by line and see how many times the scan line crosses a polygon line. If it's odd then color the pixel, otherwise don't color the pixel.
If you use this algorithm over the entire image, or from the lowest to highest Y value, then you get a filled polygon. Or at least it works most of the time. This algorithm doesn't work when a side is parallel to the scan lines. So before using this algorithm, you have to filter those out. If you don't then you'll have a dotted line and a solid line may extend to the edge of the image.
If that was the only issue then it would be simple. Filtering out horizontal lines is trivial. A great programmer considers all potential cases and creates algorithms that work for them. There are several key problems. The first is when the polygon uses too much detail. Consider this polygon:
The features in this polygon are beyond the resolution of the image. This simplest way to handle this is not to handle it. Leave it to the programmer to realize their mistake and work around it. The other way is to build anti-alias techniques into the line drawing algorithm. This partially shades a pixel depending on how much of the pixel it fills. These algorithms are more computationally expensive and it opens a big can of worms. It will be covered in another blog post along with general antialias techniques.
Another problem with the algorithm lies in polygons with crossed sides. For example, this polygon:
When writing a library, you can't assume a programmer will prevent side crossing. How the library deals with this is up to you. There's no right or wrong way, so long as it is documented. Some libraries may return an error while others may fill the enclosed areas, such as:
Generally, most libraries will fill what they can, crossed lines or not. The scan line algorithm handles it intrinsically.
The last problem with the scan-line technique involves vertices. Since it counts the number of lines it crosses, problems occur at the vertices. Consider the following two cases:
When a scan line runs through point A, it's counted twice so doesn't display anything. Yet that's a continuous line that should trigger drawing. You could fix this by ignoring one vertex in each line segment. For example, if a line segment runs from P1 to P2, then if the intercept is on P1 then it doesn't cross the line segment. This fixes the problem with point A however it also breaks point B. In point B, we want the point to be counted twice, so the scan line isn't toggled. Otherwise the pixels right of point B will colored in error. To fix this, you must check the type of intersection. If one segment is under the other then count that intersection once. This will correct that case.
Speed is the last consideration in this algorithm. For most polygons, speed isn't an issue but there's always a programmer who enters stupidly large numbers just to see what happens. (Or there is a bug that results in the same thing.) Any drawing algorithm should accept points beyond the limit of the image, because sometimes that's required. However if someone enters numbers in the trillions then it would take way too long to scan. So it's good practice to limit the scan lines to the image limits. This means the drawing algorithm must include intercept calculations for each line segment so it knows when it crosses line segments outside the image. In fact the entire algorithm could use geometry intercepts. When scanning a line, first create an equation for that line then calculate the intercept points with all other line segments. This can be done with simple highschool geometry. If the line segments intersect then calculate the start and stop points for each line segment. (Plenty of smaller optimizations can be applied.)
Once you have a list of intercepts, simply sort them. Since the scan lines are horizontal, you can sort by x value. Group the intercepts into pairs and those are your horizontal lines. After screening for image size, you can draw them with the previous line() function or just by using memset() or similar. Remember, horizontal pixels are next to each other in memory so drawing horizontal lines is very simple.
By now, some bright minds might have thought of another solution. For example, why not draw the border lines first then scan the image for those colored pixels and fill them in. This fails when lines are too detailed or when they cross. You could also make a complex algorithm that calculates all enclosed areas and fill them. This is done by calculating any line crossings, changing them into vertices then making each enclosed space into a separate polygon. This would work for most cases, but it may fail for some cases. Consider this polygon:
The scan line algorithm would only fill the tips while a general fill algorithm would fill everything. Neither method is right or wrong, the algorithm's behavior just needs to be documented and consistent. For a personal project, it's alright to be flexible. For a professional project, you are often given requirements. If the algorithm can't produce the output then it must be replaced, so requirements will matter. The largest problem with this algorithm is calculating the intercepts. Figuring out how to make new polygons, or which points to join, is the computationally inexpensive part. The expensive part will be finding the intercepts. This is an n2 algorithm because it has to compare each line segment with every other line segment. So the performance drops with polygons containing many sides. If you think that will never happen then you haven't learned splines.
This concludes the summary of polygon drawing algorithms. There will always be additional details, depending on the project requirements. Computer graphics is a good choice for personal projects. These kinds of programs help exercise problem solving and algorithm skills. Come up with new ideas and try them out. Learn what works and what doesn't work and use that to grow. In terms of a graphics library, polygon functions are just one of many.