Printable View
I'm trying to create a binary space partition tree for a space. I just want to input the space and have an algorithm partition it. How is the input spatial data represented? Is it just a set of polygons(described by a set of 2D points) with 3D coordinates, and then another set of coordinates for spatial orientation?
Are there any tutorials or books on this that you would recommend?
The input format can be anything you want. Most model formats have something like a vertex set, and then polys specified in terms of the vertices.
edit: wotsit.org has file format specs for some 3D model formats.
Normally BSPs are based on planes created by vertices rather than just vertices. The vertices in themselves do not represent much. Remember that any 3 points in space are guaranteed to form a plane.
Once you determine the planes and the plane you wish to use as the root of the BSP you can then decide which half-space other planes lie in relation to the root plane. This is how you would build your tree.
There are several docs on the web about this. Now picking the correct starting plane so as to keep the tree as balanced as possible is quite complex.