1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/pathops/SkDCubicToQuads.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,187 @@
1.4 +/*
1.5 +http://stackoverflow.com/questions/2009160/how-do-i-convert-the-2-control-points-of-a-cubic-curve-to-the-single-control-poi
1.6 +*/
1.7 +
1.8 +/*
1.9 +Let's call the control points of the cubic Q0..Q3 and the control points of the quadratic P0..P2.
1.10 +Then for degree elevation, the equations are:
1.11 +
1.12 +Q0 = P0
1.13 +Q1 = 1/3 P0 + 2/3 P1
1.14 +Q2 = 2/3 P1 + 1/3 P2
1.15 +Q3 = P2
1.16 +In your case you have Q0..Q3 and you're solving for P0..P2. There are two ways to compute P1 from
1.17 + the equations above:
1.18 +
1.19 +P1 = 3/2 Q1 - 1/2 Q0
1.20 +P1 = 3/2 Q2 - 1/2 Q3
1.21 +If this is a degree-elevated cubic, then both equations will give the same answer for P1. Since
1.22 + it's likely not, your best bet is to average them. So,
1.23 +
1.24 +P1 = -1/4 Q0 + 3/4 Q1 + 3/4 Q2 - 1/4 Q3
1.25 +
1.26 +
1.27 +SkDCubic defined by: P1/2 - anchor points, C1/C2 control points
1.28 +|x| is the euclidean norm of x
1.29 +mid-point approx of cubic: a quad that shares the same anchors with the cubic and has the
1.30 + control point at C = (3·C2 - P2 + 3·C1 - P1)/4
1.31 +
1.32 +Algorithm
1.33 +
1.34 +pick an absolute precision (prec)
1.35 +Compute the Tdiv as the root of (cubic) equation
1.36 +sqrt(3)/18 · |P2 - 3·C2 + 3·C1 - P1|/2 · Tdiv ^ 3 = prec
1.37 +if Tdiv < 0.5 divide the cubic at Tdiv. First segment [0..Tdiv] can be approximated with by a
1.38 + quadratic, with a defect less than prec, by the mid-point approximation.
1.39 + Repeat from step 2 with the second resulted segment (corresponding to 1-Tdiv)
1.40 +0.5<=Tdiv<1 - simply divide the cubic in two. The two halves can be approximated by the mid-point
1.41 + approximation
1.42 +Tdiv>=1 - the entire cubic can be approximated by the mid-point approximation
1.43 +
1.44 +confirmed by (maybe stolen from)
1.45 +http://www.caffeineowl.com/graphics/2d/vectorial/cubic2quad01.html
1.46 +// maybe in turn derived from http://www.cccg.ca/proceedings/2004/36.pdf
1.47 +// also stored at http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/bezier%20cccg04%20paper.pdf
1.48 +
1.49 +*/
1.50 +
1.51 +#include "SkPathOpsCubic.h"
1.52 +#include "SkPathOpsLine.h"
1.53 +#include "SkPathOpsQuad.h"
1.54 +#include "SkReduceOrder.h"
1.55 +#include "SkTArray.h"
1.56 +#include "SkTSort.h"
1.57 +
1.58 +#define USE_CUBIC_END_POINTS 1
1.59 +
1.60 +static double calc_t_div(const SkDCubic& cubic, double precision, double start) {
1.61 + const double adjust = sqrt(3.) / 36;
1.62 + SkDCubic sub;
1.63 + const SkDCubic* cPtr;
1.64 + if (start == 0) {
1.65 + cPtr = &cubic;
1.66 + } else {
1.67 + // OPTIMIZE: special-case half-split ?
1.68 + sub = cubic.subDivide(start, 1);
1.69 + cPtr = ⊂
1.70 + }
1.71 + const SkDCubic& c = *cPtr;
1.72 + double dx = c[3].fX - 3 * (c[2].fX - c[1].fX) - c[0].fX;
1.73 + double dy = c[3].fY - 3 * (c[2].fY - c[1].fY) - c[0].fY;
1.74 + double dist = sqrt(dx * dx + dy * dy);
1.75 + double tDiv3 = precision / (adjust * dist);
1.76 + double t = SkDCubeRoot(tDiv3);
1.77 + if (start > 0) {
1.78 + t = start + (1 - start) * t;
1.79 + }
1.80 + return t;
1.81 +}
1.82 +
1.83 +SkDQuad SkDCubic::toQuad() const {
1.84 + SkDQuad quad;
1.85 + quad[0] = fPts[0];
1.86 + const SkDPoint fromC1 = {(3 * fPts[1].fX - fPts[0].fX) / 2, (3 * fPts[1].fY - fPts[0].fY) / 2};
1.87 + const SkDPoint fromC2 = {(3 * fPts[2].fX - fPts[3].fX) / 2, (3 * fPts[2].fY - fPts[3].fY) / 2};
1.88 + quad[1].fX = (fromC1.fX + fromC2.fX) / 2;
1.89 + quad[1].fY = (fromC1.fY + fromC2.fY) / 2;
1.90 + quad[2] = fPts[3];
1.91 + return quad;
1.92 +}
1.93 +
1.94 +static bool add_simple_ts(const SkDCubic& cubic, double precision, SkTArray<double, true>* ts) {
1.95 + double tDiv = calc_t_div(cubic, precision, 0);
1.96 + if (tDiv >= 1) {
1.97 + return true;
1.98 + }
1.99 + if (tDiv >= 0.5) {
1.100 + ts->push_back(0.5);
1.101 + return true;
1.102 + }
1.103 + return false;
1.104 +}
1.105 +
1.106 +static void addTs(const SkDCubic& cubic, double precision, double start, double end,
1.107 + SkTArray<double, true>* ts) {
1.108 + double tDiv = calc_t_div(cubic, precision, 0);
1.109 + double parts = ceil(1.0 / tDiv);
1.110 + for (double index = 0; index < parts; ++index) {
1.111 + double newT = start + (index / parts) * (end - start);
1.112 + if (newT > 0 && newT < 1) {
1.113 + ts->push_back(newT);
1.114 + }
1.115 + }
1.116 +}
1.117 +
1.118 +// flavor that returns T values only, deferring computing the quads until they are needed
1.119 +// FIXME: when called from recursive intersect 2, this could take the original cubic
1.120 +// and do a more precise job when calling chop at and sub divide by computing the fractional ts.
1.121 +// it would still take the prechopped cubic for reduce order and find cubic inflections
1.122 +void SkDCubic::toQuadraticTs(double precision, SkTArray<double, true>* ts) const {
1.123 + SkReduceOrder reducer;
1.124 + int order = reducer.reduce(*this, SkReduceOrder::kAllow_Quadratics);
1.125 + if (order < 3) {
1.126 + return;
1.127 + }
1.128 + double inflectT[5];
1.129 + int inflections = findInflections(inflectT);
1.130 + SkASSERT(inflections <= 2);
1.131 + if (!endsAreExtremaInXOrY()) {
1.132 + inflections += findMaxCurvature(&inflectT[inflections]);
1.133 + SkASSERT(inflections <= 5);
1.134 + }
1.135 + SkTQSort<double>(inflectT, &inflectT[inflections - 1]);
1.136 + // OPTIMIZATION: is this filtering common enough that it needs to be pulled out into its
1.137 + // own subroutine?
1.138 + while (inflections && approximately_less_than_zero(inflectT[0])) {
1.139 + memmove(inflectT, &inflectT[1], sizeof(inflectT[0]) * --inflections);
1.140 + }
1.141 + int start = 0;
1.142 + int next = 1;
1.143 + while (next < inflections) {
1.144 + if (!approximately_equal(inflectT[start], inflectT[next])) {
1.145 + ++start;
1.146 + ++next;
1.147 + continue;
1.148 + }
1.149 + memmove(&inflectT[start], &inflectT[next], sizeof(inflectT[0]) * (--inflections - start));
1.150 + }
1.151 +
1.152 + while (inflections && approximately_greater_than_one(inflectT[inflections - 1])) {
1.153 + --inflections;
1.154 + }
1.155 + SkDCubicPair pair;
1.156 + if (inflections == 1) {
1.157 + pair = chopAt(inflectT[0]);
1.158 + int orderP1 = reducer.reduce(pair.first(), SkReduceOrder::kNo_Quadratics);
1.159 + if (orderP1 < 2) {
1.160 + --inflections;
1.161 + } else {
1.162 + int orderP2 = reducer.reduce(pair.second(), SkReduceOrder::kNo_Quadratics);
1.163 + if (orderP2 < 2) {
1.164 + --inflections;
1.165 + }
1.166 + }
1.167 + }
1.168 + if (inflections == 0 && add_simple_ts(*this, precision, ts)) {
1.169 + return;
1.170 + }
1.171 + if (inflections == 1) {
1.172 + pair = chopAt(inflectT[0]);
1.173 + addTs(pair.first(), precision, 0, inflectT[0], ts);
1.174 + addTs(pair.second(), precision, inflectT[0], 1, ts);
1.175 + return;
1.176 + }
1.177 + if (inflections > 1) {
1.178 + SkDCubic part = subDivide(0, inflectT[0]);
1.179 + addTs(part, precision, 0, inflectT[0], ts);
1.180 + int last = inflections - 1;
1.181 + for (int idx = 0; idx < last; ++idx) {
1.182 + part = subDivide(inflectT[idx], inflectT[idx + 1]);
1.183 + addTs(part, precision, inflectT[idx], inflectT[idx + 1], ts);
1.184 + }
1.185 + part = subDivide(inflectT[last], 1);
1.186 + addTs(part, precision, inflectT[last], 1, ts);
1.187 + return;
1.188 + }
1.189 + addTs(*this, precision, 0, 1, ts);
1.190 +}
