86 9. COLLISION DETECTION AND RESPONSE
algorithm ever converges! Obviously, this can be problematic and there exist techniques to deal
with this situation which will be discussed later in this chapter. Another difficult situation is
when cloth slides over itself or another garment. e cloth is in contact with itself so it is colliding
but we do not want to restrict it too much since this would create snagging artifacts.
9.2 COLLISION DETECTION
e collision detection phase can be split into a broad phase, a mid phase, and a narrow phase.
We recommend the excellent book by Ericson [2004] and the freely available chapter on collision
detection in Akenine-Möller et al. [2018]. e broad phase is first performed and is meant to
quickly discard object pairs that are definitely not colliding. As a second step, the mid phase
will look at the overlapping primitives between object pairs. As a final step, the narrow phase
then takes a closer look at primitive pairs that could potentially be close to each other. We give
a quick overview.
• e broad phase works by looking at objects that overlap. e workhorse for the broad
phase is the sweep and prune algorithm [Akenine-Möller et al., 2018]. However, for cloth
simulations we typically assume a limited number of meshes in the scene and we can safely
skip the broad phase and start with the mid phase.
• e mid phase works on pairs of objects to find primitives in the object that overlap. e
phase makes use of spatial acceleration structures that can quickly prune particle pairs that
definitely won’t collide. is significantly reduces the number of expensive collision tests
that need to be performed in the narrow phase. Possible acceleration data structures are
bounding volume hierarchies, acceleration grids, or k-d trees.
• In the narrow phase, the remaining potential cloth-cloth intersections can then be com-
puted using particle-triangle and edge-edge collision tests. e cloth-solid intersections
are computed by checking the cloth particles with respect to the faces of the solid object.
When using axis-aligned bounding boxes for the triangles in the acceleration structures,
we typically enlarge the bounding box by the thickness of the cloth, e.g., 10
3
m. Of course,
as particles and triangles move around in the simulation the acceleration structure has to be
updated in every iteration.
Collision detection algorithms can be classified by when they look for collisions. To be
more precise, we have the following.
• Discrete time collision detection will look for all particles that are in close proximity at
the beginning of the time step and will add constraints or penalty forces to particles that
appear to be colliding. is will hopefully prevent the collision but there are no guarantees
and this is why algorithms need failure modes to recover from collision. ese methods
are also known as a posteriori. To reliably resolve the collision continuous time algorithms
will be needed.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.