path: root/dda.c

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <stdint.h>
#include <string.h>

typedef int32_t			fixed_t;

#include "testdata.c"

#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 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;
    int64_t e;
    int64_t delta_e_big_x;
    int64_t delta_e_small_x;
    int64_t delta_e_big_y;
    int64_t delta_e_small_y;
    dir_t dir;
};

static void
edge_init (edge_t *edge,
	   fixed_t x0, fixed_t y0,
	   fixed_t x1, fixed_t y1,
	   dir_t dir)
{
    int64_t dx, dy;
    sample_t xi, yi;

    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 (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);

/* FIXME:
 *
 * When updating the xi, we are stepping one sample at a time, but we
 * can do better because we know how the minimum damage that is done on every Y
 * step. This means we know we have to undo at least that much damage, so
 * we can step much more than one sample if the edge is close to horizontal.
 *
 * The first micro-step is an exception - it may not do as much damage as
 * normal.
 */
static void
edge_step (edge_t *edge, sample_t yi, emitter_t emit, void *data)
{
    if (edge->delta_e_small_y >= 0)
    {
	while (edge->e <= 0)
	{
	    if (fixed_frac (edge->xi) == N_GRID_X - 1)
	    {
		edge->e += edge->delta_e_big_x;
		edge->xi += fixed_1;
		edge->xi = fixed_floor (edge->xi);
	    }
	    else
	    {
		edge->e += edge->delta_e_small_x;
		edge->xi++;
	    }
	}
    }
    else
    {
    begin:
	if (fixed_frac (edge->xi) == 0)
	{
	    if (edge->e > edge->delta_e_big_x)
	    {
		edge->e -= edge->delta_e_big_x;
		edge->xi -= fixed_1;
		edge->xi |= (N_GRID_X - 1);
		goto small;
	    }
	}
	else
	{
	small:
	    if (edge->e > edge->delta_e_small_x)
	    {
		edge->e -= edge->delta_e_small_x;
		edge->xi--;
		goto begin;
	    }
	}
    }

    emit (edge->xi, yi, data);

    if (fixed_frac (yi) == N_GRID_Y - 1)
	edge->e -= edge->delta_e_big_y;
    else
	edge->e -= edge->delta_e_small_y;
}

static void
emit (sample_t xi, sample_t yi, void *data)
{
    fixed_t *points = data;

    if (xi != points[0] || yi != points[1])
    {
	printf ("0x%x, 0x%x - should be 0x%x 0x%x,\n",
		xi, yi, points[0], points[1]);
	exit (1);
    }

    return;
}

static void
dda (test_data_t *testdata)
{
    fixed_t x0 = testdata->segment.x0;
    fixed_t y0 = testdata->segment.y0;
    fixed_t x1 = testdata->segment.x1;
    fixed_t y1 = testdata->segment.y1;

#if 0
    printf ("{\n{ 0x%x, 0x%x, 0x%x, 0x%x },\n{\n", x0, y0, x1, y1);
#endif

    edge_t edge;
    int i = 0;
    int yi;

    edge_init (&edge, x0, y0, x1, y1, DOWN);

    yi = next_sample_y (y0);
    while (yi < edge.bottom)
    {
	edge_step (&edge, yi, emit, &(testdata->points[i]));

	i += 2;

	yi = step_y (yi);
    }
#if 0
    printf ("} \n},\n");
#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;
}

#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, 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)
    {
	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)
	{
	    min = MIN (top->y, min);

	    edge_init (&(get[n_edges++]),
		       top->x, top->y, bottom->x, bottom->y,
		       (top == &(seg->p1))? DOWN : UP);
	}
    }

    *n = n_edges;
    return get;
}

static edge_t **
update_aet (edge_t **aet, int *n_active,
	    sample_t y, edge_t **global, int *n_edges)
{
    int i;
    int new_size;
    int n_new;

    for (i = 0; i < *n_edges; ++i)
    {
	edge_t *e = global[i];

    }

    *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, *next_edge;
    fixed_t min;
    sample_t yi;
    edge_t **aet;
    int n_active;

    next_edge = get = make_get (polygon, x, y, width, height, &n_edges, &min);

    yi = next_sample_y (min);

    n_active = 0;
    aet = update_aet (NULL, &n_active, yi, &next_edge, &n_edges);

    while (fixed_to_int (yi) < y + height)
    {
	int i;

	for (i = 0; i < n_active; ++i)
	    edge_step (aet[i], yi, poly_emit, NULL);

	yi = step_y (yi);

	aet = update_aet (aet, &n_active, yi, &next_edge, &n_edges);
    }

    /* First step all the edges to the top of the bounding box */

    free (get);
}

int
main ()
{
    int i;

    for (i = 0; i < 1000; ++i)
    {
	test_data_t *tt = &(testdata[i]);

	dda (tt);
    }

    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