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.

View, browse and sort the ever-growing list of GDC sessions by time, pass type, topic, and format. With GDC Session Scheduler, you can build your schedule in advance and access it during the show via export or with the GDC Mobile App, once live.

If you've registered for GDC, you can use the same login credentials for your Session Scheduler account. Adding a session to your schedule does not guarantee you a seat. Sessions do fill up, so please arrive early to sessions that you would like to attend.

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

Gino van den Bergen (Physics Programmer, Dtecta)

Location: Room 2006, West Hall

Date: Tuesday, March 17

Time: 4:40pm - 5:10pm

Pass Type: All Access Pass, Core+Summits Pass, Summits Pass - Get your pass now!

Topic: Programming

Format: Session

Vault Recording: TBD

Audience Level: Advanced

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.