I'm planning on using a BSP-tree combined with a Beam tree, this should be pretty
fast for hardware. Quake1 uses a similar vsd system, so it works fine in software too.
I tried octree but they are way too slow, by them self at least. A portal engine with each
sector subdivided into an octree should work well, then you can have pretty big sectors.
KD-trees seem like a crappier version of BSP-tree...
If you don't know what Beam trees are, you can look it up in Micheal Abrash Black book
thingie, and Harmless algos on flipCode has some info. That's everything I've found on
beamtrees, CG P&P doesn't even mention it.
Anyway, good luck
Greetings Tobias