# Binary Space Partitioning

Binary Space Partitioning is an algorithim that takes a set of 2D lines or 3D polygons and recursively groups them into a BSP Tree. Each node has three lists: two child nodes representing lines in front of and lines behind and a thirt list representing lines on the same plane. Once the BSP Tree is built it can be used to search which lines are facing any position in linear time.

It originally was created in 1969 during early attempts at 3D rendering but was most popularly introduced by John Carmack in the original DOOM game. In the game, a level editor was used by the DOOM team to create levels which were comprised by sectors and line data called linedefs. When publishing their level data, Binary Space Partitioning was run against the level and produced a BSP tree of LineDefs and subsplit linedefs called Segs. This BSP tree was then included in their level data for the game engine called a WAD file.

When the DOOM engine loaded the data from the level, it would use the BSP tree nodes to traverse and render the game in a reverse painters algorithm. The BSP tree allowed the game engine to only search and draw walls that were facing the player, culling large numbers of walls from the process. This was where the BSP shined allowing DOOM to run in ways other DOS games had not at the time.

A BSP tree is computationally expensive to run, which is why it was done during level creation and as such required levels be static in nature without horizontal changes in the map's layout.

## The Algorithm

* Two connected vertices define a LineDef
* A LineDef has an outward face to define which side of it is considered open and which side is solid
* A list of LineDefs form a Polygon that can define the boundaries of a room, or "sector"
* A Binary Space Partition class accepts the worlds list of LineDefs
    * The BSP chooses a best candidate "splitter" LineDef by which to judge all other LineDefs
    * The BSP creates two child BSPs to place other LineDefs behind or in front of the splitter
    * LineDefs that cross the plane of the splitter and split into smaller LineDefs to be sorted
* The BSP sorts all LineDefs recursively in the child trees
* Using the BSP we can test whether a position is in open space with a depth search
* Using the BSP we can also render all walls from either back to front or front to back
    * Doom rendered them front to back and used culling to prevent overdraw
    * Other engines have rendered back to front called the Painters Algorithm
* The BSP Tree is built before the game begins as a means of significant performance gain

### Creating 2D Rooms of Connected Lines

Using Python I will demonstrate how a BSP is built, but first we need to create some meaningful polygons to split into a BSP tree. This set of polygons will be comprised of lines with: x coord, y coord, which way it is "facing", and the height of the wakll (used only in rendering).

_NOTE:_ all math is included at the end.

```python
# Lines, each vertex connects to the next one in CW fashion
# third element is direction its facing, when CW facing 1 = left
polygons = [
    # open room
    [
        # x, y, facing, height
        [30,  30, 0, 10],
        [300, 20, 0, 10],
        [400, 300, 0, 10],
        [30, 200, 0, 10]
    ],
    # inner col
    [
        # x, y, facing
        [50,  50, 1, 5],
        [100, 50, 1, 5],
        [75,  75, 1, 5],
        [100, 100, 1, 5],
        [50,  100, 1, 5]
    ],
    # inner room
    [
        [55, 55, 0, 5],
        [70, 55, 0, 5],
        [70, 95, 0, 5],
        [55, 95, 0, 5],
    ]
]

# Line Defs built Clockwise
allLineDefs = []
for i, v in enumerate(polygons):
    polygon = polygons[i]
    lineDefs = []
    for idx, val in enumerate(polygon):
        lineDef = LineDef()

        # first point, connect to second point
        if idx == 0:
            lineDef.asRoot(polygon[idx][0], polygon[idx][1], polygon[idx + 1][0], polygon[idx + 1][1], polygon[idx + 1][2], polygon[idx + 1][3])
            lineDefs.append(lineDef)
            allLineDefs.append(lineDef)

        # some point in the middle
        elif idx < len(polygon) - 1:
            lineDef.asChild(lineDefs[-1], polygon[idx + 1][0], polygon[idx + 1][1], polygon[idx + 1][2], polygon[idx + 1][3])
            lineDefs.append(lineDef)
            allLineDefs.append(lineDef)

        # final point, final line, connects back to first point
        elif idx == len(polygon) - 1:
            lineDef.asLeaf(lineDefs[-1], lineDefs[0], polygon[idx][2], polygon[idx][3])
            lineDefs.append(lineDef)
            allLineDefs.append(lineDef)
```

