Optimizing dynamic mesh colliders using search algorithms

Mesh colliders provide the basis for representing any non-standard geometry within a physics simulation. Collision detection on large meshes often relies on Bounding Volume Hierarchies (BVH) to reduce the number of collision pairs when checking for collisions. However, if the mesh is dynamic (meaning the vertices are allowed to move independently to morph the mesh), then continuously updating a large BVH can be too computationally expensive for real-time simulations. This report proposes a solution for optimizing large dynamic meshes to allow for real-time dynamic terrains in physics simulations. Terrains often use large mesh colliders; however, the proposed solution, dubbed Smart-Mesh, works by dynamically generating smaller mesh colliders from the triangles within the larger mesh. These smaller colliders follow other colliding objects near the larger mesh. Smart-Mesh uses graph search algorithms, including Best-First Search and Breadth-First Search, to find and collect a set of vertices that are closest to other colliding objects. Through these optimizations and others mentioned in this report, the complexity of updating mesh colliders for large dynamic meshes is reduced from O(n log n) to O(n) for the general case, and to O(1) for the case when simplifying assumptions are made about the mesh.