[ Pobierz całość w formacie PDF ]

where corresponds to the dot product. This results in four equations in four un-
Let us analyze the algebraic complexity of these two system of equations cor-
responding to closest features. Lets consider the rst system corresponding to 4.1 .
In particular, given 2 rational parametric surfaces F s; t and G u; v , both of their
numerators and denominators are polynomials of degree n, the degrees of numerators
and denominators of the partials are 2n ,1 and 2n respectively in the given vari-
ables due to quotient rule . The numerator and denominator of F11 s; t; u; v;
have degree 2n and 2n due to subtraction of two rational polynomials. As for
F12 s; t; u; v; , taking the cross product doubles the degrees for both the numer-
ator and denominator; therefore, the degrees for the numerator and denominator of
F12 s; t; u; v; are 4n,2 and 4n respectively. To eliminate from F1 s; t; u; v; ,
1 1 1
we get
F11 X s; t; u; v; F11 Y s; t; u; v; F11 Z s; t; u; v;
1 1 1
= = 4:3
F12 X s; t; u; v; F12 Y s; t; u; v; F12 Z s; t; u; v;
1 1 1
After cross multiplication to clear out the denominators we get two polynomails of
degree 12n ,2 each. Once again, by the same reasoning as stated above, both the
numerators and denominators of F21 s; t; u; v; and F22 s; t; u; v; have degrees
2 2
of 4n ,2 and 4n. By similar method mentioned above, we can eliminate from
F2 s; t; u; v; . We get two polynomial equations of degree 16n ,4 each after cross
2 2
multiplication. As a result the system has a Bezout bound of 12n ,2 16n ,4 .
Each equation in the second system of equations has degree 4n ,1 obtained
after computing the partials and addition of two rational polynomials and therefore
the overall algebraic complexity corresponding to the Bezout bound is 4n,1 . Since
the later system results in a lower degree bound, in the rest of the analysis we will
use this system. However, we are only interested in the solutions in the domain of
interest since each surface is de ned on a subset of the real plane .
Bara has used a formulation similar to 4.1 to keep track of closest points
between closed convex surfaces 3 based on local optimization routines. The main
problem is nding a solution to these equations for the initial con guration. In
general, these equations can have more than one solution in the associated domain, i.e.
the real plane, even though there is only one closest point pair and the optimization
routine may not converge to the right solution. A simple example is the formulation
for the problem of collision detection between two spheres. There is only one pair of
closest points, however equations 4.1 or 4.2 have four pairs of real solutions.
Given two algebraic surfaces, f x; y; z = 0 and g x; y; z = 0, the problem
Tangent Plane
Contact Point
( a )
is a boundary point
( b )
Figure 4.3: Tangential intersection and boundary intersection between two B ezier
of closest point determination can be reduced to nding roots of the following system
of 8 algebraic equations:
f x1; y1; z1 = 0
g x2; y2; z2 = 0 4.4
0 1 0 1
fx x1; y1; z1 gx x2; y2; z2
= 1
fy x1; y1; z1 gy x2; y2; z2
@ A @ A
fz x1; y1; z1 gz x2; y2; z2
0 1 0 1 0 1
x1 x2 gx x2; y2; z2
, = 2
y1 y2 gy x2; y2; z2
@ A @ A @ A
z1 z2 gz x2; y2; z2
Given two algebraic surfaces of degree n, we can eliminate by setting
fx x1;y1;z1 fy x1;y1;z1
= . After cross multiplication, we have a polynomial equation
gx x2;y2 ;z2 gy x2;y2;z2
of 2n-2, since each partial has degree of n , 1 and the multiplication results in
x1 ,x2 y1 ,y2
the degree sum of 2n ,2. To eliminate , we set = and the
gx x2;y2 ;z2 gy x2;y2 ;z2
degree of the resulting polynomial equation is n. We have six quations after elim-
inating and : two of degrees 2n , 2 and four of degress n respectively 2
1 2
from eliminating and 2 from f x1; y1; z1 and g x2; y2; z2 . Therefore, the Bezout
bound of the resulting system can be as high as N = 2n ,2 n4. In general, if
the system of equations is sparse, we can get a tight bound with Bernstein bound
8 . The Bernstein bound for Eqn. 4.4 is n2 n2 + 3 n , 1 . Canny and Emiris
calculate the Bernstein bounds e ciently by using sparse mixed resultant formula-
tion 16 . For example, the Bernstein bounds2 for the case of n = 2; 3; 4; 5; 6; 7; 8; 9
are 28; 432; 2736; 11200; 35100; 91728; 210112; 435456, while the Bezout bounds are
64; 1296; 9216; 40000; 129600; 345744; respectively. Even for small values of n, N
can be large and therefore, the algebraic complexity of computing the closest points
can be fairly high. In our applications we are only interested in the real solutions to
these equations in the corresponding domain of interest. The actual number of real
solutions may change as the two objects undergo motion and some con gurations can
result in in nite solutions e.g. when a closest pair corresponds to a curve on each
surface, as shown for two cylinders in Fig. 4.4. . As a result, it is fairly non-trivial to
keep track of all the closest points between objects and updating them as the objects
undergo motion.
4.2.3 Contact Formulation
The problem of collision detection corresponds to determining whether there
is any contact between the two objects. In particular, it is assumed that in the
beginning the objects are not overlapping. As they undergo motion, we are interested
in knowing whether there is any contact between the objects. There are two types
of contacts. They are tangential contact and boundary contact. In this section, we
formulate both of these problems in terms of a system of algebraic equations. In the
next section, we describe how the algorithm tests for these conditions as the object
These gures are calculated by John Canny and Ioannis Emiris using their code based on the
sparse mixed resultant formulation.
undergoes rigid motion.
Tangential Intersection : This corresponds to a tangential intersection between
the two surfaces at a geometric contact point, as in Fig.4.3 a . The contact point
lies in the interior of each surface as opposed to being on the boundary curve
and the normal vectors at that point are collinear. These constraints can be
formulated as:
F s; t = G u; v 4.5
Fs s; t Ft s; t Gu u; v = 0
Fs s; t Ft s; t Gv u; v = 0
The rst vector equation corresponds to a contact between the two surfaces and
the last two equations represent the fact that their normals are collinear. They
are expressed as scalar triple product of the vector The last vector equation
represented in terms of cross product corresponds to three scalar equations.
We obtain 5 equations in 4 unknowns. This is an overconstrained system and
has a solution only when the two surfaces are touching each other tangentially.
However, we solve the problem by computing all the solutions to the rst four
equations using global methods and substitute them into the fth equation. If
the given equations have a common solution, than one of the solution of the
rst four equation will satisfy the fth equation as well. For the rst three
equations, after cross multiplication we get 3 polynomial equations of degree
2n each. The dot product results in the addition of degrees of the numerator
polynomials. Therefore, we get a polynomial equation of degree 6n ,3 from [ Pobierz całość w formacie PDF ]