These polygons contain line data which are similar to LineDefs in DOOM, and of note the have a "face" direction which indicates which side is the exposed side to the game world and should be rendered. This facilitates the concept of a wall and is important for subdividing the other lines into the BSP tree.

These polygons when glued together and rendered look like this, with a larger room in which our world is contained and within a smaller room completely enclosed within another set of walls.

The blue lines are the overall walls, the smaller lines projecting as their normal vector represent their face's direction. The Dot and Line are the camera position and angle in the 2D world.

![](/images/bsp_1_polys.png)


This algorithm converts the raw polygon data into a LineDef object that is defined as:

```python
import random
from engine.mathdef import crossProductLine
from engine.mathdef import normalize
from engine.mathdef import intersection2d
from engine.mathdef import pointBehindSegment

# A polygon is a collection of lines, each line has a direction
# All lines should be connected, meaning one should start where the last one ends

class LineDef(object):
    def __init__(self):
        self.start = []
        self.end = []
        self.facing = None
        self.mid = []
        self.normals = []
        self.drawColor = (random.randint(10, 255), random.randint(10, 255), random.randint(50, 255))
        self.height = 10
        # TODO: get normals and stuff calculated here

    def asRoot(self, startX, startY, endX, endY, facing, height):
        self.start = [startX, startY]
        self.end = [endX, endY]
        self.facing = facing
        self.height = height
        self.setup()

    def asChild(self, preLineDef, endX, endY, facing, height):
        self.start = [preLineDef.end[0], preLineDef.end[1]]
        self.end = [endX, endY]
        self.facing = facing
        self.height = height
        self.setup()

    def asLeaf(self, preLineDef, rootLineDef, facing, height):
        self.start = [preLineDef.end[0], preLineDef.end[1]]
        self.end = [rootLineDef.start[0], rootLineDef.start[1]]
        self.facing = facing
        self.height = height
        self.setup()

    def setup(self):
        self.setMidpoint()
        self.setNormals()

    def setMidpoint(self):
        # (a.x+b.x)/2,(a.y+b.y)/2
        self.mid.append((self.start[0] + self.end[0]) / 2)
        self.mid.append((self.start[1] + self.end[1]) / 2)

    def setNormals(self):
        dx = self.end[0] - self.start[0]
        dy = self.end[1] - self.start[1]
        self.normals.append(normalize(-dy, dx)) # First normal is the one facing in (if we are Clockwise)
        self.normals.append(normalize(dy, -dx)) # Second normal is the one facing out (if we are Clockwise)

    def isPointBehind(self, a, b):
        # If it is behind and we are facing left CW
        beh = pointBehindSegment([a, b], self.start, self.end) # true, false or none (for on the same plane)
        if beh != None:
            if self.facing == 1:
                return beh
            return not beh
        return None

    def classifyLine(self, testLine):
        # 1 = back
        # 2 = front
        # 3 = spanning
        # 4 = co planar
        points = [testLine.start, testLine.end]
        backCounter = 0
        frontCounter = 0
        for point in points:
            result = self.isPointBehind(point[0], point[1])
            if result == True:
                backCounter += 1
            if result == False:
                frontCounter +=1
            # if result == None:
                # co planar, no counters

        # spanning
        if backCounter != 0 and frontCounter != 0:
            return 3
        # back
        if backCounter:
            return 1
        # front
        if frontCounter:
            return 2
        return 4

    def split(self, other):
        # get the intersecting point
        intersection = self.findIntersection(other)
        if intersection:
            # create a line from other start to intersection and return that as front??
            splitA = [other.start, intersection]
            splitB = [intersection, other.end]
            aBehind = self.isPointBehind(other.start[0], other.start[1])
            # return them with position 0 behind and position 1 in front
            if aBehind:
                return [splitA, splitB]
            else:
                return [splitB, splitA]
        return None

    def findIntersection(self, other):
        return intersection2d(self.start, self.end, other.start, other.end)
```

