[ Pobierz całość w formacie PDF ]

travels is not known in advance, then we can calculate a lower bound on collision
time. This lower bound on collision time is calculated adaptively to speed up the
performance of dynamic collision detection.
79
Let amax be an upper bound on the relative acceleration between any two
points on any pair of objects. The bound amax can be easily obtained from bounds on
the relative absolute linear ~ and relative rotational accelerations ~ and relative
alin arot
rotational velocities !r of the bodies and their diameters: ~ = ~ + ~ ~ + !r
~ amax alin arot r ~
!r ~ where r is the vector di erence between the centers of mass of two bodies. Let
~ r
d be the initial separation for a given pair of objects, and vi where ~ = ~ + !r ~
vi vlin ~ r
the initial relative velocity of closest points on these objects. Then we can bound the
time tc to collision as
q
2
vi +2amaxd ,vi
tc = 5.1
amax
This is the minimum safe time that is added to the current time to give the
wakeup time for this pair of objects. To avoid a Zeno's paradox" condition where
smaller and smaller times are added and the collision is never reached, we must add
a lower bound to the time increment. So rather than just adding tc as derived above,
1
we added tw = max tc; tmin , where tmin is a constant say 1 mSec or which
FrameRate
determines the e ective time resolution of the calculation.
As a side note here, we would like to mention the fact that since we can
calculate the lower bound on collision time adaptively, we can give a fairly good
estimate of exact collision time to the precision in magnitude of tmin. In addition,
since the lower bound on time to collision is calculated adaptively for the object
most likely to collide rst, it is impossible for the algorithm to fail to detect an
interpenetration.
This can be done by modifying tmin, the e ective time resolution, and the
user de ned safety tolerance according to the environment so as to avoid the case
where one object collides with the other between time steps. is used because the
polyhedra may be actually shrunk by amount to approximate the actual object.
Therefore, the collision should be declared when the distance between two convex
polytopes is less than 2 . This is done to ensure that we can always report a collision
or near-misses.
80
5.1.2 The Overall Approach
Our scheme for dynamic simulation using our distance computation algo-
rithm is an iterative process which continuously inserts and deletes the object pairs
from a heap according to their approximate time to collision, as the objects move in
a dynamic environment.
It is assumed that there is a function Ai t given for each object, which
returns the object's pose at time t, as a 4x4 matrix. Initially, all poses are determined
at t = 0, and the distance calculation algorithm in Chapter 3 is run on all pairs of
objects that might collide. The pairs are inserted into the heap according to their
approximate time to collision.
Then the rst pair of objects is pulled o the queue. Its closest feature pair
at t = 0 will be available, and the distance measuring algorithm from Chapter refdist
is run. If a collision has occurred and been reported, then the pair is re-inserted
in the queue with a minimum time increment, tmin. If not, a new lower bound on
time-to-collision for that pair is computed, and the pair is re-inserted in the queue.
This process is repeated until the wakeup time of the head of the queue exceeds the
simulation time.
Note that the lower bound on collision time is calculated adaptively for the
pair most likely to collide. Therefore, no collision can be missed. We will not need to
worry about those sleeping pairs which will not collide before their wake-up time ,
until the clock reaches the wake-up time Wi for each pair Pi.
This scheme described above can take care of all object pairs e ciently so
that the distant object pairs wake up much less frequently. Thus, it reduces the run
time in a signi cant way.
If no upper bounds on the velocity and acceleration can be assumed, in the
next section we propose algorithms which impose a bounding hierarchy on each
0 1box
N
@ A
object in the environment to reduce the naive bound of pairwise comparisons
2
for a dynamic environment of n objects. Once the object pairs' bounding boxes
already collide, then we can apply the algorithm described in Chapter 3 to perform
81
collision detection and to nd the exact contact points if applicable.
5.2 Sweep & Sort and Interval Tree
In the three-dimensional workspace, if two bodies collide then their projec-
tions down to the lower-dimensional x ,y; y ,z; x ,z hyperplanes must overlap as
well. Therefore, if we can e ciently update their overlapping status in each axis or in
a 2-dimensional plane, we can easily eliminate the object pairs which are de nitely
not in contact with each other. In order to quickly determine all object pairs over-
lapping in the lower dimensions, we impose a virtual bounding box hierarchy on each
body.
5.2.1 Using Bounding Volumes
To compute exact collision contacts, using a bounding volume for an in-
terference test is not su cient, but it is rather e cient for eliminating those object
pairs which are of no immediate interests from the point of collision detection. The
bounding box can either be spherical or rectangular even elliptical , depending on
the application and the environment. We prefer spherical and rectangular volume
due to their simplicity and suitability in our application.
Consider an environment where most of objects are elongated and only a
few objects probably just the robot manipulators in most situations are moving,
then rectangular bounding boxes are preferable. In a more dynamic environment
like a vibrating parts feeder where all objects are rather fat" 68 and bouncing
around, then spherical bounding boxes are more desirable. If the objects are con-
cave or articulated, then a subpart-hierarchical bounding box representation similar
to subpart-hierarchical tree representation, with each node storing a bounding box
should be employed. The reasons for using each type of the bounding volumes are as
follows.
Using a spherical bounding volume, we can precompute the box during the
preprocessing step. At each time step, we only need to update the center of each
82
spherical volume and get the minimum and maximum x; y ; z ,coordinates almost
instantaneously by subtracting the measurement of radius from the coordinates of the
center. This involves only one vector-matrix multiplication and six simple arithmetic
operations 3 addition and 3 subtraction . However, if the objects are rather oblong,
then a sphere is a rather poor bounding volume to use.
Therefore, a rectangular bounding box emerges to be a better choice for
elogated objects. To impose a virtual rectangular bounding volume on an object
rotating and translating in space involves a recomputation of the rectangular bound-
ing volume. Recomputing a rectangular bounding volume is done by updating the
maximum and minimum x; y ; z ,coordinates at each time instance. This is a simple
procedure which can be done at constant time for each body. We can update the
min" and max" by the following approaches:
Since the bounding boxes are convex, the maximum and minimum in the [ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

glaz.keep.pl