Doom3world

since doom1, id software has relied on bsp trees to increase the performce of its engines. bsp trees are very useful in both rendering and collision detection. the doom3 engine stores the rendering bsp tree in the .proc file and the collision bsp tree in the .cm file. oh yeah, the collision bsp can also be used for creating ai pathfinding systems (also known as the area awareness system in doom3).

hmmm, sounds like this might be helpful with creating ai for qw:et.

so what's collision detection exactly? without a collision detection system, the player would be able to walk right through every wall in the map. if you want to experience a game without a collision system, simply enable noclip in doom3. such a system will calculate whether or not the player (among other objects) makes contact with solid surfaces. if the player does the system will then prevent the player from passing through. duh!

simple enough, right? well, imagine a map with 4,000 brushes or roughly 24,000 brush faces. looping through all 24,000 faces in each frame to determine whenter or not the player is in contact with one of them is not very efficient. this is where the bsp tree comes in. in short, instead of looping through all 24,000 faces, a bsp tree allows us to elimate huge chunks of brushes almost instantly. with just a few calculations, a properly configured bsp tree can narrow down the 24,000 brush faces to just a handful! quite an improvement i'd say.

for much more on bsp's, check out this nice tutorial:
http://www.oracledbaexpert.com/BSPTrees ... Trees.html

now on to the .cm file...


CM "3"

3430155526

