Mathematical Modelling of Systems

ISSN: 1381-2424 (Print) (Online) Journal homepage: http://www.tandfonline.com/loi/nmcm19

Collision ditection for contact problems in

mechanics with a boundary search algorithm

Peter Eberhard & Shoushan jlang

To cite this article: Peter Eberhard & Shoushan jlang (1997) Collision ditection for contact
problems in mechanics with a boundary search algorithm, Mathematical Modelling of Systems,
3:4, 265-281, DOI: 10.1080/13873959708837061

To link to this article: http://dx.doi.org/10.1080/13873959708837061

Published online: 30 Mar 2007.

Submit your article to this journal

Article views: 33

View related articles

Full Terms & Conditions of access and use can be found at

http://www.tandfonline.com/action/journalInformation?journalCode=nmcm19

Download by: [University of Nebraska, Lincoln] Date: 29 October 2015, At: 23:08
 Mathematical Modelling of Systems 1381-2424/97/0304-265$12.00
1997, Vol. 3, No. 4, pp. 265-281 @wets & Zeitlinger

Collision Detection for Contact Problems

in Mechanics with a
Boundary Search Algorithm
Downloaded by [University of Nebraska, Lincoln] at 23:08 29 October 2015

PETER EBERHARD* AND SHOUSHAN JIANG~

ABSTRACT

The accurate description and modeling of contact problems in mechanics is an important techni-
cal problem, where many disciplines, e.g., mechanics, dynamics, geometry or visualization have
to contribute. In this paper an algorithm to determine the intersecting part between two bodies
described by polyhedra is presented. At first a rough but fast test is used to check whether there
exists at all the possibility that two objects collide. If they possibly collide, a more sophisticated
algorithm checks the actual collision status. The intersection boundary is computed, defined
by a closed polygon with a tracking method. Then, the boundary faces are searched along the
intersection boundary polygon. In the last step, the inserted faces are found and the intersecting
part is formed. The presented boundary search algorithm has the following advantages: I. high
precision, 11. high efficiency, 111. simple data structure. The collision detection and collision
geometry modeling are important tasks which build the basis for the analysis of the contact
kinematics and contact force computation.
Keywords: boundary search, collision detection, contact problem, polyhedra, track procedure.

1 INTRODUCTION

Collision detection is an important research subject not only in robotics, computer

animation and NC programming, but also in many other applications. For example, in
elastic multibody dynamics, if a collision occurs, we want to study the deformation of
the objects in the neighbourhood of the collision boundary and also quantities such as
resulting forces and torques on the colliding parts are required for their simulation. In
general, for different applications, the emphasis and the properties of the algorithms
may be different. Although there already exist several collision detection algorithms,
*Institute B of Mechanics, University of Stuttgart, 70550 Stuttgart, Germany.
E-mail: pe@mechb.uni-stuttgart.de
+CAD Research Center, Xian Institute of Technology, Xian, Shaanxi 710032, PR of China.
 266 PETER EBERHARD AND SHOUSHAN JIANG

different kinds of new algorithms are developed for special purposes. Most of the
algorithms have their own advantages, but it is hard or maybe even impossible for a
single algorithm to satisfy all application situations. Therefore, we compared several
approaches, but came to the conclusion, that due to our special requirements, a new
algorithm has to be developed, implemented and tested.
In elastic multibody dynamics, we need to know not only whether, when and
where, but also how two or more moving objects collide. The collision detection
algorithm should guarantee a sufficient accuracy, because all following calculations,
e.g., the force computation, are based on the intersection subpart. The algorithm
should also offer a high efficiency, because the whole system will be animated online
Downloaded by [University of Nebraska, Lincoln] at 23:08 29 October 2015

