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
|
# General algorithms required
1. curve/curve intersections
2. curve/surface intersections
3. surface/surface intersections
# Types of surface intersection algorithms
1. subdivision -- if subdivision is stopped too early, this method can miss small loops or lead to incorrect connectivity in the presence of singularities. Synder 1992 improved this method by using an algebraic representation and using interval arithmetic.
2. lattice evaluation -- these methods decompose the problem into smaller low-dimensional geometric complexity problems such as curve-surface intersections (Rossignac and Requicha 1987). This is followed by connecting the discrete points into curves. Determining the discrete step size is hard and can miss finding all of the small loops and singularities in a problem.
3. analytic methods -- these methods are usually limited to very specific intersection scenarios.
4. marching methods -- the idea behind marching methods is to do an analytic formulation of intersection curves, determination of a starting point on each component, and the use of local geometry to trace out the curve. The intersection curve can be defined implicitly as an algebraic set based on the surface equations, as a curve of zero distance between the two surfaces, or as a vector field (Hoffmann 1990; Kriezis et al. 1990b; Cheng 1989). Tracing can be done on the intersection curve in higher dimensions or on its projection in the plane. According to Hoffmann [1990], the projection results in a high-degree formulation and its computation can be inefficient and numerically unreliable. To circumvent these problems, a representation based on an unevaluated determinant was introduced in Manocha and Canny [1991].
The components of an intersection curve consist of boundary segments
and closed loops. Start points on the boundary segments are obtained by
curve-surface intersections [Sederberg and Nishita 1991]. Many techniques
have appeared over the last few years to detect closed loops on the
intersection curve.2 They are based on bounds on Gauss maps, and subdi-
vide each surface until sufficient conditions for the nonexistence of loops
are satisfied. These algorithms work very well to isolate cases with no loops
only if the surfaces are relatively flat. However, in the presence of small
loops or singularities, the algorithm becomes slow.
Most algorithms use the local geometry of the curve coupled with
quasi-Newton methods [Bajaj et al. 1988; Barnhill and Kersey 1990] for
tracing. These methods do not converge well sometimes [Field and Field
1992], and many issues related to choice of step size to prevent component
jumping are still open. Therefore, most implementations use very conserva-
tive step sizes for tracing and this slows down the algorithm. Overall,
current tracing algorithms are not considered robust [Snyder 1992].
The singularities on the intersection curve can be classified in terms of
solutions of algebraic equations. However, no methods are known in the
literature that can efficiently compute them for high degree surfaces (such
as bicubic patches) and classify the curve branches in their neighborhood.
??? boolean operations using polyhedral approximations
# An efficient surface intersection algorithm based on lower-dimensional formulation
Our algorithm formulates the intersection problem algebraically, computes
the projection of the intersection curve as an algebraic plane curve, and
evaluates it. The projection is represented as the singular set of a bivariate
matrix polynomial and the algorithm uses matrix computations to trace the
curve. Tracing is a geometric operation and evaluating the curve in the
plane reduces its geometric complexity. The loops of the intersection curve
are characterized algebraically and computed using curve–surface intersec-
tions followed by complex tracing. The tracing algorithm employs domain
decomposition and the use of inverse power iterations. Domain decomposi-
tion provides a natural procedure to compute the step size and prevent
component jumping. This is a major advantage of our tracing algorithm
since incorrect connectivity of the various curve components was considered
a flaw in traditional marching methods.
The rest of the article is organized in the following manner. We review
the problem formulation and the representation of the intersection curve in
terms of matrices in Section 2. The special case handling of parameteriza-
tions with base points is discussed in Section 3. Section 4 describes
algorithms to compute start points on every curve component including
loops. The tracing algorithm using domain decomposition is presented in
Section 5. Methods for identification of singularities on the intersection
curve are given both in Sections 5 and 6. Section 7 outlines the main issues
concerning robustness and efficiency, and the contributions of our algo-
rithm. Application of our intersection algorithm to large-sized models is
presented in Section 8. This is followed by a discussion on the performance
of our algorithm on these models in Section 9. We finally conclude in
Section 10.
# Glossary
intersection curve
b-splines
NURBS - non-uniform rational b-splines
# Marching bounding boxes
http://kingkong.me.berkeley.edu/~adarsh/Papers/TVCG09.pdf
# CATIA
"CATIA uses polyhedral approximations for intersection and boundary computations. These methods suffer from from incorrect results and data proliferation."
# "Exact" (Krishna)
http://www2.research.att.com/~krishnas/MY_PAPERS/exact.pdf
1. Intersection curve computation (for each pair of patches):
1.1. Obtain the intersection curve(s) between the two patches.
1.2. Find the points where the intersection curve meets the patch boundary.
1.3. Decompose the intersection curve into a set of monotonic curves.
1.4. Find the points where the intersection curve meets the trimming boundary and subdivide the trimming and intersection curves.
1.5. Compute adjacency information for remaining intersection curves.
2. Curve merging and boundary computation (for each patch):
2.1. Merge intersection curves together in each patch to partition the patch domain.
2.2. Compute the adjacency graph and components separated by intersection curves.
2.3. Shoot rays from one solid to the other solid to classify components as inside or outside the solid.
2.4. Propogate the information from the previous step in the adjacency graph to find the final solid.
# TVCG09
Performing efficient NURBS modeling operations on the GPU
http://kingkong.me.berkeley.edu/~adarsh/Papers/TVCG09.pdf
TVCG09 uses the GPU and textures to compute a marching bounding box approximation of intersection curves. The intersection points are computed by a triangle approximation and then stitched together into polylines.
# Watertight NURBS
from a conversation in \#brlcad with the military...
13:44 < starseeker> kanzure: if that "Watertight Trimmed NURBS" paper is right, it's actually impossible to get exact curve solutions in general without being willing to distort the NURBS surfaces in the neighborhood of the intersection
13:45 < kanzure> but what about from a mechanical engineering perspective: approximations of shape intersections leads to bad modeling results, doesn't it?
13:46 < starseeker> my guess is that would depend on the exact definition of "approximations" and "bad results"
13:48 < starseeker> kanzure: do any existing CAD systems claim to solve intersections exactly? (Sounds like ACIS at least doesn't, from what you were saying)
13:50 < kanzure> some academic papers claim to solve intersections in an exact/algebraic manner
13:50 < kanzure> caveat: please don't take my word as an exhaustive survey :P
13:50 < starseeker> usually with a considerable (as in prohibitive) performance hit though
watertight nurbs paper - http://www.tsplines.com/technology/WTN.pdf
14:39 < kanzure> i suppose as long as the values are within the tolerances i previously configured, i don't really care what the intersection of two shapes looks like
14:40 <@jblake> arguably, you should be aiming for within the square of the tolerance or some such smaller limit in order to avoid magnification of errors from the interactions between approximated surfaces
|
