[cairo] Playing with spline decomposition

Bill Spitzak spitzak at thefoundry.co.uk
Fri Oct 17 14:05:13 PDT 2008

Carl Worth wrote:
> On Tue, 2008-10-14 at 21:56 +0100, Chris Wilson wrote:
>> 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).
> Interesting stuff!
>>  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 are the expected savings from this part? The whole of "using the
> pen" is a linear-time walk of the flattened path with additions to
> compute points. Oh, and some slope comparisons as the path turns---is
> that what you're hoping so save here?

I did not understand the math at all, but it looks like it produces a 
different set of straight line segments for each side of the path. This 
makes it have a lot fewer segments. Fig 10 shows this clearly.

I think it approximates the Bezier as straight lines and circular arcs. 
It is relatively easy to find the edges of the pens path of a circular 
arc, as that is also a circular arc (except when the circle is too 
small). All these arcs are then decomposed into straight lines 

Bill Spitzak, Senior Software Engineer
The Foundry, 618 Hampton Drive, Venice, CA, 90291, USA
Tel: +1 310 399-4555 * Fax: +1 310 450-4516 * Web: www.thefoundry.co.uk
The Foundry Visionmongers Ltd * Registered in England and Wales No: 4642027

More information about the cairo mailing list