Deformable Body SimulationOutlineDeformable body simulation Possible approachesFree-form deformationBasics of m-repsObject representationDiscrete vs ContinuousProperties of m-repsM-rep based deformationSegmentation using m-repsAlgorithmAlgorithm detailsResultsAdvantages of m-rep based deformationsInteractive Skeleton-Driven Dynamic DeformationsWhat is this paper all about?Application AreasChallengesSkeleton and control latticeGeneral IdeasOne simulation stepMesh RequirementsIdeas to achieve our goalsComponentsGoalThe Hierarchical BasisEquations of MotionComputing V“Body Forces”Numerical integrationSkeletal SimulationRegionsSolving the nonlinear systemConjugent Gradient MethodBone ConstraintsLinear Subspace ConstraintsBlended Local LinearizationOne Simulation Step - revisitedTwist ConstraintAdaptationContributions...contributionsSlide 43ReferencesDeformable Body SimulationIpek OGUZCOMP259 – 04.12.2005Outline•M-rep based deformations–Introduction to m-reps–Deformable m-reps for image segmentation•Skeleton-driven deformations–Character animationDeformable body simulationPossible approaches•Finite differences method, using Lagrangian motion equations•Hierarchical models, octrees, etc.•Stability problem: Implicit solvers•Quasi-static solutions: Compute equilibrium state, than animate•BEM assuming constant material properties inside the object•Anatomical modellingFree-form deformation•Embed the object into a domain that is more easily parametrized than the object.•Advantages: –You can deform arbitrary objects–Independent of object representationBasics of m-reps•Atom(‘hub’) position, x•Spoke length, r•Spoke bisector, b•Object angle Ө•b, b ┴and n form local coordinate frame•Left, internal atom•Right, end atomObject representation•Mesh of medial atoms•Here, the middle one is internal, the rest are end atomsDiscrete vs ContinuousProperties of m-reps•The medial locus of an object is represented explicitly.•A fuzzy approximate representation of the object's boundary is implied by the medial locus representation.•An accurate description of the boundary is given by a smooth fine-scale deformation of the fuzzy implied boundary.M-rep based deformation•Mostly used for image segmentation•Can be used for PBS as wellInitial model(ex: from an atlas)Target imageDeformationM-rep FEM modelFEM-based deformationSegmentation using m-reps•Bayesian approach•P(w|f): a posteriori probability•P(f|w): likelihood•P(w): a priori probability•p(f): scaling factor •Optimize P(w|f) over all possible deformations–maximum a posteriori (MAP)Algorithm•Start with an initial model m•Optimize F(m|Itarget)–F is a sum of two terms, log prior, and log likelihood•Can be applied at different scales•The initial model can come from–Geometrical analysis of a set of hand-segmented training images–A single hand-segmented training imageAlgorithm details•Manually place the model in the 3D image,•Find and apply the similarity transform which optimizes F(m|Itarget) •Until convergence, do –For each medial atom in m •{Transform the atom to optimize F(m|Itarget)} •For each boundary tile implied by m –{Shift the position of the tile along the tile’s normal to optimize F(m|Itarget)}Results•VideoAdvantages of m-rep based deformations•Capability for deformation of the interior•Provides a way for appropriate locality based on medical relevance•Multiple scale levels (multi-object, object, object section, boundary)•Correspondences are preservedInteractive Skeleton-Driven Dynamic DeformationsSteve Capell, Seth Green, Brial Curless, Tom Duchamp, Zoran PopovicWhat is this paper all about?•Character animation•We want to tell how the character should act•But we don’t want to tell how the character should move!•The answer: elastically deformable characters modeled with a simple skeletonApplication Areas•Movies: You want to let the animator construct the model easily–Previous work included muscle, skin, etc models – painful process•Games, VR: You want to have interactive rates–Previous work included purely kinematic deformations – not realisticChallenges•We need:–A lot of physical principles–A lot of geometric modelling–A lot of computational tools–Interactive simulation rate–Ease of use•What else could you possibly need?Skeleton and control lattice•Each object Ω has:–A skeleton, S (in red)–A control lattice, K (in black)•The control lattice can have hierarchical scale–K0 (in black) vs K1 (in green)General Ideas•Coarse volumetric control lattice provides the elements for FEM•Motion control: Put line constraints along “bones” of the skeleton•Form regions around bones, and simulate linearly in regions•Hierarchical control lattice: Level-of-detail simulationOne simulation step•For each region do–Extract regional variables from global system–Compute displacement from “rest state” transformed according to the transformation of the “bone”–Build the linear system for solving local equations of motion–Solve the linear system using conjugate gradients•Merge solution from each region, weighted (user-assigned weights)•Update the global system stateMesh Requirements•The mesh can be coarse, but it should encompass the geometric model, to ensure complete integration over interior.•Not necessarily regular grid: could even contain mix of tetrahedra and hexahedra•Could have hierarchical basis, for adaptive level of detail simulationIdeas to achieve our goals•Motion control via skeleton: add line (“bone”) constraints to the finite element model•Make computation simpler: Have an edge in the mesh for each bone •Interactive rate: Linearly solve motion equations around each bone, blending deformation at overlapping regions•Similar approach to free form deformations, but here principles of continuum elasticity are usedComponents•The object (or the character): Domain Ω•The skeleton: a graph S, is a subset of Ω•Joints: Vertices of S•Bones: Edges of S•Motion: p(x, t)•Restriction Map: a piecewise linear function on S, ps(x, t)Goal•Solve for the dynamic motion of the object given the motion of the skeleton•Basically a PDE system with constraint:p(x, t) = ps(x, t) for all xєS•Separate p(x, t) into a rest state r(x) and a displacement d(x, t)The Hierarchical Basis•Control lattice: “Lazy wavelets”•For all i, j, i≠j, the intersection