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