BSP trees and your mom.
category: general [glöplog]
Anyone use bsp trees for collision detection? I never have, seems I always rely on oct-trees for nearly everything. It's just simpler in my head. Any wicked crazy bsp fans out there? What algorithms for either sorting what to test/draw first or reducing the number of polygons to be tested/drawn do people like?
BVH, BIH, kD.. and even grids will have a comeback soon, i guess..
well on my side i'm more your basic kd-tree boy for space partitionning :p but else what toxie said.. BVH and BIH can be (much) faster to build.. in fact i wonder who the hell still uses BSP nowadays..
I'm using hierarchical spatial hashing for cpu-based collision detection in my physics system. I'm looking for ideas for a pure gpu-based system, but so far have only tested grids using texture arrays. I suppose I'd be interested in literature concerning this if anyone has looked into the issue.
I did some basic rendering tests a while ago using bsp/pvs with bruteforce raycasting but obtained some pretty terrible results, probably because my approach sucked :-)
I did some basic rendering tests a while ago using bsp/pvs with bruteforce raycasting but obtained some pretty terrible results, probably because my approach sucked :-)
Vleesboom.
(General) BSPs are not a great collision structure.
Comparing with kd-Trees and BIHs: Axis-aligned splits are significantly faster to evaluate, and more importantly, unconditionally numerically robust.
Comparing with BVHs and BIHs: The latter two are much better at carving away empty space and hence drilling down to the interesting parts (or, just as well, quicker to find that no collision occurs).
Comparing with Octrees: Hmm, never been a fan of Octrees myself. Very rigid structure (both in terms of data structure and spatially) and lots of pointers (i.e. data that is just spent describing your structure organization in memory): with a binary tree, storing just one pointer to the left child and having the right one follow immediately afterwards is a good tradeoff; you just need 2 extra bits to denote which of the two child nodes exist, and those you can usually scrounge together from elsewhere. For octrees, while the same is theoretically possible, you need to find 8 extra bits somewhere (not nearly as easy as 2), and things like "descend to all children" need to iterate over bits set in that flag field. No fun. Also, the classic "just halve along each axis" splitting rule is really bad with objects of very different sizes. And if you don't have them, why bother with an octree, just use a good grid implementation - simpler and better locality! If, on the other hand, you want more adaptivity, then screw Octrees and use something like Quad-BVHs. Better fan-out than the binary partitions (i.e. less tree levels to traverse, this is the main advantage of Octrees in theory, but then they squander it on needing 4 extra levels just to get anywhere in large scenes), more useful work done per cache line touched, and not significantly more complex than a normal BVH.
BSPs for collision are a good choice in a BSP-based renderer, since you have them lying around anyway, and you presumably already spent the time on the hairy numerical robustness issues. But when you don't, well, there's better options with lower complexity and far larger "bang for the buck".
Comparing with kd-Trees and BIHs: Axis-aligned splits are significantly faster to evaluate, and more importantly, unconditionally numerically robust.
Comparing with BVHs and BIHs: The latter two are much better at carving away empty space and hence drilling down to the interesting parts (or, just as well, quicker to find that no collision occurs).
Comparing with Octrees: Hmm, never been a fan of Octrees myself. Very rigid structure (both in terms of data structure and spatially) and lots of pointers (i.e. data that is just spent describing your structure organization in memory): with a binary tree, storing just one pointer to the left child and having the right one follow immediately afterwards is a good tradeoff; you just need 2 extra bits to denote which of the two child nodes exist, and those you can usually scrounge together from elsewhere. For octrees, while the same is theoretically possible, you need to find 8 extra bits somewhere (not nearly as easy as 2), and things like "descend to all children" need to iterate over bits set in that flag field. No fun. Also, the classic "just halve along each axis" splitting rule is really bad with objects of very different sizes. And if you don't have them, why bother with an octree, just use a good grid implementation - simpler and better locality! If, on the other hand, you want more adaptivity, then screw Octrees and use something like Quad-BVHs. Better fan-out than the binary partitions (i.e. less tree levels to traverse, this is the main advantage of Octrees in theory, but then they squander it on needing 4 extra levels just to get anywhere in large scenes), more useful work done per cache line touched, and not significantly more complex than a normal BVH.
BSPs for collision are a good choice in a BSP-based renderer, since you have them lying around anyway, and you presumably already spent the time on the hairy numerical robustness issues. But when you don't, well, there's better options with lower complexity and far larger "bang for the buck".
go fekk a demo about it
