Voxels collision

Post Reply
anton.nagornyi
Posts: 5
Joined: Wed Sep 21, 2016 6:42 am

Voxels collision

Post by anton.nagornyi » Wed Sep 21, 2016 7:02 am

I have implemented procedural mesh generation based on the marching cubes algorythm. This is done in Unity. To make it work with PhysX I have also created mesh colliders for that generated mesh. The problem I have is that cooking mesh colliders in PhysX takes a lot of time. I don't khow how faster is Bullet with that but I think I don't need mesh colliders at all. I already have voxels data that can be used to detect collisions. I am reading Bullet's documentation and I think it is possible to create custom collision shape for my voxel geometry. If I get it right I can inherite btCollisionShape to introduce my VoxelCollision, but I still don't understand how should I properly register it within Bullet's engine. Please provide me with a guide of how to create a custom collision shape that could be properly used in the Bullet's simulation. Thanks

Dirk Gregorius
Posts: 874
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Voxels collision

Post by Dirk Gregorius » Thu Sep 22, 2016 3:07 am

I think mesh colliders are the right way to do this. How many voxels did you batch into one mesh? A good size might be something around 12x12 voxels. Is PhysX cooking really so slow that it cannot do this on the fly? This can be done also in parallel.

User avatar
drleviathan
Posts: 486
Joined: Tue Sep 30, 2014 6:03 pm
Location: San Francisco

Re: Voxels collision

Post by drleviathan » Thu Sep 22, 2016 4:01 am

Voxels are made of boxes, therefore it would be very easy to make a btCompoundShape with boxes as the subshapes. You could coalesce adjacent boxes to build an optimized set. You could even share any btBoxShape's that happen to appear more than once in the optimized set. This would be much easier than implementing a new shape type and filling out the "algorithm" matrix between your new shape and the others.

anton.nagornyi
Posts: 5
Joined: Wed Sep 21, 2016 6:42 am

Re: Voxels collision

Post by anton.nagornyi » Thu Sep 22, 2016 5:28 am

Dirk Gregorius wrote:I think mesh colliders are the right way to do this. How many voxels did you batch into one mesh? A good size might be something around 12x12 voxels. Is PhysX cooking really so slow that it cannot do this on the fly? This can be done also in parallel.
I have very detailed environment. My chunk is 64x64x64 voxels. When mesh extraction is complete there are huge number of triangles even after decimation algorythm. So it is really takes a lot of time to cook such mesh collider. When saying a lot of time I mean updating all my chunks in a frame can take up to 200ms which is not acceptable ). As I am working with unity I do not have access to the built in PhysX directly, so I do not know how to update colliders in parallel. Is there such a way?

anton.nagornyi
Posts: 5
Joined: Wed Sep 21, 2016 6:42 am

Re: Voxels collision

Post by anton.nagornyi » Thu Sep 22, 2016 5:45 am

drleviathan wrote:Voxels are made of boxes, therefore it would be very easy to make a btCompoundShape with boxes as the subshapes. You could coalesce adjacent boxes to build an optimized set. You could even share any btBoxShape's that happen to appear more than once in the optimized set. This would be much easier than implementing a new shape type and filling out the "algorithm" matrix between your new shape and the others.
Yes it could work. But I concern about the number of boxes I need to compound. To optimize it I need to do some additional computations. The advantages of this approach are:
1. Relatively easy way of creating my geometry collider

Disadvantages:

1. Optimizing number of compound boxes can take some additional time
2. I still would have just collision "surface". If something goes fast it could go through it (in physX I need to enable continuos collision detection to prevent such behaviour).
3. I think uploading information about my compound collider to the bullet engine also will take some time. (Like cooking of mesh collisders in PhysX)

If I have my own collision shape I can resolve collisions based on voxels data. In every moment of time I know everything about every single point of space. I always can tell if moving entity is inside or outside of geometry and it is also not a big deal to get triangles in a collision point to calculate normals. I gues creation of custom collision shape is not a trivial task, but if it is done I would have greate performance boost and reliable collisions without CCT enabled.

Dirk Gregorius
Posts: 874
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Voxels collision

Post by Dirk Gregorius » Thu Sep 22, 2016 5:13 pm

I would not use compounds of boxes. You will get a lot of ghost collisions with internal edges which will be difficult to handle. It might be also very inefficient.

