diff options
Diffstat (limited to 'newplan')
-rw-r--r-- | newplan | 126 |
1 files changed, 126 insertions, 0 deletions
@@ -0,0 +1,126 @@ +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. + +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); + + /* 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; ++i) + { + for_each (aet) + step edge (emit); + + yi = step_y (yi); + + aet = update_aet (aet); + } + + // done scan line + } + + yi = next_sample (y); +} + +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. |