btVoxelShape for grid-based world support

[immortius]

I have put together a branch of Bullet with support for a btVoxelShape - an infinite, 3D grid, where each cell can contain a collision shape with different settings (friction, restitution, rolling friction, user pointer). Its collision and ray/sweep algorithms take advantage of the grid structure to determine which cells are involved, and then delegate off to the correct algorithm for each cell's content.

The branch can be found here.

A quick summary of the changes in the branch:

• btCollisionObjectWrapper, LocalRayResult and LocalSweepResult were changed to carry additional information. btCollisionObjectWrapper now holds friction, rollingFriction, restitution and userPointer, to allow per-voxel (grid location) settings. The ray results now carry the collision shape and user pointer of the btCollisionObjectWrapper involved.
• Introduced btVoxelShape. This represents an infinite voxel world. It must be constructed with a btVoxelContentProvider, which provides the information on each voxel (as a btVoxelInfo).

Currently it is assumed that btVoxelShapes are unmoving, centered at (0,0,0) (so the voxel at 0,0,0 extends from -0.5 to 0.5 in each dimension), and infinite. btVoxelShape could be improved to relax these restrictions, which could allow for some interesting developments (voxel vehicles perhaps).

This is a port of my previous voxel integration into JBullet.

A short article on the reason I took this approach over using existing collision structures can be found here.

[d3x0r]

Well this looks interesting

So many questions....

What I would like to have is a btVoxelShape that has different units. The ground 1.0 is fine, but I'd like to have a (for example) 1.3 and a 0.25 type of movable voxel body. How much work to extend to support independant voxel bodies colliding with a fixed voxel terrain?

How about with voxel bodies attached with joints?

----
Thoughts about destructable voxels? I dunno maybe I'm making a mountain out of a mole hill.. but say you have a car that collides with a wall; I'd want the car deflected some, unless the wall gave away completely... with the btDiscreteDynamicsWorld if I get a collision in a partial step, can I update the world, and allow it to continue until the end of it's normal time step?

[immortius]

What I would like to have is a btVoxelShape that has different units. The ground 1.0 is fine, but I'd like to have a (for example) 1.3 and a 0.25 type of movable voxel body. How much work to extend to support independant voxel bodies colliding with a fixed voxel terrain?

The main change would be incorporating the voxel collision objects' transform into the collision calculations (so offset, rotation and scale would be applied in discovering and applying the individual voxel info). Scale would determine the units. A touch of work would also be needed incorporating the bounds of the shape into calculations (currently voxel shapes are considered infinite). This would be needed anyway to support movable voxel objects.

How about with voxel bodies attached with joints?

I cannot think of anything about the voxel support that would prevent support for joints between voxel collision objects and other objects, besides their current lack of support for movement.

Thoughts about destructable voxels? I dunno maybe I'm making a mountain out of a mole hill.. but say you have a car that collides with a wall; I'd want the car deflected some, unless the wall gave away completely... with the btDiscreteDynamicsWorld if I get a collision in a partial step, can I update the world, and allow it to continue until the end of it's normal time step?

There shouldn't be any issues with the voxel world changing mid-step, as long as the voxel provider retrieves voxel information in an atomic fashion (either all the information from the before or after voxel, not a mixture of both). That is the voxel information provided be the voxelProvider should be a snapshot of the current state at the time it is requested, and not a live view.

[immortius]

Some further thoughts:

• There's not scale in a btTransform, so localScaling would probably be the place to hook in the units.
• On further thought, there are likely some performance issues with voxel<->voxel shape collisions. The voxel collision algorithm works by determining the subregion of the voxel world that is needed for calculating the collisions and obtaining just that, so if you have a voxel object moving around inside another voxel object, the full "world" of the inner object would always be obtained and processed each time. At that point a compound shape would perform just as well if not better, for rigid body calculations at least.

Edit: I've committed changes to support localScaling for the voxel shape. It is up to the voxel provider to provide voxels with shapes that correspond to the desired scale. i.e. if you set the localScaling to (2, 2, 2) then the voxel shape will consider the space between (-1, -1, -1) and (1, 1, 1) to be a single voxel, but it does not scale the shape provided for that voxel.

[d3x0r]

The engine I'm basing my ideas from is BlackVoxel (www.blackvoxel.com)
They track their world in sectors of (16x64x16) (tall boxes where x,z is ground); think I'm going to rescale that to 32x32x32 blocks (still only 15 bits)... but your position in the world is basically first divided by the sector size to get the sector and then the modulus is where in the sector you are.

So to extend their world to support independant floating sections, would just extend a sector to include a transform (or maybe wrap an array of sectors so I can have parts larger than a single sector).... I Like the idea of what space engineers has done with large and small ship frames.

There is like 0 physics support in blackvoxel, other than typically a player is 1x2x1 voxels so it's easy to see if you're colliding with something else. When I changed the world scaling to be like 0.25 the size it was, the the player was effectively 4x8x4 and since they were only testing the corner points, it was possible to go through a beam of voxels in front of you... so I set that aside for future consideration.

in the case of 32x32x32 the worst case of shapes in a volume is every other cube and turns out to be like 63488 ( ( 15 + 16 ) * 16 ) * 32 ... ( every other voxel, with an offset every other voxel in the next row times 16 times across a layer and 32 layers)

the best - stupid case - would be 1024 (32x32 cubes on top exposed, not building shapes for any voxels that are surrounded by other voxles... that have at least 1 face exposed). Could then join these in groups so make a single 1 voxel thick 32x32 voxel wide/long shape for the top. (this is a rare case though only useful for initial conditions)... and only useful for the areas around the origin (in black voxel as you leave the starting area they have various terrain biomes; one for instance is a forest of VERY large trees... which are probably 4096 shapes around a trunc through a sector (4 * 1024 for each side)... less than that 'cause it's round but... ).

----------
So I dunno maybe it is better to just do 1 rigid body for each sector and enable/disable them as they are required (say only 9 active at a time... or get really tricky and use only 4 at a time....) though that only solves collisions around the player... for each mobile sector they'd have their own 4 sectors plus all other mobile volumes.