Proceedings: GI 2008

Convex hull covering of polygonal scenes for accurate collision detection in games

Rong Liu, Hao Zhang, James Busby

Proceedings of Graphics Interface 2008: Windsor, Ontario, Canada, 28 - 30 May 2008, 203-210

  • BibTex

    author = {Liu, Rong and Zhang, Hao and Busby, James},
    title = {Convex hull covering of polygonal scenes for accurate collision detection in games},
    booktitle = {Proceedings of Graphics Interface 2008},
    series = {GI 2008},
    year = {2008},
    issn = {0713-5424},
    isbn = {978-1-56881-423-0},
    location = {Windsor, Ontario, Canada},
    pages = {203--210},
    numpages = {8},
    publisher = {Canadian Human-Computer Communications Society},
    address = {Toronto, Ontario, Canada},


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 with boundaries, holes, and complex interior structures) that model the scene geometry in a game environment, we wish to find a small set of convex hulls such that colliding objects in the scene against such a set of convex hulls produces the same game behavior as colliding against the original surfaces. The vague formulation of the problem is due to the difficulty of defining the space accessible by the objects involved in the game play. Under reasonable assumptions, we arrive at a set of conditions for valid convex decomposition and develop a construction algorithm via greedy merging driven by patch compactness. We show that our validity conditions ensure valid collision-related game behavior. The effectiveness of our decomposition algorithm is demonstrated through real examples from game development. To the best of our knowledge, no previous convex hull decomposition or surface decomposition algorithms were designed to handle the type of models we consider or be able to compute a set of convex hulls that ensure accurate collision detection results.