[cairo] Playing with spline decomposition

[Chris Wilson]

I'm sure some of you have a better spline decomposition routine than the
current recursive De Casteljau algorithm. In particular, the "Fast,
precise flattening of cubic Bezier path and offset curves" by T F Hain
et al, seems quite promising. (I can no longer find a link to the paper,
but I did find the two master theses upon which the paper is based
http://www.cis.usouthal.edu/~hain/general/Theses/Racherla_thesis.pdf and
http://www.cis.usouthal.edu/~hain/general/Theses/Ahmad_thesis.pdf) The
premise of that paper is that by using a more accurate bisection length
we can reduce the number of points required for flattening the spline.
As the spline is immediately feed into the tessellator for
trapezoidation, even a small reduction can have a dramatic impact on
performance. (For example, my first foray is just a bisection search for
the best step length, and achieves a 20% reduction in tessellation -
about an 8% speed up for the whole benchmark.) The second aspect sounds
even more promising as it suggests that we can entirely avoid using the
pen whilst stroking curve segments, and generate more accurate results
with even fewer points.

What surprises me though is that I can find little discussion of this
paper. Has any one come across this work, or have a faster method of
generating a flattened curve with the minimum number of segments?
-- 
Chris
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0006--spline-Bisection-search-for-optimal-subdivision.patch
Type: text/x-patch
Size: 0 bytes
Desc: 
Url : http://lists.cairographics.org/archives/cairo/attachments/20081014/c1252953/attachment.bin