Beginning of polygon rasterizer

2 files changed, 228 insertions, 9 deletions

diff --git a/dda.c b/dda.c
index f41d06b..d83dea9 100644
--- a/dda.c
+++ b/dda.c
@@ -2,6 +2,7 @@
 #include <stdio.h>
 #include <math.h>
 #include <stdint.h>
+#include <string.h>
 
 typedef int32_t			fixed_t;
 
@@ -109,7 +110,26 @@ next_sample_x (fixed_t x)
     return i + sample_no;
 }
 
-typedef struct
+typedef struct edge_t edge_t;
+typedef struct seg_t seg_t;
+typedef struct point_t point_t;
+
+typedef enum
+{
+    UP, DOWN
+} dir_t;
+
+struct point_t
+{
+    fixed_t x, y;
+};
+
+struct seg_t
+{
+    point_t p1, p2;
+};
+
+struct edge_t
 {
     sample_t xi;
     sample_t bottom;
@@ -118,24 +138,34 @@ typedef struct
     int64_t delta_e_small_x;
     int64_t delta_e_big_y;
     int64_t delta_e_small_y;
-} edge_t;
+    dir_t dir;
+};
 
 static void
-edge_init (edge_t *edge, fixed_t x0, fixed_t y0, fixed_t x1, fixed_t y1)
+edge_init (edge_t *edge,
+	   fixed_t x0, fixed_t y0,
+	   fixed_t x1, fixed_t y1,
+	   dir_t dir)
 {
-    int64_t dx = (x1 - x0);
-    int64_t dy = (y1 - y0);
-    int yi = next_sample_y (y0);
+    int64_t dx, dy;
+    sample_t xi, yi;
 
-    edge->xi = next_sample_x (x0);
+    dx = (x1 - x0);
+    dy = (y1 - y0);
+    xi = next_sample_x (x0);
+    yi = next_sample_y (y0);
+
+    edge->xi = xi;
     edge->bottom = next_sample_y (y1);
     edge->e =
-	(int64_t)(sample_to_pos_x (edge->xi) - (int64_t)x0) * dy -
+	(int64_t)(sample_to_pos_x (xi) - (int64_t)x0) * dy -
 	(int64_t)(sample_to_pos_y (yi) - (int64_t)y0) * dx;
     edge->delta_e_big_x = BIG_STEP_X * dy;
     edge->delta_e_small_x = SMALL_STEP_X * dy;
     edge->delta_e_big_y = BIG_STEP_Y * dx;
     edge->delta_e_small_y = SMALL_STEP_Y * dx;
+
+    edge->dir = dir;
 }
 
 typedef void (* emitter_t) (sample_t x, sample_t y, void *data);
@@ -241,7 +271,7 @@ dda (test_data_t *testdata)
     int i = 0;
     int yi;
 
-    edge_init (&edge, x0, y0, x1, y1);
+    edge_init (&edge, x0, y0, x1, y1, DOWN);
 
     yi = next_sample_y (y0);
     while (yi < edge.bottom)
@@ -255,6 +285,126 @@ dda (test_data_t *testdata)
 #endif
 }
 
