[cairo-commit] src/cairo-traps.c
Carl Worth
cworth at kemper.freedesktop.org
Wed Mar 14 15:23:34 PDT 2007
src/cairo-traps.c | 372 ------------------------------------------------------
1 files changed, 372 deletions(-)
New commits:
diff-tree 5d23d0c90c31b233d5916c12eaf2a1dafc441243 (from 1f3a5b4e1283cc0e55f7ea6baca6d0fe67fd14b1)
Author: Carl Worth <cworth at cworth.org>
Date: Wed Mar 14 15:23:01 2007 -0700
Remove dead-code remnants of old tessellator
diff --git a/src/cairo-traps.c b/src/cairo-traps.c
index 33e6447..96b0a45 100644
--- a/src/cairo-traps.c
+++ b/src/cairo-traps.c
@@ -49,18 +49,9 @@ _cairo_traps_add_trap (cairo_traps_t *tr
static int
_compare_point_fixed_by_y (const void *av, const void *bv);
-static int
-_compare_cairo_edge_by_top (const void *av, const void *bv);
-
-static int
-_compare_cairo_edge_by_slope (const void *av, const void *bv);
-
static cairo_fixed_16_16_t
_compute_x (cairo_line_t *line, cairo_fixed_t y);
-static int
-_line_segs_intersect_ceil (cairo_line_t *left, cairo_line_t *right, cairo_fixed_t *y_ret);
-
void
_cairo_traps_init (cairo_traps_t *traps)
{
@@ -512,52 +503,6 @@ _cairo_traps_tessellate_convex_quad (cai
return traps->status;
}
-static int
-_compare_cairo_edge_by_top (const void *av, const void *bv)
-{
- const cairo_edge_t *a = av, *b = bv;
-
- return a->edge.p1.y - b->edge.p1.y;
-}
-
-/* Return value is:
- > 0 if a is "clockwise" from b, (in a mathematical, not a graphical sense)
- == 0 if slope (a) == slope (b)
- < 0 if a is "counter-clockwise" from b
-*/
-static int
-_compare_cairo_edge_by_slope (const void *av, const void *bv)
-{
- const cairo_edge_t *a = av, *b = bv;
- cairo_fixed_32_32_t d;
-
- cairo_fixed_48_16_t a_dx = a->edge.p2.x - a->edge.p1.x;
- cairo_fixed_48_16_t a_dy = a->edge.p2.y - a->edge.p1.y;
- cairo_fixed_48_16_t b_dx = b->edge.p2.x - b->edge.p1.x;
- cairo_fixed_48_16_t b_dy = b->edge.p2.y - b->edge.p1.y;
-
- d = b_dy * a_dx - a_dy * b_dx;
-
- if (d > 0)
- return 1;
- else if (d == 0)
- return 0;
- else
- return -1;
-}
-
-static int
-_compare_cairo_edge_by_current_x_slope (const void *av, const void *bv)
-{
- const cairo_edge_t *a = av, *b = bv;
- int ret;
-
- ret = a->current_x - b->current_x;
- if (ret == 0)
- ret = _compare_cairo_edge_by_slope (a, b);
- return ret;
-}
-
/* XXX: Both _compute_x and _compute_inverse_slope will divide by zero
for horizontal lines. Now, we "know" that when we are tessellating
polygons that the polygon data structure discards all horizontal
@@ -578,128 +523,6 @@ _compare_cairo_edge_by_current_x_slope (
doesn't matter much anyway).
*/
-/* XXX: Keith's new intersection code is much cleaner, and uses
- * sufficient precision for correctly sorting intersections according
- * to the analysis in Hobby's paper.
- *
- * But, when we enable this code, some things are failing, (eg. the
- * stars in test/fill_rule get filled wrong). This could indicate a
- * bug in one of tree places:
- *
- * 1) The new intersection code in this file
- *
- * 2) cairo_wideint.c (which is only exercised here)
- *
- * 3) In the current tessellator, (where the old intersection
- * code, with its mystic increments could be masking the bug).
- *
- * It will likely be easier to revisit this when the new tessellation
- * code is in place. So, for now, we'll simply disable the new
- * intersection code.
- */
-
-#define CAIRO_TRAPS_USE_NEW_INTERSECTION_CODE 0
-
-#if CAIRO_TRAPS_USE_NEW_INTERSECTION_CODE
-static const cairo_fixed_32_32_t
-_det16_32 (cairo_fixed_16_16_t a,
- cairo_fixed_16_16_t b,
- cairo_fixed_16_16_t c,
- cairo_fixed_16_16_t d)
-{
- return _cairo_int64_sub (_cairo_int32x32_64_mul (a, d),
- _cairo_int32x32_64_mul (b, c));
-}
-
-static const cairo_fixed_64_64_t
-_det32_64 (cairo_fixed_32_32_t a,
- cairo_fixed_32_32_t b,
- cairo_fixed_32_32_t c,
- cairo_fixed_32_32_t d)
-{
- return _cairo_int128_sub (_cairo_int64x64_128_mul (a, d),
- _cairo_int64x64_128_mul (b, c));
-}
-
-static const cairo_fixed_32_32_t
-_fixed_16_16_to_fixed_32_32 (cairo_fixed_16_16_t a)
-{
- return _cairo_int64_lsl (_cairo_int32_to_int64 (a), 16);
-}
-
-static int
-_line_segs_intersect_ceil (cairo_line_t *l1, cairo_line_t *l2, cairo_fixed_t *y_intersection)
-{
- cairo_fixed_16_16_t dx1, dx2, dy1, dy2;
- cairo_fixed_32_32_t den_det;
- cairo_fixed_32_32_t l1_det, l2_det;
- cairo_fixed_64_64_t num_det;
- cairo_fixed_32_32_t intersect_32_32;
- cairo_fixed_48_16_t intersect_48_16;
- cairo_fixed_16_16_t intersect_16_16;
- cairo_quorem128_t qr;
-
- dx1 = l1->p1.x - l1->p2.x;
- dy1 = l1->p1.y - l1->p2.y;
- dx2 = l2->p1.x - l2->p2.x;
- dy2 = l2->p1.y - l2->p2.y;
- den_det = _det16_32 (dx1, dy1,
- dx2, dy2);
-
- if (_cairo_int64_eq (den_det, _cairo_int32_to_int64(0)))
- return 0;
-
- l1_det = _det16_32 (l1->p1.x, l1->p1.y,
- l1->p2.x, l1->p2.y);
- l2_det = _det16_32 (l2->p1.x, l2->p1.y,
- l2->p2.x, l2->p2.y);
-
- num_det = _det32_64 (l1_det, _fixed_16_16_to_fixed_32_32 (dy1),
- l2_det, _fixed_16_16_to_fixed_32_32 (dy2));
-
- /*
- * Ok, this one is a bit tricky in fixed point, the denominator
- * needs to be left with 32-bits of fraction so that the
- * result of the divide ends up with 32-bits of fraction (64 - 32 = 32)
- */
- qr = _cairo_int128_divrem (num_det, _cairo_int64_to_int128 (den_det));
-
- intersect_32_32 = _cairo_int128_to_int64 (qr.quo);
-
- /*
- * Find the ceiling of the quotient -- divrem returns
- * the quotient truncated towards zero, so if the
- * quotient should be positive (num_den and den_det have same sign)
- * bump the quotient up by one.
- */
-
- if (_cairo_int128_ne (qr.rem, _cairo_int32_to_int128 (0)) &&
- (_cairo_int128_ge (num_det, _cairo_int32_to_int128 (0)) ==
- _cairo_int64_ge (den_det, _cairo_int32_to_int64 (0))))
- {
- intersect_32_32 = _cairo_int64_add (intersect_32_32,
- _cairo_int32_to_int64 (1));
- }
-
- /*
- * Now convert from 32.32 to 48.16 and take the ceiling;
- * this requires adding in 15 1 bits and shifting the result
- */
-
- intersect_32_32 = _cairo_int64_add (intersect_32_32,
- _cairo_int32_to_int64 ((1 << 16) - 1));
- intersect_48_16 = _cairo_int64_rsa (intersect_32_32, 16);
-
- /*
- * And drop the top bits
- */
- intersect_16_16 = _cairo_int64_to_int32 (intersect_48_16);
-
- *y_intersection = intersect_16_16;
-
- return 1;
-}
-#endif /* CAIRO_TRAPS_USE_NEW_INTERSECTION_CODE */
static cairo_fixed_16_16_t
_compute_x (cairo_line_t *line, cairo_fixed_t y)
@@ -711,201 +534,6 @@ _compute_x (cairo_line_t *line, cairo_fi
return line->p1.x + (ex / dy);
}
-#if ! CAIRO_TRAPS_USE_NEW_INTERSECTION_CODE
-static double
-_compute_inverse_slope (cairo_line_t *l)
-{
- return (_cairo_fixed_to_double (l->p2.x - l->p1.x) /
- _cairo_fixed_to_double (l->p2.y - l->p1.y));
-}
-
-static double
-_compute_x_intercept (cairo_line_t *l, double inverse_slope)
-{
- return _cairo_fixed_to_double (l->p1.x) - inverse_slope * _cairo_fixed_to_double (l->p1.y);
-}
-
-static int
-_line_segs_intersect_ceil (cairo_line_t *l1, cairo_line_t *l2, cairo_fixed_t *y_ret)
-{
- /*
- * x = m1y + b1
- * x = m2y + b2
- * m1y + b1 = m2y + b2
- * y * (m1 - m2) = b2 - b1
- * y = (b2 - b1) / (m1 - m2)
- */
- cairo_fixed_16_16_t y_intersect;
- double m1 = _compute_inverse_slope (l1);
- double b1 = _compute_x_intercept (l1, m1);
- double m2 = _compute_inverse_slope (l2);
- double b2 = _compute_x_intercept (l2, m2);
-
- if (m1 == m2)
- return 0;
-
- y_intersect = _cairo_fixed_from_double ((b2 - b1) / (m1 - m2));
-
- if (m1 < m2) {
- cairo_line_t *t;
- t = l1;
- l1 = l2;
- l2 = t;
- }
-
- /* Assuming 56 bits of floating point precision, the intersection
- is accurate within one sub-pixel coordinate. We must ensure
- that we return a value that is at or after the intersection. At
- most, we must increment once. */
- if (_compute_x (l2, y_intersect) > _compute_x (l1, y_intersect))
- y_intersect++;
- /* XXX: Hmm... Keith's error calculations said we'd at most be off
- by one sub-pixel. But, I found that the paint-fill-BE-01.svg
- test from the W3C SVG conformance suite definitely requires two
- increments.
-
- It could be that we need one to overcome the error, and another
- to round up.
-
- It would be nice to be sure this code is correct, (but we can't
- do the while loop as it will work for way to long on
- exceedingly distant intersections with large errors that we
- really don't care about anyway as they will be ignored by the
- calling function.
- */
- if (_compute_x (l2, y_intersect) > _compute_x (l1, y_intersect))
- y_intersect++;
- /* XXX: hmm... now I found "intersection_killer" inside xrspline.c
- that requires 3 increments. Clearly, we haven't characterized
- this completely yet. */
- if (_compute_x (l2, y_intersect) > _compute_x (l1, y_intersect))
- y_intersect++;
- /* I think I've found the answer to our problems. The insight is
- that everytime we round we are changing the slopes of the
- relevant lines, so we may be introducing new intersections that
- we miss, so everything breaks apart. John Hobby wrote a paper
- on how to fix this:
-
- [Hobby93c] John D. Hobby, Practical Segment Intersection with
- Finite Precision Output, Computation Geometry Theory and
- Applications, 13(4), 1999.
-
- Available online (2003-08017):
-
- http://cm.bell-labs.com/cm/cs/doc/93/2-27.ps.gz
-
- Now we just need to go off and implement that.
- */
-
- *y_ret = y_intersect;
-
- return 1;
-}
-#endif /* CAIRO_TRAPS_USE_NEW_INTERSECTION_CODE */
-
-/* The algorithm here is pretty simple:
-
- inactive = [edges]
- y = min_p1_y (inactive)
-
- while (num_active || num_inactive) {
- active = all edges containing y
-
- next_y = min ( min_p2_y (active), min_p1_y (inactive), min_intersection (active) )
-
- fill_traps (active, y, next_y, fill_rule)
-
- y = next_y
- }
-
- The invariants that hold during fill_traps are:
-
- All edges in active contain both y and next_y
- No edges in active intersect within y and next_y
-
- These invariants mean that fill_traps is as simple as sorting the
- active edges, forming a trapezoid between each adjacent pair. Then,
- either the even-odd or winding rule is used to determine whether to
- emit each of these trapezoids.
-
- Warning: This function obliterates the edges of the polygon provided.
-*/
-cairo_status_t
-_cairo_traps_tessellate_polygon (cairo_traps_t *traps,
- cairo_polygon_t *poly,
- cairo_fill_rule_t fill_rule)
-{
- int i, active, inactive;
- cairo_fixed_t y, y_next, intersect;
- int in_out, num_edges = poly->num_edges;
- cairo_edge_t *edges = poly->edges;
-
- if (num_edges == 0)
- return CAIRO_STATUS_SUCCESS;
-
- qsort (edges, num_edges, sizeof (cairo_edge_t), _compare_cairo_edge_by_top);
-
- y = edges[0].edge.p1.y;
- active = 0;
- inactive = 0;
- while (active < num_edges) {
- while (inactive < num_edges && edges[inactive].edge.p1.y <= y)
- inactive++;
-
- for (i = active; i < inactive; i++)
- edges[i].current_x = _compute_x (&edges[i].edge, y);
-
- qsort (&edges[active], inactive - active,
- sizeof (cairo_edge_t), _compare_cairo_edge_by_current_x_slope);
-
- /* find next inflection point */
- y_next = edges[active].edge.p2.y;
-
- for (i = active; i < inactive; i++) {
- if (edges[i].edge.p2.y < y_next)
- y_next = edges[i].edge.p2.y;
- /* check intersect */
- if (i != inactive - 1 && edges[i].current_x != edges[i+1].current_x)
- if (_line_segs_intersect_ceil (&edges[i].edge, &edges[i+1].edge,
- &intersect))
- if (intersect > y && intersect < y_next)
- y_next = intersect;
- }
- /* check next inactive point */
- if (inactive < num_edges && edges[inactive].edge.p1.y < y_next)
- y_next = edges[inactive].edge.p1.y;
-
- /* walk the active edges generating trapezoids */
- in_out = 0;
- for (i = active; i < inactive - 1; i++) {
- if (fill_rule == CAIRO_FILL_RULE_WINDING) {
- if (edges[i].clockWise)
- in_out++;
- else
- in_out--;
- if (in_out == 0)
- continue;
- } else {
- in_out++;
- if ((in_out & 1) == 0)
- continue;
- }
- _cairo_traps_add_trap (traps, y, y_next, &edges[i].edge, &edges[i+1].edge);
- }
-
- /* delete inactive edges */
- for (i = active; i < inactive; i++) {
- if (edges[i].edge.p2.y <= y_next) {
- memmove (&edges[active+1], &edges[active], (i - active) * sizeof (cairo_edge_t));
- active++;
- }
- }
-
- y = y_next;
- }
- return traps->status;
-}
-
static cairo_bool_t
_cairo_trap_contains (cairo_trapezoid_t *t, cairo_point_t *pt)
{
More information about the cairo-commit
mailing list