An octree-based proxy for collision detection in large-scale particle systems

Abstract

Particle systems are important building block for simulating vivid and detail-rich effects in virtual world. One of the most difficult aspects of particle systems has been detecting collisions between particles and mesh surface. Due to the huge computation, a variety of proxy-based approaches have been proposed recently to perform visually correct simulation. However, all either limit the complexity of the scene, fail to guarantee non-penetration, or are too slow for real-time use with many particles. In this paper, we propose a new octree-based proxy for colliding particles with meshes on the GPU. Our approach works by subdividing the scene mesh with an octree in which each leaf node associates with a representative normal corresponding to the normals of the triangles that intersect the node. We present a view-visible method, which is suitable for both closed and non-closed models, to label the empty leaf nodes adjacent to nonempty ones with appropriate back/front property, allowing particles to collide with both sides of the scene mesh. We show how collisions can be performed robustly on this proxy structure in place of the original mesh, and describe an extension that allows for fast traversal of the octree structure on the GPU. The experiments show that the proposed method is fast enough for real-time performance with millions of particles interacting with complex scenes.