collisionModel "worldMap" 8 {
vertices { /* numVertices = */ 44
/* 0 */ ( 96 192 0 )
/* 1 */ ( 96 64 0 )
/* 2 */ ( 96 64 256 )
/* 3 */ ( 96 192 256 )
/* 4 */ ( 128 64 0 )
/* 5 */ ( 128 64 256 )
/* 6 */ ( 128 160 0 )
/* 7 */ ( 128 160 256 )
/* 8 */ ( 256 160 0 )
/* 9 */ ( 256 160 256 )
/* 10 */ ( 256 192 0 )
/* 11 */ ( 256 192 256 )
/* 12 */ ( -32 0 0 )
/* 13 */ ( -32 0 256 )
/* 14 */ ( -32 256 256 )
/* 15 */ ( -32 256 0 )
/* 16 */ ( 0 256 0 )
/* 17 */ ( 0 256 256 )
/* 18 */ ( 0 0 256 )
/* 19 */ ( 0 0 0 )
/* 20 */ ( 256 0 0 )
/* 21 */ ( 256 0 256 )
/* 22 */ ( 256 256 256 )
/* 23 */ ( 256 256 0 )
/* 24 */ ( 288 256 0 )
/* 25 */ ( 288 256 256 )
/* 26 */ ( 288 0 256 )
/* 27 */ ( 288 0 0 )
/* 28 */ ( 0 -32 0 )
/* 29 */ ( 256 -32 0 )
/* 30 */ ( 256 -32 256 )
/* 31 */ ( 0 -32 256 )
/* 32 */ ( 0 288 256 )
/* 33 */ ( 256 288 256 )
/* 34 */ ( 256 288 0 )
/* 35 */ ( 0 288 0 )
/* 36 */ ( 0 0 288 )
/* 37 */ ( 256 0 288 )
/* 38 */ ( 256 256 288 )
/* 39 */ ( 0 256 288 )
/* 40 */ ( 256 0 -32 )
/* 41 */ ( 0 0 -32 )
/* 42 */ ( 0 256 -32 )
/* 43 */ ( 256 256 -32 )
}
edges { /* numEdges = */ 89
/* 0 */ ( 0 0 ) 0 0
/* 1 */ ( 0 1 ) 1 1
/* 2 */ ( 1 2 ) 0 2
/* 3 */ ( 2 3 ) 1 1
/* 4 */ ( 3 0 ) 0 2
/* 5 */ ( 1 4 ) 1 1
/* 6 */ ( 4 5 ) 0 2
/* 7 */ ( 5 2 ) 1 1
/* 8 */ ( 4 6 ) 1 1
/* 9 */ ( 6 7 ) 1 2
/* 10 */ ( 7 5 ) 1 1
/* 11 */ ( 6 8 ) 1 1
/* 12 */ ( 8 9 ) 1 1
/* 13 */ ( 9 7 ) 1 1
/* 14 */ ( 11 10 ) 1 1
/* 15 */ ( 12 13 ) 0 2
/* 16 */ ( 13 14 ) 0 2
/* 17 */ ( 14 15 ) 0 2
/* 18 */ ( 15 12 ) 0 2
/* 19 */ ( 16 17 ) 1 2
/* 20 */ ( 17 18 ) 1 2
/* 21 */ ( 18 19 ) 1 2
/* 22 */ ( 19 16 ) 1 2
/* 23 */ ( 14 17 ) 0 2
/* 24 */ ( 16 15 ) 0 2
/* 25 */ ( 13 18 ) 0 2
/* 26 */ ( 12 19 ) 0 2
/* 27 */ ( 20 21 ) 1 2
/* 28 */ ( 21 22 ) 1 2
/* 29 */ ( 22 23 ) 1 2
/* 30 */ ( 23 20 ) 1 2
/* 31 */ ( 24 25 ) 0 2
/* 32 */ ( 25 26 ) 0 2
/* 33 */ ( 26 27 ) 0 2
/* 34 */ ( 27 24 ) 0 2
/* 35 */ ( 22 25 ) 0 2
/* 36 */ ( 24 23 ) 0 2
/* 37 */ ( 21 26 ) 0 2
/* 38 */ ( 20 27 ) 0 2
/* 39 */ ( 28 29 ) 0 2
/* 40 */ ( 29 30 ) 0 2
/* 41 */ ( 30 31 ) 0 2
/* 42 */ ( 31 28 ) 0 2
/* 43 */ ( 18 21 ) 1 2
/* 44 */ ( 21 20 ) 1 2
/* 45 */ ( 20 19 ) 1 2
/* 46 */ ( 19 18 ) 1 2
/* 47 */ ( 18 31 ) 0 2
/* 48 */ ( 30 21 ) 0 2
/* 49 */ ( 29 20 ) 0 2
/* 50 */ ( 28 19 ) 0 2
/* 51 */ ( 16 23 ) 1 2
/* 52 */ ( 23 22 ) 1 2
/* 53 */ ( 22 17 ) 1 2
/* 54 */ ( 17 16 ) 1 2
/* 55 */ ( 32 33 ) 0 2
/* 56 */ ( 33 34 ) 0 2
/* 57 */ ( 34 35 ) 0 2
/* 58 */ ( 35 32 ) 0 2
/* 59 */ ( 32 17 ) 0 2
/* 60 */ ( 22 33 ) 0 2
/* 61 */ ( 23 34 ) 0 2
/* 62 */ ( 16 35 ) 0 2
/* 63 */ ( 21 18 ) 1 2
/* 64 */ ( 18 17 ) 1 2
/* 65 */ ( 17 22 ) 1 2
/* 66 */ ( 22 21 ) 1 2
/* 67 */ ( 36 37 ) 0 2
/* 68 */ ( 37 38 ) 0 2
/* 69 */ ( 38 39 ) 0 2
/* 70 */ ( 39 36 ) 0 2
/* 71 */ ( 21 37 ) 0 2
/* 72 */ ( 36 18 ) 0 2
/* 73 */ ( 22 38 ) 0 2
/* 74 */ ( 17 39 ) 0 2
/* 75 */ ( 40 41 ) 0 2
/* 76 */ ( 41 42 ) 0 2
/* 77 */ ( 42 43 ) 0 2
/* 78 */ ( 43 40 ) 0 2
/* 79 */ ( 19 20 ) 1 2
/* 80 */ ( 20 23 ) 1 2
/* 81 */ ( 23 16 ) 1 2
/* 82 */ ( 16 19 ) 1 2
/* 83 */ ( 40 20 ) 0 2
/* 84 */ ( 19 41 ) 0 2
/* 85 */ ( 43 23 ) 0 2
/* 86 */ ( 42 16 ) 0 2
/* 87 */ ( 3 11 ) 1 1
/* 88 */ ( 10 0 ) 1 1
}
nodes {
( 0 128 )
( 1 160 )
( -1 0 )
( -1 0 )
( 1 64 )
( 1 192 )
( -1 0 )
( -1 0 )
( -1 0 )
}
polygons /* numPolygons = */ 41 /* numPolygonEdges = */ 164 {
4 ( 79 80 81 82 ) ( 0 0 1 ) 0 ( 0 0 0 ) ( 256 256 0 ) "textures/common_floors/c_4floor_1" ( 0 0 ) ( 2 2 ) ( 0 2 ) 7
4 ( 75 76 77 78 ) ( 0 0 -1 ) 32 ( 0 0 -32 ) ( 256 256 -32 ) "textures/common_floors/c_4floor_1" ( 0 -0 ) ( 2 -2 ) ( 0 -2 ) 7
4 ( 67 68 69 70 ) ( 0 0 1 ) 288 ( 0 0 288 ) ( 256 256 288 ) "textures/common_floors/c_4floor_1" ( 0 0 ) ( 2 2 ) ( 0 2 ) 6
4 ( 63 64 65 66 ) ( 0 0 -1 ) -256 ( 0 0 256 ) ( 256 256 256 ) "textures/common_floors/c_4floor_1" ( 0 0 ) ( 2 -2 ) ( 0 -2 ) 6
4 ( -78 85 -80 -83 ) ( 1 0 0 ) 256 ( 256 0 -32 ) ( 256 256 0 ) "textures/common_floors/c_4floor_1" ( 0 0.25 ) ( 2 0 ) ( 2 0.25 ) 7
4 ( -66 73 -68 -71 ) ( 1 0 0 ) 256 ( 256 0 256 ) ( 256 256 288 ) "textures/common_floors/c_4floor_1" ( 0 -2 ) ( 2 -2.25 ) ( 2 -2 ) 6
4 ( -30 -36 -34 -38 ) ( 0 0 -1 ) 0 ( 256 0 0 ) ( 288 256 0 ) "textures/common_floors/c_4floor_1" ( 0 -2 ) ( 2 -2.25 ) ( 2 -2 ) 3
4 ( -28 37 -32 -35 ) ( 0 0 1 ) 256 ( 256 0 256 ) ( 288 256 256 ) "textures/common_floors/c_4floor_1" ( 0 2 ) ( 2 2.25 ) ( 2 2 ) 3
4 ( 31 32 33 34 ) ( 1 0 0 ) 288 ( 288 0 0 ) ( 288 256 256 ) "textures/common_floors/c_4floor_1" ( 0 0 ) ( 2 -2 ) ( 2 0 ) 3
4 ( 27 28 29 30 ) ( -1 0 0 ) -256 ( 256 0 0 ) ( 256 256 256 ) "textures/common_floors/c_4floor_1" ( 0 0 ) ( -2 -2 ) ( -2 0 ) 3
4 ( -77 86 -81 -85 ) ( 0 1 0 ) 256 ( 0 256 -32 ) ( 256 256 0 ) "textures/common_floors/c_4floor_1" ( -0 0.25 ) ( -2 0 ) ( -2 0.25 ) 7
4 ( -65 74 -69 -73 ) ( 0 1 0 ) 256 ( 0 256 256 ) ( 256 256 288 ) "textures/common_floors/c_4floor_1" ( -0 -2 ) ( -2 -2.25 ) ( -2 -2 ) 6
4 ( -51 62 -57 -61 ) ( 0 0 -1 ) 0 ( 0 256 0 ) ( 256 288 0 ) "textures/common_floors/c_4floor_1" ( 2 0 ) ( 2.25 -2 ) ( 2 -2 ) 5
4 ( -56 -60 -52 61 ) ( 1 0 0 ) 256 ( 256 256 0 ) ( 256 288 256 ) "textures/common_floors/c_4floor_1" ( 2 0 ) ( 2.25 -2 ) ( 2 -2 ) 5
4 ( -55 59 -53 60 ) ( 0 0 1 ) 256 ( 0 256 256 ) ( 256 288 256 ) "textures/common_floors/c_4floor_1" ( 2 0 ) ( 2.25 2 ) ( 2 2 ) 5
4 ( 55 56 57 58 ) ( 0 1 0 ) 288 ( 0 288 0 ) ( 256 288 256 ) "textures/common_floors/c_4floor_1" ( -0 0 ) ( -2 -2 ) ( -2 0 ) 5
4 ( 51 52 53 54 ) ( 0 -1 0 ) -256 ( 0 256 0 ) ( 256 256 256 ) "textures/common_floors/c_4floor_1" ( -0 0 ) ( 2 -2 ) ( 2 0 ) 5
4 ( -29 35 -31 36 ) ( 0 1 0 ) 256 ( 256 256 0 ) ( 288 256 256 ) "textures/common_floors/c_4floor_1" ( -2 0 ) ( -2.25 -2 ) ( -2 -2 ) 3
4 ( 88 -4 87 14 ) ( 0 1 0 ) 192 ( 96 192 0 ) ( 256 192 256 ) "textures/common_floors/c_4floor_1" ( -1.5000001192 0 ) ( -1.7500001192 -2 ) ( -1.5000001192 -2 ) 0
4 ( 11 12 13 -9 ) ( 0 -1 0 ) -160 ( 128 160 0 ) ( 256 160 256 ) "textures/common_floors/c_4floor_1" ( 1 0 ) ( 2 -2 ) ( 1 -2 ) 1
4 ( -75 83 -79 84 ) ( 0 -1 0 ) 0 ( 0 0 -32 ) ( 256 0 0 ) "textures/common_floors/c_4floor_1" ( 0 0.25 ) ( 2 0 ) ( 2 0.25 ) 7
4 ( -63 71 -67 72 ) ( 0 -1 0 ) 0 ( 0 0 256 ) ( 256 0 288 ) "textures/common_floors/c_4floor_1" ( 0 -2 ) ( 2 -2.25 ) ( 2 -2 ) 6
4 ( -39 50 -45 -49 ) ( 0 0 -1 ) 0 ( 0 -32 0 ) ( 256 0 0 ) "textures/common_floors/c_4floor_1" ( -0.25 0 ) ( 0 -2 ) ( -0.25 -2 ) 4
4 ( -44 -48 -40 49 ) ( 1 0 0 ) 256 ( 256 -32 0 ) ( 256 0 256 ) "textures/common_floors/c_4floor_1" ( -0.25 0 ) ( 0 -2 ) ( -0.25 -2 ) 4
4 ( -43 47 -41 48 ) ( 0 0 1 ) 256 ( 0 -32 256 ) ( 256 0 256 ) "textures/common_floors/c_4floor_1" ( -0.25 0 ) ( 0 2 ) ( -0.25 2 ) 4
4 ( 43 44 45 46 ) ( 0 1 0 ) 0 ( 0 0 0 ) ( 256 0 256 ) "textures/common_floors/c_4floor_1" ( 0 0 ) ( -2 -2 ) ( -2 0 ) 4
4 ( 39 40 41 42 ) ( 0 -1 0 ) 32 ( 0 -32 0 ) ( 256 -32 256 ) "textures/common_floors/c_4floor_1" ( 0 0 ) ( 2 -2 ) ( 2 0 ) 4
4 ( -33 -37 -27 38 ) ( 0 -1 0 ) 0 ( 256 0 0 ) ( 288 0 256 ) "textures/common_floors/c_4floor_1" ( 2 0 ) ( 2.25 -2 ) ( 2 -2 ) 3
4 ( 8 9 10 -6 ) ( 1 0 0 ) 128 ( 128 64 0 ) ( 128 160 256 ) "textures/common_floors/c_4floor_1" ( -2 0 ) ( -1.2499998808 -2 ) ( -2 -2 ) 0
4 ( -76 -84 -82 -86 ) ( -1 0 0 ) 0 ( 0 0 -32 ) ( 0 256 0 ) "textures/common_floors/c_4floor_1" ( 0 0.25 ) ( -2 0 ) ( -2 0.25 ) 7
4 ( -64 -72 -70 -74 ) ( -1 0 0 ) 0 ( 0 0 256 ) ( 0 256 288 ) "textures/common_floors/c_4floor_1" ( 0 -2 ) ( -2 -2.25 ) ( -2 -2 ) 6
4 ( -18 -24 -22 -26 ) ( 0 0 -1 ) 0 ( -32 0 0 ) ( 0 256 0 ) "textures/common_floors/c_4floor_1" ( 0 0.25 ) ( 2 0 ) ( 2 0.25 ) 2
4 ( -16 25 -20 -23 ) ( 0 0 1 ) 256 ( -32 0 256 ) ( 0 256 256 ) "textures/common_floors/c_4floor_1" ( 0 -0.25 ) ( 2 0 ) ( 2 -0.25 ) 2
4 ( 19 20 21 22 ) ( 1 0 0 ) 0 ( 0 0 0 ) ( 0 256 256 ) "textures/common_floors/c_4floor_1" ( 0 0 ) ( 2 -2 ) ( 2 0 ) 2
4 ( 15 16 17 18 ) ( -1 0 0 ) 32 ( -32 0 0 ) ( -32 256 256 ) "textures/common_floors/c_4floor_1" ( -0 0 ) ( -2 -2 ) ( -2 0 ) 2
4 ( -54 -59 -58 -62 ) ( -1 0 0 ) 0 ( 0 256 0 ) ( 0 288 256 ) "textures/common_floors/c_4floor_1" ( -2 0 ) ( -2.25 -2 ) ( -2 -2 ) 5
4 ( -17 23 -19 24 ) ( 0 1 0 ) 256 ( -32 256 0 ) ( 0 256 256 ) "textures/common_floors/c_4floor_1" ( 0.25 0 ) ( -0 -2 ) ( 0.25 -2 ) 2
4 ( 5 6 7 -2 ) ( 0 -1 0 ) -64 ( 96 64 0 ) ( 128 64 256 ) "textures/common_floors/c_4floor_1" ( 1.5000001192 0 ) ( 1.7500001192 -2 ) ( 1.5000001192 -2 ) 0
4 ( 1 2 3 4 ) ( -1 0 0 ) -96 ( 96 64 0 ) ( 96 192 256 ) "textures/common_floors/c_4floor_1" ( 2 0 ) ( 0.9999998212 -2 ) ( 2 -2 ) 0
4 ( -42 -47 -46 -50 ) ( -1 0 0 ) 0 ( 0 -32 0 ) ( 0 0 256 ) "textures/common_floors/c_4floor_1" ( 0.25 0 ) ( 0 -2 ) ( 0.25 -2 ) 4
4 ( -21 -25 -15 26 ) ( 0 -1 0 ) 0 ( -32 0 0 ) ( 0 0 256 ) "textures/common_floors/c_4floor_1" ( -0.25 0 ) ( 0 -2 ) ( -0.25 -2 ) 2
}
brushes /* numBrushes = */ 8 /* numBrushPlanes = */ 48 {
6 {
( 0 0 -1 ) 32
( 0 0 1 ) 0
( 0 -1 0 ) 0
( 1 0 0 ) 256
( 0 1 0 ) 256
( -1 0 0 ) 0
} ( 0 0 -32 ) ( 256 256 0 ) "solid,opaque" 7
6 {
( 0 0 -1 ) -256
( 0 0 1 ) 288
( 0 -1 0 ) 0
( 1 0 0 ) 256
( 0 1 0 ) 256
( -1 0 0 ) 0
} ( 0 0 256 ) ( 256 256 288 ) "solid,opaque" 6
6 {
( -1 0 0 ) -256
( 1 0 0 ) 288
( 0 1 0 ) 256
( 0 0 1 ) 256
( 0 -1 0 ) 0
( 0 0 -1 ) 0
} ( 256 0 0 ) ( 288 256 256 ) "solid,opaque" 3
6 {
( 0 -1 0 ) -256
( 0 1 0 ) 288
( 0 0 1 ) 256
( 1 0 0 ) 256
( 0 0 -1 ) 0
( -1 0 0 ) 0
} ( 0 256 0 ) ( 256 288 256 ) "solid,opaque" 5
6 {
( 0 0 -1 ) 0
( 0 0 1 ) 256
( 0 -1 0 ) -160
( 1 0 0 ) 256
( 0 1 0 ) 192
( -1 0 0 ) -128
} ( 128 160 0 ) ( 256 192 256 ) "solid,opaque" 1
6 {
( 0 -1 0 ) 32
( 0 1 0 ) 0
( 0 0 1 ) 256
( 1 0 0 ) 256
( 0 0 -1 ) 0
( -1 0 0 ) 0
} ( 0 -32 0 ) ( 256 0 256 ) "solid,opaque" 4
6 {
( -1 0 0 ) 32
( 1 0 0 ) 0
( 0 1 0 ) 256
( 0 0 1 ) 256
( 0 -1 0 ) 0
( 0 0 -1 ) 0
} ( -32 0 0 ) ( 0 256 256 ) "solid,opaque" 2
6 {
( 0 0 -1 ) 0
( 0 0 1 ) 256
( -1 0 0 ) -96
( 0 -1 0 ) -64
( 1 0 0 ) 128
( 0 1 0 ) 192
} ( 96 64 0 ) ( 128 192 256 ) "solid,opaque" 0
}
}


