path: root/poly2.c

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <stdint.h>
#include <string.h>
#include <assert.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;
typedef struct global_t global_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_W,
    SHORT_E,
    LONG,
    UNINITIALIZED
} edge_type_t;

struct edge_common_t
{
    edge_type_t	type;
    int		dir;
    sample_t	xi;
    sample_t	bottom;
};

struct short_edge_t
{
    edge_common_t	common;
    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;
};

struct vertical_edge_t
{
    edge_common_t	common;
};

struct long_edge_t
{
    edge_common_t	common;
    /* stuff here, pointer */
};

struct uninitialized_edge_t
{
    edge_common_t	common;
    sample_t		yi;
    const seg_t *	seg;
    const point_t *	top;
    const point_t *	bottom;
};

union edge_t
{
    edge_type_t		 type;
    edge_common_t	 common;
    vertical_edge_t	 vertical;
    short_edge_t	 short_;
    long_edge_t		 long_;
    uninitialized_edge_t uninitialized;
};

static void
short_e_edge_update_error (short_edge_t *edge)
{
    while (edge->e <= 0)
    {
	if (fixed_frac (edge->common.xi) == N_GRID_X - 1)
	{
	    edge->e += edge->delta_e_big_x;
	    edge->common.xi = fixed_floor (edge->common.xi + fixed_1);
	}
	else
	{
	    edge->e += edge->delta_e_small_x;
	    edge->common.xi++;
	}
    }
}

static void
short_w_edge_update_error (short_edge_t *edge)
{
again:
    if (fixed_frac (edge->common.xi) == 0)
    {
	if (edge->e > edge->delta_e_big_x)
	{
	    edge->e -= edge->delta_e_big_x;
	    edge->common.xi = (edge->common.xi - fixed_1) | (N_GRID_X - 1);
	    goto again;
	}
    }
    else
    {
	if (edge->e > edge->delta_e_small_x)
	{
	    edge->e -= edge->delta_e_small_x;
	    edge->common.xi--;
	    goto again;
	}
    }
}

static void
edge_init (edge_t *edge, sample_t first_yi)
{
    const point_t *top = edge->uninitialized.top;
    const point_t *bottom = edge->uninitialized.bottom;
    const seg_t *seg = edge->uninitialized.seg;

    edge->common.dir = 2 * (top == &seg->p1) - 1;
    edge->common.bottom = next_sample_y (bottom->y);
    edge->common.xi = next_sample_x (top->x);

    if (top->x == bottom->x)
    {
	/* vertical */
	edge->common.type = VERTICAL;
    }
    else
    {
	fixed_t dx, dy;

	dy = bottom->y - top->y;
	dx = bottom->x - top->x;

	assert (dy > 0);

	if (dy < int_to_fixed (1 << (16 - FIXED_BITS)) &&
	    dx < int_to_fixed (1 << (16 - FIXED_BITS)) &&
	    dx < 8 * dy)
	{
	    /* short */
	    edge->short_.e =
		(sample_to_pos_x (edge->common.xi) - top->x) * dy -
		(sample_to_pos_y (first_yi) - top->y) * dx;
	    edge->short_.delta_e_big_x = BIG_STEP_X * dy;
	    edge->short_.delta_e_small_x = SMALL_STEP_X * dy;
	    edge->short_.delta_e_big_y = BIG_STEP_Y * dx;
	    edge->short_.delta_e_small_y = SMALL_STEP_Y * dx;

	    if (dx >= 0)
	    {
		edge->common.type = SHORT_E;
		short_e_edge_update_error (&edge->short_);
	    }
	    else
	    {
		edge->common.type = SHORT_W;
		short_w_edge_update_error (&edge->short_);
	    }
	}
	else
	{
	    /* long */
	}
    }
}

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;
}

struct global_t
{
    edge_t *	last;
    edge_t	edges[1];
};

static global_t *
create_global (polygon_t *polygon, int x, int y, int width, int height)
{
    global_t *global;
    int i;

    global = malloc (
	sizeof (global_t) + (polygon->n_segments - 1) * sizeof (edge_t));

    global->last = &(global->edges[0]);

    for (i = 0; i < polygon->n_segments; ++i)
    {
	const 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)
	{
	    uninitialized_edge_t *u = &(global->last++->uninitialized);

	    u->seg = seg;
	    u->top = top;
	    u->bottom = bottom;
	    u->yi = next_sample_y (u->top->y);
	}
    }

    return global;
}

struct active_t
{
    global_t *	global;
    edge_t *	current;
    int		n_edges;
    edge_t *	edges[1];
};

static active_t *
create_active (global_t *global)
{
    active_t *active = malloc (sizeof *active);

    active->global = global;
    active->current = &(global->edges[0]);
    active->n_edges = 0;

    return active;
}

static active_t *
update_active (active_t *active, sample_t yi)
{
    while (active->current < active->global->last   &&
	   active->current->uninitialized.yi <= yi)
    {
	edge_init (active->current, yi);

	/* FIXME: this should be made more efficient */
	active = realloc (
	    active, sizeof (*active) + active->n_edges * sizeof (edge_t *));
	active->edges[active->n_edges++] = active->current++;
    }

    /* sort edges */
    return active;
}

static void
polygon_rasterize (polygon_t *polygon, int x, int y, int width, int height)
{
    global_t *global = create_global (polygon, x, y, width, height);
}

int
main (int argc, char **argv)
{
    return 0;
}