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