0 0 10 views

**Unformatted text preview:**

Deformable Materials 3 Adrien Treuille Overview Last Week s Question Elastic Collision Detection Collision Detection for Reduced Models Surface Based Elastics New Question Overview Last Week s Question Elastic Collision Detection Collision Detection for Reduced Models Surface Based Elastics New Question Question How could we reduce the cost of simulation for a very nely 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 simpli ed 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 ne 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 interior Overview Last Week s Question Elastic Collision Detection Collision Detection for Reduced Models Surface Based Elastics New Question Overview Last Week s Question Elastic Collision Detection Collision Detection for Reduced Models Surface Based Elastics New Question Collision Detection Broad Phase Guess collisions between objects Narrow Phase Determine collision points Broad Phase Fast Interval Operations class BroadIntersection int body 1 index int body 2 index bool x overlap bool y overlap bool z overlap Temporal coherency keep list between timesteps Use insertion sort Expected O n runtime Update overlaps during insertion sort Three cases A minimum and a maximum ip Toggle overlap bit Don t toggle Two minima ip Don t toggle Two maxima ip Narrow Phase Find exact collision point Use a geometric partitioning algorithm Two types Bounding Volume Hierarchies Spatial Partitioning BVH vs Spatial Partitioning BVH SP Object centric Spatial redundancy Space centric Object redundancy From Doug James s Slides BVH vs Spatial Partitioning BVH SP Object centric Spatial redundancy Space centric Object redundancy From Doug James s Slides BVH vs Spatial Partitioning BVH SP Object centric Spatial redundancy Space centric Object redundancy From Doug James s Slides BVH vs Spatial Partitioning BVH SP Object centric Spatial redundancy Space centric 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 How Directly How Which is faster Geometric Subdivision Topological Subdivision Triangle Intersection Edge Edge Vertex Face Summary 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 Question Overview Last Week s Question Elastic Collision Detection Collision Detection for Reduced Models Surface Based Elastics New Question superposition of displacement basis functions that are known at the time of BD Tree construction The BD Tree then tracks average motions associated with these displacement fields and locally bounds their displacement deviations As we will see the fewer and more spatially coherent the displacement fields are the better BD Trees tend to perform Suppose we have N undeformed point locations p T Without loss of generality we will assume that the p on p detec1 N ecent sur a b c d a linear superdeformed point locations p are approximated by Sphere 2 Example deformation Reference shapecolumns p b Dis of U The position ofFigure M displacement fields a given by the rchy used placement field U c Field U d Deformed shape p 1 2 lan 1994 amplitude of each displacement field is given by corresponding reBradshaw duced ding vol coordinates q so that see Figure 2 Collision Detection for 3 Bounded Deformation Trees degradaM This section describes the construction derivation postHierarchy p p updating Uq andoruse of BD Trees pi pi Without Uiloss 1 deformation j q j of ween feagenerality we consider sphere trees constructedj 1 on polygonal as well as models henceforth and briefly discuss how these could be extended loth and to bounding boxes Throughout we will describe the bounding with radius coordinates R and center point c seedetermined Figure 5 Note that sphere the reduced q are by some other formable ion algoSource Doug L James and Dinesh K Pai BD Tree Output Sensitive Collision Detection for Collision possibly nonlinear black boxACM Transactions process therefore Detection for Reduced Models on Graphics ACM SIGGRAPH 2004 23 3 pp although the shape 3 1 BD Tree Construction A Wrapped Hierarchy 393 398 n e g at spheres see Figure 3 Layered hierarchies are important in previous work on updating using hierarchical linear time sphere refitting e g see Brown et al 2001 Unfortunately layered bounds can fit more loosely than wrapped ones Guibas et al 2002 By updating a wrapped hierarchy BD Trees can obtain tighter bounds than the deformable layered case see Figure 4 Hierarchy Types Figure 3 The wrapped hierarchy left has smaller spheres than the Wrapped Layered layered hierarchy right The base geometry is shown in green Hierarchy Hierarchy with five vertices Notice that in a wrapped hierarchy the bounding sphere of a node at one level need not contain the spheres of its descendents and so can be significantly smaller However since each Source Doug L James and Dinesh K Pai BD Tree Output Sensitive Collision Detection for Collision Detection for Reduced Models ACM Transactions on Graphics ACM SIGGRAPH 2004 23 3 pp 393 398 propose to compute each sphere s updated center c and an updated conservative radius R as functions of the reduced coordinates q Sphere Center Update The update processbounding is illustrated in during Figure deformation 5 A key point is that Figure 5 BD Tree sphere illustrating evaluated as afor this becenter performed each sphere and the update change can in the c cindependently weighted average of and reduced also forpmany models enlarged radius R R the efficiently points pi the conservatively