CASA2014-Hierarchical_structures_for_collision_checking_between_virtual_characters.pdf

(7450 KB) Pobierz
Hierarchical structures for collision checking between virtual
characters
Published in Computer Animation and Virtual Worlds 2014;
25:333–342
Sybren A. St¨vel
1
, Nadia Magnenat-Thalmann
2
, Daniel Thalmann
2
, Arjan Egges
1
, and
u
A. Frank van der Stappen
1
2
VHTLab, Universiteit Utrecht
Institute for Media Innovation, Nanyang Technological University
June 4, 2014
1
Figure 1: A crowded pavement.
Abstract
Simulating a crowded scene like a busy shopping
street requires tight packing of virtual characters.
In such cases collisions are likely to occur, and the
choice in collision detection shape will influence
how characters are allowed to intermingle. Full col-
lision detection is too expensive for crowds, so sim-
plifications are needed. The most common simplifi-
cation, the fixed-width, pose-independent cylinder,
does not allow intermingling of characters, as it will
either cause too much empty space between char-
acters or undetected penetrations. As a possible
solution to this problem, we introduce the
bound-
1
e-mail:{s.a.stuvel,j.egges,a.f.vanderstappen}@uu.nl
2
e-mail:{nadiathalmann,danielthalmann}@ntu.edu.sg
ing cylinder hierarchy
(BCH), a bounding volume
hierarchy that uses vertical cylinders as bound-
ing shapes. Since the BCH is a generalization of
the single cylinder, we expect that this represen-
tation can be easily integrated with existing crowd
simulation systems. We compare our BCH with
commonly used collision shapes, namely the single
cylinder and oriented bounding box tree, in terms
of query time, construction time and represented
volume. To get an indication of possible crowd
densities, we investigate how close characters can
be before collision is detected, and finally propose
a critical maximum depth for the BCH.
Hierarchical structures for collision checking between virtual characters
1
Introduction
Crowd simulation plays an ever increasing role in
different fields. When a crowd consists of densely
packed characters, such as shown in Figure 1, colli-
sion detection on all characters can become com-
putationally expensive. A brute-force approach
to collision detection would check every primitive
of one character with all primitives of the other.
For a real-time crowd this becomes unattainable,
and a smarter approach is needed. Most agent-
based crowd simulation systems use a simplifica-
tion where crowd agents are modeled as a cylinder
sliding on a ground plane, animating a character in-
side this cylinder using a walk cycle [PAB07]. For
sparse to medium-density crowds, this method is
often sufficient. However, when the density of the
crowd increases such that the movement of an agent
may be impaired, a more precise representation of
the space that virtual characters occupy is needed.
Collision detection typically occurs in two phases
[vdB04]. The
broad phase
finds pairs of objects that
may collide and eliminates pairs that are far away
from each other, usually employing space partition-
ing structures such as voxel grids [Rey06] or space
partitioning trees [VLnG10]. The
narrow phase
takes these pairs of objects, and performs the actual
collision test. It is in this phase that the techniques
described in this paper are applied.
To calculate a physically plausible collision re-
sponse, the force of the collision needs to be known.
Collision is usually only detected after two objects
have some measure of interpenetration, and the
penetration depth is then used as a measure of the
collision force [HTKG04]. Calculation of this pene-
tration depth requires a volumetric representation
of the colliding objects. However, most applica-
tions use a boundary representation where objects
consist of a polyhedral mesh. In this case we are
limited to detecting intersections of the boundaries
of the objects.
In this paper we introduce the
bounding cylinder
hierarchy
(BCH). We set criteria for collision han-
dling between virtual characters in a crowd, based
on query performance, construction speed and rep-
resented volume. We use this to compare the fol-
lowing collision detection structures: the oriented
bounding box tree, our BCH, and the shape most
widely used in crowd simulation, the single cylin-
der. Based on the outcome of a comparative exper-
Comp. Anim. Virtual Worlds 2014;
25:333–342
iment, we show which collision structure is suitable
for which use case. We represent characters by a
polyhedral mesh in which the vertices are defined
in a object-local coordinate frame.
Related work is discussed in the next section.
Section 3 formalizes bounding volume hierarchies
for collision detection, and defines the bounding
cylinder hierarchy (BCH) and OBB tree within
that formal definition. Section 4 details our experi-
mental comparison between the single cylinder, the
BCH and OBB tree. In Section 5 we investigate dif-
ferent properties of the BCH. We discuss possible
future work in Section 6, and conclude in Section 7.
2
Related Work
Collision detection is a widely researched topic.
Applications range from robotics via computer
aided design and manufacturing to crowd simula-
tion. It is common that simplified shapes are used
in order to reduce computational complexity, such
as a set of bounding boxes for the head, the torso
and the limbs. By using algebraic definitions, such
shapes can be intersected to approximate the pen-
etration depth. However, finding the correct alge-
braic shapes that tightly fit a given mesh can be
cumbersome.
A different approach to speed up the narrow
phase is the use of model partitioning techniques
such as bounding volume hierarchies (BVHs) that
allow for quick determination of non-intersection.
Commonly used BVHs are sphere trees [Hub96],
axis-aligned bounding box trees [vdB97], oriented
bounding box trees [GLM96] and k-DOP trees
[KHM
+
98].
Other authors have also compared different col-
lision shapes. Gottschalk et al. [Got00] proved
that oriented bounding box (OBB) trees are su-
perior over sphere trees and axis-aligned bounding
box (AABB) trees for surface based BVHs. Their
method is widely used, and will be used for compar-
ison with the bounding circle hierarchy. Van den
Bergen showed that AABB trees are easy to ad-
just after the object has been deformed, so for real-
time adaptation of the collision hierarchy AABB
trees are preferred [vdB97]. Both box-based meth-
ods use a bounding shape with straight edges and
square corners, which does not form a good match
for the human shape. This in itself is not an issue as
2
Hierarchical structures for collision checking between virtual characters
the hierarchy contains all the necessary details, but
when the maximum recursion depth is limited (as
we investigate in Section 5) this becomes relevant.
Sphere trees do not have such square corners, and
have been proven useful for the estimation of pen-
etration depth [OD99]. Collision tests on spheres
are simple as they are independent of the charac-
ter’s rotation. However, a sphere bounding a vir-
tual character would contain much empty space.
For a more detailed survey on collision detection
techniques we refer to the work of Kockara et al.
[KHI
+
07].
In this paper we extend the work of St¨vel et
u
+
al. [SES 13] by introducing the
bounding cylinder
hierarchy
for discrete collision detection. The cylin-
der is the prevalent shape in crowd simulation, and
is widely accepted as a rough approximation of the
human shape. By employing a hierarchical refine-
ment strategy, we ensure that the BCH represents
much tighter fit than possible with a single cylin-
der. The cylinder’s rotational symmetry allows for
fast intersection tests and efficient storage.
4. A stop criterion for the subdivision.
Let
�½
be any node in the tree, and
C(�½)
=
{µ
1
, . . . , µ
k
}
denote its child nodes. We impose the
following requirements for the hierarchical struc-
tures we consider in this paper, where
int(X)
de-
notes the interior of
X.
1.
P
(�½) =
µ∈C(�½)
P
(µ)
2. For all
µ, µ
∈
C(�½), µ
=
µ
:
int(P
(µ))
∩
int(P
(µ )) =
∅
So in other words,
P
(�½) is partitioned into the
sub-objects associated with the members of
C(�½).
A crucial property of bounding volumes is that for
any query object
Q
and node
�½,
if
Q
∩
B(�½)
=
∅
then
Q
∩
P
(�½) =
∅.
The above properties rule out certain bounding
volume hierarchies, such as using bounding boxes
for torso (root node) and head, arms and legs (child
nodes), or the elliptical and cylindrical collision
shapes by Dube et al. [DTT11]
3.1
Bounding Cylinder Hierarchy
3
Hierarchical structures for
collision detection
In the previous section, we have described a family
of bounding volume hierarchies that are commonly
used for collision or interference detection. This
section presents a formal definition of such struc-
tures, providing us with a common reference frame
to compare members of this family. We introduce
the bounding cylinder hierarchy as a hierarchical
generalization of the commonly used cylinder, and
redefine the oriented bounding box tree within the
terms of our reference frame. Section 4 will use
these definitions in a comparative experiment.
For an object
P
the ingredients for a hierarchical
collision structure
H(P
) are:
1. A family of shapes such as cylinders, boxes or
spheres;
2. A finite tree structure, where every node
�½
con-
tains a bounding volume
B(�½)
of the afore-
mentioned shape family, and represents a sub-
object
P
(�½)
⊂
P
;
3. A subdivision strategy, defining nodes in tree
layer
i
+ 1 given the nodes in layer
i;
Comp. Anim. Virtual Worlds 2014;
25:333–342
In this section we introduce the Bounding Cylin-
der Hierarchy (BCH). It refines the cylindrical rep-
resentation commonly used in crowd simulation.
Note that in this paper we use
bounding
shapes for
collision detection of characters (and parts of char-
acters), which is not always the case in the field
of animation; often approximations are used that
do not necessarily contain the entire character, in
order to artificially allow increased crowd densities
at the expense of realism. We define the structure
BCH(P
) as:
1. A vertical cylinder is used as the bounding
shape
B(�½).
2. The tree is binary; the root represents the en-
tire object
P
with its smallest enclosing cylin-
der.
3. We consider the projections of
P
(�½) against
the two horizontal global coordinate axes; the
axis for which the projection has the largest ex-
tent defines the normal of a separation plane.
P
(µ
1
) and
P
(µ
2
) are defined as a partition of
P
(�½) by that plane – details are given below.
B(µ
i
) is defined as the smallest enclosing cylin-
der of
P
(µ
i
).
3
Hierarchical structures for collision checking between virtual characters
very little overlap between the cylinders associated
with the leaf nodes of the hierarchy, as shown in
Figure 2.
Contour (centre):
This approach is almost
identical to the
contour
approach, differing only in
that it uses the centre point rather than the cen-
troid.
All projected triangles:
In this method we
eliminate the need to calculate the contour explic-
itly, by simply including all triangles into the hier-
archy. This will allow for faster construction at the
cost of an increase of the query time. This approach
mimics the decomposition used by Gottschalk et
al.[GLM96]. A triangle is never subdivided into
smaller pieces, but is placed into a subdivision
Figure 2: Visualization of the
contour
BCH.
P
(µ
i
) depending on the position of its centroid with
respect to the separating plane. The separation
4. When the radius of
B(�½)
is less than a prede- plane is chosen as described above, except that the
fined threshold, subdivision stops.
centroid of the mesh vertices is used. Subdivision
stops when a node contains a single triangle. Since
P
(µ
1
) and
P
(µ
2
) are separated by the verti- they are not subdivided, we cannot get arbitrarily
cal plane, hence their interiors are disjoint. As small cylinders. However, we do have the ability to
P
(µ
1
)∪P (µ
2
) =
P
(�½), it follows that
P
(�½) is parti- perform efficient, exact intersection tests as every
tioned properly. We have investigated three meth- leaf in the tree contains exactly one triangle.
ods of representing
P
(�½) and chosen appropriate
subdivision schemes accordingly:
Single cylinder:
This method could be de-
scribed as the
all projected triangles
method, but
Contour:
In this approach we only consider the using an infinitely large number of triangles for the
contour (from the top view) of
P
(�½). The sepa- stop criterion. This results in a hierarchy with one
ration plane is then defined by its normal (as de- node, containing only a single bounding cylinder.
scribed earlier), and the centroid of the contour As this form is so common, we handle it as a
polygon. The centroid is commonly used, as it of- special case.
ten results in a more balanced tree and better query
performance. We have chosen to use the centroid
A binary split was chosen in favour of a split into
of the projection rather than of the mesh vertices, four parts, as the latter can result in longer, thin-
in order to prevent bias to more detailed or heavily ner subdivisions that are not a good match for a
overlapping areas.
cylindrical bounding shape. In our implementation
The contour boundary is interpreted as a se- we consider the bounding cylinders to be of infinite
quence of line segments
S
=
{S
0
, . . . , S
n
}.
For each height, effectively ignoring the height of the charac-
segment the centre point is calculated; depending ter. This is common practice in crowd simulations.
on the side of the separating plane the centroid lies Future development could include the height infor-
on, it is used to define
P
(µ
1
) or
P
(µ
2
), taking care mation in intersection tests.
that neither set will be empty.
When
S
only contains a single line segment, and
3.2 Oriented Bounding Box tree
the segment is longer than twice the threshold ra-
dius, the line segment is split into two halves and The OBB tree by Gottschalk et al.[GLM96] is a
decomposed as described above. This results in well-known and widely used method for collision
Comp. Anim. Virtual Worlds 2014;
25:333–342
4
Hierarchical structures for collision checking between virtual characters
detection, and thus forms a good comparison for the experiments, those are regarded simply as a col-
the BCH. It follows the formal definition given at lection of triangles; the fact that they were posed
the start of this section:
using an articulated structure was of no relevance,
and we do not use any metrics that depend on such
1. An oriented box is used as the bounding shape. a structure. Tests are run multiple times to reduce
jitter and average out external factors, on an Intel
2. The tree is binary; the root represents the en-
Core i7 3630QM 3.2 GHz laptop. The BCH radius
tire object
P
with its oriented bounding box.
threshold is set at 1 cm.
3. Triangles of the mesh are stored in the leaves,
We represent characters by their boundaries and
based on which side of a separating plane their do not see them as solids; we consider two objects
centroid lies. For the exact spatial subdivision as colliding when their boundaries intersect. This
rules we refer to [GLM96].
means that we will not be able to detect the case
where one character completely envelopes another.
4. When a node contains only a single triangle, In our intended scenario this will not be an issue,
subdivision stops.
as collision will be detected before this can happen,
if at all.
At every internal node, every triangle in
P
(�½) is
represented by exactly one child node. This ensures
that
P
(�½) is partitioned properly. At the leaf nodes,
the OBB collision test performs triangle-triangle in-
4.1 Experiments
tersection tests. We define three techniques to con-
struct the OBB tree:
In our first experiment we measure the time re-
quired to construct the representations for each of
Full:
The OBB tree is populated with the trian- the 200 random poses. The time to load the mesh
gles of the mesh. This is an exact representation of data from disk is excluded from the test. The re-
the mesh.
sults are shown in the left bar chart of Figure 3.
The “BCH single cylinder” column shows the time
Contour:
We calculate the contour of the mesh, needed to calculate the bounding cylinder for the
as in Section 3.1. The line segments that make up posed mesh.
this contour are used to populate the OBB tree.
The second experiment measures the duration of
intersection tests. Each of our 500 test cases is
All projected triangles:
We use all triangles created by selecting two random poses, a random
projected onto the ground plane to populate the translation over the ground plane and a rotation
hierarchy, as in Section 3.1. Our hypothesis is that about the up-vector. The process of randomiza-
this will be less efficient to query than the
contour
tion is repeated until a true collision is detected
case but faster to construct. It may be faster to using the exact
full
OBB method. This presents us
query than the
full
case.
with a worst case test set, as negative tests often do
not require descending the entire tree where posi-
tive tests do. All tests are binary, i.e. only report
4 Comparison
whether an intersection is found.
In order to compare the BCH and OBB tree, we
perform two timing experiments. Each experiment
uses two character meshes, one male and one female
(see Figure 4) of approximately 2850 triangles each.
We use motion capture recordings totalling 212 sec-
onds of walking, turning, side-stepping and idling
motions. For each of the two meshes, we randomly
select 100 motion capture frames, resulting in a to-
tal of 200 randomly posed character meshes. For
Comp. Anim. Virtual Worlds 2014;
25:333–342
We run 10000 test iterations, where each itera-
tion tests all 500 test cases sequentially, preventing
over-optimistic results due to caching. To illustrate
the effect of caching, we have performed the experi-
ment in a different order by running each individual
test case 10000 times. This resulted in an approxi-
mately 15% better performance, but as this would
not reflect a real use case, it will not be included in
our results.
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin