path: root/poly3.c

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <stdint.h>
#include <string.h>
#include <assert.h>
#include <cairo.h>
#include <gtk/gtk.h>


/*
 * The sample grid.
 *
 * Note that this starts breaking down if we go above 8 bits of
 * alpha. For 10 bits of alpha, the sample grid becomes 31 x 33, the
 * "small step" is 4 in the 24.8, and the big step is 8. The big is twice
 * as big as the small step, so instead it would be better to alternate
 * big steps and small steps; we can no longer put the whole big step
 * at the end.

 * If there are more samples than there is fixed-point resolution,
 * then things break down completely. For example, with 16 bits of alpha,
 * the sample grid is 255 x 257, so n that case, we really need more than
 * 8 fractional bits. In the X direction, the small step would be 0, so we
 * would get divide-by-zero errors.
 *
 *    +--------------------------------------------------+
 *    |                           <Y_FRAC_FIRST>         |
 *    | <X_FRAC_FIRST> * * * * * * * * * * * * * * * * * |\  SMALL_STEP_Y
 *    |                * * * * * * * * * * * * * * * * * |/
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                          | <BIG_STEP_Y>          |
 *    +--------------------------------------------------+
 */

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_BITS		       8

#define N_GRID_X               N_X_FRAC(N_BITS)
#define N_GRID_Y               N_Y_FRAC(N_BITS)

#define BIG_STEP_Y             STEP_Y_BIG(N_BITS)
#define SMALL_STEP_Y           STEP_Y_SMALL(N_BITS)
#define FIRST_STEP_Y           Y_FRAC_FIRST(N_BITS)

#define BIG_STEP_X             STEP_X_BIG(N_BITS)
#define SMALL_STEP_X           STEP_X_SMALL(N_BITS)
#define FIRST_STEP_X           X_FRAC_FIRST(N_BITS)

/* 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
int_to_sample (int i)
{
    return i << FIXED_BITS;
}

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 long_edge_t long_edge_t;
typedef struct uninitialized_edge_t uninitialized_edge_t;

typedef enum
{
    UNINITIALIZED,
    LONG
} edge_type_t;

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

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

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

union edge_t
{
    edge_type_t		 type;
    edge_common_t	 common;
    uninitialized_edge_t uninitialized;
    long_edge_t		 long_;
};

static void
long_edge_update_error (long_edge_t *edge)
{
    if (edge->delta_e_small_y >= 0)
    {
	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_1;
		edge->common.xi = fixed_floor (edge->common.xi);
	    }
	    else
	    {
		edge->e += edge->delta_e_small_x;
		edge->common.xi++;
	    }
	}
    }
    else
    {
    begin:
	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 -= fixed_1;
		edge->common.xi |= (N_GRID_X - 1);
		goto begin;
	    }
	}
	else
	{
	    if (edge->e > edge->delta_e_small_x)
	    {
		edge->e -= edge->delta_e_small_x;
		edge->common.xi--;
		goto begin;
	    }
	}
    }
}

static void
long_edge_small_step (long_edge_t *edge)
{
    edge->e -= edge->delta_e_small_y;

    long_edge_update_error (edge);
}

static void
long_edge_big_step (long_edge_t *edge)
{
    edge->e -= edge->delta_e_big_y;

    long_edge_update_error (edge);
}

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

    /* Long */
    {
	int64_t dx, dy;

#if 0
	printf ("Activating (%f %f %f %f)\n",
		fixed_to_double (top->x),
		fixed_to_double (top->y),
		fixed_to_double (bottom->x),
		fixed_to_double (bottom->y));
#endif
	    
	dx = (bottom->x - top->x);
	dy = (bottom->y - top->y);

	edge->long_.e =
	    (int64_t)(sample_to_pos_x (edge->common.xi) - (int64_t)top->x) * dy -
	    (int64_t)(sample_to_pos_y (first_yi) - (int64_t)top->y) * dx;
	edge->long_.delta_e_big_x = BIG_STEP_X * dy;
	edge->long_.delta_e_small_x = SMALL_STEP_X * dy;
	edge->long_.delta_e_big_y = BIG_STEP_Y * dx;
	edge->long_.delta_e_small_y = SMALL_STEP_Y * dx;
	
	long_edge_update_error (&edge->long_);
    }
}

static void
edge_small_step (edge_t *edge)
{
    long_edge_small_step (&edge->long_);
}

