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_quad_coords(double a, double b, double c, double t) | |
13 { | |
14 double ab = interp(a, b, t); | |
15 double bc = interp(b, c, t); | |
16 return interp(ab, bc, t); | |
17 } | |
18 | |
19 static int coincident_line(const Quadratic& quad, Quadratic& reduction) { | |
20 reduction[0] = reduction[1] = quad[0]; | |
21 return 1; | |
22 } | |
23 | |
24 static int vertical_line(const Quadratic& quad, ReduceOrder_Styles reduceStyle, | |
25 Quadratic& reduction) { | |
26 double tValue; | |
27 reduction[0] = quad[0]; | |
28 reduction[1] = quad[2]; | |
29 if (reduceStyle == kReduceOrder_TreatAsFill) { | |
30 return 2; | |
31 } | |
32 int smaller = reduction[1].y > reduction[0].y; | |
33 int larger = smaller ^ 1; | |
34 if (findExtrema(quad[0].y, quad[1].y, quad[2].y, &tValue)) { | |
35 double yExtrema = interp_quad_coords(quad[0].y, quad[1].y, quad[2].y, tV
alue); | |
36 if (reduction[smaller].y > yExtrema) { | |
37 reduction[smaller].y = yExtrema; | |
38 } else if (reduction[larger].y < yExtrema) { | |
39 reduction[larger].y = yExtrema; | |
40 } | |
41 } | |
42 return 2; | |
43 } | |
44 | |
45 static int horizontal_line(const Quadratic& quad, ReduceOrder_Styles reduceStyle
, | |
46 Quadratic& reduction) { | |
47 double tValue; | |
48 reduction[0] = quad[0]; | |
49 reduction[1] = quad[2]; | |
50 if (reduceStyle == kReduceOrder_TreatAsFill) { | |
51 return 2; | |
52 } | |
53 int smaller = reduction[1].x > reduction[0].x; | |
54 int larger = smaller ^ 1; | |
55 if (findExtrema(quad[0].x, quad[1].x, quad[2].x, &tValue)) { | |
56 double xExtrema = interp_quad_coords(quad[0].x, quad[1].x, quad[2].x, tV
alue); | |
57 if (reduction[smaller].x > xExtrema) { | |
58 reduction[smaller].x = xExtrema; | |
59 } else if (reduction[larger].x < xExtrema) { | |
60 reduction[larger].x = xExtrema; | |
61 } | |
62 } | |
63 return 2; | |
64 } | |
65 | |
66 static int check_linear(const Quadratic& quad, ReduceOrder_Styles reduceStyle, | |
67 int minX, int maxX, int minY, int maxY, Quadratic& reduction) { | |
68 int startIndex = 0; | |
69 int endIndex = 2; | |
70 while (quad[startIndex].approximatelyEqual(quad[endIndex])) { | |
71 --endIndex; | |
72 if (endIndex == 0) { | |
73 printf("%s shouldn't get here if all four points are about equal", _
_FUNCTION__); | |
74 SkASSERT(0); | |
75 } | |
76 } | |
77 if (!isLinear(quad, startIndex, endIndex)) { | |
78 return 0; | |
79 } | |
80 // four are colinear: return line formed by outside | |
81 reduction[0] = quad[0]; | |
82 reduction[1] = quad[2]; | |
83 if (reduceStyle == kReduceOrder_TreatAsFill) { | |
84 return 2; | |
85 } | |
86 int sameSide; | |
87 bool useX = quad[maxX].x - quad[minX].x >= quad[maxY].y - quad[minY].y; | |
88 if (useX) { | |
89 sameSide = sign(quad[0].x - quad[1].x) + sign(quad[2].x - quad[1].x); | |
90 } else { | |
91 sameSide = sign(quad[0].y - quad[1].y) + sign(quad[2].y - quad[1].y); | |
92 } | |
93 if ((sameSide & 3) != 2) { | |
94 return 2; | |
95 } | |
96 double tValue; | |
97 int root; | |
98 if (useX) { | |
99 root = findExtrema(quad[0].x, quad[1].x, quad[2].x, &tValue); | |
100 } else { | |
101 root = findExtrema(quad[0].y, quad[1].y, quad[2].y, &tValue); | |
102 } | |
103 if (root) { | |
104 _Point extrema; | |
105 extrema.x = interp_quad_coords(quad[0].x, quad[1].x, quad[2].x, tValue); | |
106 extrema.y = interp_quad_coords(quad[0].y, quad[1].y, quad[2].y, tValue); | |
107 // sameSide > 0 means mid is smaller than either [0] or [2], so replace
smaller | |
108 int replace; | |
109 if (useX) { | |
110 if (extrema.x < quad[0].x ^ extrema.x < quad[2].x) { | |
111 return 2; | |
112 } | |
113 replace = (extrema.x < quad[0].x | extrema.x < quad[2].x) | |
114 ^ (quad[0].x < quad[2].x); | |
115 } else { | |
116 if (extrema.y < quad[0].y ^ extrema.y < quad[2].y) { | |
117 return 2; | |
118 } | |
119 replace = (extrema.y < quad[0].y | extrema.y < quad[2].y) | |
120 ^ (quad[0].y < quad[2].y); | |
121 } | |
122 reduction[replace] = extrema; | |
123 } | |
124 return 2; | |
125 } | |
126 | |
127 bool isLinear(const Quadratic& quad, int startIndex, int endIndex) { | |
128 LineParameters lineParameters; | |
129 lineParameters.quadEndPoints(quad, startIndex, endIndex); | |
130 // FIXME: maybe it's possible to avoid this and compare non-normalized | |
131 lineParameters.normalize(); | |
132 double distance = lineParameters.controlPtDistance(quad); | |
133 return approximately_zero(distance); | |
134 } | |
135 | |
136 // reduce to a quadratic or smaller | |
137 // look for identical points | |
138 // look for all four points in a line | |
139 // note that three points in a line doesn't simplify a cubic | |
140 // look for approximation with single quadratic | |
141 // save approximation with multiple quadratics for later | |
142 int reduceOrder(const Quadratic& quad, Quadratic& reduction, ReduceOrder_Styles
reduceStyle) { | |
143 int index, minX, maxX, minY, maxY; | |
144 int minXSet, minYSet; | |
145 minX = maxX = minY = maxY = 0; | |
146 minXSet = minYSet = 0; | |
147 for (index = 1; index < 3; ++index) { | |
148 if (quad[minX].x > quad[index].x) { | |
149 minX = index; | |
150 } | |
151 if (quad[minY].y > quad[index].y) { | |
152 minY = index; | |
153 } | |
154 if (quad[maxX].x < quad[index].x) { | |
155 maxX = index; | |
156 } | |
157 if (quad[maxY].y < quad[index].y) { | |
158 maxY = index; | |
159 } | |
160 } | |
161 for (index = 0; index < 3; ++index) { | |
162 if (AlmostEqualUlps(quad[index].x, quad[minX].x)) { | |
163 minXSet |= 1 << index; | |
164 } | |
165 if (AlmostEqualUlps(quad[index].y, quad[minY].y)) { | |
166 minYSet |= 1 << index; | |
167 } | |
168 } | |
169 if (minXSet == 0x7) { // test for vertical line | |
170 if (minYSet == 0x7) { // return 1 if all four are coincident | |
171 return coincident_line(quad, reduction); | |
172 } | |
173 return vertical_line(quad, reduceStyle, reduction); | |
174 } | |
175 if (minYSet == 0xF) { // test for horizontal line | |
176 return horizontal_line(quad, reduceStyle, reduction); | |
177 } | |
178 int result = check_linear(quad, reduceStyle, minX, maxX, minY, maxY, reducti
on); | |
179 if (result) { | |
180 return result; | |
181 } | |
182 memcpy(reduction, quad, sizeof(Quadratic)); | |
183 return 3; | |
184 } | |
OLD | NEW |