New issue
Advanced search Search tips

Issue 1036 link

Starred by 7 users

Issue metadata

Status: Accepted
Owner: ----
Cc:
Area: Geometry
NextAction: ----
Priority: Low
Type: Idea



Sign in to add a comment

path-length thoughts

Project Member Reported by reed@google.com, Dec 21 2012

Issue description

Cool math for exactly quadratic arc-length

http://segfaultlabs.com/docs/quadratic-bezier-curve-length

Webkit code for path-length

http://trac.webkit.org/browser/trunk/Source/WebCore/platform/graphics/PathTraversalState.cpp

Skia has this in SkPathMeasure.

1. Is SkPathMeasure as fast as it should be?
2. Can we make it more accurate w/o hurting speed (much)?

Dashing and textOnPath are the big users of our pathmeasure.
 
Project Member

Comment 1 by hcm@google.com, Sep 10 2014

Labels: -Type-Defect -Priority-Medium Type-Idea Priority-Low Area-Geometry
Project Member

Comment 2 by caryclark@google.com, Sep 2 2015

Status: Invalid
Sadly the cool math page is now a sexy lady smoking a cigarette and the Webkit code does nothing more interesting than subdivide until the curve is flat. Marking Invalid -- feel free to reopen if you come across more cool math in the future.
Project Member

Comment 3 by reed@google.com, Sep 2 2015

Project Member

Comment 4 by caryclark@google.com, Sep 2 2015

Copying the implementation for future generations

float blen(v* p0, v* p1, v* p2)
{
 v a,b;
 a.x = p0->x - 2*p1->x + p2->x;
 a.y = p0->y - 2*p1->y + p2->y;
 b.x = 2*p1->x - 2*p0->x;
 b.y = 2*p1->y - 2*p0->y;
 float A = 4*(a.x*a.x + a.y*a.y);
 float B = 4*(a.x*b.x + a.y*b.y);
 float C = b.x*b.x + b.y*b.y;

 float Sabc = 2*sqrt(A+B+C);
 float A_2 = sqrt(A);
 float A_32 = 2*A*A_2;
 float C_2 = 2*sqrt(C);
 float BA = B/A_2;

 return ( A_32*Sabc + 
          A_2*B*(Sabc-C_2) + 
          (4*C*A-B*B)*log( (2*A_2+BA+Sabc)/(BA+C_2) ) 
        )/(4*A_32);
};

Project Member

Comment 5 by hcm@google.com, Nov 23 2015

Labels: Hotlist-Fixit
Project Member

Comment 6 by caryclark@google.com, Dec 18 2015

Cc: -caryclark@google.com
Owner: caryclark@google.com
Status: Accepted
The following revision refers to this bug:
  https://skia.googlesource.com/skia.git/+/17bc0851d34afe8c89d7455c061a1d419f76af8a

commit 17bc0851d34afe8c89d7455c061a1d419f76af8a
Author: caryclark <caryclark@google.com>
Date: Mon Dec 21 13:32:53 2015

check in direct quad length measure

Add code so that it at minimum won't bit-rot.
Next: add tests to see if it works.

R=reed@google.com
BUG=skia:1036
GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1541523002

Review URL: https://codereview.chromium.org/1541523002

[modify] http://crrev.com/17bc0851d34afe8c89d7455c061a1d419f76af8a/src/core/SkPathMeasure.cpp

Project Member

Comment 8 by caryclark@google.com, Jan 7 2016

Status: WontFix (was: Accepted)
The code fails for trivial (arguably degenerate) quads. For instance:

(0, 0) (0, 1) (0, 2)

computes

a = (0, 0)
A = 0
A_2 = 0
BA = NaN

This implies that quads close to straight lines will suffer a similar numerical fate.

This isn't worth pursing for shippable code.

Project Member

Comment 9 by reed@google.com, Jan 7 2016

Cc: -reed@google.com jvanverth@google.com herb@google.com caryclark@google.com
Owner: reed@google.com
Status: Accepted (was: WontFix)
Possibly, though we have to detect nearly straight quads even in our quadrootfinder, so perhaps this is no different:

- first see if its nearly straight
- if so, take a simpler case (length is trivial for this case)
- else do the tricky part, which hopefully won't compute degenerate values

I'd like us to spend a little time on this and investigate further
Project Member

Comment 10 by caryclark@google.com, Jan 12 2016

As Mike suggested, with some additional work, the code can handle the error cases.

By computing the current piecewise approach and the direct computation
approach described above for a quad of the form

  (0,0) (A,B) (C,D)

where A/B/C/D are random values +/-1000. , is

  {0, 0}, {780.426f, 746.948f}, {-433.807f, -417.938f}}

The (old) piecewise length is 1445.86
The (new) direct quad length is 1447.13

Drawing the quad, it nearly folds back on itself. The extrema as drawn is at (305.341, 291.826).
The length found by adding the length of two lines from end point to the extrema,
the empirical length is 1447.12

Next up is handling subdividing the quad when its length is nonlinear with respect to t.
Project Member

Comment 11 by caryclark@google.com, Feb 26 2016

Owner: caryclark@google.com
Project Member

Comment 12 by carycl...@skia.org, Mar 6 2018

Owner: ----

Sign in to add a comment