[cairo] Questions and optimizations in cairoarc
Behdad Esfahbod
behdad at cs.toronto.edu
Tue Jul 26 03:42:27 PDT 2005
Hi,
I was looking at the cairoarc.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 pathmodifying operations only allowed to query the
current point, or the alreadybuilt parts of the path too? I'm
thinking about metapoststyle 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/cairoarc.c
===================================================================
RCS file: /cvs/cairo/cairo/src/cairoarc.c,v
retrieving revision 1.3
diff u p r1.3 cairoarc.c
 src/cairoarc.c 11 Jul 2005 20:29:46 0000 1.3
+++ src/cairoarc.c 26 Jul 2005 09:55:53 0000
@@ 50,7 +50,7 @@
curves", Tor Dokken and Morten Daehlen, Computer Aided Geometric
Design 8 (1990) 2241, 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) 227238, 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, (6thorder 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) 227238, 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, (6thorder 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