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
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 :-)
If you like this post, you may also like one of my other posts:
- Raymarching distance fields
- Tokyo – breakdown of a webgl fragment shader
- JS1k post-mortem Minecraft
- Rendering distance fields using the Go-language
- Marker Detection for Augmented Reality Applications