[PATCH] Greedy trapezoidation.
Chris Wilson
chris at chris-wilson.co.uk
Thu Oct 2 16:38:27 PDT 2008
---
src/cairo-bentley-ottmann.c | 177 ++++++++++++++++++++++++++++--------------
1 files changed, 118 insertions(+), 59 deletions(-)
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index f596696..017ede0 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -257,6 +257,29 @@ edges_compare_x_for_y (const cairo_bo_edge_t *a,
int32_t bdx, bdy;
cairo_int128_t L, R;
+ /* don't bother solving for abscissa if the edges' bounding boxes
+ * can be used to order them. */
+ {
+ int32_t amin, amax;
+ int32_t bmin, bmax;
+ if (a->middle.x < a->bottom.x) {
+ amin = a->middle.x;
+ amax = a->bottom.x;
+ } else {
+ amin = a->bottom.x;
+ amax = a->middle.x;
+ }
+ if (b->middle.x < b->bottom.x) {
+ bmin = b->middle.x;
+ bmax = b->bottom.x;
+ } else {
+ bmin = b->bottom.x;
+ bmax = b->middle.x;
+ }
+ if (amax < bmin) return -1;
+ if (amin > bmax) return +1;
+ }
+
adx = a->bottom.x - a->top.x;
ady = a->bottom.y - a->top.y;
@@ -273,7 +296,7 @@ edges_compare_x_for_y (const cairo_bo_edge_t *a,
bdy),
y - a->top.y));
- /* return _cairo_int128_cmp (L, R); */
+ /* return _cairo_int128_cmp (L, R, tolerance?); */
if (_cairo_int128_lt (L, R))
return -1;
if (_cairo_int128_gt (L, R))
@@ -291,29 +314,6 @@ _cairo_bo_sweep_line_compare_edges (cairo_bo_sweep_line_t *sweep_line,
if (a == b)
return 0;
- /* don't bother solving for abscissa if the edges' bounding boxes
- * can be used to order them. */
- {
- int32_t amin, amax;
- int32_t bmin, bmax;
- if (a->middle.x < a->bottom.x) {
- amin = a->middle.x;
- amax = a->bottom.x;
- } else {
- amin = a->bottom.x;
- amax = a->middle.x;
- }
- if (b->middle.x < b->bottom.x) {
- bmin = b->middle.x;
- bmax = b->bottom.x;
- } else {
- bmin = b->bottom.x;
- bmax = b->middle.x;
- }
- if (amax < bmin) return -1;
- if (amin > bmax) return +1;
- }
-
cmp = edges_compare_x_for_y (a, b, sweep_line->current_y);
if (cmp)
return cmp;
@@ -1145,28 +1145,34 @@ _cairo_bo_edge_end_trap (cairo_bo_edge_t *left,
* right edge differs from `edge->next', or do nothing if the new
* trapezoid would be a continuation of the existing one. */
static cairo_status_t
-_cairo_bo_edge_start_or_continue_trap (cairo_bo_edge_t *edge,
- int32_t top,
+_cairo_bo_edge_start_or_continue_trap (cairo_bo_edge_t *left,
+ cairo_bo_edge_t *right,
+ int top,
cairo_bo_traps_t *bo_traps)
{
cairo_status_t status;
- cairo_bo_trap_t *trap = edge->deferred_trap;
+ cairo_bo_trap_t *trap;
+ trap = left->deferred_trap;
if (trap) {
- if (trap->right == edge->next) return CAIRO_STATUS_SUCCESS;
- status = _cairo_bo_edge_end_trap (edge, top, bo_traps);
+ if (trap->right == right)
+ return CAIRO_STATUS_SUCCESS;
+
+ status = _cairo_bo_edge_end_trap (left, top, bo_traps);
if (status)
return status;
}
- if (edge->next) {
- trap = edge->deferred_trap = _cairo_freelist_alloc (&bo_traps->freelist);
- if (!edge->deferred_trap)
+ if (right) {
+ trap = _cairo_freelist_alloc (&bo_traps->freelist);
+ if (trap == NULL)
return _cairo_error (CAIRO_STATUS_NO_MEMORY);
- trap->right = edge->next;
+ trap->right = right;
trap->top = top;
+ left->deferred_trap = trap;
}
+
return CAIRO_STATUS_SUCCESS;
}
@@ -1218,40 +1224,79 @@ _cairo_bo_sweep_line_validate (cairo_bo_sweep_line_t *sweep_line)
static cairo_status_t
-_active_edges_to_traps (cairo_bo_edge_t *head,
+_active_edges_to_traps (cairo_bo_edge_t *left,
int32_t top,
+ int32_t bot,
cairo_fill_rule_t fill_rule,
cairo_bo_traps_t *bo_traps)
{
+ cairo_bo_edge_t *right;
cairo_status_t status;
- int in_out = 0;
- cairo_bo_edge_t *edge;
- for (edge = head; edge; edge = edge->next) {
- if (fill_rule == CAIRO_FILL_RULE_WINDING) {
- if (edge->reversed)
+ if (fill_rule == CAIRO_FILL_RULE_WINDING) {
+ while (left != NULL) {
+ int in_out = 0;
+
+ if (left->reversed)
in_out++;
else
in_out--;
- if (in_out == 0) {
- status = _cairo_bo_edge_end_trap (edge, top, bo_traps);
+
+ /* Greedily search for the closing edge, so that we generate the
+ * maximal span width and minimal the number of trapezoids */
+ for (right = left->next; right != NULL; right = right->next) {
+ status = _cairo_bo_edge_end_trap (right, top, bo_traps);
if (status)
return status;
- continue;
+
+ if (right->reversed)
+ in_out++;
+ else
+ in_out--;
+
+ if (in_out == 0) {
+ cairo_bo_edge_t *next;
+ cairo_bool_t skip = FALSE;
+
+ /* skip co-linear edges */
+ next = right->next;
+ if (next != NULL && FALSE) {
+ skip = edges_compare_x_for_y (right, next, top) >= 0 &&
+ edges_compare_x_for_y (right, next, bot) >= 0;
+ }
+
+ if (! skip)
+ break;
+ }
}
- } else {
- in_out++;
- if ((in_out & 1) == 0) {
- status = _cairo_bo_edge_end_trap (edge, top, bo_traps);
+
+ status = _cairo_bo_edge_start_or_continue_trap (left, right,
+ top, bo_traps);
+ if (status)
+ return status;
+
+ left = right;
+ if (left)
+ left = left->next;
+ }
+ } else {
+ int in_out = 0;
+ while (left != NULL) {
+ if ((in_out++ & 1) == 0) {
+ status = _cairo_bo_edge_start_or_continue_trap (left,
+ left->next,
+ top,
+ bo_traps);
+ if (status)
+ return status;
+ } else {
+ status = _cairo_bo_edge_end_trap (left, top, bo_traps);
if (status)
return status;
- continue;
}
- }
- status = _cairo_bo_edge_start_or_continue_trap (edge, top, bo_traps);
- if (status)
- return status;
+ left = left->next;
+ }
}
return CAIRO_STATUS_SUCCESS;
@@ -1299,6 +1344,7 @@ _cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_edge_t *edges,
if (event->point.y != sweep_line.current_y) {
status = _active_edges_to_traps (sweep_line.head,
sweep_line.current_y,
+ event->point.y,
fill_rule, &bo_traps);
if (status)
goto unwind;
@@ -1578,13 +1624,19 @@ static cairo_fixed_t
_compute_intersection_x_for_y (const cairo_line_t *line,
cairo_fixed_t y)
{
- cairo_fixed_t dx = line->p2.x - line->p1.x;
- cairo_fixed_t dy = line->p2.y - line->p1.y;
- cairo_fixed_t x;
+ cairo_fixed_t x, dy;
+
+ if (y == line->p1.y)
+ return line->p1.x;
+ if (y == line->p2.y)
+ return line->p2.x;
x = line->p1.x;
+ dy = line->p2.y - line->p1.y;
if (dy != 0)
- x += _cairo_fixed_mul_div_round (y - line->p1.y, dx, dy);
+ x += _cairo_fixed_mul_div_round (y - line->p1.y,
+ line->p2.x - line->p1.x,
+ dy);
return x;
}
@@ -1593,13 +1645,19 @@ static cairo_fixed_t
_compute_intersection_y_for_x (const cairo_line_t *line,
cairo_fixed_t x)
{
- cairo_fixed_t dx = line->p2.x - line->p1.x;
- cairo_fixed_t dy = line->p2.y - line->p1.y;
- cairo_fixed_t y;
+ cairo_fixed_t y, dx;
+
+ if (x == line->p1.x)
+ return line->p1.y;
+ if (x == line->p2.x)
+ return line->p2.y;
y = line->p1.y;
+ dx = line->p2.x - line->p1.x;
if (dx != 0)
- y += _cairo_fixed_mul_div_round (x - line->p1.x, dy, dx);
+ y += _cairo_fixed_mul_div_round (x - line->p1.x,
+ line->p2.y - line->p1.y,
+ dx);
return y;
}
@@ -1833,6 +1891,7 @@ dump_traps (cairo_traps_t *traps, const char *filename)
traps->traps[n].right.p2.x,
traps->traps[n].right.p2.y);
}
+ fprintf (file, "\n");
fclose (file);
}
}
--
1.5.6.3
--=-K1wYJ1mC6cXzAoBwV32N--
More information about the cairo
mailing list