[cairo] Tessellator performance patch
Rafael Villar Burke
pachi at rvburke.com
Sun Dec 10 13:21:17 PST 2006
This is a new version of the patch that passes all tests and still
brings in some speedup. It basically checks the input coordinates
significant bits and reduces precision in the computations when it's
overflow safe to avoid computing intersections with the existing 64 bit
precision. Joonas and me have been trying to discard subpixel
positioning information and always use 15bit coordinates, so the
determinant result fits in 32bits, but the error bounds are so high for
improper intersection checks that the speed gains vanish.
The speedups for this new patch are these:
Speedups
========
image-rgb tessellate-256-100 61.54 1.02% -> 32.81 5.66%: 1.88x speedup
â–‰
xlib-rgba tessellate-256-100 61.67 0.56% -> 33.86 5.06%: 1.82x speedup
â–‰
xlib-rgb tessellate-256-100 61.74 0.76% -> 34.98 6.07%: 1.77x speedup
â–Š
image-rgba tessellate-256-100 61.87 0.67% -> 36.33 5.85%: 1.70x speedup
â–Š
image-rgba zrusin_another_tessellate-415 14.61 1.36% -> 12.94 2.70%:
1.13x speedup
â–
xlib-rgb zrusin_another_tessellate-415 15.06 1.36% -> 13.50 2.05%: 1.12x
speedup
â–
xlib-rgba zrusin_another_tessellate-415 15.02 1.41% -> 13.53 4.45%:
1.11x speedup
â–
image-rgb zrusin_another_tessellate-415 14.58 1.78% -> 13.28 1.95%:
1.10x speedup
â–
image-rgba tessellate-16-100 0.13 1.20% -> 0.12 1.07%: 1.09x speedup
â–
image-rgb tessellate-16-100 0.13 1.09% -> 0.12 3.37%: 1.08x speedup
â–
image-rgb zrusin_another_fill-415 22.22 1.63% -> 20.57 1.56%: 1.08x speedup
â–
image-rgba zrusin_another_fill-415 22.17 1.65% -> 20.65 1.48%: 1.07x speedup
â–
xlib-rgba zrusin_another_fill-415 30.30 1.49% -> 28.70 1.33%: 1.06x speedup
xlib-rgb zrusin_another_fill-415 30.41 0.80% -> 28.82 1.09%: 1.06x speedup
Regards,
Rafael Villar Burke
--
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 4a72a8d..857e84a 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -796,6 +796,75 @@ _cairo_bo_event_queue_fini (cairo_bo_event_queue_t
*event_queue)
free (event_queue->sorted_startstop_event_ptrs);
}
+#define SUBPIXEL_PRECISION 2
+#define not_top_precision(i) (((i) >> (32-SUBPIXEL_PRECISION)) == 0)
+#define get_with_lower_precision(i) ((i) >> (16-SUBPIXEL_PRECISION))
+
+static cairo_bool_t
+_cairo_may_intersect (cairo_bo_edge_t const *edge1,
+ cairo_bo_edge_t const *edge2)
+{
+ /* Check wether the given edges MAY intersect using reduced precision
+ * arithmetic for colinearity and proper intersection tests.
+ * We discard some subpixel positioning information and use the estimate
+ * error due to it.
+ * If intersection is possible or no fast reduced precision checks can
+ * be done return TRUE, else return FALSE */
+
+ if (not_top_precision(edge1->top.x) &&
+ not_top_precision(edge1->top.y) &&
+ not_top_precision(edge1->bottom.x) &&
+ not_top_precision(edge1->bottom.y) &&
+ not_top_precision(edge2->top.x) &&
+ not_top_precision(edge2->top.y) &&
+ not_top_precision(edge2->bottom.x) &&
+ not_top_precision(edge2->bottom.y))
+ {
+ int32_t ax = get_with_lower_precision(edge1->top.x);
+ int32_t ay = get_with_lower_precision(edge1->top.y);
+ int32_t bx = get_with_lower_precision(edge1->bottom.x);
+ int32_t by = get_with_lower_precision(edge1->bottom.y);
+ int32_t cx = get_with_lower_precision(edge2->top.x);
+ int32_t cy = get_with_lower_precision(edge2->top.y);
+ int32_t dx = get_with_lower_precision(edge2->bottom.x);
+ int32_t dy = get_with_lower_precision(edge2->bottom.y);
+
+ /* Determinant evaluation |b-a, c-a| to find wether c lies on the
+ * a->b vector or on its right or left side.
+ * If positive, then point c lies on the left side of the a->b vector
+ * if negative, c lies on the right side
+ * if zero, c is on the vector a->b */
+ int32_t det_abc = ((bx - ax) * (cy - ay)) - ((cx - ax) * (by - ay));
+ int32_t det_abd = ((bx - ax) * (dy - ay)) - ((dx - ax) * (by - ay));
+ int32_t det_cda = ((dx - cx) * (ay - cy)) - ((ax - cx) * (dy - cy));
+ int32_t det_cdb = ((dx - cx) * (by - cy)) - ((bx - cx) * (dy - cy));
+
+ /* Proper intersection check: if proper intersection return TRUE */
+ if (((det_abc > 0) != (det_abd > 0)) && ((det_cda > 0) != (det_cdb >
0))) return TRUE;
+
+ /* Error limits.
+ * With a 0 to +1 unit error in the point coordinates, the determinant
+ * expression error is bounded by the following expressions: */
+ int32_t error_abc = ((abs(bx - ax) + abs(cy - ay) + abs(cx - ax) +
abs(by - ay))>>SUBPIXEL_PRECISION) + 1;
+ int32_t error_abd = ((abs(bx - ax) + abs(dy - ay) + abs(dx - ax) +
abs(by - ay))>>SUBPIXEL_PRECISION) + 1;
+ int32_t error_cda = ((abs(dx - cx) + abs(ay - cy) + abs(ax - cx) +
abs(dy - cy))>>SUBPIXEL_PRECISION) + 1;
+ int32_t error_cdb = ((abs(dx - cx) + abs(by - cy) + abs(bx - cx) +
abs(dy - cy))>>SUBPIXEL_PRECISION) + 1;
+
+ /* Colinearity check: if colinear, return True */
+ if (abs(det_abc) <= error_abc ||
+ abs(det_abd) <= error_abd ||
+ abs(det_cda) <= error_cda ||
+ abs(det_cdb) <= error_cdb)
+ return TRUE;
+
+ /* If no proper intersection and no collinearity are possible, then no
+ * intersection can happen */
+ return FALSE;
+ }
+ /* else we fallback to safe intersection computation */
+ else return TRUE;
+}
+
static void
_cairo_bo_event_queue_insert_if_intersect_below_current_y
(cairo_bo_event_queue_t *event_queue,
cairo_bo_edge_t *left,
@@ -808,6 +877,9 @@
_cairo_bo_event_queue_insert_if_intersect_below_current_y
(cairo_bo_event_queue_
if (left == NULL || right == NULL)
return;
+ if (!_cairo_may_intersect (left, right))
+ return;
+
/* The names "left" and "right" here are correct descriptions of
* the order of the two edges within the active edge list. So if a
* slope comparison also puts left less than right, then we know
-------------- next part --------------
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 4a72a8d..857e84a 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -796,6 +796,75 @@ _cairo_bo_event_queue_fini (cairo_bo_event_queue_t *event_queue)
free (event_queue->sorted_startstop_event_ptrs);
}
+#define SUBPIXEL_PRECISION 2
+#define not_top_precision(i) (((i) >> (32-SUBPIXEL_PRECISION)) == 0)
+#define get_with_lower_precision(i) ((i) >> (16-SUBPIXEL_PRECISION))
+
+static cairo_bool_t
+_cairo_may_intersect (cairo_bo_edge_t const *edge1,
+ cairo_bo_edge_t const *edge2)
+{
+ /* Check wether the given edges MAY intersect using reduced precision
+ * arithmetic for colinearity and proper intersection tests.
+ * We discard some subpixel positioning information and use the estimate
+ * error due to it.
+ * If intersection is possible or no fast reduced precision checks can
+ * be done return TRUE, else return FALSE */
+
+ if (not_top_precision(edge1->top.x) &&
+ not_top_precision(edge1->top.y) &&
+ not_top_precision(edge1->bottom.x) &&
+ not_top_precision(edge1->bottom.y) &&
+ not_top_precision(edge2->top.x) &&
+ not_top_precision(edge2->top.y) &&
+ not_top_precision(edge2->bottom.x) &&
+ not_top_precision(edge2->bottom.y))
+ {
+ int32_t ax = get_with_lower_precision(edge1->top.x);
+ int32_t ay = get_with_lower_precision(edge1->top.y);
+ int32_t bx = get_with_lower_precision(edge1->bottom.x);
+ int32_t by = get_with_lower_precision(edge1->bottom.y);
+ int32_t cx = get_with_lower_precision(edge2->top.x);
+ int32_t cy = get_with_lower_precision(edge2->top.y);
+ int32_t dx = get_with_lower_precision(edge2->bottom.x);
+ int32_t dy = get_with_lower_precision(edge2->bottom.y);
+
+ /* Determinant evaluation |b-a, c-a| to find wether c lies on the
+ * a->b vector or on its right or left side.
+ * If positive, then point c lies on the left side of the a->b vector
+ * if negative, c lies on the right side
+ * if zero, c is on the vector a->b */
+ int32_t det_abc = ((bx - ax) * (cy - ay)) - ((cx - ax) * (by - ay));
+ int32_t det_abd = ((bx - ax) * (dy - ay)) - ((dx - ax) * (by - ay));
+ int32_t det_cda = ((dx - cx) * (ay - cy)) - ((ax - cx) * (dy - cy));
+ int32_t det_cdb = ((dx - cx) * (by - cy)) - ((bx - cx) * (dy - cy));
+
+ /* Proper intersection check: if proper intersection return TRUE */
+ if (((det_abc > 0) != (det_abd > 0)) && ((det_cda > 0) != (det_cdb > 0))) return TRUE;
+
+ /* Error limits.
+ * With a 0 to +1 unit error in the point coordinates, the determinant
+ * expression error is bounded by the following expressions: */
+ int32_t error_abc = ((abs(bx - ax) + abs(cy - ay) + abs(cx - ax) + abs(by - ay))>>SUBPIXEL_PRECISION) + 1;
+ int32_t error_abd = ((abs(bx - ax) + abs(dy - ay) + abs(dx - ax) + abs(by - ay))>>SUBPIXEL_PRECISION) + 1;
+ int32_t error_cda = ((abs(dx - cx) + abs(ay - cy) + abs(ax - cx) + abs(dy - cy))>>SUBPIXEL_PRECISION) + 1;
+ int32_t error_cdb = ((abs(dx - cx) + abs(by - cy) + abs(bx - cx) + abs(dy - cy))>>SUBPIXEL_PRECISION) + 1;
+
+ /* Colinearity check: if colinear, return True */
+ if (abs(det_abc) <= error_abc ||
+ abs(det_abd) <= error_abd ||
+ abs(det_cda) <= error_cda ||
+ abs(det_cdb) <= error_cdb)
+ return TRUE;
+
+ /* If no proper intersection and no collinearity are possible, then no
+ * intersection can happen */
+ return FALSE;
+ }
+ /* else we fallback to safe intersection computation */
+ else return TRUE;
+}
+
static void
_cairo_bo_event_queue_insert_if_intersect_below_current_y (cairo_bo_event_queue_t *event_queue,
cairo_bo_edge_t *left,
@@ -808,6 +877,9 @@ _cairo_bo_event_queue_insert_if_intersect_below_current_y (cairo_bo_event_queue_
if (left == NULL || right == NULL)
return;
+ if (!_cairo_may_intersect (left, right))
+ return;
+
/* The names "left" and "right" here are correct descriptions of
* the order of the two edges within the active edge list. So if a
* slope comparison also puts left less than right, then we know
More information about the cairo
mailing list