Edges come in different type: *horizontal* which are ignored. This is when dy is 0 *vertical* which is when the edge is vertical *short* which is when dy and dx are both shorter than say 8 pixels. and also dx / dy < 4 <=> dx < 4 * dy Probably further split into *short forward/backward* to avoid the extra test. Or even short NORTH_WEST short NORTH_EAST short SOUTH_WEST short SOUTH_EAST since we do need to keep track of up/down for winding rule purposes. *long* otherwise *uninitialized* which is before the edge has been added to the aet An edge can be stepped an arbitrary amount, or it can be stepped one step. A *long* edge uses runslice (with a division). It is stored as a pointer to allocated memory, since we assume these will be rare. A *short* edge uses bresenham. It also does internal book keeping in 32 bit integers. All edges Potential optimizations: - Polygons could store the edges as a kind of BSP tree to allow quick access to arbitrary sub-rectangles. - Rectilinear polygons could be recognized - Rectilinear integer-aligned polygons could be recognized. Write it top-down. rasterize (polygon, int x, int y, int width, int height) { sample_t yi; get = get_global_edges (polygon); yi = next_sample_y (y); // yi = y << 8; aet = update_aet (aet, yi, scanline=true); /* For each scanline */ while (fixed_to_int (yi) < height) { /* later: switch (aet->state) case VERTICALS/NON_OVERLAP/etc. */ for (i = 0; i < N_GRID_Y - 1; ++i) { for_each (aet) small step edge (emit); yi = small_step_y (yi); aet = update_aet (aet, scanline=false); } for_each (aet) big_step edge (emit); yi = big_step_y (yi); // yi = fixed_floor (yi + fixed_1); aet = update_aet (yi, scanline=true); } } update_aet (yi) for each global edge if y0 <= yi add to aet initialize long_step (yi - y0) else break; /* global edges are sorted in YX order */ sort aet Later on, update_aet() should keep track of various properties: - All edges vertical for one or more scanlines - The edges are longer than one scanline, and they don't cross each other. basically, if the next slope is bigger than or equal to the current one's: if (next dx/dy >= current dx dy) which is equivlaent to next dx * current dy >= current dx * next dy Since dy's are always positive. If this is the case, we can track it for a full range of scanlines. - How many active edges there are. If there aren't many, then we can use a simpler sort such as insertion sort. Note this means update_aet() should do two different things depending on whether it's moving between subrows and scanlines. Testing: - Generate a ton of polygons in a naive way. Make sure they never change. - Rasterize polygons that completely cover a rectangle. Make sure there are no seams. - Rasterize on polygon that consists of many pieces that together cover an entire rectangle.