1 /* 2 http://stackoverflow.com/questions/2009160/how-do-i-convert-the-2-control-points-of-a-cubic-curve-to-the-single-control-poi 3 */ 4 5 /* 6 Let's call the control points of the cubic Q0..Q3 and the control points of the quadratic P0..P2. 7 Then for degree elevation, the equations are: 8 9 Q0 = P0 10 Q1 = 1/3 P0 + 2/3 P1 11 Q2 = 2/3 P1 + 1/3 P2 12 Q3 = P2 13 In your case you have Q0..Q3 and you're solving for P0..P2. There are two ways to compute P1 from 14 the equations above: 15 16 P1 = 3/2 Q1 - 1/2 Q0 17 P1 = 3/2 Q2 - 1/2 Q3 18 If this is a degree-elevated cubic, then both equations will give the same answer for P1. Since 19 it's likely not, your best bet is to average them. So, 20 21 P1 = -1/4 Q0 + 3/4 Q1 + 3/4 Q2 - 1/4 Q3 22 23 SkDCubic defined by: P1/2 - anchor points, C1/C2 control points 24 |x| is the euclidean norm of x 25 mid-point approx of cubic: a quad that shares the same anchors with the cubic and has the 26 control point at C = (3C2 - P2 + 3C1 - P1)/4 27 28 Algorithm 29 30 pick an absolute precision (prec) 31 Compute the Tdiv as the root of (cubic) equation 32 sqrt(3)/18 |P2 - 3C2 + 3C1 - P1|/2 Tdiv ^ 3 = prec 33 if Tdiv < 0.5 divide the cubic at Tdiv. First segment [0..Tdiv] can be approximated with by a 34 quadratic, with a defect less than prec, by the mid-point approximation. 35 Repeat from step 2 with the second resulted segment (corresponding to 1-Tdiv) 36 0.5<=Tdiv<1 - simply divide the cubic in two. The two halves can be approximated by the mid-point 37 approximation 38 Tdiv>=1 - the entire cubic can be approximated by the mid-point approximation 39 40 confirmed by (maybe stolen from) 41 http://www.caffeineowl.com/graphics/2d/vectorial/cubic2quad01.html 42 // maybe in turn derived from http://www.cccg.ca/proceedings/2004/36.pdf 43 // also stored at http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/bezier%20cccg04%20paper.pdf 44 45 */ 46 47 #include "SkPathOpsCubic.h" 48 #include "SkPathOpsLine.h" 49 #include "SkPathOpsQuad.h" 50 #include "SkReduceOrder.h" 51 #include "SkTArray.h" 52 #include "SkTSort.h" 53 54 #define USE_CUBIC_END_POINTS 1 55 56 static double calc_t_div(const SkDCubic& cubic, double precision, double start) { 57 const double adjust = sqrt(3.) / 36; 58 SkDCubic sub; 59 const SkDCubic* cPtr; 60 if (start == 0) { 61 cPtr = &cubic; 62 } else { 63 // OPTIMIZE: special-case half-split ? 64 sub = cubic.subDivide(start, 1); 65 cPtr = ⊂ 66 } 67 const SkDCubic& c = *cPtr; 68 double dx = c[3].fX - 3 * (c[2].fX - c[1].fX) - c[0].fX; 69 double dy = c[3].fY - 3 * (c[2].fY - c[1].fY) - c[0].fY; 70 double dist = sqrt(dx * dx + dy * dy); 71 double tDiv3 = precision / (adjust * dist); 72 double t = SkDCubeRoot(tDiv3); 73 if (start > 0) { 74 t = start + (1 - start) * t; 75 } 76 return t; 77 } 78 79 SkDQuad SkDCubic::toQuad() const { 80 SkDQuad quad; 81 quad[0] = fPts[0]; 82 const SkDPoint fromC1 = {(3 * fPts[1].fX - fPts[0].fX) / 2, (3 * fPts[1].fY - fPts[0].fY) / 2}; 83 const SkDPoint fromC2 = {(3 * fPts[2].fX - fPts[3].fX) / 2, (3 * fPts[2].fY - fPts[3].fY) / 2}; 84 quad[1].fX = (fromC1.fX + fromC2.fX) / 2; 85 quad[1].fY = (fromC1.fY + fromC2.fY) / 2; 86 quad[2] = fPts[3]; 87 return quad; 88 } 89 90 static bool add_simple_ts(const SkDCubic& cubic, double precision, SkTArray<double, true>* ts) { 91 double tDiv = calc_t_div(cubic, precision, 0); 92 if (tDiv >= 1) { 93 return true; 94 } 95 if (tDiv >= 0.5) { 96 ts->push_back(0.5); 97 return true; 98 } 99 return false; 100 } 101 102 static void addTs(const SkDCubic& cubic, double precision, double start, double end, 103 SkTArray<double, true>* ts) { 104 double tDiv = calc_t_div(cubic, precision, 0); 105 double parts = ceil(1.0 / tDiv); 106 for (double index = 0; index < parts; ++index) { 107 double newT = start + (index / parts) * (end - start); 108 if (newT > 0 && newT < 1) { 109 ts->push_back(newT); 110 } 111 } 112 } 113 114 // flavor that returns T values only, deferring computing the quads until they are needed 115 // FIXME: when called from recursive intersect 2, this could take the original cubic 116 // and do a more precise job when calling chop at and sub divide by computing the fractional ts. 117 // it would still take the prechopped cubic for reduce order and find cubic inflections 118 void SkDCubic::toQuadraticTs(double precision, SkTArray<double, true>* ts) const { 119 SkReduceOrder reducer; 120 int order = reducer.reduce(*this, SkReduceOrder::kAllow_Quadratics); 121 if (order < 3) { 122 return; 123 } 124 double inflectT[5]; 125 int inflections = findInflections(inflectT); 126 SkASSERT(inflections <= 2); 127 if (!endsAreExtremaInXOrY()) { 128 inflections += findMaxCurvature(&inflectT[inflections]); 129 SkASSERT(inflections <= 5); 130 } 131 SkTQSort<double>(inflectT, &inflectT[inflections - 1]); 132 // OPTIMIZATION: is this filtering common enough that it needs to be pulled out into its 133 // own subroutine? 134 while (inflections && approximately_less_than_zero(inflectT[0])) { 135 memmove(inflectT, &inflectT[1], sizeof(inflectT[0]) * --inflections); 136 } 137 int start = 0; 138 int next = 1; 139 while (next < inflections) { 140 if (!approximately_equal(inflectT[start], inflectT[next])) { 141 ++start; 142 ++next; 143 continue; 144 } 145 memmove(&inflectT[start], &inflectT[next], sizeof(inflectT[0]) * (--inflections - start)); 146 } 147 148 while (inflections && approximately_greater_than_one(inflectT[inflections - 1])) { 149 --inflections; 150 } 151 SkDCubicPair pair; 152 if (inflections == 1) { 153 pair = chopAt(inflectT[0]); 154 int orderP1 = reducer.reduce(pair.first(), SkReduceOrder::kNo_Quadratics); 155 if (orderP1 < 2) { 156 --inflections; 157 } else { 158 int orderP2 = reducer.reduce(pair.second(), SkReduceOrder::kNo_Quadratics); 159 if (orderP2 < 2) { 160 --inflections; 161 } 162 } 163 } 164 if (inflections == 0 && add_simple_ts(*this, precision, ts)) { 165 return; 166 } 167 if (inflections == 1) { 168 pair = chopAt(inflectT[0]); 169 addTs(pair.first(), precision, 0, inflectT[0], ts); 170 addTs(pair.second(), precision, inflectT[0], 1, ts); 171 return; 172 } 173 if (inflections > 1) { 174 SkDCubic part = subDivide(0, inflectT[0]); 175 addTs(part, precision, 0, inflectT[0], ts); 176 int last = inflections - 1; 177 for (int idx = 0; idx < last; ++idx) { 178 part = subDivide(inflectT[idx], inflectT[idx + 1]); 179 addTs(part, precision, inflectT[idx], inflectT[idx + 1], ts); 180 } 181 part = subDivide(inflectT[last], 1); 182 addTs(part, precision, inflectT[last], 1, ts); 183 return; 184 } 185 addTs(*this, precision, 0, 1, ts); 186 } 187