by the way, this is the map i'm using. the center walls go from floor to ceiling- this simplifies the bsp tree to "2D" rather than "3D".


the first group in the .cm file lists the coordinates of all the verts. the second group lists the edges (defined as two verts from the previous group). the third group lists the nodes of the bsp tree. the fourth group lists all of the brush planes and the last lists the individual brushes. for now, forget everything but the node list.

nodes {
( 0 128 )
( 1 160 )
( -1 0 )
( -1 0 )
( 1 64 )
( 1 192 )
( -1 0 )
( -1 0 )
( -1 0 )
}

a node is plane in one of the three axis. the format here is (AXIS LOCATION) and 0 = X, 1 = Y and 2 = Z. so a (0 128) node would be a plane that splits the map at x = 128. (-1 0) means that there are no more child nodes below the parent node (more on that later).

now lets build (or rather reconstruct) the bsp tree shall we!
..............................
.........(0 128)..........
......../.........\..........
.......f...........b.........
.............................



the red line is first node plane. we are looking from above so it looks like a line but its a plane, trust me. the little red line defines the plane's front. now lets move on to the second node.

.........(0 128)..........
......../..........\.........
.......f............b........
(1 160)...................
.............................


this next node plane is Y = 160 and its only drawn on the front side of the first node. notice the shape of the tree we are reconstructing, front = left and back = right. now we continue along the front to the thrid node on the list.

