 |
Claims  |
|
|
We claim:
1. A recursive subdivision process performed in a solid-modeling system
including computer means for performing a plurality of functions and
storage means for storing data, said process for operating said computer
means to identify intersections between the surfaces of a pair of solid
models A and B represented by digital data surface descriptions stored in
said storage means, said digital data surface descriptions produced by
computer-aided design, said models representing, for example, articles of
manufacture, machine parts or the path described by the movement thereof
through space, each said surface description of each said model subdivided
into a plurality of surface patches S each represented by a corresponding
digital data surface path description stored in a first pool of surface
patch description pairs in said storage means, each said pair including
one surface patch description from each of said models A and B, said
process for determining by recursive subdivision which said surface patch
description pairs in said first pool have a transversal intersection to
produce a second pool of surface patch description pairs each known to
have a transversal intersection, said process further determining when
each of a said pair of surface patch descriptions in said first pool have
been subdivided to a limit specified by a predetermined criterion to
produce a third pool of surface patch description pairs wherein both
surface patch descriptions of said pair are known to meet said
predetermined criterion, said process comprising causing said computer
means to perform the steps of:
(1) reading said storage means to retrieve from said first pool a pair of
digital data patch descriptions representing, respectively a pair of
surface patches S.sub.A and S.sub.B of said models A and B;
(2) operating on said retrieved patch descriptions to perform a mutual
point exclusion test for said surface patches S.sub.A and S.sub.B and if
no mutual points exist terminating further intersection identifying
processing on said pair and returning to step 1 to retrieve from said
first pool further patch descriptions representing a new pair of surface
patches S.sub.A and S.sub.B for processing;
(3) operating on said retrieved patch descriptions to determine if said
pair of surface patches S.sub.A and S.sub.B are transversal and if
transversal terminating further subdivision of said pair and going to step
6;
(4) operating on said retrieved patch descriptions to test each of said
surface patches S.sub.A and S.sub.B against a predetermined criterion and
if said criterion is met for both said surface patches classifying said
pair in said third pool as having met said criterion whereby the
intersection set of said pair can be approximated and terminating further
subdivision on said surface patches S.sub.A and S.sub.B and returning to
step 1 to retrieve from said first pool further patch descriptions
representing a new pair of surface patches S.sub.A and S.sub.B for
processing;
(5) operating on said retrieved patch descriptions to subdivide one or both
of said surface patches S.sub.A and S.sub.B if they do not meet said
predetermined criterion, said patch or patches subdivided into a further
plurality of patches to create a plurality of new surface patch pairs
representing new patch descriptions, and storing the digital data patch
descriptions representing said new pairs in said first pool in said
storage means for further processing and returning to step 1 to retrieve
from said first pool further patch descriptions representing a new pair of
surface patches S.sub.A and S.sub.B for processing; and
(6) operating on said retrieved patch descriptions for said pair of surface
patches S.sub.A and S.sub.B determined to be transversal to perform a test
to detect intersection between said pair and if an intersection of said
pair is detected classifying said pair of surface patches S.sub.A and
S.sub.B in said second pool as having a transversal intersection whereby
it is known that said pair intersect in a curve if they intersect so that
the intersection set can be determined without further subdivision, and
returning to step 1 to retrieve from said first pool further patch
descriptions representing a new pair of surface patches S.sub.A and
S.sub.B for processing.
2. A process according to claim 1 wherein said test performed in step 6 is
a boundary test.
3. A process according to claim 2 further including the step of operating
on said retrieved data for said pair of surface patches S.sub.A and
S.sub.B determined to have a transversal intersection to compute a
representation of the intersection of the intersection of said pair.
4. A process according to claim 1 further including the step of operating
on said retrieved data for said pair of surface patches S.sub.A and
S.sub.B determined to have a transversal intersection to compute a
representation of the intersection of said pair.
5. A process according to claim 1 wherein said predetermined criterion of
said step (4) is a patch flatness criterion.
6. A process according to claim 1 including the step of operating on said
data for said pair of surface patches S.sub.A and S.sub.B which meet said
predetermined criterion to approximate the surface patches S.sub.A and
S.sub.B to a geometry for which the intersection set can be computed and
computing a representation of said intersection set and storing it in said
storage means.
7. A process according to claim 1, 2, 4, 3, 5 or 6 wherein said surface
patches S.sub.A and S.sub.B are represented by said data in the form of
boundary representations.
8. A process according to claim 1, 2, 4, 3, 5 or 6 wherein said surface
patches S.sub.A and S.sub.B are represented by said data in the form of
faceted representations.
9. A process according to claim 1, 2, 4, 3, 5 or 6 wherein said surface
patches S.sub.A and S.sub.B are represented by said data so that it is
possible to extract information about said surface patches whose disjoint
union comprises the bounding surfaces of the respective objects A and B.
10. A process according to claim 1 wherein said pair of surface patches
S.sub.A and S.sub.B are determined not to be transversal if W.sub.A
.andgate.W.sub.B =.0. wherein S.sub.A and S.sub.B are two smooth surfaces
in R.sup.3, and W.sub.A, W.sub.B are subsets of unit spherical surface
S.sup.2 around the origin S.sup.2 containing points x.sub.A and x.sub.B
such that
##EQU18##
wherein .delta..sub.A and .delta..sub.B are bounds on the sets of normals
N(S.sub.A) and N(S.sub.B), respectively.
11. A process according to claim 10 wherein said W.sub.A .andgate.W.sub.B
=.0. is determined to be true if D(x.sub.A, x.sub.B)>.delta..sub.A
+.delta..sub.B wherein x.sub.A .epsilon.N(S.sub.A) and x.sub.B
.epsilon.N(S.sub.B).
12. A process according to claim 11 wherein said bounds .delta..sub.A and
.delta..sub.B on N(S.sub.A) and N(S.sub.B) for said surface patches
S.sub.A and S.sub.B are computable so that an x.sub.A .epsilon.N(S.sub.A)
and a .delta..sub.A are computable such that D(x.sub.A,
x).ltoreq..delta..sub.A, x.delta.N(S.sub.A) and an x.sub.B
.delta.N(S.sub.B) and a .delta..sub.B are compatible such that D(x.sub.B,
x).ltoreq..delta..sub.B, x .epsilon.N(S.sub.B).
13. A process according to claim 12 wherein said step (3) of determining
whether said pair of surface patches S.sub.A and S.sub.B are transversal
includes causing said computer means to operate on said retrieved data to
perform the steps of:
(a) computing x.sub.A and x.sub.B for each of said surface patches S.sub.A
and S.sub.B, respectively, wherein x.sub.A and x.sub.B are elements of the
respective sets of normals N(S.sub.A) and N(S.sub.B) to said patches
S.sub.A and S.sub.B ;
(b) computing D(x.sub.A,x.sub.B)=.sqroot.1-(x.sub.A,x.sub.B)
(c) computing .delta..sub.A and .delta..sub.B for each of said surface
patches S.sub.A and S.sub.B respectively wherein .delta..sub.A and
.delta..sub.B are bounds on the sets of normals N(S.sub.A) and N(S.sub.B),
respectively; and
(d) determining if D(x.sub.A,x.sub.B)>.delta..sub.A +.delta..sub.B which if
true indicates that said surface patches S.sub.A and S.sub.B are
transversal.
14. A process according to claim 13 wherein said surface patches S.sub.A
and S.sub.B are defined parametrically by said retrieved data such that:
S=f(0,.phi.)=(x(.theta.,.phi.), y(.theta.,.phi.), z(.theta.,.phi.)),
(.theta., .phi.).epsilon.D
where x, y, z
are evaluated functions and D is the domain of said patch.
15. A process according to claim 14 said bounds on the set of normals over
said patches S.sub.A and S.sub.B are each defined as a real number
.epsilon. such that .epsilon..gtoreq.D(N.sub.x (S), N.sub.x (S))
x.epsilon.S wherein x=f(.theta.,.phi.) in S, and further wherein each said
bound is the one for which .epsilon.=max.sub.x.epsilon.S D(N.sub.x (S),
N.sub.x (S)).ltoreq..sqroot.1-<w,n.sub..theta. .times.n.sub..phi. >.sup.2
wherein w is a vector denoting the maximum variation of N.sub.x (S) over S
from N.sub.x (S) and x=f(.theta.,.phi.),n.sub..theta. =f.sub..theta.
(.theta.,.phi.), n.sub..theta. =f.sub..phi. (.theta.,.phi.), and <,>
denotes inner products, and x deniotes cross product.
16. A process according to claim 15 wherein w is computed by computing
.epsilon..sub..theta. and .epsilon..sub..phi. and then solving the systems
##EQU19##
for the one w which minimizes <w, n.sub..theta. .times.n.sub..phi. >.
17. A process according to claim 16 wherein .epsilon..sub..theta. and
.epsilon..sub..phi. are equal to
.epsilon..sub..theta. =max.sub.(.theta.,.phi.).epsilon.D) D(f.sub..theta.
(.theta.,.phi.),f.sub..theta.
(.theta.,.phi.))=(.epsilon.(f.sub..theta.))/.vertline.f.sub..theta.
.vertline.
and
.epsilon..sub..phi. =max.sub.(.theta.,.phi.).epsilon.D D(f.sub..phi.
(.theta.,.phi.),f.sub..phi.
(.theta.,.phi.))=(.epsilon.(f.sub..phi.))/.vertline.f.sub..phi.
.vertline..
wherein D is domain of the parametric patches S.sub.A and S.sub.B.
18. A process according to claim 17 wherein .epsilon..sub..theta. and
.epsilon..sub..phi. are computed using Taylor series expansion and
interval arithmetic wherein
##EQU20##
wherein .parallel..theta.-.theta..parallel. and
.parallel..phi.-.phi..parallel. are known for one of said patches S.sub.A
and S.sub.B from their respective domains D while
##EQU21##
are computed using interval arithmetic on the symbolic expression for
x.sub..theta..theta. derivable from f(.theta.,.phi.), and further wherein
.epsilon.(y.sub..theta.), .epsilon.(z.sub..theta.),
.epsilon.(x.sub..phi.), .epsilon.(y.sub..phi.), .epsilon.(z.sub..phi.) are
computed in a similar manner to .epsilon.(x.sub..theta.).
19. A method according to claim 1 further wherein if {S.sub.i } is a
sequence of surface patches S.sub.A or S.sub.B, such that S.sub.j is a
subpatch of S.sub.j-1 and diameter (S.sub.i).fwdarw.0 as i.fwdarw..infin.,
and such that .delta..sub.i is the sequence of computed bounds on N(S)
such that D(x.sub.i, x).ltoreq..delta..sub.i, x.epsilon.N(S.sub.i) for
some sequence of points {x.sub.i } in S.sup.2, then
lim.sub.i.fwdarw..infin. .delta..sub.i =0 so that said subdivision process
can converge to arbitrarily fine approximations of the integration sets.
20. In a subdivision process performed in a solid-modeling system including
storage means for storing data to identify an intersection between a pair
of surface patches S.sub.A and S.sub.B each representing, respectively, a
portion of the surface of a pair of solid-models A and B represented by
digital data surface descriptions stored in said storage means, said
digital data surface descriptions produced by computer-aided design, said
models representing, for example, articles of manufacture, machine parts
or the path described by the movement thereof through space, said surface
patches S.sub.A and S.sub.B each repreented by a corresponding digital
data surface patch description stored in a first pool of surface patch
description pairs in said storage means, each said pair including one
surface patch description from each of said models, wherein said process
operates on said patch descriptions to subdivide said pair of surface
patches in said first pool unless mutual point exclusion is proved or
unless each surface of said pair meets a predetermined criterion
permitting the intersection set of said pair to be determined from
approximations of the geometry of each of said surface patches, the
improvement comprising:
operating on said digital data surface patch descriptions representing said
pair for those said pair of surface patches S.sub.A and S.sub.B for which
mutual point exclusion is not proved to determine if said pair of surface
patches are transversal, whereby it is known that said pair intersects in
a curve if intersecting, and if transversal terminating further
subdivision of said pair and operating further on said retrieved patch
descriptions to perform a test to detect intersection between said pair
and if an intersection is detected classifying said pair as having a
transversal intersection to produce a second pool of surface patch
description pairs each known to have a transversal intersection whereby a
description of the intersection of said pairs in said second pool can be
determined by exploiting the known curve intersection geometry of said
pair.
21. A process according to claim 20 wherein said test to detect
intersection is a boundary test.
22. A process according to claim 21 including the step of operating on said
retrieved data for said pair of surface patches S.sub.A and S.sub.B
determined to have a transversal intersection to compute a representation
of the intersection of said pair.
23. A process according to claim 20 further including the step of operating
on said retrieved data for said pair of surface patches S.sub.A and
S.sub.B determined to have a transversal intersection to compute a
representation of the intersection of said pair.
24. A process according to claim 20 wherein said predetermined criterion is
a patch flatness criterion.
25. A process according to claim 20 including the step of operating on said
data for said pair of surface patches S.sub.A and S.sub.B which meet said
predetermined criterion to approximate the surface patches S.sub.A and
S.sub.B to geometry for which the intersection set can be computed and
computing a representation of said intersection set and storing it in said
storage means.
26. A process according to claims 20, 21, 23, 22, 24 or 18 wherein said
surface patches S.sub.A and S.sub.B are represented by said data in the
form of boundary representations.
27. A process according to claim 20, 21, 25, 22, 24 or 25 wherein said
surface patches S.sub.A and S.sub.B are represented by said data in the
form of faceted representations.
28. A process according to claim 20, 21, 25, 22, 24 or 25 wherein said
surface patches S.sub.A and S.sub.B are represented by said data so that
it is possible to extract information about said surface patches whose
disjoint union comprises the bounding surfaces of the respective objects A
and B.
29. A process according to claim 20 wherein in said pair of surface patches
S.sub.A and S.sub.B are determined not to be transversal if W.sub.A
.andgate.W.sub.B =.0. wherein S.sub.A and S.sub.B are two smooth surfaces
in R.sup.3, and W.sub.A, W.sub.B are subsets of unit spherical surface
S.sup.2 around the origin S.sup.2 containing points x.sub.A and x.sub.B
such that
##EQU22##
wherein .epsilon..sub.A and .epsilon..sub.B are bounds on the sets of
normals N(S.sub.A) and N(S.sub.B), respectively.
30. A process according to claim 29 wherein said W.sub.A .andgate.W.sub.B
=.0. is determined to be true if D(x.sub.A,x.sub.B)>.epsilon..sub.A
+.epsilon..sub.B wherein x.sub.A .epsilon.N(S.sub.A) and x.sub.B
.epsilon.N(S.sub.B).
31. A process according to claim 30 wherein said bounds .epsilon..sub.A and
.epsilon..sub.B on N(S.sub.A) and N(S.sub.B) for said surface patches
S.sub.A and S.sub.B are computable so that an x.sub.A .epsilon.N(S.sub.A)
and a .epsilon..sub.A are computable such that
D(x.sub.A,x).ltoreq..epsilon..sub.A, x.epsilon.N(S.sub.A) and an x.sub.B
.epsilon.N(S.sub.B) and a .epsilon..sub.B are computable such that
D(x.sub.B, x).ltoreq..epsilon..sub.B, x.epsilon.N(S.sub.B).
32. A process according to claim 31 wherein in determining whether said
pair of surface patches S.sub.A and S.sub.B are transversal includes
operating on said retrieved data to perform the steps of:
(a) computing x.sub.A and x.sub.B for each of said surface patches S.sub.A
and S.sub.B, respectively, wherein x.sub.A and x.sub.B are elements of the
respective sets of normals N(S.sub.A) and N(S.sub.B) to said patches
S.sub.A and S.sub.B ;
(b) computing D(x.sub.A,x.sub.B)=.sqroot.1-<x.sub.A,x.sub.B >
(c) computing .epsilon..sub.A and .epsilon..sub.B for each of said surface
patches S.sub.A and S.sub.B respectively wherein .epsilon..sub.A and
.epsilon..sub.B are bounds on the sets of normals N(S.sub.A) and
N(S.sub.B), respectively; and
(d) determining if D(x.sub.A,x.sub.B)>.epsilon..sub.A +.epsilon..sub.B
which if true indicates that said surface patches S.sub.A and S.sub.B are
transversal.
33. A process according to claim 32 wherein said surface patches S.sub.A
and S.sub.B are defined parametrically by said retrieved data such that:
S=f(.theta.,.phi.)=(x(.theta.,.phi.), y(.theta.,.phi.)),
(.theta.,.phi.).epsilon.D
where x, y, z are evaluated functions and D is the domain of said patch.
34. A process according to claim 33 wherein said bounds on the set of
normals over said patches S.sub.A and S.sub.B are each defined as a real
number .epsilon. such that .epsilon..gtoreq.D(N.sub.x (S), N.sub.x (S))
x.epsilon.S wherein x=f(.theta.,.phi.) in S, and further wherein each said
bound is the one for which .epsilon.=max.sub.x.epsilon.S D(N.sub.x (S),
N.sub.x (S)).ltoreq..sqroot.1-<w,n.sub..theta. .times.n.sub..phi. >.sup.2
wherein w is a vector denoting the maximum variation of N.sub.x (S) over S
from N.sub.x (S) and x=f(.theta.,.phi.),n.sub..theta. =f.sub..theta.
(.theta.,.phi.), n.sub..phi. =f.sub..phi. (.theta.,.phi.), and <,> denotes
inner products, and x denotes cross product.
35. A process according to claim 34 wherein w is computed by computing
.epsilon..sub..theta. and .epsilon..sub..phi. and then solving the systems
<w,n.sub..theta. >.noteq..epsilon..sub..theta.
<w,n.sub..phi. >.noteq..epsilon..sub..phi.
.parallel.w.parallel..sub.2 =1
for the one w which minimizes <w, n.sub..theta. >n.sub..phi.>.
36. A process according to claim 35 wherein .epsilon..sub..theta. and
.epsilon..sub..phi. are equal to
.epsilon..sub..theta. =max.sub.(.theta.,.phi.).epsilon.D) D(f.sub..theta.
(.theta.,.phi.),f.sub..theta.
(.theta.,.phi.))=(.epsilon.(f.sub..theta.))/.vertline.f.sub..theta..vertli
ne.
and
.epsilon.=max .sub.(.theta.,.phi.).epsilon.D D(f.sub..theta.
(.theta.,.phi.),f.sub..phi.
(.theta.,.phi.))=(.epsilon.(f.sub..phi.)/.vertline.f.sub..phi. .vertline..
wherein D is domain of the parametric patches S.sub.A and S.sub.B.
37. A process according to claim 36 wherein .epsilon..sub..theta. and
.epsilon..sub..phi. are computed using Taylor series expansion and
interval arithmetic wherein
##EQU23##
wherein .parallel..theta.-.theta..parallel. and
.parallel..phi.-.phi..parallel. are known for one of said patches S.sub.A
and S.sub.B from their respective domains D while
##EQU24##
are computed using interval arithmetic on the symbolic expression for
x.sub..theta..theta. derivable from f(.theta., .phi.), and further wherein
.epsilon.(y.sub..theta.), .epsilon.(z.sub..theta.),
.epsilon.(x.sub..phi.), .epsilon.(y.sub..phi.), .epsilon.(z.sub..phi.) are
computed in a similar manner to .delta.(x.sub..theta.).
38. A method according to claim 20 further wherein if {S.sub.i } is a
sequence of surface patches S.sub.A or S.sub.B, such that S.sub.j is a
subpatch of S.sub.j-1 and diameter (S.sub.i).fwdarw.0 as i.fwdarw..infin.,
and such that .epsilon..sub.i is the sequence of computed bounds on N(S)
such that D(x.sub.i, x).ltoreq..delta..sub.i, x.epsilon.N(S.sub.i) for
some sequence of points {x.sub.i } in S.sup.2, then
lim.sub.i.fwdarw..infin. .epsilon..sub.i =0 so that said subdivision
process can converge to arbitrarily fine approximations of the integration
sets. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
TECHNICAL FIELD OF THE INVENTION
The present invention pertains generally to the fields of CAD/CAM and
robotics and more particularly to determination of intersections between
surfaces in a solid-modeling system.
BACKGROUND OF THE INVENTION
Solid-modeling in the realm of computer-aided shape design has rapidly
emerged as one of the most important and challenging fields of
manufacturing research and development. Although activity in this area was
initiated by computerized drafting systems serving as no more than
electronic drafting tables, its applications today exist in areas ranging
from realistic image generation to CAD/CAM and robotics.
The roots of solid-modeling technology can be traced back to the
computer-aided drafting systems that were developed during the early 70's;
these systems--aptly called wireframe systems--could only handle the
drafting of primitive points and curves. Soon, however, the need was felt
for extending this facility to not only drafting with CAD systems but
designing with them. Since solid parts cannot be modeled unambiguously by
only points and lines, drafting systems were soon replaced by the so
called solid-modeling systems. Today there are a host of solid-modeling
systems available from commercial vendors or from universities.
The use of solid-modeling systems, however, has not been able to graduate
much beyond producing shaded-graphics and computing mass-properties. Even
for these simple applications, the domain of the modeling system is
severely restricted. Amongst the variety of reasons that can be cited for
the break in the previously phenomenal growth-rate of this technology is
the fact that the algorithms used for various processing needs within
solid-modeling systems are either not efficient, not reliable, or not
general enough in their domain of application.
The ability to compute the intersection of two surfaces usually forms the
heart of a solid-modeling system. Such processing is useful not only in
building an internal representation for the object from its description,
but also in applications such as collision-detection, that are built upon
it. Many algorithms have been proposed to compute intersections of
surfaces. However, the lack of a computationally efficient algorithm
applicable to a wide range of surfaces has made the application of solid
modeling systems infeasible in areas such as robotics, where complex
processing operations such as sweeping are required.
Reliable intersection algorithms are known for quadric surfaces but they
are not applicable to other surfaces such as bicubic patches or B-spline
surfaces since they capitalize heavily on properties specific to the class
of quadric surfaces. On the other hand, there are edge-tracking algorithms
implemented in solid-modeling systems such as BUILD, ROMULUS and TIPS-1
that are potentially applicable to a wide variety of surfaces, but they
need an initial point on each component of the intersection set before
they can trace it out. Since there are no known reliable methods to even
determine the number of components of the intersection set in general,
these algorithms tend to be unreliable. In general, each algorithm has
some advantages and disadvantages; there is no clear supremacy of any one
intersection algorithm over the others and research continues on almost
all of them.
Algorithms designed to compute intersections of surfaces need to satisfy
certain criteria that arise in the context of solid-modeling. Some of
these considerations are generality, reliability, accuracy, robustness and
speed. An intersection algorithm should be general enough to handle as
wide a variety of surfaces as exists in the domain of a solid-modeling
system. For systems that model all surfaces under a uniform scheme the
criterion is met automatically by any one intersection algorithm. However,
for systems that use surface-specific properties in order to design
special purpose, high speed algorithms, the amount of work required to
include a new surface in the modeling domain can be prohibitive. This
inhibits the upward expansion of a solid-modeling system and supports, at
best, a very constrained modeling environment.
The intersection for geometric entities may be invoked in a solid-modeling
environment towards two different ends:
1. to detect the intersection of two solids--here only a boolean result is
desired--or
2. to construct a representation of the intersection set from the
representations of the intersection solids.
Lack of reliability has different implications in the two above cases.
For purely detection purposes, reliability is important from the point of
view of functionality. For example, in the automatic generation of
numerical code for machining, a rapid traversal command may be inserted
along a path where no collision with the workpiece or the fixtures is
detected. However, if, in fact, there is a collision, then the tool is
liable to break since tools are typically not designed to handle cutting
at feed-rates of the order of rapid-traversal speeds. Similarly
reliability is crucial in applications such as robot-motion-simulation and
part-assembly verification systems.
When the intersection operation is used to construct a representation of
the intersection set from the representation of the intersecting solids
then unreliable intersections can cripple the algorithm by creating
inconsistent topological data which do not permit proper termination of
the algorithm. Considerable care therefore needs to be taken to detect all
components of the intersection set. Algorithms suffering from this problem
can be found in solid-modeling systems such as TIPS-1. The property of a
solid-modeling system that prevents a system from terminating due to such
internal errors, is also referred to in literature as robustness.
An intersection algorithm that computes approximate intersections from
object representations does so only with a certain accuracy. The
inaccuracies due to the algorithm itself are different from and in
addition to those due to roundoff errors in floating point digital
arithmetic. Such systems must then be able to compute how close the
approximations are to the actual intersection sets. Different definitions
of "closeness" may be formulated--each meaningful in the context of a
desired application. One could, for example, call an intersection small if
the diameter of each face is smaller than a defined .epsilon.. On the
other hand it may be called negligible if two planes can be determined
that are some .epsilon. apart and contain the intersection set between
them.
The need to determine whether an intersection is meaningful or not exists,
for example, in keeping topological information consistent and in
applications such as part assembly verification. Accuracy measures are
also needed in order to estimate faithfulness of representation under
various operations. In a flexible modeling system, intersection sets may
be further operated on by functions such as sweep, intersect, etc. The
representation of the final object so created may be geometrically--and
even topologically--far from its actual representation because of
accumulation of inaccuracies and magnifications thereof during operations.
Such magnifications occur, for example, when points near a singularity are
mapped; small errors in the points can get magnified to appreciable
amounts in such operations.
The desire for high speed intersection operations, although practically
contradictory to the idea of reliable intersections, is almost as
important. Speed is essential for an effective design and manufacturing
environment based on solid-modeling. In applications such as NC machining,
thousands of swept volumes are typically created--one due to each cutter
move. Each one of these is treated as a solid and subtracted from the
workpiece. Constructing the actual representation of the finished
workpiece from such complex solids can take upwards of 2 to 3 hours on a
high speed mainframe.
The existing methods for intersections of solids may broadly be classified
into two categories: exact and approximate methods. This categorization is
not very rigid and is based broadly on the level of approximations that
the intersection algorithm may assume. It is emphasized that this
distinction is fairly nebulous and a wide-variety of algorithms pass off
as what is known in literature as "semi-analytical methods".
The methods that fall into the exact method category are those that derive
an exact representation of the intersection set through algebraic or
semi-algebraic means from exact representations of the intersecting
surfaces. They incorporate techniques from algebraic geometry and
numerical linear-algebra to yield algorithms that are systematic are
reliable. The substitution method, quantifier elimination method, Levin's
Algorithm and Ocken's Method, are examples of the exact method
intersection algorithm.
In contrast with the exact methods, the number of algorithms in the
category of approximate methods is much larger. Also these methods are
much more widely used in current systems because they are easier to encode
and often more general. However, this is almost always at the cost of
reliability and accuracy. Some algorithms are based on fairly
sophisticated mathematical techniques while others are purely searching
schemes adapted for the intersection problem. One numerical method, known
as Morgan's Method and incorporated into GMSolid, has been found
successful in practice. However, the method is good only for the
intersections of three surfaces that yield a finite set of points and is
not meant to compute a representation of the intersection of two surfaces.
It can be used to compute a set of points along an edge of intersection,
but it is not clear if it does so reliably and efficiently. Moreover, the
method is limited to algebraic surfaces and degrades very fast with the
degree of equations involved.
Also in the class of approximate methods are the polygonal algorithms.
These algorithms compute intersections of a faceted representation (a
piece-wise linear approximation) of the intersection surfaces. The
computations involved are simple and fast, and hence, numerous commercial
geometric modeling systems (such as Geomod, CITIA etc.) based on this
intersection algorithm have cropped up. A very serious disadvantage of
this algorithm, however, is its lack of reliability and accuracy:
approximating badly oriented surface patches as flat polygons is subject
to serious pitfalls whereby erroneous results may be obtained.
Tracking algorithms are also in the approximate method category and use an
iterative procedure that assumes facilities such as computations of normal
vectors and computation of the distance of a point from a surface. The
main idea is that given a point x on the intersection edge, a good
estimate to the next one may be obtained by stepping out in the direction
of the tangent vector to the edge at x. Iterative techniques can then be
used to "pull" the point down to an actual intersection point.
The tracking method is very general, and has been implemented in geometric
modeling systems such as TIPS-1 and ROMULUS. The disadvantage of this
algorithm is again the lack of reliability: Firstly, it assumes that the
intersection set is actually an edge--in reality it may be only a point or
itself a surface. Secondly, it needs an initial point on each component of
the intersection set to start the tracking procedure. This has to be done
by some heuristic means. The method is in general inefficient as well
since the number since the "pulling" operation can be very expensive.
One other algorithm belonging to the class of approximate algorithms and
the one germane to the present invention is the subdivision algorithm. The
subdivision algorithm for computing intersections of surfaces is based on
the divide and conquer paradigm. Given a surface and a processing task,
the idea is to recursively subdivide the surface into smaller and smaller
patches until each patch is small enough that processing a geometric
approximation to the patches instead of the patches themselves yields
results accurate to within acceptable bounds. This approach was first used
by Catmull (See E Catmull, "A subdivision Algorithm for Computer Display
of Curved Surfaces," University of Utah Comp. Sci Dept. UTEC-CSC-74-133,
1974), in generating shaded images of curved surfaces. A very natural
extension of this scheme was found in computing intersections of curved
surfaces. The intersection algorithm was first developed for B-spline
surfaces (See Jeffrey M. Lane and Richard R. Riesenfeld, "A Theoretical
Development for the computer Generation and Display of Piecewise
Polynomial Surfaces," Transactions on Pattern Analysis and Machine
Intelligence, vol PAMI-2, no. 1, January 1980), and later extended to
include general parametric surfaces (See S. P. Madur, P. A. Koparkar,
"Interval Methods for Processing Geometric Objections", IEEE CG&A,
February 1984). The subdivision algorithm is very general in terms of the
surfaces it can be used for. The disclosures of the above three
publications are hereby incorporated by reference herein with particular
respect to computation of intersections in the Madur publication.
A big advantage of the subdivision algorithm for intersection of surfaces
lies in the fact that it works with a clear interface between the
intersection algorithm and representation schemes. Hence, it is not tied
to any representation scheme and is limited only by the existence of the
defined interface. In this respect it is similar to approximate schemes
such as the tracking method for computing intersections. Another advantage
of the intersection algorithm is its reliability: theoretically, since
surfaces can be subdivided to as small a size as possible, all
intersections can be found. However, as will be shown below the current
form of the algorithm cannot be both reliable and efficient.
The subdivision algorithm is capable of computing an arbitrarily close
approximation to the intersection set by subdividing the surfaces to finer
and finer levels. The prescribed way of controlling the closeness of the
approximation is by suitably changing the flatness criterion. It may be
noted, however, that in reported versions of the algorithm, the
quantitative relationship between these two measures has not been explored
or exploited.
A serious drawback of the subdivision algorithm is that, since in practice
infinite subdivisions are not possible and a linear approximation is used
at some stage, it can sometimes miss a component of the intersection set.
This becomes quite obvious if we assume that the surfaces shown in FIGS. 1
and 2 are flat to within the prescribed flatness criterion and follow the
steps of the subdivision algorithm. For the case in FIG. 1, the
intersection of the planar approximations to the surfaces will result in a
straight line closely approximating the actual curve of intersection. For
the situation in FIG. 2, however, such an approximation is not assured
because the curve of intersection is a closed curve lying entirely in the
interior of the surfaces. Interestingly, a curve with such a topology
cannot possibly be obtained by the intersection of planar polygons.
As explained above, for some applications an intersection such as the one
in FIG. 2 may be negligible. In fact, since the surfaces are flat to
within some predefined tolerance limit and it may be acceptable to neglect
intersections of such a nature. But for certain other applications, such
an intersection may not be negligible. For example, it may be required to
produce a new surface by sweeping the curve obtained by intersecting the
given surfaces. In this case, it is not the flatness but the diameter of
the intersection that has to be small for the intersection to be
negligible. In general, a reliable solid-modeling system cannot choose to
neglect such intersection.
To get around this problem, one may think of prescribing a more stringent
flatness criterion. This, however, is not a general solution since--as
emphasized by reported subdivision-algorithm implementations (See
Elizabeth G. Houghton, Robert F. Emnett, James D. Factor, and Chaman L.
Sabharwal, "Implementation of a divide-and-conquer method for the
intersection of parametric surfaces", Computer Aided Geometric Design, 2,
1985, 173-183--one can constuct a case as in FIG. 2 for any given flatness
criterion.
A surer remedy, motivated by the fact that computer arithmetic and real
life applications work only with finite precision, is to subdivide each
surface until the patches are smaller than some working precision. Another
approach on similar lines would be to subdivide each surface until it is
flat to within such a working precision. Once the new definition of
intersection based on the working precision has been incorporated into the
algorithm (mainly in the polygon-intersection procedure), it could
conceivably be made to yield approximations to the intersection set that
are accurate to around the working precision. However, without even going
into the details of implementation of such approaches, the following
objections can be raised against them. First, the initial approach will be
wasteful in general since it will subdivide surfaces intersecting as in
FIG. 1 to the same extent as surfaces in FIG. 2. In the latter case, some
new topological information may be uncovered by the refined subdivision.
However, the only result of refined subdivision for a situation as in FIG.
1 is to further improve the already good approximation of the edge of
intersection. Secondly, similar objection can be raised against the second
approach. The intersection for all cases will have to be computed to
working precision before the topological aspects--such as the number of
components of the intersection set--are known. This is clearly wasteful in
an application such as collision detection where it would be sufficient to
determine the existence or non-existence of any components. Thirdly, a
small tolerance would cause a proliferation of surface patches. Hence
intersections may be computed reliably, but only at a considerably cost in
terms of storage and computations.
SUMMARY OF THE INVENTION
The present invention provides apparatus and method of topology directed
subdivision of a pair of surfaces with the intent of computing their
intersection set. Accordingly, the present inv | | |
