CASA2014-Hierarchical_structures_for_collision_checking_between_virtual_characters (1).pdf

(459 KB) Pobierz
Hierarchical structures for collision checking between virtual
characters
Sybren A. St¨vel
1
, Nadia Magnenat-Thalmann
2
, Daniel Thalmann
2
, Arjan Egges
1
, and
u
A. Frank van der Stappen
1
VHTLab, Universiteit Utrecht
2
Institute for Media Innovation, Nanyang Technological University
March 31, 2014
1
Figure 1: A crowded pavement.
Abstract
ing shapes. Since the BCH is a generalization of
the single cylinder, we expect that this represen-
Simulating a crowded scene like a busy shopping tation can be easily integrated with existing crowd
street requires tight packing of virtual characters. simulation systems. We compare our BCH with
In such cases collisions are likely to occur, and the commonly used collision shapes, namely the single
choice in collision detection shape will influence cylinder and oriented bounding box tree, in terms
how characters are allowed to intermingle. Full col- of query time, construction time and represented
lision detection is too expensive for crowds, so sim- volume. To get an indication of possible crowd
plifications are needed. The most common simplifi- densities, we investigate how close characters can
cation, the fixed-width, pose-independent cylinder, be before collision is detected, and finally propose
does not allow intermingling of characters, as it will a critical maximum depth for the BCH.
either cause too much empty space between char-
acters or undetected penetrations. As a possible
Introduction
solution to this problem, we introduce the
bound-
1
ing cylinder hierarchy
(BCH), a bounding volume
hierarchy that uses vertical cylinders as bound- Crowd simulation plays an ever increasing role in
different fields. When a crowd consists of densely
1
e-mail:{s.a.stuvel,j.egges,a.f.vanderstappen}@uu.nl
packed characters, such as shown in Figure 1, colli-
2
e-mail:{nadiathalmann,danielthalmann}@ntu.edu.sg
sion detection on all characters can become com-
Hierarchical structures for collision checking between virtual characters
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 simplification
where crowd agents are modeled as a cylinder slid-
ing on a ground plane, animating a character inside
this cylinder using a walk cycle [1]. For sparse to
medium-density crowds, this method is often suf-
ficient. 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
[2]. The
broad phase
finds pairs of objects that may
collide and eliminates pairs that are far away from
each other, usually employing space partitioning
structures such as voxel grids [3] or space partition-
ing trees [4]. 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 [5]. Calculation of this penetration
depth requires a volumetric representation of the
colliding objects. However, most applications 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 ob-
jects.
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-
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 [6], axis-
aligned bounding box trees [7], oriented bounding
box trees [8] and k-DOP trees [9].
Other authors have also compared different col-
lision shapes. Gottschalk et al. [10] proved that
oriented bounding box (OBB) trees are superior
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 [7]. Both box-based methods 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 the hierarchy contains all the necessary details,
but when the maximum recursion depth is limited
(as we investigate in Section 5) this becomes rele-
vant. Sphere trees do not have such square corners,
and have been proven useful for the estimation of
penetration depth [11]. Collision tests on spheres
are simple as they are independent of the charac-
2
To be published in the Computer Animation and Virtual Worlds journal, 2014
Hierarchical structures for collision checking between virtual characters
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.
[12].
In this paper we extend the work of St¨vel et
u
al. [13] by introducing the
bounding cylinder hier-
archy
for discrete collision detection. The cylinder
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.
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. [14]
3
Hierarchical structures for
3.1 Bounding Cylinder Hierarchy
In this section we introduce the Bounding Cylin-
collision detection
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
).
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;
4. A stop criterion for the subdivision.
Let
�½
be any node in the tree, and
C(�½)
=
4. When the radius of
B(�½)
is less than a prede-
{µ
1
, . . . , µ
k
}
denote its child nodes. We impose the
fined threshold, subdivision stops.
following requirements for the hierarchical struc-
tures we consider in this paper, where
int(X)
de-
P
(µ
1
) and
P
(µ
2
) are separated by the verti-
cal plane, hence their interiors are disjoint. As
notes the interior of
X.
To be published in the Computer Animation and Virtual Worlds journal, 2014
3
Hierarchical structures for collision checking between virtual characters
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.[8]. A triangle is never subdivided into smaller
pieces, but is placed into a subdivision
P
(µ
i
) de-
pending on the position of its centroid with respect
to the separating plane. The separation plane is
chosen as described above, except that the cen-
troid of the mesh vertices is used. Subdivision stops
when a node contains a single triangle. Since they
are not subdivided, we cannot get arbitrarily small
cylinders. However, we do have the ability to per-
form efficient, exact intersection tests as every leaf
in the tree contains exactly one triangle.
Single cylinder:
This method could be de-
scribed as the
all projected triangles
method, but
using an infinitely large number of triangles for the
stop criterion. This results in a hierarchy with one
node, containing only a single bounding cylinder.
As this form is so common, we handle it as a
special case.
A binary split was chosen in favour of a split into
four parts, as the latter can result in longer, thin-
ner subdivisions that are not a good match for a
cylindrical bounding shape. In our implementation
we consider the bounding cylinders to be of infinite
height, effectively ignoring the height of the charac-
ter. This is common practice in crowd simulations.
Future development could include the height infor-
mation in intersection tests.
Figure 2: Visualization of the
contour
BCH.
P
(µ
1
)∪P (µ
2
) =
P
(�½), it follows that
P
(�½) is parti-
tioned properly. We have investigated three meth-
ods of representing
P
(�½) and chosen appropriate
subdivision schemes accordingly:
Contour:
In this approach we only consider the
contour (from the top view) of
P
(�½). The sepa-
ration plane is then defined by its normal (as de-
scribed earlier), and the centroid of the contour
polygon. The centroid is commonly used, as it of-
ten results in a more balanced tree and better query
performance. We have chosen to use the centroid
of the projection rather than of the mesh vertices,
in order to prevent bias to more detailed or heavily
overlapping areas.
The contour boundary is interpreted as a se-
quence of line segments
S
=
{S
0
, . . . , S
n
}.
For each
segment the centre point is calculated; depending
on the side of the separating plane the centroid lies
on, it is used to define
P
(µ
1
) or
P
(µ
2
), taking care
that neither set will be empty.
When
S
only contains a single line segment, and
the segment is longer than twice the threshold ra-
dius, the line segment is split into two halves and
decomposed as described above. This results in
very little overlap between the cylinders associated
with the leaf nodes of the hierarchy, as shown in
Figure 2.
3.2
Oriented Bounding Box tree
The OBB tree by Gottschalk et al.[8] is a well-
known and widely used method for collision de-
tection, and thus forms a good comparison for the
BCH. It follows the formal definition given at the
start of this section:
1. An oriented box is used as the bounding shape.
4
To be published in the Computer Animation and Virtual Worlds journal, 2014
Hierarchical structures for collision checking between virtual characters
2. The tree is binary; the root represents the en-
tire object
P
with its oriented bounding box.
3. Triangles of the mesh are stored in the leaves,
based on which side of a separating plane their
centroid lies. For the exact spatial subdivision
rules we refer to [8].
4. When a node contains only a single triangle,
subdivision stops.
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-
tersection tests. We define three techniques to con-
struct the OBB tree:
Core i7 3630QM 3.2 GHz laptop. The BCH radius
threshold is set at 1 cm.
We represent characters by their boundaries and
do not see them as solids; we consider two objects
as colliding when their boundaries intersect. This
means that we will not be able to detect the case
where one character completely envelopes another.
In our intended scenario this will not be an issue,
as collision will be detected before this can happen,
if at all.
4.1
Experiments
In our first experiment we measure the time re-
quired to construct the representations for each of
the 200 random poses. The time to load the mesh
data from disk is excluded from the test. The re-
Full:
The OBB tree is populated with the trian- sults are shown in the left bar chart of Figure 3.
gles of the mesh. This is an exact representation of The “BCH single cylinder” column shows the time
the mesh.
needed to calculate the bounding cylinder for the
posed mesh.
Contour:
We calculate the contour of the mesh,
The second experiment measures the duration of
as in Section 3.1. The line segments that make up intersection tests. Each of our 500 test cases is
this contour are used to populate the OBB tree.
created by selecting two random poses, a random
translation over the ground plane and a rotation
All projected triangles:
We use all triangles about the up-vector. The process of randomiza-
projected onto the ground plane to populate the tion is repeated until a true collision is detected
hierarchy, as in Section 3.1. Our hypothesis is that using the exact
full
OBB method. This presents us
this will be less efficient to query than the
contour
with a worst case test set, as negative tests often do
case but faster to construct. It may be faster to not require descending the entire tree where posi-
query than the
full
case.
tive tests do. All tests are binary, i.e. only report
whether an intersection is found.
We run 10000 test iterations, where each itera-
4 Comparison
tion tests all 500 test cases sequentially, preventing
In order to compare the BCH and OBB tree, we over-optimistic results due to caching. To illustrate
perform two timing experiments. Each experiment the effect of caching, we have performed the experi-
uses two character meshes, one male and one female ment in a different order by running each individual
(see Figure 4) of approximately 2850 triangles each. test case 10000 times. This resulted in an approxi-
We use motion capture recordings totalling 212 sec- mately 15% better performance, but as this would
onds of walking, turning, side-stepping and idling not reflect a real use case, it will not be included in
motions. For each of the two meshes, we randomly our results.
select 100 motion capture frames, resulting in a to-
tal of 200 randomly posed character meshes. For
4.2 Conclusion
the experiments, those are regarded simply as a col-
lection of triangles; the fact that they were posed The experiments show a query time of 2.66
µs
for
using an articulated structure was of no relevance, the
BCH contour
method, and 4.63
µs
for the
OBB
and we do not use any metrics that depend on such
contour
method; in our scenario the BCH is 74%
a structure. Tests are run multiple times to reduce faster to query than the OBB tree. In general, the
jitter and average out external factors, on an Intel amount of overlap between cylinders of the same
To be published in the Computer Animation and Virtual Worlds journal, 2014
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin