Fixing the behavior of SkPathMeasure to reflect changes in SkPath::Iter.

Fixing the behavior of SkPathMeasure to reflect changes in SkPath::Iter.
This implementation modifies SkPath::Iter extensively to avoid copying
the points when used to measure path length.

BUG=446
TEST=tests/PathMeasureTest.cpp
Committed: https://code.google.com/p/skia/source/detail?r=3062

[Stephen Chenney, 2012-01-11 22:43:14]

http://codereview.appspot.com/5533074/diff/1/include/core/SkPath.h
File include/core/SkPath.h (left):

http://codereview.appspot.com/5533074/diff/1/include/core/SkPath.h#oldcode770
include/core/SkPath.h:770: friend const SkPoint* sk_get_path_points(const
SkPath&, int index);
No longer required

http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp
File src/core/SkPathMeasure.cpp (left):

http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#oldco...
src/core/SkPathMeasure.cpp:18: kCloseLine_SegType,
Not needed now that we cache the segment points, instead of relying on the array
in SkPath.

http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#oldco...
src/core/SkPathMeasure.cpp:170: if (!SkScalarNearlyZero(d)) {
New SkPath::Iter behavior will never give a zero length path.

[reed1, 2012-01-11 22:56:45]

is this related http://codereview.appspot.com/5529074/

[schenney, 2012-01-11 23:04:33]

On Wed, Jan 11, 2012 at 5:56 PM, <reed@google.com> wrote:

> is this related
http://codereview.appspot.com/**5529074/<http://codereview.appspot.com/5529074/>
>
>
http://codereview.appspot.com/**5533074/<http://codereview.appspot.com/5533074/>
>

Yes and no. :-)

The code you have changed always adds the necessary move after close at
construction time, while the existing code added it at iteration time. With
your change we could remove the code that inserts the move during iteration.

The problems with SkPathMeasure come from degenerate segments (in addition
to the missing move) so the fix I have up is still needed.

Life would be easier for me in SVG land if your change still went in. I'll
comment on the review to that effect.

Cheers,
Stephen.
-
-
Stephen Chenney | Software Engineer | schenney@google.com | 404-314-1809

[reed1, 2012-01-12 13:03:48]

I was hoping to find a way to not require making a copy of all of the points. I
need to read this CL a bit more to see why that is still needed.

[reed1, 2012-01-12 13:05:33]

Perhaps we can land just the change to PathMeasureTest (disabled) so we can use
to it locally exercise each CL as we work on them.

[Stephen Chenney, 2012-01-12 14:31:12]

On 2012/01/12 13:03:48, reed1 wrote:
> I was hoping to find a way to not require making a copy of all of the points.
I
> need to read this CL a bit more to see why that is still needed.

It was need due to the issue that your other change fixes. That is, when a close
is not followed by an explicit move in the existing code, the points that define
a primitive are not contiguous in the path pts array. With your fix, it is
always the case, even with degenerate paths, that there are enough contiguous
points to define the primitive.

I think I would get your fix in first. Then I will try to refactor SkPathMeasure
to be a subclass of SkPath::Iter and have a custom iteration function that
returns the index of the primitive instead of copying and returning the points.
I think that's much cleaner than modifying the current code, and it avoids any
data copying or public exposure of private methods or data.

[Stephen Chenney, 2012-01-12 14:31:46]

On 2012/01/12 13:05:33, reed1 wrote:
> Perhaps we can land just the change to PathMeasureTest (disabled) so we can
use
> to it locally exercise each CL as we work on them.

Good idea. I will land the tests when I get in to the office.

[Stephen Chenney, 2012-01-12 15:15:17]

On 2012/01/12 14:31:46, Stephen Chenney wrote:
> On 2012/01/12 13:05:33, reed1 wrote:
> > Perhaps we can land just the change to PathMeasureTest (disabled) so we can
> use
> > to it locally exercise each CL as we work on them.
> 
> Good idea. I will land the tests when I get in to the office.

Tests up.
http://codereview.appspot.com/5529078/

[Stephen Chenney, 2012-01-13 00:17:58]

A patch is up that avoids copying the pts array for use by SkPathMeasure.
However, it is dramatically more complicated and required significant changes to
SkPath::Iter. I prefer the copying solution in the first patch set.

To avoid copying the points SkPath::Iter must be modified to work using point
indexes instead of pointers, and it needs to track the most recent contiguous
points defining any primitive, even in the presence of degeneracies.

[reed1, 2012-01-13 20:08:30]

we you upload a rebaselined version, now that the inject CL has landed?

[Stephen Chenney, 2012-01-13 21:25:47]

On 2012/01/13 20:08:30, reed1 wrote:
> we you upload a rebaselined version, now that the inject CL has landed?

I think I've done what you would like. If you compare Patch set 2 to the base, I
believe you will see diffs against the latest revision.

[reed1, 2012-01-13 21:37:09]

wonder if this affects Iter perf at all. Brian has been concerned about this in
the past. I will look to see if we already have a bench.

http://codereview.appspot.com/5533074/diff/11007/src/core/SkPath.cpp
File src/core/SkPath.cpp (right):

http://codereview.appspot.com/5533074/diff/11007/src/core/SkPath.cpp#newcode137
src/core/SkPath.cpp:137: fVerbs           = src.fVerbs;
dup w/ line 143

http://codereview.appspot.com/5533074/diff/11007/src/core/SkPath.cpp#newcode169
src/core/SkPath.cpp:169: fVerbs.swap(other.fVerbs);
we are swaping fLastMoveToIndex twice now (see line 175)

http://codereview.appspot.com/5533074/diff/11007/src/core/SkPath.cpp#newcode1316
src/core/SkPath.cpp:1316: SkScalarIsNaN(fPts[fMoveToIndex].fY)) {
do we need 

if (startIndex)

before the assignment?

[reed1, 2012-01-13 21:38:55]

can we make the two index* arguments to Iter::next() be required, so we can skip
all of the null-ptr checks inside?

[Stephen Chenney, 2012-01-13 21:42:02]

On 2012/01/13 21:38:55, reed1 wrote:
> can we make the two index* arguments to Iter::next() be required, so we can
skip
> all of the null-ptr checks inside?

Yes. I think we should just pass them by reference and we can get rid of many
ifs.

And yes, it may be worse for performance. Worse than the path measure points
copy, probably. Given that we don't measure paths as often as we iterate (every
time we draw) I like the simpler patch more.

Maybe there is some more optimization that can be squeezed out, but there's a
lot of state to track.

[reed1, 2012-01-13 22:00:04]

nit: don't use references for mutable parameters -- confuses the call site
reader. asserts are fine to help document that they are required: e.g.

void next (int* index) {
    SkASSERT(index);
    ...
    *index = ...
}

[Stephen Chenney, 2012-01-13 22:17:13]

On 2012/01/13 22:00:04, reed1 wrote:
> nit: don't use references for mutable parameters -- confuses the call site
> reader. asserts are fine to help document that they are required: e.g.
> 
> void next (int* index) {
>     SkASSERT(index);
>     ...
>     *index = ...
> }

Got the message. :-)

All comments addressed, short of performance checks.

[reed1, 2012-01-17 14:11:32]

I see a new private method plus making measure a friend, to get at next(index,
index). Why is this needed, instead of calling the existing next(pts) method?

[Stephen Chenney, 2012-01-17 14:32:24]

On 2012/01/17 14:11:32, reed1 wrote:
> I see a new private method plus making measure a friend, to get at next(index,
> index). Why is this needed, instead of calling the existing next(pts) method?

Because SkPathMeasure does not want to copy points, so it needs the indexes into
the internal SkPath array of point data and access to that data. Such
information is not available from other methods.

[Stephen Chenney, 2012-01-17 15:36:37]

Let's back up a step.

The correctness issue is with SkPathMeasure. SkPath::Iter is correct as
currently implemented, but the change in behavior to handle degenerate path
segments caused assumptions in SkPathMeasure to fail. In my opinion they were
bad assumptions, and failed in certain circumstances.

There are two very different fixes up for review in
http://codereview.appspot.com/5533074/.

