i just heard that it has something to do with something about ... about spatial division? i also know that it is widely used in some circumstances like "in door rendering". i also know what a BSP tree is, theoretically, i learned it from my Data-Structure course. But, what i do not know is how it works, what benefit it can bring us graphics programmer. could anybody give me a short description about BSP tree in graphics programming? thx very much!

Like devil says, it has to do with the order of rendering.
Each node contains one triangle/plane.
Start at the first node.
Find out if the camera position is in front of or behind the node.
Go to the node on the opposite side and perform this process on it.
Draw this node.
Go to the node on this side and perform this process on it.
When you are done you will have drawn everything is the proper order.

Setting up the tree simply requires that every plane does not intersect any other triangle. So it requires splitting triangles up into multiples for cases where the planes do intersect. Look it up if you''re curious.

--------------------------------------------------------
Life would be so much easier if we could just get the source code.

quote:Original post by Challenger17
i just heard that it has something to do with something about ... about spatial division?

Yup, it''s one of a number of spatial subdivision techniques.

In graphics (and, indeed, in the rest of a game) it''s often very helpful to be able to describe where things are in relation to one another. For example: if you know that a polygon is behind another one, you don''t need to bother drawing it.

BSP (Binary Space-Partitioning) trees work by taking a load of geometry - say, your level - and ''partitioning'' (splitting) it repeatedly using planes. Geometry is divided into polygons in front of the plane, and behind the plane (polygons intersecting the plane are usually split in two and sent either way).

It''s not really used in graphics - at least for depth sorting - because hardware z-buffering is so proliferant these days (though it still may be useful for things like alpha blended polygons - YMMV).

Where it''s more useful is in areas like collision detection. If you want to test an object for collisions with the world geometry, you''d have to test it against every polygon in the level, regardless of where that polygon is in relation to the object. By using spatial subdivision techniques - BSPs, Octrees, or whatever you like - you can quickly test the object against the planes in the BSP tree, and each time you do that you''re throwing out half of what you''ve got left to test.

Using BSP for back to front rendering is probably the least important characteristic of them. That''s what Z-buffers are for.

More important than this is the benefits for collision detection, and, when combined with PVS, reduced geometry rendering.

i got it! thx a lot!
btw could anyone show me some link to let me get deep in to this BSP tree?

Ask and ye shall recieve...

http://www.3dtechdev.com/tutorials/leafbsp/3dbsptrees.html


-=[ Megahertz ]=-