107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comhttp://stackoverflow.com/questions/2009160/how-do-i-convert-the-2-control-points-of-a-cubic-curve-to-the-single-control-poi 307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com*/ 407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comLet's call the control points of the cubic Q0..Q3 and the control points of the quadratic P0..P2. 707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comThen for degree elevation, the equations are: 807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comQ0 = P0 1007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comQ1 = 1/3 P0 + 2/3 P1 1107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comQ2 = 2/3 P1 + 1/3 P2 1207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comQ3 = P2 1307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comIn your case you have Q0..Q3 and you're solving for P0..P2. There are two ways to compute P1 from 1407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com the equations above: 1507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comP1 = 3/2 Q1 - 1/2 Q0 1707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comP1 = 3/2 Q2 - 1/2 Q3 1807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comIf this is a degree-elevated cubic, then both equations will give the same answer for P1. Since 1907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com it's likely not, your best bet is to average them. So, 2007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comP1 = -1/4 Q0 + 3/4 Q1 + 3/4 Q2 - 1/4 Q3 2207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comSkDCubic defined by: P1/2 - anchor points, C1/C2 control points 2407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com|x| is the euclidean norm of x 2507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.commid-point approx of cubic: a quad that shares the same anchors with the cubic and has the 2607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com control point at C = (3·C2 - P2 + 3·C1 - P1)/4 2707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comAlgorithm 2907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 3007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.compick an absolute precision (prec) 3107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comCompute the Tdiv as the root of (cubic) equation 3207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comsqrt(3)/18 · |P2 - 3·C2 + 3·C1 - P1|/2 · Tdiv ^ 3 = prec 3307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comif Tdiv < 0.5 divide the cubic at Tdiv. First segment [0..Tdiv] can be approximated with by a 3407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com quadratic, with a defect less than prec, by the mid-point approximation. 3507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Repeat from step 2 with the second resulted segment (corresponding to 1-Tdiv) 3607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com0.5<=Tdiv<1 - simply divide the cubic in two. The two halves can be approximated by the mid-point 3707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com approximation 3807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comTdiv>=1 - the entire cubic can be approximated by the mid-point approximation 3907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 4007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comconfirmed by (maybe stolen from) 4107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comhttp://www.caffeineowl.com/graphics/2d/vectorial/cubic2quad01.html 4207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// maybe in turn derived from http://www.cccg.ca/proceedings/2004/36.pdf 4307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// also stored at http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/bezier%20cccg04%20paper.pdf 4407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 4507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com*/ 4607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 4707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsCubic.h" 4807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsLine.h" 4907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsQuad.h" 5007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkReduceOrder.h" 51d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com#include "SkTArray.h" 52b76d3b677713693137936ff813b92c4be48af173commit-bot@chromium.org#include "SkTSort.h" 5307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 5407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#define USE_CUBIC_END_POINTS 1 5507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 5607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic double calc_t_div(const SkDCubic& cubic, double precision, double start) { 5707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double adjust = sqrt(3.) / 36; 5807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDCubic sub; 5907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const SkDCubic* cPtr; 6007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (start == 0) { 6107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com cPtr = &cubic; 6207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 6307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // OPTIMIZE: special-case half-split ? 6407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com sub = cubic.subDivide(start, 1); 6507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com cPtr = ⊂ 6607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const SkDCubic& c = *cPtr; 6807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dx = c[3].fX - 3 * (c[2].fX - c[1].fX) - c[0].fX; 6907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dy = c[3].fY - 3 * (c[2].fY - c[1].fY) - c[0].fY; 7007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dist = sqrt(dx * dx + dy * dy); 7107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double tDiv3 = precision / (adjust * dist); 7207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double t = SkDCubeRoot(tDiv3); 7307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (start > 0) { 7407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t = start + (1 - start) * t; 7507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return t; 7707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 7807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 7907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comSkDQuad SkDCubic::toQuad() const { 8007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDQuad quad; 8107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com quad[0] = fPts[0]; 8207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const SkDPoint fromC1 = {(3 * fPts[1].fX - fPts[0].fX) / 2, (3 * fPts[1].fY - fPts[0].fY) / 2}; 8307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const SkDPoint fromC2 = {(3 * fPts[2].fX - fPts[3].fX) / 2, (3 * fPts[2].fY - fPts[3].fY) / 2}; 8407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com quad[1].fX = (fromC1.fX + fromC2.fX) / 2; 8507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com quad[1].fY = (fromC1.fY + fromC2.fY) / 2; 8607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com quad[2] = fPts[3]; 8707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return quad; 8807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 8907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 90d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.comstatic bool add_simple_ts(const SkDCubic& cubic, double precision, SkTArray<double, true>* ts) { 9107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double tDiv = calc_t_div(cubic, precision, 0); 9207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (tDiv >= 1) { 9307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return true; 9407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 9507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (tDiv >= 0.5) { 96d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com ts->push_back(0.5); 9707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return true; 9807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 9907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return false; 10007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 10107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 10207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic void addTs(const SkDCubic& cubic, double precision, double start, double end, 103d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com SkTArray<double, true>* ts) { 10407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double tDiv = calc_t_div(cubic, precision, 0); 10507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double parts = ceil(1.0 / tDiv); 10607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (double index = 0; index < parts; ++index) { 10707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double newT = start + (index / parts) * (end - start); 10807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (newT > 0 && newT < 1) { 109d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com ts->push_back(newT); 11007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 11107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 11207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 11307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 11407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// flavor that returns T values only, deferring computing the quads until they are needed 11507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// FIXME: when called from recursive intersect 2, this could take the original cubic 11607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// and do a more precise job when calling chop at and sub divide by computing the fractional ts. 11707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// it would still take the prechopped cubic for reduce order and find cubic inflections 118d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.comvoid SkDCubic::toQuadraticTs(double precision, SkTArray<double, true>* ts) const { 11907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkReduceOrder reducer; 120927b7028d44c46e9cbc18368f16ec2262d59d94dcaryclark@google.com int order = reducer.reduce(*this, SkReduceOrder::kAllow_Quadratics); 12107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (order < 3) { 12207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return; 12307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 12407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double inflectT[5]; 12507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int inflections = findInflections(inflectT); 12607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(inflections <= 2); 12707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!endsAreExtremaInXOrY()) { 12807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com inflections += findMaxCurvature(&inflectT[inflections]); 12907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(inflections <= 5); 13007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 131b76d3b677713693137936ff813b92c4be48af173commit-bot@chromium.org SkTQSort<double>(inflectT, &inflectT[inflections - 1]); 13207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // OPTIMIZATION: is this filtering common enough that it needs to be pulled out into its 13307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // own subroutine? 13407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com while (inflections && approximately_less_than_zero(inflectT[0])) { 13507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com memmove(inflectT, &inflectT[1], sizeof(inflectT[0]) * --inflections); 13607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 13707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int start = 0; 1387911ade991336adab70a99f50fbe9dc5ef79d0a0skia.committer@gmail.com int next = 1; 139197fea2d1810874d76f5c1046b4713db5676e958commit-bot@chromium.org while (next < inflections) { 14007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!approximately_equal(inflectT[start], inflectT[next])) { 14107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ++start; 1427911ade991336adab70a99f50fbe9dc5ef79d0a0skia.committer@gmail.com ++next; 14307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 14407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 14507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com memmove(&inflectT[start], &inflectT[next], sizeof(inflectT[0]) * (--inflections - start)); 146197fea2d1810874d76f5c1046b4713db5676e958commit-bot@chromium.org } 147197fea2d1810874d76f5c1046b4713db5676e958commit-bot@chromium.org 14807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com while (inflections && approximately_greater_than_one(inflectT[inflections - 1])) { 14907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com --inflections; 15007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 15107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDCubicPair pair; 15207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (inflections == 1) { 15307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com pair = chopAt(inflectT[0]); 154927b7028d44c46e9cbc18368f16ec2262d59d94dcaryclark@google.com int orderP1 = reducer.reduce(pair.first(), SkReduceOrder::kNo_Quadratics); 15507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (orderP1 < 2) { 15607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com --inflections; 15707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 158927b7028d44c46e9cbc18368f16ec2262d59d94dcaryclark@google.com int orderP2 = reducer.reduce(pair.second(), SkReduceOrder::kNo_Quadratics); 15907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (orderP2 < 2) { 16007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com --inflections; 16107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 16207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 16307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 16407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (inflections == 0 && add_simple_ts(*this, precision, ts)) { 16507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return; 16607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 16707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (inflections == 1) { 16807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com pair = chopAt(inflectT[0]); 16907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com addTs(pair.first(), precision, 0, inflectT[0], ts); 17007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com addTs(pair.second(), precision, inflectT[0], 1, ts); 17107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return; 17207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 17307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (inflections > 1) { 17407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDCubic part = subDivide(0, inflectT[0]); 17507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com addTs(part, precision, 0, inflectT[0], ts); 17607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int last = inflections - 1; 17707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int idx = 0; idx < last; ++idx) { 17807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com part = subDivide(inflectT[idx], inflectT[idx + 1]); 17907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com addTs(part, precision, inflectT[idx], inflectT[idx + 1], ts); 18007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 18107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com part = subDivide(inflectT[last], 1); 18207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com addTs(part, precision, inflectT[last], 1, ts); 18307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return; 18407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 18507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com addTs(*this, precision, 0, 1, ts); 18607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 187