Line by Line, HOW do I query my BSP?

Now, if you read my last post (sorry about the length...), you will remember we constructed a BSP tree. The BSP tree we created could hold these entities, but we never actually used this feature. Well, I was sitting and thinking about what someone might want to do with a BSP tree, and then it hit me, read from it! So, that's exactly what we're going to do, except, we're going to do it for a specific use case.

The View Frustum

Imagine you're playing a 3D game, where the walls are governed by a BSP tree. Now, looking from the top down, what would the player's view look like? A triangle! This is called the view frustum. What we're going to do, is apply the view frustum on the BSP tree, and in return we should get all entities that a hypothetical player could see. Our current function simply takes a point, and gets all entities in the node at that point, but that's practically useless. So now after all this, we should end up with some meaningful functionality.

The Camera

To start our programming, we want a camera object that we can move around the world. This way, we could easily move it around to get different results.

type Camera struct {
    pos     Pos
    angle   float64
    viewDis float64
    fov     float64
}

func (camera *Camera) createViewFrustum() int {
    // Generates a bounding triangle that
    // should encapsulate everything that
    // the camera can see
    // TODO: Return a triangle
    return 0
}

func (camera *Camera) getEntitiesInView(world *BSPTree) []*Entity {
    // Queries the BSP tree using the
    // view frustum for all viewable entities
    return nil
}

A position, an angle, the view distance, and the field of view, pretty simple. We also need to be able to create the view frustum based off of the camera, so we've got a method for that. We also need that method to get all the entities the camera can view. We're missing something, we need to define what a triangle is, otherwise we can't make that view frustum.

type Triangle struct {
    p1, p2, p3 Pos
}

Very simple, pretty much exactly how you would expect. Remember, lines have a front and a back side, so the order of p1, p2, and p3 will be important later.

Creating the View Frustum

Let's implement generating the view frustum. All we need is to create a triangle, and for that, we only need 3 points. The first point is obvious, the position of the camera, but the other two will require some trigonometry to figure out.

return Triangle{
    p1: camera.pos,
    p2: Pos{},
    p3: Pos{},
}

Well, it should be pretty easy to generate a point in the direction the player is facing. We would simply use sine and cosine to get the x and y coordinates of this point using the camera's angle as input. Then, we would scale by view distance. Well, we can do the exact same thing for the edges of our view. All we have to do is add or subtract half of the field of view before our calculations!

return Triangle{
    p1: camera.pos,
    p2: Pos{
        camera.pos.x + math.Cos(camera.angle-camera.fov/2)*camera.viewDis,
        camera.pos.y + math.Sin(camera.angle-camera.fov/2)*camera.viewDis,
    },
    p3: Pos{
        camera.pos.x + math.Cos(camera.angle+camera.fov/2)*camera.viewDis,
        camera.pos.y + math.Sin(camera.angle+camera.fov/2)*camera.viewDis,
    },
}

Looks like we've started to do some addition of positions and multiplication of magnitudes, so let's move those to their own functions.

func (pos Pos) add(other Pos) Pos {
    return Pos{
        pos.x + other.x,
        pos.y + other.y,
    }
}

func (pos Pos) scale(scale float64) Pos {
    return Pos{
        pos.x * scale,
        pos.y * scale,
    }
}

func (camera *Camera) createViewFrustum() Triangle {
    return Triangle{
        p1: camera.pos,
        p2: camera.pos.add(Pos{
            math.Cos(camera.angle-camera.fov/2),
            math.Sin(camera.angle-camera.fov/2),
        }.scale(camera.viewDis)),
        p3: camera.pos.add(Pos{
            math.Cos(camera.angle+camera.fov/2),
            math.Sin(camera.angle+camera.fov/2),
        }.scale(camera.viewDis)),
    }
}

That's a lot better, and will probably help in future, but with that, we have completed our view frustum.

Finishing the Camera

Before we can finish the camera, let's define our method on the BSP tree to run this code.

func (tree *BSPTree) queryEntitiesByTriangle(triangle Triangle) []*Entity {
    // Will find all entities within this triangle
    return nil
}

Nice, now we can call this in our camera code.

func (camera *Camera) getEntitiesInView(world *BSPTree) []*Entity {
    return world.queryEntitiesByTriangle(camera.createViewFrustum())
}

