Bug 12047 - SVGPathSegList needs better getTotalLength, getSegmentAtLength path traversal code
Summary: SVGPathSegList needs better getTotalLength, getSegmentAtLength path traversal...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: SVG (show other bugs)
Version: 420+
Hardware: Macintosh OS X 10.4
: P2 Normal
Assignee: Dirk Schulze
URL:
Keywords:
Depends on: 10827 44009
Blocks:
  Show dependency treegraph
 
Reported: 2006-12-31 13:20 PST by Eric Seidel (no email)
Modified: 2011-05-20 13:12 PDT (History)
3 users (show)

See Also:


Attachments
Patch (8.23 KB, patch)
2011-05-20 10:52 PDT, Dirk Schulze
darin: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Eric Seidel (no email) 2006-12-31 13:20:29 PST
SVGPathSegList needs getTotalLength, getSegmentAtLength path traversal code

Now that bug 12033 is complete SVGPathElement::getTotalLength works.  However right now it uses toPathData() (without any caching).  In some cases it would be more efficient to use a getTotalLength function on a SVGPathSegList (assuming one is already created for DOM use).  Certainly getSegmentAtLengh should traverse the SVGPathSegList instead of the Path object.

This bug covers implementing SVGPathSegList path traversal functions.

The major question to answer with regards to SVGPathSegList is whether to support non-normalized path traversal or not.  (For example, we'd have to automatically process arcs into curves, or write code to measure arc length in addition to the existing code for measuring bezier curve lengths)
Comment 1 Eric Seidel (no email) 2007-01-03 08:27:20 PST
I added these when working on animateMotion.  However they don't yet work for general case SVGPathSegLists.  Currently they only work on normalized/processed SVGPathSegLists which only contain lines, movetos, closepaths, and curvetos.  Eventually support should be added for all the various types, including arcs (at least in the case of getSegmentAtLength).

Also, right now SVGPathSegList has a couple copies of the same switch statement for doing these traversals.  Better might be to add a length() method onto the individual segment classes, or to at least share the switch statement with a single common method (similar to how PathTraversalState is used to support sharing a single switch inside Path.cpp).
Comment 2 Eric Seidel (no email) 2007-06-12 10:32:44 PDT
We need a few JS test cases to demonstrate this.
Comment 3 Dirk Schulze 2010-08-14 23:31:09 PDT
Normalized behavior of TraversalState shouldn't be a problem, once the patch on bug 44009 landed.
Comment 4 Dirk Schulze 2011-05-20 10:52:49 PDT
Created attachment 94238 [details]
Patch
Comment 5 Darin Adler 2011-05-20 11:05:09 PDT
Comment on attachment 94238 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=94238&action=review

> Source/WebCore/svg/SVGPathElement.cpp:67
> +    SVGPathParserFactory* factory = SVGPathParserFactory::self();

I don’t think this local variable helps clarity or performance.

> Source/WebCore/svg/SVGPathElement.cpp:75
> +    SVGPathParserFactory* factory = SVGPathParserFactory::self();

I don’t think this local variable helps clarity or performance.

> Source/WebCore/svg/SVGPathParserFactory.cpp:282
> +    totalLength = builder->totalLength();

Should this be done only if ok is true?

> Source/WebCore/svg/SVGPathParserFactory.cpp:299
> +    point = builder->currentPoint();

Should this be done only if ok is true?

> Source/WebCore/svg/SVGPathTraversalStateBuilder.cpp:88
>  bool SVGPathTraversalStateBuilder::continueConsuming()
>  {
> -    ASSERT(m_traversalState);
> -    ASSERT(m_traversalState->m_action == PathTraversalState::TraversalSegmentAtLength);
> -    return m_traversalState->m_totalLength < m_traversalState->m_desiredLength;
> +    ASSERT(m_traversalState);    
> +    if (m_traversalState->m_action == PathTraversalState::TraversalSegmentAtLength
> +        && m_traversalState->m_totalLength >= m_traversalState->m_desiredLength)
> +        m_traversalState->m_success = true;
> +    
> +    if ((m_traversalState->m_action == PathTraversalState::TraversalPointAtLength
> +         || m_traversalState->m_action == PathTraversalState::TraversalNormalAngleAtLength)
> +        && m_traversalState->m_totalLength >= m_traversalState->m_desiredLength) {
> +        FloatSize change = m_traversalState->m_current - m_traversalState->m_previous;
> +        float slope = atan2f(change.height(), change.width());
> +        if (m_traversalState->m_action == PathTraversalState::TraversalPointAtLength) {
> +            float offset = m_traversalState->m_desiredLength - m_traversalState->m_totalLength;
> +            m_traversalState->m_current.move(offset * cosf(slope), offset * sinf(slope));
> +        } else
> +            m_traversalState->m_normalAngle = rad2deg(slope);
> +        m_traversalState->m_success = true;
> +    }
> +    m_traversalState->m_previous = m_traversalState->m_current;
> +
> +    return !m_traversalState->m_success;
>  }

Seeing m_traversalState-> so many times over and over again leads to the question of whether m_traversalState could have some function members to make this code simpler. A function like this is a bit of an anti-pattern.
Comment 6 Dirk Schulze 2011-05-20 11:41:06 PDT
Comment on attachment 94238 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=94238&action=review

>> Source/WebCore/svg/SVGPathElement.cpp:67
>> +    SVGPathParserFactory* factory = SVGPathParserFactory::self();
> 
> I don’t think this local variable helps clarity or performance.

Fixed.

>> Source/WebCore/svg/SVGPathElement.cpp:75
>> +    SVGPathParserFactory* factory = SVGPathParserFactory::self();
> 
> I don’t think this local variable helps clarity or performance.

Fixed.

>> Source/WebCore/svg/SVGPathParserFactory.cpp:282
>> +    totalLength = builder->totalLength();
> 
> Should this be done only if ok is true?

It doesn't matter. The idea is, that you check the status before using totalLength(). And totalLength() should not cause an invalid behavior (also checked by an assert). But it is just possible to grab totalLength after the parsePathDataFromSource call.

>> Source/WebCore/svg/SVGPathParserFactory.cpp:299
>> +    point = builder->currentPoint();
> 
> Should this be done only if ok is true?

Ditto.

>> Source/WebCore/svg/SVGPathTraversalStateBuilder.cpp:88
>>  }
> 
> Seeing m_traversalState-> so many times over and over again leads to the question of whether m_traversalState could have some function members to make this code simpler. A function like this is a bit of an anti-pattern.

I'll check this.
Comment 7 Dirk Schulze 2011-05-20 12:05:14 PDT
Committed r86973: <http://trac.webkit.org/changeset/86973>
Comment 8 Dirk Schulze 2011-05-20 13:12:45 PDT
Committed r86979: <http://trac.webkit.org/changeset/86979>