1	Collision Handling for Virtual Environments Carol O'Sullivan John Dingliana Fabio Ganovelli Gareth Bradshaw
2	"An efficient and realistic collision..." An efficient and realistic collision handling mechanism is fundamental to any physically plausible animation system.
3
4
5	Outline Applications and Challenges Collision Detection Bounding volumes Collision of deformable objects Collision Response
6	Applications Offline Analysis CAD, robotics, movies Realtime and Interactive systems Virtual Environments, autonomous robots, Games Much cross-over research between robotics and graphics [Lin and Canny 1991] and [Lin 1993]
7	More Applications Molecular modeling Training and education systems E.g. virtual surgery, what-if analysis. Human character animation clothes and hair, self-collisions Haptic interfaces touching virtual objects.
8	Virtual Environments - 1 Allow users to enter a computer-generated virtual world and interact with graphical objects. May be immersive or desktop based. Requirement for extremely high and constant frame-rates.
9	Virtual Environments - 2 Physical interactions triggered by collision. Non-deterministic Þ can't pre-process most of the work. More objects, more complexity Þ greater burden on the engine that powers the simulation Need very fast collision handling
10	Problem Timewarp simulation Avalanche took 97 seconds per frame on an SGI Onyx
11	Problem Bottleneck is not the simulation but the number and complexity of contact groups formed. Mirtich favours robustness over efficiency For VEs this is not an option Þ Speed-accuracy trade-off is often needed
12	Rigid body collision detection All-pairs problem: O(N²) problem of detecting collisions between all N objects. Solution: Eliminate objects that couldn't be colliding
13	Hybrid Collision Detection A collision detection method which first performs one or more iterations of approximate tests to identify interfering objects in the entire workspace and then performs more accurate tests to identify the object parts causing interference. Hubbard, Cohen et al., Kitamura et al.
14	Multi-phase approach Broad Phase Narrow Phase Hubbard Progressive refinement levels Exact level
15	Broad Phase Fixed-timestep weakness. Big timestep Þ more efficient but could have tunnelling Small time-step causes a lot of extra unnecessary intersection tests. One solution: Use an adaptive timestep
16	4-dimensional bounds Space-time bounds provide a conservative estimate of where an object may be in the future A fourth dimension represents time Adapt time-step when objects more likely to collide Overlaps of these bounds trigger the narrow phase
17	4-dimensional bounds
18	Sweep and Prune Orthogonally project axis-aligned bounding boxes onto the x, y and z-axes. Intervals which overlap in all three dimensions indicate potential collisions Exploits coherence by using insertion sort Runs in almost constant time for a given number of objects
19	Sweep & Prune
20	Sweep and Prune Extension: Bounding box of the object orientation-independent Bounding box of the volume swept in the time step Hierachical Sweep & Prune
21	Narrow Phase: Exact Level Depends on model representation In V.Es, polygonal models prevalent Survey of CD algorithms between other geometric models Lin and Gottschalk Often many polygons to approximate surfaces Þ CD can be expensive Problems: special cases, tunnelling…
22	Exact Level - Assumptions Exact level algorithms usually assume convexity. Non-convex polytopes must be represented by hierarchies of convex components
23	Exact Level: Algorithms Feature-based methods: examine vertices, edges and faces of two polytopes, i.e. their features. Simplex-based methods: simplex: the generalisation of a triangle to arbitrary dimensions. treat a polytope as the convex hull of a point set.
24	Feature-based Algorithms Main goal is to detect whether two polytopes are touching or not All are broadly derived from Lin-Canny Closest Features algorithm. determines whether two objects are disjoint or not, by computing the distance between their closest features.
25	Feature-based Algorithms
26	Closest Features - 1 Voronoi Region constructed for each feature the set of points closer to that feature than any other.
27	Closest Features - 2 Tracks these features, and caches them between subsequent calls to the algorithm. Exploits coherency: uses feature-stepping if closest features have changed, they are going to be adjacent to those cached, and hence finding them is quite efficient.
28	Performance runs in expected constant time if the collision detection time-step is small relative to the objects' speed. I-Collide, V-Collide, Rapid, SWIFT available on the web: http://www.cs.unc.edu/~geom/collide/packages.html Cohen et al. Ponamgi et al.
29	Problems Pair-processing weakness cycling behaviour for penetrating polytopes Difficult to implement due to special cases Needs tolerances to be adjusted (magic number) No measure of penetration V-Clip Mirtich Overcomes most of these limitations Fast and efficient for yes-no answers
30	Simplex-based algorithms Treat a polytope as the convex hull of a point set. Operations performed on simplices defined by subsets of these points. Gilbert et al. (GJK) Rabbitz (exploited coherency) Cameron (Enhanced GJK)
31	GJK - algorithm
32	GJK - algorithm
33	Exact level - conclusions GJK algorithms return the best measure of interpenetration. V-Clip algorithm requires fewer floating-point operations Both work well for slightly non-convex objects, but become very inefficient as the level of non-convexity increases.
34	Bounding Volume Hierarchies for Interactive Collision Handling
35	The Principle If a volume B includes a volume A, it is called bounding volume for A No object can intersect A without intersecting B If two bounding volumes do not overlap, the same hold for the volumes included
36	The Principle What if they do overlap? Refine.
37	Questions! What kind of Bounding Volumes? What kind of hierarchy? How to build the hierarchy? How to update (if needed) the hierarchy? How to transverse the hierarchy? All the literature on CD for non-convex objects is about answering these questions.
38	Cost T_c = N_vC_v + N_nC_n+ N_s*C_s v : visited nodes n : couple of bounding volumes tested for overlap s : couple of polygons tested for overlap N: number of C: Cost
39	BHV - Desirable Properties (2) The hierarchy should be able to be constructed in an automatic predictable manner The hierarchical representation should be able to approximate the original model to a high degree or accuracy allow quick localisation of areas of contact reduce the appearance of object repulsion
40	BHV - Desirable Properties The hierarchy approximates the bounding volume of the object, each level representing a tighter fit than its parent For any node in the hierarchy, its children should collectively cover the area of the object contained within the parent node The nodes of the hierarchy should fit the original model as tightly as possible
41	Sphere-Tree [O’Rourke and Badler 1979 , Hubbard 1995a & 1996, Palmer and Grimsdale 1995, Dingliana and O’Sullivan 2000] Nodes of BVH are spheres. Low update cost C_u translate sphere center Cheap overlap test C_v D² < (R₁ + R₂)² Slow convergence to object geometry Relatively high N_u & N_v
42	Sphere-Tree Construction Dingliana and O’Sullivan 2000 Spheres placed around the boxes of a regular oct-tree
43	Sphere-Tree Construction Hubbard 1995a & 1996, Spheres placed along the Medial-Axis (transform)
44	Axis-Aligned Bounding Box [van den Bergen 1997] The bounding volumes are axis aligned boxes (in the object coordinate system) The hierarchy is a binary tree (built top down) Split of the boxes along the longest edge at the median (equal number of polygons in both children)
45	Axis-Aligned Bounding Box The hierarchy of boxes can be quickly updated using the following property: let be the smallest AABB of a region R and two regions.
46	AABB - Overlap If two convex polyhedra do not overlap, then there exists a direction L such that their projections on L do not overlap. L is called Separating Axis Separating Axis Theorem: L can only be one of the following: Normal to a face of one of the polyedra Normal to 2 edges, one for each polyedron
47	AABB - Overlap Ex: There are 15 possible axes for two boxes: 3 faces from each box, and 3x3 edge direction combinations
48	Oriented Bounding Box [Gottschalk et al. 1996]
49	Building an OBB The OBB fitting problem requires finding the orientation of the box that best fits the data Principal Components Analysis: Point sample the convex hull of the geometry to be bound Find the mean and covariance matrix of the samples The mean will be the center of the box The eigenvectors of the covariance matrix are the principal directions – they are used for the axes of the box The principle directions tend to align along the longest axis, then the next longest that is orthogonal, and then the other orthogonal axis
50	Principal Component Analysis
51	Discrete Oriented Polytope [Klosowski et al. 1997] Convex polytope whose faces are oriented normal to k directions Overlap test similar to OBB k/2 pairs of co-linear vectors k/2 overlap tests k-DOP needs to be updated in a similar way as the AABB AABB is a 6-DOP
52	Discrete Oriented Polytope [Klosowski et al. 1997]
53	QuOSPOs Combines OBB with k-DOPs Large number of discrete oriented slabs Each node has Primary Orientations (OBB) SAT Slabs closest to primary orientations OBB mapped onto primary orientations
54	Swept Sphere Volume [Larssen et al. 1999] Convolution of sphere with geometric primitive Point Swept Sphere (PSS) Line Swept Sphere (LSS) Rectangle Swept Sphere (RSS) Provides similar tightness of fit to OBB Fitted using an OBB Reduces update cost (C_u) and overlap cost (C_v) whenever geometry is well suited to the PSS/LSS
55	Interruptible Algorithm [Hubbard 1995a, Dingliana and O’Sullivan 2000] Maintain consistently high frame-rates Smooth simulation prevents simulator sickness Omits the final stage and interrupts the narrow phase when time slot has expired Time critical computing BVH approximation is used for collision response Tightness of BHV is critical to simulation quality
56	Interruptible Collision Detection
57	Scheduling
58	Causality - 1
59	Causality - 2
60	So… Introduction of a time delay at the point of collision reduces the perception of causality Interruptible Collision Detection is currently the only feasible solution for large numbers of objects interacting in real-time (on low-end platforms).
61	Perception-based Graphics Physically Accurate Graphics? OR Visually Plausible Graphics?
62	Perception of collisions What are the factors? Mental models of dynamics Clement, Profitt, Gilden Perception of causality Michotte Eccentricity (peripheral vision) Distractors Velocity, distance etc…
63	Gaze-directed Collision Handling
64
65	Conclusions: The Laws! CH in VE must be: Consistent, not correct Interruptible – Time Critical Plausible “The best way to implement physics is not to do it” [in “Real time physics: a cheater’s guide” S.Collins (Havok), EG-IRL 2002]