diff options
author | Chris Wilson <chris@chris-wilson.co.uk> | 2007-11-01 19:49:19 +0000 |
---|---|---|
committer | Chris Wilson <chris@chris-wilson.co.uk> | 2007-11-01 22:27:34 +0000 |
commit | 2a25e226588404da2970f473bdeb0d2ce106ce58 (patch) | |
tree | 6d16af3bb4da26c31a352e40718c2950e7ac2c77 /src/cairo-spline.c | |
parent | b311c414a27b7374540671b3ef7153b30def0451 (diff) | |
download | cairo-2a25e226588404da2970f473bdeb0d2ce106ce58.tar.gz |
[cairo-spline] Reduce stack requirements during recursive refinement.
By splitting out the knot vectors into a smaller, separate structure, we
can dramatically reduce the stack allocation for each level of recursion.
Secondly we can have the storage requirements by modifying the first set
of knots in-place, thus we need only allocate stack space for the knots
covering the deferred half of the spline.
Diffstat (limited to 'src/cairo-spline.c')
-rw-r--r-- | src/cairo-spline.c | 94 |
1 files changed, 47 insertions, 47 deletions
diff --git a/src/cairo-spline.c b/src/cairo-spline.c index 898ce7c31..779a15e38 100644 --- a/src/cairo-spline.c +++ b/src/cairo-spline.c @@ -40,45 +40,45 @@ static cairo_status_t _cairo_spline_grow (cairo_spline_t *spline); static cairo_status_t -_cairo_spline_add_point (cairo_spline_t *spline, cairo_point_t *point); +_cairo_spline_add_point (cairo_spline_t *spline, const cairo_point_t *point); static void -_lerp_half (cairo_point_t *a, cairo_point_t *b, cairo_point_t *result); +_lerp_half (const cairo_point_t *a, const cairo_point_t *b, cairo_point_t *result); static void -_de_casteljau (cairo_spline_t *spline, cairo_spline_t *s1, cairo_spline_t *s2); +_de_casteljau (cairo_spline_knots_t *s1, cairo_spline_knots_t *s2); static double -_cairo_spline_error_squared (cairo_spline_t *spline); +_cairo_spline_error_squared (const cairo_spline_knots_t *spline); static cairo_status_t -_cairo_spline_decompose_into (cairo_spline_t *spline, double tolerance_squared, cairo_spline_t *result); +_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, - cairo_point_t *a, cairo_point_t *b, - cairo_point_t *c, cairo_point_t *d) + const cairo_point_t *a, const cairo_point_t *b, + const cairo_point_t *c, const cairo_point_t *d) { - spline->a = *a; - spline->b = *b; - spline->c = *c; - spline->d = *d; + spline->knots.a = *a; + spline->knots.b = *b; + spline->knots.c = *c; + spline->knots.d = *d; if (a->x != b->x || a->y != b->y) - _cairo_slope_init (&spline->initial_slope, &spline->a, &spline->b); + _cairo_slope_init (&spline->initial_slope, &spline->knots.a, &spline->knots.b); else if (a->x != c->x || a->y != c->y) - _cairo_slope_init (&spline->initial_slope, &spline->a, &spline->c); + _cairo_slope_init (&spline->initial_slope, &spline->knots.a, &spline->knots.c); else if (a->x != d->x || a->y != d->y) - _cairo_slope_init (&spline->initial_slope, &spline->a, &spline->d); + _cairo_slope_init (&spline->initial_slope, &spline->knots.a, &spline->knots.d); else return CAIRO_INT_STATUS_DEGENERATE; if (c->x != d->x || c->y != d->y) - _cairo_slope_init (&spline->final_slope, &spline->c, &spline->d); + _cairo_slope_init (&spline->final_slope, &spline->knots.c, &spline->knots.d); else if (b->x != d->x || b->y != d->y) - _cairo_slope_init (&spline->final_slope, &spline->b, &spline->d); + _cairo_slope_init (&spline->final_slope, &spline->knots.b, &spline->knots.d); else - _cairo_slope_init (&spline->final_slope, &spline->a, &spline->d); + _cairo_slope_init (&spline->final_slope, &spline->knots.a, &spline->knots.d); spline->points = spline->points_embedded; spline->points_size = ARRAY_LENGTH (spline->points_embedded); @@ -114,7 +114,7 @@ _cairo_spline_grow (cairo_spline_t *spline) 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)); + new_size, sizeof (cairo_point_t)); } if (new_points == NULL) @@ -127,7 +127,7 @@ _cairo_spline_grow (cairo_spline_t *spline) } static cairo_status_t -_cairo_spline_add_point (cairo_spline_t *spline, cairo_point_t *point) +_cairo_spline_add_point (cairo_spline_t *spline, const cairo_point_t *point) { cairo_status_t status; cairo_point_t *prev; @@ -151,39 +151,38 @@ _cairo_spline_add_point (cairo_spline_t *spline, cairo_point_t *point) } static void -_lerp_half (cairo_point_t *a, cairo_point_t *b, cairo_point_t *result) +_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_t *spline, cairo_spline_t *s1, cairo_spline_t *s2) +_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 (&spline->a, &spline->b, &ab); - _lerp_half (&spline->b, &spline->c, &bc); - _lerp_half (&spline->c, &spline->d, &cd); + _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); - s1->a = spline->a; - s1->b = ab; - s1->c = abbc; - s1->d = final; - s2->a = final; s2->b = bccd; s2->c = cd; - s2->d = spline->d; + s2->d = s1->d; + + s1->b = ab; + s1->c = abbc; + s1->d = final; } static double -_PointDistanceSquaredToPoint (cairo_point_t *a, cairo_point_t *b) +_PointDistanceSquaredToPoint (const cairo_point_t *a, const cairo_point_t *b) { double dx = _cairo_fixed_to_double (b->x - a->x); double dy = _cairo_fixed_to_double (b->y - a->y); @@ -192,7 +191,7 @@ _PointDistanceSquaredToPoint (cairo_point_t *a, cairo_point_t *b) } static double -_PointDistanceSquaredToSegment (cairo_point_t *p, cairo_point_t *p1, cairo_point_t *p2) +_PointDistanceSquaredToSegment (const cairo_point_t *p, const cairo_point_t *p1, const cairo_point_t *p2) { double u; double dx, dy; @@ -209,12 +208,12 @@ _PointDistanceSquaredToSegment (cairo_point_t *p, cairo_point_t *p1, cairo_point u = ((p - p1) . (p2 - p1)) / (||(p2 - p1)|| ^ 2); */ + if (p2->x == p1->x && p2->y == p1->y) + return _PointDistanceSquaredToPoint (p, p1); + dx = _cairo_fixed_to_double (p2->x - p1->x); dy = _cairo_fixed_to_double (p2->y - p1->y); - if (dx == 0 && dy == 0) - return _PointDistanceSquaredToPoint (p, p1); - pdx = _cairo_fixed_to_double (p->x - p1->x); pdy = _cairo_fixed_to_double (p->y - p1->y); @@ -234,12 +233,12 @@ _PointDistanceSquaredToSegment (cairo_point_t *p, cairo_point_t *p1, cairo_point /* 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 -_cairo_spline_error_squared (cairo_spline_t *spline) +_cairo_spline_error_squared (const cairo_spline_knots_t *knots) { double berr, cerr; - berr = _PointDistanceSquaredToSegment (&spline->b, &spline->a, &spline->d); - cerr = _PointDistanceSquaredToSegment (&spline->c, &spline->a, &spline->d); + berr = _PointDistanceSquaredToSegment (&knots->b, &knots->a, &knots->d); + cerr = _PointDistanceSquaredToSegment (&knots->c, &knots->a, &knots->d); if (berr > cerr) return berr; @@ -248,18 +247,17 @@ _cairo_spline_error_squared (cairo_spline_t *spline) } static cairo_status_t -_cairo_spline_decompose_into (cairo_spline_t *spline, double tolerance_squared, cairo_spline_t *result) +_cairo_spline_decompose_into (cairo_spline_knots_t *s1, double tolerance_squared, cairo_spline_t *result) { + cairo_spline_knots_t s2; cairo_status_t status; - cairo_spline_t s1, s2; - if (_cairo_spline_error_squared (spline) < tolerance_squared) { - return _cairo_spline_add_point (result, &spline->a); - } + if (_cairo_spline_error_squared (s1) < tolerance_squared) + return _cairo_spline_add_point (result, &s1->a); - _de_casteljau (spline, &s1, &s2); + _de_casteljau (s1, &s2); - status = _cairo_spline_decompose_into (&s1, tolerance_squared, result); + status = _cairo_spline_decompose_into (s1, tolerance_squared, result); if (status) return status; @@ -274,15 +272,17 @@ cairo_status_t _cairo_spline_decompose (cairo_spline_t *spline, double tolerance) { cairo_status_t status; + cairo_spline_knots_t s1; /* reset the spline, but keep the buffer */ spline->num_points = 0; - status = _cairo_spline_decompose_into (spline, tolerance * tolerance, spline); + s1 = spline->knots; + status = _cairo_spline_decompose_into (&s1, tolerance * tolerance, spline); if (status) return status; - status = _cairo_spline_add_point (spline, &spline->d); + status = _cairo_spline_add_point (spline, &spline->knots.d); if (status) return status; |