Divided Voxels: an efficient algorithm for interactive cutting of deformable objects

摘要

Efficient algorithms that support dynamic topological updates are necessary for the simulation of progressive interactive cutting of deformable objects. Existing mesh-based techniques suffer from the generation of ill-shaped elements, whereas voxel grid-based methods require additional cut surfaces to be generated or the use of lookup tables for pre-computed cutting patterns. To overcome these limitations of existing methods, we propose a novel voxel-based topological operator, divide, which divides a voxel into two voxels identical to the original voxel's size by dynamically distributing its voxel elements (nodes, edges) into the newly divided voxels until the cutting of the original voxel is completed. The connectivity between the divided voxels and the neighbors of the original voxel is retained during the cut, and new connectivity between the adjacent divided voxels is generated to represent the continuity of the cut. As a result, the cut surface can be generated directly from the divided voxels on the fly, and the correspondence between the cut surface and the simulation voxels is maintained without any additional effort. We use several example problems to demonstrate the efficiency of our method and compare it with other existing approaches.