### The BSP Tree Data Structure

Here is a BSP Tree class that does all the brutal work. Being a tree the actual class is just a sindle Node of the tree with recursive functions for traversing and building child Node lists.

```python
class SolidBSPNode(object):
    def __init__(self, lineDefs):
        self.splitter = None # LineDef
        self.front = None # Self
        self.back =  None # Self
        self.isLeaf = False
        self.isSolid = False

        if len(lineDefs) == 0: # leaf
            return

        # get splitter line
        splitterIndex = self.selectBestSplitter(lineDefs)
        self.splitter = lineDefs[splitterIndex]

        # iterate the lineDefs and figure out which side of the splitter they are on
        frontList = []
        backList = []
        for lineDef in lineDefs:
            # skip splitter self check
            if lineDef != self.splitter:
                d = self.classifyLine(self.splitter, lineDef)

                if d == 1:
                    # Behind
                    backList.append(lineDef)
                elif d == 2 or d == 4:
                    # Front or coplanar
                    frontList.append(lineDef)
                elif d == 3:
                    # Spanning
                    # first element is behind, second is in front
                    splits = self.splitLine(self.splitter, lineDef)
                    backList.append(splits[0])
                    frontList.append(splits[1])

        # all lines have been split and put into front or back list
        if len(frontList) == 0:
            # create an empty leaf node
            self.front = SolidBSPNode([])
            self.front.isLeaf = True
            self.front.isSolid = False
        else:
            # create our recursive front
            self.front = SolidBSPNode(frontList)

        if len(backList) == 0:
            # create a solid back node
            self.back = SolidBSPNode([])
            self.back.isLeaf = True
            self.back.isSolid = True
        else:
            # create our recursive back
            self.back = SolidBSPNode(backList)

    def splitLine(self, splitterLineDef, lineDef):
        # first element is behind, second is in front, use facing from parent
        splits = splitterLineDef.split(lineDef)

        splitBehind = splits[0]
        splitBehindDef = linedef.LineDef()
        splitBehindDef.asRoot(splitBehind[0][0], splitBehind[0][1], splitBehind[1][0], splitBehind[1][1], lineDef.facing,  lineDef.height)

        splitFront = splits[1]
        splitFrontDef = linedef.LineDef()
        splitFrontDef.asRoot(splitFront[0][0], splitFront[0][1], splitFront[1][0], splitFront[1][1], lineDef.facing,  lineDef.height)
        return [splitBehindDef, splitFrontDef]

    # if all points behind, we would put whole poly in back list
    # if all points ahead, we would put whole poly in front list
    # if overlap, split and put into both
    def classifyLine(self, splitterLineDef, lineDef):
        return splitterLineDef.classifyLine(lineDef)

    def selectBestSplitter(self, lineDefs):
        # compare each line to each other line
        # classify where the line falls and increment number
        best = 99999
        splitterIndex = 0
        for idxA, lineDefA, in enumerate(lineDefs):
            fronts = 0
            backs = 0
            splits = 0
            for idxB, lineDefB, in enumerate(lineDefs):
                if lineDefA != lineDefB:
                    d = self.classifyLine(lineDefA, lineDefB)
                    if d == 1: #back
                        backs += 1
                    elif d == 2 or d == 4: # front or coplanar
                        fronts += 1
                    elif d == 3: # spanning
                        splits += 1
                    # make splits more costly
                    score = abs(fronts - backs) + (splits * 8)
                    if score < best:
                        best = score
                        splitterIndex = idxA
        return splitterIndex

    def inEmpty(self, testPoint):
        # recurse the tree until we find a leaf node
        if self.isLeaf:
            return self.isSolid == False
        beh = self.splitter.isPointBehind(testPoint[0], testPoint[1])
        if beh:
            return self.back.inEmpty(testPoint)
        else:
            return self.front.inEmpty(testPoint)

    def getWallsSorted(self, posA, posB, walls, depth = 0):
        if not self.isLeaf:
            behind = self.splitter.isPointBehind(posA, posB)
            # painter's algorithm paints back to front, (front to back recursively)
            # to switch to doom algorithm (requires clipping) swap front and back orders
            if behind:
                self.front.getWallsSorted(posA, posB, walls, depth + 1)
                # walls.append(self.splitter)
                self.back.getWallsSorted(posA, posB, walls, depth + 1)
            else:
                self.back.getWallsSorted(posA, posB, walls, depth + 1)
                walls.append(self.splitter)
                self.front.getWallsSorted(posA, posB, walls, depth + 1)
```

