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