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