and real-time operator-in-the-loop simulations even for complicated bodies and contact
situations are one of the future goals of our investigations. Besides this, the used data
structure should be as simple as any possible for an easy integration of the collision
detection algorithm into the existing modeling, simulation and analysis environment.
The classical polygon intersection algorithm offers a high precision but the computation
efficiency is not very satisfying [7]. The hybrid algorithm as described in [8] is
efficient, but the data structure using sphere-trees is complex. Other algorithms have
certain limitations when applied to our problem. For example, the algorithm given
in [I] solves mainly the problem if and where the collision occurs, but for force
computations derived from modeling based on the intersection subparts, we have to
include their exact geometrical description. The algorithms provided in [4, 111 treat
only special shapes of objects. Therefore, based on the polygon intersection algorithm
and the hybrid algorithm, a new collision detection and analysis algorithm, called
boundary search algorithm, has been developed. Its name already shows, that the
efficient search along the boundary is the main strategy of the algorithm.
The algorithm can be divided into at least two phases: In the first phase, the
question must be answered whether and when the moving objects collide (i.e., the
classical purpose of collision detection), whereas in the second phase, we have to
compute where and how they collide (a task of big importance for the mechanical
modeling).
In Section 2, the contact mechanics environment is briefly introduced. Then, the
basic principle of the boundary search algorithm through the analysis of the intersecting
part between two polyhedra is given in Section 3. The used data representation
for the algorithm is especially explained in Section 4 due to its importance in the
application of the algorithm. In Section 5, we describe the procedure of determining
the intersecting part in some detail. Typical examples of computed intersections with
different complexity are provided in Section 6. Finally, we give a short evaluation and
summary about the algorithm. The algorithm can be trivially extended to collision
detection problems with n bodies, but special sorting algorithms are necessary to avoid
an increase in computation time of order O(n2).
 BOUNDARY SEARCH FOR CONTACT PROBLEMS

2 CONTACT MECHANICS ENVIRONMENT

Collision detection algorithms are used for different purposes. Our purpose is to use
it as an important part of a contact mechanics program environment. Despite the fact,
that collision detection is the main topic in this paper, we also want to give a brief
overview over other important topics. If no collision is detected, i.e., if no contact
between bodies occurs, we usually may describe the motion by methods from rigid
multibody dynamics [9], where the equation of motion for holonomic systems reads
as
+
M ( t ,Y)Y k(t,Y,y ) = 90, Y,Y), Y Q O )= Y O , to) = yo, (1)
Downloaded by [University of Nebraska, Lincoln] at 23:08 29 October 2015

where M is the mass matrix, k the vector of generalized Coriolis forces, q the vector
of generalized applied forces, y the vector of generalized positions and y the vector of
generalized velocities. This set of 2 f ordinary differential equations can be solved by
numerical time integration. For each time step ti, we have to check whether collision
occurs and if so, the collision forces have to be computed.
Several approaches have been applied sucessfully for this purpose. For classical
multibody systems, where the bodies are rigid, i.e., undergo no deformations, a La-
grange multiplier method can be used, where in an iterative procedure contact forces
are computed, such that finally the overlap between the body vanishes, see e.g., [5].
If penalty methods are used, a small overlap is even required to compute the contact
forces, see e.g., [lo]. One can think of this approach as putting very hard springs in the
contact zone. Of course, the penalty method is somewhat 'unphysical' because two
solid bodies in contact can never penetrate and the penalty factors are hard to guess,
but this approach has proven to be useful and reliable in many applications.
The underlying mechanical model can also be derived from Elastic Multibody Dy-
namics, from Finite Element Method or from the Boundary Element Method. Using
these approaches, the bodies change their shape due to contact forces and sophisti-
cated algorithms have been developed to compute mechanically correct motions and
deformations, see [12].
Other important parts of the software environment are for general administration,
for the assembly and solution of the equations or for online visualization [3].
If finite elements or boundary elements are used, it is for low-velocity impacts not
indispensable that the whole body has to be regarded as elastic. It can be sufficient,
that the body is split into a rigid and an elastic subpart. The latter has to be computed
from the original geometry and must be discretisized adaptively. In the contact zone
the discretization must be very fine, the farther away one is from the contact area,
the coarser the grid may be chosen. However, if travelling waves or their reflections
are important for the correct modeling of the problem, no rigid subpart may be used
because it causes waves of infinite velocity and therefore unphysical results.
Other interesting problems are the on-the-fly change from Multibody Dynamics
to Finite Elements, where the integration algorithm has to deal with a very different
number of degrees of freedom.
 268 PETER EBERHARD AND SHOUSHAN JIANG
Downloaded by [University of Nebraska, Lincoln] at 23:08 29 October 2015

intersecting part P

Fig. 1 . Intersection boundary polygon and intersecting part.

3 PRINCIPLE OF THE BOUNDARY SEARCH ALGORITHM

