Line by Line, Finding Walls for Rendering in a BSP Tree

Recently we managed to grab all entities that a camera could hypothetically see from a BSP tree. Now, it's time for the similar job of finding all walls that should be rendered. The main idea here is that we want as few walls as possible, to minimize compute and overdraw. Although we won't be doing the actual rendering, this could be used by a game that would do the rendering.

Also, after the last post, I added functionality to find entities using a circle as the query object. I would suggest looking through the code for that one, and see if you can understand it. This functionality would be good for checking collision between the player and entities (if the player is a cylinder).

Using the View Frustum

When we were funding entities, we were able to use this thing called the view frustum to search for ones that were visible. This is exactly what we're going to do here.

func (node *BSPNode) querySegmentsByTriangle(triangle Triangle) []*Segment {
    // Finds all segments that are within this triangle
    return nil
}

func (tree *BSPTree) querySegmentsByTriangle(triangle Triangle) []*Segment {
    return tree.root.querySegmentsByTriangle(triangle)
}

// Queries the BSP tree using the
// view frustum for all viewable walls
func (camera *Camera) getWallsInView(world *BSPTree) []*Segment {
    return world.querySegmentsByTriangle(camera.createViewFrustum())
}

As per usual, we've defined the wrapper method on the tree, and call this from the camera using the view frustum.

How Do We Get The Lines?

With pretty much every query we've made so far, we've done the leaf node case first, which is exactly what we're going to do now. The thing is, the leaf nodes don't contain any lines, and therefore don't need checking. This means if we're at a leaf node, we do nothing!

if node.isLeaf() {
    return nil
}

Now we can start the interesting case, branch nodes. Just like querying entities with a triangle, we want to know if the triangle overlaps the splitter, or is entirely on one side. If it is entirely on one side, then we don't add any lines, but check the respective child node.

relation := node.splitter.triangleRelation(triangle)

switch relation {
case 1:
    return node.front.querySegmentsByTriangle(triangle)
case -1:
    return node.back.querySegmentsByTriangle(triangle)
default:
    // TODO: Triangle lies on splitter
    // (need to search through own lines)
    return append(
        node.front.querySegmentsByTriangle(triangle),
        node.back.querySegmentsByTriangle(triangle)...,
    )
}

If it's fully in front, only check the front. If it's fully behind, only check behind. If it's both, check both, and we also need to check the splitting lines. So now we need a method to check if a line intersects with a triangle. There are many cases to this, but there are 3 main ones.

1. The line intersects with one of the triangle's lines.
2. The line is fully within the triangle, and therefore no intersects trigger.
3. The line is outside of the triangle completely.

With these in mind, let's start writing!

func (triangle *Triangle) segmentIntersect(segment Segment) bool {
    // Find intersections between any lines
    _, i := (&Segment{triangle.p1, triangle.p2}).intersect(segment)
    if i != LI_NONE {
        return true
    }

    _, i = (&Segment{triangle.p2, triangle.p3}).intersect(segment)
    if i != LI_NONE {
        return true
    }

    _, i = (&Segment{triangle.p3, triangle.p1}).intersect(segment)
    if i != LI_NONE {
        return true
    }

    return false
}

Those are the line intersect cases, so we've done case 1 (and implicitly case 3 with the final return false). And case 2 should be easy, just check if one of the segment's points is within the triangle.

return triangle.pointWithin(segment.start)

As per usual, we only have to check one of the ends. This is because if only one point was within, an intersection would've occurred and be caught by an earlier case.

Getting ALL Intersecting Lines

So now we know how to check if a line is within a triangle, we can find all the intersecting lines from the node.

func (node *BSPNode) getLinesWithinTriangle(triangle Triangle) []*Segment {
    // Start with some capacity rather than
    // many grow calls
    marked := make([]*Segment, 0, len(node.lines))

    // Find all intersecting lines
    for i := range len(node.lines) {
        s := node.lines[i]
        if triangle.segmentIntersect(*s) {
            marked = append(marked, s)
        }
    }

    return marked
}

Then, we use this function in that recursive query we were writing before.

return append(
    node.getLinesWithinTriangle(triangle),
    append(
        node.front.querySegmentsByTriangle(triangle),
        node.back.querySegmentsByTriangle(triangle)...,
    )...
)

And that should get us all the intersecting lines!

First Tests

Using this:

walls := camera.getWallsInView(bsp)
fmt.Println("Found these walls from triangle")
for i := range len(walls) {
    fmt.Println(walls[i])
}

I get some walls! And the walls look correct after looking through the original level. What would be cool is to have a top down visualization of those walls that are marked for rendering.

Back-face Culling

We're not done yet, when finding walls to mark for rendering, we want as few as possible. A common way to cull lines is through the method of back-face culling. What this does is only render the lines that are facing towards the camera. Imagine the walls in your house, they are not a single segment, but rather 4 segments put together to give the physical wall depth. You can now imagine that the front-face of these segments all face outwards, and the back-face points inwards. In this way, all the back-faces are occluded by the front-faces, so they will never be drawn. Here is a diagram to help with this a bit.

As you can see, there is never a case where you can actually see the back-faces, and so we're going to cull them!

// Queries the BSP tree using the
// view frustum for all viewable walls
func (camera *Camera) getWallsInView(world *BSPTree) []*Segment {
    return camera.backfaceCull(
        world.querySegmentsByTriangle(
            camera.createViewFrustum(),
            ),
        )
}

// Deletes any walls that aren't
// facing the player
func (camera *Camera) backfaceCull(walls []*Segment) []*Segment {
    facing := make([]*Segment, 0, len(walls))

    for i := range len(walls) {
        w := walls[i]
        if w.pointInFront(camera.pos) {
            facing = append(facing, w)
        }
    }

    return facing
}

That was very easy, doesn't change the output for me since each line is facing the camera, but, looks good. Now we have an efficient way to find all segments the camera can see!

Challenge

The BSP tree is coming together quite nicely, but it's still far from being usable. Hence, here are some more vital functions you could add.

1. Hit-scan collision with walls to find closest point of contact.
2. Hit-scan collision with entities to find possible targets.
3. Player collision with walls.
4. Moving an entity through the BSP tree.