[cairo] git "performance" patchset # 1 available + a few questions
David Turner
david at freetype.org
Thu Aug 31 16:47:25 PDT 2006
Hi Carl,
I finally salvaged the relevant patches, I'm sending them attached
to this e-mail. Please note that the last one (gradient optimizations)
does "break" the test suite (on my system, the number of failed tests
jumps from 9 to 16).
I hope I'll be able to contribute more to the project in a few weeks,
once I'm settled in my new job
Best Regards,
- David
On Thu, 31 Aug 2006 15:07:29 +0200, "David Turner" <dturner at nds.com> said:
> Carl Worth a écrit :
> >> Anyway, I can send you right now a copy of the original patch files, but
> >> they were diff-ed against 1.1.6
> >> and I could never apply them to recent versions of Cairo,
> >> unfortunately.
> >>
> >
> > I could make do with that just fine.
> >
> >
> Here's the original patch. I'd like to ask you to wait until tomorrow
> though, because I'm
> pretty certain that there is a major bug in it that might crash cairo
> under rare conditions
> (the inline assembly isn't correctly proofed against all divide
> overflow/underflows)
>
> I have a correct version in my git repo, and I'll track to extract it
> tonight from home.
>
> > Oh, it's too bad you've lost work. That's no fun. It's perhaps worth
> > noting that even if you do something "destructive" like "git reset"
> > that it only moves references around. Previously-made commits can be
> > left "dangling", (with no branches referring to them), but they can be
> > recovered easily enough by running "git fsck-objects" to list the
> > references.
> >
> >
> Ah ! I understood the fact that the commits were still there, dangling
> somewhere, but couldn't
> find a way to find their name :-) I wouldn't imagined that fsck-objects
> would do it. thanks a lot.
> > On the other hand, "git prune" is truly destructive as it will delete
> > the unreachable objects.
> >
> >
> Yes, fortunately, I didn't use that.
> > But, yeah, git does take a bit of getting used to. I had the benefit
> > of sitting through a hands-on tutorial with someone very proficient in
> > git, and that was vastly more helpful than the things I was able to
> > read. I think I've also been successful at bringing new people up to
> > speed with git quite quickly in person, but I'm not yet aware of a
> > great means for acquiring the proper mental model by just reading
> > available tutorials.
> >
> >
> I agree that the all the currently available tutorials are very poor. I
> quite understand what is in
> git-core, what's lacking is a proper explanation of the higher levels of
> branch management, what's
> really happening during merges, and more importantly conflict resolution.
>
> Maybe if I have more time in the future will I write something about
> that.
>
> > If you could find a way to get that git repository to me, then I could
> > definitely help you figure out what's going on. In the meantime, if
> > you can look at things in either "git log" or gitk and find the commit
> > IDs of your <first> and <last> commits, (assuming they're in a linear
> > sequence), then you should be able to extract them as patches easily
> > enough with a command like:
> >
> > git format-patch first..last
> >
> > But, sure, if you don't want to be bothered with git, then just
> > sending the patches you have one by one to the list is perfectly
> > fine.
> >
> >
> That should be possible, I'm going to try that tonight !!
> > Bizarre. I just manually subscribed that address. Please let me know
> > if you don't get the welcome message and if you don't get any list
> > messages to that address. If not, I'll get an admin who knows more
> > about mail than I do to look at the issue.
> >
> >
> OK, I've just checked, and I still haven't received anything at the
> moment, though this may
> be a normal delay from Mailman. My take on the issue is that my address
> is probably part
> of one or more black-list, because many spammers and viruses are using
> fake source
> addresses in the @freetype.org domain, unfortunately.
>
> I guess, I'll need a new public e-mail address soon :-(
>
> Thanks a lot for the info, I hope to provide you with something useful
> tomorrow.
>
> Regards,
>
> - David
> ***********************************************************************************
> Information contained in this email message is confidential and may be
> privileged, and is intended only for use of the individual or entity
> named above. If the reader of this message is not the intended recipient,
> or the employee or agent responsible to deliver it to the intended
> recipient, you are hereby notified that any dissemination, distribution
> or copying of this communication is strictly prohibited. If you have
> received this communication in error, please immediately notify the
> postmaster at nds.com and destroy the original message.
> ***********************************************************************************
>
- David Turner
- The FreeType Project (www.freetype.org)
-------------- next part --------------
Subject: [PATCH] - changing _cairo_fixed_to_double into a macro
- introducing _cairo_polygon_init_static
- introducing _cairo_spline_decompose_direct
- performance optimization of the spline flatening algorithm
(doesn't change the spline decomposition, simply computes it faster)
---
src/cairo-fixed.c | 6 -
src/cairo-polygon.c | 11 ++
src/cairo-spline.c | 266 ++++++++++++++++++++++++++++-----------------------
src/cairoint.h | 19 +++-
4 files changed, 175 insertions(+), 127 deletions(-)
864ab0b1d051eb4b02f7c4e086ae557cec7fd99c
diff --git a/src/cairo-fixed.c b/src/cairo-fixed.c
index 604c9e7..8c057b3 100644
--- a/src/cairo-fixed.c
+++ b/src/cairo-fixed.c
@@ -54,12 +54,6 @@ _cairo_fixed_from_26_6 (uint32_t i)
return i << 10;
}
-double
-_cairo_fixed_to_double (cairo_fixed_t f)
-{
- return ((double) f) / 65536.0;
-}
-
int
_cairo_fixed_is_integer (cairo_fixed_t f)
{
diff --git a/src/cairo-polygon.c b/src/cairo-polygon.c
index dc9d380..60162d5 100644
--- a/src/cairo-polygon.c
+++ b/src/cairo-polygon.c
@@ -54,6 +54,17 @@ _cairo_polygon_init (cairo_polygon_t *po
}
void
+_cairo_polygon_init_static (cairo_polygon_t *polygon,
+ int num_edges,
+ cairo_edge_t *edges)
+{
+ _cairo_polygon_init (polygon);
+
+ polygon->edges = edges;
+ polygon->edges_size = num_edges;
+}
+
+void
_cairo_polygon_fini (cairo_polygon_t *polygon)
{
if (polygon->edges_size) {
diff --git a/src/cairo-spline.c b/src/cairo-spline.c
index 900d3ca..5030703 100644
--- a/src/cairo-spline.c
+++ b/src/cairo-spline.c
@@ -42,18 +42,6 @@ _cairo_spline_grow_by (cairo_spline_t *s
static cairo_status_t
_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);
-
-static void
-_de_casteljau (cairo_spline_t *spline, cairo_spline_t *s1, cairo_spline_t *s2);
-
-static double
-_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_int_status_t
_cairo_spline_init (cairo_spline_t *spline,
cairo_point_t *a, cairo_point_t *b,
@@ -144,142 +132,182 @@ _cairo_spline_add_point (cairo_spline_t
return CAIRO_STATUS_SUCCESS;
}
-static void
-_lerp_half (cairo_point_t *a, 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)
-{
- 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 (&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;
-}
-static double
-_PointDistanceSquaredToPoint (cairo_point_t *a, cairo_point_t *b)
-{
- double dx = _cairo_fixed_to_double (b->x - a->x);
- double dy = _cairo_fixed_to_double (b->y - a->y);
-
- return dx*dx + dy*dy;
-}
-
-static double
-_PointDistanceSquaredToSegment (cairo_point_t *p, cairo_point_t *p1, cairo_point_t *p2)
+static int
+_cairo_spline_point_proximity (cairo_point_t *a,
+ cairo_point_t *b,
+ double tolerance2)
+{
+ double dx = b->x - a->x;
+ double dy = b->y - a->y;
+
+ return (dx*dx+dy*dy) < tolerance2*(65536.0*65536.0);
+}
+
+/* this function determines wether a bezier is sufficiently
+ * 'straight' to be approximated by a simple line segment.
+ *
+ * this implementation simply checks that both control points
+ * are sufficiently near the segment, i.e.,
+ *
+ * dist(b,ad)^2 < tolerance_squared &&
+ * dist(c,ad)^2 < tolerance_squared
+ *
+ * this is a re-implementation of the original _cairo_spline_error_squared
+ * function that backs-off as soon as possible, and avoids re-computing
+ * various things for each control point
+ *
+ * it is possible to use a much faster algorithm based on
+ * shifts and adds and some useful properties of cubic beziers, but
+ * this will slightly change the interpretation of the tolerance
+ * parameter, and is likely to subtly change the number of
+ * spline sub-beziers generated, and this would fail the cairo
+ * test suite.
+ */
+static int
+_cairo_spline_is_straight (cairo_point_t *base, double tolerance2)
{
double u;
- double dx, dy;
+ double dx, dy, len2;
double pdx, pdy;
cairo_point_t px;
+ cairo_point_t *p1, *p2, *p;
- /* intersection point (px):
-
- px = p1 + u(p2 - p1)
- (p - px) . (p2 - p1) = 0
-
- Thus:
+ p1 = &base[3];
+ p2 = &base[0];
- u = ((p - p1) . (p2 - p1)) / (||(p2 - p1)|| ^ 2);
- */
+ if ( p1->x == p2->x && p1->y && p2->y )
+ return _cairo_spline_point_proximity( &base[1], p1, tolerance2) &&
+ _cairo_spline_point_proximity( &base[2], p2, tolerance2);
- 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);
+ dx = _cairo_fixed_to_double (p2->x - p1->x);
+ dy = _cairo_fixed_to_double (p2->y - p1->y);
+ len2 = dx*dx + dy*dy;
+ /* handle first control point */
+ p = &base[1];
pdx = _cairo_fixed_to_double (p->x - p1->x);
pdy = _cairo_fixed_to_double (p->y - p1->y);
- u = (pdx * dx + pdy * dy) / (dx*dx + dy*dy);
+ u = (pdx * dx + pdy * dy);
- if (u <= 0)
- return _PointDistanceSquaredToPoint (p, p1);
- else if (u >= 1)
- return _PointDistanceSquaredToPoint (p, p2);
+ if (u <= 0) {
+ if (!_cairo_spline_point_proximity (p, p1, tolerance2))
+ return 0;
+ } else if (u >= len2) {
+ if (!_cairo_spline_point_proximity (p, p2, tolerance2))
+ return 0;
+ } else {
+ u /= len2;
- px.x = p1->x + u * (p2->x - p1->x);
- px.y = p1->y + u * (p2->y - p1->y);
+ px.x = p1->x + u * (p2->x - p1->x);
+ px.y = p1->y + u * (p2->y - p1->y);
- return _PointDistanceSquaredToPoint (p, &px);
-}
+ if (!_cairo_spline_point_proximity (p, &px, tolerance2))
+ return 0;
+ }
-/* 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)
-{
- double berr, cerr;
+ /* handle second control point */
+ p = &base[2];
+ pdx = _cairo_fixed_to_double (p->x - p1->x);
+ pdy = _cairo_fixed_to_double (p->y - p1->y);
- berr = _PointDistanceSquaredToSegment (&spline->b, &spline->a, &spline->d);
- cerr = _PointDistanceSquaredToSegment (&spline->c, &spline->a, &spline->d);
+ u = (pdx * dx + pdy * dy);
- if (berr > cerr)
- return berr;
- else
- return cerr;
-}
+ if (u <= 0) {
+ return _cairo_spline_point_proximity (p, p1, tolerance2);
+ } else if (u >= len2) {
+ return _cairo_spline_point_proximity (p, p2, tolerance2);
+ } else {
+ u /= len2;
-static cairo_status_t
-_cairo_spline_decompose_into (cairo_spline_t *spline, double tolerance_squared, cairo_spline_t *result)
-{
- cairo_status_t status;
- cairo_spline_t s1, s2;
+ px.x = p1->x + u * (p2->x - p1->x);
+ px.y = p1->y + u * (p2->y - p1->y);
- if (_cairo_spline_error_squared (spline) < tolerance_squared) {
- return _cairo_spline_add_point (result, &spline->a);
+ return _cairo_spline_point_proximity (p, &px, tolerance2);
}
-
- _de_casteljau (spline, &s1, &s2);
-
- status = _cairo_spline_decompose_into (&s1, tolerance_squared, result);
- if (status)
- return status;
-
- status = _cairo_spline_decompose_into (&s2, tolerance_squared, result);
- if (status)
- return status;
-
- return CAIRO_STATUS_SUCCESS;
}
cairo_status_t
-_cairo_spline_decompose (cairo_spline_t *spline, double tolerance)
-{
- cairo_status_t status;
+_cairo_spline_decompose_direct (cairo_spline_t *spline,
+ double tolerance,
+ cairo_spline_point_func_t *point_func,
+ void *point_closure,
+ cairo_bool_t keep_first)
+{
+ cairo_point_t stack[64];
+ cairo_point_t *base;
+ cairo_status_t status;
+ double tolerance_squared = tolerance*tolerance;
if (spline->points_size) {
- _cairo_spline_fini (spline);
+ _cairo_spline_fini (spline);
}
- status = _cairo_spline_decompose_into (spline, tolerance * tolerance, spline);
- if (status)
- return status;
+ base = stack;
+ base[0] = spline->d;
+ base[1] = spline->c;
+ base[2] = spline->b;
+ base[3] = spline->a;
+
+ for (;;)
+ {
+ if (base + 7 > stack + 64 ||
+ _cairo_spline_is_straight (base, tolerance_squared))
+ {
+ if (!keep_first) {
+ keep_first = 1;
+ } else {
+ status = (*point_func) (point_closure, &base[3]);
+ if (status)
+ goto BAIL;
+ }
+
+ if (base == stack)
+ break;
+
+ base -= 3;
+ }
+ else
+ {
+ /* decasteljau directly in the stack */
+ cairo_fixed_t a, b, c, d;
+
+ base[6].x = base[3].x;
+ c = base[1].x;
+ d = base[2].x;
+ base[1].x = a = ( base[0].x + c ) / 2;
+ base[5].x = b = ( base[3].x + d ) / 2;
+ c = ( c + d ) / 2;
+ base[2].x = a = ( a + c ) / 2;
+ base[4].x = b = ( b + c ) / 2;
+ base[3].x = ( a + b ) / 2;
+
+ base[6].y = base[3].y;
+ c = base[1].y;
+ d = base[2].y;
+ base[1].y = a = ( base[0].y + c ) / 2;
+ base[5].y = b = ( base[3].y + d ) / 2;
+ c = ( c + d ) / 2;
+ base[2].y = a = ( a + c ) / 2;
+ base[4].y = b = ( b + c ) / 2;
+ base[3].y = ( a + b ) / 2;
- status = _cairo_spline_add_point (spline, &spline->d);
- if (status)
- return status;
+ base += 3;
+ }
+ }
- return CAIRO_STATUS_SUCCESS;
+ status = (*point_func) (point_closure, &spline->d);
+BAIL:
+ return status;
+}
+
+
+cairo_status_t
+_cairo_spline_decompose (cairo_spline_t *spline, double tolerance)
+{
+ return _cairo_spline_decompose_direct (spline, tolerance,
+ (cairo_spline_point_func_t*) &_cairo_spline_add_point,
+ spline, 1);
}
diff --git a/src/cairoint.h b/src/cairoint.h
index 119ee26..76d52fc 100644
--- a/src/cairoint.h
+++ b/src/cairoint.h
@@ -356,6 +356,10 @@ typedef struct _cairo_spline {
cairo_point_t *points;
} cairo_spline_t;
+typedef cairo_status_t
+(cairo_spline_point_func_t) (void *closure,
+ cairo_point_t *point);
+
typedef struct _cairo_pen_vertex {
cairo_point_t point;
@@ -1126,8 +1130,7 @@ _cairo_fixed_from_double (double d);
cairo_private cairo_fixed_t
_cairo_fixed_from_26_6 (uint32_t i);
-cairo_private double
-_cairo_fixed_to_double (cairo_fixed_t f);
+#define _cairo_fixed_to_double(f) ((double)(f)/65536.0)
cairo_private int
_cairo_fixed_is_integer (cairo_fixed_t f);
@@ -2082,6 +2085,11 @@ cairo_private void
_cairo_polygon_init (cairo_polygon_t *polygon);
cairo_private void
+_cairo_polygon_init_static (cairo_polygon_t *polygon,
+ int num_edges,
+ cairo_edge_t *edges);
+
+cairo_private void
_cairo_polygon_fini (cairo_polygon_t *polygon);
cairo_private cairo_status_t
@@ -2107,6 +2115,13 @@ _cairo_spline_init (cairo_spline_t *spli
cairo_private cairo_status_t
_cairo_spline_decompose (cairo_spline_t *spline, double tolerance);
+cairo_private cairo_status_t
+_cairo_spline_decompose_direct (cairo_spline_t *spline,
+ double tolerance,
+ cairo_spline_point_func_t *point_func,
+ void *point_closure,
+ cairo_bool_t keep_first);
+
cairo_private void
_cairo_spline_fini (cairo_spline_t *spline);
--
1.1.3
-------------- next part --------------
Subject: [PATCH] - modification of the path filler to use _cairo_spline_decompose_direct,
in order to avoid un-necessary memory allocations and copies
- introducing _cairo_path_fixed_fill_extents, to compute the extents
of a path without any tessellation (major speedup here).
---
src/cairo-gstate.c | 17 ++-----
src/cairo-path-fill.c | 120 ++++++++++++++++++++++++++++++++++++++++++++-----
src/cairoint.h | 6 ++
3 files changed, 118 insertions(+), 25 deletions(-)
cbf0e6a3cbd5ed7d60d437fb5129ec68a9b68dd0
diff --git a/src/cairo-gstate.c b/src/cairo-gstate.c
index 2f9079b..543286b 100644
--- a/src/cairo-gstate.c
+++ b/src/cairo-gstate.c
@@ -1085,20 +1085,15 @@ _cairo_gstate_fill_extents (cairo_gstate
double *x2, double *y2)
{
cairo_status_t status;
- cairo_traps_t traps;
- cairo_box_t extents;
+ cairo_box_t extents;
- _cairo_traps_init (&traps);
-
- status = _cairo_path_fixed_fill_to_traps (path,
- gstate->fill_rule,
- gstate->tolerance,
- &traps);
+ status = _cairo_path_fixed_fill_extents (path,
+ gstate->fill_rule,
+ gstate->tolerance,
+ &extents);
if (status)
goto BAIL;
- _cairo_traps_extents (&traps, &extents);
-
*x1 = _cairo_fixed_to_double (extents.p1.x);
*y1 = _cairo_fixed_to_double (extents.p1.y);
*x2 = _cairo_fixed_to_double (extents.p2.x);
@@ -1108,8 +1103,6 @@ _cairo_gstate_fill_extents (cairo_gstate
_cairo_gstate_backend_to_user (gstate, x2, y2);
BAIL:
- _cairo_traps_fini (&traps);
-
return status;
}
diff --git a/src/cairo-path-fill.c b/src/cairo-path-fill.c
index 51e067f..d0f0951 100644
--- a/src/cairo-path-fill.c
+++ b/src/cairo-path-fill.c
@@ -126,7 +126,6 @@ _cairo_filler_curve_to (void *closure,
cairo_point_t *c,
cairo_point_t *d)
{
- int i;
cairo_status_t status = CAIRO_STATUS_SUCCESS;
cairo_filler_t *filler = closure;
cairo_polygon_t *polygon = &filler->polygon;
@@ -137,18 +136,11 @@ _cairo_filler_curve_to (void *closure,
if (status == CAIRO_INT_STATUS_DEGENERATE)
return CAIRO_STATUS_SUCCESS;
- _cairo_spline_decompose (&spline, filler->tolerance);
- if (status)
- goto CLEANUP_SPLINE;
-
- for (i = 1; i < spline.num_points; i++) {
- status = _cairo_polygon_line_to (polygon, &spline.points[i]);
- if (status)
- break;
- }
-
- CLEANUP_SPLINE:
- _cairo_spline_fini (&spline);
+ /* avoid un-necessary memory copies */
+ status = _cairo_spline_decompose_direct
+ (&spline, filler->tolerance,
+ (cairo_spline_point_func_t*) &_cairo_polygon_line_to,
+ polygon, 0);
filler->current_point = *d;
@@ -205,3 +197,105 @@ BAIL:
return status;
}
+
+
+typedef struct
+{
+ cairo_fixed_t xmin;
+ cairo_fixed_t ymin;
+ cairo_fixed_t xmax;
+ cairo_fixed_t ymax;
+
+ cairo_point_t current_point;
+ double tolerance;
+
+} cairo_fillbox_t;
+
+static cairo_status_t
+_cairo_fillbox_move_to (void *closure, cairo_point_t *point)
+{
+ cairo_fillbox_t *box = closure;
+ cairo_fixed_t x = point->x;
+ cairo_fixed_t y = point->y;
+
+ if ( x < box->xmin )
+ box->xmin = x;
+
+ if ( x > box->xmax )
+ box->xmax = x;
+
+ if ( y < box->ymin )
+ box->ymin = y;
+
+ if ( y > box->ymax )
+ box->ymax = y;
+
+ box->current_point = point[0];
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
+
+static cairo_status_t
+_cairo_fillbox_curve_to (void *closure,
+ cairo_point_t *b,
+ cairo_point_t *c,
+ cairo_point_t *d)
+{
+ cairo_fillbox_t *box = closure;
+ cairo_status_t status = CAIRO_STATUS_SUCCESS;
+ cairo_spline_t spline;
+
+ status = _cairo_spline_init (&spline, &box->current_point, b, c, d);
+
+ if (status == CAIRO_INT_STATUS_DEGENERATE)
+ return CAIRO_STATUS_SUCCESS;
+
+ status = _cairo_spline_decompose_direct (&spline, box->tolerance,
+ (cairo_spline_point_func_t*)&_cairo_fillbox_move_to,
+ box, 0);
+ _cairo_spline_fini (&spline);
+
+ box->current_point = *d;
+
+ return status;
+}
+
+static cairo_status_t
+_cairo_fillbox_close_path (void *closure)
+{
+ return CAIRO_STATUS_SUCCESS;
+}
+
+cairo_status_t
+_cairo_path_fixed_fill_extents (cairo_path_fixed_t *path,
+ cairo_fill_rule_t fill_rule,
+ double tolerance,
+ cairo_box_t *extents)
+{
+ cairo_status_t status = CAIRO_STATUS_SUCCESS;
+ cairo_fillbox_t fillbox;
+
+ fillbox.xmin = fillbox.ymin = +INT_MAX;
+ fillbox.xmax = fillbox.ymax = -INT_MAX;
+ fillbox.tolerance = tolerance;
+
+ status = _cairo_path_fixed_interpret (path,
+ CAIRO_DIRECTION_FORWARD,
+ _cairo_fillbox_move_to,
+ _cairo_fillbox_move_to,
+ _cairo_fillbox_curve_to,
+ _cairo_fillbox_close_path,
+ &fillbox);
+ if (status)
+ goto BAIL;
+
+ extents->p1.x = fillbox.xmin;
+ extents->p1.y = fillbox.ymin;
+ extents->p2.x = fillbox.xmax;
+ extents->p2.y = fillbox.ymax;
+
+BAIL:
+
+ return status;
+}
diff --git a/src/cairoint.h b/src/cairoint.h
index 76d52fc..2f6b593 100644
--- a/src/cairoint.h
+++ b/src/cairoint.h
@@ -1589,6 +1589,12 @@ _cairo_path_fixed_fill_to_traps (cairo_p
double tolerance,
cairo_traps_t *traps);
+cairo_private cairo_status_t
+_cairo_path_fixed_fill_extents (cairo_path_fixed_t *path,
+ cairo_fill_rule_t fill_rule,
+ double tolerance,
+ cairo_box_t *extents);
+
/* cairo_path_stroke.c */
cairo_private cairo_status_t
_cairo_path_fixed_stroke_to_traps (cairo_path_fixed_t *path,
--
1.1.3
-------------- next part --------------
Subject: [PATCH] - modified the path stroker to use _cairo_spline_decompose_direct in order
to avoid un-necessary mallocs and memory copies
- introducing _cairo_path_fixed_stroke_extents in order to compute the
bounds of a given stroke without tessellation (big speedup)
---
src/cairo-gstate.c | 14 +-
src/cairo-path-stroke.c | 379 +++++++++++++++++++++++++++++++++++++++--------
src/cairo-pen.c | 5 -
src/cairoint.h | 14 ++
4 files changed, 334 insertions(+), 78 deletions(-)
29e375119b9467928c20958a74c2ce5b5e96e776
diff --git a/src/cairo-gstate.c b/src/cairo-gstate.c
index 543286b..917010d 100644
--- a/src/cairo-gstate.c
+++ b/src/cairo-gstate.c
@@ -1053,17 +1053,15 @@ _cairo_gstate_stroke_extents (cairo_gsta
_cairo_traps_init (&traps);
- status = _cairo_path_fixed_stroke_to_traps (path,
- &gstate->stroke_style,
- &gstate->ctm,
- &gstate->ctm_inverse,
- gstate->tolerance,
- &traps);
+ status = _cairo_path_fixed_stroke_extents (path,
+ &gstate->stroke_style,
+ &gstate->ctm,
+ &gstate->ctm_inverse,
+ gstate->tolerance,
+ &extents);
if (status)
goto BAIL;
- _cairo_traps_extents (&traps, &extents);
-
*x1 = _cairo_fixed_to_double (extents.p1.x);
*y1 = _cairo_fixed_to_double (extents.p1.y);
*x2 = _cairo_fixed_to_double (extents.p2.x);
diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c
index 792fbfa..c3914b8 100644
--- a/src/cairo-path-stroke.c
+++ b/src/cairo-path-stroke.c
@@ -36,6 +36,16 @@
#include "cairoint.h"
+typedef cairo_status_t
+(cairo_stroker_tri_func_t)(void* closure,
+ cairo_point_t *tri);
+typedef cairo_status_t
+(cairo_stroker_quad_func_t)(void* closure,
+ cairo_point_t *points);
+typedef cairo_status_t
+(cairo_stroker_polygon_func_t)(void* closure,
+ cairo_polygon_t *polygon);
+
typedef struct cairo_stroker {
cairo_stroke_style_t *style;
@@ -62,6 +72,11 @@ typedef struct cairo_stroker {
unsigned int dash_index;
int dash_on;
double dash_remain;
+ void *func_closure;
+ cairo_stroker_tri_func_t *func_tri;
+ cairo_stroker_quad_func_t *func_quad;
+ cairo_stroker_polygon_func_t *func_polygon;
+
} cairo_stroker_t;
/* private functions */
@@ -244,8 +259,11 @@ _cairo_stroker_join (cairo_stroker_t *st
while (i != stop) {
tri[2] = in->point;
_translate_point (&tri[2], &pen->vertices[i].point);
- _cairo_traps_tessellate_triangle (stroker->traps, tri);
- tri[1] = tri[2];
+ status = (*stroker->func_tri)(stroker->func_closure,tri);
+ if (status)
+ return status;
+
+ tri[1] = tri[2];
i += step;
if (i < 0)
i = pen->num_vertices - 1;
@@ -255,7 +273,7 @@ _cairo_stroker_join (cairo_stroker_t *st
tri[2] = *outpt;
- return _cairo_traps_tessellate_triangle (stroker->traps, tri);
+ return (*stroker->func_tri)(stroker->func_closure, tri);
}
case CAIRO_LINE_JOIN_MITER:
default: {
@@ -296,7 +314,6 @@ _cairo_stroker_join (cairo_stroker_t *st
double x1, y1, x2, y2;
double mx, my;
double dx1, dx2, dy1, dy2;
- cairo_polygon_t polygon;
cairo_point_t outer;
/*
@@ -339,17 +356,16 @@ _cairo_stroker_join (cairo_stroker_t *st
*/
outer.x = _cairo_fixed_from_double (mx);
outer.y = _cairo_fixed_from_double (my);
- _cairo_polygon_init (&polygon);
- _cairo_polygon_move_to (&polygon, &in->point);
- _cairo_polygon_line_to (&polygon, inpt);
- _cairo_polygon_line_to (&polygon, &outer);
- _cairo_polygon_line_to (&polygon, outpt);
- _cairo_polygon_close (&polygon);
- status = _cairo_traps_tessellate_polygon (stroker->traps,
- &polygon,
- CAIRO_FILL_RULE_WINDING);
- _cairo_polygon_fini (&polygon);
+ {
+ cairo_point_t p[4];
+
+ p[0] = in->point;
+ p[1] = inpt[0];
+ p[2] = outer;
+ p[3] = outpt[0];
+ status = (*stroker->func_quad) (stroker->func_closure, p);
+ }
return status;
}
/* fall through ... */
@@ -360,7 +376,7 @@ _cairo_stroker_join (cairo_stroker_t *st
tri[1] = *inpt;
tri[2] = *outpt;
- return _cairo_traps_tessellate_triangle (stroker->traps, tri);
+ return (*stroker->func_tri) (stroker->func_closure, tri);
}
}
}
@@ -392,18 +408,20 @@ _cairo_stroker_add_cap (cairo_stroker_t
for (i=start; i != stop; i = (i+1) % pen->num_vertices) {
tri[2] = f->point;
_translate_point (&tri[2], &pen->vertices[i].point);
- _cairo_traps_tessellate_triangle (stroker->traps, tri);
- tri[1] = tri[2];
+ status = (*stroker->func_tri) (stroker->func_closure, tri);
+ if (status)
+ return status;
+
+ tri[1] = tri[2];
}
tri[2] = f->ccw;
- return _cairo_traps_tessellate_triangle (stroker->traps, tri);
+ return (*stroker->func_tri) (stroker->func_closure, tri);
}
case CAIRO_LINE_CAP_SQUARE: {
double dx, dy;
cairo_slope_t fvector;
cairo_point_t occw, ocw;
- cairo_polygon_t polygon;
dx = f->usr_vector.x;
dy = f->usr_vector.y;
@@ -417,16 +435,16 @@ _cairo_stroker_add_cap (cairo_stroker_t
ocw.x = f->cw.x + fvector.dx;
ocw.y = f->cw.y + fvector.dy;
- _cairo_polygon_init (&polygon);
- _cairo_polygon_move_to (&polygon, &f->cw);
- _cairo_polygon_line_to (&polygon, &ocw);
- _cairo_polygon_line_to (&polygon, &occw);
- _cairo_polygon_line_to (&polygon, &f->ccw);
- _cairo_polygon_close (&polygon);
+ {
+ cairo_point_t p[4];
- status = _cairo_traps_tessellate_polygon (stroker->traps, &polygon, CAIRO_FILL_RULE_WINDING);
- _cairo_polygon_fini (&polygon);
+ p[0] = f->cw;
+ p[1] = ocw;
+ p[2] = occw;
+ p[3] = f->ccw;
+ status = (*stroker->func_quad) (stroker->func_closure, p);
+ }
return status;
}
case CAIRO_LINE_CAP_BUTT:
@@ -574,7 +592,6 @@ _cairo_stroker_add_sub_edge (cairo_strok
cairo_stroke_face_t *end)
{
cairo_status_t status;
- cairo_polygon_t polygon;
_compute_face (p1, slope, stroker, start);
@@ -586,28 +603,16 @@ _cairo_stroker_add_sub_edge (cairo_strok
if (p1->x == p2->x && p1->y == p2->y)
return CAIRO_STATUS_SUCCESS;
- /* XXX: I should really check the return value of the
- move_to/line_to functions here to catch out of memory
- conditions. But since that would be ugly, I'd prefer to add a
- status flag to the polygon object that I could check only once
- at then end of this sequence, (like we do with cairo_t
- already). */
- _cairo_polygon_init (&polygon);
- _cairo_polygon_move_to (&polygon, &start->cw);
- _cairo_polygon_line_to (&polygon, &start->ccw);
- _cairo_polygon_line_to (&polygon, &end->ccw);
- _cairo_polygon_line_to (&polygon, &end->cw);
- _cairo_polygon_close (&polygon);
+ {
+ cairo_point_t p[4];
- /* XXX: We can't use tessellate_rectangle as the matrix may have
- skewed this into a non-rectangular shape. Perhaps it would be
- worth checking the matrix for skew so that the common case
- could use the faster tessellate_rectangle rather than
- tessellate_polygon? */
- status = _cairo_traps_tessellate_polygon (stroker->traps,
- &polygon, CAIRO_FILL_RULE_WINDING);
+ p[0] = start->cw;
+ p[1] = start->ccw;
+ p[2] = end->ccw;
+ p[3] = end->cw;
- _cairo_polygon_fini (&polygon);
+ status = (*stroker->func_quad) (stroker->func_closure, p);
+ }
return status;
}
@@ -802,6 +807,47 @@ _cairo_stroker_line_to_dashed (void *clo
return status;
}
+/* the following is a slightly modified copy of _cairo_pen_stroke_spline */
+
+/* Compute outline of a given spline using the pen.
+ The trapezoids needed to fill that outline will be added to traps
+*/
+static cairo_status_t
+_cairo_stroker_stroke_spline (cairo_stroker_t *stroker,
+ cairo_pen_t *pen,
+ cairo_spline_t *spline,
+ double tolerance)
+{
+ cairo_status_t status;
+ cairo_polygon_t polygon;
+
+ /* If the line width is so small that the pen is reduced to a
+ single point, then we have nothing to do. */
+ if (pen->num_vertices <= 1)
+ return CAIRO_STATUS_SUCCESS;
+
+ _cairo_polygon_init (&polygon);
+
+ status = _cairo_spline_decompose (spline, tolerance);
+ if (status)
+ goto BAIL;
+
+ status = _cairo_pen_stroke_spline_half (pen, spline, CAIRO_DIRECTION_FORWARD, &polygon);
+ if (status)
+ goto BAIL;
+
+ status = _cairo_pen_stroke_spline_half (pen, spline, CAIRO_DIRECTION_REVERSE, &polygon);
+ if (status)
+ goto BAIL;
+
+ _cairo_polygon_close (&polygon);
+ status = (*stroker->func_polygon) (stroker->func_closure, &polygon);
+
+BAIL:
+ _cairo_polygon_fini (&polygon);
+ return status;
+}
+
static cairo_status_t
_cairo_stroker_curve_to (void *closure,
cairo_point_t *b,
@@ -857,7 +903,7 @@ _cairo_stroker_curve_to (void *closure,
if (status)
goto CLEANUP_PEN;
- status = _cairo_pen_stroke_spline (&pen, &spline, stroker->tolerance, stroker->traps);
+ status = _cairo_stroker_stroke_spline (stroker, &pen, &spline, stroker->tolerance);
if (status)
goto CLEANUP_PEN;
@@ -900,7 +946,6 @@ _cairo_stroker_curve_to_dashed (void *cl
cairo_spline_t spline;
cairo_point_t *a = &stroker->current_point;
cairo_line_join_t line_join_save;
- int i;
status = _cairo_spline_init (&spline, a, b, c, d);
if (status == CAIRO_INT_STATUS_DEGENERATE)
@@ -909,31 +954,30 @@ _cairo_stroker_curve_to_dashed (void *cl
/* If the line width is so small that the pen is reduced to a
single point, then we have nothing to do. */
if (stroker->pen.num_vertices <= 1)
- goto CLEANUP_SPLINE;
+ goto BAIL;
/* Temporarily modify the stroker to use round joins to guarantee
* smooth stroked curves. */
line_join_save = stroker->style->line_join;
stroker->style->line_join = CAIRO_LINE_JOIN_ROUND;
- status = _cairo_spline_decompose (&spline, stroker->tolerance);
- if (status)
- goto CLEANUP_GSTATE;
-
- for (i = 1; i < spline.num_points; i++) {
- if (stroker->dashed)
- status = _cairo_stroker_line_to_dashed (stroker, &spline.points[i]);
- else
- status = _cairo_stroker_line_to (stroker, &spline.points[i]);
- if (status)
- break;
+ if (stroker->dashed)
+ {
+ status = _cairo_spline_decompose_direct
+ (&spline, stroker->tolerance,
+ (cairo_spline_point_func_t*) &_cairo_stroker_line_to_dashed,
+ stroker, 0);
+ }
+ else
+ {
+ status = _cairo_spline_decompose_direct
+ (&spline, stroker->tolerance,
+ (cairo_spline_point_func_t*) &_cairo_stroker_line_to,
+ stroker, 0);
}
-
- CLEANUP_GSTATE:
stroker->style->line_join = line_join_save;
- CLEANUP_SPLINE:
- _cairo_spline_fini (&spline);
+ BAIL:
return status;
}
@@ -968,6 +1012,42 @@ _cairo_stroker_close_path (void *closure
return CAIRO_STATUS_SUCCESS;
}
+
+static cairo_status_t
+_cairo_stroker_tessellate_quad (void* closure,
+ cairo_point_t *points)
+{
+ cairo_polygon_t polygon;
+ cairo_edge_t polygon_edges[4];
+ cairo_traps_t *traps = closure;
+ cairo_status_t status;
+
+ _cairo_polygon_init_static (&polygon, 4, polygon_edges);
+
+ /* the following can't fail, because we allocated enough
+ * space for the edges array
+ */
+ _cairo_polygon_move_to (&polygon, &points[0]);
+ _cairo_polygon_line_to (&polygon, &points[1]);
+ _cairo_polygon_line_to (&polygon, &points[2]);
+ _cairo_polygon_line_to (&polygon, &points[3]);
+ _cairo_polygon_close (&polygon);
+
+ status = _cairo_traps_tessellate_polygon (traps,
+ &polygon,
+ CAIRO_FILL_RULE_WINDING);
+ return status;
+}
+
+static cairo_status_t
+_cairo_stroker_tessellate_polygon (void* closure,
+ cairo_polygon_t *polygon)
+{
+ cairo_traps_t *traps = closure;
+
+ return _cairo_traps_tessellate_polygon (traps, polygon, CAIRO_FILL_RULE_WINDING);
+}
+
cairo_status_t
_cairo_path_fixed_stroke_to_traps (cairo_path_fixed_t *path,
cairo_stroke_style_t *stroke_style,
@@ -983,6 +1063,11 @@ _cairo_path_fixed_stroke_to_traps (cairo
ctm, ctm_inverse, tolerance,
traps);
+ stroker.func_closure = traps;
+ stroker.func_tri = (cairo_stroker_tri_func_t*) &_cairo_traps_tessellate_triangle;
+ stroker.func_quad = &_cairo_stroker_tessellate_quad;
+ stroker.func_polygon = &_cairo_stroker_tessellate_polygon;
+
if (stroker.style->dash)
status = _cairo_path_fixed_interpret (path,
CAIRO_DIRECTION_FORWARD,
@@ -1009,3 +1094,165 @@ BAIL:
return status;
}
+
+
+typedef struct
+{
+ cairo_fixed_t xmin;
+ cairo_fixed_t ymin;
+ cairo_fixed_t xmax;
+ cairo_fixed_t ymax;
+
+} cairo_stroker_box_t;
+
+static cairo_status_t
+_cairo_stroker_extents_triangle (void *closure,
+ cairo_point_t *tri)
+{
+ cairo_stroker_box_t *box = closure;
+ int nn;
+
+ for ( nn = 0; nn < 3; nn++ ) {
+ cairo_fixed_t x, y;
+
+ x = tri[nn].x;
+ y = tri[nn].y;
+
+ if ( x < box->xmin )
+ box->xmin = x;
+ if ( x > box->xmax )
+ box->xmax = x;
+
+ if ( y < box->ymin )
+ box->ymin = y;
+ else if ( y > box->ymax )
+ box->ymax = y;
+ }
+ return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_status_t
+_cairo_stroker_extents_quad (void *closure,
+ cairo_point_t *quad)
+{
+ cairo_stroker_box_t *box = closure;
+ int nn;
+
+ for ( nn = 0; nn < 4; nn++ ) {
+ cairo_fixed_t x, y;
+
+ x = quad[nn].x;
+ y = quad[nn].y;
+
+ if ( x < box->xmin )
+ box->xmin = x;
+ if ( x > box->xmax )
+ box->xmax = x;
+
+ if ( y < box->ymin )
+ box->ymin = y;
+ else if ( y > box->ymax )
+ box->ymax = y;
+ }
+ return CAIRO_STATUS_SUCCESS;
+}
+
+
+static cairo_status_t
+_cairo_stroker_extents_polygon (void *closure,
+ cairo_polygon_t *polygon)
+{
+ cairo_stroker_box_t *box = closure;
+ int nn;
+
+ for (nn=0; nn < polygon->num_edges; nn++)
+ {
+ cairo_line_t *line = &polygon->edges[nn].edge;
+ cairo_fixed_t x, y;
+
+ x = line->p1.x;
+ y = line->p1.y;
+
+ if ( x < box->xmin )
+ box->xmin = x;
+ if ( x > box->xmax )
+ box->xmax = x;
+
+ if ( y < box->ymin )
+ box->ymin = y;
+ else if ( y > box->ymax )
+ box->ymax = y;
+
+ x = line->p2.x;
+ y = line->p2.y;
+
+ if ( x < box->xmin )
+ box->xmin = x;
+ if ( x > box->xmax )
+ box->xmax = x;
+
+ if ( y < box->ymin )
+ box->ymin = y;
+ else if ( y > box->ymax )
+ box->ymax = y;
+ }
+ return CAIRO_STATUS_SUCCESS;
+}
+
+cairo_status_t
+_cairo_path_fixed_stroke_extents (cairo_path_fixed_t *path,
+ cairo_stroke_style_t *stroke_style,
+ cairo_matrix_t *ctm,
+ cairo_matrix_t *ctm_inverse,
+ double tolerance,
+ cairo_box_t *extents)
+{
+ cairo_status_t status = CAIRO_STATUS_SUCCESS;
+ cairo_stroker_t stroker;
+ cairo_stroker_box_t box;
+
+ _cairo_stroker_init (&stroker, stroke_style,
+ ctm, ctm_inverse, tolerance,
+ NULL);
+
+ box.xmin = box.ymin = +INT_MAX;
+ box.xmax = box.ymax = -INT_MAX;
+
+ stroker.func_closure = &box;
+ stroker.func_tri = &_cairo_stroker_extents_triangle;
+ stroker.func_quad = &_cairo_stroker_extents_quad;
+ stroker.func_polygon = &_cairo_stroker_extents_polygon;
+
+ if (stroker.style->dash)
+ status = _cairo_path_fixed_interpret (path,
+ CAIRO_DIRECTION_FORWARD,
+ _cairo_stroker_move_to_dashed,
+ _cairo_stroker_line_to_dashed,
+ _cairo_stroker_curve_to_dashed,
+ _cairo_stroker_close_path,
+ &stroker);
+ else
+ status = _cairo_path_fixed_interpret (path,
+ CAIRO_DIRECTION_FORWARD,
+ _cairo_stroker_move_to,
+ _cairo_stroker_line_to,
+ _cairo_stroker_curve_to,
+ _cairo_stroker_close_path,
+ &stroker);
+ if (status)
+ goto BAIL;
+
+ status = _cairo_stroker_add_caps (&stroker);
+ if (status)
+ goto BAIL;
+
+ extents->p1.x = box.xmin;
+ extents->p1.y = box.ymin;
+ extents->p2.x = box.xmax;
+ extents->p2.y = box.ymax;
+
+BAIL:
+ _cairo_stroker_fini (&stroker);
+
+ return status;
+}
diff --git a/src/cairo-pen.c b/src/cairo-pen.c
index 87de9a4..ad6cbc4 100644
--- a/src/cairo-pen.c
+++ b/src/cairo-pen.c
@@ -42,9 +42,6 @@ _cairo_pen_vertices_needed (double toler
static void
_cairo_pen_compute_slopes (cairo_pen_t *pen);
-static cairo_status_t
-_cairo_pen_stroke_spline_half (cairo_pen_t *pen, cairo_spline_t *spline, cairo_direction_t dir, cairo_polygon_t *polygon);
-
cairo_status_t
_cairo_pen_init_empty (cairo_pen_t *pen)
{
@@ -348,7 +345,7 @@ _cairo_pen_find_active_ccw_vertex_index
return CAIRO_STATUS_SUCCESS;
}
-static cairo_status_t
+cairo_status_t
_cairo_pen_stroke_spline_half (cairo_pen_t *pen,
cairo_spline_t *spline,
cairo_direction_t dir,
diff --git a/src/cairoint.h b/src/cairoint.h
index 2f6b593..27d775f 100644
--- a/src/cairoint.h
+++ b/src/cairoint.h
@@ -1604,6 +1604,14 @@ _cairo_path_fixed_stroke_to_traps (cairo
double tolerance,
cairo_traps_t *traps);
+cairo_private cairo_status_t
+_cairo_path_fixed_stroke_extents (cairo_path_fixed_t *path,
+ cairo_stroke_style_t *stroke_style,
+ cairo_matrix_t *ctm,
+ cairo_matrix_t *ctm_inverse,
+ double tolerance,
+ cairo_box_t *extents);
+
/* cairo-scaled-font.c */
cairo_private cairo_status_t
@@ -2086,6 +2094,12 @@ _cairo_pen_stroke_spline (cairo_pen_t *p
double tolerance,
cairo_traps_t *traps);
+cairo_private cairo_status_t
+_cairo_pen_stroke_spline_half (cairo_pen_t *pen,
+ cairo_spline_t *spline,
+ cairo_direction_t dir,
+ cairo_polygon_t *polygon);
+
/* cairo_polygon.c */
cairo_private void
_cairo_polygon_init (cairo_polygon_t *polygon);
--
1.1.3
-------------- next part --------------
Subject: [PATCH] - speeding up tessellator through inline assembly (doesn't fix the
algorihtm)
- other uses of _cairo_spline_decompose_direct
---
src/cairo-path-data.c | 20 +++------
src/cairo-traps.c | 110 +++++++++++++++++++++++++++++++++++++++++++------
2 files changed, 104 insertions(+), 26 deletions(-)
f7784315ec16ee586e1f3f760e325b360106570e
diff --git a/src/cairo-path-data.c b/src/cairo-path-data.c
index cd15192..b45776d 100644
--- a/src/cairo-path-data.c
+++ b/src/cairo-path-data.c
@@ -94,7 +94,6 @@ _cpdc_curve_to_flatten (void *clos
cpdc_t *cpdc = closure;
cairo_status_t status;
cairo_spline_t spline;
- int i;
cairo_point_t *p0 = &cpdc->current_point;
@@ -102,19 +101,17 @@ _cpdc_curve_to_flatten (void *clos
if (status == CAIRO_INT_STATUS_DEGENERATE)
return CAIRO_STATUS_SUCCESS;
- status = _cairo_spline_decompose (&spline, cpdc->tolerance);
+ status = _cairo_spline_decompose_direct (&spline, cpdc->tolerance,
+ (cairo_spline_point_func_t*) &_cpdc_line_to,
+ cpdc, 0);
if (status)
- goto out;
-
- for (i=1; i < spline.num_points; i++)
- _cpdc_line_to (cpdc, &spline.points[i]);
+ goto out;
cpdc->current_point = *p3;
status = CAIRO_STATUS_SUCCESS;
out:
- _cairo_spline_fini (&spline);
return status;
}
@@ -266,7 +263,6 @@ _cpdp_curve_to_flatten (void *clos
cpdp_t *cpdp = closure;
cairo_status_t status;
cairo_spline_t spline;
- int i;
cairo_point_t *p0 = &cpdp->current_point;
@@ -274,19 +270,17 @@ _cpdp_curve_to_flatten (void *clos
if (status == CAIRO_INT_STATUS_DEGENERATE)
return CAIRO_STATUS_SUCCESS;
- status = _cairo_spline_decompose (&spline, cpdp->gstate->tolerance);
+ status = _cairo_spline_decompose_direct (&spline, cpdp->gstate->tolerance,
+ (cairo_spline_point_func_t*) &_cpdp_line_to,
+ cpdp, 0);
if (status)
goto out;
- for (i=1; i < spline.num_points; i++)
- _cpdp_line_to (cpdp, &spline.points[i]);
-
cpdp->current_point = *p3;
status = CAIRO_STATUS_SUCCESS;
out:
- _cairo_spline_fini (&spline);
return status;
}
diff --git a/src/cairo-traps.c b/src/cairo-traps.c
index 107276c..a88d8f7 100644
--- a/src/cairo-traps.c
+++ b/src/cairo-traps.c
@@ -60,12 +60,106 @@ _compare_cairo_edge_by_top (const void *
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);
+#if defined(__GNUC__) && defined(i386)
+/* the following function computes dx*ey/dy with
+ * 64-bits intermediate accuracy. the inline assembly
+ * provided is much faster than using GCC's 64-bit integer
+ * types, which always tries to divide two 64-bit numbers,
+ * which is slower than the 64-by-32 division we perform
+ * here.
+ *
+ * assumes that dy > 0
+ */
+static cairo_fixed_16_16_t
+_compute_x_helper (cairo_fixed_16_16_t dx,
+ cairo_fixed_16_16_t ey,
+ cairo_fixed_16_16_t dy)
+{
+#if 0
+ return (cairo_fixed_32_32_t)dx*ey / dy;
+#else
+ cairo_fixed_16_16_t ex;
+
+ __asm__ (
+ /* compute ey*dx in edx:eax */
+ "imul %%edx\n"
+
+ /* check for overflows and underflows */
+ /* separate the case positive and negative cases */
+ "test %%edx, %%edx\n"
+ "js Negative\n"
+ "cmpl %%ecx, %%edx\n"
+ "jae Overflow\n"
+ "divl %%ecx\n" /* note: an _unsigned_ division */
+ "testl %%eax, %%eax\n" /* its result must fit in 31 bits */
+ "jns Next\n"
+
+ "Overflow:\n"
+ "movl $0x7fffffff, %%eax\n"
+ "jmp Next\n"
+
+ "Negative:\n"
+ "negl %%eax\n" /* negate edx:eax */
+ "adcl $0, %%edx\n"
+ "negl %%edx\n"
+
+ "cmpl %%ecx, %%edx\n"
+ "jae Underflow\n"
+ "divl %%ecx\n" /* note: an _unsigned_ division */
+ "testl %%eax, %%eax\n"
+ "js Underflow\n"
+ "negl %%eax\n"
+ "jmp Next\n"
+
+ "Underflow:\n"
+ "movl $0x80000000, %%eax\n"
+
+ "Next:\n"
+
+ : "=a"(ex)
+ : "d"(dx), "a"(ey), "c"(dy)
+ );
+ return ex;
+#endif
+}
+
+static __inline__ cairo_fixed_16_16_t
+_compute_x (cairo_line_t *line, cairo_fixed_t y)
+{
+ cairo_fixed_16_16_t dx = line->p2.x - line->p1.x;
+ cairo_fixed_16_16_t ey = y - line->p1.y;
+ cairo_fixed_16_16_t dy = line->p2.y - line->p1.y;
+ cairo_fixed_16_16_t ex;
+
+ if (ey < dy && ey > -dy) {
+ __asm__ __volatile__ (
+ "imul %%edx\n"
+ "idiv %%ecx\n"
+ : "=a" (ex)
+ : "a"(dx), "d"(ey), "c"(dy)
+ );
+ return line->p1.x + ex;
+ }
+ else {
+ return line->p1.x + _compute_x_helper(dx,ey,dy);
+ }
+}
+#else /* other platforms */
+static __inline__ cairo_fixed_16_16_t
+_compute_x (cairo_line_t *line, cairo_fixed_t y)
+{
+ cairo_fixed_16_16_t dx = line->p2.x - line->p1.x;
+ cairo_fixed_32_32_t ex = (cairo_fixed_48_16_t) (y - line->p1.y) * (cairo_fixed_48_16_t) dx;
+ cairo_fixed_16_16_t dy = line->p2.y - line->p1.y;
+
+ return line->p1.x + (ex / dy);
+}
+#endif
+
+
void
_cairo_traps_init (cairo_traps_t *traps)
{
@@ -596,16 +690,6 @@ _line_segs_intersect_ceil (cairo_line_t
}
#endif /* CAIRO_TRAPS_USE_NEW_INTERSECTION_CODE */
-static cairo_fixed_16_16_t
-_compute_x (cairo_line_t *line, cairo_fixed_t y)
-{
- cairo_fixed_16_16_t dx = line->p2.x - line->p1.x;
- cairo_fixed_32_32_t ex = (cairo_fixed_48_16_t) (y - line->p1.y) * (cairo_fixed_48_16_t) dx;
- cairo_fixed_16_16_t dy = line->p2.y - line->p1.y;
-
- return line->p1.x + (ex / dy);
-}
-
#if ! CAIRO_TRAPS_USE_NEW_INTERSECTION_CODE
static double
_compute_inverse_slope (cairo_line_t *l)
--
1.1.3
-------------- next part --------------
Subject: [PATCH] optimize the gradient computations - WARNING: this breaks the test suite !!
---
pixman/src/fbcompose.c | 458 ++++++++++++++++++++++++++++++++++--------------
1 files changed, 320 insertions(+), 138 deletions(-)
1307a4b791977ede80717fc2e70e6abe8993927f
diff --git a/pixman/src/fbcompose.c b/pixman/src/fbcompose.c
index 4958241..ec9a515 100644
--- a/pixman/src/fbcompose.c
+++ b/pixman/src/fbcompose.c
@@ -2731,78 +2731,242 @@ static void fbFetch(PicturePtr pict, int
#define DIV(a,b) ((((a) < 0) == ((b) < 0)) ? (a) / (b) :\
((a) - (b) + 1 - (((b) < 0) << 1)) / (b))
-static CARD32
-xRenderColorMultToCard32 (pixman_color_t *c)
+typedef struct
+{
+ CARD32 left_ag;
+ CARD32 left_rb;
+ CARD32 right_ag;
+ CARD32 right_rb;
+ int32_t left_x;
+ int32_t right_x;
+ int32_t width_x;
+ int32_t stepper;
+
+ pixman_gradient_stop_t *stops;
+ int num_stops;
+ unsigned int spread;
+
+} GradientWalker;
+
+static void
+_gradient_walker_init (GradientWalker *walker,
+ SourcePictPtr pGradient,
+ unsigned int spread)
{
- return
- ((((uint32_t) c->red * c->alpha) >> 24) << 16) |
- ((((uint32_t) c->green * c->alpha) >> 24) << 8) |
- ((((uint32_t) c->blue * c->alpha) >> 24) << 0) |
- ((((uint32_t) c->alpha ) >> 8) << 24);
+ walker->num_stops = pGradient->gradient.nstops;
+ walker->stops = pGradient->gradient.stops;
+ walker->left_x = 0;
+ walker->right_x = 0x10000;
+ walker->width_x = 0; /* will force a reset */
+ walker->stepper = 0;
+ walker->left_ag = 0;
+ walker->left_rb = 0;
+ walker->right_ag = 0;
+ walker->right_rb = 0;
+ walker->spread = spread;
}
-static CARD32 gradientPixel(const SourcePictPtr pGradient, xFixed_48_16 pos, unsigned int spread)
+static void
+_gradient_walker_reset (GradientWalker *walker,
+ xFixed_32_32 pos)
{
- int ipos = (pos * pGradient->gradient.stopRange - 1) >> 16;
+ int32_t x, left_x, right_x;
+ pixman_color_t *left_c, *right_c;
+ int n, count = walker->num_stops;
+ pixman_gradient_stop_t *stops = walker->stops;
+
+ static const pixman_color_t transparent_black = { 0, 0, 0, 0 };
+
+ switch (walker->spread)
+ {
+ case RepeatNormal:
+ x = (int32_t)pos & 0xFFFF;
+ for (n = 0; n < count; n++)
+ if (x < stops[n].x)
+ break;
+ if (n == 0) {
+ left_x = stops[count-1].x - 0x10000;
+ left_c = &stops[count-1].color;
+ } else {
+ left_x = stops[n-1].x;
+ left_c = &stops[n-1].color;
+ }
+
+ if (n == count) {
+ right_x = stops[0].x + 0x10000;
+ right_c = &stops[0].color;
+ } else {
+ right_x = stops[n].x;
+ right_c = &stops[n].color;
+ }
+ left_x += (pos - x);
+ right_x += (pos - x);
+ break;
+
+ case RepeatPad:
+ for (n = 0; n < count; n++)
+ if (pos < stops[n].x)
+ break;
+
+ if (n == 0) {
+ left_x = INT_MIN;
+ left_c = &stops[0].color;
+ } else {
+ left_x = stops[n-1].x;
+ left_c = &stops[n-1].color;
+ }
+
+ if (n == count) {
+ right_x = INT_MAX;
+ right_c = &stops[n-1].color;
+ } else {
+ right_x = stops[n].x;
+ right_c = &stops[n].color;
+ }
+ break;
+
+ case RepeatReflect:
+ x = (int32_t)pos & 0xFFFF;
+ if ((int32_t)pos & 0x10000)
+ x = 0x10000 - x;
+ for (n = 0; n < count; n++)
+ if (x < stops[n].x)
+ break;
+
+ if (n == 0) {
+ left_x = -stops[0].x;
+ left_c = &stops[0].color;
+ } else {
+ left_x = stops[n-1].x;
+ left_c = &stops[n-1].color;
+ }
+
+ if (n == count) {
+ right_x = 0x20000 - stops[n-1].x;
+ right_c = &stops[n-1].color;
+ } else {
+ right_x = stops[n].x;
+ right_c = &stops[n].color;
+ }
+
+ if ((int32_t)pos & 0x10000) {
+ pixman_color_t *tmp_c;
+ int32_t tmp_x;
+
+ tmp_x = 0x20000 - right_x;
+ right_x = 0x20000 - left_x;
+ left_x = tmp_x;
+
+ tmp_c = right_c;
+ right_c = left_c;
+ left_c = tmp_c;
+ }
+ left_x += (pos - x);
+ right_x += (pos - x);
+ break;
+
+ default: /* RepeatNone */
+ for (n = 0; n < count; n++)
+ if (pos < stops[n].x)
+ break;
+
+ if (n == 0)
+ {
+ left_x = INT_MIN;
+ right_x = stops[0].x;
+ left_c = right_c = (pixman_color_t*) &transparent_black;
+ }
+ else if (n == count)
+ {
+ left_x = stops[n-1].x;
+ right_x = INT_MAX;
+ left_c = right_c = (pixman_color_t*) &transparent_black;
+ }
+ else
+ {
+ left_x = stops[n-1].x;
+ right_x = stops[n].x;
+ left_c = &stops[n-1].color;
+ right_c = &stops[n].color;
+ }
+ }
+
+ walker->left_x = left_x;
+ walker->right_x = right_x;
+ walker->width_x = right_x - left_x;
+ walker->left_ag = ((left_c->alpha >> 8) << 16) | (left_c->green >> 8);
+ walker->left_rb = ((left_c->red & 0xff00) << 8) | (left_c->blue >> 8);
+ walker->right_ag = ((right_c->alpha >> 8) << 16) | (right_c->green >> 8);
+ walker->right_rb = ((right_c->red & 0xff00) << 8) | (right_c->blue >> 8);
+
+ if ( walker->width_x == 0 ||
+ ( walker->left_ag == walker->right_ag &&
+ walker->left_rb == walker->right_rb ) )
+ {
+ walker->width_x = 1;
+ walker->stepper = 0;
+ }
+ else
+ {
+ walker->stepper = ((1 << 24) + walker->width_x/2)/walker->width_x;
+ }
+}
- /* calculate the actual offset. */
- if (ipos < 0 || ipos >= pGradient->gradient.stopRange)
- {
- if (pGradient->type == SourcePictTypeConical || spread == RepeatNormal)
- {
- ipos = ipos % pGradient->gradient.stopRange;
- ipos = ipos < 0 ? pGradient->gradient.stopRange + ipos : ipos;
+#define GRADIENT_WALKER_NEED_RESET(w,x) \
+ ( (x) < (w)->left_x || (x) - (w)->left_x >= (w)->width_x )
- }
- else if (spread == RepeatReflect)
- {
- const int limit = pGradient->gradient.stopRange * 2 - 1;
+/* the following assumes that GRADIENT_WALKER_NEED_RESET(w,x) is FALSE */
+static CARD32
+_gradient_walker_pixel (GradientWalker *walker,
+ xFixed_32_32 x)
+{
+ int dist, idist;
+ uint32_t t1, t2, a, color;
- ipos = ipos % limit;
- ipos = ipos < 0 ? limit + ipos : ipos;
- ipos = ipos >= pGradient->gradient.stopRange ? limit - ipos : ipos;
+ if (GRADIENT_WALKER_NEED_RESET (walker, x))
+ _gradient_walker_reset (walker, x);
- }
- else if (spread == RepeatPad)
- {
- if (ipos < 0)
- ipos = 0;
- else
- ipos = pGradient->gradient.stopRange - 1;
- }
- else /* RepeatNone */
- {
- return 0;
- }
- }
+ dist = ((int)(x - walker->left_x)*walker->stepper) >> 16;
+ idist = 256 - dist;
- if (pGradient->gradient.colorTableSize)
- {
- return pGradient->gradient.colorTable[ipos];
- }
- else
- {
- int i;
+ /* combined INTERPOLATE and premultiply */
+ t1 = walker->left_rb*idist + walker->right_rb*dist;
+ t1 = (t1 >> 8) & 0xff00ff;
- if (ipos <= pGradient->gradient.stops->x)
- return xRenderColorMultToCard32 (&pGradient->gradient.stops->color);
+ t2 = walker->left_ag*idist + walker->right_ag*dist;
+ t2 &= 0xff00ff00;
- for (i = 1; i < pGradient->gradient.nstops; i++)
- {
- if (pGradient->gradient.stops[i].x >= ipos)
- return PictureGradientColor (&pGradient->gradient.stops[i - 1],
- &pGradient->gradient.stops[i],
- ipos);
- }
+ color = t2 & 0xff000000;
+ a = t2 >> 24;
- return xRenderColorMultToCard32 (&pGradient->gradient.stops[--i].color);
- }
+#if 0
+ t1 = t1*a + 0x800080;
+ t1 = (t1 + ((t1 >> 8) & 0xff00ff)) >> 8;
+
+ t2 = (t2 >> 8)*a + 0x800080;
+ t2 = (t2 + ((t2 >> 8) & 0xff00ff));
+#else
+ /* this is faster and the difference is completely
+ * un-noticeable
+ */
+ a += (a >> 7);
+
+ t1 = t1*a >> 8;
+ t2 = t2*a >> 8;
+#endif
+
+ return (color | (t1 & 0xff00ff) | (t2 & 0xff00));
}
+
+
static void fbFetchSourcePict(PicturePtr pict, int x, int y, int width, CARD32 *buffer, CARD32 *mask, CARD32 maskBits)
{
- SourcePictPtr pGradient = pict->pSourcePict;
- CARD32 *end = buffer + width;
+ SourcePictPtr pGradient = pict->pSourcePict;
+ GradientWalker walker;
+ CARD32 *end = buffer + width;
+
+ _gradient_walker_init (&walker, pGradient, pict->repeat);
if (pGradient->type == SourcePictTypeSolidFill) {
register CARD32 color = pGradient->solidFill.color;
@@ -2853,20 +3017,29 @@ static void fbFetchSourcePict(PicturePtr
{
register CARD32 color;
- color = gradientPixel (pGradient, t, pict->repeat);
+ color = _gradient_walker_pixel( &walker, t );
while (buffer < end)
*buffer++ = color;
}
else
{
- while (buffer < end) {
- if (!mask || *mask++ & maskBits)
- {
- *buffer = gradientPixel (pGradient, t, pict->repeat);
- }
- ++buffer;
- t += inc;
- }
+ if (!mask) {
+ while (buffer < end)
+ {
+ *buffer = _gradient_walker_pixel (&walker, t);
+ buffer += 1;
+ t += inc;
+ }
+ } else {
+ while (buffer < end) {
+ if (*mask++ & maskBits)
+ {
+ *buffer = _gradient_walker_pixel (&walker, t);
+ }
+ buffer += 1;
+ t += inc;
+ }
+ }
}
}
else /* projective transformation */
@@ -2890,31 +3063,31 @@ static void fbFetchSourcePict(PicturePtr
t = ((a * x + b * y) >> 16) + off;
}
- color = gradientPixel (pGradient, t, pict->repeat);
+ color = _gradient_walker_pixel( &walker, t );
while (buffer < end)
*buffer++ = color;
}
else
{
- while (buffer < end)
- {
- if (!mask || *mask++ & maskBits)
- {
- if (v.vector[2] == 0) {
- t = 0;
- } else {
- xFixed_48_16 x, y;
- x = ((xFixed_48_16)v.vector[0] << 16) / v.vector[2];
- y = ((xFixed_48_16)v.vector[1] << 16) / v.vector[2];
- t = ((a*x + b*y) >> 16) + off;
- }
- *buffer = gradientPixel(pGradient, t, pict->repeat);
- }
- ++buffer;
- v.vector[0] += unit.vector[0];
- v.vector[1] += unit.vector[1];
- v.vector[2] += unit.vector[2];
- }
+ while (buffer < end)
+ {
+ if (!mask || *mask++ & maskBits)
+ {
+ if (v.vector[2] == 0) {
+ t = 0;
+ } else {
+ xFixed_48_16 x, y;
+ x = ((xFixed_48_16)v.vector[0] << 16) / v.vector[2];
+ y = ((xFixed_48_16)v.vector[1] << 16) / v.vector[2];
+ t = ((a*x + b*y) >> 16) + off;
+ }
+ *buffer = _gradient_walker_pixel (&walker, t);
+ }
+ ++buffer;
+ v.vector[0] += unit.vector[0];
+ v.vector[1] += unit.vector[1];
+ v.vector[2] += unit.vector[2];
+ }
}
}
} else {
@@ -2951,19 +3124,22 @@ static void fbFetchSourcePict(PicturePtr
ry -= pGradient->radial.fy;
while (buffer < end) {
- double b, c, det, s;
+ double b, c, det, s;
- if (!mask || *mask++ & maskBits)
- {
- b = 2*(rx*pGradient->radial.dx + ry*pGradient->radial.dy);
- c = -(rx*rx + ry*ry);
- det = (b * b) - (4 * pGradient->radial.a * c);
- s = (-b + sqrt(det))/(2. * pGradient->radial.a);
- *buffer = gradientPixel(pGradient,
- (xFixed_48_16)((s*pGradient->radial.m + pGradient->radial.b)*65536),
- pict->repeat);
- }
- ++buffer;
+ if (!mask || *mask++ & maskBits)
+ {
+ xFixed_48_16 t;
+
+ b = 2*(rx*pGradient->radial.dx + ry*pGradient->radial.dy);
+ c = -(rx*rx + ry*ry);
+ det = (b * b) - (4 * pGradient->radial.a * c);
+ s = (-b + sqrt(det))/(2. * pGradient->radial.a);
+
+ t = (xFixed_48_16)((s*pGradient->radial.m + pGradient->radial.b)*65536);
+
+ *buffer = _gradient_walker_pixel (&walker, t);
+ }
+ ++buffer;
rx += cx;
ry += cy;
}
@@ -2972,25 +3148,27 @@ static void fbFetchSourcePict(PicturePtr
double x, y;
double b, c, det, s;
- if (!mask || *mask++ & maskBits)
- {
- if (rz != 0) {
- x = rx/rz;
- y = ry/rz;
- } else {
- x = y = 0.;
- }
- x -= pGradient->radial.fx;
- y -= pGradient->radial.fy;
- b = 2*(x*pGradient->radial.dx + y*pGradient->radial.dy);
- c = -(x*x + y*y);
- det = (b * b) - (4 * pGradient->radial.a * c);
- s = (-b + sqrt(det))/(2. * pGradient->radial.a);
- *buffer = gradientPixel(pGradient,
- (xFixed_48_16)((s*pGradient->radial.m + pGradient->radial.b)*65536),
- pict->repeat);
- }
- ++buffer;
+ if (!mask || *mask++ & maskBits)
+ {
+ xFixed_48_16 t;
+
+ if (rz != 0) {
+ x = rx/rz;
+ y = ry/rz;
+ } else {
+ x = y = 0.;
+ }
+ x -= pGradient->radial.fx;
+ y -= pGradient->radial.fy;
+ b = 2*(x*pGradient->radial.dx + y*pGradient->radial.dy);
+ c = -(x*x + y*y);
+ det = (b * b) - (4 * pGradient->radial.a * c);
+ s = (-b + sqrt(det))/(2. * pGradient->radial.a);
+ t = (xFixed_48_16)((s*pGradient->radial.m + pGradient->radial.b)*65536);
+
+ *buffer = _gradient_walker_pixel (&walker, t);
+ }
+ ++buffer;
rx += cx;
ry += cy;
rz += cz;
@@ -3005,37 +3183,41 @@ static void fbFetchSourcePict(PicturePtr
while (buffer < end) {
double angle;
- if (!mask || *mask++ & maskBits)
- {
- angle = atan2(ry, rx) + a;
+ if (!mask || *mask++ & maskBits)
+ {
+ xFixed_48_16 t;
- *buffer = gradientPixel(pGradient, (xFixed_48_16) (angle * (65536. / (2*M_PI))),
- pict->repeat);
- }
+ angle = atan2(ry, rx) + a;
+ t = (xFixed_48_16) (angle * (65536. / (2*M_PI)));
+
+ *buffer = _gradient_walker_pixel (&walker, t);
+ }
++buffer;
rx += cx;
ry += cy;
}
} else {
-
while (buffer < end) {
double x, y;
- double angle;
+ double angle;
- if (!mask || *mask++ & maskBits)
- {
- if (rz != 0) {
- x = rx/rz;
- y = ry/rz;
- } else {
- x = y = 0.;
- }
- x -= pGradient->conical.center.x/65536.;
- y -= pGradient->conical.center.y/65536.;
- angle = atan2(y, x) + a;
- *buffer = gradientPixel(pGradient, (xFixed_48_16) (angle * (65536. / (2*M_PI))),
- pict->repeat);
- }
+ if (!mask || *mask++ & maskBits)
+ {
+ xFixed_48_16 t;
+
+ if (rz != 0) {
+ x = rx/rz;
+ y = ry/rz;
+ } else {
+ x = y = 0.;
+ }
+ x -= pGradient->conical.center.x/65536.;
+ y -= pGradient->conical.center.y/65536.;
+ angle = atan2(y, x) + a;
+ t = (xFixed_48_16) (angle * (65536. / (2*M_PI)));
+
+ *buffer = _gradient_walker_pixel (&walker, t);
+ }
++buffer;
rx += cx;
ry += cy;
--
1.1.3
More information about the cairo
mailing list