static void
edge_big_step (edge_t *edge)
{
    long_edge_big_step (&edge->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 (top->y == bottom->y)
	    continue;
	
	if (fixed_to_int (top->y) >= y + height)
	    break;

	if (fixed_to_int (bottom->y) >= y)
	{
	    uninitialized_edge_t *u = &(global->last++->uninitialized);

	    printf ("adding %x %x\n", top->x, top->y);
	    
	    u->seg = seg;
	    u->top = top;
	    u->bottom = bottom;
	    u->yi = next_sample_y (u->top->y);
	}
    }

    printf ("%d segments\n", global->last - global->edges);
    
    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 int
compare_active (const void *v1, const void *v2)
{
    const edge_t *e1 = *(const edge_t **)v1;
    const edge_t *e2 = *(const edge_t **)v2;

    return e1->common.xi - e2->common.xi;
}

static active_t *
update_active (active_t *active, sample_t yi)
{
    int i, d;

    /* eliminate dead edges */
    d = 0;
    for (i = 0; i < active->n_edges; ++i)
    {
	edge_t *edge = active->edges[i];

	if (yi >= edge->common.bottom)
	    d++;
	else if (d)
	    active->edges[i - d] = edge;
    }

    active->n_edges -= d;

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

    qsort (active->edges, active->n_edges, sizeof (edge_t *), compare_active);
    
    return active;
}

typedef void (* emit_func_t) (sample_t xi, sample_t yi, void *data);

static void
polygon_rasterize (polygon_t *polygon,
		   int x, int y, int width, int height,
		   emit_func_t emit, void *data)
{
    global_t *global = create_global (polygon, x, y, width, height);
    active_t *active = create_active (global);
    sample_t yi = int_to_sample (y);
    sample_t end = int_to_sample (y + height);

    while (yi < end)
    {
	int i, j;

	active = update_active (active, yi);

	for (i = 0; i < N_GRID_Y - 1; ++i)
	{
	    for (j = 0; j < active->n_edges; ++j)
	    {
		edge_t *edge = active->edges[j];
		
		emit (edge->common.xi, yi, data);
		
		edge_small_step (edge);
	    }

	    yi++;
	    active = update_active (active, yi);
	}

	active = update_active (active, yi);

	for (j = 0; j < active->n_edges; ++j)
	{
	    edge_t *edge = active->edges[j];

	    emit (edge->common.xi, yi, data);
	    
	    edge_big_step (edge);
	}

	yi = fixed_floor (yi + fixed_1);
    }
}

#define df(a) double_to_fixed(a)

#define MULTIPLIER  (375)

static int last_y;
static int last_x;
static int p;

static void
emit (sample_t xi, sample_t yi, void *data)
{
    cairo_t *cr = data;
    double x =  (MULTIPLIER * fixed_to_double (sample_to_pos_x (xi)));
    double y =  (MULTIPLIER * fixed_to_double (sample_to_pos_y (yi)));

#if 0
    printf ("point: %f %f\n", x, y);
#endif

    cairo_set_source_rgba (cr, 0.4, 0.8, 0.4, 0.8);
    if (!p)
	cairo_move_to (cr, x, y);
    else
    {
	cairo_line_to (cr, x, y);
	
	cairo_set_line_width (cr, 2);
	cairo_stroke (cr);
    }
    
#if 0
    cairo_rectangle (cr, floor (x - 0.5), floor (y - 0.5), 1, 1);
    cairo_fill (cr);
#endif

    p = !p;
}

static gboolean
on_expose (GtkWidget *widget, GdkEvent *event, gpointer data)
{
    if (!GTK_WIDGET_DRAWABLE (widget))
	return TRUE;
    
    seg_t pentagons[] = {
	{ { df (10.2), df (2.2)}, { df (11.3),  df (2.2) } },
	{ { df (11.3), df (2.2) }, { df (15.7),  df (5.5) } },
	{ { df (15.7), df (5.5) }, { df (20.8), df (15.8) } },
	{ { df (20.8), df (15.8) }, { df (13.2), df (25.2) } },
	{ { df (13.2), df (25.2) }, { df (10.2),  df (2.2) } },

	{ { df (15 + 10.2), df (2.2)}, { df (15 + 11.3),  df (2.2) } },
	{ { df (15 + 11.3), df (2.2) }, { df (15 + 15.7),  df (5.5) } },
	{ { df (15 + 15.7), df (5.5) }, { df (15 + 20.8), df (15.8) } },
	{ { df (15 + 20.8), df (15.8) }, { df (-5 + 13.2), df (25.2) } },
	{ { df (-5 + 13.2), df (25.2) }, { df (15 + 10.2),  df (2.2) } },

	{ { df (7.0), df (2.0) }, { df (38.0), df (2.1) } },
	{ { df (7.0), df (12.0) }, { df (13.0), df (12.0) } },
	{ { df (7.0), df (2.0) }, { df (7.0), df (12.0) } },
	{ { df (13.0), df (12.0) }, { df (38.0), df (2.1) } },
    };

    cairo_t *cr = gdk_cairo_create (widget->window);
    int i, j;

    last_y = -1;
    last_x = -1;
    p = 0;

    cairo_set_source_rgb (cr, 1, 1, 1);
    cairo_set_operator (cr, CAIRO_OPERATOR_SOURCE);
    cairo_paint (cr);
    cairo_set_operator (cr, CAIRO_OPERATOR_SOURCE);
    
    for (i = 0; i < 40; ++i)
    {
	cairo_set_source_rgba (cr, 0.5, 0.5, 1, 0.8);

	cairo_rectangle (cr, MULTIPLIER * i, 0, 1, MULTIPLIER * 50);
	cairo_fill (cr);
    }

    for (i = 0; i < 30; ++i)
    {
	cairo_set_source_rgba (cr, 0.5, 0.5, 1, 0.8);

	cairo_rectangle (cr, 0, MULTIPLIER * i, MULTIPLIER * 50, 1);
	cairo_fill (cr);
    }

    polygon_t *polygon = polygon_create (
	pentagons, sizeof (pentagons) / sizeof (pentagons[0]));

    cairo_set_source_rgba (cr, 0.8, 0.2, 0.2, 1.0);
    cairo_set_line_width (cr, 1);
    for (i = 0; i < polygon->n_segments; ++i)
    {
	seg_t *seg = &(polygon->segments[i]);
	double x0 = fixed_to_double (seg->p1.x);
	double y0 = fixed_to_double (seg->p1.y);
	double x1 = fixed_to_double (seg->p2.x);
	double y1 = fixed_to_double (seg->p2.y);
	cairo_move_to (cr, x0 * MULTIPLIER, y0 * MULTIPLIER);
	cairo_line_to (cr, x1 * MULTIPLIER, y1 * MULTIPLIER);
	cairo_stroke (cr);
    }

    cairo_set_operator (cr, CAIRO_OPERATOR_OVER);
    polygon_rasterize (polygon, 0, 0, 45, 30, emit, cr);

    cairo_set_source_rgba (cr, 1, 1, 1, 0.2);
    cairo_set_operator (cr, CAIRO_OPERATOR_SOURCE);
    for (i = 0; i < 30; ++i)
    {
	int yy;
	if ((i + 1) * MULTIPLIER < event->expose.area.y)
	    continue;
	if (i * MULTIPLIER > event->expose.area.y + event->expose.area.height)
	    continue;
	for (yy = 0; yy < N_GRID_Y; ++yy)
	{
	    for (j = 0; j < 40; ++j)
	    {
		int xx;

		if ((j + 1) * MULTIPLIER < event->expose.area.x)
		    continue;
		if (j * MULTIPLIER > event->expose.area.x + event->expose.area.width)
		    continue;
		
		for (xx = 0; xx < N_GRID_X; ++xx)
		{
		    double y =
			(MULTIPLIER *
			 fixed_to_double (
			     sample_to_pos_y ((i << FIXED_BITS) | yy))) - 0.5;
		    double x =
			(MULTIPLIER *
			 fixed_to_double (
			     sample_to_pos_x ((j << FIXED_BITS) | xx)) - 0.5);
		    
		    cairo_rectangle (cr, x, y, 1, 1);
		    
		    cairo_fill (cr);
		}
	    }
	}
    }
    
    return TRUE;
    
}

int
main (int argc, char **argv)
{
    GtkWidget *window;
    GtkWidget *area;
    GtkWidget *sw;

    gtk_init (&argc, &argv);

    area = gtk_drawing_area_new ();
    sw = gtk_scrolled_window_new (NULL, NULL);
    window = gtk_window_new (GTK_WINDOW_TOPLEVEL);

    gtk_container_add (GTK_CONTAINER (window), sw);

    gtk_scrolled_window_add_with_viewport (GTK_SCROLLED_WINDOW (sw), area);

    gtk_widget_set_size_request (area, MULTIPLIER * 50, MULTIPLIER * 50);

    gtk_window_set_default_size (GTK_WINDOW (window), 800, 600);
    
    gtk_widget_show_all (window);

    g_signal_connect (area, "expose_event", G_CALLBACK (on_expose), NULL);
    g_signal_connect (window, "delete_event", G_CALLBACK (gtk_main_quit), NULL);
    
    
    gtk_main ();
    
    
    return 0;
}