Jump to content
  • entries
  • comments
  • views


Sign in to follow this  


We are not going to use BSP in the traditional way (ie, for implementing painters algorithm during rendering).
Rather we will use BSP as an intermediate tool for generating our cell and portal graph.
We are interested in discovering a set of convex subspaces and the 'holes' that connect them - BSP is going to get us more than half way to our goal.

[subheading]Discovering Convex Subspaces[/subheading]
The first stage then is to generate a BSP tree from an input set of triangles.
And to be quite specific, it will be a 'leafy' tree, with all the polygons located in leaf nodes, and all other nodes recording a splitting plane (this will make more sense as we progress).

While building our BSP tree, it is desirable to attempt to create a well-balanced tree of minimal depth... this brings us to our first algorithm: given an input set of triangles, discover a triangle whose 3D Plane 'best' partitions the input triangles.
By 'best', we mean that Plane which produces the most even number of triangles in each of the resulting subsets, while simultaneously 'splitting' the least other triangles.
These two goals are mutually exclusive, this algorithm implements a simple heuristic which attempts to achieve our mutual goals.

The process of building the BSP tree is recursive - given the original input set of triangles, partition it into two subsets, and repeat.
When should we stop?
For our purposes, we should not stop until a triangle subset contains NO candidate splitting planes.
When this happens, we have discovered a CONVEX SUBSPACE whose CLOSED HULL is defined by the set of planes of the triangles in this subset (and the planes of its ancestor nodes). Furthermore, we know that the holes or portals which connect this subspace to other subspaces must exist on existing splitting planes, defined at non-leaf nodes in our tree.

At this stage, we have a complete leafy BSP tree describing our world... its leaf nodes represent convex subspaces or 'rooms' in our world, our next step is to discover the portals or 'holes' which connect the subspaces together.
Sign in to follow this  


Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!