[PATCH] [spline] Bisection search for optimal subdivision.
Chris Wilson
chris at chris-wilson.co.uk
Tue Oct 14 10:32:55 PDT 2008
Perform a bisection search for the point along the spline that produces a
subdivision of exactly the tolerance requested.
Whilst replaying gnome-system-monitor which generates smooth, continuous
graphs of system resources, the number of points produced along each curve
was on average almost halved. Although the bisection search made the
spline decomposition 3x more expensive, that was more than recouped by a
20% reduction in the runtime of the tessellator - overall the benchmark
improved by a measly 8%.
---
src/cairo-spline.c | 152 +++++++++++++++++++++++++--------------------------
1 files changed, 75 insertions(+), 77 deletions(-)
diff --git a/src/cairo-spline.c b/src/cairo-spline.c
index b39257e..b9e4d91 100644
--- a/src/cairo-spline.c
+++ b/src/cairo-spline.c
@@ -36,24 +36,6 @@
#include "cairoint.h"
-static cairo_status_t
-_cairo_spline_grow (cairo_spline_t *spline);
-
-static cairo_status_t
-_cairo_spline_add_point (cairo_spline_t *spline, const cairo_point_t *point);
-
-static void
-_lerp_half (const cairo_point_t *a, const cairo_point_t *b, cairo_point_t *result);
-
-static void
-_de_casteljau (cairo_spline_knots_t *s1, cairo_spline_knots_t *s2);
-
-static double
-_cairo_spline_error_squared (const cairo_spline_knots_t *spline);
-
-static cairo_status_t
-_cairo_spline_decompose_into (cairo_spline_knots_t *spline, double tolerance_squared, cairo_spline_t *result);
-
cairo_int_status_t
_cairo_spline_init (cairo_spline_t *spline,
const cairo_point_t *a, const cairo_point_t *b,
@@ -110,8 +92,10 @@ _cairo_spline_grow (cairo_spline_t *spline)
if (spline->points == spline->points_embedded) {
new_points = _cairo_malloc_ab (new_size, sizeof (cairo_point_t));
- if (new_points)
- memcpy (new_points, spline->points, old_size * sizeof (cairo_point_t));
+ if (new_points) {
+ memcpy (new_points, spline->points,
+ old_size * sizeof (cairo_point_t));
+ }
} else {
new_points = _cairo_realloc_ab (spline->points,
new_size, sizeof (cairo_point_t));
@@ -144,43 +128,11 @@ _cairo_spline_add_point (cairo_spline_t *spline, const cairo_point_t *point)
return status;
}
- spline->points[spline->num_points] = *point;
- spline->num_points++;
+ spline->points[spline->num_points++] = *point;
return CAIRO_STATUS_SUCCESS;
}
-static void
-_lerp_half (const cairo_point_t *a, const cairo_point_t *b, cairo_point_t *result)
-{
- result->x = a->x + ((b->x - a->x) >> 1);
- result->y = a->y + ((b->y - a->y) >> 1);
-}
-
-static void
-_de_casteljau (cairo_spline_knots_t *s1, cairo_spline_knots_t *s2)
-{
- cairo_point_t ab, bc, cd;
- cairo_point_t abbc, bccd;
- cairo_point_t final;
-
- _lerp_half (&s1->a, &s1->b, &ab);
- _lerp_half (&s1->b, &s1->c, &bc);
- _lerp_half (&s1->c, &s1->d, &cd);
- _lerp_half (&ab, &bc, &abbc);
- _lerp_half (&bc, &cd, &bccd);
- _lerp_half (&abbc, &bccd, &final);
-
- s2->a = final;
- s2->b = bccd;
- s2->c = cd;
- s2->d = s1->d;
-
- s1->b = ab;
- s1->c = abbc;
- s1->d = final;
-}
-
/* Return an upper bound on the error (squared) that could result from
* approximating a spline as a line segment connecting the two endpoints. */
static double
@@ -243,45 +195,91 @@ _cairo_spline_error_squared (const cairo_spline_knots_t *knots)
return cerr;
}
-static cairo_status_t
-_cairo_spline_decompose_into (cairo_spline_knots_t *s1, double tolerance_squared, cairo_spline_t *result)
+static void
+_lerp (const cairo_point_t *a,
+ const cairo_point_t *b,
+ int t,
+ cairo_point_t *result)
{
- cairo_spline_knots_t s2;
- cairo_status_t status;
-
- if (_cairo_spline_error_squared (s1) < tolerance_squared)
- return _cairo_spline_add_point (result, &s1->a);
-
- _de_casteljau (s1, &s2);
-
- status = _cairo_spline_decompose_into (s1, tolerance_squared, result);
- if (status)
- return status;
+ result->x = a->x + ((t * (b->x - a->x)) >> 8);
+ result->y = a->y + ((t * (b->y - a->y)) >> 8);
+}
- status = _cairo_spline_decompose_into (&s2, tolerance_squared, result);
- if (status)
- return status;
+static void
+_de_casteljau (const cairo_spline_knots_t *s1,
+ int t,
+ cairo_spline_knots_t *s2,
+ cairo_spline_knots_t *s3)
+{
+ cairo_point_t ab, bc, cd;
+ cairo_point_t abbc, bccd;
+ cairo_point_t final;
- return CAIRO_STATUS_SUCCESS;
+ _lerp (&s1->a, &s1->b, t, &ab);
+ _lerp (&s1->b, &s1->c, t, &bc);
+ _lerp (&s1->c, &s1->d, t, &cd);
+ _lerp (&ab, &bc, t, &abbc);
+ _lerp (&bc, &cd, t, &bccd);
+ _lerp (&abbc, &bccd, t, &final);
+
+ s3->a = final;
+ s3->b = bccd;
+ s3->c = cd;
+ s3->d = s1->d;
+
+ s2->a = s1->a;
+ s2->b = ab;
+ s2->c = abbc;
+ s2->d = final;
}
+#define TOLERANCE (_cairo_fixed_to_double(1)*_cairo_fixed_to_double(1))
cairo_status_t
-_cairo_spline_decompose (cairo_spline_t *spline, double tolerance)
+_cairo_spline_decompose (cairo_spline_t *spline,
+ double tolerance)
{
+ cairo_spline_knots_t s1, s2, s3;
cairo_status_t status;
- cairo_spline_knots_t s1;
/* reset the spline, but keep the buffer */
spline->num_points = 0;
+ tolerance *= tolerance;
s1 = spline->knots;
- status = _cairo_spline_decompose_into (&s1, tolerance * tolerance, spline);
+ status = _cairo_spline_add_point (spline, &s1.a);
if (status)
return status;
- status = _cairo_spline_add_point (spline, &spline->knots.d);
- if (status)
- return status;
+ do {
+ int lo, hi;
+ double error;
- return CAIRO_STATUS_SUCCESS;
+ error = _cairo_spline_error_squared (&s1);
+ if (error <= tolerance)
+ break;
+
+ lo = 0;
+ hi = 256;
+ do {
+ double mid = (hi + lo) >> 1;
+
+ _de_casteljau (&s1, mid, &s2, &s3);
+
+ error = _cairo_spline_error_squared (&s2);
+ if (error < tolerance - TOLERANCE) {
+ lo = mid;
+ } else if (error > tolerance + TOLERANCE) {
+ hi = mid;
+ } else
+ break;
+ } while (hi - lo > 1);
+
+ status = _cairo_spline_add_point (spline, &s2.d);
+ if (status)
+ return status;
+
+ s1 = s3;
+ } while (TRUE);
+
+ return _cairo_spline_add_point (spline, &spline->knots.d);
}
--
1.5.6.3
--=-Rp9tfI3PA/eI6jFt90oT--
More information about the cairo
mailing list