AABB BVH

[Mitox]

Hello (I'm doing a new post since the previous one was about another question)

1/ Is there any way to get/set the deepness of a AABB BVH computed ?

I've got complex environments containing "some" thousands, and all my intersection tests are going to be inside the AABB, so without a hierarchy bullet is going to test all the triangles
They are quite regularly disposed in the environment

with about 40 000 triangles (and even with 1 200 000) I tried this :

Code: Select all

m_indexVertexArrays = new btTriangleIndexVertexArray(totalTriangles,
		this->gIndices,
		indexStride,
		totalVerts,(btScalar*) &this->gVertices[0].x(),vertStride);

bool useQuantizedAabbCompression = true;
trimeshShape  = new btBvhTriangleMeshShape(m_indexVertexArrays,useQuantizedAabbCompression);
m_collisionShapes.push_back(trimeshShape);

btOptimizedBvh * myBVH = trimeshShape->getOptimizedBvh();
QuantizedNodeArray nodearray = myBVH->getLeafNodeArray();
cout << "nodearray size :" << nodearray.size() << endl;

2/ which indicates me the nodearray's size is 0, am I missing something ?

3/ I'm doing rayTest on this, so with about 10 000 000 of rayTest on 12 000 triangles it takes me about 27 seconds, while my method take about 4 seconds.. so I think the rayTest is done on each triangle, is there some code I should look at ? or write it myself ?

Thanks,

Thomas

[Erwin Coumans]

1/ Is there any way to get/set the deepness of a AABB BVH computed ?

If you enable the define DEBUG_TREE_BUILDING inside btQuantizedBvh.cpp, then gMaxStackDepth will show the maximum tree depth.

2/ which indicates me the nodearray's size is 0, am I missing something ?

You might want to try getQuantizedNodeArray instead.

3/ I'm doing rayTest on this, so with about 10 000 000 of rayTest on 12 000 triangles it takes me about 27 seconds, while my method take about 4 seconds.. so I think the rayTest is done on each triangle, is there some code I should look at ? or write it myself ?

It is unlikely that each triangle is traversed. Instead of using btCollisionWorld::rayTest, you can directly call btBvhTriangleMeshShape::performRaycast and test if the callback is really called for each triangle. Bullet ray cast implementation isn't extremely optimized and uses callbacks to keep the framework generic. Begin generic costs some performance, so it would be easy to create a faster implementation. Can you share your benchmark (including your faster implementation) so we can help optimizing?

Thanks a lot for the feedback,
Erwin

[Mitox]

It is unlikely that each triangle is traversed

You are totally right, I'm plotting the results of the rayTest in function of the number of triangle and they don't increase linearly.

Can you share your benchmark (including your faster implementation) so we can help optimizing?

Unfortunately -for the moment- I can't, it's still unpublished research.
I'm not sure my work will help your raycast implementation, I'm doing particle continous collision detection so I use your raycast implementation as a segment/triangles tests.
But if you are interested in it, I can warn you when it's published.

I easily "optimized" by removing the "world" test and removing the -g option at the compilation : I gained approximately one second on a million of segment/triangle tests, I'll look if I see better optimizations as soon as I can.

1/ Is there some optimization you think of ?

2/ Is there a way to use more than 2097152 triangles with a btQuantizedBvh ?
(cf. #define MAX_NUM_PARTS_IN_BITS 10)
=> I'm trying to show the logarithm increasing of complexity of the AABB BVH, so the more triangle I use, the more it will appear

Thanks a lot for your answers,

Thomas

[Erwin Coumans]

1/ Is there some optimization you think of ?

• There are a few traversal methods, check the constructor of btQuantizedBvh, and change the m_traversalMode from TRAVERSAL_STACKLESS into TRAVERSAL_STACKLESS_CACHE_FRIENDLY or TRAVERSAL_RECURSIVE and see if that helps.
• Do you enable quantization when creating the btBvhTriangleMeshShape? It should be faster, but please double check how the feature impacts performance by disabling it.
• You could also modify/re-implement the AABB traversal implementation and get rid of the virtual method to call btNodeOverlapCallback.
• Try to use batch raycasts, traversing the AABB tree for multiple rays (reducing the callback overhead). See Demos\ConcaveRaycastDemo\ConcaveRaycastDemo.cpp for some sample implementation (enable #define BATCH_RAYCASTER

2/ Is there a way to use more than 2097152 triangles with a btQuantizedBvh ?
(cf. #define MAX_NUM_PARTS_IN_BITS 10)

Just change this define to #define MAX_NUM_PARTS_IN_BITS 1, to allocate more bits for the triangle indices (as you probably don't partition the mesh in parts).

Hope this helps,
Erwin