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