SkOpAngle.cpp revision b76d3b677713693137936ff813b92c4be48af173
107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Copyright 2012 Google Inc. 307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * 407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * found in the LICENSE file. 607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkIntersections.h" 807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkOpAngle.h" 907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsCurve.h" 10b76d3b677713693137936ff813b92c4be48af173commit-bot@chromium.org#include "SkTSort.h" 1107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// FIXME: this is bogus for quads and cubics 1307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// if the quads and cubics' line from end pt to ctrl pt are coincident, 1407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// there's no obvious way to determine the curve ordering from the 1507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// derivatives alone. In particular, if one quadratic's coincident tangent 1607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// is longer than the other curve, the final control point can place the 1707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// longer curve on either side of the shorter one. 1807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf 1907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// may provide some help, but nothing has been figured out yet. 2007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/*( 2207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comfor quads and cubics, set up a parameterized line (e.g. LineParameters ) 2307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comfor points [0] to [1]. See if point [2] is on that line, or on one side 2407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comor the other. If it both quads' end points are on the same side, choose 2507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comthe shorter tangent. If the tangents are equal, choose the better second 2607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comtangent angle 2707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.commaybe I could set up LineParameters lazily 2907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com*/ 3007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.combool SkOpAngle::operator<(const SkOpAngle& rh) const { 3107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double y = dy(); 3207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double ry = rh.dy(); 3307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if ((y < 0) ^ (ry < 0)) { // OPTIMIZATION: better to use y * ry < 0 ? 3407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return y < 0; 3507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 3607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double x = dx(); 3707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double rx = rh.dx(); 3807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (y == 0 && ry == 0 && x * rx < 0) { 3907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return x < rx; 4007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 4107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double x_ry = x * ry; 4207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double rx_y = rx * y; 4307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double cmp = x_ry - rx_y; 4407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!approximately_zero(cmp)) { 4507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return cmp < 0; 4607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 4707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (approximately_zero(x_ry) && approximately_zero(rx_y) 4807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && !approximately_zero_squared(cmp)) { 4907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return cmp < 0; 5007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // at this point, the initial tangent line is coincident 5207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // see if edges curl away from each other 5307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (fSide * rh.fSide <= 0 && (!approximately_zero(fSide) 5407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com || !approximately_zero(rh.fSide))) { 5507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // FIXME: running demo will trigger this assertion 5607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // (don't know if commenting out will trigger further assertion or not) 5707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // commenting it out allows demo to run in release, though 5807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fSide < rh.fSide; 5907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // see if either curve can be lengthened and try the tangent compare again 610361032c0b53401030a720bc8b4930c3ec59f19ecaryclark@google.com if (/* cmp && */ (*fSpans)[fEnd].fOther != rh.fSegment // tangents not absolutely identical 6207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && (*rh.fSpans)[rh.fEnd].fOther != fSegment) { // and not intersecting 6307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpAngle longer = *this; 6407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkOpAngle rhLonger = rh; 6507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (longer.lengthen() | rhLonger.lengthen()) { 6607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return longer < rhLonger; 6707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if ((fVerb == SkPath::kLine_Verb && approximately_zero(x) && approximately_zero(y)) 7007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com || (rh.fVerb == SkPath::kLine_Verb 7107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && approximately_zero(rx) && approximately_zero(ry))) { 7207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // See general unsortable comment below. This case can happen when 7307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // one line has a non-zero change in t but no change in x and y. 7407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fUnsortable = true; 7507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com rh.fUnsortable = true; 7607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return this < &rh; // even with no solution, return a stable sort 7707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if ((*rh.fSpans)[SkMin32(rh.fStart, rh.fEnd)].fTiny 7907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com || (*fSpans)[SkMin32(fStart, fEnd)].fTiny) { 8007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fUnsortable = true; 8107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com rh.fUnsortable = true; 8207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return this < &rh; // even with no solution, return a stable sort 8307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 8407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(fVerb >= SkPath::kQuad_Verb); 8507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(rh.fVerb >= SkPath::kQuad_Verb); 8607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // FIXME: until I can think of something better, project a ray from the 8707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // end of the shorter tangent to midway between the end points 8807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // through both curves and use the resulting angle to sort 8907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive 9007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double len = fTangent1.normalSquared(); 9107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double rlen = rh.fTangent1.normalSquared(); 9207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDLine ray; 9307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkIntersections i, ri; 9407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int roots, rroots; 9507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool flip = false; 9607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 9707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool useThis = (len < rlen) ^ flip; 9807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const SkDCubic& part = useThis ? fCurvePart : rh.fCurvePart; 9907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkPath::Verb partVerb = useThis ? fVerb : rh.fVerb; 10007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ray[0] = partVerb == SkPath::kCubic_Verb && part[0].approximatelyEqual(part[1]) ? 10107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com part[2] : part[1]; 10207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ray[1].fX = (part[0].fX + part[partVerb].fX) / 2; 10307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ray[1].fY = (part[0].fY + part[partVerb].fY) / 2; 10407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(ray[0] != ray[1]); 10507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com roots = (i.*CurveRay[fVerb])(fPts, ray); 10607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com rroots = (ri.*CurveRay[rh.fVerb])(rh.fPts, ray); 10707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } while ((roots == 0 || rroots == 0) && (flip ^= true)); 10807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (roots == 0 || rroots == 0) { 10907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // FIXME: we don't have a solution in this case. The interim solution 11007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // is to mark the edges as unsortable, exclude them from this and 11107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // future computations, and allow the returned path to be fragmented 11207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fUnsortable = true; 11307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com rh.fUnsortable = true; 11407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return this < &rh; // even with no solution, return a stable sort 11507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 11607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDPoint loc; 11707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double best = SK_ScalarInfinity; 11807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDVector dxy; 11907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dist; 12007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int index; 12107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (index = 0; index < roots; ++index) { 12207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com loc = (*CurveDPointAtT[fVerb])(fPts, i[0][index]); 12307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com dxy = loc - ray[0]; 12407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com dist = dxy.lengthSquared(); 12507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (best > dist) { 12607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com best = dist; 12707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 12807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 12907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (index = 0; index < rroots; ++index) { 13007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com loc = (*CurveDPointAtT[rh.fVerb])(rh.fPts, ri[0][index]); 13107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com dxy = loc - ray[0]; 13207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com dist = dxy.lengthSquared(); 13307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (best > dist) { 13407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fSide < 0; 13507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 13607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 13707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fSide > 0; 13807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 13907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 14007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.combool SkOpAngle::lengthen() { 14107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int newEnd = fEnd; 14207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (fStart < fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) { 14307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fEnd = newEnd; 14407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com setSpans(); 14507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return true; 14607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 14707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return false; 14807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 14907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 15007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.combool SkOpAngle::reverseLengthen() { 15107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (fReversed) { 15207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return false; 15307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 15407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int newEnd = fStart; 15507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (fStart > fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) { 15607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fEnd = newEnd; 15707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fReversed = true; 15807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com setSpans(); 15907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return true; 16007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 16107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return false; 16207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 16307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 16407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comvoid SkOpAngle::set(const SkPoint* orig, SkPath::Verb verb, const SkOpSegment* segment, 16507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int start, int end, const SkTDArray<SkOpSpan>& spans) { 16607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fSegment = segment; 16707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fStart = start; 16807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fEnd = end; 16907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fPts = orig; 17007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fVerb = verb; 17107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fSpans = &spans; 17207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fReversed = false; 17307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fUnsortable = false; 17407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com setSpans(); 17507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 17607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 17707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 17807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comvoid SkOpAngle::setSpans() { 17907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double startT = (*fSpans)[fStart].fT; 18007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double endT = (*fSpans)[fEnd].fT; 18107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com switch (fVerb) { 18207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com case SkPath::kLine_Verb: { 18307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDLine l = SkDLine::SubDivide(fPts, startT, endT); 18407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // OPTIMIZATION: for pure line compares, we never need fTangent1.c 18507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fTangent1.lineEndPoints(l); 18607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fSide = 0; 18707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } break; 18807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com case SkPath::kQuad_Verb: { 18907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDQuad& quad = *SkTCast<SkDQuad*>(&fCurvePart); 19007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com quad = SkDQuad::SubDivide(fPts, startT, endT); 19107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fTangent1.quadEndPoints(quad, 0, 1); 19207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (dx() == 0 && dy() == 0) { 19307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fTangent1.quadEndPoints(quad); 19407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 19507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fSide = -fTangent1.pointDistance(fCurvePart[2]); // not normalized -- compare sign only 19607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } break; 19707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com case SkPath::kCubic_Verb: { 198b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com // int nextC = 2; 19907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fCurvePart = SkDCubic::SubDivide(fPts, startT, endT); 20007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fTangent1.cubicEndPoints(fCurvePart, 0, 1); 20107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (dx() == 0 && dy() == 0) { 20207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fTangent1.cubicEndPoints(fCurvePart, 0, 2); 203b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com // nextC = 3; 20407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (dx() == 0 && dy() == 0) { 20507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fTangent1.cubicEndPoints(fCurvePart, 0, 3); 20607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 20707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 208b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com // fSide = -fTangent1.pointDistance(fCurvePart[nextC]); // compare sign only 209b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com // if (nextC == 2 && approximately_zero(fSide)) { 210b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com // fSide = -fTangent1.pointDistance(fCurvePart[3]); 211b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com // } 212b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com double testTs[4]; 213b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com // OPTIMIZATION: keep inflections precomputed with cubic segment? 214b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com int testCount = SkDCubic::FindInflections(fPts, testTs); 215b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com double limitT = endT; 216b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com int index; 217b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com for (index = 0; index < testCount; ++index) { 218b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com if (!between(startT, testTs[index], limitT)) { 219b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com testTs[index] = -1; 220b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com } 221b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com } 222b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com testTs[testCount++] = startT; 223b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com testTs[testCount++] = endT; 224b76d3b677713693137936ff813b92c4be48af173commit-bot@chromium.org SkTQSort<double>(testTs, &testTs[testCount - 1]); 225b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com double bestSide = 0; 226b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com int testCases = (testCount << 1) - 1; 227b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com index = 0; 228b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com while (testTs[index] < 0) { 229b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com ++index; 230b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com } 231b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com index <<= 1; 232b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com for (; index < testCases; ++index) { 233b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com int testIndex = index >> 1; 234b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com double testT = testTs[testIndex]; 235b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com if (index & 1) { 236b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com testT = (testT + testTs[testIndex + 1]) / 2; 237b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com } 238b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com // OPTIMIZE: could avoid call for t == startT, endT 239b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com SkDPoint pt = dcubic_xy_at_t(fPts, testT); 240b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com double testSide = fTangent1.pointDistance(pt); 241b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com if (fabs(bestSide) < fabs(testSide)) { 242b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com bestSide = testSide; 243b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com } 24407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 245b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com fSide = -bestSide; // compare sign only 24607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } break; 24707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com default: 24807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(0); 24907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 25007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fUnsortable = dx() == 0 && dy() == 0; 25107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (fUnsortable) { 25207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return; 25307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 25407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(fStart != fEnd); 25507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int step = fStart < fEnd ? 1 : -1; // OPTIMIZE: worth fStart - fEnd >> 31 type macro? 25607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int index = fStart; index != fEnd; index += step) { 25707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if 1 25807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const SkOpSpan& thisSpan = (*fSpans)[index]; 25907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const SkOpSpan& nextSpan = (*fSpans)[index + step]; 26007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (thisSpan.fTiny || precisely_equal(thisSpan.fT, nextSpan.fT)) { 26107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 26207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 26307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fUnsortable = step > 0 ? thisSpan.fUnsortableStart : nextSpan.fUnsortableEnd; 26407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_UNSORTABLE 26507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (fUnsortable) { 26607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkPoint iPt = (*CurvePointAtT[fVerb])(fPts, thisSpan.fT); 26707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkPoint ePt = (*CurvePointAtT[fVerb])(fPts, nextSpan.fT); 26807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, 26907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com index, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); 27007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 27107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 27207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return; 27307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#else 27407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if ((*fSpans)[index].fUnsortableStart) { 27507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fUnsortable = true; 27607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return; 27707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 27807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 27907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 28007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if 1 28107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_UNSORTABLE 28207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkPoint iPt = (*CurvePointAtT[fVerb])(fPts, startT); 28307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkPoint ePt = (*CurvePointAtT[fVerb])(fPts, endT); 28407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, 28507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); 28607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 28707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fUnsortable = true; 28807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 28907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 290