More poly2

2 files changed, 262 insertions, 3 deletions

diff --git a/newplan b/newplan
index dbdb57c..b11d26f 100644
--- a/newplan
+++ b/newplan
@@ -71,10 +71,8 @@ rasterize (polygon, int x, int y, int width, int height)
 		    aet = update_aet (aet);
                 }
 
-		// done scan line 
+		// emit scan line 
 	}
-
-	yi = next_sample (y);
 }
 
 update_aet (yi)
diff --git a/poly2.c b/poly2.c
new file mode 100644
index 0000000..1631d0f
--- /dev/null
+++ b/poly2.c
@@ -0,0 +1,261 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <math.h>
+#include <stdint.h>
+#include <string.h>
+
+typedef int32_t			fixed_t;
+
+#define FIXED_BITS		(8)
+
+#define fixed_e                 ((fixed_t) 1)
+#define fixed_1                 (int_to_fixed(1))
+#define fixed_1_minus_e         (fixed_1 - fixed_e)
+#define fixed_to_int(f)         ((int) ((f) >> FIXED_BITS))
+#define int_to_fixed(i)         ((fixed_t) ((i) << FIXED_BITS))
+#define fixed_frac(f)           ((f) & fixed_1_minus_e)
+#define fixed_floor(f)          ((f) & ~fixed_1_minus_e)
+#define fixed_ceil(f)           fixed_floor ((f) + fixed_1_minus_e)
+#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))
+
+#define MAX_ALPHA(n)    ((1 << (n)) - 1)
+#define N_Y_FRAC(n)     ((n) == 1 ? 1 : (1 << ((n)/2)) - 1)
+#define N_X_FRAC(n)     ((n) == 1 ? 1 : (1 << ((n)/2)) + 1)
+
+#define STEP_Y_SMALL(n) (fixed_1 / N_Y_FRAC(n))
+#define STEP_Y_BIG(n)   (fixed_1 - (N_Y_FRAC(n) - 1) * STEP_Y_SMALL(n))
+
+#define Y_FRAC_FIRST(n) (STEP_Y_SMALL(n) / 2)
+#define Y_FRAC_LAST(n)  (Y_FRAC_FIRST(n) + (N_Y_FRAC(n) - 1) * STEP_Y_SMALL(n))
+
+#define STEP_X_SMALL(n) (fixed_1 / N_X_FRAC(n))
+#define STEP_X_BIG(n)   (fixed_1 - (N_X_FRAC(n) - 1) * STEP_X_SMALL(n))
+
+#define X_FRAC_FIRST(n) (STEP_X_SMALL(n) / 2)
+#define X_FRAC_LAST(n)  (X_FRAC_FIRST(n) + (N_X_FRAC(n) - 1) * STEP_X_SMALL(n))
+
+#define N_GRID_X               N_X_FRAC(8)
+#define N_GRID_Y               N_Y_FRAC(8)
+
+#define BIG_STEP_Y             STEP_Y_BIG(8)
+#define SMALL_STEP_Y           STEP_Y_SMALL(8)
+#define FIRST_STEP_Y           Y_FRAC_FIRST(8)
+
+#define BIG_STEP_X             STEP_X_BIG(8)
+#define SMALL_STEP_X           STEP_X_SMALL(8)
+#define FIRST_STEP_X           X_FRAC_FIRST(8)
+
+/* A "sample_t" is a fixed_t where the fractional bits are replaced with
+ * a small integer indicating the sample number in the pixel.
+ */
+typedef int32_t sample_t;
+
+static fixed_t
+sample_to_pos_x (sample_t x)
+{
+    return fixed_floor (x) + FIRST_STEP_X + fixed_frac (x) * SMALL_STEP_X;
+}
+
+static fixed_t
+sample_to_pos_y (sample_t y)
+{
+    return fixed_floor (y) + FIRST_STEP_Y + fixed_frac (y) * SMALL_STEP_Y;
+}
+
+static sample_t
+next_sample_y (fixed_t y)
+{
+    fixed_t f = fixed_frac (y);
+    fixed_t i = fixed_floor (y);
+    int sample_no;
+
+    sample_no = ((f - FIRST_STEP_Y + SMALL_STEP_Y - fixed_e) / SMALL_STEP_Y);
+
+    if (sample_no > N_GRID_Y - 1)
+    {
+	/* FIXME: i can overflow here, but we should probably just
+	 * reject edges that close to the border
+	 */
+	sample_no -= N_GRID_Y;
+	i += fixed_1;
+    }
+
+    return i + sample_no;
+}
+
+static sample_t
+next_sample_x (fixed_t x)
+{
+    fixed_t f = fixed_frac (x);
+    fixed_t i = fixed_floor (x);
+    int sample_no;
+
+    sample_no = ((f - FIRST_STEP_X + SMALL_STEP_X - fixed_e) / SMALL_STEP_X);
+
+    if (sample_no > N_GRID_X - 1)
+    {
+	/* FIXME: i can overflow here, but we should probably just
+	 * reject edges that close to the border
+	 */
+	sample_no -= N_GRID_X;
+	i += fixed_1;
+    }
+
+    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 polygon_t polygon_t;
+typedef struct point_t point_t;
+typedef struct seg_t seg_t;
+typedef struct active_t active_t;
+
+struct point_t
+{
+    fixed_t	x, y;
+};
+
+struct seg_t
+{
+    point_t p1, p2;
+};
+
+struct polygon_t
+{
+    seg_t *segments;
+    int n_segments;
+};
+
+typedef union edge_t edge_t;
+typedef struct edge_common_t edge_common_t;
+typedef struct short_edge_t short_edge_t;
+typedef struct vertical_edge_t vertical_edge_t;
+typedef struct long_edge_t long_edge_t;
+typedef struct uninitialized_edge_t uninitialized_edge_t;
+
+typedef enum
+{
+    VERTICAL,
+    SHORT_NE,
+    SHORT_NW,
+    SHORT_SE,
+    SHORT_SW,
+    LONG,
+    UNINITIALIZED
+} edge_type_t;
+
+struct edge_common_t
+{
+    edge_type_t	type;
+};
+
+struct short_edge_t
+{
+    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
+{
+    /* stuff here, pointer */
+};
+
+union edge_t
+{
+    edge_type_t		type;
+    edge_common_t	common;
+    short_edge_t	short_;
+    long_edge_t		long_;
+    vertical_edge_t	vertical;
+};
+
+static 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;
+    }
+}
+
+static polygon_t *
+polygon_create (seg_t *segments, int n_segments)
+{
+    polygon_t *polygon = malloc (sizeof *polygon);
+
+    polygon->n_segments = n_segments;
+    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;
+}
+
+int
+main (int argc, char **argv)
+{
+    return 0;
+}