.....................................
..............(0 128)............
............../........\............
.............f...........b..........
.......(1 160)...................
....../..........\.................
.....f.............b...............
( -1 0 )..........................
....................................

here we have hit the first (-1 0) entry in the node list. this tells us that there are no more nodes that can split this area further. once we hit the first (-1 0) entry, we begin to go up the backside of the tree one node at a time like this:

...................................................
.......................(0 128)..................
....................../..........\.................
.....................f.............b..............
............(1 160)............(1 64)........
............/........\.............................
..........f............b...........................
( -1 0 )..........( -1 0 ).....................
...................................................

notice how the node plane (1 64) is on the back side of the first node.


once we can not go any further up the backside, we start down the next front side again like this:

....................................................
....................(0 128)......................
..................../.........\.....................
...................f............b...................
..........(1 160)...........(1 64).............
........../........\.........../.......\............
........f...........b.........f.........b..........
(-1 0)........(-1 0)...(1 192)...............
.....................................................



and finally adding the last few entries in the node list like this:

.............................................................
.....................(0 128).............................
..................../..........\............................
...................f.............b..........................
..........(1 160).............(1 64)..................
........./.........\............./.......\.................
........f...........b...........f.........b...............
(-1 0).......(-1 0)....(1 192).....(-1 0).........
.........................../.........\......................
..........................f............b....................
.....................(-1 0).........(-1 0)..............
............................................................

