I think that I’ve figured out how the .cm files in Doom III are used for collision detection.

In the .cm files the nodes discribing a tree are saved in the following format:

( 0 320 )
( 1 -1351.9996337891 )

If you interpret the first number of each node as an index for the plane normal (with 0 the x-vector, 1 the y-vector and 2 the z-vector) and the second number (float) as the distance to the plane, you can construct a plane splitting the node in two child nodes.

The node is a leaf if the first number equals -1.

Building a kD-tree using this algorithm gives you the possibility to do very fast ‘is-the-point-in-front-of-plane-checks’, because the equation

plane.normal * point + plane.distance > 0 

simply becomes:

point[ node.index ] > -node.distance.


In this demo I’ve implemented this kD-tree. When the demo is started, all brushes (which are also defined in the .cm file) are inserted into the tree.

For the collision detection you simply walk recursively through the tree to find the brushes you could collide with.

I have to say again: I am not sure this is the real meaning of these ‘two number’ nodes, but hey, it works :-)

Download zip. Full source code is included.

kD-tree collision detection