summaryrefslogtreecommitdiff
path: root/newplan
diff options
context:
space:
mode:
Diffstat (limited to 'newplan')
-rw-r--r--newplan126
1 files changed, 126 insertions, 0 deletions
diff --git a/newplan b/newplan
new file mode 100644
index 0000000..dbdb57c
--- /dev/null
+++ b/newplan
@@ -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.