phew!! i hope those trees turn out right when i hit the submit button

there, now you know how to reconstruct id's collision bsp tree. let take a walk thtough it shall we? pick any point in the map like (32, 224, 0) which happens to be the player's start position. its very easy and fast to calc which side of the first node plane this point is on. in this case its the front. so follow the tree to the next front node plane which is (1 160). now where does the player fall? on the back of this node plane. now there is no place further to go on the tree so we are done "walking" the tree.

as you can see in the pictures above, we are in the lower left rectangle formed by the nodes. the only brush faces we need to check for collision are the two closest walls- all the other brushes and walls have been elimated!! (well, there is also the floor and ceiling, but this is more or less a "2D" tree anyway).

here's another look at the node list, this time showing the node's parent and side.

nodes {
1. (0 128)
2. (1 160) 1 front
3. (-1 0) 2 front
4. (-1 0) 2 back
5. (1 64) 1 back
6. (1 192) 5 front
7. (-1 0) 6 front
8. (-1 0) 6 back
9. (-1 0) 5 back
}

the algorithim works like this (as best i can explain it):
1. start with the first node
2. place the next node to the front side of the one before it
3. continue step 2 until you place the first (-1 0), at that point you can no longer continue to the front
4. then place the next list entry to the back side right next to the (-1 0) node above
5 continue going up the backsides until you place a non (-1 0) node
7. at that point you can place the next entry on the front side again.
8. repeat until you reach the end of the node list

