Modifying the contents of a btTriangleMesh

[PolyVox]

Hi, I have Bullet nicely integrated with my project and it is working great, so thanks for that. However, I provide fully dynamic worlds (it's a voxel engine) and I am trying to improve the rate at which I can get the modified geometry into Bullet.

The world is divided into a number of fixed size regions. Each time the geometry in a region changes I am creating a new btTriangleMesh, passing that into a new btBvhTriangleMeshShape, and then creating a new (static) rigid body. This is all happening through OgreBullet, but hopefully that doesn't matter.

Ideally, I would just like to modify the data in btTriangleMesh without having to add/remove and new/delete any object. The AABB will be fixed (it's the size of the region) so I was hoping this would be possible but don't see a way to do it through the btTriangleMesh interface.

In a nutshell, my question is how many of the objects can just be updated, and how many do I need to create and destroy each time?

Thanks for any help!

[Erwin Coumans]

Do you add and remove triangles/vertices, or do you only move existing vertices? Bullet has a refit and partial refit for the AABB tree, see ConcaveDemo.

There are several options, but it really depends on the details of your deformation method.

Bullet 2.68 will have deformable objects with collision detection, that could also be useful for certain rigid body deformations.
Hope this helps,
Erwin

[PolyVox]

Thanks for the reply, I'll explain a bit more how it works. I represent my world with a 256x256x256 volume where each voxel in the volume is either 'filled' or 'empty'. This volume is actually broken down into several subvolumes which 32x32x32 voxels. Initially I run the Marching Cubes algorithm on each subvolume and upload the data both to Ogre and to Bullet.

Now, when the user modifies part of the volume I rerun the Marching Cubes algorithm on the subvolumes which have changed. I would like Bullet to replace the old mesh with the new one with as little overhead as possible. It is a completely new mesh and there is no guarantee that the number of vertices and triangles will be the same (it probably won't be), but of course both the old and the new mesh will completly inside the extents of the subvolume (which could therefore be used as the AABB). We're talking something like a few hundred triangles per subvolume, though I may change the size of the subvolume or perform mesh decimation.

Because a picture is worth a thousand words you can see my (GPL) project here:

http://www.ogre3d.org/phpBB2/viewtopic.php?t=27394

Thanks!

[Erwin Coumans]

That looks pretty cool. How many individual voxels/cells are there in total?

How many triangles are approximately in each cell?

I recommend following approach:
First make it work (slow), and then add some additional acceleration structures to make it fast, when needed.

So please create a separate mesh object for each cell, and simply add them all as separate objects. This means, each cell has its own broadphase entry. When things deform, simply destroy that object, and create a new one. You can build a btBvhTriangleMeshShape for each voxel to start with.

Once this is all up and running, we can worry about performance. Don't worry, there are plenty of optimizations available, but it would be good to first have something up and running.

How does that sound?
Thanks,
Erwin

[Erwin Coumans]

Secondly, I highly recommend using the Zlib license, instead of (L)GPL. It is much better for game developers in general.

(L)GPL is incompatible with development on most game consoles: the non disclosure agreement (NDA) is in conflict with (L)GPL.

And once people start contributing to your project, you cannot easily change the license, unless you get permission from each contributor. This can become difficult, especially when people pass away etc.

Do you consider changing the license?
Thanks,
Erwin

[chunky]

(L)GPL is incompatible with development on most game consoles: the non disclosure agreement (NDA) is in conflict with (L)GPL.

Plus there's the practical problem with it: (L)GPL demands that an end user can recompile the source and run it themselves, that's the core point. Which end users can't do on consoles.

Ryan had this problem with PhysFS and talked about it here

I'll throw in that I quite like ZLib aswell, FWIW.

Gary (-;

[PolyVox]

Thanks for the replies, let's first look at the technical stuff:

How many individual voxels/cells are there in total?

The whole volume is 256x256x256 voxels, though I hope to increase this in the future. The volume is broken into regions which are each 32x32x32 voxels but this could be adjusted.

How many triangles are approximately in each cell?

I think it varies between about 0 and 5000. But I fully expect to implement mesh decimation in the future and use a lower resolution mesh for physics than for rendering.

The whole volume has something like 250,000 triangles in it.

I recommend following approach:
First make it work (slow), and then add some additional acceleration structures to make it fast, when needed.

So please create a separate mesh object for each cell, and simply add them all as separate objects. This means, each cell has its own broadphase entry. When things deform, simply destroy that object, and create a new one. You can build a btBvhTriangleMeshShape for each voxel to start with.

Ok, actually this is the stage I was already at. It was working but it was making use of OgreBullet which was obscuring what was going on. I spent this evening removing OgreBullet and calling Bullet directly. It's now a lot clearer to me what I need to do.

Once this is all up and running, we can worry about performance. Don't worry, there are plenty of optimizations available, but it would be good to first have something up and running.

Ok, so I was creating at btTriangleMesh, btBvhTriangleMeshShape, and btRigidBody each time a region changed. I've now eliminated the re-creation of the btRigidBody as it seems I can simply call btRigidBody->setCollisionShape().

However, I think a better way to do it is to leave all three objects in place and directly modify the mesh data through
btTriangleMesh->getLockedVertexIndexBase(). Does that sound like it should work? None of the AABB's etc should need to be recalculated.

As for the question of licensing, my reason for choosing the GPL was actually to restrict commercial use. This could allow me to charge for licensing exemptions, or create some other type of dual licensing scheme in the future. But at this point I have no idea whether there will be any commercial interest, so it's really just a hobby project for the time being.

[Erwin Coumans]

The whole volume is 256x256x256 voxels, though I hope to increase this in the future. The volume is broken into regions which are each 32x32x32 voxels but this could be adjusted.

How many of those voxels are actually filled with mesh data? Are you saying you create 256x256x256 rigid bodies?

Ok, so I was creating at btTriangleMesh, btBvhTriangleMeshShape, and btRigidBody each time a region changed. I've now eliminated the re-creation of the btRigidBody as it seems I can simply call btRigidBody->setCollisionShape().

You can avoid destroying/creating a new btRigidBody, but it would be best to remove it from the dynamics world before calling the 'setCollisionShape'. Then add it back to the dynamics world, so that the data structures are properly updated.

However, I think a better way to do it is to leave all three objects in place and directly modify the mesh data through
btTriangleMesh->getLockedVertexIndexBase(). Does that sound like it should work? None of the AABB's etc should need to be recalculated.

Does everything work already, but slow? This sounds like an optimization, which we should defer until things work.
If you only move some vertices, check out Bullet/Demos/ConcaveDemo/ConcavePhysicsDemo.cpp how to do this.

Code: Select all

trimeshShape->partialRefitTree(aabbMin,aabbMax);
//clear all contact points involving mesh proxy. Note: this is a slow/unoptimized operation.
m_dynamicsWorld->getBroadphase()->getOverlappingPairCache()->cleanProxyFromPairs(staticBody->getBroadphaseHandle(),getDynamicsWorld()->getDispatcher());

If you add/remove vertices you need to rebuild some internal structures of the btBvhTriangleMeshShape. Alternatively (and more interesting) you can create your custom concave shape, like we did for the btSoftBody and GIMPACT. But we should not discuss this, until you have things working.

As for the question of licensing, my reason for choosing the GPL was actually to restrict commercial use. This could allow me to charge for licensing exemptions, or create some other type of dual licensing scheme in the future. But at this point I have no idea whether there will be any commercial interest, so it's really just a hobby project for the time being.

I highly recommend making it available under the ZLib license. If your open source project catches on, you are likely to make more money (and add job stability) with a potential job offer or consultancy, rather then having your middleware business trying to license tech. By the way, Stan Melax might consider integrating some of his deforming technology into Bullet (http://www.melax.com/). That integration work should be very similar to yours.

Thanks,
Erwin

[PolyVox]

The whole volume is 256x256x256 voxels, though I hope to increase this in the future. The volume is broken into regions which are each 32x32x32 voxels but this could be adjusted.

How many of those voxels are actually filled with mesh data? Are you saying you create 256x256x256 rigid bodies?

No, I create one RigidBody for each region (which is 32x32x32 voxels). That's means there are 8x8x8=512 rigid bodies. Probably 5% of the voxels contain mesh data. Something like 1000 triangles per region and RigidBody.

Does everything work already, but slow?

Yes, everything works. Let me first show the the slow but working version of the code. Note that by slow I mean that updating the mesh is slow - the actual simulation runs pretty fast. Anytime a voxel changes I run the following code to update the mesh:

Code: Select all

//Create a new btTriangleMesh and copy in the data from my own 'IndexedSurfacePatch' (basically a mesh)
mTriMesh = new btTriangleMesh();
copyISPToTriangleMesh(isp, mTriMesh);

//Create a new btBvhTriangleMeshShape from the btTriangleMesh
const btVector3 minAabb(0,0,0);
const btVector3 maxAabb(PolyVox::POLYVOX_REGION_SIDE_LENGTH,PolyVox::POLYVOX_REGION_SIDE_LENGTH,PolyVox::POLYVOX_REGION_SIDE_LENGTH);
const bool useQuantizedAABB = true;
mShape = new btBvhTriangleMeshShape(mTriMesh, useQuantizedAABB, minAabb, maxAabb);

//Create a new btRigidBody
mBody = new btRigidBody(0.0, 0, mShape);
mBody->setRestitution(gDynamicBodyRestitution);
mBody->setFriction(gDynamicBodyFriction);
mBody->getWorldTransform().setOrigin(btVector3(pos.x, pos.y, pos.z));
mBody->getWorldTransform().setRotation(btQuaternion(0, 0, 0, 1));
getBulletDynamicsWorld()->addRigidBody(mBody);

That code is roughly what I had when I posted my initial message a few days ago (except I was going through OgreBullet). Over the last few days I have discovered I can avoid recreating both the btRigidBody and the btTriangleMesh, but I'm still having to recreate the btBvhTriangleMeshShape. My latest code look as follows:

Code: Select all

//If the mesh doesn't exist yet we create it, otherwise we update it.
if(mTriMesh == 0)
{
	mTriMesh = new btTriangleMesh();
	copyISPToTriangleMesh(isp, mTriMesh);   
}
else
{
	updateTriangleMeshWithNewISP(isp, mTriMesh); //uses btTriangleMesh::getLockedVertexIndexBase()
}

//Same as before, I haven't got around recreating this yet.
const btVector3 minAabb(0,0,0);
const btVector3 maxAabb(PolyVox::POLYVOX_REGION_SIDE_LENGTH,PolyVox::POLYVOX_REGION_SIDE_LENGTH,PolyVox::POLYVOX_REGION_SIDE_LENGTH);
const bool useQuantizedAABB = true;
mShape = new btBvhTriangleMeshShape(mTriMesh, useQuantizedAABB, minAabb, maxAabb);
	
//If the body doesn't exist then create it, otherwise just update the collision shape
if(mBody == 0)
{
	mBody = new btRigidBody(0.0, 0, mShape);
	mBody->setRestitution(gDynamicBodyRestitution);
	mBody->setFriction(gDynamicBodyFriction);
	mBody->getWorldTransform().setOrigin(btVector3(pos.x, pos.y, pos.z));
	mBody->getWorldTransform().setRotation(btQuaternion(0, 0, 0, 1));
	getBulletDynamicsWorld()->addRigidBody(mBody);
}
else
{
	mBody->setCollisionShape(mShape);
}

The above code also works, but I'm still recreating the btBvhTriangleMeshShape each time. To avoid that I tried the following but it crashed:

Code: Select all

const btVector3 minAabb(0,0,0);
const btVector3 maxAabb(PolyVox::POLYVOX_REGION_SIDE_LENGTH,PolyVox::POLYVOX_REGION_SIDE_LENGTH,PolyVox::POLYVOX_REGION_SIDE_LENGTH);
const bool useQuantizedAABB = true;
if(mShape == 0)
{
	mShape = new btBvhTriangleMeshShape(mTriMesh, useQuantizedAABB, minAabb, maxAabb);
}
else
{
	mShape->m_meshInterface = mTriMesh; //I hacked the bullet source to make this public...
	mShape->partialRefitTree(minAabb, maxAabb); //With or without this line makes no difference. I don't think it should be needed.
}

So basically, any advice you have about avoiding the recreation of the btBvhTriangleMeshShape would be appreciated

I highly recommend making it available under the ZLib license. If your open source project catches on, you are likely to make more money (and add job stability) with a potential job offer or consultancy, rather then having your middleware business trying to license tech.

I will give this some serious thought and maybe post on GameDev. I don't really have the time, business experience, or money to start licensing the tech, and using ZLib would allow more widespread knowledge of my project. But it's a one-way decision, so I have to think carefully

Anyway, thanks for your help so far!