IVR Chapter 8 Collision Detection
Questions about the lecture 'Introduction to Virtual Reality' of the RWTH Aachen Chapter 8 Collision Detection
Questions about the lecture 'Introduction to Virtual Reality' of the RWTH Aachen Chapter 8 Collision Detection
-
- 1 / 62
-
Flashcards
What happened 1970s?
[history.collision detection, 2]
1. Applications of 3D collision detection in robotics
2. Automation continuous time axis
What happened 1980s?
[history.collision detection, 2]
1. Computational geometry as new research area
2. Geometric algorithms from mathematical point of view
What happened 1984?
[history.collision detection]
Evolving from keyframe animation to PBM (Baraff) for automatic collisions resolving
What happened 1990s?
[history.collision detection]
Evolving from animation to interactive applications
What happened 1995?
[history.collision detection]
I-COLLIDE the first collision detection library
What happened 1996?
[history.collision detection, 3]
1. PC game “Quake” with BSP trees
2. Spheres as bounding volumes (Hubbard)
3. Oriented boxes as bounding volumes (Lin)
What happened 1997?
[history.collision detection]
AABB trees as bounding volumes (Bergen)
What happened 1998?
[history.collision detection]
Discrete oriented polytopes (DOP) (Klosowski)
What are sources of collisions?
[basics.collision detection, 2]
1. User interaction e.g. selection of objects
2. Dynamic virtual environment with movement and deforming
What holds for real vs virtual world?
[basics.collision detection, 3]
1. Two objects can [V] not [R] occupy same point in space at same time
2. Collision is hit [R], configurations of interpenetrating objects [V]
3. Response is physical behavior [R], its real-time simulation [V]
What are the challenges?
[basics.collision detection, 3]
1. Correctness
2. Real-time and performance
3. Precision and stability
What are the characteristics?
[correctness.basics.collision detection, 2]
1. Discrete time in digital computers
2. Objects are geometrical approximation
What is the characteristic?
[real-time and performance.basics.collision detection]
Complex scenes with limited processing power and memory
What is the characteristic?
[precision and stability.basics.collision detection]
Rounding errors due to floating points yield incorrect answers
Which method handles interference of objects?
[basics.collision detection]
Interference detection or collision query
What are the characteristics?
[interf det and coll query.basics.collision detection, 2]
1. Statically detect if object are inside others (penetration depth)
2. If used repeatedly for collision detection, can miss fast objects
What are the characteristics?
[sampling.basics.collision detection, 3]
1. Exact time and location may need to be found
2. Discrete interval
3. Swept volumes
What are the characteristics?
[discrete interval.sampling.basics.collision detection, 2]
1. Can miss collision entirely (So-called in-between collisions)
2. Can return wrong collision
What are the characteristics?
[discrete swept volumes.basics.collision detection, 2]
1. Sufficient but no necessary for collision free objects
2. Perform subdivision
What is the interesting result?
[collision response.basics.collision detection, 2]
1. Positive interference
2. Contact
How to react for ego shooters?
[collision response.basics.collision detection]
Object disappears
How to react for object selection?
[collision response.basics.collision detection]
Object color changes
How to react for physically-based VEs?
[collision response.basics.collision detection]
Compute forces and impulses
Which values are needed?
[VEs.collision response.basics.collision detection, 3]
1. When? → Time of collision
2. Where? → Contact point
3. How? → Contact normal to point and separating plane
How to compute?
[time.VEs.collision response.basics.collision detection, 3]
1. Use ti-1 and ti
2. Test ti-0.5
3. If collision then test ti-0.75 else test ti-0.25
What are the characteristics?
[time.VEs.collision response.basics.collision detection, 2]
1. Computationally expensive
2. No guarantee for earliest collision time
What is the first way to compute?
[contact point.VEs.collision response.basics.collision detection, 2]
1. Compute pair of closest points at ti-1
2. Normal is difference of pair of points
What is the second way to compute?
[contact point.VEs.collision response.basics.collision detection, 2]
1. Compute penetration depth at ti as length to translate objects back to touching constant
2. Normal is depth vector
How to compute?
[contact normal.VEs.collision response.basics.collision detection, 2]
1. Eps-neighborhood around point
2. Assume convex property inside neighborhood
How to compute?
[computational cost.basics.collision detection]
F = Np * Cp with F total cost, Np number and Cp cost of (primitive) pairs tests
What holds for the naive approach?
[computational cost.basics.collision detection]
Np = (N over 2) = ½*N*(N-1) ~ O(N) with N number of objects in scene
How can we optimize?
[computational cost.basics.collision detection, 2]
1. Reduce Np via spatial and temporal coherence
2. Optimize Cp via object shapes complexity (accuracy vs performance)
What are the characteristics?
[bounding volumes.collision detection, 2]
1. Object centric
2. Spatial redundancy
What are the requirements?
[bounding volumes.collision detection, 3]
1. Tight fitting
2. Fast overlap test
3. Efficient re-computation of BV
What are the types (from cheap to expensive but tight)?
[bounding volumes.collision detection, 5]
1. Sphere
2. Axis aligned bounding boxes (AABB)
3. Oriented bounding boxes (OBB)
4. k-discrete oriented polytopes (DOP)
5. Convex hull
What are the characteristics?
[sphere.bounding volumes.collision detection, 4]
1. Center c and radius r
2. Check with |c1-c2|>r1+r2
3. Invariant to rotations
4. Translation applied to c
What are the characteristics?
[AABB.bounding volumes.collision detection, 2]
1. Check on every 1D axis and tag pairs for all dimensions
2. 3 axis test
What are the characteristics?
[OBB.bounding volumes.collision detection, 5]
1. Use point sample of convex hull to get n vertices
2. Compute mean and covariance matrix of samples with mye = 1/n Sumi=1nvi and Cjk = 1/n Sumi=1n vij*vij
3. Mean is center of the box
4. Eigenvectors of the covariance matrix are directions
5. Better for rigid bodies
What are the characteristics?
[overlap test.OBB.bounding volumes.collision detection, 2]
1. Strongly depends on planes
2. Use projection and interval
How does it work?
[overlap test.OBB.bounding volumes.collision detection]
If separating plane \exists L: T*L > pA*pB then two convex objects do not overlap