In multibody dynamics, the shape of the objects may be described by polyhedra. For
the sake of simplicity, we assume here that the polyhedra are convex, at least local
convex. Any non-convex polyhedron can be decomposed into convex polyhedra,
therefore, this restriction does not influence the result of the algorithm. First, let us
observe a collision example. In Fig. 1, polyhedra A and B intersect.
We can easily observe the following facts:
1. The intersection boundary between object A and object B consists of one or
more closed polygons. Considering the special application in elastic multibody
dynamics, our main concern is the case of only one closed intersection boundary
polygon. However, as long as various intersection boundary polygon are inde-
pendent, several collisions can be investigated simultaneously without requiring
extensions of the algorithm.
2. The intersection part consists of two subparts: part IA and part IB, where IA
belongs to object A but is enclosed within object B and IB belongs to object B,
but is enclosed within object A.
 BOUNDARY SEARCH FOR CONTACT PROBLEMS 269

3. Each of the polygon faces of object A can be classified into one of the following
three types:
(a) faces completely inside of object B,
(b) faces completely outside of object B,
(c) faces divided by the intersection boundary polygon.
4. The face divided by the intersection boundary polygon consists of two parts; the
part inside the other object and the part outside the other object.
For the convenience of explanation, we give the following definitions:
Downloaded by [University of Nebraska, Lincoln] at 23:08 29 October 2015

Intersection Edge: When two polygon faces intersect, the intersection line segment
is called intersection edge.
Intersection Point: The end points of intersection edges are called intersection points.
Intersection Face: If a polygon face from object A and a polygon face from object
B intersect, both faces are named intersection faces. These two corresponding
intersection faces are called a pair of intersection faces.
Intersection Boundary Polygon: The intersection edges compose a closed polygon,
which is called intersection boundary polygon.
Boundary Face: When a polygon face of the original object is divided by the inter-
section polygon, the part enclosed within an other object is also a polygon face,
which is called boundary face.
Inserted Face: The polygon faces completely enclosed within another object are
called inserted faces.
The key to form the intersection part P = IA U IB is to find the boundary polygon
faces of object A and object B as the inserted faces are easy to be determined. To find
the boundary faces, first the intersection boundary polygon must be obtained.
From the above analysis, we know that two factors are important to increase the
efficiency of the collision analysis algorithm. An efficient method to construct the
intersection boundary polygon has to be used and we need an efficient method to
determine boundary faces.
The main difficulty to get the intersection boundary polygon is the exact location of
the pairs of intersection faces, belonging to object A and object B respectively, because
the computation of the intersection edge between two polygon faces must be precise
enough. To solve this problem, the hybrid algorithm described in [8] uses a sphere-
trees method to determine the colliding region. The smaller the region, the shorter
the computing time. As soon as the first pair of the intersection faces is found, the
following pairs will be located precisely in a straight-forward and efficient computation
 270 PETER EBERHARD AND SHOUSHAN JIANG

sequence. The costly one-by-one comparisons therefore are required only until the
first pair is obtained.
An efficient method of determining boundary faces will further decrease the com-
puting time, Unfortunately, this fact is hardly investigated in most collision analysis
algorithms. In our boundary search algorithm, main attention is paid to these two
points. Besides, a rough test using simple enclosing primitives is utilized in advance
to exclude the cases where the investigated objects are far away from each other and
therefore certainly do not touch. These computations are very simple and efficient.
The boundary search algorithm adopts the following computation steps:
Downloaded by [University of Nebraska, Lincoln] at 23:08 29 October 2015

perform a rough collision test,

search the intersection boundary polygon using a track method to guarantee the
exact location of the pairs of intersection faces for each step,
search the boundary faces along the intersection boundary polygon,
find the inserted faces.
form the intersection part,
compute other interesting quantities, such as gap functions or collision forces.

4 DATA STRUCTURES

Two data structures are the basis of the boundary search algorithm. The first structure
contains the data description of the polyhedra, which is provided from the preprocess-
ing of the multibody system, see [2], The second type is a specially designed data
description of the intersection boundary polygon.
A polygon face is described by sequential vertices in counter-clockwisedirection,
where the face normals are always pointing to the outside. A polyhedron is described
as a collection of its vertices and its polygon faces. From this information the edges
can be easily derived. We take the data representation of a simple cube as example to
illustrate this. The cube in Fig. 2 has the data representation:

