[cairo] Summer of Code ideas

[Jeff Muizelaar]

On Fri, Mar 28, 2008 at 12:38:54AM +0100, Marc Vinyals wrote:
> Hi,
> 
> I found some of the ideas for SoC interesting, so I decided to introduce 
> myself and ask some questions. I'm primarily interested in math-related 
> algorithms/projects, thus both implementing cairo_stroke_to_path() and 
> implementing path operations like combine/intersect/overlay look good to 
> me. Maybe path operations would be more challenging, but this is just my 
> first feeling.

It would be neat to have a stroke_to_path that preserved splines. The
generaly used term for this kind of thing is 'offset curve'. Exact
offset curves likely don't exist for cairo's splines so you'd have to
approximate them, but afaict there's a fair amount of literature on
doing this.

> 
> I see some guidelines already exist, but I'd like to know how much fixed 
>  would the projects be. I mean, would it consist of implementing 
> already known algorithms or would the student have freedom at developing 
> an approach to the problems?

I haven't come across a 'textbook' algorithm for doing stroke_to_path.
I've looked at a bunch different implementations and there's a fair
amount of variation among them. A lot of it depends on the requirements
for the result. Cairo's stroking code, for example, produces trapezoids
targeted at rasterization backends.

At one end of the spectrum you could just turn these trapezoids into
individual paths to produce the final path (see behdad's user-font
branch). At the other end you could produce the cleanest non-intersecting
path that represents stroke. 

Also, for software rasterization purposes, it may be useful to produce
clean possibly-intersecting path. This avoids the cost of computing
intersections and can be filled using the non-zero rule. It's my
understanding that this is what AGG does.

-Jeff