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 holds for the candidates?
[overlap test.OBB.bounding volumes.collision detection, 2]
Are perpendicular 1. to a face and 2. to an edge
How many candidates exist?
[overlap test.OBB.bounding volumes.collision detection, 2]
1. #candidates is 2*F + E² with faces F and edges E
2. OBBs have only E=3 and F=3 → 15 axis test
What are the characteristics?
[k-DOP.bounding volumes.collision detection, 3]
1. k is the amount of fixed orientations
2. Representation with k/2 directions and pairs of min, max
3. Better for deformable object
How does it work?
[overlap test.k-DOP.bounding volumes.collision detection]
If projections in at least one direction do not overlap then no overlap
What is a problem?
[object transformation.bounding volumes.collision detection, 2]
1. Even though translation works for all representations
2. No rotation for AABB and k-DOP
How to react?
[object transformation.bounding volumes.collision detection]
Perform recomputation for AABB and k-DOP
How to compute?
[recomputation.object transformation.bounding volumes.collision detection, 4]
1. Additional storage of the convex hull
2. Check extremal vertices after rotation
3. Compare with adjacent vertices of convex hull
4. “Climb the hill” to extremal vertex
How to deal with collision detection localization?
[bounding volumes.collision deteciton]
Using hierarchies (BVH)
What holds for different levels?
[BVH.bounding volumes.collision deteciton, 2]
1. Higher precision for lower levels
2. Fast computing for higher levels
What is the effect of the branching factor?
[BVH.bounding volumes.collision deteciton, 2]
1. Fewer nodes → lower total update costs
2. Lower recursion depth → lower memory requirements of stack
What are the characteristics?
{top-down.BHV.bounding volumes.collision deteciton, 4]
1. Start with object
2. Fit BV to object
3. Split object recursively according to heuristic
4. Stop if BV contains less than n primitives
What are the characteristics?
{bottom-up.BHV.bounding volumes.collision deteciton, 4]
1. Start with primitives
2. Fit BV to given number of primitives
3. Group primitives recursively
4. Stop if single BV occurs
What are the goals?
[BHV.bounding volumes.collision deteciton, 2]
1. Balanced tree
2. Tight-fitting BV
How does it work?
[interference check.BHV.bounding volumes.collision deteciton, 2]
1. If nodes overlap then test children
2. Recursively until primitives are found
How to compute?
[computational cost.BHV.bounding volumes.collision deteciton]
F = Nu * Cu + Nbv * Cbv + Np * Cp with u is BV updated, bv is BV overlap test and p is primitive pair test
What are the effects of Cbv and Np?
[computational cost.BHV.bounding volumes.collision deteciton, 4]
1. Cbv and Np depend on broad phase’s scheme
2. Low Cbv due to cheap test might result in high Np
3. OBB-tree good at Np
4. AABB-tree good at Cbv
What are the characteristics?
[space partitioning.collision detection, 2]
1. Space centric
2. Object redundancy
What is the idea?
[space partitioning.collision detection, 2]
1. Assign object to discrete space cells
2. Only test pairs of objects sharing cell
What are the data structures?
[space partitioning.collision detection, 3]
1. Voxel grid
2. Octree and k-d tree
3. BSP-tree
What are the characteristics?
[voxel grid.space partitioning.collision detection, 5]
1. Object independent
2. Uniform rectangular axis-aligned cells
3. Scan conversion of primitives to grid OR AABBs of primitives
4. Fast cell access
5. Optimal cell size concerns #primitives per cell
What are the characteristics?
[oc- and k-d tree.space partitioning.collision detection, 6]
1. Object dependent
2. Hierarchical structures
3. Non-uniform rectangular axis-aligned cells
4. Root node corresponds to AABB of a scene
5. Leaves corresponds to primitive list
6. Subdivision can be uniform [Octree] or not [k-d tree]
What are the characteristics?
[bsp tree.space partitioning.collision detection, 3]
1. Object dependent
2. As k-d tree with arbitrarily oriented planes
3. Cells are convex
