[cairo] Questions and optimizations in cairo-arc
Behdad Esfahbod
behdad at cs.toronto.edu
Tue Jul 26 03:42:27 PDT 2005
Hi,
I was looking at the cairo-arc.c source code and performed some
trivial optimizations. Patch attached.
I've got a few questions though:
- What does the signature of cairo_arc_to should look like? I
see this in cairo.h:
/* XXX: NYI
void
cairo_arc_to (cairo_t *cr,
double x1, double y1,
double x2, double y2,
double radius);
*/
but I cannot make any sense of it. AFAIU the '_to' functions are
use the current point. Then with x1,y1 and x2,y2 we would have
three points and there is a unique arc starting at current point,
passing x1,y1 and ending at x2,y2. No need for radius. But the
problem is that:
- This is not the '_to' version of cairo_arc. A '_to' version
of cairo_arc makes no sense, since cairo_arc does not get an
starting point.
- This definition of cairo_arc_to is hardly useful, since you
need to know a point on the arc, which is not quite obvious.
A viable signature would be:
void
cairo_arc_to (cairo_t *cr,
double x, double y,
double radius);
and draws the unique arc with the specified radius that connects
the current point to x,y. This still has the problem that it is
not the '_to' version of cairo_arc.
All these brought me to the next question:
- Are these path-modifying operations only allowed to query the
current point, or the already-built parts of the path too? I'm
thinking about metapost-style features, like drawing smooth
paths, computing the control points of the bezier, etc. And then
you can actually uniquely and smoothly arc_to any point, given
access to current and previous points on the path.
- Is there any interest in developing abovementioned features?
I understand that cairo is not metafont/metapost, but having
these features helps a lot when you actually write code using
cairo manually, in contrast to when cairo is used as a backend to
something like a viewer or editor, for example.
- One more thing that I find useful is functions that get a
path and produce another path. One useful example would be a
function that give a path and pen, computes the outline of the
stroke. Another one is a function that given a path, outputs
another path that uses arcs of (at most) some radius instead of
sharp joints. Then for example you can filter the path from
cairo_rectangle to get a rectangle with round edges, etc... Any
thoughts about how useful these may be? Intersecting paths comes
to my mind too, and union, etc...
- One more thing that I noticed is that in many places in the
code we(well, you :-) need to compute both sin and cos of the
same angle. Most FPUs have a single instruction for doing this,
and glibc has a function for it too: sincos(3). I think it's
worth using that. Fortunately a simple implementation with no
drawback is possible:
#if HAVE_SINCOS
# define _cairo_sincos(angle,s,c) sincos((angle), (s), (c))
#else
# define _cairo_sincos(angle,s,c) \
do { *(s) = sin(angle); *(c) = cos(angle); } while (0)
#endif
Cheers,
--behdad
http://behdad.org/
-------------- next part --------------
Index: src/cairo-arc.c
===================================================================
RCS file: /cvs/cairo/cairo/src/cairo-arc.c,v
retrieving revision 1.3
diff -u -p -r1.3 cairo-arc.c
--- src/cairo-arc.c 11 Jul 2005 20:29:46 -0000 1.3
+++ src/cairo-arc.c 26 Jul 2005 09:55:53 -0000
@@ -50,7 +50,7 @@
curves", Tor Dokken and Morten Daehlen, Computer Aided Geometric
Design 8 (1990) 22-41, we learn:
- abs (max(e)) = 4/27 * sin**6(angle/4) / cos**2(angle/4)
+ max (abs(e)) = 4/27 * sin**6(angle/4) / cos**2(angle/4)
and
abs (error) =~ 1/2 * e
@@ -71,7 +71,7 @@ _arc_max_angle_for_tolerance_normalized
int i;
/* Use table lookup to reduce search time in most cases. */
- struct {
+ const struct {
double angle;
double error;
} table[] = {
@@ -93,16 +93,15 @@ _arc_max_angle_for_tolerance_normalized
if (table[i].error < tolerance)
return table[i].angle;
- ++i;
do {
- angle = M_PI / i++;
+ angle = M_PI / ++i;
error = _arc_error_normalized (angle);
} while (error > tolerance);
return angle;
}
-/* XXX: The computation here if bogus. Correct math (with proof!) is
+/* XXX: The computation here is bogus. Correct math (with proof!) is
* available in _cairo_pen_vertices_needed. */
static int
_arc_segments_needed (double angle,
@@ -127,59 +126,6 @@ _arc_segments_needed (double angle
return (int) ceil (angle / max_angle);
}
-/* We want to draw a single spline approximating a circular arc radius
- R from angle A to angle B. Since we want a symmetric spline that
- matches the endpoints of the arc in position and slope, we know
- that the spline control points must be:
-
- (R * cos(A), R * sin(A))
- (R * cos(A) - h * sin(A), R * sin(A) + h * cos (A))
- (R * cos(B) + h * sin(B), R * sin(B) - h * cos (B))
- (R * cos(B), R * sin(B))
-
- for some value of h.
-
- "Approximation of circular arcs by cubic poynomials", Michael
- Goldapp, Computer Aided Geometric Design 8 (1991) 227-238, provides
- various values of h along with error analysis for each.
-
- From that paper, a very practical value of h is:
-
- h = 4/3 * tan(angle/4)
-
- This value does not give the spline with minimal error, but it does
- provide a very good approximation, (6th-order convergence), and the
- error expression is quite simple, (see the comment for
- _arc_error_normalized).
-*/
-static void
-_cairo_arc_segment (cairo_t *cr,
- double xc,
- double yc,
- double radius,
- double angle_A,
- double angle_B)
-{
- double r_sin_A, r_cos_A;
- double r_sin_B, r_cos_B;
- double h;
-
- r_sin_A = radius * sin (angle_A);
- r_cos_A = radius * cos (angle_A);
- r_sin_B = radius * sin (angle_B);
- r_cos_B = radius * cos (angle_B);
-
- h = 4.0/3.0 * tan ((angle_B - angle_A) / 4.0);
-
- cairo_curve_to (cr,
- xc + r_cos_A - h * r_sin_A,
- yc + r_sin_A + h * r_cos_A,
- xc + r_cos_B + h * r_sin_B,
- yc + r_sin_B - h * r_cos_B,
- xc + r_cos_B,
- yc + r_sin_B);
-}
-
static void
_cairo_arc_in_direction (cairo_t *cr,
double xc,
@@ -194,7 +140,7 @@ _cairo_arc_in_direction (cairo_t *cr,
/* Recurse if drawing arc larger than pi */
if (angle_max - angle_min > M_PI) {
- double angle_mid = angle_min + (angle_max - angle_min) / 2.0;
+ double angle_mid = (angle_min + angle_max) / 2.0;
/* XXX: Something tells me this block could be condensed. */
if (dir == CAIRO_DIRECTION_FORWARD) {
_cairo_arc_in_direction (cr, xc, yc, radius,
@@ -217,6 +163,7 @@ _cairo_arc_in_direction (cairo_t *cr,
cairo_matrix_t ctm;
int i, segments;
double angle, angle_step;
+ double dx1, dy1, h;
cairo_get_matrix (cr, &ctm);
segments = _arc_segments_needed (angle_max - angle_min,
@@ -231,11 +178,53 @@ _cairo_arc_in_direction (cairo_t *cr,
angle_step = - angle_step;
}
+ /* We want to draw a single spline approximating a circular arc radius
+ R from angle A to angle B. Since we want a symmetric spline that
+ matches the endpoints of the arc in position and slope, we know
+ that the spline control points must be:
+
+ (R * cos(A), R * sin(A))
+ (R * cos(A) - R * h * sin(A), R * sin(A) + R * h * cos (A))
+ (R * cos(B) + R * h * sin(B), R * sin(B) - R * h * cos (B))
+ (R * cos(B), R * sin(B))
+
+ for some value of h.
+
+ "Approximation of circular arcs by cubic poynomials", Michael
+ Goldapp, Computer Aided Geometric Design 8 (1991) 227-238, provides
+ various values of h along with error analysis for each.
+
+ From that paper, a very practical value of h is:
+
+ h = 4/3 * tan(angle/4)
+
+ This value does not give the spline with minimal error, but it does
+ provide a very good approximation, (6th-order convergence), and the
+ error expression is quite simple, (see the comment for
+ _arc_error_normalized).
+ */
+ h = 4.0/3.0 * tan (angle_step / 4.0);
+
+ dx1 = radius * cos (angle);
+ dy1 = radius * sin (angle);
+ angle += angle_step;
+
for (i = 0; i < segments; i++, angle += angle_step) {
- _cairo_arc_segment (cr, xc, yc,
- radius,
- angle,
- angle + angle_step);
+ double dx2, dy2;
+
+ dx2 = radius * cos (angle);
+ dy2 = radius * sin (angle);
+
+ cairo_curve_to (cr,
+ xc + dx1 - h * dy1,
+ yc + dy1 + h * dx1,
+ xc + dx2 + h * dy2,
+ yc + dy2 - h * dx2,
+ xc + dx2,
+ yc + dy2);
+
+ dx1 = dx2;
+ dy1 = dy2;
}
}
}
More information about the cairo
mailing list