path ops for Skia

[Cary Clark]

I have a series of CLs that will enable computing the intersection, union, difference, and so on, of SkPaths.

The first of these CLs defines data types and some basic math to operate on those types:

https://codereview.chromium.org/12827020/

If you have a bent towards math or geometry, please consider adding yourself as a reviewer. 

Thanks

Cary

[Rik Cabanier]

Hi Cary,

this is great!

How much testing have you done on this? Is there a wiki that describes the capabilities and how the intersections are calculated?

Rik

[Cary Clark]

Hi Rik

I've run about 20 million sequential and random tests that perform simplify, intersection, union, difference, and xor on contours made up of rectangles, triangles, quadrilaterals, quadratics, cubics, and degenerate paths.

The external interface is trivial and for now mirrors SkRegion's Op method. 

There's no wiki. I write up some design documentation later.

The line/line quad/quad quad/line cubic/line intersections are computed by solving the implicit equations.

The cubic self-intersection and the cubic/cubic intersection is novel as far as I know. Computing cubic intersections has been very challenging.

Cary

[Rik Cabanier]

On Mon, Mar 25, 2013 at 5:20 AM, Cary Clark <cary...@google.com> wrote:

Hi Rik

I've run about 20 million sequential and random tests that perform simplify, intersection, union, difference, and xor on contours made up of rectangles, triangles, quadrilaterals, quadratics, cubics, and degenerate paths.

The external interface is trivial and for now mirrors SkRegion's Op method. 

There's no wiki. I write up some design documentation later.

The line/line quad/quad quad/line cubic/line intersections are computed by solving the implicit equations.

The cubic self-intersection and the cubic/cubic intersection is novel as far as I know. Computing cubic intersections has been very challenging.

We have an internal library that does that too. It took us a long time to get it right and we use it all the time.

What does simplify do? Does it remove unneeded intersections and make the path agnostic to winding rules?

[Cary Clark]

Simplify reduces the path to its simplest form so that it draws the same area as the original without overlapping contours.

[Cary Clark]

I've uploaded the second CL in the series. This one deals with computing the intersections of lines, quads, and cubics.

https://codereview.chromium.org/12880016/

[Rik Cabanier]

once this is stable, we can start thinking on what API surface we can create to expose this.

I have a proposal for canvas shapes that could be extended so you can do the path operations and there are also SVG proposals (vector effects)