## Bsp

Feanor
Unregistered

Post: #1
Given a list of polygons, how might one chose the polygons to act as the splitting planes?
Luminary
Posts: 5,143
Joined: 2002.04
Post: #2
Guess

Seriously, finding the "best" BSP is almost certainly NP-complete, so just pick a largish polygon somewhere near the geometric center of the set of polygons you're trying to split...

Make sure that only the crude level geometry is being put into your BSP, too &mdash; complex objects like trees and statues and so forth should be handled by a separate system.
Luminary
Posts: 5,143
Joined: 2002.04
Post: #3
Also, I assume you're using the BSP for collision detection/physics rather than graphics (that is so last century), so consider having simplified collision geometry rather than colliding against the actual level geometry. That'll not only make the BSP easier to create, but faster to use as well.
Feanor
Unregistered

Post: #4
I may have found a means to avoid using a BSP, but, yes, I was being retro and thinking about making a classical Quake-style BSP for geometry. I found an article that talked about how to make a CSG with a BSP. However I have since found a better solution -- SGI has an article about how to use the stencil buffer and a normalized CSG tree to draw CSG boundary representations -- no need to modify the actual geometry!

The only thing is, I'm thinking of using it for indoors, where the "objects" in the CSG would be rooms and hallways and such, which are effectively inside out (complements). I'm thinking that won't make any difference, but I'm not sure.

But I'd still like to make a BSP in Cocoa. I found some great C++ sample code to try to convert. If it is useful for collision detection in my game, that would be excellent. I will be giving it away free, anyway, if I get it working.

What are you using these days for fast geometry visibility determination? I'm partial to Octrees, but it seems to me there are times when a BSP would still be useful. Octrees are great because there is a way to quickly calculate adjacent nodes, even nodes at different scales, for when dynamic objects are moving around.