[ Pobierz całość w formacie PDF ]
3
to the rst four equations is bounded by N = 2n 6n ,3 , where n is the
parametric degree of each surface. Similarly for two algebraic surfaces, the
problem of tangential intersection can be formulated as:
f x; y; z =0
g x; y; z =0 4.6
70
0 1 0 1
fx x; y; z gx x; y; z
B C B C
B C B C
B C B C
=
fy x; y; z gy x; y; z
B C B C
@ A @ A
fz x; y; z gz x; y; z
In this case, we obtain 4 equations in 3 unknowns after eliminating and
these equations correspond to an overconstrained system as well. These over-
constrained system is solved in a manner similar to that of parametric surfaces.
The rst two equations are of degrees n. To eliminate from the third equa-
tion, we get a polynomial equation of degree 2 n-1 due to cross multiplication
and taking partial with respect to x; y; z. The Bezout bound for the rst three
equations is N = n2 2n ,2 .
Boundary Intersection : Such intersections lie on the boundary curve of one
of the two surfaces. Say we are given a B ezier surface, de ned over the domain,
s; t 2 0; 1 0; 1 , we obtain the boundary curves by substituting s or t to be
0 or 1. The resulting problem reduces to solving the equations:
F s; 1 = G u; v 4:7
Other possible boundary intersections can be computed in a similar manner.
The intersection points can be easily computed using global methods. An ex-
ample has been shown in Figure 4.3 b
Two objects collide if one of these sets of equations, 4.5 or 4.7 for para-
metric surfaces and 4.6 for algebraic surfaces, have a common solution in their
domain.
In a few degenerate cases, it is possible that the system of equations 4.5
and 4.7 have an in nite number of solutions. One such example is shown for two
cylinders in Fig.4.4. In this case the geometric contact corresponds to a curve on each
surface, as opposed to a point. These cases can be detected using resultant methods
as well 55 .
71
Closest
Closest
Point Sets
Points
( b )
( a )
Figure 4.4: Closest features between two di erent orientations of a cylinder
4.3 Coherence for Collision Detection between
Curved Objects
In most dynamic environments, the closest features or points between two
moving objects change infrequently between two time frames. We have used this
coherence property in designing the expected constant time algorithm for collision
detection among convex polytopes and applied to non-convex polytopes as well. In
this section we utilize this coherence property along with the algebraic formulations
presented in the previous section for curved models.
4.3.1 Approximating Curved Objects by Polyhedral Mod-
els
We approximate each physical object with curved boundary by a polyhedra
or polygonal mesh . Such approximations are used by rendering algorithms utiliz-
72
ing polygon rendering capabilities available on current hardware. These polyhedral
models are used for collision detection, based on the almost constant time algorithm
utilizing local features. Eventually a geometric contact is determined by solving the
equations highlighted in the previous section. We use an -polytope approximation
for a curved surface. It is de ned as:
De nition: Let S be a surface and P is -polytope approximation, if for all points,
p on the boundary of polytope P, there is a point s on S such that k s ,p k .
Similarly for each point s on S, there is a point p on the boundary of P such that
k p ,s k .
An -polytope approximation is obtained using either a simple mesh gener-
ation algorithm or an adaptive subdivision of the surfaces. Given a user de ned ,
algorithms for generating such meshes are highlighted for parametric B-spline surfaces
in 36 and for algebraic surfaces in 44 . In our implementation we used an inscribed
polygonal approximation to the surface boundary.
We use the -polytope approximations for convex surfaces only. In such
cases the resulting polytope is convex as well. Often a curved model can be repre-
sented as a union of convex objects. Such models are represented hierarchically, as
described in Section 4.1.1. Each polytope at a leaf node corresponds to an -polytope
approximation.
4.3.2 Convex Curved Surfaces
In this section we present an algorithm for two convex spline surfaces. The
input to the algorithm are two convex B-spline surfaces say SA and SB and their
associated control polytopes. It is assumed that the surfaces have at least rst order
continuity. We compute an -polytope approximation for each spline surface. Let PA
and Pb be -polytope and -polytope approximations of SA and SB, respectively.
A B
If the objects do not collide, there may be no need to nd the exact closest
points between them but a rough estimate of location to preserve the property of
geometric coherence. In this case, we keep track of the closest points between PA
and PB. Based on those closest points, we have a good bound on the actual distance
73
between the two surfaces. At any instance let dp be the minimum distance between
PA and PB computed using the polyhedral collision detection algorithm . Let ds be
the minimum distance between the two surfaces. It follows from the -approximation:
dp , , ds dp: 4:8
A B
The algorithm proceeds by keeping track of the closest points between PA and PB and
updating the bounds on ds based on dp. Whenever dp + , we use Gauss Newton
A B
routines to nd the closest points between the surfaces SA and SB. In particular, we
formulate the problem: For Gauss Newton routines, we want to minimize the function
4
X
2
H s; t; u; v = Hi s; t; u; v ;
i=1
where Hi are de ned in 4.2 . We use Gauss-Newton algorithm to minimize H. The
initial guess to the variables is computed in the following manner.
We use the line, say LA;B, joining the closest points of PA and PB as an
initial guess to the line joining the closest points of SA and SB in terms of direction .
The initial estimate to the variables in the equations in 4.2 is obtained by nding the
intersection of the line LA;B with the surfaces, F s; t and G u; v . This corresponds
to a line-surface intersection problem and can be solved using subdivision or algebraic
methods 35, 55 . As the surfaces move along, the coe cients of the equations in 4.2
are updated according to the rigid motion. The closest points between the resulting
surfaces are updated using Gauss Newton routines. Finally, when these closest points
coincide, there is a collision.
In practice, the convergence of the Gauss Newton routines to the closest
points of SA and SB is a function of and . In fact, the choice of in the -polytope
A B
approximation is important to the overall performance of the algorithm. Ideally, as
! 0, we get a ner approximation of the curved surface and better the convergence
of the Gauss Newton routines. However, a smaller increases the number of features in
the resulting polytope. Though polyhedral collision detection is an expected constant
time algorithm at each step, the overall performance of this algorithm is governed by
the total number of feature pairs traversed by the algorithm. The latter is dependent
74
on motion and the resolution of the approximation. Consequently, a very small can
slow down the overall algorithm. In our applications, we have chosen as a function
of the dimension of a simple bounding box used to bound SA. In particular, let l
be dimension of the smallest cube, enclosing SA. We have chosen = l, where
[ Pobierz całość w formacie PDF ]