8 6 12 (number of vertices, faces and edges)

1 0 0
1 1 0
1 1 1
1 0 1 (cartesian vertex coordinates )
0 1 0
0 1 1
0 0 1
 BOUNDARY SEARCH FOR CONTACT PROBLEMS
Downloaded by [University of Nebraska, Lincoln] at 23:08 29 October 2015

Fig. 2. A cube and its representation.

0 0 0
4 0 1 2 3
4 2 6 7 3
4 6 5 4 7
4 5 1 0 4 (number of the vertices of a single polygon
4 5 6 2 1 and its vertex indices)
4 0 3 7 4

From this data description, we know the cube has 8 vertices, 6 faces and 12 edges.
The coordinates of each vertex and the face information are known. For example, the
0-th face has 4 vertices which are Vo, Vl , V2 and V3. Optionally, color information for
edges or faces can be included in the data description.
The more interesting data structure used in the boundary search algorithm is the
description of the intersection boundary polygon. It must contain all the required
information while being as simple as possible. Let Lk stand for the k-th edge of the
intersection boundary polygon. Then the following data representation is designed to
describe Lk

where
'Ai= index of polygon face of the object A
B j = index of polygon face of the object B
 272 PETER EBERHARD AND SHOUSHAN JIANG
Downloaded by [University of Nebraska, Lincoln] at 23:08 29 October 2015

Fig. 3. Intersection edges between polygon faces

From these two entries, we know that Lk is the intersection between polygon face
A, and polygon face B, .
Po = (xo, yo, 20): the start point of edge Lk
ASo: information about Po on the polygon face A,
ASo = -1 and ASI = 0: Po is inside the polygon face A,
ASo = index of the edge of the polygon face A, containing the start point
Po. In this case, when
AS1 = 1: the start point of the denoted edge AS0 is inserted into the
object B,
AS1 = 2: the end point of the denoted edge ASo is inserted into the
object BI
B So: information about Po on the polygon face Bl
BSo = -1 and BS1 = 0: Po is at the inside the polygon face BI
BSo = index of the edge of the polygon face B, containing the start
point Po. At this case, when
BS1 = 1: the start point of the denoted edge BSo is inserted into the
object A,
BS1 = 2: the end point of the denoted edge BSo is inserted into the
object A,
PI = ( X I y, ~z l, ) : the end point of Lk
AEo, AE1, BE0 and BE1 have the same meanings as ASo, A S ! , BSo and B S I while
the described point is PI instead of Po.
Figure 3 shows two examples for intersecting edges between polygon faces be-
longing to two different objects. The intersection edge between A3 and Bs reads as
follows:
 BOUNDARY SEARCH FOR CONTACT PROBLEMS

and the intersection edge between A7 and B7 is

According to the above definition, we know that the first intersection edge is the
intersection between face Ag and face B5. The start point of the intersection edge is
(xo, yo, zo) which is inside of face Ag and on the first edge of face BS. The end point of
the first edge of face B5 is enclosed within object A. The end point of the intersection
Downloaded by [University of Nebraska, Lincoln] at 23:08 29 October 2015

edge is (XI,yl, zl) which is inside of face BS and on the first edge of face A3. The
end point of the first edge of face A3 is enclosed within object B. For the second
intersection edge, the same information can be obtained.

5 CONSTRUCTING THE INTERSECTING SUBPART

If each of the polygon faces A; from object A is checked against each of the polygon
faces B, from object B to determine whether an intersection exists, the computation
time can be extremely large for a large number n of objects. The time then is roughly
proportional to n2, i.e., of order 0(n2). For example, to inspect whether two bodies
defined by 50 faces intersect, we would have to perform about 2500 face to face
checks, for 100 faces already 10000 checks. With a fast method to test whether a
simple enclosing approximation of the original geometrical shape, e.g., an enclosing
min-max cube or an enclosing sphere collide, a lot of time can be saved. When even
their simple geometric approximations do not intersect, any further computation may
be avoided. Otherwise finer tests have to be performed to finally decide their collision
status.

5.1 Rough collision test

