IVR Chapter 8 Collision Detection

Questions about the lecture 'Introduction to Virtual Reality' of the RWTH Aachen Chapter 8 Collision Detection

0.0 (0)

R. B.

Étudier

R. B.

À propos de ce fichier

This flashcard set delves into advanced collision detection techniques at the university level, focusing on space partitioning, bounding volumes, and computational costs. It covers various methods like voxel grids, octrees, and BSP-trees, along with characteristics of different bounding volumes such as spheres, AABBs, and OBBs. The flashcards explain how to optimize computational costs, handle object transformations, and compute collision responses, making it invaluable for computer science students and professionals working on physics engines, game development, or virtual reality applications.

Cartes-fiches

Utilisateurs

Langue

Anglais

Catégorie

Informatique

Niveau

Université

Créé / Mis à jour

03.02.2017 / 13.05.2018

Fichiers de cartes similaires

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 = N_u * C_u + N_bv * C_bv + N_p * C_p_with u is BV updated, bv is BV overlap test and p is primitive pair test

What are the effects of C_bv and N_p?

[computational cost.BHV.bounding volumes.collision deteciton, 4]

1. C_bv and N_p depend on broad phase’s scheme

2. Low C_bv due to cheap test might result in high N_p

3. OBB-tree good at N_p

4. AABB-tree good at C_bv

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

What happened 1970s?

[history.collision detection, 2]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

1. Applications of 3D collision detection in robotics

2. Automation continuous time axis

What happened 1980s?

[history.collision detection, 2]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

1. Computational geometry as new research area

2. Geometric algorithms from mathematical point of view

What happened 1984?

[history.collision detection]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Evolving from keyframe animation to PBM (Baraff) for automatic collisions resolving

What happened 1990s?

[history.collision detection]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Evolving from animation to interactive applications

What happened 1995?

[history.collision detection]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

I-COLLIDE the first collision detection library

What happened 1996?

[history.collision detection, 3]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

AABB trees as bounding volumes (Bergen)

What happened 1998?

[history.collision detection]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Discrete oriented polytopes (DOP) (Klosowski)

What are sources of collisions?

[basics.collision detection, 2]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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

1 / 62

Cartes-fiches

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 t_i-1 and t_i

2. Test t_i-0.5

3. If collision then test t_i-0.75else test t_i-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 t_i-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 t_i 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 = N_p * C_pwith F total cost, N_p number and C_p cost of (primitive) pairs tests

What holds for the naive approach?

[computational cost.basics.collision detection]

N_p = (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 N_p via spatial and temporal coherence

2. Optimize C_p 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 |c₁-c₂|>r₁+r₂

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 Sum_i=1ⁿv_iand C_jk = 1/n Sum_i=1ⁿv_ij*v_ij

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 > p_A*p_B then two convex objects do not overlap

Étudier

IVR Chapter 8 Collision Detection

Créer ou copier des fichiers d'apprentissage

Cartes-fiches

Veuillez vous connecter

Google

Apple ID

Microsoft

Switch edu-ID

Edulog

Google

Apple ID

Microsoft

Switch edu-ID

Edulog