new plan

2 files changed, 138 insertions, 12 deletions

diff --git a/dda.c b/dda.c
index 52ceb20..3df28c5 100644
--- a/dda.c
+++ b/dda.c
@@ -404,14 +404,17 @@ make_get (polygon_t *polygon, int x, int y, int width, int height,
 }
 
 static edge_t **
-update_aet (edge_t **aet, sample_t y, edge_t **global, int *n_edges)
+update_aet (edge_t **aet, int *n_active,
+	    sample_t y, edge_t **global, int *n_edges)
 {
     int i;
+    int new_size;
     int n_new;
 
     for (i = 0; i < *n_edges; ++i)
     {
-	/* add stuff from global [i] if it has become active */
+	edge_t *e = global[i];
+
     }
 
     *n_edges -= n_new;
@@ -434,28 +437,25 @@ polygon_rasterize (polygon_t *polygon, int x, int y, int width, int height)
     fixed_t min;
     sample_t yi;
     edge_t **aet;
+    int n_active;
 
     next_edge = get = make_get (polygon, x, y, width, height, &n_edges, &min);
 
     yi = next_sample_y (min);
 
-    aet = update_aet (NULL, yi, &next_edge, &n_edges);
+    n_active = 0;
+    aet = update_aet (NULL, &n_active, yi, &next_edge, &n_edges);
 
     while (fixed_to_int (yi) < y + height)
     {
-	edge_t **active;
-
-	active = aet;
-	while (*active)
-	{
-	    edge_step (*active, yi, poly_emit, NULL);
+	int i;
 
-	    active++;
-	}
+	for (i = 0; i < n_active; ++i)
+	    edge_step (aet[i], yi, poly_emit, NULL);
 
 	yi = step_y (yi);
 
-	aet = update_aet (aet, yi, &next_edge, &n_edges);
+	aet = update_aet (aet, &n_active, yi, &next_edge, &n_edges);
     }
 
     /* First step all the edges to the top of the bounding box */
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.