In Computer Aided Graphics Design (CAGD), the convex-hull is often used to judge
if two curves or two surfaces intersect. Using this idea, we choose a enclosing min-
max cube as the (non-minimal) convex hull of a polyhedron. It is trivial to form the
min-max cube of a polyhedron and to test if two cubes intersect. Suppose polyhedron
A has n vertices
V;=(x;,yi,zi), i = O ,..., n - 1 . (2)
 274 PETER EBERHARD AND SHOUSHAN JIANG

where

Box-B is defined analogously. Only if the three conditions

Downloaded by [University of Nebraska, Lincoln] at 23:08 29 October 2015

are satisfied simultaneously, Box-A and Box-B intersect. For rotating bodies with
similar x/y/z-dimensions,enclosing spheres have advantages over enclosing min-max
cubes.

5.2 Compute the intersection boundary polygon

The problem of obtaining the intersection edge between two polygon faces can be
simplified to the problem of determining the intersection point between a line segment
and a polygon face, details may be found in [8]. In the following we explain how to
track intersection faces.
1. After the rough test, we know there exists the possibility that object A and
object B intersect, i.e., that the bodies are not far apart. Therefore, a further
more detailed test has to be performed. At the beginning, we have to find the first
pair of the intersection faces belonging to object A and object B respectively.
At this step, we have to test possible pairs of polygon faces until the first one is
found. Suppose the first pair of the intersection faces are (Aio, B j o ) and their
intersection edge is L 1 , as shown in Fig. 4. Edge Ll has the following data
record:

2. Since P2 is inside the polygon face A j o ( AEo = - 1 ) and on the edge Bjol(BEo =
Bjol)of the polygon face Bjo, it is easy to track the polygon face B j l which
shares the common edge Bjol = B j l mwith Bjo. Computing the intersection
between Aio and B j l , we get the intersection edge L2, which has the data record:
 BOUNDARY SEARCH FOR CONTACT PROBLEMS
Downloaded by [University of Nebraska, Lincoln] at 23:08 29 October 2015

Fig. 4. Intersection boundary polygon.

3. Since P3 is inside the polygon face B j l and on the edge Aio,(AEo = Aio,) of
the polygon face Aio, it is easy to track the polygon face Ail which shares the
common edge Aion = A i l p with AiO. Computing the intersection between Ail
and B j l , we obtain the intersection edge L3, which has the data record:

4. Repeating the above tracking procedures, we obtain L4, L 5 , . . . L q , which com-

pose a closed 3D polygon, the so-called intersection boundary polygon.
Except for the first pair of the intersection faces (Aio, B j o ) , all other pairs of
the intersection faces ( A i o ,B j l ) , ( A i l ,B j l ) , ( A i l ,B j 2 ) , . . .are tracked without
search, because all information about adjacent faces is included in the data
structure and therefore the algorithm can proceed directly to the correct next
face.

5.3 Compute the boundary faces

In Section 2, boundary faces have been defined. Boundary faces of object A and
boundary faces of object B are assembled to form a band along the intersection
boundary polygon, as shown in Fig. 5. Therefore, we have to split the intersection
faces in those inside the body and those outside the other body.
 PETER EBERHARD AND SHOUSHAN JIANG

intersection boundary polygon

I boundary faces
Downloaded by [University of Nebraska, Lincoln] at 23:08 29 October 2015

Fig. 5. Boundary polygon band.

Figure 6 illustrates two typical boundary faces where the intersection edges of the
left example are connected and form one polygon, but the intersection edges of the
right example are separated and form two polygons. We take the right situation as
example to describe the search. Suppose the original polygon face is A i , which is
divided into boundary face Ai and other sub-faces. Face Ai consists of seven vertices
and seven edges, where VI, V2, Vs, V6 are enclosed within object B.
The intersection edges L4, L5,L6, L I Zhave the data records:

where * denotes values defined by actual node positions. The boundary faces may
then be computed as follows:

1. From the first entry of the above data record, we can determine the face number
A i which is the original polygon face of the requested boundary face Ai.
 BOUNDARY SEARCH FOR CONTACT PROBLEMS
Downloaded by [University of Nebraska, Lincoln] at 23:08 29 October 2015

' boundary polygon .:,'

Fig. 6. Boundary polygon faces

