1/*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7#include "SkGeometry.h"
8#include "SkReduceOrder.h"
9
10int SkReduceOrder::reduce(const SkDLine& line) {
11    fLine[0] = line[0];
12    int different = line[0] != line[1];
13    fLine[1] = line[different];
14    return 1 + different;
15}
16
17static int coincident_line(const SkDQuad& quad, SkDQuad& reduction) {
18    reduction[0] = reduction[1] = quad[0];
19    return 1;
20}
21
22static int reductionLineCount(const SkDQuad& reduction) {
23    return 1 + !reduction[0].approximatelyEqual(reduction[1]);
24}
25
26static int vertical_line(const SkDQuad& quad, SkDQuad& reduction) {
27    reduction[0] = quad[0];
28    reduction[1] = quad[2];
29    return reductionLineCount(reduction);
30}
31
32static int horizontal_line(const SkDQuad& quad, SkDQuad& reduction) {
33    reduction[0] = quad[0];
34    reduction[1] = quad[2];
35    return reductionLineCount(reduction);
36}
37
38static int check_linear(const SkDQuad& quad,
39        int minX, int maxX, int minY, int maxY, SkDQuad& reduction) {
40    if (!quad.isLinear(0, 2)) {
41        return 0;
42    }
43    // four are colinear: return line formed by outside
44    reduction[0] = quad[0];
45    reduction[1] = quad[2];
46    return reductionLineCount(reduction);
47}
48
49// reduce to a quadratic or smaller
50// look for identical points
51// look for all four points in a line
52    // note that three points in a line doesn't simplify a cubic
53// look for approximation with single quadratic
54    // save approximation with multiple quadratics for later
55int SkReduceOrder::reduce(const SkDQuad& quad) {
56    int index, minX, maxX, minY, maxY;
57    int minXSet, minYSet;
58    minX = maxX = minY = maxY = 0;
59    minXSet = minYSet = 0;
60    for (index = 1; index < 3; ++index) {
61        if (quad[minX].fX > quad[index].fX) {
62            minX = index;
63        }
64        if (quad[minY].fY > quad[index].fY) {
65            minY = index;
66        }
67        if (quad[maxX].fX < quad[index].fX) {
68            maxX = index;
69        }
70        if (quad[maxY].fY < quad[index].fY) {
71            maxY = index;
72        }
73    }
74    for (index = 0; index < 3; ++index) {
75        if (AlmostEqualUlps(quad[index].fX, quad[minX].fX)) {
76            minXSet |= 1 << index;
77        }
78        if (AlmostEqualUlps(quad[index].fY, quad[minY].fY)) {
79            minYSet |= 1 << index;
80        }
81    }
82    if ((minXSet & 0x05) == 0x5 && (minYSet & 0x05) == 0x5) { // test for degenerate
83        // this quad starts and ends at the same place, so never contributes
84        // to the fill
85        return coincident_line(quad, fQuad);
86    }
87    if (minXSet == 0x7) {  // test for vertical line
88        return vertical_line(quad, fQuad);
89    }
90    if (minYSet == 0x7) {  // test for horizontal line
91        return horizontal_line(quad, fQuad);
92    }
93    int result = check_linear(quad, minX, maxX, minY, maxY, fQuad);
94    if (result) {
95        return result;
96    }
97    fQuad = quad;
98    return 3;
99}
100
101////////////////////////////////////////////////////////////////////////////////////
102
103static int coincident_line(const SkDCubic& cubic, SkDCubic& reduction) {
104    reduction[0] = reduction[1] = cubic[0];
105    return 1;
106}
107
108static int reductionLineCount(const SkDCubic& reduction) {
109    return 1 + !reduction[0].approximatelyEqual(reduction[1]);
110}
111
112static int vertical_line(const SkDCubic& cubic, SkDCubic& reduction) {
113    reduction[0] = cubic[0];
114    reduction[1] = cubic[3];
115    return reductionLineCount(reduction);
116}
117
118static int horizontal_line(const SkDCubic& cubic, SkDCubic& reduction) {
119    reduction[0] = cubic[0];
120    reduction[1] = cubic[3];
121    return reductionLineCount(reduction);
122}
123
124// check to see if it is a quadratic or a line
125static int check_quadratic(const SkDCubic& cubic, SkDCubic& reduction) {
126    double dx10 = cubic[1].fX - cubic[0].fX;
127    double dx23 = cubic[2].fX - cubic[3].fX;
128    double midX = cubic[0].fX + dx10 * 3 / 2;
129    double sideAx = midX - cubic[3].fX;
130    double sideBx = dx23 * 3 / 2;
131    if (approximately_zero(sideAx) ? !approximately_equal(sideAx, sideBx)
132            : !AlmostEqualUlps_Pin(sideAx, sideBx)) {
133        return 0;
134    }
135    double dy10 = cubic[1].fY - cubic[0].fY;
136    double dy23 = cubic[2].fY - cubic[3].fY;
137    double midY = cubic[0].fY + dy10 * 3 / 2;
138    double sideAy = midY - cubic[3].fY;
139    double sideBy = dy23 * 3 / 2;
140    if (approximately_zero(sideAy) ? !approximately_equal(sideAy, sideBy)
141            : !AlmostEqualUlps_Pin(sideAy, sideBy)) {
142        return 0;
143    }
144    reduction[0] = cubic[0];
145    reduction[1].fX = midX;
146    reduction[1].fY = midY;
147    reduction[2] = cubic[3];
148    return 3;
149}
150
151static int check_linear(const SkDCubic& cubic,
152        int minX, int maxX, int minY, int maxY, SkDCubic& reduction) {
153    if (!cubic.isLinear(0, 3)) {
154        return 0;
155    }
156    // four are colinear: return line formed by outside
157    reduction[0] = cubic[0];
158    reduction[1] = cubic[3];
159    return reductionLineCount(reduction);
160}
161
162/* food for thought:
163http://objectmix.com/graphics/132906-fast-precision-driven-cubic-quadratic-piecewise-degree-reduction-algos-2-a.html
164
165Given points c1, c2, c3 and c4 of a cubic Bezier, the points of the
166corresponding quadratic Bezier are (given in convex combinations of
167points):
168
169q1 = (11/13)c1 + (3/13)c2 -(3/13)c3 + (2/13)c4
170q2 = -c1 + (3/2)c2 + (3/2)c3 - c4
171q3 = (2/13)c1 - (3/13)c2 + (3/13)c3 + (11/13)c4
172
173Of course, this curve does not interpolate the end-points, but it would
174be interesting to see the behaviour of such a curve in an applet.
175
176--
177Kalle Rutanen
178http://kaba.hilvi.org
179
180*/
181
182// reduce to a quadratic or smaller
183// look for identical points
184// look for all four points in a line
185    // note that three points in a line doesn't simplify a cubic
186// look for approximation with single quadratic
187    // save approximation with multiple quadratics for later
188int SkReduceOrder::reduce(const SkDCubic& cubic, Quadratics allowQuadratics) {
189    int index, minX, maxX, minY, maxY;
190    int minXSet, minYSet;
191    minX = maxX = minY = maxY = 0;
192    minXSet = minYSet = 0;
193    for (index = 1; index < 4; ++index) {
194        if (cubic[minX].fX > cubic[index].fX) {
195            minX = index;
196        }
197        if (cubic[minY].fY > cubic[index].fY) {
198            minY = index;
199        }
200        if (cubic[maxX].fX < cubic[index].fX) {
201            maxX = index;
202        }
203        if (cubic[maxY].fY < cubic[index].fY) {
204            maxY = index;
205        }
206    }
207    for (index = 0; index < 4; ++index) {
208        double cx = cubic[index].fX;
209        double cy = cubic[index].fY;
210        double denom = SkTMax(fabs(cx), SkTMax(fabs(cy),
211                SkTMax(fabs(cubic[minX].fX), fabs(cubic[minY].fY))));
212        if (denom == 0) {
213            minXSet |= 1 << index;
214            minYSet |= 1 << index;
215            continue;
216        }
217        double inv = 1 / denom;
218        if (approximately_equal_half(cx * inv, cubic[minX].fX * inv)) {
219            minXSet |= 1 << index;
220        }
221        if (approximately_equal_half(cy * inv, cubic[minY].fY * inv)) {
222            minYSet |= 1 << index;
223        }
224    }
225    if (minXSet == 0xF) {  // test for vertical line
226        if (minYSet == 0xF) {  // return 1 if all four are coincident
227            return coincident_line(cubic, fCubic);
228        }
229        return vertical_line(cubic, fCubic);
230    }
231    if (minYSet == 0xF) {  // test for horizontal line
232        return horizontal_line(cubic, fCubic);
233    }
234    int result = check_linear(cubic, minX, maxX, minY, maxY, fCubic);
235    if (result) {
236        return result;
237    }
238    if (allowQuadratics == SkReduceOrder::kAllow_Quadratics
239            && (result = check_quadratic(cubic, fCubic))) {
240        return result;
241    }
242    fCubic = cubic;
243    return 4;
244}
245
246SkPath::Verb SkReduceOrder::Quad(const SkPoint a[3], SkPoint* reducePts) {
247    SkDQuad quad;
248    quad.set(a);
249    SkReduceOrder reducer;
250    int order = reducer.reduce(quad);
251    if (order == 2) {  // quad became line
252        for (int index = 0; index < order; ++index) {
253            *reducePts++ = reducer.fLine[index].asSkPoint();
254        }
255    }
256    return SkPathOpsPointsToVerb(order - 1);
257}
258
259SkPath::Verb SkReduceOrder::Conic(const SkConic& c, SkPoint* reducePts) {
260    SkPath::Verb verb = SkReduceOrder::Quad(c.fPts, reducePts);
261    if (verb > SkPath::kLine_Verb && c.fW == 1) {
262        return SkPath::kQuad_Verb;
263    }
264    return verb == SkPath::kQuad_Verb ? SkPath::kConic_Verb : verb;
265}
266
267SkPath::Verb SkReduceOrder::Cubic(const SkPoint a[4], SkPoint* reducePts) {
268    if (SkDPoint::ApproximatelyEqual(a[0], a[1]) && SkDPoint::ApproximatelyEqual(a[0], a[2])
269            && SkDPoint::ApproximatelyEqual(a[0], a[3])) {
270        reducePts[0] = a[0];
271        return SkPath::kMove_Verb;
272    }
273    SkDCubic cubic;
274    cubic.set(a);
275    SkReduceOrder reducer;
276    int order = reducer.reduce(cubic, kAllow_Quadratics);
277    if (order == 2 || order == 3) {  // cubic became line or quad
278        for (int index = 0; index < order; ++index) {
279            *reducePts++ = reducer.fQuad[index].asSkPoint();
280        }
281    }
282    return SkPathOpsPointsToVerb(order - 1);
283}
284