More poly work

1 files changed, 76 insertions, 18 deletions

diff --git a/dda.c b/dda.c
index d83dea9..52ceb20 100644
--- a/dda.c
+++ b/dda.c
@@ -21,6 +21,9 @@ typedef int32_t			fixed_t;
 #define fixed_mod_2(f)          ((f) & (fixed1 | fixed_1_minus_e))
 #define fixed_max_int           ((fixed_t)((0xffffffff << FIXED_BITS) & ~0x80000000))
 
+#define FIXED_MIN		((fixed_t)0x80000000)
+#define FIXED_MAX		((fixed_t)0x7fffffff)
+
 #define fixed_to_double(f)      ((double) ((f) * (1 / (double) fixed_1)))
 #define double_to_fixed(d)      ((fixed_t) ((d) * fixed_1))
 
@@ -110,6 +113,15 @@ next_sample_x (fixed_t x)
     return i + sample_no;
 }
 
+static sample_t
+step_y (sample_t yi)
+{
+    if (fixed_frac (yi) == N_GRID_Y - 1)
+	return fixed_floor (yi + fixed_1);
+    else
+	return yi + 1;
+}
+
 typedef struct edge_t edge_t;
 typedef struct seg_t seg_t;
 typedef struct point_t point_t;
@@ -181,7 +193,7 @@ typedef void (* emitter_t) (sample_t x, sample_t y, void *data);
  * normal.
  */
 static void
-edge_step (edge_t *edge, int *yi, emitter_t emit, void *data)
+edge_step (edge_t *edge, sample_t yi, emitter_t emit, void *data)
 {
     if (edge->delta_e_small_y >= 0)
     {
@@ -225,19 +237,12 @@ edge_step (edge_t *edge, int *yi, emitter_t emit, void *data)
 	}
     }
 
-    emit (edge->xi, *yi, data);
+    emit (edge->xi, yi, data);
 
-    if (fixed_frac (*yi) == N_GRID_Y - 1)
-    {
+    if (fixed_frac (yi) == N_GRID_Y - 1)
 	edge->e -= edge->delta_e_big_y;
-	(*yi) += fixed_1;
-	(*yi) = fixed_floor (*yi);
-    }
     else
-    {
 	edge->e -= edge->delta_e_small_y;
-	(*yi)++;
-    }
 }
 
 static void
@@ -276,9 +281,11 @@ dda (test_data_t *testdata)
     yi = next_sample_y (y0);
     while (yi < edge.bottom)
     {
-	edge_step (&edge, &yi, emit, &(testdata->points[i]));
+	edge_step (&edge, yi, emit, &(testdata->points[i]));
 
 	i += 2;
+
+	yi = step_y (yi);
     }
 #if 0
     printf ("} \n},\n");
@@ -354,17 +361,23 @@ polygon_create (seg_t *segments, int n_segments)
     return polygon;
 }
 
+#define MIN(a,b)	(((a) < (b))? (a) : (b))
+
 static edge_t *
-make_get (polygon_t *polygon, int x, int y, int width, int height, int *n)
+make_get (polygon_t *polygon, int x, int y, int width, int height,
+	  int *n, fixed_t *m)
 {
     edge_t *get;
     int n_edges;
+    fixed_t min;
     int i;
 
     get = malloc (polygon->n_segments * sizeof (edge_t));
 
     n_edges = 0;
 
+    min = FIXED_MAX;
+
     /* Find the relevant edges */
     for (i = 0; i < polygon->n_segments; ++i)
     {
@@ -378,6 +391,8 @@ make_get (polygon_t *polygon, int x, int y, int width, int height, int *n)
 
 	if (fixed_to_int (bottom->y) >= y)
 	{
+	    min = MIN (top->y, min);
+
 	    edge_init (&(get[n_edges++]),
 		       top->x, top->y, bottom->x, bottom->y,
 		       (top == &(seg->p1))? DOWN : UP);
@@ -388,21 +403,64 @@ make_get (polygon_t *polygon, int x, int y, int width, int height, int *n)
     return get;
 }
 
+static edge_t **
+update_aet (edge_t **aet, sample_t y, edge_t **global, int *n_edges)
+{
+    int i;
+    int n_new;
+
+    for (i = 0; i < *n_edges; ++i)
+    {
+	/* add stuff from global [i] if it has become active */
+    }
+
+    *n_edges -= n_new;
+
+    /* sort the aet */
+
+    return NULL;
+}
+
+static void
+poly_emit (sample_t xi, sample_t yi, void *data)
+{
+}
+
 static void
 polygon_rasterize (polygon_t *polygon, int x, int y, int width, int height)
 {
     int n_edges;
-    edge_t *get;
-    int i;
+    edge_t *get, *next_edge;
+    fixed_t min;
     sample_t yi;
+    edge_t **aet;
 
-    get = make_get (polygon, x, y, width, height, &n_edges);
+    next_edge = get = make_get (polygon, x, y, width, height, &n_edges, &min);
 
-    /* First step all the edges to the top of the bounding box */
-    for (i = 0; i < n_edges; ++i)
+    yi = next_sample_y (min);
+
+    aet = update_aet (NULL, 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);
+
+	    active++;
+	}
+
+	yi = step_y (yi);
+
+	aet = update_aet (aet, yi, &next_edge, &n_edges);
     }
+
+    /* First step all the edges to the top of the bounding box */
+
+    free (get);
 }
 
 int