SkDCubicToQuads.cpp revision 07393cab57ce74a4aae89a31fae9aaa9780fc19d
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.com 2407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comSkDCubic defined by: P1/2 - anchor points, C1/C2 control points 2507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com|x| is the euclidean norm of x 2607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.commid-point approx of cubic: a quad that shares the same anchors with the cubic and has the 2707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com control point at C = (3·C2 - P2 + 3·C1 - P1)/4 2807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comAlgorithm 3007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 3107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.compick an absolute precision (prec) 3207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comCompute the Tdiv as the root of (cubic) equation 3307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comsqrt(3)/18 · |P2 - 3·C2 + 3·C1 - P1|/2 · Tdiv ^ 3 = prec 3407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comif Tdiv < 0.5 divide the cubic at Tdiv. First segment [0..Tdiv] can be approximated with by a 3507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com quadratic, with a defect less than prec, by the mid-point approximation. 3607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Repeat from step 2 with the second resulted segment (corresponding to 1-Tdiv) 3707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com0.5<=Tdiv<1 - simply divide the cubic in two. The two halves can be approximated by the mid-point 3807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com approximation 3907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comTdiv>=1 - the entire cubic can be approximated by the mid-point approximation 4007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 4107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comconfirmed by (maybe stolen from) 4207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comhttp://www.caffeineowl.com/graphics/2d/vectorial/cubic2quad01.html 4307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// maybe in turn derived from http://www.cccg.ca/proceedings/2004/36.pdf 4407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// also stored at http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/bezier%20cccg04%20paper.pdf 4507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 4607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com*/ 4707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 4807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsCubic.h" 4907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsLine.h" 5007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsQuad.h" 5107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkReduceOrder.h" 5207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkTDArray.h" 5307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "TSearch.h" 5407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 5507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#define USE_CUBIC_END_POINTS 1 5607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 5707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic double calc_t_div(const SkDCubic& cubic, double precision, double start) { 5807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double adjust = sqrt(3.) / 36; 5907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDCubic sub; 6007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const SkDCubic* cPtr; 6107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (start == 0) { 6207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com cPtr = &cubic; 6307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 6407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // OPTIMIZE: special-case half-split ? 6507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com sub = cubic.subDivide(start, 1); 6607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com cPtr = ⊂ 6707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const SkDCubic& c = *cPtr; 6907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dx = c[3].fX - 3 * (c[2].fX - c[1].fX) - c[0].fX; 7007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dy = c[3].fY - 3 * (c[2].fY - c[1].fY) - c[0].fY; 7107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dist = sqrt(dx * dx + dy * dy); 7207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double tDiv3 = precision / (adjust * dist); 7307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double t = SkDCubeRoot(tDiv3); 7407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (start > 0) { 7507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t = start + (1 - start) * t; 7607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return t; 7807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 7907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 8007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comSkDQuad SkDCubic::toQuad() const { 8107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDQuad quad; 8207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com quad[0] = fPts[0]; 8307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const SkDPoint fromC1 = {(3 * fPts[1].fX - fPts[0].fX) / 2, (3 * fPts[1].fY - fPts[0].fY) / 2}; 8407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const SkDPoint fromC2 = {(3 * fPts[2].fX - fPts[3].fX) / 2, (3 * fPts[2].fY - fPts[3].fY) / 2}; 8507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com quad[1].fX = (fromC1.fX + fromC2.fX) / 2; 8607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com quad[1].fY = (fromC1.fY + fromC2.fY) / 2; 8707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com quad[2] = fPts[3]; 8807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return quad; 8907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 9007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 9107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic bool add_simple_ts(const SkDCubic& cubic, double precision, SkTDArray<double>* ts) { 9207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double tDiv = calc_t_div(cubic, precision, 0); 9307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (tDiv >= 1) { 9407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return true; 9507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 9607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (tDiv >= 0.5) { 9707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *ts->append() = 0.5; 9807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return true; 9907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 10007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return false; 10107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 10207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 10307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic void addTs(const SkDCubic& cubic, double precision, double start, double end, 10407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkTDArray<double>* ts) { 10507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double tDiv = calc_t_div(cubic, precision, 0); 10607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double parts = ceil(1.0 / tDiv); 10707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (double index = 0; index < parts; ++index) { 10807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double newT = start + (index / parts) * (end - start); 10907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (newT > 0 && newT < 1) { 11007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *ts->append() = newT; 11107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 11207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 11307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 11407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 11507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// flavor that returns T values only, deferring computing the quads until they are needed 11607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// FIXME: when called from recursive intersect 2, this could take the original cubic 11707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// and do a more precise job when calling chop at and sub divide by computing the fractional ts. 11807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// it would still take the prechopped cubic for reduce order and find cubic inflections 11907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comvoid SkDCubic::toQuadraticTs(double precision, SkTDArray<double>* ts) const { 12007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkReduceOrder reducer; 12107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int order = reducer.reduce(*this, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style); 12207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (order < 3) { 12307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return; 12407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 12507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double inflectT[5]; 12607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int inflections = findInflections(inflectT); 12707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(inflections <= 2); 12807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!endsAreExtremaInXOrY()) { 12907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com inflections += findMaxCurvature(&inflectT[inflections]); 13007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(inflections <= 5); 13107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 13207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com QSort<double>(inflectT, &inflectT[inflections - 1]); 13307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // OPTIMIZATION: is this filtering common enough that it needs to be pulled out into its 13407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // own subroutine? 13507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com while (inflections && approximately_less_than_zero(inflectT[0])) { 13607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com memmove(inflectT, &inflectT[1], sizeof(inflectT[0]) * --inflections); 13707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 13807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int start = 0; 13907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 14007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int next = start + 1; 14107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (next >= inflections) { 14207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com break; 14307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 14407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!approximately_equal(inflectT[start], inflectT[next])) { 14507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ++start; 14607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 14707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 14807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com memmove(&inflectT[start], &inflectT[next], sizeof(inflectT[0]) * (--inflections - start)); 14907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } while (true); 15007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com while (inflections && approximately_greater_than_one(inflectT[inflections - 1])) { 15107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com --inflections; 15207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 15307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDCubicPair pair; 15407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (inflections == 1) { 15507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com pair = chopAt(inflectT[0]); 15607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int orderP1 = reducer.reduce(pair.first(), SkReduceOrder::kNo_Quadratics, 15707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkReduceOrder::kFill_Style); 15807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (orderP1 < 2) { 15907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com --inflections; 16007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 16107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int orderP2 = reducer.reduce(pair.second(), SkReduceOrder::kNo_Quadratics, 16207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkReduceOrder::kFill_Style); 16307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (orderP2 < 2) { 16407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com --inflections; 16507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 16607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 16707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 16807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (inflections == 0 && add_simple_ts(*this, precision, ts)) { 16907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return; 17007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 17107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (inflections == 1) { 17207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com pair = chopAt(inflectT[0]); 17307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com addTs(pair.first(), precision, 0, inflectT[0], ts); 17407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com addTs(pair.second(), precision, inflectT[0], 1, ts); 17507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return; 17607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 17707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (inflections > 1) { 17807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDCubic part = subDivide(0, inflectT[0]); 17907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com addTs(part, precision, 0, inflectT[0], ts); 18007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int last = inflections - 1; 18107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int idx = 0; idx < last; ++idx) { 18207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com part = subDivide(inflectT[idx], inflectT[idx + 1]); 18307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com addTs(part, precision, inflectT[idx], inflectT[idx + 1], ts); 18407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 18507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com part = subDivide(inflectT[last], 1); 18607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com addTs(part, precision, inflectT[last], 1, ts); 18707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return; 18807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 18907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com addTs(*this, precision, 0, 1, ts); 19007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 191