Patch Set 1 modifies SkPathMeausure to copy the points returned by
SkPath::Iter::next. This allocates memory each time a SkPathMeasure is created
for a certain path. The fix is very clean - it makes the code in SkPathMeasure
simpler and leaves the code in SkPath::Iter as is. It removes a requirement that
SkPathMeasure or any of its methods be friends of SkPath.

Patch Set 3 modifies SkPath::Iter to allow SkPathMeasure to avoid copying
points. In this scenario, SkPathMeasure doesn't change much but SkPath::Iter
changes a whole lot and becomes significantly more complicated and hard to
understand.

The question is: which patch set to use? I ran performance numbers and they seem
to be the same speed. Given that,  I prefer Path Set 1 because it is much
simpler and easier to understand, and protects better against future changes to
the SkPath implementation. The core Skia team may feel otherwise, and I am
totally happy to go with Patch Set 3 if desired.

[reed1, 2012-01-17 16:27:29]

Is the change that you're referring to, the removal of degenerate segments
during Iter:next? If so, then I think I understand the motivation for patch#1
(btw, next time, it might be easier to have separate CLs if we're going to
explore different approaches).

If path.lineTo/quadTo/cubicTo performed the degenerate test itself, and
suppressed those segments, would pathmeasure work as is? I ask partly to
understand more, and partly in case this would/could make iteration faster.

[Stephen Chenney, 2012-01-17 16:42:45]

On 2012/01/17 16:27:29, reed1 wrote:
> Is the change that you're referring to, the removal of degenerate segments
> during Iter:next? If so, then I think I understand the motivation for patch#1
> (btw, next time, it might be easier to have separate CLs if we're going to
> explore different approaches).
> 
> If path.lineTo/quadTo/cubicTo performed the degenerate test itself, and
> suppressed those segments, would pathmeasure work as is? I ask partly to
> understand more, and partly in case this would/could make iteration faster.

Yes, the instigating change was to have SkPath::Iter handle degenerate segment
removal. This unblocked WebKit SVG work.

I think SkPathMeasure could stay as it is if degenerate segments are removed at
construction time and if moveTo are inserted at each new contour (as they now
are).

While the lineTo/quadTo/cubicTo methods could perform degenerate checking
themselves, that would leave us back in trouble in WebKit SVG land, where we
need the raw data as entered by the user. 

The overhead of testing degeneracy on non-degenerate paths (the most common
case) is minimal, if any. The primary cost of iteration is in managing the
closing of contours for fill and filling in the return data, and that code
cannot easily change.

It occurs to me that we have another possible approach. We can use super fast
raw iteration in cases where (a) the path is not degenerate and (b) closed
contours are not required. We can probably figure out a  way to detect these
conditions, cache them, and serve up the fastest iterator.

First I would like to get one of these fixes in place to resolve the WebKit SVG
issues. Then I can contribute to optimizing.

[reed1, 2012-01-17 17:01:13]

comments on patch#1

http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp
File src/core/SkPathMeasure.cpp (right):

http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#newco...
src/core/SkPathMeasure.cpp:189: kMaxTValue, ptIndex);
Why are we setting isClosed here? (and not in kQuadTo).

