Why do we need a broad phase and a narrow phase in collision detection?
broad phase: fast search for approximate collision
narrow phase: exact location of collision
speed up the process
Name different types of bounding objects and sort them by efficiency of the collision test!
sphere, aabb, convex hull
Explain the different bounding object types. What are there advantages and disadvantages?
Sphere: - smallest sphere that encloses a object
- simple collision, Invariant to rotaion
- poor bounding
AABB: - box with edges are aligned with axes of coordinate system
- simple collision
- not rotation invariant, poor bounding
Convex Hull: - smallest convex set that contains all points of the mesh
- Invariant to rotation, optimal bound
- expensive to compute
What is the separating hyperplane theorem about?
If two convex objects are not penetrating, there exists an axis for which the projection of the objects will not overlap
How can we use the separating axis theorem to determine if a collision occured?
compute the projection for every edge, if one axis with no overlap exists, no collision occured
Apply different space partitioning techniques to a set of randomly drawn objects!
KD-Tree, Grid-Based, Spatial Hashing
What is the runtime complexity of a bounding volume hierarchy collision detection?
log(n)
What are desirable properties for bounding volume hierarchy?
Balanced, minimal volume, minimal siblings overlap, nodes should be near
each other
Explain Feature-based collision detection using Voronoi regions!
Two objects, find the two closest points between features of these, if points lie in Voronoi region of the other feature, no other points of the objects are closer to each other
Draw the Minkowski Sum/Difference of two spheres!
center: center1+-center2
radius: radius1+radius2
Apply the GJK algorithm for a given Minkowski polytope (Minkowski difference)!
How does the expanding polytope algorithm work?
start with the latest GJK simplex structure
expand the clossest edge to the origin outwards with the support function
remove inside edges, repeat until closest edge is a edge of Minkowski polytype
Why can we ignore vertex-to-vertex and vertex-to-edge collisions?
they are degenerate, will result in vertex to face or edge to edge moments later
What is a penality-based collision response and what are its disadvantages?
apply spring force for a short amount of time
Disadvantages:
• Collision response depends on applied forces
• Strong response forces require prohibitively small
time steps
• Objects might get locked for continuous collisions
• Impulse forces take time to propagate through
stacks of objects
How does an impluse-based collision response work?
instead of a force over time, apply a impulse (t = 0), linear velocity = impulse/mass
Why is it difficult to respond to multiple objects at once?
order important -> solve a Linear Complementarity Problem
Last changed2 years ago
