BSP Algorithim

hi. a good start for learning the concepts and uses of BSP trees would be the BSP FAQs. http://www.faqs.org/faqs/graphics/bsptree-faq/. You should find many many other articles on BSP trees on the net which will help you understand its recursive structure. Given a collection of polygons in a scene you can use the planes of each as splitting planes to construct a BSP tree. The tree will have leaves at the end of a path that is a conjunction of splitting planes and objects can be classified by this tree.

http://www.devmaster.net/articles/bsp-trees/

that linked helped me imensly, its pretty much all psuedo code, and some small things have been left out, but it was the best resource I found on how to create and also has a very good function to find the dividing polygon. It also has many other tutorials which build off this. I highly recommend it, while not perfect it still helped me a lot.

-THACO

Vlastimil Havran's PhD Thesis is an awesome source of information. His focus is on spatial subdivision schemes which are useful for shooting rays, but the tree construction is applicable to both collision detection and rendering. He begins by discussing the most widely used partitioning methods and their pros and cons, then narrows his focus to kd-trees (or BSPs with axis-aligned split planes) as they have been widely found to be best for raytracing.

It would be worth buying if it weren't already free :)

also, try and get your hands on the Wildmagic 2.5 source
code. it's got an easy to understand bsp-tree implementation
(it picks the first triangle in the list and uses it as the
first splitting plane and then recursively puts triangles
into + - and coincident lists). Wildmagic 3.0 has chucked
bsp trees.

for more complex bsp-tree code, Croteam's full bsp tree source
is available on the Serious Sam SDK. But don't look at that,
because it's one hell of a mess :D.