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 | |
8 #include "CubicUtilities.h" | |
9 #include "CurveIntersection.h" | |
10 #include "Intersections.h" | |
11 #include "IntersectionUtilities.h" | |
12 #include "LineIntersection.h" | |
13 | |
14 static const double tClipLimit = 0.8; // http://cagd.cs.byu.edu/~tom/papers/bezc
lip.pdf see Multiple intersections | |
15 | |
16 class CubicIntersections : public Intersections { | |
17 public: | |
18 | |
19 CubicIntersections(const Cubic& c1, const Cubic& c2, Intersections& i) | |
20 : cubic1(c1) | |
21 , cubic2(c2) | |
22 , intersections(i) | |
23 , depth(0) | |
24 , splits(0) { | |
25 } | |
26 | |
27 bool intersect() { | |
28 double minT1, minT2, maxT1, maxT2; | |
29 if (!bezier_clip(cubic2, cubic1, minT1, maxT1)) { | |
30 return false; | |
31 } | |
32 if (!bezier_clip(cubic1, cubic2, minT2, maxT2)) { | |
33 return false; | |
34 } | |
35 int split; | |
36 if (maxT1 - minT1 < maxT2 - minT2) { | |
37 intersections.swap(); | |
38 minT2 = 0; | |
39 maxT2 = 1; | |
40 split = maxT1 - minT1 > tClipLimit; | |
41 } else { | |
42 minT1 = 0; | |
43 maxT1 = 1; | |
44 split = (maxT2 - minT2 > tClipLimit) << 1; | |
45 } | |
46 return chop(minT1, maxT1, minT2, maxT2, split); | |
47 } | |
48 | |
49 protected: | |
50 | |
51 bool intersect(double minT1, double maxT1, double minT2, double maxT2) { | |
52 Cubic smaller, larger; | |
53 // FIXME: carry last subdivide and reduceOrder result with cubic | |
54 sub_divide(cubic1, minT1, maxT1, intersections.swapped() ? larger : smaller)
; | |
55 sub_divide(cubic2, minT2, maxT2, intersections.swapped() ? smaller : larger)
; | |
56 Cubic smallResult; | |
57 if (reduceOrder(smaller, smallResult, kReduceOrder_NoQuadraticsAllowed, | |
58 kReduceOrder_TreatAsFill) <= 2) { | |
59 Cubic largeResult; | |
60 if (reduceOrder(larger, largeResult, kReduceOrder_NoQuadraticsAllowed, | |
61 kReduceOrder_TreatAsFill) <= 2) { | |
62 const _Line& smallLine = (const _Line&) smallResult; | |
63 const _Line& largeLine = (const _Line&) largeResult; | |
64 Intersections lineTs; | |
65 // FIXME: this doesn't detect or deal with coincident lines | |
66 if (!::intersect(smallLine, largeLine, lineTs)) { | |
67 return false; | |
68 } | |
69 if (intersections.swapped()) { | |
70 lineTs.fT[0][0] = interp(minT2, maxT2, lineTs.fT[0][0]); | |
71 lineTs.fT[1][0] = interp(minT1, maxT1, lineTs.fT[1][0]); | |
72 } else { | |
73 lineTs.fT[0][0] = interp(minT1, maxT1, lineTs.fT[0][0]); | |
74 lineTs.fT[1][0] = interp(minT2, maxT2, lineTs.fT[1][0]); | |
75 } | |
76 _Point pt; | |
77 xy_at_t(cubic1, lineTs.fT[0][0], pt.x, pt.y); | |
78 intersections.insert(lineTs.fT[0][0], lineTs.fT[1][0], pt); | |
79 return true; | |
80 } | |
81 } | |
82 double minT, maxT; | |
83 if (!bezier_clip(smaller, larger, minT, maxT)) { | |
84 if (minT == maxT) { | |
85 if (intersections.swapped()) { | |
86 minT1 = (minT1 + maxT1) / 2; | |
87 minT2 = interp(minT2, maxT2, minT); | |
88 } else { | |
89 minT1 = interp(minT1, maxT1, minT); | |
90 minT2 = (minT2 + maxT2) / 2; | |
91 } | |
92 _Point pt; | |
93 xy_at_t(cubic1, minT1, pt.x, pt.y); | |
94 intersections.insert(minT1, minT2, pt); | |
95 return true; | |
96 } | |
97 return false; | |
98 } | |
99 | |
100 int split; | |
101 if (intersections.swapped()) { | |
102 double newMinT1 = interp(minT1, maxT1, minT); | |
103 double newMaxT1 = interp(minT1, maxT1, maxT); | |
104 split = (newMaxT1 - newMinT1 > (maxT1 - minT1) * tClipLimit) << 1; | |
105 #define VERBOSE 0 | |
106 #if VERBOSE | |
107 printf("%s d=%d s=%d new1=(%g,%g) old1=(%g,%g) split=%d\n", | |
108 __FUNCTION__, depth, splits, newMinT1, newMaxT1, minT1, maxT1, | |
109 split); | |
110 #endif | |
111 minT1 = newMinT1; | |
112 maxT1 = newMaxT1; | |
113 } else { | |
114 double newMinT2 = interp(minT2, maxT2, minT); | |
115 double newMaxT2 = interp(minT2, maxT2, maxT); | |
116 split = newMaxT2 - newMinT2 > (maxT2 - minT2) * tClipLimit; | |
117 #if VERBOSE | |
118 printf("%s d=%d s=%d new2=(%g,%g) old2=(%g,%g) split=%d\n", | |
119 __FUNCTION__, depth, splits, newMinT2, newMaxT2, minT2, maxT2, | |
120 split); | |
121 #endif | |
122 minT2 = newMinT2; | |
123 maxT2 = newMaxT2; | |
124 } | |
125 return chop(minT1, maxT1, minT2, maxT2, split); | |
126 } | |
127 | |
128 bool chop(double minT1, double maxT1, double minT2, double maxT2, int split) { | |
129 ++depth; | |
130 intersections.swap(); | |
131 if (split) { | |
132 ++splits; | |
133 if (split & 2) { | |
134 double middle1 = (maxT1 + minT1) / 2; | |
135 intersect(minT1, middle1, minT2, maxT2); | |
136 intersect(middle1, maxT1, minT2, maxT2); | |
137 } else { | |
138 double middle2 = (maxT2 + minT2) / 2; | |
139 intersect(minT1, maxT1, minT2, middle2); | |
140 intersect(minT1, maxT1, middle2, maxT2); | |
141 } | |
142 --splits; | |
143 intersections.swap(); | |
144 --depth; | |
145 return intersections.intersected(); | |
146 } | |
147 bool result = intersect(minT1, maxT1, minT2, maxT2); | |
148 intersections.swap(); | |
149 --depth; | |
150 return result; | |
151 } | |
152 | |
153 private: | |
154 | |
155 const Cubic& cubic1; | |
156 const Cubic& cubic2; | |
157 Intersections& intersections; | |
158 int depth; | |
159 int splits; | |
160 }; | |
161 | |
162 bool intersect(const Cubic& c1, const Cubic& c2, Intersections& i) { | |
163 CubicIntersections c(c1, c2, i); | |
164 return c.intersect(); | |
165 } | |
OLD | NEW |