Deformable Materials 3Adrien TreuilleOverview•Last Week’s Question•Elastic Collision Detection•Collision Detection for Reduced Models•Surface-Based Elastics•New QuestionOverview•Last Week’s Question•Elastic Collision Detection•Collision Detection for Reduced Models•Surface-Based Elastics•New QuestionQuestion•How could we reduce the cost of simulation for a very finely discretized surface?•Are there cheap ways of getting volumetric behavior without a full tetrahedralization?•How can collision constraints be integrated?•How to simulate plasticity?Solutions•bounding volume tree w/ tetrahedra at leaves•simulate parent nodes instead of leaves (if stresses are close)•simulate on a simplified mesh (make details into bump maps)•adaptive tetrahedralization based on force magnitudes•come up with tetrahedralization that best captures the simulation based on precomputed simulations•springs connected to a “skeleton”•plasticity based on sparse springs connecting the surface mesh to itself•embed fine tetrahedral mesh as barycentric coordinates on a coarse tetrahedral mesh, solve on coarse mesh•angular springs in a surface discretization of the dynamics•nonuniform tetrahedral mesh based on the curvature of the surface mesh•greater distance to the surface -- the larger the tetrahedron•“shell” tetrahedralization with springs on the interiorOverview•Last Week’s Question•Elastic Collision Detection•Collision Detection for Reduced Models•Surface-Based Elastics•New QuestionOverview•Last Week’s Question•Elastic Collision Detection•Collision Detection for Reduced Models•Surface-Based Elastics•New QuestionCollision Detection•Broad Phase:•Guess collisions between objects.•Narrow Phase:•Determine collision points.Broad PhaseFast Interval Operations•Temporal coherency: keep list between timesteps.•Use insertion sort.•Update overlaps during insertion sort.•Three cases:•A minimum and a maximum flip. •Two minima flip.•Two maxima flip.class BroadIntersection {int body_1_index;int body_2_index;bool x_overlap;bool y_overlap;bool z_overlap;}Expected O(n) runtime.Toggle overlap bit.Don’t toggle.Don’t toggle.Narrow Phase•Find exact collision point.•Use a geometric partitioning algorithm.•Two types:•Bounding Volume Hierarchies•Spatial PartitioningBVH vs. Spatial PartitioningBVH: SP:- Object centric - Space centric- Spatial redundancy - Object redundancy(From Doug James’s Slides.)BVH vs. Spatial PartitioningBVH: SP:- Object centric - Space centric- Spatial redundancy - Object redundancy(From Doug James’s Slides.)BVH vs. Spatial PartitioningBVH: SP:- Object centric - Space centric- Spatial redundancy - Object redundancy(From Doug James’s Slides.)BVH vs. Spatial PartitioningBVH: SP:- Object centric - Space centric- Spatial redundancy - Object redundancy(From Doug James’s Slides.)Bounding Volume Hierarchies•How to create a BVH:•Geometric Subdivision•Topological Subdivision•How implement?•Which is better?•How to update a BVH:•Bottom Up•Directly•Which is faster?GeometricSubdivisionTopologicalSubdivision(How?)(How?)Triangle Intersection•Edge-Edge•Vertex-FaceSummary•Broad Phase:•Guess collisions between objects.•Narrow Phase:•Determine collision points.Overview•Last Week’s Question•Elastic Collision Detection•Collision Detection for Reduced Models•Surface-Based Elastics•New QuestionOverview•Last Week’s Question•Elastic Collision Detection•Collision Detection for Reduced Models•Surface-Based Elastics•New QuestionCollision Detection for 1.1 Related WorkMany important methods have been developed for collision detec-tion with rigid models. We refer the reader to these recent sur-veys: [Lin and Gottschalk 1998; Jimenez et al. 2001]. Spheretrees are a canonical example of a bounding volume hierarchy usedfor collision detection and proximity queries (e.g., [Quinlan 1994;Hubbard 1995; Brown et al. 2001; Guibas et al. 2002; Bradshawand O’Sullivan 2004]). Collision detection with bounding vol-ume hierarchies is output-sensitive and provides graceful degrada-tion [Hubbard 1995; Dingliana and O’Sullivan 2000]. Hierarchyconstruction can be based on either spatial proximity between fea-tures within the undeformed model or on mesh topology, as well asinter-surface proximity (as in [Bridson et al. 2002] for cloth, andin [Warren and Weimer 2001] for subdivision hierarchies).Many of these methods could be directly applied to deformableobjects. The major cost for hierarchical collision detection algo-rithms is updating the hierarchy after every deformation, e.g., ateach time step, before queries are performed. As a result, much at-tention has been drawn to hierarchies with easy to compute bounds(e.g., [van den Bergen 1997; Ganovelli et al. 2000]). Alterna-tively, intelligent methods for updating the bounding hierarchiesand exploiting temporal coherence have been explored [Guibaset al. 2002; Brown et al. 2001; Larsson and Akenine-M¨oller 2001].Larsson et al. [2003] propose a collision detection algorithm spe-cialized for morphing that has features similar to ours (and is aspecial case). Because we use a more general deformation model(Eq. 1) our method can be applied in a more general setting (see sec-ond paragraph of Sec. 1), and we derive significantly less expensivebounds (Secs. 3.2 and 3.5).Recently, hardware-accelerated collision detection methods havereceived increased attention; see [Manocha et al. 2002] for a recentoverview. These general purpose methods are very useful, but tendto produce coarser approximations, since they are limited by thesize of frame buffer memory, and not floating point precision. Notethat the entire model has to be rendered for collision detection inthese methods, and not just visible portions; a notable advantageof our approach is that it only requires touching a potentially smalloutput-sensitive subset of model polygons.2 Reduced Deformation ModelBD-Trees exploit spatially coherent motion that can be describedas a combination of (hopefully smooth) displacement fields. Math-ematically, we assume a general shape model based on the linearsuperposition of displacement basis functions that are known atthe time of BD-Tree construction. The BD-Tree then tracks aver-age motions associated with these displacement fields, and