#include #include #include #include #include #include #include #include /* * 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. * * +--------------------------------------------------+ * | | * | * * * * * * * * * * * * * * * * * |\ SMALL_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; }