↓bottom↓   ↓Menu↓   ↑top↑

» DooM - xFAQ «

---

 

The Resources for the Binary Space Partition

by Matthew S. Fell

 

---

 SEGS

↓bottom↓   ↑Menu↑   ↑top↑

 

Each SEG represents a segment of a line. Its record has 12 bytes in 6 short fields:

The structure of a single SEG
Offset	Size	Purpose
0	short	Starting VERTEX of thisSEG.
2	short	End VERTEX.
4	short	Angle: 0=east, 16384=north, -16384=south, -32768=west. In hex, 0000=east, 4000=north, 8000=west, c000=south. This is also know as BAMS for Binary Angle Measurement.
6	short	LINEDEF that thisSEG goes along.
8	short	Direction: 0 if the SEG goes the same direction as the LINEDEF it is on, 1 if the SEG goes the opposite direction. This is the same as 0 if the SEG is on the right side of the LINEDEF or 1 if the SEG is on its left side .
10	short	Offset: distance along the LINEDEF to the start of this SEG (the VERTEX in field 1). The offset is in the same direction as the SEG. If field 5 is 0, then the distance is from the Start VERTEX of the LINEDEF to the Starting VERTEX of the SEG. If field 5 is 1, then the offset is from the end VERTEX of the LINEDEF to the Starting VERTEX of the SEG. So if the SEGbegins at one of the two endpoints of the LINEDEF, this offset will be 0. [More details]

Calculating non-orthoganol offsets

For diagonal SEGs, the offset distance can be obtained from the formula DISTANCE = SQR((x2 - x1)^2 + (y2 - y1)^2). The angle can be calculated from the inverse tangent of the dx and dy in the VERTEXES, multiplied to convert PI/2 radians (90 degrees) to 16384. And since most arctan functions return a value between -(PI/2) and (PI/2), you'll have to do some tweaking based on the sign of (x2-x1), to account for SEGs that go "west". Fun, eh?

SEG order

The SEGs are stored in a sequential order determined by the SSECTORS, which are part of the NODES recursive tree.

 

---

 SSECTORS

↓bottom↓   ↑Menu↑   ↑top↑

 

SSECTOR stands for sub-sector. These divide up all the SECTORS into convex polygons. They are then referenced through the NODES resources. There will be (number of NODES + 1) SSECTORS.

Each SSECTOR is 4 bytes in 2 fields:

The structure of a single SSECTOR
Offset	Size	Purpose
0	short	Total number of SEGS in this SSECTOR....
0	short	... starting with this SEG number..

The SEGs in SSECTOR 0 should be SEGs 0 through x, then SSECTOR 1 contains SEGs x+1 through y, SSECTOR 2 containing SEGs y+1 to z, etc.

 

---

 NODES

↓bottom↓   ↑Menu↑   ↑top↑

 

The NODES resource contains the division of the map into a Binary Space Partition. This is a tree-like structure, explained in detail shortly.

NODES structure

Each individual NODE is 28 bytes in 14 short fields:

The structure of a single NODE in the Binary Space Partition
Offset	Size	Purpose	Comments
0	short	X-coordinate of partition line's start.	If fields (1) to (4) equaled 64, 128, -64, -64, respectively, the partition line would go from (64,128) to (0,64).
2	short	Y-coordinate of partition line's start.
4	short	DX, change in X to end of partition line
6	short	DY, change in Y to end of partition line
8	short	Y upper bound for right bounding-box.	All SEGS in the right child of this NODE must be within this box.
10	short	Y lower bound
12	short	X lower bound
14	short	X upper bound
16	short	Y upper bound for left bounding-box.	All SEGS in the left child of this NODE must be within this box.
18	short	Y lower bound
20	short	X lower bound
22	short	X upper bound
24	short	a NODE or SSECTOR number for the right child.	In these fields, if bit 15 is set, then the rest of the number represents the child SSECTOR, otherwise the appropriate child is a recursed NODE.
26	short	a NODE or SSECTOR number for the left child.

 

---

 The operation of a Binary Space Partition

↓bottom↓   ↑Menu↑   ↑top↑

 

The NODES lump is by far the most difficult to understand of all the data structures in DOOM. A new level won't display right without a valid set of precalculated NODES, SSECTORS, and SEGS.

