[cairo] Re: adding a new curve type to cairo

[Carl Worth]

On Thu, 13 Jul 2006 12:49:42 -0700 (PDT), Jeff Smith wrote:
> --- Jeff Smith <whydoubt at yahoo.com> wrote:
> > --- Niki Spahiev <niki.spahiev at gmail.com> wrote:
> > > Carl Worth wrote:
> > > > poorly approximated with individual cubic B�ziers, (even the common
> > > > approach of 4 cubic B�ziers per circle is poor, so cairo_arc does
> > > > better than that when necessary).
> > > 
> > > Any info on how poor it is?
> > 
> > http://cgafaq.info/wiki/Bezier_Circle.  I am pretty sure the formula is correct, as I
> > calculated it independently once upon a time.  The accuracy stated I cannot vouch for.
> 
> I found a program I wrote once to calculate the accuracy.  I calculated it with higher
> precision than that given on the page I just cited.  The most inaccurate point is off by
> 0.027253% of the radius.  This occurs at +/-19.02 degrees from each of (0, 90, 180, 270)
> degrees. 

The papers cited there are the same papers I read when doing the
implementation in cairo. Here are the comments I wrote in cairo-arc.c
when I did that:

/* 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).
*/

/* Spline deviation from the circle in radius would be given by:

	error = sqrt (x**2 + y**2) - 1

   A simpler error function to work with is:

	e = x**2 + y**2 - 1

   From "Good approximation of circles by curvature-continuous Bezier
   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)

   and
	abs (error) =~ 1/2 * e

   Of course, this error value applies only for the particular spline
   approximation that is used in _cairo_gstate_arc_segment.
*/

You can find the current version of cairo-arc.c here:

http://gitweb.freedesktop.org/?p=cairo;a=blob;h=fdef6a32570aa4d6df8aad10f780b57659acec12;hb=6a5d66f651b7fe94e74ee803a452bac5b54c95ca;f=src/cairo-arc.c

The error calculation above suggests that the error for using 4
splines for a circle would be about:

	radius * 1/2 * 4/27 * sin**6(pi/8) / cos**2(pi/8)

which is about:

	radius * 0.00027256714373

Which says that we're all pretty much in agreement about the error.

So, if you only care about getting within the nearest pixel, using 4
splines per circle is pretty good and the error won't exceed 0.5
pixels until a radius greater than about 1834 or so.

Meanwhile, cairo will use enough splines to maintain an accuracy
within the tolerance value specified by cairo_set_tolerance, (which is
0.1 pixels by default). So, by default cairo is using more than 4
splines per circle at radius values greater than about 367.

And, interestingly enough, cairo will also use only 2 splines per
circle when it can get away with it. The error for approximating an
angle of pi instead of pi/2 gets bad pretty fast, roughly:

	radius * 1/2 * 4/27 * sin**6(pi/4) / cos**2(pi/4)

which is about:

	radius * 0.018518518518518

But even with the default tolerance of 0.1 pixels, this means that 2
splines per pixel is sufficient for circles of radius 5 or less. That
was a surprising result to me. And I've wondered if many other systems
actually take advantage of that.

-Carl
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://lists.freedesktop.org/archives/cairo/attachments/20060713/4310efc8/attachment.pgp