2. Find an edge on A; whose end point is inserted into object B and on which there
is an intersection point. That is, AS1 or A El must be 2. Here two edges e4 and
eo satisfy the conditions because in the data record of L6, A Eo = e4, A El = 2
and in the data record of L12, A Eo = eo, A E l = 2. Suppose the first one
found is e4. Then determine the edge index of the intersection edge L6 whose
end point P7 is at e4. The end point P7 of the edge L7 is the first vertex of the
bounday face A; to be determined. Using B P to denote the set of vertices of
the boundary face, we have at this step B P = {P7}.
3. Since P7 is on the edge e4 of A; and the end point V5 is enclosed within B,
the next search will be carried out along this edge. If there is also an other
intersection point on the edge e4, this point will be the next vertex of B P and the
next search will be carried out along the intersection boundary polygon instead
of the original polygon A i . Because there is no other intersection point on the
edge e4, the end point V5 of eq is the second vertex of the boundary face A;,i.e.,
B P = (P7, V5).
4. Continuing the search along the next edge es of the original polygon A;, no
intersection point is found, so the end point V6 of the edge e5 is the third vertex
of the boundary face Ai, i.e., B P = { P7, Vs, V6}. On the next edge e6, an
intersection point P12is detected. This intersetion point is the fourth vertex of
the boundary face, B P = { P7, V5, V6, P12}.
5. Since an intersection point is found at the edge e6, the next search is carried along
the intersection boundary polygon. The end point P13 of L I Zis the fifth vertex of
B P , B P = (P7, Vs, V6, P12, P13}.Then, PI3is checked whether it is inside
of A i or on one of the edges of A;. If PI3 is inside of A i , the next search step
will be carried out along the next intersection edge L14. Otherwise the search
 278 PETER EBERHARD AND SHOUSHAN JIANG

will proceed along the edge of A;,on which the point P13 was found. Since PI3
is on the edge eo of A;,the further search is carried out along eo. We notice
that the end point of eo is inserted within object B. That is, the intersection point
PI3has the same function as the intersection point P7 in the search process, i.e.,
repeating the search steps from (2) to (4) analogously, vertices VI, V2, P4, P5
and P6 are determined. The boundary face A; finally has ten vertices with
B P = IP7, V5, V6, PI27 P13, Vli V2, P4i P5i P6}*
6. When the intersection point P7 is obtained again, the search is finished. The
boundary face Ai divided from the original polygon face A i has been formed.
Downloaded by [University of Nebraska, Lincoln] at 23:08 29 October 2015

All boundary polygon faces can be determined this way.

5.4 Determining the inserted faces

If all vertices of a polygon face are enclosed within another object, the polygon face
is an inserted face. Since it is easy to check whether a vertex from one polyhedron is
enclosed within another, determining the inserted polygon faces is straight-forward.

5.5 Forming the intersecting subpart

If all inserted faces and the boundary faces are found, they are assembled to form a
standard polyhedron as described in Section 3. Again, the computation is straight-
forward and must not be explained here in detail.

5.6 Computing other quantities for the dynamical simulation

In mechanics several quantities such as forces, torques, gap functions, center of gravity
based on the intersecting subpart are required for an appropriate modeling of the contact
situation and have to be computed in following steps. Since we have provided the
intersecting subpart, the computation can be performed in standard procedures, see
e.g., [lo].

6 EXAMPLES

In this section, we provide three simple examples to show the application of the
boundary search algorithm.
For all these examples, it can be seen that the intersecting subpart can be obtained.
It should be emphazised, that no restrictive assumptions are necessary and the described
algorithm is usable for a wide range of problems in elastic multibody system dynamics
and contact problems.
 BOUNDARY SEARCH FOR CONTACT PROBLEMS
Downloaded by [University of Nebraska, Lincoln] at 23:08 29 October 2015

--.
Fig. 7. Cube 1 cube and half sphere I half sphere.

Fig. 8. Cylinder 1 cylinder.

7 SUMMARY

The boundary search algorithm for collision detection is an efficient improvement to

the basic polygon intersection algorithm. This is done through the adoption of some
 280 PETER EBERHARD AND SHOUSHAN JIANG

