[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