Bug 12033 – SVG needs ability to calculate path lengths

• Status: RESOLVED
• Resolution: FIXED
• Component: SVG

[Eric Seidel (no email)]

SVG needs ability to calculate path lengths

This is arguably a platform bug as much as an SVG bug.

SVG requires the ability to calculate path lengths.  Both total path length, as well as the ability to identify a segment at a given length along a path.

Calculating the length of a bezier curve is non-trivial, and most algorithms use successive approximation of the curve length.

We have several options here:
1.  I expect CoreGraphics (or some other library on OS X) has this functionality (possibly not via public methods) that with a little help from the Apple folks, we could find and expose via WebKitSystemInterface.
2.  mozilla has their own code for this: http://lxr.mozilla.org/seamonkey/source/content/svg/content/src/nsSVGPathSeg.cpp#90 which we potentially could borrow, since I believe mozilla's triple license is compatible with WebKit's BSD/LGPL licensing.
4.  There may be some other library or code snippet out there that we could use
5.  We could write our own.  I'm sure one of us has a CS book which documents a decent algorithm or two.  There are also various guides on the web: (e.g. http://72.14.203.104/search?q=cache:lXe763sRSqMJ:www.cs.uiowa.edu/~kearney/22c196Spring03/ArcLengthParameterization.ppt+approximate+bezier+curve+length&hl=en&gl=us&ct=clnk&cd=5&client=safari)

In any case, this will require a non-trivial amount of effort, but the results of which enable quite a few SVG features (including text-on-path).

[Eric Seidel (no email)]

Created attachment 12116 [details]
first (incomplete) stab

What can I say?  I felt inspired.

It's kinda amusing how the 100+ lines of mozilla code which I used to start this, *completely* morphed and turned into about 20 lines of WebKit code.

This is still not done.  This only supports calculating path lengths from Path objects, not yet from SVGPathSegList objects, but that second part won't be hard to add.

When adding the SVGPathSegList code, we'll also add the ability to walk a path and find the segment at a specific length.

The only tricky part about adding the SVGPathSegList support is handling SVG Arc segments.  There is additional mozilla code we can use to convert from Arcs to curves however.

[Eric Seidel (no email)]

Created attachment 12136 [details]
Working patch

I decided to chuck the little remaining mozilla code and re-wrote it.  We use a similar text length algorithm, but (IMO) a much nicer implementation thereof.

[Eric Seidel (no email)]

*** Bug 11975 has been marked as a duplicate of this bug. ***

[Sam Weinig]

Landed in r18493.