Convex hull covering of polygonal scenes for accurate collision detection in games
Rong Liu, Hao Ran Zhang, J. H. Busby · 2008
(a) A building model used in computer games. (b) Convex hull covering computed by our algorithm. Figure 1: A result of convex hull covering. (a) A complex building mesh used in games, where front and top walls are culled to reveal the interior structures. The building contains a disconnected collection of closed and open mesh pieces with highly non-uniform tessellations. (b) The convex hulls obtained, shown in different colors, collectively cover the building geometry (they may overlap, hence a covering), but do not take away any original game playing space — this is our accuracy requirement. The original model has 14,608 polygons and the algorithm returned 3,137 convex hulls. Although the convex hull count is still high due to the strict accuracy requirement, about 80 % of collision entity reduction (triangles to convex hulls) still provides great potential to lower the computation cost of collision detection. Decomposing a complex object into simpler pieces, e.g., convex patches or convex polyhedra, is a well-studied geometry problem. A well constructed decomposition can greatly accelerate collision detection since intersections with and between convex objects are fast to compute. In this paper, we look at a particular instance of the convex decomposition problem which arises from real-world game development. Given a collection of polyhedral surfaces (possibly