Drawing Polygons

In this blog, we're going to explore how to render anti aliased polygons, the complete code samples are available here. For this blog, a polygon is a collection of contours. Each contour is a collection of points. The direction of the contour matters, clockwise polygons will be filled while counter clockwise polygons represent a hole in the geometry. Let's make a Point structure, and typedef the Contour and Polygon types.

struct Point {
    float x;
    float y;
};
    
struct BoundingBox {
    Point min;
    Point max;
};

typedef std::vector< Point > Contour;
typedef std::vector< Contour > Polygon;

Point in polygon

To determine if a point is inside a polygon, we must find it's winding number. The winding number counds how many times the polygon travels around the point counter clockwise. If the winding number is not 0, the point is inside the polygon.

We only need edges that cross the scanline of the point to find it's winding number. The scanline of the point is a horizontal line with y = point.y. The direction of an edge is important. The following demo shows which edges are considered when rasterizing a scanline. The red scanline will follow your mouse, purple edges are the ones that cross the scan line.

Canvas support required

Edges that cross the scanline top to bottom will decrease the winding number, but only if the point is on the right side of the edge. Wdges that cross bottom to top will increase the winding number, only if the point is on the left side of the edge. The cross product can be used to tell what side of an edge a point lies on.

We can think of a polygon as a 3D object that happens to be drawn on the xy plane with a z component of 0. Given an edge and a point, find a vector from the start point of the edge to the test point and another vector from the end point of the edge to the test point. Take the cross product of these two vectors. The direction of the z axis will tell us if a point is on the right or left side of the edge. If the edge crosses the scanline top to bottom, a positive z axis means the test point is on the right of the edge. If the edge crosses bottom to top, a negative z axis means the test point is on the left of the edge.

The algorithm we have discussed so far is outlined below. For a more in-depth explanation of how the winding number works, check out Dan Sunday's Inclusion of a Point in a Polygon, also available in Practical Geometry Algorithms

bool PointInPolygon(const Point& point, const Polygon& poly) {
    BoundingBox bbox = GetBoundingBox(poly);
    if (point.x < bbox.min.x || point.x > bbox.max.x) {
        return false;
    }
    if (point.y < bbox.min.y || point.y > bbox.max.y) {
        return false;
    }

    int winding = 0;
    for (int contour = 0, numContours = poly.size(); contour < numContours; ++contour) {
        const Contour& c = poly[contour];
        for (int pt = 0, numPoints = c.size(); pt < numPoints; ++pt) {
            const Point& p = c[pt];
            const Point& n = c[(pt + 1) % numPoints];

            Point toStart { p.x - point.x, p.y - point.y }; 
            Point toEnd { n.x - point.x, n.y - point.y }; 
            float crossZ = toStart.x * toEnd.y - toStart.y * toEnd.x;

            if (p.y <= point.y && n.y > point.y) { // Crossing scanline top to bottom
                if (crossZ > 0) { // Point is on right of edge
                    winding -= 1;
                }
            }
            else if (n.y <= point.y && p.y > point.y) { // Crossing scanline bottom up
                if (crossZ < 0) { // Point is on left of edge
                    winding += 1;
                }
            }
        }
    }

    return winding != 0;
}

Drawing a polygon

The easiest way to draw a polygon is to loop trough every pixel inside the polygons bounding box, and test if the point is inside the polygon or not. If a point is inside, it gets shaded. In the next section we'll explore optimizing the drawing code.

void DrawPolygon(int _x, int _y, const Polygon& poly, unsigned char r, unsigned char g, unsigned char b) {
    BoundingBox bbox = GetBoundingBox(poly);
    int s_x = bbox.min.x < 0.0f ? bbox.min.x - 0.5f : bbox.min.x + 0.5f;
    int e_x = bbox.max.x < 0.0f ? bbox.max.x - 0.5f : bbox.max.x + 0.5f;
    int s_y = bbox.min.y < 0.0f ? bbox.min.y - 0.5f : bbox.min.y + 0.5f;
    int e_y = bbox.max.y < 0.0f ? bbox.max.y - 0.5f : bbox.max.y + 0.5f;

    for (int y = s_y; y <= e_y; ++y) {
        for (int x = s_x; x < e_x; ++x) {
            if (PointInPolygon(Point{ (float)x, (float)y }, poly)) {
                DrawPixel(x + _x, y + _y, r, g, b);
            }
        }
    }
}