OLD | NEW |
| (Empty) |
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 "CurveIntersection.h" | |
8 #include "Extrema.h" | |
9 #include "IntersectionUtilities.h" | |
10 #include "LineParameters.h" | |
11 | |
12 static double interp_cubic_coords(const double* src, double t) | |
13 { | |
14 double ab = interp(src[0], src[2], t); | |
15 double bc = interp(src[2], src[4], t); | |
16 double cd = interp(src[4], src[6], t); | |
17 double abc = interp(ab, bc, t); | |
18 double bcd = interp(bc, cd, t); | |
19 return interp(abc, bcd, t); | |
20 } | |
21 | |
22 static int coincident_line(const Cubic& cubic, Cubic& reduction) { | |
23 reduction[0] = reduction[1] = cubic[0]; | |
24 return 1; | |
25 } | |
26 | |
27 static int vertical_line(const Cubic& cubic, ReduceOrder_Styles reduceStyle, Cub
ic& reduction) { | |
28 double tValues[2]; | |
29 reduction[0] = cubic[0]; | |
30 reduction[1] = cubic[3]; | |
31 if (reduceStyle == kReduceOrder_TreatAsFill) { | |
32 return 2; | |
33 } | |
34 int smaller = reduction[1].y > reduction[0].y; | |
35 int larger = smaller ^ 1; | |
36 int roots = findExtrema(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y, tVal
ues); | |
37 for (int index = 0; index < roots; ++index) { | |
38 double yExtrema = interp_cubic_coords(&cubic[0].y, tValues[index]); | |
39 if (reduction[smaller].y > yExtrema) { | |
40 reduction[smaller].y = yExtrema; | |
41 continue; | |
42 } | |
43 if (reduction[larger].y < yExtrema) { | |
44 reduction[larger].y = yExtrema; | |
45 } | |
46 } | |
47 return 2; | |
48 } | |
49 | |
50 static int horizontal_line(const Cubic& cubic, ReduceOrder_Styles reduceStyle, C
ubic& reduction) { | |
51 double tValues[2]; | |
52 reduction[0] = cubic[0]; | |
53 reduction[1] = cubic[3]; | |
54 if (reduceStyle == kReduceOrder_TreatAsFill) { | |
55 return 2; | |
56 } | |
57 int smaller = reduction[1].x > reduction[0].x; | |
58 int larger = smaller ^ 1; | |
59 int roots = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x, tVal
ues); | |
60 for (int index = 0; index < roots; ++index) { | |
61 double xExtrema = interp_cubic_coords(&cubic[0].x, tValues[index]); | |
62 if (reduction[smaller].x > xExtrema) { | |
63 reduction[smaller].x = xExtrema; | |
64 continue; | |
65 } | |
66 if (reduction[larger].x < xExtrema) { | |
67 reduction[larger].x = xExtrema; | |
68 } | |
69 } | |
70 return 2; | |
71 } | |
72 | |
73 // check to see if it is a quadratic or a line | |
74 static int check_quadratic(const Cubic& cubic, Cubic& reduction) { | |
75 double dx10 = cubic[1].x - cubic[0].x; | |
76 double dx23 = cubic[2].x - cubic[3].x; | |
77 double midX = cubic[0].x + dx10 * 3 / 2; | |
78 if (!AlmostEqualUlps(midX - cubic[3].x, dx23 * 3 / 2)) { | |
79 return 0; | |
80 } | |
81 double dy10 = cubic[1].y - cubic[0].y; | |
82 double dy23 = cubic[2].y - cubic[3].y; | |
83 double midY = cubic[0].y + dy10 * 3 / 2; | |
84 if (!AlmostEqualUlps(midY - cubic[3].y, dy23 * 3 / 2)) { | |
85 return 0; | |
86 } | |
87 reduction[0] = cubic[0]; | |
88 reduction[1].x = midX; | |
89 reduction[1].y = midY; | |
90 reduction[2] = cubic[3]; | |
91 return 3; | |
92 } | |
93 | |
94 static int check_linear(const Cubic& cubic, ReduceOrder_Styles reduceStyle, | |
95 int minX, int maxX, int minY, int maxY, Cubic& reduction) { | |
96 int startIndex = 0; | |
97 int endIndex = 3; | |
98 while (cubic[startIndex].approximatelyEqual(cubic[endIndex])) { | |
99 --endIndex; | |
100 if (endIndex == 0) { | |
101 printf("%s shouldn't get here if all four points are about equal\n",
__FUNCTION__); | |
102 SkASSERT(0); | |
103 } | |
104 } | |
105 if (!isLinear(cubic, startIndex, endIndex)) { | |
106 return 0; | |
107 } | |
108 // four are colinear: return line formed by outside | |
109 reduction[0] = cubic[0]; | |
110 reduction[1] = cubic[3]; | |
111 if (reduceStyle == kReduceOrder_TreatAsFill) { | |
112 return 2; | |
113 } | |
114 int sameSide1; | |
115 int sameSide2; | |
116 bool useX = cubic[maxX].x - cubic[minX].x >= cubic[maxY].y - cubic[minY].y; | |
117 if (useX) { | |
118 sameSide1 = sign(cubic[0].x - cubic[1].x) + sign(cubic[3].x - cubic[1].x
); | |
119 sameSide2 = sign(cubic[0].x - cubic[2].x) + sign(cubic[3].x - cubic[2].x
); | |
120 } else { | |
121 sameSide1 = sign(cubic[0].y - cubic[1].y) + sign(cubic[3].y - cubic[1].y
); | |
122 sameSide2 = sign(cubic[0].y - cubic[2].y) + sign(cubic[3].y - cubic[2].y
); | |
123 } | |
124 if (sameSide1 == sameSide2 && (sameSide1 & 3) != 2) { | |
125 return 2; | |
126 } | |
127 double tValues[2]; | |
128 int roots; | |
129 if (useX) { | |
130 roots = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x, tVal
ues); | |
131 } else { | |
132 roots = findExtrema(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y, tVal
ues); | |
133 } | |
134 for (int index = 0; index < roots; ++index) { | |
135 _Point extrema; | |
136 extrema.x = interp_cubic_coords(&cubic[0].x, tValues[index]); | |
137 extrema.y = interp_cubic_coords(&cubic[0].y, tValues[index]); | |
138 // sameSide > 0 means mid is smaller than either [0] or [3], so replace
smaller | |
139 int replace; | |
140 if (useX) { | |
141 if (extrema.x < cubic[0].x ^ extrema.x < cubic[3].x) { | |
142 continue; | |
143 } | |
144 replace = (extrema.x < cubic[0].x | extrema.x < cubic[3].x) | |
145 ^ (cubic[0].x < cubic[3].x); | |
146 } else { | |
147 if (extrema.y < cubic[0].y ^ extrema.y < cubic[3].y) { | |
148 continue; | |
149 } | |
150 replace = (extrema.y < cubic[0].y | extrema.y < cubic[3].y) | |
151 ^ (cubic[0].y < cubic[3].y); | |
152 } | |
153 reduction[replace] = extrema; | |
154 } | |
155 return 2; | |
156 } | |
157 | |
158 bool isLinear(const Cubic& cubic, int startIndex, int endIndex) { | |
159 LineParameters lineParameters; | |
160 lineParameters.cubicEndPoints(cubic, startIndex, endIndex); | |
161 // FIXME: maybe it's possible to avoid this and compare non-normalized | |
162 lineParameters.normalize(); | |
163 double distance = lineParameters.controlPtDistance(cubic, 1); | |
164 if (!approximately_zero(distance)) { | |
165 return false; | |
166 } | |
167 distance = lineParameters.controlPtDistance(cubic, 2); | |
168 return approximately_zero(distance); | |
169 } | |
170 | |
171 /* food for thought: | |
172 http://objectmix.com/graphics/132906-fast-precision-driven-cubic-quadratic-piece
wise-degree-reduction-algos-2-a.html | |
173 | |
174 Given points c1, c2, c3 and c4 of a cubic Bezier, the points of the | |
175 corresponding quadratic Bezier are (given in convex combinations of | |
176 points): | |
177 | |
178 q1 = (11/13)c1 + (3/13)c2 -(3/13)c3 + (2/13)c4 | |
179 q2 = -c1 + (3/2)c2 + (3/2)c3 - c4 | |
180 q3 = (2/13)c1 - (3/13)c2 + (3/13)c3 + (11/13)c4 | |
181 | |
182 Of course, this curve does not interpolate the end-points, but it would | |
183 be interesting to see the behaviour of such a curve in an applet. | |
184 | |
185 -- | |
186 Kalle Rutanen | |
187 http://kaba.hilvi.org | |
188 | |
189 */ | |
190 | |
191 // reduce to a quadratic or smaller | |
192 // look for identical points | |
193 // look for all four points in a line | |
194 // note that three points in a line doesn't simplify a cubic | |
195 // look for approximation with single quadratic | |
196 // save approximation with multiple quadratics for later | |
197 int reduceOrder(const Cubic& cubic, Cubic& reduction, ReduceOrder_Quadratics all
owQuadratics, | |
198 ReduceOrder_Styles reduceStyle) { | |
199 int index, minX, maxX, minY, maxY; | |
200 int minXSet, minYSet; | |
201 minX = maxX = minY = maxY = 0; | |
202 minXSet = minYSet = 0; | |
203 for (index = 1; index < 4; ++index) { | |
204 if (cubic[minX].x > cubic[index].x) { | |
205 minX = index; | |
206 } | |
207 if (cubic[minY].y > cubic[index].y) { | |
208 minY = index; | |
209 } | |
210 if (cubic[maxX].x < cubic[index].x) { | |
211 maxX = index; | |
212 } | |
213 if (cubic[maxY].y < cubic[index].y) { | |
214 maxY = index; | |
215 } | |
216 } | |
217 for (index = 0; index < 4; ++index) { | |
218 double cx = cubic[index].x; | |
219 double cy = cubic[index].y; | |
220 double denom = SkTMax(fabs(cx), SkTMax(fabs(cy), | |
221 SkTMax(fabs(cubic[minX].x), fabs(cubic[minY].y)))); | |
222 if (denom == 0) { | |
223 minXSet |= 1 << index; | |
224 minYSet |= 1 << index; | |
225 continue; | |
226 } | |
227 double inv = 1 / denom; | |
228 if (approximately_equal_half(cx * inv, cubic[minX].x * inv)) { | |
229 minXSet |= 1 << index; | |
230 } | |
231 if (approximately_equal_half(cy * inv, cubic[minY].y * inv)) { | |
232 minYSet |= 1 << index; | |
233 } | |
234 } | |
235 if (minXSet == 0xF) { // test for vertical line | |
236 if (minYSet == 0xF) { // return 1 if all four are coincident | |
237 return coincident_line(cubic, reduction); | |
238 } | |
239 return vertical_line(cubic, reduceStyle, reduction); | |
240 } | |
241 if (minYSet == 0xF) { // test for horizontal line | |
242 return horizontal_line(cubic, reduceStyle, reduction); | |
243 } | |
244 int result = check_linear(cubic, reduceStyle, minX, maxX, minY, maxY, reduct
ion); | |
245 if (result) { | |
246 return result; | |
247 } | |
248 if (allowQuadratics == kReduceOrder_QuadraticsAllowed | |
249 && (result = check_quadratic(cubic, reduction))) { | |
250 return result; | |
251 } | |
252 memcpy(reduction, cubic, sizeof(Cubic)); | |
253 return 4; | |
254 } | |
OLD | NEW |