Chunked Bounding Volume Hierarchies for Fast Digital Prototyping Using Volumetric Meshes

Area of Science:

• Computer Graphics
• Computational Geometry
• Scientific Simulation

Background:

• Collision detection is crucial for accurate digital prototyping simulations.
• Volumetric meshes, common in simulations, lead to larger Bounding Volume Hierarchies (BVHs) than surface meshes.
• Efficiently handling large BVHs on parallel hardware like GPUs is challenging.

Purpose of the Study:

• To propose a novel approach for collision detection of volumetric meshes using chunked BVHs.
• To optimize BVH management for large datasets in digital prototyping.
• To enhance the performance of collision detection on Graphics Processing Units (GPUs).

Main Methods:

• Developed an algorithm to split large volumetric meshes into smaller chunks, each with a limited-size BVH.
• Implemented guided, all-pairs testing on chunked meshes suitable for GPU parallelization.
• Analyzed performance bottlenecks, focusing on data structure conversion and GPU implementation efficiency.

Main Results:

• The proposed chunking method achieved up to a two-orders-of-magnitude speedup on GPUs compared to unchunked approaches.
• Chunking proved simpler and more effective for GPUs than dynamic load balancing methods.
• GPU solutions, even with OpenMP accelerated data conversions, outperformed CPU solutions by 20%.

Conclusions:

• Mesh chunking with limited-height BVHs is an effective strategy for accelerating collision detection on GPUs.
• Data structure conversion, not data transfer, was identified as a key performance impediment.
• The approach demonstrates significant speedups for complex rigid and deformable body simulations across various GPUs.