More poly2

2 files changed, 168 insertions, 18 deletions

diff --git a/newplan b/newplan
index b11d26f..16f5af8 100644
--- a/newplan
+++ b/newplan
@@ -41,6 +41,10 @@ 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)
@@ -51,7 +55,7 @@ rasterize (polygon, int x, int y, int width, int height)
 
 	yi = next_sample_y (y); // yi = y << 8;
 
-	aet = update_aet (aet, yi);
+	aet = update_aet (aet, yi, scanline=true);
 
 	/* For each scanline */
 	while (fixed_to_int (yi) < height)
@@ -61,17 +65,22 @@ rasterize (polygon, int x, int y, int width, int height)
 		   case VERTICALS/NON_OVERLAP/etc.
 		 */
 
-	        for (i = 0; i < N_GRID_Y; ++i)
+	        for (i = 0; i < N_GRID_Y - 1; ++i)
 	        {
 		    for_each (aet)
-			step edge (emit);
+			small step edge (emit);
 
-	            yi = step_y (yi);
+	            yi = small_step_y (yi);
 
-		    aet = update_aet (aet);
+		    aet = update_aet (aet, scanline=false);
                 }
 
-		// emit scan line 
+		for_each (aet)
+			 big_step edge (emit);
+
+		yi = big_step_y (yi); // yi = fixed_floor (yi + fixed_1);
+
+		aet = update_aet (yi, scanline=true);
 	}
 }
 
diff --git a/poly2.c b/poly2.c
index 1631d0f..0d8632b 100644
--- a/poly2.c
+++ b/poly2.c
@@ -3,6 +3,7 @@
 #include <math.h>
 #include <stdint.h>
 #include <string.h>
+#include <assert.h>
 
 typedef int32_t			fixed_t;
 
@@ -125,6 +126,7 @@ typedef struct polygon_t polygon_t;
 typedef struct point_t point_t;
 typedef struct seg_t seg_t;
 typedef struct active_t active_t;
+typedef struct global_t global_t;
 
 struct point_t
 {
@@ -152,10 +154,7 @@ typedef struct uninitialized_edge_t uninitialized_edge_t;
 typedef enum
 {
     VERTICAL,
-    SHORT_NE,
-    SHORT_NW,
-    SHORT_SE,
-    SHORT_SW,
+    SHORT,
     LONG,
     UNINITIALIZED
 } edge_type_t;
@@ -163,23 +162,23 @@ typedef enum
 struct edge_common_t
 {
     edge_type_t	type;
+    sample_t	bottom;
+    int		dir;
 };
 
 struct short_edge_t
 {
+    sample_t	xi;
     uint32_t	e;
     uint32_t	delta_e_big_x;
     uint32_t	delta_e_small_x;
     uint32_t	delta_e_big_y;
     uint32_t	delta_e_small_y;
-    sample_t	xi;
-    sample_t	bottom;
 };
 
 struct vertical_edge_t
 {
     sample_t	xi;
-    sample_t	bottom;
 };
 
 struct long_edge_t
@@ -187,16 +186,73 @@ struct long_edge_t
     /* stuff here, pointer */
 };
 
+struct uninitialized_edge_t
+{
+    sample_t	   yi;
+    const seg_t   *seg;
+    const point_t *top;
+    const point_t *bottom;
+};
+
 union edge_t
 {
-    edge_type_t		type;
-    edge_common_t	common;
-    short_edge_t	short_;
-    long_edge_t		long_;
-    vertical_edge_t	vertical;
+    edge_type_t		 type;
+    edge_common_t	 common;
+    vertical_edge_t	 vertical;
+    short_edge_t	 short_;
+    long_edge_t		 long_;
+    uninitialized_edge_t uninitialized;
 };
 
 static void