Here I will explain what the NODES are for, and how they can be generated automatically from the set of LINEDEFS, SIDEDEFS, and VERTEXES. Not included here is any code or a pseudo-code algorithm. This is for reasons of space, and more importantly, the fact that I haven't written any such algorithm myself. If there's to be some "node code" published here, it will have to be donated by someone, well-commented, well-organized, in pseudo-code, and 100% effective! So the odds are long against it.

The Binary Space Partition

The NODES are branches in a binary space partition (BSP) that divides up the level and is used to determine which walls are in front of others, a process know as hidden-surface removal. The SSECTORS (sub-sectors) and SEGS (segments) lumps are necessary parts of the structure.

A BSP tree is normally used in 3-D space, but DOOM uses a simplified 2-D version of the scheme. Basically, the idea is to keep dividing the map into smaller spaces until each of the smallest spaces contains only wall segments which cannot possibly occlude (block from view) other walls in its own space. The smallest, undivided spaces will become SSECTORS. Each wall segment is part or all of a LINEDEF (and thus a straight line), and becomes a SEG. All of the divisions are kept track of in a binary tree structure, which is used to greatly speed the rendering process (drawing what is seen). How does this binary tree lead to faster rendering? I have no idea!

It is only the SECTORS that need to be divided. The parts of the levels that are "outside" sectors can be ignored, as they will never need to be displayed. Also, only the walls need to be kept track of. The sides of any created SSECTORS which are not parts of LINEDEFS do not become SEGS, again because there is nothing to render along their length.

Arranging the division

Some sectors do not require any dividing. Consider a square sector. All the walls are orthogonal to the floor (the walls are all straight up and down), so from any viewpoint inside the square, none of its four walls can possibly block the view of any of the others.

Consider, however, a sector shaped like this:

  +----------------.----+   The * is the viewpoint, looking ->, east. The
  |                 .   |   diagonal wall marked @ @ can't be seen at all,
  |                 /\  |@  and the vertical wall marked @@@ is partially
  |  *->           / @\ |@  occluded by the other diagonal wall. This sector
  |               /   @\|@  needs to be divided. Suppose the diagonal wall
  +--------------/          is extended, as shown by the two dots (..):
  

Now each of the two resulting sub-sectors are sufficient, because while the player is in either one, no wall that is part of that sub-sector blocks any other.

In general, being a convex polygon is the goal of a ssector. Convex means a line connecting any two points that are inside the polygon will be completely contained in the polygon. All triangles and rectangles are convex, but not all quadrilaterals. In DOOM's simple Euclidean space, convex also means that all the interior angles of the polygon are less than or equal to 180 degrees.

An additional complication arises because of the two-sided LINEDEF. Its two sides are in different sectors, so they will end up in different SSECTORS too. Thus every two-sided LINEDEF becomes two SEGS (or more). Or you could say that every SIDEDEF becomes a SEG. Creating SEGS from SIDEDEFS is a good idea, because the SEG can then be associated with a sector. Two SEGS that aren't part of the same sector cannot possibly be in the same SSECTOR, so further division will be required of any set of SEGS that aren't all from the same sector.

Carving up the map

Whenever a division needs to be made, a SEG is picked, somewhat arbitrarily, which along with its imaginary extensions, forms a "knife" that divides the remaining space in two (thus binary). This SEG is the partition line of a NODE: the remaining spaces on either side of the partition line becoming the right and left children of the NODE. All partition lines have a direction (see the LINEDEFs page for an explanation of line handedness), and the space on the right side of the partition is termed the right child of the NODE. The space on the left is the left child. Note that if there does not exist a SEG in the remaining space which can serve as a partition line, then there is no need for a further partition. This space simply becomes a SSECTOR and a "leaf" on the NODES tree.

If the "knife" passes through any lines/SEGS other than at VERTEXES, they are split at the intersection, with one part going to each child. A two-sided LINEDEF, which is already two SEGS remember, when split will result in four SEGS. A two-sider that lies along an extension of the partition line has each of its two SEGS go to opposite sides of the partition line. This is the eventual fate of all SEGS on two-sided LINEDEFS.

Building the tree

As the partition lines are picked and the NODES created, a strict ordering must be maintained. The NODES tree is created from the "top" down: after the first division is made, the left child is divided, then its left child, and so on, until finally a left child is a SSECTOR. Then you move back up the tree one branch to divide the previously determined right child, proceding with its left, etc. Remember: always the left child first, on the way down, process the right child on the way back up.

