DOOM specs author's document "Explaining the NODES" 3/11/94
JoeMcD1066
It attempts to explain how one can algorithmically construct the
NODES resouce used in DOOM.
Explaining the nodes
--------------------
Thanks to:
Alistair (A.D....@bradford.ac.uk),
Jeff Bird (JE...@wench.ece.jcu.edu.au),
and the comp.graphics.algorithms messages of
Tom Nettleship (ma...@midge.bath.ac.uk)
for helping me to understand the nodes.
I am certainly no expert on binary space partitioning, since everything I
know has been learned from correspondents and from reading messages
in the newsgroups. But I think I have achieved an understanding of the
nodes, and so I will try to explain it. It is a complex subject, so I'm
leaving some assumptions out, and maybe I'm explaining some too much.
Below is a crude attempt at drawing a portion of e2m9, the very westernmost
part, and how it is divided up in the node structure. I have simplified
the shape, but the way I've drawn it retains the main features which
I'm trying to elucidate. I originally did this drawing at 50x80,
but then remembered that most people use 25x80, so at character
resolutions other than 25x80 it might not look right.
| and --- and \ and / represent linedefs, EXCEPT that right next to a
number they indicate which direction that node's partition line is going.
The ... represents imaginary lines, extending from linedefs used as
partition lines, that divide up the 2d space into smaller, eventually
convex, polygons.
A node's partition line starts at the corner nearest to the number, and
goes in the direction indicated (37- means it goes east, 39/ northeast).
In the tree diagram, the numbers are nodes, the "s39" numbers are ssectors.
|-------------|50
| | | top of node tree
| -36 | \
|----\ . . . .. 50
37- \ . / \
_______35\ \..... 49etc 41
| \ 34- / . . / \
| \------/ . . 40 37
| . . . / \ / \
| . . . 39 s40 36 35
| . . / \ / \ / \
| /41 . . . 38 s41 s39 s38 s34 35
| /------\ .. / \ / \
|-------/ \ \ . . s43 s42 s37 s36
38 / .
40- / .
|----/ . . . .
| 39/ |
| |
|-------------|
So, coming from the TOP of the node tree structure down, we arrive at
node 50. Extending the line downwards, then the child on the right side
of node 50 is what's in the drawing. We'll not worry about the left child
now (node 49 and its sub-tree). In actuality, we ALWAYS traverse the left
side first, but we'll assume we've already done that side.
Pick 41 to divide the space. Then even though 41 goes southwest, the dotted
lines extending from it to the northeast are used to "cut" the space. Since
the extension of 41 to the NE hits the previous extension of 50 to the S,
that's it (no linedef cuts are necessary).
Now move to the left child of 41. Pick 40. This time, the child on the right
turns out to be convex, but first we have to continue doing the left parts,
to get the numbering right. Pick 39. Once again, another convex polygon
on the right side of 39, but the left is not. Pick 38. Now, finally, both
sides of 38 are convex. They each become ssectors. The one on the left
becomes ssector 43, and on the right, ssector 42. Actually, when working
down the tree, creating it, we don't know how many ssectors we'll end up
with, so we probably start at node 0 at the TOP of the tree, INCREASING
our index numbers for nodes and ssectors, and when we're all done, then we
reverse the numbers.
The left side of 38 is a small triangle, only one of whose sides is a
linedef. So a seg is defined, equal to the linedef, and the ssector that will
become #43 has just that one seg. And the bounding box for node 38's left
side will have the y upper and lower bounds equal, since the only seg in
the ssector is a horizontal line. Now the right side of 38 is also convex,
but it is four-sided, and only PART of one of the sides of the polygon is
a linedef. This is fine. Once again, we'll have a ssector with only a single
seg, but this time, the bounding box will actually be a box since the seg
is diagonal.
The only parts of the convex polygons that matter for these purposes are
those parts that coincide with linedefs. Thus if somehow the extensions
of the partition lines create a polygon whose sides are ALL these extension
lines, that polygon would have no part in the tree. It would have no segs,
it would not be a ssector, etc.
Anyway, since we bottomed out at ssectors, we work back up the tree, and
move to the right. If the right child needed further subdivision, then
we would move to its LEFT child first, down, down, back up, do the right
side, etc.
Now, one thing which isn't in this drawing but is very important, is the
linedefs with two sides. There will always be at least two segs for each
of these lines (if the line is split once, that's four segs; two splits,
six segs, etc). When a two-sided linedef is itself a partition line, or lies
ALONG the extension of a partition line, it has its right side in the
right child of the node, and its left side in the left child. The two segs
that represent the same portion of a two-sided linedef will have opposite
directions, that's what the 0 or 1 for direction in a seg is for. And they
will of course end up being in different ssectors.
So how do we pick which lines will be used as partition lines? From studying
the maps, it appears that they usually choose a linedef which divides the
child's space roughly in "half". This is restricted by the availability of
a linedef in a good location, with a good angle (approximately perpendicular
to the parent node's partition line). Also, the "half" might refer to the
total number of ssectors that we'll end up with, which we have no way of
knowing when we start! Optimization methods are probably used, maybe trying
several choices in succession (and recursed, it could take a LONG time...)
From my admittedly very weak understanding of what I've learned from reading
the newsgroups discussions on BSP tress, they are apparently two goals when
creating the tree, which are partially exclusive. One is to have a balanced
tree, i.e. for any node, there are about the same total number of
sub-nodes on either side of it. The other goal is to minimize the number
of "splits" necessary, in this case, the number of linedef splits needed,
along with the accompanying new vertexes and extra segs. Only a very
primitive and specially constructed set of linedefs could avoid having any
splits, so they are inevitable. It's just that with some choices of
partition lines, there end up being fewer. For example,
|-----------| If a and b are chosen as partition lines, there will be
| | four extra vertices needed, and this shape becomes
|---| |---| <-A five ssectors. If A and B are chosen, however, there
|a b| are no extra vertices, and only three ssectors.
|---| |---| <-B
| |
|-----------|
So anyway, I've read that for a "small" number of polygons (less < 1000?),
which is what we're dealing with in a doom level, probably, one should
definately try to minimize splits, and not worry about balancing the tree.
I can't say for sure, but it does appear that the original levels strive
for this. Their trees are not totally unbalanced, but there are some parts
where many succesive nodes each have a node and a ssector as children (this
is unbalanced). I think the algorithm that id software used tried to
optimize both, but with fewer splits being more important.
Now, as to an algorithm to generate the nodes. I am pretty sure that this
would work: I pick the partition lines (always going left first, remember),
and the algorithm does all the line-extending, intersection calculating,
creating segs and ssectors (all with temporary index numbers, to be inverted
when all is complete). What I have a tough time picturing is the algorithm
picking the partition lines, unless it does it by brute force, trying every
one in succesion. Like I mentioned previously, I think this could take
forever. Maybe it could approximately divide the area of a child in half,
and find the linedef which is closest, and just go from there, and not worry
about either tree balance OR splits. Regardless, I think this might be a
good approach. Sufficiently inspired programmers, please try!
And of course, if you know more, or have a better idea of what's going on,
please correct me with a message!
------ ------ ------
Matt Fell
Unofficial DOOM Specs Author (DMSPEC12.TXT - 1.3 will have the nodes solved!)
Internet: matt.b...@acebbs.com