Add beginning of fixpoint scan converter

1 files changed, 177 insertions, 0 deletions

diff --git a/scv.c b/scv.c
new file mode 100644
index 0000000..4df3ffc
--- /dev/null
+++ b/scv.c
@@ -0,0 +1,177 @@
+#include <stdio.h>
+#include <math.h>
+#include <pixman.h>
+#include <gtk/gtk.h>
+
+typedef pixman_fixed_16_16_t	fixed_t;
+
+
+#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) >> 16))
+#define int_to_fixed(i)		((fixed_t) ((i) << 16))
+#define fixed_frac(f)		((f) & pixman_fixed_1_minus_e)
+#define fixed_floor(f)		((f) & ~pixman_fixed_1_minus_e)
+#define fixed_ceil(f)		pixman_fixed_floor ((f) + pixman_fixed_1_minus_e)
+#define fixed_mod_2(f)		((f) & (pixman_fixed1 | pixman_fixed_1_minus_e))
+
+#define fixed_to_double(f)	(double) ((f) / (double) pixman_fixed_1)
+#define double_to_fixed(d)	((pixman_fixed_t) ((d) * 65536.0))
+
+
+/*
+ *    +--------------------------------------------------+
+ *    |                           <Y_FRAC_FIRST>         |
+ *    | <X_FRAC_FIRST> * * * * * * * * * * * * * * * * * |
+ *    |                * * * * * * * * * * * * * * * * * |
+ *    |                * * * * * * * * * * * * * * * * * |
+ *    |                * * * * * * * * * * * * * * * * * |
+ *    |                * * * * * * * * * * * * * * * * * |
+ *    |                * * * * * * * * * * * * * * * * * |
+ *    |                * * * * * * * * * * * * * * * * * |
+ *    |                * * * * * * * * * * * * * * * * * |
+ *    |                * * * * * * * * * * * * * * * * * |
+ *    |                * * * * * * * * * * * * * * * * * |
+ *    |                * * * * * * * * * * * * * * * * * |
+ *    |                * * * * * * * * * * * * * * * * * |
+ *    |                * * * * * * * * * * * * * * * * * |
+ *    |                * * * * * * * * * * * * * * * * * |
+ *    |                * * * * * * * * * * * * * * * * * |
+ *    |                          | <BIG_STEP>            |
+ *    +--------------------------------------------------+
+ */
+
+#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)	(pixman_fixed_1 / N_X_FRAC(n))
+#define STEP_X_BIG(n)	(pixman_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))
+
+typedef struct edge_t edge_t;
+struct edge_t
+{
+    fixed_t			x0;
+    fixed_t			y0;
+    fixed_t			x1;
+    fixed_t			y1;
+};
+
+#define N_GRID_X 17
+#define N_GRID_Y 15
+
+static fixed_t
+next_sample_x (fixed_t x)
+{
+    pixman_fixed_t   f = pixman_fixed_frac(x);
+    pixman_fixed_t   i = pixman_fixed_floor(x);
+
+    f = ((f + Y_FRAC_FIRST(N_GRID_X)) / STEP_Y_SMALL(N_GRID_X)) * STEP_Y_SMALL(N_GRID_X) + Y_FRAC_FIRST(N_GRID_X);
+    if (f > Y_FRAC_LAST(N_GRID_X))
+    {
+	f = Y_FRAC_FIRST(N_GRID_X);
+	i += pixman_fixed_1;
+    }
+    return (i | f);
+}
+
+static fixed_t
+next_sample_y (fixed_t y)
+{
+    pixman_fixed_t   f = pixman_fixed_frac(y);
+    pixman_fixed_t   i = pixman_fixed_floor(y);
+
+    f = ((f + Y_FRAC_FIRST(N_GRID_Y)) / STEP_Y_SMALL(N_GRID_Y)) * STEP_Y_SMALL(N_GRID_Y) + Y_FRAC_FIRST(N_GRID_Y);
+    if (f > Y_FRAC_LAST(N_GRID_Y))
+    {
+	f = Y_FRAC_FIRST(N_GRID_Y);
+	i += pixman_fixed_1;
+    }
+    return (i | f);
+}
+
+static fixed_t
+sample_step_x (fixed_t x)
+{
+    (void)x;
+    
+    return 1.0;
+}
+
+static fixed_t
+sample_step_y (fixed_t y)
+{
+    if (pixman_fixed_frac (y) == Y_FRAC_LAST (N_GRID_Y))
+    {
+	return STEP_Y_BIG (N_GRID_Y);
+    }
+    else
+    {
+	return STEP_Y_SMALL (N_GRID_Y);
+    }
+}
+
+static void
+dda (fixed_t x0, fixed_t y0, fixed_t x1, fixed_t y1)
+{
+    fixed_t y = next_sample_y (y0);
+    fixed_t dxdy = (y1 - y0) / (x1 - x0);
+
+    printf ("line %f %f %f %f\n",
+	    pixman_fixed_to_double (x0),
+	    pixman_fixed_to_double (y0),
+	    pixman_fixed_to_double (x1),
+	    pixman_fixed_to_double (y1));
+
+    printf ("bottom: %f\n", pixman_fixed_to_double (next_sample_y (y1)));
+    
+    while (y < next_sample_y (y1))
+    {
+	fixed_t dy = y - y0;
+	fixed_t dx = x1 - x0;
+	fixed_t x = ((((y - y0) * (pixman_fixed_48_16_t)(x1 - x0)))) / (y1 - y0) + x0;
+
+	x = next_sample_x (x);
+	
+	printf ("  %f %f\n",
+		pixman_fixed_to_double (x),
+		pixman_fixed_to_double (y));
+	
+	y += sample_step_y (y);
+    }
+}
+
+static void
+ddda (double x0, double y0, double x1, double y1)
+{
+    dda (pixman_double_to_fixed (x0),
+	 pixman_double_to_fixed (y0),
+	 pixman_double_to_fixed (x1),
+	 pixman_double_to_fixed (y1));
+}
+
+int
+main (int argc, char **argv)
+{
+    gtk_init (&argc, &argv);
+
+    
+    ddda (0.5, 0.5, 2.5, 1.6);
+    ddda (0.3, 0.2, 3.7, 2.2);
+    ddda (3.7, 2.2, 7.2, 2.8);
+    ddda (3.7, 2.2, 4.2, 7.2);
+    ddda (0.5, 0.5, 1.5, 1.5);
+    ddda (0.5, 0.5, 2.5, 2.5);
+    
+    return 0;
+}