My name is Randy Gaul. For Team Atmos I'm developing all the physics simulation and collision detection code. So far a lot of features have been finished and right now an interesting problem has sprung up.

Imagine a world of triangles. This probably isn't too hard since most modern games are composed of huge numbers of triangles. Very often these triangles are only really used for rendering, and an entirely different set of geometry that is invisible represents the world that the player can interact with and walk around upon. This is one style of creating the collision geometry of a world and can take artists and level designers a long time to complete.

An alternative is to pick out groups of triangles used for rendering and then have these represent collision geometry directly. Collision detection with triangles is full of hairy problems, the most notorious of which would be collision tunneling. One strategy to avoid tunneling entirely is to compute the time of impact of when a shape

Since many games, including Dischord, have many triangles collision detection code gets bogged down easily. A broadphase is needed to lower the number of pairwise collision tests that are performed at each simulation step. A popular style of broadphase is the dynamic AABB tree. However, the dynamic AABB tree alone isn't enough when a game has tons and tons of triangles representing the world. If all these hundreds of thousands (or millions) of triangles are individually placed into the dynamic AABB tree it will become over-saturated with AABBs and run slowly. Here's a video I made a while ago to show off a 2D dynamic AABB tree:

Imagine a world of triangles. This probably isn't too hard since most modern games are composed of huge numbers of triangles. Very often these triangles are only really used for rendering, and an entirely different set of geometry that is invisible represents the world that the player can interact with and walk around upon. This is one style of creating the collision geometry of a world and can take artists and level designers a long time to complete.

An alternative is to pick out groups of triangles used for rendering and then have these represent collision geometry directly. Collision detection with triangles is full of hairy problems, the most notorious of which would be collision tunneling. One strategy to avoid tunneling entirely is to compute the time of impact of when a shape

*should*collide with a triangle. This time of impact is usually somewhere in the middle of two game frames and has to be handled with some kind of sub-frame algorithm.Since many games, including Dischord, have many triangles collision detection code gets bogged down easily. A broadphase is needed to lower the number of pairwise collision tests that are performed at each simulation step. A popular style of broadphase is the dynamic AABB tree. However, the dynamic AABB tree alone isn't enough when a game has tons and tons of triangles representing the world. If all these hundreds of thousands (or millions) of triangles are individually placed into the dynamic AABB tree it will become over-saturated with AABBs and run slowly. Here's a video I made a while ago to show off a 2D dynamic AABB tree:

The way the dynamic AABB tree works is by testing all of its AABBs in every leaf against itself. This will result in checking triangle AABBs against triangle AABBs. In the end these triangle to triangle pairs are just thrown away by the physics engine since these triangles are static world geometry that never moves.

One solution is to place meshes (which are composed of triangles) into their own trees. Each mesh builds its own simple AABB tree (not a dynamic one), and this tree is placed into the dynamic AABB tree. This way the dynamic tree has way less stuff inside of it and thusly is more resistant to static geometry pollution. This is the solution I'm currently finishing up.

So I'm making a tree of trees.

Alternative solutions might be to maintain the dynamic tree for moving objects, and have another dynamic tree strictly for the level geometry. Then a tree to tree query can be written, and throw-away triangle to triangle pairs can be avoided altogether.

Additionally, the triangle meshes used for rendering are often really highly tessellated so they look nice on screen. Tessellation actually degrades the quality of physical simulation. Some kind of mesh simplification algorithm could be used as a pre-processing step on graphical meshes in order to produce smaller and simpler collision meshes. I don't plan to implement this kind of feature since Dischord is low-poly in style, but it is definitely an important feature for other games. For example, in Diablo III meshes are simplified before collision geometry is produced.

One solution is to place meshes (which are composed of triangles) into their own trees. Each mesh builds its own simple AABB tree (not a dynamic one), and this tree is placed into the dynamic AABB tree. This way the dynamic tree has way less stuff inside of it and thusly is more resistant to static geometry pollution. This is the solution I'm currently finishing up.

So I'm making a tree of trees.

Alternative solutions might be to maintain the dynamic tree for moving objects, and have another dynamic tree strictly for the level geometry. Then a tree to tree query can be written, and throw-away triangle to triangle pairs can be avoided altogether.

Additionally, the triangle meshes used for rendering are often really highly tessellated so they look nice on screen. Tessellation actually degrades the quality of physical simulation. Some kind of mesh simplification algorithm could be used as a pre-processing step on graphical meshes in order to produce smaller and simpler collision meshes. I don't plan to implement this kind of feature since Dischord is low-poly in style, but it is definitely an important feature for other games. For example, in Diablo III meshes are simplified before collision geometry is produced.