Convex Decomposition of a Triangle Soup

Radical Entertainment is a video game developer which creates and develops games for all current and next generation platforms. Collision detection forms an indispensable part in today’s 3D game engines. Due to increasing size of the 3D objects used in game development, high-performance collision detection running directly on these objects requires a significant amount of work. To allow for real-time collision detection between a 3D object and other objects in the game environment, the typical approach is to first find for each object a set of best-fitting convex hulls. Collision detection can then be conservatively, yet efficiently, carried out by detecting the collision between the set of convex hulls. In this project, in collaboration with Radical Entertainment, the intern will focus on 3D objects represented by triangle soups, where a “soup” of triangles without explicit connectivity roughly approximates the surface of an object. The goal is to compute a “good” set of convex hulls for an arbitrary 3D object represented by a triangle soup, where “good” means that the number of convex hulls is small, while the volume enclosed by the convex hulls is also a close approximation to the volume bounded by the original object. The small number of convex hulls helps improve the efficiency of collision detection; while the tightness of bounding by the convex hulls lead to more accurate collision detection.

Faculty Supervisor:

Dr. Richard Zhang

Student:

Frank Liu

Partner:

Radical Entertainment

Discipline:

Computer science

Sector:

Information and communications technologies

University:

Simon Fraser University