rasterizing

2 files changed, 89 insertions, 10 deletions

diff --git a/build.sh b/build.sh
index 6e02d64..6d5710f 100755
--- a/build.sh
+++ b/build.sh
@@ -1,2 +1,2 @@
-gcc -Wall `pkg-config --cflags --libs gtk+-2.0` poly3.c
+gcc -g -Wall `pkg-config --cflags --libs gtk+-2.0` poly3.c
 
diff --git a/poly3.c b/poly3.c
index ea580f2..d8802d9 100644
--- a/poly3.c
+++ b/poly3.c
@@ -112,6 +112,12 @@ next_sample_x (fixed_t x)
     return i + sample_no;
 }
 
+static sample_t
+int_to_sample (int i)
+{
+    return i << FIXED_BITS;
+}
+
 typedef struct polygon_t polygon_t;
 typedef struct point_t point_t;
 typedef struct seg_t seg_t;
@@ -256,6 +262,12 @@ edge_init (edge_t *edge, sample_t first_yi)
     {
 	int64_t dx, dy;
 
+	printf ("Activating (%f %f %f %f)\n",
+		fixed_to_double (top->x),
+		fixed_to_double (top->y),
+		fixed_to_double (bottom->x),
+		fixed_to_double (bottom->y));
+	    
 	dx = (bottom->x - top->x);
 	dy = (bottom->y - top->y);
 
@@ -266,7 +278,7 @@ edge_init (edge_t *edge, sample_t first_yi)
 	edge->long_.delta_e_small_x = SMALL_STEP_X * dy;
 	edge->long_.delta_e_big_y = BIG_STEP_Y * dx;
 	edge->long_.delta_e_small_y = SMALL_STEP_Y * dx;
-
+	
 	long_edge_update_error (&edge->long_);
     }
 }
@@ -360,6 +372,9 @@ create_global (polygon_t *polygon, int x, int y, int width, int height)
 
 	get_points (seg, &top, &bottom);
 
+	if (top->y == bottom->y)
+	    continue;
+	
 	if (fixed_to_int (top->y) >= y + height)
 	    break;
 
@@ -367,6 +382,8 @@ create_global (polygon_t *polygon, int x, int y, int width, int height)
 	{
 	    uninitialized_edge_t *u = &(global->last++->uninitialized);
 
+	    printf ("adding %x %x\n", top->x, top->y);
+	    
 	    u->seg = seg;
 	    u->top = top;
 	    u->bottom = bottom;
@@ -374,6 +391,8 @@ create_global (polygon_t *polygon, int x, int y, int width, int height)
 	}
     }
 
+    printf ("%d segments\n", global->last - global->edges);
+    
     return global;
 }
 
@@ -397,9 +416,34 @@ create_active (global_t *global)
     return active;
 }
 
+static int
+compare_active (const void *v1, const void *v2)
+{
+    const edge_t *e1 = *(const edge_t **)v1;
+    const edge_t *e2 = *(const edge_t **)v2;
+
+    return e1->common.xi - e2->common.xi;
+}
+
 static active_t *
 update_active (active_t *active, sample_t yi)
 {
+    int i, d;
+
+    /* eliminate dead edges */
+    d = 0;
+    for (i = 0; i < active->n_edges; ++i)
+    {
+	edge_t *edge = active->edges[i];
+
+	if (yi >= edge->common.bottom)
+	    d++;
+	else if (d)
+	    active->edges[i - d] = edge;
+    }
+
+    active->n_edges -= d;
+
     while (active->current < active->global->last   &&
 	   active->current->uninitialized.yi <= yi)
     {
@@ -411,17 +455,27 @@ update_active (active_t *active, sample_t yi)
 	active->edges[active->n_edges++] = active->current++;
     }
 
-    /* FIXME: sort edges */
+    qsort (active->edges, active->n_edges, sizeof (edge_t *), compare_active);
+    
     return active;
 }
 
 static void
+emit (sample_t xi, sample_t yi)
+{
+    printf ("(%8x, %8x)  =>   (%f, %f)\n",
+	    xi, yi,
+	    fixed_to_double (sample_to_pos_x (xi)),
+	    fixed_to_double (sample_to_pos_y (yi)));
+}
+
+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);
     active_t *active = create_active (global);
-    sample_t yi = y << FIXED_BITS;
-    sample_t end = (y + height) << FIXED_BITS;
+    sample_t yi = int_to_sample (y);
+    sample_t end = int_to_sample (y + height);
 
     while (yi < end)
     {
@@ -433,9 +487,11 @@ polygon_rasterize (polygon_t *polygon, int x, int y, int width, int height)
 	{
 	    for (j = 0; j < active->n_edges; ++j)
 	    {
-		/* emit yi, edge->xi */
-
-		edge_small_step (active->edges[j]);
+		edge_t *edge = active->edges[j];
+		
+		emit (edge->common.xi, yi);
+		
+		edge_small_step (edge);
 	    }
 
 	    yi++;
@@ -446,17 +502,40 @@ polygon_rasterize (polygon_t *polygon, int x, int y, int width, int height)
 
 	for (j = 0; j < active->n_edges; ++j)
 	{
-	    /* emit ((yi | (N_GRID_Y - 1), edge->xi), */
+	    edge_t *edge = active->edges[j];
 
-	    edge_big_step (active->edges[j]);
+	    emit (edge->common.xi, yi);
+	    
+	    edge_big_step (edge);
 	}
 
 	yi = fixed_floor (yi + fixed_1);
     }
 }
 
+#define df(a) double_to_fixed(a)
+
 int
 main (int argc, char **argv)
 {
+    seg_t pentagons[] = {
+	{ { df (10.2), df (2.2)}, { df (11.3),  df (2.2) } },
+	{ { df (11.3), df (2.2) }, { df (15.7),  df (5.5) } },
+	{ { df (15.7), df (5.5) }, { df (20.8), df (15.8) } },
+	{ { df (20.8), df (15.8) }, { df (13.2), df (25.2) } },
+	{ { df (13.2), df (25.2) }, { df (10.2),  df (2.2) } },
+
+	{ { df (15 + 10.2), df (2.2)}, { df (15 + 11.3),  df (2.2) } },
+	{ { df (15 + 11.3), df (2.2) }, { df (15 + 15.7),  df (5.5) } },
+	{ { df (15 + 15.7), df (5.5) }, { df (15 + 20.8), df (15.8) } },
+	{ { df (15 + 20.8), df (15.8) }, { df (15 + 13.2), df (25.2) } },
+	{ { df (15 + 13.2), df (25.2) }, { df (15 + 10.2),  df (2.2) } }
+    };
+
+    polygon_t *polygon = polygon_create (
+	pentagons, sizeof (pentagons) / sizeof (pentagons[0]));
+
+    polygon_rasterize (polygon, 0, 0, 45, 30);
+    
     return 0;
 }