I think that I have figured out how the .cm files in Doom III are used for collision detection.
In the .cm files the nodes describing 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 into 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 Code language: GLSL (glsl)simply becomes:
point[ node.index ] > -node.distance.Code language: GLSL (glsl)
In this demo, I have 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.
Similar posts
If you like this post, you may also like one of my other posts:
- Marker Detection for Augmented Reality Applications
- Rendering distance fields using the Go-language
- Doom 3 – OpenGL Shading Language
- Dynamic skydome
- Grass Experiment