Fakultät Informatik

A Hexahedral Multigrid Approach for Simulating Cuts in Deformable Objects

 Christian Dick,  Joachim Georgii, Rüdiger Westermann

Computer Graphics and Visualization Group, Technische Universität München, Germany



We present a hexahedral finite element method for simulating cuts in deformable bodies using the corotational formulation of strain at high computational efficiency. Key to our approach is a novel embedding of adaptive element refinements and topological changes of the simulation grid into a geometric multigrid solver. Starting with a coarse hexahedral simulation grid, this grid is adaptively refined at the surface of a cutting tool until a finest resolution level, and the cut is modeled by separating elements along the cell faces at this level. To represent the induced discontinuities on successive multigrid levels, the affected coarse grid cells are duplicated and the resulting connectivity components are distributed to either side of the cut. Drawing upon recent work on octree and multigrid schemes for the numerical solution of partial differential equations, we develop efficient algorithms for updating the systems of equations of the adaptive finite element discretization and the multigrid hierarchy. To construct a surface that accurately aligns with the cuts, we adapt the splitting cubes algorithm to the specific linked voxel representation of the simulation domain we use. The paper is completed by a convergence analysis of the finite element solver and a performance comparison to alternative numerical solution methods. These investigations show that our approach offers high computational efficiency and physical accuracy, and that it enables cutting of deformable bodies at very high resolutions.


The first author is funded by the International Graduate School of Science and Engineering (IGSSE) of the Technische Universität München.

A previous version is available as a technical report.

A Flexible and Interactive Approach for Cutting Deformable Objects
C. Dick, J. Georgii, R. Westermann, Technical Report, November 2010
[Download] [Bibtex]


Accompanying video of the paper [ 64 MB DivX]



Matthias Niessner, our new Professor from Stanford University, offers a number of interesting topics for  master theses.


A new PhD/PostDoc position on  Computational Fabrication and 3D Printing is available at the Computer Graphics & Visualization group.