techniques to increase the computing speed while keeping the additional data structure
simple. Here we emphasize several important properties of the algorithm.
1. Precision: The boundary search algorithm has the same precision as the classical
algorithm or the hybrid algorithm, because the computation of the intersection
between polygon faces can be obtained without approximation.
2. Efficiency: The computation efficiency of a collision detection algorithm de-
pends, to a great extend, on the time spent to determine the pairs of the intersec-
tion faces. Besides, it also depends on the time required to find the boundary
faces. In the boundary search algorithm, all pairs, except the first pair of the
Downloaded by [University of Nebraska, Lincoln] at 23:08 29 October 2015

intersection faces, are tracked directly without search. The amount of compu-
tation time, for the tracking phase is very small. Thus, in general, the algorithm
has a high average computation speed. Only statements about the average speed
are possible, because for the search of the first pair it is hard to give an accurate
estimation. Compared to the time to obtain the first pair we can neglect the
tracking time. Usually problems in mechanics fulfill the coherence criterion,
see [6]. This helps to reduce the time spend for the search of the first pair
by utilizing information kepts from the last steps and will be one of the next
improvements to implement and investigate.
3. Storage requirement: The additional data structure involved in the boundary
search algorithm is only required for the description of the intersection boundary
polygon. Compared with most other algorithms, this data structure is very simple
and easy to manipulate.
4. Limitations: In the beginning, we made two assumptions: The polyhedra
are convex, or at least local convex and there is only one closed intersection
boundary polygon between two objects. The first limitation is by far stricter
than required, because a polyhedron can always be split into several convex
sub-polyhedra. So this limitation can be ommited by appropriate preprocessing.
The second limitation was just for ease of explanation, because if there is
more than one intersection boundary polygon, the search will be carried out
along all intersection boundary polygons instead of only one. The computation
complexity would not change.

ACKNOWLEDGEMENTS

This work was partially completed during P. E.'s visit to the Department of Mechanical Engi-
neering at the University of California at Berkeley, and was supported by the German Research
Council (DFG) under grant EB 19511-1.
 BOUNDARY SEARCH FOR CONTACT PROBLEMS 28 1

REFERENCES

1. Bez, H.E., Bricis, A.M., Ascough, J.: A Collision Detection Method with Application in
CAD System for the Apprel Industry. Computer-Aided Design, Vol. 28(1), (1996),
pp. 27-32.
2. Eberhard, P.: NEWANIM - Animation of Multibody Systems. Manual AN-37, Institute B
of Mechanics, University of Stuttgart, 1994.
3. Eberhard, P.: Zur Mehrkriterienoptimiemng von Mehrkorpersystemen. VDI-Fortschritt
Berichte, Reihe 11, Nr.227, Diisseldorf: VDI-Verlag, 1996.
4. Garcia-Alonso, A., Serrano, N., Flaguer, J.: Solving the Collision Detection Problem.
IEEE Computer Graphics and Applications, (1994), pp. 36-42.
5. Glocker, C., Pfeiffer, F.: Multiple Impacts with Friction in Rigid Multibody Systems.
Nonlinear Dynamics, 7, (1995), pp. 471497.
Downloaded by [University of Nebraska, Lincoln] at 23:08 29 October 2015

6. Lin, M.C.: Efficient Collision Detection for Animation and Robotics. PhD. Thesis, Dept. of
Electrical Engineering and Computer Science, University of Califonia, Berkeley,
1993.
7. Moore, M., Wilhelms, J.: Collision Detection and Response for Computer Animation.
Computer Graphics, Vol. 22(4), (1988), pp. 289-298.
8. Palmer, I.J., Girmsdale, R.L.: Collision Detection for Animation using Sphere-Trees.
Computer Graphics Forum, Vol. 14(2), (1995), pp. 105-1 16.
9. Schiehlen, W.O. (Ed.): Advanced Multibody System Dynamics - Simulation and Software
Tools. Dordrecht: Kluwer Academic Publishers, 1993.
10. Schoen, S.: Dynamikanalyse von Verkehrsunfdlen. Thesis, STUD-137, Institute B of
Mechanics, University of Stuttgart, 1996.
11. Thalmann N.M., Thalmann, D.: Construction and Animation of a Synthetic Actress. Proc.
of Eurographics'88, (1988), pp. 55-66.
12. Wriggers, P.: Finite Element Algorithms for Contact Problems. Archives of Computational
Methods in Engineering, Vol. 2(7), (1995), pp. 1-49.