Parallel Collision Algorithms for Cutting Simulation of Octree-based Deformable Objects

To increase the performance of collision processing during deformable cutting simulations, and to solve the problem of cutting negatively affecting the stability of deformation, parallel implementations for collision processing in octree-based deformable cutting simulations are proposed. A linked voxel model representing material connectivity and an adaptive octree mesh used for deformation are combined to model deformable objects. The surface mesh used for collision and graphics display is reconstructed from the linked voxel model. Broad phase collision uses a spatial Hash table of the octree mesh to construct potential collision pairs. Narrow phase collision uses topology-aware distance field interpolation of the distance field values at voxel centers to detect collision and calculate penetration depths. Collision and self-collision of deformable objects are performed on GPU using a novel multi-stage detection and reduction method, while collision between deformable objects and the cutting tool is performed on CPU simultaneously using multi-threading techniques. Cutting is performed by disconnecting links swept by the cutting tool, reconstructing cut surfaces near disconnected links, recursively subdividing and duplicating octree elements, and recalculating distance field values using a fast marching method. The results of simulation tests show that when compared to a 3-threaded CPU implementation, the proposed GPU-accelerated deformable object collision and self-collision algorithm is 76%~215% faster; while a 3-threaded CPU implementation of the proposed cutting tool-deformable object collision algorithm is 132%~190% faster when compared to a single-threaded implementation.