Hopefully the code is self explanatory in regards to the algorithm itself.

Some of the more complicated elements include determining if a LineDef plane crosses another line def plane and splitting that location.

Of note as well is the concept of if a node `isSolid`. This is a flag that is set for all node children that are created. All Leaf nodes do not actually contain line lists but two primay flags: `isLeaf` and `isSolid`. The parent of a leaf node is actually the parent of two leaf nodes, one in front and one behind. We can designate all "behind" leaf nodes as `isSolid=true`.

If we test a position against the tree and we wind up at a leaf node that `isSolid` we know the position is invalid.


#### Segs

The splitting and sorting operation creates the segs, or sub segments of lines and can be seen here as different colored lines that comprise either all or portions of our previous line defs.

Can you determine which line was the "Splitter" line of this BSP tree from the segs created?

![](/images/bsp_2_segs.png)

This drawing routine is appended to our BSP class such as

```python
    def drawSegs(self, display, depth = 0):
        # draw self
        if self.isLeaf == False:

            ln = 4
            mx = self.splitter.mid[0]
            my = self.splitter.mid[1]
            nx = self.splitter.normals[self.splitter.facing][0] * ln
            ny = self.splitter.normals[self.splitter.facing][1] * ln
            if self.splitter.facing == 1:
                display.drawLine([ [mx, my] , [mx + nx, my + ny] ], (0, 255, 255), 1)
            else:
                display.drawLine([ [mx, my] , [mx + nx, my + ny] ], (255, 0, 255), 1)

            display.drawLine([self.splitter.start, self.splitter.end], self.splitter.drawColor, 1)

        if self.back:
            self.back.drawSegs(display, depth + 1)
        if self.front:
            self.front.drawSegs(display, depth + 1)
```

#### Faces

We can also visualize the faces of the lines and which ones face our chosen position by recursing and testing the position with the seg's face direction. The faded lines represent those facing away from the position.

![](/images/bsp_3_facing.png)

`posA` being the x coord and `posB` being the y coord of the camera or player

```python
    def drawFaces(self, display, posA, posB, depth = 0):
        # draw self
        if self.isLeaf == False:
            behind = self.splitter.isPointBehind(posA, posB)
            if not behind:
                display.drawLine([self.splitter.start, self.splitter.end], (255, depth * 20, 0), 1)
            else:
                display.drawLine([self.splitter.start, self.splitter.end], (60, depth * 5, 0), 1)

        if self.back:
            self.back.drawFaces(display, posA, posB, depth + 1)
        if self.front:
            self.front.drawFaces(display, posA, posB, depth + 1)
```

#### Walls

We simply need to adjust how we are rendering our faces to not render lines facing away from the player. Traversing before or after rendering defines in which order we render our walls facing our player.

The traditional Painters Algorithm renders based on furthest to closest, each wall covering the one behind it. This is simple but non-performant as large portions of walls are rendered and then overwritten wastefully.

