GDC is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

Use the GDC 2021 Session Viewer to browse and sort the ever-growing list of sessions by day, time, pass type, topic, and format. All registered attendees will be able to build their personal schedule directly within the event platform, once live early July 2021. All times are listed in Pacific Time.

Math In Game Development Summit: Conservative Mesh Decimation for Collision Detection and Occlusion Culling

Gino van den Bergen  (Physics Programmer, Dtecta)

Date: Tuesday, July 20

Time: 1:20pm - 1:50pm

Pass Type: All Access Pass, Summits Pass

Topic: Programming

Format: Session

Vault Recording: Video

Collision detection and occlusion culling can be sped up considerably by reducing the complexity of the used triangle meshes. A popular method for decimating a mesh is the Garland-Heckbert algorithm. This approach uses edge contractions to reduce the number of triangles. The maximum error of the decimated mesh is bounded by a so-called quadric error metric (QEM). In this talk, properties of QEMs are discussed. We show what causes issues when using QEMs to find positions for newly created vertices and how to improve mesh quality. We show how to choose the new vertex positions conservatively, i.e. such that the decimated mesh either completely encapsulates the original mesh for the purpose of collision detection, or is completely encapsulated by the original mesh for the purpose of occlusion culling. Performance tweaks and termination criteria are addressed, and trade-offs are discussed.


Attendees will learn about the pitfalls of QEMs and how to overcome them. We discuss the unconstrained Garland-Heckbert algorithm and how to adapt it for returning conservative meshes. We present a few performance optimizations, and a novel approach for constructing tighter QEMs that bound maximum errors.

Intended Audience

There is a lot of math in this talk, however, images, screen shots, and a demo of our decimation tool should make this talk accessible to attendees that only have a sketchy understanding of the subject matter. The talk is targeted at programmers that work on game physics or graphics.