Since there will be splits along the way, there is no way to know ahead of time how many NODES and SSECTORS there will be by the end. The NODE that is created first is given the highest number: this will be the top of the tree. As NODES and SSECTORS are created, they are simply numbered in order from 0 on up, and when it's all done (with nothing left but SSECTORS), then all of the numbers, for NODES and SSECTORS, are reversed. If there are 485 NODES, say, then 485 becomes 0 and 0 becomes 485, etc.

Here is another fabulous drawing which will explain everything.

+ is a VERTEX, - and | indicate LINEDEFS, with ... indicates an extension of a partition line. The <, >, and ^ symbols indicate the directions of partition lines. All the space within the drawing is actual level space, i.e. sectors.

  
        +-----+-------+-------+            0                     (5)
        |     |       |       |         /     \      ==>       /     \
        |  e  |^  f   |^  g   |       1         4           (4)       (1)
        |     |4      |5      |     /   \      / \         /   \      / \
  +---- + . . +-------+-------+    2     3    e   5      (3)   (2)   2  (0)
  |     |           < 0       |   / \   / \      / \     / \   / \      / \
  |  a  |       b             |  a   b c   d    f   g   6   5 4   3    1   0
  |     |^                    |
  | . . |2. . . . . +---------+ The order in which      How the elements are
  |     |           |1 >        the node tree's         numbered when it's
  |  c  |^    d     |           elements get made.      finished.
  |     |3          |           0 = node                (5) = node
  +-----+-----------+           a = ssector             6 = ssector
  
  

1. Make SEGS from all the LINEDEFS. There are 5 two-sided lines here.
2. Pick the VERTEX at 0 and go west (left). This is the first partition line. Note the ... extension line.
3. Pick the VERTEX at 1, going east. The backwards extension ... cuts the line 3>2>, and the unlabelled left edge line. The left edge was one SEG, which becomes two. The 3>2> line was two SEGS, it becomes four. New vertices are created at the intersection points to do this.
4. Pick the (newly created) VERTEX at 2. Now the remaining spaces on both sides of the partition line are suitable for SSECTORS. The left one is first, it becomes a, the right b. Note that SSECTOR a has 3 SEGS, and SSECTOR b has 5 SEGS. The ... imaginary lines are not SEGS.
5. Back up the tree, and take 1's right branch. Pick 3. Once again, we can make 2 SSECTORS, c and d, 3 SEGS each. Back up the tree to 0.
6. Pick 4. Now the left side is a SSECTOR, it becomes e. But the right side is not, it needs one more NODE. Pick 5, make f and g.
7. All done, so reverse all the ordination of the NODES and the SSECTORS. SSECTOR 0's SEGS become SEGS 0-2, SSECTOR 1's SEGS become SEGS 3-7, etc. The SEGS are written sequentially according to the SSECTOR numbering.

Optimising NODES building

If we want to create an algorithm to build the NODES tree automatically, it needs to be able to pick partition lines automatically. From studying the original maps, it appears that they usually chose a LINEDEF which divides the child's space roughly in "half". This is restricted by the availability of there being a SEG in a good location, with a good angle. Also, the "half" refers to the total number of ssectors in any particular child, which we have no way of knowing when we start! Optimization methods are probably used, or maybe brute force, trying every candidate SEG until the "best" one is found.

What is the best possible choice for a partition line? Well, there are apparently two goals when creating a BSP 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 SEG 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 splits. For example:

  +--------------+       If a and b are chosen as partition lines,
  |              |       there will be four extra VERTEXES needed,
  +---+      +---+ < A   and this shape becomes five SSECTORS and
      |^    ^|           16 SEGS. If A and B are chosen, however,
  +---+a    b+---+ < B   there are no extra VERTEXES, and only three
  |              |       SSECTORS and 12 SEGS.
  +--------------+       
  

I've read that for a "small" number of polygons (less than 1000?), which is what we're dealing with in a DOOM level, one should definitely 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 successive NODES each have a NODE and a SSECTOR as children (this is unbalanced). And there are a lot of examples to prove that the number of extra SEGS and VERTEXES they create is very low compared to what it could be. I think the algorithm that id Software used tried to optimize both, but with fewer splits being more important.

 

---

	↑ Menu ↑			HTML-Version new styled on Nov 2008 by Dieter Heinrich	↑ top ↑