In DOOM they revesed the approach rendering from closest to furthest. Because the game was actually 2D projected as 3D the geometry was simple enough to keep a running list of screen coords that were rendered to and to cull any walls behind the walls already rendered.

![](/images/bsp_4_walls.png)

```python
    def drawWalls(self, camera, display, depth = 0):
        if self.isLeaf == False:
            behind = self.splitter.isPointBehind(camera.worldX, camera.worldY)
            if not behind:
                topLeft, topRight, bottomRight, bottomLeft = camera.projectWall(self.splitter, display.width, display.height)
                if topLeft:
                    wallLines = [ topLeft, topRight, bottomRight, bottomLeft ]
                    display.drawPolygon(wallLines, self.splitter.drawColor, 0)
        if self.front:
            self.front.drawWalls(camera, display, depth + 1)
        if self.back:
            self.back.drawWalls(camera, display, depth + 1)
```

#### Basic Collision/Bounds Checking

It was simple enough to test if the position is "within" a wall" through a form of BSP collision detection. Enabling this check in code prevented the player from crossing a wall.

We can facilitate this with a check to see if the leaf node of the tree we wind up in is considered solid or not. If the position we are testing is in a lead node that is solid then it is not allowed.

```python
    def inEmpty(self, testPoint):
        # recurse the tree until we find a leaf node
        if self.isLeaf:
            return self.isSolid == False
        beh = self.splitter.isPointBehind(testPoint[0], testPoint[1])
        if beh:
            return self.back.inEmpty(testPoint)
        else:
            return self.front.inEmpty(testPoint)
```


## Conclusions

The BSP tree is really an awesome algorithm and data structure in one. The selection of a splitter line can affect the performance. The wider and shallower our tree the faster our checks become, so more than one BSP could be tested for performance improvements.

You can see this BSP Tree in action in my Doom Engine recreation in Python.

Some of the code here was of course referenced from other documentation about a BSP tree.


### Maths

As I stated before here is the math functions referenced in the code above

```python
import math

def crossProductLine(a, b):
    return a[0] * b[1] - a[1] * b[0]
    #{   return (p.x*q.y - p.y*q.x); }

def pointBehindSegment(point, a, b):
    cross = (b[0] - a[0]) * (point[1] - a[1]) - (b[1] - a[1]) * (point[0] - a[0])
    if cross > 0:
        return True
    if cross < 0:
        return False
    if cross == 0:
        return None

def normalize(a, b):
    if a != 0 or b != 0:
        length = math.sqrt(a * a + b * b)
        return [a / length, b / length]
    return [a, b]

def perp2d(a, b):
    return [-b, a]

def rotate2d(x, y, rads):
    cos = math.cos(rads)
    sin = math.sin(rads)
    return [(x * cos) - (y * sin), (x * sin) + (y * cos)]

def distance2d(x1, y1, x2, y2):
    x = x1 - x2
    y = y1 - y2
    return math.sqrt(x*x  + y*y)

def toRadians(x, y):
    v = normalize(x, y)
    return math.atan2(v[1], v[0])

def toVector(rads):
    return [math.cos(rads), math.sin(rads)]

def intersection2d(splitterStart, splitterEnd, lineStart, lineEnd):
    s1 = splitterStart
    e1 = splitterEnd
    s2 = lineStart
    e2 = lineEnd

    a1 = e1[1] - s1[1]
    b1 = s1[0] - e1[0]
    c1 = a1 * s1[0] + b1 * s1[1]

    a2 = e2[1] - s2[1]
    b2 = s2[0] - e2[0]
    c2 = a2 * s2[0] + b2 * s2[1]

    delta = a1 * b2 - a2 * b1
    # if lines are parallel, the result will be delta = 0
    if delta != 0:
        return [(b2 * c1 - b1 * c2) / delta, (a1 * c2 - a2 * c1) / delta]
    return None
```