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
155
156
157
158
159
160
161
162
163
164
165
166
|
add unit test for quadratic horizontal intersection
add unit test for cubic horizontal intersection with left/right
add unit test for ActiveEdge::calcLeft (can currently loop forever)
does ActiveEdge::isCoincidentWith need to support quad, cubic?
figure out why variation in ActiveEdge::tooCloseToCall isn't better
why does 'lastPtr - 2' in addIntersectingTs break testSimplifyTriangle22?
add code to promote quad to cubic, or add quad/cubic intersection
figure out why testSimplifySkinnyTriangle13 fails
for quadratics and cubics, once various T values are added, see if consecutive
Ts have ys that go up instead of down. If so, the edge needs to be broken.
when splitting curves at inflection pts, should I retain the original curve
data and note that the first/last T are no longer 0/1 ?
I need to figure this out before I can proceed
would it make sense to leave the InEdge alone, and add multiple copies of
ActiveEdge, pointing to the same InEdge, where the copy has only the subset
of Ts that need to be walked in reverse order?
-- A Digression Which Shows Why Resolving Coincidence Does Not Make Sense --
Consider the following fine ASCII art:
+------>-------+ +------>-------+
| | | |
^ V ^ V
| | | |
+------<-------+ +------<-------+
+------>-------+ +------<-------+
| | | |
^ V V ^
| | | |
+------<-------+ +------>-------+
(assume the bottom and top of the stacked rectangles are coincident)
Simplifying said rectangles, regardless of rectangle direction, and regardless
of winding or even/odd, eliminates the coincident edge, i.e., the result is
always:
+------>-------+
| |
| |
| |
^ V
| |
| |
| |
+------<-------+
But when the rectangles are enclosed in a larger rectangle:
+-------->---------+ +-------->---------+
| +------>-------+ | | +------>-------+ |
| | | | | | | |
| ^ V | | ^ V |
| | | | | | | |
| +------<-------+ | | +------<-------+ |
| +------>-------+ | | +------<-------+ |
| | | | | | | |
| ^ V | | V ^ |
| | | | | | | |
| +------<-------+ | | +------>-------+ |
+--------<---------+ +--------<---------+
Simplifying them gives different results depending on the winding setting:
winding:
+-------->---------+ +-------->---------+
| | | |
| | | |
| | | |
| | | |
| | | +------<-------+ |
| | | | | |
| | | V ^ |
| | | | | |
| | | +------>-------+ |
+--------<---------+ +--------<---------+
even odd:
+-------->---------+ +-------->---------+
| +------<-------+ | | +------<-------+ |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| V ^ | | V ^ |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| +------>-------+ | | +------>-------+ |
+--------<---------+ +--------<---------+
So, given the inner rectangles alone (e.g., given coincident pairs in some local
context), we can't know whether to keep the coincident edges or not.
-- Thoughts About Sortless Ops --
I can't come up with anything truly sortless. It seems that the crossings need
to be sorted to know which segment is next on the outside, although sometimes
we can use that it is not coincident just to follow the direction.
If it is coincident or if there's more than two crossing segments, sorting
seems inevitable.
Likewise, to resolve whether one contour is inside another, it seems that
sorting is required. Given a pair of segments on different contours, to know
if one is inside of the other, I need to know for each which side of the edge
is the inside/filled side. When the outer contour is walked, it seems like I
could record the inside info. I guess when the inner contour is found, its
inside sense is reversed (inside is above the top). But how do I know if the
next contour is inside another? Maybe shoot out a line and brute-force
intersect it with all the segments in all the other contours? If every contour
has an extra segment when the intersections are computed, this may not be as
crazy as it seems.
Suppose each contour has one extra segment shooting straight up from the top
(or straight up from any point on the segment). This ray is not intersected
with the home contour, but is intersected with all other contours as part of
the normal intersection engine. If it is possible to get from the T values to
the other segments to the other contours, it would be straightforward to
count the contour crossings and determine if the home contour is in another
contour or not (if the count is even, not, if odd, is inside). By itself that
doesn't tell us about winding, but it's a start.
Since intersecting these rays is unrelated to computing other intersections,
it can be lazily done once the contour is found.
So
repeat the following
find the top segment of all contours
trace the outside, marking touching first and last segments as inside
continue tracing the touched segments with reversed outside/inside sense
once the edges are exhausted, remaining must be disjoint contours
send a ray from a disjoint point through all other contours
count the crossings, determine if disjoint is inside or outside, then continue
===
On Quadratic (and Cubic) Intersections
Currently, if only the end points touch, QuadracticIntersections does a lot of
work to figure that out. Can I test for that up front, then short circuit the
recursive search for the end points?
Or, is there something defective in the current approach that makes the end
point recursion go so deep? I'm seeing 56 stack frames (about 28 divides, but
thankfully, no splits) to find one matching endpoint.
Bezier curve focus may allow more quickly determining that end points with
identical tangents are practically coicident for some range of T, but I don't
understand the math yet to know.
Another approach is to determine how flat the curve is to make good guesses
about how far to move away in T before doing the intersection for the remainder
and/or to determine whether one curve is to the inside or outside of another.
According to Mike/Rob, the flatness for quadratics increases by 4 for each
subdivision, and a crude guess of the curvature can be had by comparing P1 to
(P0+P2)/2. By looking at the ULPS of the numbers, I can guess what value of
T may be far enough that the curves diverge but don't cross.
|
