# BSP trees

• 06-10-2009, 04:13 AM
Diniden
BSP trees
So I have just discovered BSP trees and am having a little bit of understanding issues here.

So with a BSP you can pre-calculate static objects into the tree quick and simple. Now, with that precalculated tree how exactly do you use a point of view in relation to it to determine hidden faces and all that jazz? I seem to be missing some major point in exactly how to use the tree after the tree is made.

Pointers and articles would help a lot!
• 06-11-2009, 09:51 AM
rachil0
From my understanding, BSP trees are more about sorting than hidden surface removal / occlusion culling. The basic idea of binary space partitioning is to identify (any) plane between two objects such that one object is totally in front of the plane, and the other object is totally behind the plane. Consider 2 spheres for example:

Code:

`O    O`

There's lots of planes you could pick:

Code:

```O /    O O  |  O O    \O```

Just pick one:

Code:

`O  |  O`

When the observer, "." is in front of the plane, the back sphere can not occlude the front.

Code:

```.   . O  |  O    (draw me first) .  .```

So draw the back sphere first, then draw the front. On the other hand, when the observer is behind the plane, the situation is flipped (draw the front sphere, then draw the back

Code:

```                                            .  . (draw me first)    O    |    O        .                                       .```
The "tree" part comes in because you apply the idea recursively to the front and back objects, until you cut them down into something to simple that it cannot self-occlude. IE each of the spheres in this example could really be a complicated object, that needs further sorting before we can "just draw it".

Not to pimp my own work too much, but you might find some of the info in this thread useful - it's a mini-blog about implementing a quake-style engine in flash 10. There are specific posts about BSP's that you might find useful (post #59, post #75), while post #113 is a good overview of the sorting techniques and occlusion culling used in the engine. Post #101 has the most recent eye-candy - the last significant update was in february.

Here's a link straight to the eye candy, from there you can decide if you want to read more.

http://board.flashkit.com/board/show...=749263&page=6

Best of luck :)
• 06-11-2009, 04:47 PM
Diniden
Ah I see now how it handles the sort thanks a ton!

And kudos on your 3D engine! It has come a long way since last I saw it :P

I'm beginning to see how I can use the tree for occlusion and corrections for intersecting objects now....I keep saying using the tree for these purposes because of these sites I went through:

http://blog.alternativaplatform.com/...20/dynamic-bsp

ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html#1.txt

I figure the more one can do with the tree the more insane efficient one can make it. I believe it's a core reason how alternitiva accomplishes those unreal graphics capabilities.
• 06-25-2009, 04:46 AM
Diniden
And for those more interested, here's a nice BSP tree article:

http://www.exaflop.org/docs/naifgfx/naifbsp.html
• 06-28-2009, 04:53 PM
Diniden
Am I going batty?

PHP Code:

``` public function viewTree(node:BSPTree, camLoc:VectorVertex, faces:Array):void {    if(node!=null) {                var test:int = partition.testVertex(camLoc); //which side the camera is in relation to the partition 1 or 0 = front                if(test!=-1) {            viewTree(node.getBack(), camLoc, faces);            faces.push(node.getPartition()); //insert faces in order into desired array            viewTree(node.getFront(), camLoc, faces);        } else {            viewTree(node.getFront(), camLoc, faces);            faces.push(node.getPartition());            viewTree(node.getBack(), camLoc, faces);        }                    }}  ```
VectorVertex is just a typical vector with X, Y, and Z value stuff.

testVertex() returns 1 if vertex is in front of the plane, 0 if on the plane, and -1 if behind the plane.

partition is the nodes partitioning plane. Each node of the tree represents a face used in the worldspace.

This recursive loop should work for walking the tree right? Where if the viewer is on one side of the plane then grab the other side first?

For some reason it's freaking out on me ;~;. I hope that there's something wrong with this part. If not, then I have some big problem back in the formation of my tree *shudders to think of returning to debugging it*

Current result: www.diniden.com/3D.html
You have to move around first, to see the boxes (sorry it moves insanely fast right now...)
• 06-28-2009, 05:56 PM
Diniden
SOLUTION:

Instead of just testing if the camera was in front or back of the plane, I found most of the time it's best to do a "back face cull" like procedure for this situation. I don't understand why the other code didn't work (I would appreciate someone helping me understand why), but here's a working walk:

PHP Code:

``` public function viewTree(node:BSPTree, camLoc:VectorVertex, faces:Array):void {    if(node!=null) {                var facePoint:Vector = node.getPartition().getVertices()[0];        var camToFace:Vector = camLoc.subtract(facePoint);        var camFaceDot:Number = camToFace.dot(node.getPartition().getSurfaceNormal());                        if(camFaceDot>0) {            viewTree(node.getBack(), camLoc, faces);            faces.push(node.getPartition());            viewTree(node.getFront(), camLoc, faces);        } else {            viewTree(node.getFront(), camLoc, faces);            //faces.push(node.getPartition()); <-omitted this for a back face cull            viewTree(node.getBack(), camLoc, faces);        }                    }}  ```
• 06-29-2009, 02:51 AM
Diniden
Alrighty, check it out: got the basic plug and chug BSP tree working for the most part