We just take that view frustum we made, and chuck it into the query logic. However, how do we know if an entity is within a triangle? Let's create a function for that, that decides whether a point is within. Luckily, the way we've defined everything makes this very simple.

Remember, lines have a front and a back, and they also have a method for determining whether a point is in front of the line or not. In the way we've defined our triangle, we are able to deduce that the point is within it if the point is in front of all the lines that make up the triangle. Make sense? Let's write the code, that might help.

func (triangle *Triangle) pointWithin(pos Pos) bool {
    return (
        (&Segment{triangle.p1, triangle.p2}).pointInFront(pos) &&
        (&Segment{triangle.p2, triangle.p3}).pointInFront(pos) &&
        (&Segment{triangle.p3, triangle.p1}).pointInFront(pos))
}

Bam, so now we can easily check if an entity is within the view frustum, since the view frustum is a triangle, and an entity is a point.

I think we're ready to get into the real code.

Querying the Node

As per usual, we have 2 cases, those being a leaf node, and a branch node. Let's start with the leaf node.

if node.isLeaf() {
    // Create the list of entities to
    // give back to query
    chosen := []*Entity{}

    // Find all entities within
    for i := range len(node.entities) {
        e := node.entities[i]
        if triangle.pointWithin(e.pos) {
            chosen = append(chosen, e)
        }
    }

    return chosen
}

This should make sense, just finding the entities that are within the triangle. However, we will now get to the more complicated case, branches. What we need to figure out is whether the triangle is entirely on one side of the splitter, or crosses it. If it is entirely on one side, then we only need to query one child, which is the efficient case we'd like. However, if the triangle lies over the splitter, then we need to query both children. From this, we want a method we can use to decide whether a triangle is in front, behind, or on top of a line.

// Positive if in front, negative if behind, 0 is on top
func (segment *Segment) triangleRelation(triangle Triangle) int {
    b1 := segment.pointInFront(triangle.p1)
    b2 := segment.pointInFront(triangle.p2)
    b3 := segment.pointInFront(triangle.p3)

    if b1 && b2 && b3 {
        // Fully in front
        return 1
    } else if !b1 && !b2 && !b3 {
        // Fully behind
        return -1
    } else {
        // Both
        return 0
    }
}

Having three cases does make this annoying, but hopefully this makes sense. From this, we can complete the branch case.

relation := node.splitter.triangleRelation(triangle)

switch relation {
case 1:
    return node.front.queryEntitiesByTriangle(triangle)
case -1:
    return node.back.queryEntitiesByTriangle(triangle)
default:
    return append(
        node.front.queryEntitiesByTriangle(triangle),
        node.back.queryEntitiesByTriangle(triangle)...,
        )
}

This should make the efficiency of the first two cases obvious, as we only have to do half the work.

Testing

// Get some entities?
camera := Camera{
    pos:     Pos{0, 0},
    angle:   0,
    viewDis: 200,
    fov:     math.Pi/2, // 90deg
}

fmt.Println(camera.getEntitiesInView(bsp))

Now obviously, we have no entities in the BSP, so this returns an empty list. So now we know it doesn't hallucinate! But let's test a real case, let's add some entities.

bsp.addEntity(&Entity{
    name: "John",
    pos:  Pos{50, 0},
})

bsp.addEntity(&Entity{
    name: "Mark",
    pos:  Pos{0, 50},
})

bsp.addEntity(&Entity{
    name: "Luke",
    pos:  Pos{-50, 0},
})

bsp.addEntity(&Entity{
    name: "Matthew",
    pos:  Pos{0, -50},
})

entities := camera.getEntitiesInView(bsp)
fmt.Println("Found these entities")
for i := range len(entities) {
    fmt.Println(entities[i].name)
}

Now, given the camera is looking towards the positive x-axis from origin, we should expect the entity with a positive x position to be shown, and this is exactly what I get, John. So with that, we've completed our work!

Challenge

Now we're able to imagine what entities might be shown if we were to view this from a first-person perspective, but what about some other useful queries? I already put rectangle and circle collision in the last post's challenges, so let's do something different.

1. Similar to this queryEntitiesByTriangle, can you write querySegmentsByTriangle.
2. Moving and turning the camera.
3. Having moving entities.
4. Could you disregard entities that are entirely obscured by a wall?
5. Visualize the view frustum and visible entities.

Note, for a little help, I've written lines to an external file, and the BSP tree is also written to a file. This way, you can easily modify the walls of the world, and see what BSP tree results.