Programming, Work

BSP Compiler

So, about a month ago, I started looking into the possibility of using a simple polygonal cutting system so that I could create more interesting shapes. Instead of just having a brush that completely replaces or removes, I have brushes that add and subtract.

So, when I have an odd shape brush, it will compute the boolean difference of the two shapes or the Union of the two shapes to create a new little tile. But, the challenge with this is of course to make it rigid and robust. I was pointed at an interesting article at work that addresses the robust issue quite elegantly and makes the whole idea a very interesting and would introduce some very powerful options.

A plane based BSP tree using fixed point math.

The first thing was to get the planes setup so that I could describe a surface with just planes and have them converted to polygons. Then after that, you setup a few simple predicates that check for plane orientation and point classification only using planes. So the polygons are planes with a list of planes as its border. Every point for the polygon is in fact a triple of planes and using a variation of the old Sutherland clipping algorithm, you are pretty much set to plug that into the old BSP Tree.

There are a few differences from traditional BSP implementations that I make, I do not setup the whole sub-hyperplane configuration since I don’t really care about merging trees. The trees are small, working on only leaf nodes in my flat octree. I just feed the original polygon into the trees to be cut and then I simplify the polygons as I traverse back up the tree. Basically undoing any unwanted cuts by the actual tree.

One of my tests is the Stanford bunny, made up of about 5000 triangles and a torus of about 530 triangles. Generating the BSP tree for the bunny on my 2 year old laptop, takes about 1 second. And computing the difference of these two shapes takes a little bit less. And this is a worst case scenario where I am importing models into the app to be converted into building blocks.

I am now collecting all the polygons that were cut but could not be merged in the first pass. Those are going to be re-tessallated to remove any t-vertices in the final output geometry. Luckily the first pass, gets rid of most of the cuts and there are another set of academic papers that address that problem as well.

Then it is time to clean up the implementation and hook it up to the rest.

A very interesting set of tools have been procured with this setup.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s