BSP trees

[Diniden]

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!

[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:

O     O

There's lots of planes you could pick:

O /    O
O   |  O
O     \O

Just pick one:

O  |  O

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

.
  .
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

                                             .   .
(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

[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.

[Diniden]

And for those more interested, here's a nice BSP tree article:

http://www.exaflop.org/docs/naifgfx/naifbsp.html

[Diniden]

Am I going batty?

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...)

[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:

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);
        }                
    }
} 

[Diniden]

Alrighty, check it out: got the basic plug and chug BSP tree working for the most part

-LINK CHANGED SEE NEXT POSTS-

This example shows randomly generated faces (very intersecting) and it shows that all are perfectly accounted for and will render properly without problem, even if they cross and pierce each other to an oblivion.

Since it's random and due to the nature of anything binary and doubling, this may accidentally cause a HUGE amount of faces to be generated. So if it gets super bogged down, that's what happened. Just reload it for a better roll if it happens :P

Also note that I turned off backface culling so that you can see the effect easier.

I haven't started on incorporating dynamic objects yet. I'm first going to finish texturing and re-tessellation on static objects before I work on incorporating the dynamic objects, so that I will have a big overview of how I handle everything, so I can try to find efficiency boosts on a bigger scale.

Oh also, please forgive the lack of re-tessellation (the disappearance of faces as they approach the edges of the screen), I've been lazy on that note and havn't thought of the best route I want to take in that area.