Hi all, I've got a nice and fast leaf based (not sold) BSP collision working. I'm doing it the standard way of splitting triangles at the partition and sending the resulting triangles down the front or back. As I say, this all works fine. The problem is this results in quite a large tree (even choosing heuristics which results in few splits). A 7000 tri level results in a 300K tree. In order to reduce this I wondered if I can, rather than splitting the triangles, send the tri that straddles the partition, down both sides of the node. This would mean I don't need to create verts/tris as the nodes could reference the orginal geometry as this wont change. Theoretically this would get my tree down to about 34K. I would have to check for duplicate references in my collision code, but this is simple housekeeping. I was wondering if this is a valid technique? Can I just dump the tri down both subspaces and forget about it? I'm thinking there may be a case where my GetGetSplitter routine will have invalid NumSplits due to splitting a tri is not actually in its subspace (it would have been clipped off using the split algorithm previously). This would also allow me to be more agressive with the GetGetSplitter() routine, as no adittional polys are being created, just referenced. Any help would be appreciated (apart from the obvious "Use a xxxtree instead"! ) Many thanks, Steve

Quote:Original post by stevenhaggerty
I was wondering if this is a valid technique?

Yes but it's a disadvantage because now you can not terminate at a leaf.

Quote:Original post by stevenhaggerty
Can I just dump the tri down both subspaces and forget about it?

Yes but now you have decide which branch will be the shortest path (therefore spend less time traversing) or stop at the first found reference which could end-up being the longest path.

Quote:Original post by stevenhaggerty
Any help would be appreciated (apart from the obvious "Use a xxxtree instead"! )

I'm afraid to say that if you using this for collision detection with triangle meshes then you would be much better off with bounding volume hierarchies (BVH), no one uses BSP trees for these any more (if ever) there is no need for spatial ordering in this case of CD.

If you where dealing with concave polygon meshes then yes BSP trees can be quite useful here because they can decompose concave polygons into convex regions/parts which is more easier and efficent for intersections than for concave polygons.

BVHs are quite easy to build and they don't have the issues that spatial partitioning strucutres have except for the fact that they lack spatial ordering because they don't divide space up they divide geometry up but for CD of convex polygon/triangle meshes this information isn't needed.

BVHs are much more simple to update as well so they are well suited for dynamic objects or deformable objects.

[Edited by - snk_kid on May 12, 2007 7:02:35 AM]

Thanks for the prompt reply.

I've come up with a better way of reducing the memory of the BSP without complicating the build process too much. Build and split as per normal (creates additional faces, I call "build faces"). But when it comes to emitting the leaves, emit the index of the original face (stored in the build face). Therefore the heuristics of the GetGetSplitter works correctly and I need no additional faces/verts etc.

I'll most certainly look into BVH's. I'll probably implement a AABB BVH as a hobby project, but as I'm working on commercial titles, with commertial time pressures I can't just dump the BSP compiler.

Also, I have to disagree with your when you said BSP's aren't used for collision any more! I know several game developers that use them. Though I
agree the spacial ordering is now largely irrelevent and I'd probably got for an AABB BVH if I had time to "Redo from start"!

Many thanks again,

Steve.

Quote:Original post by stevenhaggerty
Also, I have to disagree with your when you said BSP's aren't used for collision any more! I know several game developers that use them.

I never meant to say they aren't used at all, it largely depends on the context, what kind of intersection tests are we trying to speed up here, how accurate does the results need to be, what kind of BSP tree are we're talking about, are the splitting planes polygon or axis-aligned BSP trees, are we subdividing down to the object level (leaves contain whole objects) or subdividing down to polygon level (one large mesh being subdivided) or is it both, we need to be carefully what we are talking about here.

I assumed you're trying to accelerate intersection routines with large triangle meshs (a single polygon-aligned BSP tree for a single large triangle mesh) and you need to know the exact triangle(s) which have or about to collide/intersect with something. If this is the case i'll tell you that almost all modern advance physics/collision detection libraries do not use spatial partitioning structures (like all forms of BSP trees, octrees, etc, etc) for this they use BVHs, where the bounding volume type is typically AABBs, OBBs and k-DOPs (a generalization of AABBs, a 6-DOP is an AABB).

It shouldn't be to diffcult to turn your tree into a BVH because you can pretty much reuse the same splitting strategy for the BVH construction with very minor modifications.

The only changes are:

• You don't store the splitting plane any more, you just find a good splitting plane, divide up the list into two and then calculate the extents of the two list subsets, you do not split triangles which straddle the splitting plane just pick a reasonable side to put them in. The volumes will most likely overlap but this isn't any problem since we don't care about spatial ordering for CD.



• All nodes have bounding volumes, each level is nesting of the parent's BV.



• For CD of static tri-meshes you typically wont to have a single triangle in a leaf node. For CD of deformable/dynamic tri-meshes you might want to store a slightly bigger size of leaves, say around 40 triangles but not to big.



• You can store geometry in both internal/leaf nodes if you want, it will just depend on your requirements.



• If the BV type is AABB then the splitting planes need to be axis-aligned but the splitting position can be at any point.

Somethings to note:

• BVHs can be built, top-down, bottom up or incremental methods so there not restricted to top-down only, i only mentioned the quickest method of changing your BSP tree into a BVH (which is top-down method), it's only a few hours of work if that.



• As with splitting strategies of spatial partitioning structures, depending on which one you choose will determine how balanced your trees will be, it's been known for CD you don't want trees which are totally balanced, it was found that trees which are slightly unbalanced preformed best overall.



• BVHs don't have to be binary trees but binary trees are used most often.

[Edited by - snk_kid on May 14, 2007 5:04:10 AM]