The slow cooking times are indeed a problem. When I experimented with this I wrote a fast mesh compiler to handle this. The voxel mesh are generally well behaved and you can skip SAH and the like in the mesh builder. I also delayed rebuilds over several frames rebuilding meshes around the player first.

Can't you change you chunk size? I would try different chunk sizes if the 64x64x64 isn't hardcoded too deep into your voxel engine. PhysX is open source, so you can look at their mesh cooker and write your own more lightweight version. I know this sucks, but in the end this should be more or less just a BVH.

LEgregius
Posts: 26
Joined: Tue Oct 14, 2008 1:34 am

Re: Voxels collision

Post by LEgregius » Thu Sep 22, 2016 7:49 pm

We did an Openvdb integration to bullet for a project. It uses an abstraction layer, so it probably wouldn't directly help you, but what we ended up doing to collide was generate triangles for outer edges of the voxel data, and made it work as a custom concave shape.

You can find the code for it here.

https://svn.code.sf.net/p/delta3d/code/ ... geometry.h

anton.nagornyi
Posts: 5
Joined: Wed Sep 21, 2016 6:42 am

Re: Voxels collision

Post by anton.nagornyi » Thu Sep 22, 2016 8:45 pm

Dirk Gregorius wrote:I would not use compounds of boxes. You will get a lot of ghost collisions with internal edges which will be difficult to handle. It might be also very inefficient.

The slow cooking times are indeed a problem. When I experimented with this I wrote a fast mesh compiler to handle this. The voxel mesh are generally well behaved and you can skip SAH and the like in the mesh builder. I also delayed rebuilds over several frames rebuilding meshes around the player first.

Can't you change you chunk size? I would try different chunk sizes if the 64x64x64 isn't hardcoded too deep into your voxel engine. PhysX is open source, so you can look at their mesh cooker and write your own more lightweight version. I know this sucks, but in the end this should be more or less just a BVH.
Well generating mesh is done pretty fast. The bottleneck is in mesh colliders update. Thanks for an idea to implement lightweight cooker, I will do some research on it.

anton.nagornyi
Posts: 5
Joined: Wed Sep 21, 2016 6:42 am

Re: Voxels collision

Post by anton.nagornyi » Thu Sep 22, 2016 8:55 pm

LEgregius wrote:We did an Openvdb integration to bullet for a project. It uses an abstraction layer, so it probably wouldn't directly help you, but what we ended up doing to collide was generate triangles for outer edges of the voxel data, and made it work as a custom concave shape.

You can find the code for it here.

https://svn.code.sf.net/p/delta3d/code/ ... geometry.h
So, you have managed to create custom concave shape inherited from btCompoundShape? I just need an example code how to do that properly ). It would be great to get a link to that source. Thanks

immortius
Posts: 6
Joined: Sat Aug 22, 2015 4:12 am

Re: Voxels collision

Post by immortius » Mon Oct 03, 2016 12:58 am

http://bulletphysics.org/Bullet/phpBB3/ ... hp?t=10769

This was my approach to solving the issue of voxel collisions. It relies on the assumption that a voxel object is a 3D grid, each cell of which can contain a collision shape. It uses the grid to determine which cells are involved in a collision or trace, and requests the shape they contain dynamically, so updates are immediate and require no mesh rebuilds.

User avatar
Erwin Coumans
Site Admin
Posts: 4160
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Voxels collision

Post by Erwin Coumans » Thu Oct 13, 2016 2:52 pm

From performance and reliability perspective, it is likely fastest to add each voxel as a btBoxShape directly into the world/broadphase. Voxels/btBoxShape have volume, which is better for collision detection and penetration recovery than flat triangles in Bullet. Make sure to use the btDbvtBroadphase acceleration structure. Can you try that first and let us know?

If you add all boxes to a btCompoundShape the performance should be reasonably ok, as it will also create a local btDbvtBroadphase acceleration structure. It is still possible that the performance is worse, because it will add a single gigantic AABB entry for the large btCompoundShape into the broadphase.

Once the performance is ok, we can look in a potential problem that Dirk mentioned: collisions against "internal" box-edges.
It may not necessarily become a problem, but if it is, those internal box-edges are something interesting to sort out.

Post Reply