in other words, always go to the front side if you can. otherwise go to back side.

now for all that other stuff in the .cm file (which i might have goofed on a few)...

Vertices
/* LIST_NUM */ ( x y z )

example:
/* 0 */ ( 96 192 0 )
/* 1 */ ( 96 64 0 )
/* 2 */ ( 96 64 256 )

Edges
/* EDGE_NUM */ ( FIRST_VERT SECOND_VERT ) NOT_SURE NOT_SURE

example:
/* 1 */ ( 0 1 ) 1 1
/* 2 */ ( 1 2 ) 0 2
/* 3 */ ( 2 3 ) 1 1

if anyone knows what those last two digits are, let me know. it appears to between 0 and 2.

Nodes {
( AXIS POSITION )
where AXIS can be either 0 (yz-plane), 1 (xz-plane) or 2 (xy-plane).

example:
( 0 128 )
( 1 160 )
( -1 0 )

see above on how to reconstruct a bsp tree from this list.

Polygons (or brush faces)
NUMBER_OF_SIDES (EDGE1, EDGE2, EDGE3, EDGE4...) (PLANE_NORMAL) DISTANCE_TO_ORIGIN (MIN) (MAX) "MATERIAL_NAME" (TEXTURE_SCALE) (TEXTURE_SCALE) (TEXTURE_SCALE) BRUSH_NUMBER

example:
4 ( 79 80 81 82 ) ( 0 0 1 ) 0 ( 0 0 0 ) ( 256 256 0 ) "textures/common_floors/c_4floor_1" ( 0 0 ) ( 2 2 ) ( 0 2 ) 7

Brushes
NUMBER_OF_FACES {
(PLANE_NORMAL) DISTANCE_TO_ORIGIN
.
.
.
} (MIN) (MAX) "TYPE_OF_SOLID" BRUSH_NUMBER

where TYPE_OF_SOLID can be a combination of "solid", "opaque", "monsterclip", "aas_solid", "playerclip" or "sightClip".

example:
6 {
( 0 0 -1 ) 32
( 0 0 1 ) 0
( 0 -1 0 ) 0
( 1 0 0 ) 256
( 0 1 0 ) 256
( -1 0 0 ) 0
} ( 0 0 -32 ) ( 256 256 0 ) "solid,opaque" 7

You could make images out of it, or hope that a [ code ] block keeps the spacing.

http://www.modwiki.net/wiki/CM_%28file_format%29

The modwiki calls for you!

Sigh. Another article I will have to port over myself.

Don't look so sad, I don't think you'd be doing it if you didn't like it, just a little .

made some changes. should be pretty much complete now.

Excellent and informative. Thanks.

Excellent work. Next can you create a tool that will update the bsp in run time so we can have fully deformable terrain?

i have a guess on part the edge format (the last two digits).

Edges
/* EDGE_NUM */ ( FIRST_VERT SECOND_VERT ) NOT_SURE NOT_SURE

example:
/* 1 */ ( 0 1 ) 1 1
/* 2 */ ( 1 2 ) 0 2
/* 3 */ ( 2 3 ) 1 1

the last numbers only come in the following flavors:
- 0 1
- 1 1
- 0 2
- 1 2

and i think it goes like this:
0 1 => an edge that is not shared by another brush face. for exampe an outside edge on a patch mesh.

0 2 => an edge that is shared by two brush faces with the same material for example any edge on the surface of a single rectangle shaped brush.

1 1 => an edge that is not shared by other brush face but occupies the same space of another separate edge.

1 2 => an edge that is shared by more than one brush face from separate brushes with different materials.