[cairo] Mathematics question

[Jeff Muizelaar]

On 03/11/10 11:06 PM, Petr Kobalíček wrote:
> Hi list,
>
> I'm working on a graphics library (Fog, I already pushed links here)
> and currently I'm mainly focused to geometry. My questions are related
> to quadric/cubic bezier curves and their approximation. I'd like to
> know how cairo is tuned up for speed/quality and algorithms used by
> cairo.
>
> 1. When making dashes/path-on-path, which formula is used by cairo to
> get the length of a cubic bezier curve?
> I found this material
> (http://steve.hollasch.net/cgindex/curves/cbezarclen.html), but I'm
> not sure if it's the best. The second way (subdivision) is used by Qt
> and probably by many other libs. Another interesting paper is
> http://math.kennesaw.edu/~jdoto/13.pdf .
Dashing is done by flattening first so we don't need to compute the 
length of curve.
> 2. When stroking path-to-path, which algorithm is used by cairo?
> Making offset of a cubic curve is complicated and it must be
> approximated by more curves. Is somewhere material that describes the
> algorithm used by cairo? Or is somewhere source-code used as a base
> for the work in cairo?
cairo doesn't currently support stroking to a path, however I have a 
work in progress patch that
adds it: 
http://cgit.freedesktop.org/~ranma42/cairo/commit/?h=wip/stroke-to-path&id=330bcfa088bde325f839cf905514bd91094af25a

This uses a hybrid approach combining the method from "Offsets of 
Two-Dimensional Profiles"
with something I came up with to deal with degenerate cases.
> 3. When approximating curves to lines (flattening before
> rasterization), how algorithm is used by cairo and how it competes to
> the others? I found very interesting article (
> http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/Bezier%20Offset%20Curves.pdf
> ) that describes parabolic approximation. Is here anybody familiar
> with this method?
Cairo recursively subdivides a curve until the maximum distance 
(squared) between the control points B or C and the line A-D is less 
than the tolerance.

I've seen this paper before, but haven't tried implementing it to see 
how it compares.

-Jeff