Scanline Rasterization

Looping trough every edge for every pixel is very inefficient. In this section we're going to optimize the DrawPolygon function by tightly coupling it with the code PointInPolygon function.

Since all we care about are the edges that cross the current scanline, an easy optimization is to keep an active list of edges and only loop trough those. As we're moving from scanline to scanline, we can check if an edge started or stopped crossing the scanline, and update the active edge list accordingly.

We will need to find where each active edge crosses the scanline, and sort the active edge list left to right based on this coordinate. This makes sure we count every edge as it's passed when rasterizing the scanline. Any time an edge is passed, update the winding number of the scanlie accordingly.

Implementation

We will need to know where each edge intersects the scanline. We're going to create a RenderEdge structure to help keep track of this data.

struct RenderEdge {
    Point p0;
    Point p1;
    float x;
};

Follow these steps to implement the algorithm described above. The sample code adds 0.5f to all pixel coordinates because it assumes the pixel coordinate represents the center of the pixel.

Sort all edges by their topmost y coordinate
Maintain a list of active edgess for the current scanline
For each scanline
- Add any edge whose top-most point is above the scanline to the active edge list
- Remove any edge whose bottom-most point is above the scanline from the active edge list
- Find where each eactive edge crosses the scanline (we know the y coordiante is that of the scan line, find the x coordinate)
- Sort active edges (left to right) by their intersection point with the scanline
- Initialize winding number to 0 and loop trough all intersection (x coordinates)
  - Any time the x coordinate passes an edge, update the winding number
  - Shade pixel if the winding number is not 0.

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;

    // Build a list of edges for the polygon
    std::vector< RenderEdge > edges;
    for (int c = 0, cSize = poly.size(); c < cSize; ++c) {
        const Contour& countour = poly[c];
        int numPoints = countour.size();
        for (int p = 0; p < numPoints; ++p) {
            const Point& point = countour[p];
            const Point& next = countour[(p + 1) % numPoints];
            edges.push_back(RenderEdge{ point, next, 0.0f });
        }
    }

    std::sort(edges.begin(), edges.end(), TopmostY());
    std::list< RenderEdge > active;

    unsigned int numEdges = edges.size();
    unsigned int firstEdgeBelowScanline = 0;

    for (int y = s_y; y <= e_y; ++y) {
        // Sample from center of pixel
        float sample_y = float(y) + 0.5f;

        // Add any edges that start above the scanline
        while (firstEdgeBelowScanline < numEdges) {
            const RenderEdge& edge = edges[firstEdgeBelowScanline];
            float min_y = edge.p0.y < edge.p1.y ? edge.p0.y : edge.p1.y;
            if (min_y <= sample_y) { // Inclusive of topmost point
                // firstEdgeBelowScanline was above the scanline
                active.push_back(edges[firstEdgeBelowScanline]);
                firstEdgeBelowScanline += 1;
            }
            else { // firstEdgeBelowScanline is below the scanline
                break;
            }
        }

        // Horizontal edges are not a problem, 
        // they are added above and removed immediateley below

        // Remove any active edges that end above the scanline
        for (std::list< RenderEdge >::iterator it = active.begin(); it != active.end();) {
            float max_y = it->p0.y > it->p1.y ? it->p0.y : it->p1.y;

            if (max_y <= sample_y) { // Exclusive of bottom most point
                it = active.erase(it);
            }
            else { // Iterator crosses scanline, move to next one
                it++;
            }
        }

        // Find the x value of where each edge intersects the scanline
        for (std::list< RenderEdge >::iterator it = active.begin(), end = active.end(); it != end; ++it) {
            if (fabs(it->p0.x - it->p1.x) < 0.0001f) { // Vertical
                it->x = it->p0.x;
            }
            else {
                float m = (it->p1.y - it->p0.y) / (it->p1.x - it->p0.x);
                float b = it->p0.y - m * it->p0.x;
                it->x = (sample_y - b) / m;
            }
        }

        // Sort edges by ascending x intersection order
        active.sort(LeftmostXIntersection);

        // Init winding for scanline
        int winding = 0;

        // Draw scanline
        std::list< RenderEdge >::iterator it = active.begin();
        std::list< RenderEdge >::iterator end = active.end();
        for (int x = s_x; x <= e_x; ++x) {
            float sample_x = float(x) + 0.5f;
                
            // If any edges are on the left of the sample point
            // update the running winding number and remove the edge
            while (it != end && it->x < sample_x) {
                // Crossing scanline top to bottom
                if (it->p0.y <= sample_y && it->p1.y > sample_y) { 
                    winding -= 1;
                }
                // Crossing scanline bottom up
                else if (it->p1.y <= sample_y && it->p0.y > sample_y) { 
                    winding += 1;
                }
                ++it;
            }
                
            if (winding != 0) {
                DrawPixel(_x + x, _y + y, r, g, b);
            }
        }
    }
}

These are the sorting functions for the above sample:

struct TopmostY {
    inline bool operator() (const RenderEdge& left, const RenderEdge& right) {
        float lY = left.p0.y < left.p1.y ? left.p0.y : left.p1.y;
        float rY = right.p0.y < right.p1.y ? right.p0.y : right.p1.y;
        return lY < rY;
    }
};

bool LeftmostXIntersection(const RenderEdge& left, const RenderEdge& right) {
    return left.x < right.x;
}