diff options
author | caryclark <caryclark@google.com> | 2015-03-24 07:28:17 -0700 |
---|---|---|
committer | Commit bot <commit-bot@chromium.org> | 2015-03-24 07:28:17 -0700 |
commit | ccec0f958ffc71a9986d236bc2eb335cb2111119 (patch) | |
tree | f864209e3594293256ac391715d50222ff22d96b /src/pathops/SkDCubicToQuads.cpp | |
parent | 62a320c8d444cd04e4f2952c269ea4cbd58dee64 (diff) |
pathops version two
R=reed@google.com
marked 'no commit' to attempt to get trybots to run
TBR=reed@google.com
Review URL: https://codereview.chromium.org/1002693002
Diffstat (limited to 'src/pathops/SkDCubicToQuads.cpp')
-rw-r--r-- | src/pathops/SkDCubicToQuads.cpp | 150 |
1 files changed, 0 insertions, 150 deletions
diff --git a/src/pathops/SkDCubicToQuads.cpp b/src/pathops/SkDCubicToQuads.cpp index a28564d4c2..2d034b69e8 100644 --- a/src/pathops/SkDCubicToQuads.cpp +++ b/src/pathops/SkDCubicToQuads.cpp @@ -19,62 +19,10 @@ If this is a degree-elevated cubic, then both equations will give the same answe it's likely not, your best bet is to average them. So, P1 = -1/4 Q0 + 3/4 Q1 + 3/4 Q2 - 1/4 Q3 - -SkDCubic defined by: P1/2 - anchor points, C1/C2 control points -|x| is the euclidean norm of x -mid-point approx of cubic: a quad that shares the same anchors with the cubic and has the - control point at C = (3·C2 - P2 + 3·C1 - P1)/4 - -Algorithm - -pick an absolute precision (prec) -Compute the Tdiv as the root of (cubic) equation -sqrt(3)/18 · |P2 - 3·C2 + 3·C1 - P1|/2 · Tdiv ^ 3 = prec -if Tdiv < 0.5 divide the cubic at Tdiv. First segment [0..Tdiv] can be approximated with by a - quadratic, with a defect less than prec, by the mid-point approximation. - Repeat from step 2 with the second resulted segment (corresponding to 1-Tdiv) -0.5<=Tdiv<1 - simply divide the cubic in two. The two halves can be approximated by the mid-point - approximation -Tdiv>=1 - the entire cubic can be approximated by the mid-point approximation - -confirmed by (maybe stolen from) -http://www.caffeineowl.com/graphics/2d/vectorial/cubic2quad01.html -// maybe in turn derived from http://www.cccg.ca/proceedings/2004/36.pdf -// also stored at http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/bezier%20cccg04%20paper.pdf - */ #include "SkPathOpsCubic.h" -#include "SkPathOpsLine.h" #include "SkPathOpsQuad.h" -#include "SkReduceOrder.h" -#include "SkTArray.h" -#include "SkTSort.h" - -#define USE_CUBIC_END_POINTS 1 - -static double calc_t_div(const SkDCubic& cubic, double precision, double start) { - const double adjust = sqrt(3.) / 36; - SkDCubic sub; - const SkDCubic* cPtr; - if (start == 0) { - cPtr = &cubic; - } else { - // OPTIMIZE: special-case half-split ? - sub = cubic.subDivide(start, 1); - cPtr = ⊂ - } - const SkDCubic& c = *cPtr; - double dx = c[3].fX - 3 * (c[2].fX - c[1].fX) - c[0].fX; - double dy = c[3].fY - 3 * (c[2].fY - c[1].fY) - c[0].fY; - double dist = sqrt(dx * dx + dy * dy); - double tDiv3 = precision / (adjust * dist); - double t = SkDCubeRoot(tDiv3); - if (start > 0) { - t = start + (1 - start) * t; - } - return t; -} SkDQuad SkDCubic::toQuad() const { SkDQuad quad; @@ -86,101 +34,3 @@ SkDQuad SkDCubic::toQuad() const { quad[2] = fPts[3]; return quad; } - -static bool add_simple_ts(const SkDCubic& cubic, double precision, SkTArray<double, true>* ts) { - double tDiv = calc_t_div(cubic, precision, 0); - if (tDiv >= 1) { - return true; - } - if (tDiv >= 0.5) { - ts->push_back(0.5); - return true; - } - return false; -} - -static void addTs(const SkDCubic& cubic, double precision, double start, double end, - SkTArray<double, true>* ts) { - double tDiv = calc_t_div(cubic, precision, 0); - double parts = ceil(1.0 / tDiv); - for (double index = 0; index < parts; ++index) { - double newT = start + (index / parts) * (end - start); - if (newT > 0 && newT < 1) { - ts->push_back(newT); - } - } -} - -// flavor that returns T values only, deferring computing the quads until they are needed -// FIXME: when called from recursive intersect 2, this could take the original cubic -// and do a more precise job when calling chop at and sub divide by computing the fractional ts. -// it would still take the prechopped cubic for reduce order and find cubic inflections -void SkDCubic::toQuadraticTs(double precision, SkTArray<double, true>* ts) const { - SkReduceOrder reducer; - int order = reducer.reduce(*this, SkReduceOrder::kAllow_Quadratics); - if (order < 3) { - return; - } - double inflectT[5]; - int inflections = findInflections(inflectT); - SkASSERT(inflections <= 2); - if (!endsAreExtremaInXOrY()) { - inflections += findMaxCurvature(&inflectT[inflections]); - SkASSERT(inflections <= 5); - } - SkTQSort<double>(inflectT, &inflectT[inflections - 1]); - // OPTIMIZATION: is this filtering common enough that it needs to be pulled out into its - // own subroutine? - while (inflections && approximately_less_than_zero(inflectT[0])) { - memmove(inflectT, &inflectT[1], sizeof(inflectT[0]) * --inflections); - } - int start = 0; - int next = 1; - while (next < inflections) { - if (!approximately_equal(inflectT[start], inflectT[next])) { - ++start; - ++next; - continue; - } - memmove(&inflectT[start], &inflectT[next], sizeof(inflectT[0]) * (--inflections - start)); - } - - while (inflections && approximately_greater_than_one(inflectT[inflections - 1])) { - --inflections; - } - SkDCubicPair pair; - if (inflections == 1) { - pair = chopAt(inflectT[0]); - int orderP1 = reducer.reduce(pair.first(), SkReduceOrder::kNo_Quadratics); - if (orderP1 < 2) { - --inflections; - } else { - int orderP2 = reducer.reduce(pair.second(), SkReduceOrder::kNo_Quadratics); - if (orderP2 < 2) { - --inflections; - } - } - } - if (inflections == 0 && add_simple_ts(*this, precision, ts)) { - return; - } - if (inflections == 1) { - pair = chopAt(inflectT[0]); - addTs(pair.first(), precision, 0, inflectT[0], ts); - addTs(pair.second(), precision, inflectT[0], 1, ts); - return; - } - if (inflections > 1) { - SkDCubic part = subDivide(0, inflectT[0]); - addTs(part, precision, 0, inflectT[0], ts); - int last = inflections - 1; - for (int idx = 0; idx < last; ++idx) { - part = subDivide(inflectT[idx], inflectT[idx + 1]); - addTs(part, precision, inflectT[idx], inflectT[idx + 1], ts); - } - part = subDivide(inflectT[last], 1); - addTs(part, precision, inflectT[last], 1, ts); - return; - } - addTs(*this, precision, 0, 1, ts); -} |