+static inline void
+get_points (const seg_t *seg, const point_t **top, const point_t **bottom)
+{
+    const point_t *t, *b;
+
+    if (seg->p1.y < seg->p2.y)
+    {
+	t = &(seg->p1);
+	b = &(seg->p2);
+    }
+    else
+    {
+	t = &(seg->p2);
+	b = &(seg->p1);
+    }
+
+    if (top)
+	*top = t;
+    if (bottom)
+	*bottom = b;
+}
+
+static int
+compare_seg (const void *v1, const void *v2)
+{
+    const seg_t *s1 = v1, *s2 = v2;
+    const point_t *p1, *p2;
+
+    get_points (s1, &p1, NULL);
+    get_points (s2, &p2, NULL);
+
+    if (p1->y != p2->y)
+    {
+	return p1->y - p2->y;
+    }
+    else if (p1->x != p2->x)
+    {
+	return p1->x - p2->x;
+    }
+    else
+    {
+	return 0;
+    }
+}
+
+typedef struct polygon_t polygon_t;
+
+struct polygon_t
+{
+    /* These segments are the original segments as passed in by
+     * the user. They are sorted in YX direction after being
+     * transformed by the inverse of the image's transformation.
+     */
+    seg_t *segments;
+    int    n_segments;
+};
+
+static polygon_t *
+polygon_create (seg_t *segments, int n_segments)
+{
+    polygon_t *polygon = malloc (sizeof *polygon);
+
+    polygon->segments = malloc (n_segments * sizeof (seg_t));
+    memcpy (polygon->segments, segments, n_segments * sizeof (seg_t));
+    qsort (polygon->segments, n_segments, sizeof (seg_t), compare_seg);
+
+    return polygon;
+}
+
+static edge_t *
+make_get (polygon_t *polygon, int x, int y, int width, int height, int *n)
+{
+    edge_t *get;
+    int n_edges;
+    int i;
+
+    get = malloc (polygon->n_segments * sizeof (edge_t));
+
+    n_edges = 0;
+
+    /* Find the relevant edges */
+    for (i = 0; i < polygon->n_segments; ++i)
+    {
+	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)
+	{
+	    edge_init (&(get[n_edges++]),
+		       top->x, top->y, bottom->x, bottom->y,
+		       (top == &(seg->p1))? DOWN : UP);
+	}
+    }
+
+    *n = n_edges;
+    return get;
+}
+
+static void
+polygon_rasterize (polygon_t *polygon, int x, int y, int width, int height)
+{
+    int n_edges;
+    edge_t *get;
+    int i;
+    sample_t yi;
+
+    get = make_get (polygon, x, y, width, height, &n_edges);
+
+    /* First step all the edges to the top of the bounding box */
+    for (i = 0; i < n_edges; ++i)
+    {
+	
+    }
+}
+
 int
 main ()
 {
@@ -269,3 +419,29 @@ main ()
 
     return 0;
 }
+
+#if 0
+typedef void (* pixman_edge_func_t) (int i,
+				     pixman_fixed_24_8_t *x0,
+				     pixman_fixed_24_8_t *y0,
+				     pixman_fixed_24_8_t *x1,
+				     pixman_fixed_24_8_t *y1,
+				     void *data);
+
+pixman_image_t *
+pixman_image_create_polygon (int                 n_edges,
+			     pixman_edge_func_t  get_edge,
+			     void               *data)
+{
+    for (i = 0; i < n_edges; ++i)
+    {
+	edge = &(edges[i]);
+
+	get_edge (i, &edge->x0, &edge->y0, edges[i].x1, 
+    }
+}
+
+    pixman_image_create_polygon (poly->n_edges, get_edge, poly);
+
+#endif
+
diff --git a/plan b/plan
index 0811cc0..df264c5 100644
--- a/plan
+++ b/plan
@@ -1,3 +1,46 @@
+Polygon:
+
+Store list of edges, sorted Y, then X
+
+Init (x, y, width, height)
+  - should add all interesting edges to a global edge table
+
+    (can this just be a pointer? No, because we need to change them,
+     and we need auxiliary data)
+
+     The GET should be of unions of (x0, y0, x1, y1) and the edge
+     structure. The edge structures should only be initialized when
+     they are actually needed.
+
+     Also add this time, the edges are transformed if the image has
+     a transformation.
+
+  - Add pointers to active edges to local edge table
+
+    Can the local edge table simply be a pointer into the global edge table?
+    Yes, although, the edge structures may be too large. Can we simply link
+    them together? Then we could merge sort them.
+
+Rendering scanline
+       - step all the edges, emitting points
+       	 keep track of:
+	      - the first edge that ends up being out of order
+	      - whether all active edges are vertical
+	 if an edge dies, unlink it from the AET.
+
+       - sort again
+
+
+
+
+
+
+
+
+
+
+
+
 - Write simple floating point based line walker
 
 - Make the sample grid is non-uniform.