http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#newco...
src/core/SkPathMeasure.cpp:236: const SkPoint*
sk_get_path_points(SkTDArray<SkPoint>& pts, int index) {
is this function local now? should it be static inline ...?
is it really needed? can the caller just say &pts[index]?

http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#newco...
src/core/SkPathMeasure.cpp:239: 
can segmentPts be const?

http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#newco...
src/core/SkPathMeasure.cpp:240: static void compute_pos_tan(SkTDArray<SkPoint>&
segmentPts,
Do we still need firstPtIndex as a parameter?

http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#newco...
src/core/SkPathMeasure.cpp:271: 
can segmentPts be const?

http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#newco...
src/core/SkPathMeasure.cpp:272: static void seg_to(SkTDArray<SkPoint>&
segmentPts,
Do we need firstPtIndex?

[Stephen Chenney, 2012-01-17 18:47:12]

Does the simplicity of this patch win out over the alternative?

http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp
File src/core/SkPathMeasure.cpp (right):

http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#newco...
src/core/SkPathMeasure.cpp:189: kMaxTValue, ptIndex);
On 2012/01/17 17:01:13, reed1 wrote:
> Why are we setting isClosed here? (and not in kQuadTo).

I think it should have been removed.

http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#newco...
src/core/SkPathMeasure.cpp:236: const SkPoint*
sk_get_path_points(SkTDArray<SkPoint>& pts, int index) {
On 2012/01/17 17:01:13, reed1 wrote:
> is this function local now? should it be static inline ...?
> is it really needed? can the caller just say &pts[index]?

It can go. It existed before to be the friend of SkPath, rather than making the
entire class a friend.

http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#newco...
src/core/SkPathMeasure.cpp:239: 
On 2012/01/17 17:01:13, reed1 wrote:
> can segmentPts be const?

Yes.

http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#newco...
src/core/SkPathMeasure.cpp:240: static void compute_pos_tan(SkTDArray<SkPoint>&
segmentPts,
On 2012/01/17 17:01:13, reed1 wrote:
> Do we still need firstPtIndex as a parameter?

No. It can go.

http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#newco...
src/core/SkPathMeasure.cpp:271: 
On 2012/01/17 17:01:13, reed1 wrote:
> can segmentPts be const?

Yes.

http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#newco...
src/core/SkPathMeasure.cpp:272: static void seg_to(SkTDArray<SkPoint>&
segmentPts,
On 2012/01/17 17:01:13, reed1 wrote:
> Do we need firstPtIndex?

No.

[reed1, 2012-01-17 18:57:50]

On 2012/01/17 18:47:12, Stephen Chenney wrote:
> Does the simplicity of this patch win out over the alternative?

yes, simplicity + knowning the exact bug (degenerate paths changing the pt
indices w/o pathmeasure knowing)

> 
> http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp
> File src/core/SkPathMeasure.cpp (right):
> 
>
http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#newco...
> src/core/SkPathMeasure.cpp:189: kMaxTValue, ptIndex);
> On 2012/01/17 17:01:13, reed1 wrote:
> > Why are we setting isClosed here? (and not in kQuadTo).
> 
> I think it should have been removed.
> 
>
http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#newco...
> src/core/SkPathMeasure.cpp:236: const SkPoint*
> sk_get_path_points(SkTDArray<SkPoint>& pts, int index) {
> On 2012/01/17 17:01:13, reed1 wrote:
> > is this function local now? should it be static inline ...?
> > is it really needed? can the caller just say &pts[index]?
> 
> It can go. It existed before to be the friend of SkPath, rather than making
the
> entire class a friend.
> 
>
http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#newco...
> src/core/SkPathMeasure.cpp:239: 
> On 2012/01/17 17:01:13, reed1 wrote:
> > can segmentPts be const?
> 
> Yes.
> 
>
http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#newco...
> src/core/SkPathMeasure.cpp:240: static void
compute_pos_tan(SkTDArray<SkPoint>&
> segmentPts,
> On 2012/01/17 17:01:13, reed1 wrote:
> > Do we still need firstPtIndex as a parameter?
> 
> No. It can go.
> 
>
http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#newco...
> src/core/SkPathMeasure.cpp:271: 
> On 2012/01/17 17:01:13, reed1 wrote:
> > can segmentPts be const?
> 
> Yes.
> 
>
http://codereview.appspot.com/5533074/diff/1/src/core/SkPathMeasure.cpp#newco...
> src/core/SkPathMeasure.cpp:272: static void seg_to(SkTDArray<SkPoint>&
> segmentPts,
> On 2012/01/17 17:01:13, reed1 wrote:
> > Do we need firstPtIndex?
> 
> No.

[Stephen Chenney, 2012-01-18 16:49:43]

I've addresses the issues Mike raised. Best to diff against Patch Set 1, or the
base. Don't try to diff against patch set 2.

[reed1, 2012-01-18 17:18:15]

lgtm

[Stephen Chenney, 2012-01-18 18:02:34]

r3062

[Stephen Chenney, 2012-01-18 18:11:23]

And r3063 for a missing file.