+edge_init (edge_t *edge, sample_t first_yi)
+{
+    const point_t *top = edge->uninitialized.top;
+    const point_t *bottom = edge->uninitialized.bottom;
+    const seg_t *seg = edge->uninitialized.seg;
+
+    edge->common.dir = 2 * (top == &seg->p1) - 1;
+    edge->common.bottom = next_sample_y (bottom->y);
+
+    if (top->x == bottom->x)
+    {
+	/* vertical */
+	edge->common.type = VERTICAL;
+	edge->vertical.xi = next_sample_x (top->x);
+    }
+    else
+    {
+	fixed_t dx, dy;
+
+	dy = bottom->y - top->y;
+	dx = bottom->x - top->x;
+
+	assert (dy > 0);
+
+	if (dy < int_to_fixed (1 << (16 - FIXED_BITS)) &&
+	    dx < int_to_fixed (1 << (16 - FIXED_BITS)) &&
+	    dx < 8 * dy)
+	{
+	    /* short */
+	    sample_t xi = next_sample_x (top->x);
+
+	    edge->short_.xi = xi;
+	    edge->short_.e =
+		(sample_to_pos_x (xi) - top->x) * dy -
+		(sample_to_pos_y (first_yi) - top->y) * dx;
+	    edge->short_.delta_e_big_x = BIG_STEP_X * dy;
+	    edge->short_.delta_e_small_x = SMALL_STEP_X * dy;
+	    edge->short_.delta_e_big_y = BIG_STEP_Y * dx;
+	    edge->short_.delta_e_small_y = SMALL_STEP_Y * dx;
+	}
+	else
+	{
+	    /* long */
+	}
+    }
+}
+
+static void
 get_points (const seg_t *seg, const point_t **top, const point_t **bottom)
 {
     const point_t *t, *b;
@@ -254,6 +310,91 @@ polygon_create (seg_t *segments, int n_segments)
     return polygon;
 }
 
+struct global_t
+{
+    edge_t *	last;
+    edge_t	edges[1];
+};
+
+static global_t *
+create_global (polygon_t *polygon, int x, int y, int width, int height)
+{
+    global_t *global;
+    int i;
+
+    global = malloc (
+	sizeof (global_t) + (polygon->n_segments - 1) * sizeof (edge_t));
+
+    global->last = &(global->edges[0]);
+
+    for (i = 0; i < polygon->n_segments; ++i)
+    {
+	const seg_t *seg = &(polygon->segments[i]);
+	const point_t *top, *bottom;
+
+	get_points (seg, &top, &bottom);
+
+	if (fixed_to_int (top->y) >= y + height)
+	    break;
+
+	if (fixed_to_int (bottom->y) >= y)
+	{
+	    uninitialized_edge_t *u = &(global->last++->uninitialized);
+
+	    u->seg = seg;
+	    u->top = top;
+	    u->bottom = bottom;
+	    u->yi = next_sample_y (u->top->y);
+	}
+    }
+
+    return global;
+}
+
+struct active_t
+{
+    global_t *	global;
+    edge_t *	current;
+    int		n_edges;
+    edge_t *	edges[1];
+};
+
+static active_t *
+create_active (global_t *global)
+{
+    active_t *active = malloc (sizeof *active);
+
+    active->global = global;
+    active->current = &(global->edges[0]);
+    active->n_edges = 0;
+
+    return active;
+}
+
+static active_t *
+update_active (active_t *active, sample_t yi)
+{
+    while (active->current < active->global->last   &&
+	   active->current->uninitialized.yi <= yi)
+    {
+	edge_init (active->current, yi);
+
+	/* FIXME: this should be made more efficient */
+	active = realloc (
+	    active, sizeof (*active) + active->n_edges * sizeof (edge_t *));
+	active->edges[active->n_edges++] = active->current++;
+    }
+
+    /* sort edges */
+    return active;
+}
+
+static void
+polygon_rasterize (polygon_t *polygon, int x, int y, int width, int height)
+{
+    global_t *global = create_global (polygon, x, y, width, height);
+}
+
 int
 main (int argc, char **argv)
 {