blob: bb2038b45f2ec864e6c06883c5aabded3ff9fe2d [file] [log] [blame]
caryclark@google.com07393ca2013-04-08 11:47:37 +00001/*
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
caryclark@google.com07393ca2013-04-08 11:47:37 +000016static 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
caryclark@google.com927b7022013-11-25 14:18:21 +000025static int vertical_line(const SkDQuad& quad, SkDQuad& reduction) {
caryclark@google.com07393ca2013-04-08 11:47:37 +000026 reduction[0] = quad[0];
27 reduction[1] = quad[2];
caryclark@google.com07393ca2013-04-08 11:47:37 +000028 return reductionLineCount(reduction);
29}
30
caryclark@google.com927b7022013-11-25 14:18:21 +000031static int horizontal_line(const SkDQuad& quad, SkDQuad& reduction) {
caryclark@google.com07393ca2013-04-08 11:47:37 +000032 reduction[0] = quad[0];
33 reduction[1] = quad[2];
caryclark@google.com07393ca2013-04-08 11:47:37 +000034 return reductionLineCount(reduction);
35}
36
caryclark@google.com927b7022013-11-25 14:18:21 +000037static int check_linear(const SkDQuad& quad,
caryclark@google.com07393ca2013-04-08 11:47:37 +000038 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];
caryclark@google.com07393ca2013-04-08 11:47:37 +000054 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
caryclark@google.com927b7022013-11-25 14:18:21 +000063int SkReduceOrder::reduce(const SkDQuad& quad) {
caryclark@google.com07393ca2013-04-08 11:47:37 +000064 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 }
caryclark@google.com927b7022013-11-25 14:18:21 +000094 return vertical_line(quad, fQuad);
caryclark@google.com07393ca2013-04-08 11:47:37 +000095 }
96 if (minYSet == 0xF) { // test for horizontal line
caryclark@google.com927b7022013-11-25 14:18:21 +000097 return horizontal_line(quad, fQuad);
caryclark@google.com07393ca2013-04-08 11:47:37 +000098 }
caryclark@google.com927b7022013-11-25 14:18:21 +000099 int result = check_linear(quad, minX, maxX, minY, maxY, fQuad);
caryclark@google.com07393ca2013-04-08 11:47:37 +0000100 if (result) {
101 return result;
102 }
103 fQuad = quad;
104 return 3;
105}
106
107////////////////////////////////////////////////////////////////////////////////////
108
caryclark@google.com07393ca2013-04-08 11:47:37 +0000109static 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
caryclark@google.com927b7022013-11-25 14:18:21 +0000118static int vertical_line(const SkDCubic& cubic, SkDCubic& reduction) {
caryclark@google.com07393ca2013-04-08 11:47:37 +0000119 reduction[0] = cubic[0];
120 reduction[1] = cubic[3];
caryclark@google.com07393ca2013-04-08 11:47:37 +0000121 return reductionLineCount(reduction);
122}
123
caryclark@google.com927b7022013-11-25 14:18:21 +0000124static int horizontal_line(const SkDCubic& cubic, SkDCubic& reduction) {
caryclark@google.com07393ca2013-04-08 11:47:37 +0000125 reduction[0] = cubic[0];
126 reduction[1] = cubic[3];
caryclark@google.com07393ca2013-04-08 11:47:37 +0000127 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;
caryclark@google.com7ec5e392013-04-17 16:19:02 +0000135 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)) {
caryclark@google.com07393ca2013-04-08 11:47:37 +0000139 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;
caryclark@google.com7ec5e392013-04-17 16:19:02 +0000144 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)) {
caryclark@google.com07393ca2013-04-08 11:47:37 +0000148 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
caryclark@google.com927b7022013-11-25 14:18:21 +0000157static int check_linear(const SkDCubic& cubic,
caryclark@google.com07393ca2013-04-08 11:47:37 +0000158 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) {
commit-bot@chromium.org8cb1daa2014-04-25 12:59:11 +0000164 endIndex = 3;
165 break;
caryclark@google.com07393ca2013-04-08 11:47:37 +0000166 }
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];
caryclark@google.com07393ca2013-04-08 11:47:37 +0000174 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
caryclark@google.com927b7022013-11-25 14:18:21 +0000203int SkReduceOrder::reduce(const SkDCubic& cubic, Quadratics allowQuadratics) {
caryclark@google.com07393ca2013-04-08 11:47:37 +0000204 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 }
caryclark@google.com927b7022013-11-25 14:18:21 +0000244 return vertical_line(cubic, fCubic);
caryclark@google.com07393ca2013-04-08 11:47:37 +0000245 }
246 if (minYSet == 0xF) { // test for horizontal line
caryclark@google.com927b7022013-11-25 14:18:21 +0000247 return horizontal_line(cubic, fCubic);
caryclark@google.com07393ca2013-04-08 11:47:37 +0000248 }
caryclark@google.com927b7022013-11-25 14:18:21 +0000249 int result = check_linear(cubic, minX, maxX, minY, maxY, fCubic);
caryclark@google.com07393ca2013-04-08 11:47:37 +0000250 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
caryclark@google.com07e97fc2013-07-08 17:17:02 +0000261SkPath::Verb SkReduceOrder::Quad(const SkPoint a[3], SkPoint* reducePts) {
caryclark@google.com07393ca2013-04-08 11:47:37 +0000262 SkDQuad quad;
263 quad.set(a);
264 SkReduceOrder reducer;
caryclark@google.com927b7022013-11-25 14:18:21 +0000265 int order = reducer.reduce(quad);
caryclark@google.com07393ca2013-04-08 11:47:37 +0000266 if (order == 2) { // quad became line
267 for (int index = 0; index < order; ++index) {
caryclark@google.com07e97fc2013-07-08 17:17:02 +0000268 *reducePts++ = reducer.fLine[index].asSkPoint();
caryclark@google.com07393ca2013-04-08 11:47:37 +0000269 }
270 }
reed@google.com277c3f82013-05-31 15:17:50 +0000271 return SkPathOpsPointsToVerb(order - 1);
caryclark@google.com07393ca2013-04-08 11:47:37 +0000272}
273
caryclark@google.com07e97fc2013-07-08 17:17:02 +0000274SkPath::Verb SkReduceOrder::Cubic(const SkPoint a[4], SkPoint* reducePts) {
caryclark@google.com07393ca2013-04-08 11:47:37 +0000275 SkDCubic cubic;
276 cubic.set(a);
277 SkReduceOrder reducer;
caryclark@google.com927b7022013-11-25 14:18:21 +0000278 int order = reducer.reduce(cubic, kAllow_Quadratics);
caryclark@google.com07393ca2013-04-08 11:47:37 +0000279 if (order == 2 || order == 3) { // cubic became line or quad
280 for (int index = 0; index < order; ++index) {
caryclark@google.com07e97fc2013-07-08 17:17:02 +0000281 *reducePts++ = reducer.fQuad[index].asSkPoint();
caryclark@google.com07393ca2013-04-08 11:47:37 +0000282 }
283 }
reed@google.com277c3f82013-05-31 15:17:50 +0000284 return SkPathOpsPointsToVerb(order - 1);
caryclark@google.com07393ca2013-04-08 11:47:37 +0000285}