Real-time voronoi fracture and shatter for Bullet Physics

[RBD]

@Flix: yes, to enable shatter of any (indeed non-convex, but closed) triangle meshes using Bullet Physics. Currently in Blender I'm using its boolean intersections; works quite well (and preserves the uvs), but it does get slow with high poly counts. In Blender I am using HACD along with voronoi fracture, but after the boolean intersections: for convex decomposition of non-convex voronoi shards.

[Flix]

In Blender I am using HACD along with voronoi fracture, but after the boolean intersections: for convex decomposition of non-convex voronoi shards.

Thanks for the info (I was wondering how you made your videos...).

I've made some extensions to your code to support generic polyhedral convex shapes in Bullet. In case somebody is interested:

These are the modifications I've made to extend the algorithm to generic convex polyhedral shapes (but use them at your own risk ).

Well, first of all I do the whole stuff in "Local Space" (but I think it should be possible and maybe faster to do all in world space: I just needed to simplify the code a bit): so I didn't use:
const btQuaternion& bbq
const btVector3& bbt
as arguments.
I replaced them with a
const btTransform& T
that I only use when the shard is ready: shardTransform = T * shardTransform;

Then I replaced the arguments:
const btVector3& bbmin, const btVector3& bbmax
with:
const btAlignedObjectArray<btVector3>& originalPlanes
that represent the plane equations of the original convex shape to be shattered; more on this later (*).

Now I just needed to shorten the code a bit like this:
Replaced this code:

Code: Select all

btVector3 icp = quatRotate(bbiq, curVoronoiPoint - bbt);	// replace this line only if you use local space for points as I did
//=====================================================
rbb = icp - bbmax;
nrbb = bbmin - icp;
planes.resize(6);
planes[0] = bbvx; planes[0][3] = rbb.x();
planes[1] = bbvy; planes[1][3] = rbb.y();
planes[2] = bbvz; planes[2][3] = rbb.z();
planes[3] = -bbvx; planes[3][3] = nrbb.x();
planes[4] = -bbvy; planes[4][3] = nrbb.y();
planes[5] = -bbvz; planes[5][3] = nrbb.z();
maxDistance = rbb.length();
distance = nrbb.length();
if (maxDistance < distance)
	maxDistance = distance;
//======================================================
// Note that bbvx,bbvy,bbvz,rbb,nrbb (and bbmin,bbmax) are not used anymore

With:

Code: Select all

// This is because I use both 'points' and 'originalPlanes' in "Local Space" (I apply a transform later)
const btVector3& icp = curVoronoiPoint;	// Untransformed
// But probably the "transformed code"  works with 'points' in 'Global Space' and 'originalPlanes' still in "Local Space" (like in the original method AFAIK). 
//=======================================================
maxDistance = 0;	// Needed ???
planes.copyFromArray(originalPlanes);
for (int i=0;i<planes.size();i++)	{
	btVector3& p(planes[i]);
	distance = -p[3] - p.dot(icp);
	p[3] = -distance;
	if (maxDistance < distance) maxDistance = distance;
}
//=======================================================

(*) OK now we just need to extract the "originalPlanes" from a convex shape.
Luckily for us, in the case of btPolyhedralConvexShapes (that AFAIK include btBoxShape and btConvexHullShape, but don't include btSphereShape,btCylinderShape,etc.), Bullet can calculate these planes for us. Here's how to do it:
1) Call the method btPolyhedralConvexShape::initializePolyhedralFeatures() (although this has probably some side effect on the collision detection behavior of the shape...).
2) Retrieve the btConvexPolyhedron from the shape (see btPolyhedralConvexShape.h and btConvexPolyhedron.h and things will appear clear soon).
3) Retrieve the planes (4 btscalars) of each face and put them in the 'originalPlane' array (btVector3 can contain 4 btScalars: the 4th value can be set like this: originalPlane[3] = value).
Now it should work (well, I've only tried it on a box shape and a pyramidal convex hull so far).
The main drawback is that many random points in the shape local aabb will be outside the convex shape, but this can't be avoided (anyway these points will be automatically excluded). And please remember that the points I used are in "Local Space" now.

@ R&D: I'm starting thinking that probably you've deliberately released only the part of the code relative to "cuboids"... if this is the case I feel terribly sorry (I should have asked you before posting this...).

[RBD]

These are the modifications I've made to extend the algorithm to generic convex polyhedral shapes

The algorithm was already for convex polys… no problem, have fun with it.
The demo code for cuboid / bounding box was intended to keep it simple and fast (and generic, for use with boolean ops in other software).

OK now we just need to extract the "originalPlanes" from a convex shape.[...]

BTW, Bullet Physics has a simple utility function to retrieve plane equations: btGeometryUtil::getPlaneEquationsFromVertices(vertices, planes)

[RBD]

Note: Source code update on first post...

Flix, you made me think about this, and I should indeed have included the original code for convex hull shatter (as per algorithm). It's not at all that I didn't want people to have it ; I was just thinking the optimized (I thought much faster, but maybe not?) generic cuboid / bounding box one was preferable. But you are right that it could be useful. I have updated the demo source code to included a voronoiConvexHullShatter function (copied from the other so that differences would be clear) for anyone who wants it. Thank you for pointing this out Flix, and sorry for making you work on it.

You did also make me question the initial value of maxDistance… I haven't really thought about it that hard, but I don't think it did make sense, so I cleared it for now. I think it should instead be that the point itself be considered whether it is too far outside? (I didn't add that yet, it may indeed not be needed).

Thanks for the info (I was wondering how you made your videos...).

Sorry, I missed this earlier... to clarify: I'm pretty sure HACD was not used on any of the voronoi shattered shards in those demos. I was just mentionning that my tools in Blender do optionally call HACD on (post boolean) non-convex shards (when there are some).

[Flix]

Wow, thanks for your new update R&D !

It's not at all that I didn't want people to have it ; I was just thinking the optimized (much faster) generic cuboid / bounding box one was preferable.

Feelin' much better now

BTW, Bullet Physics has a simple utility function to retrieve plane equations: btGeometryUtil::getPlaneEquationsFromVertices(vertices, planes)

Thanks for pointing it out, this is much faster, but I don't know if it merges coplanar planes like in initializePolyhedralFeatures(), and having a small number of planes should make the algorithm a bit faster (if the call to initializePolyhedralFeatures() is made once at init time).

PS. about closed concave meshes, I've found some articles about using a "tetralized" version of the input mesh for extracting the clipped Voronoi diagram together with other material about it (see here in the "publication" section:https://sites.google.com/site/yandongming/).
Anyway I'm not sure if they can be of interest in your case (it's not a fast convex hull to non-convex triangle mesh intersection routine), but the idea of starting with tetra meshes seems interesting...

Thanks again .

[RBD]

I don't know if it merges coplanar planes like in initializePolyhedralFeatures()

getPlaneEquationsFromVertices() does not care about the faces of a mesh, only the outside most vertices, and it will not add two planes with the same equation, so I think that is not a problem.

[Flix]

getPlaneEquationsFromVertices() does not care about the faces of a mesh, only the outside most vertices, and it will not add two planes with the same equation, so I think that is not a problem.

Ok, good to know. Thanks again.

[RBD]

For fun tried calculating plane equations using convexHullComputer instead of getPlaneEquationsFromVertices and it is significantly faster for large meshes... updated source on first post again (take your pick). ...always a better/faster way.

[ahmedismaiel]

great demo ,i was wondering what is the best way to distribute the resistance to fracturing (ex. the center of the object is more resistant to fracturing than the outer pieces unless you add more force to it ) .i'm not sure what the technical term to start learning how to do it.
the second question i have is how can i make the fractured structure (ex. a wall) stand still on a plane or a terrain without falling until another object hits it ?

[RBD]

@ahmedismaiel: the simplest: have a btBoxShape in your scene, upon impact (collision) by a projectile spray voronoi points from the projectile in its velocity vector direction, then generate voronoi shards and delete the original btBoxShape, all in real-time.
If you would like to pre-fracture and then break apart compounded voronoi shards based on collision impacts have a look at Bullet Physics' included FractureDemo.

[Erwin Coumans]

This is very cool work, thanks for sharing!

We have been busy working on OpenCL physics implementation (see http://www.youtube.com/watch?v=8jGZv1YYe2c), so I nearly missed this post.

Thanks,
Erwin

[majestik666]

Hey Erwin,

What is the penalty of transferring the data back to main memory ?
15fps for 110k bodies is impressive but in our case we need the data
back in the memory..

F

[kloplop321]

Erwin,

I think you should post your video link in the Bullet on GPU thread which has practically had no news for several years.

[Flix]

We have been working on OpenCL physics implementation (see http://www.youtube.com/watch?v=8jGZv1YYe2c).

Amazing video (although when I try it the stack of boxes falls through the static "floor", but I guess my video card is a bit old (Nvidia GT 120) and I haven't updated the drivers...).

@RBD: I've made a (rather trivial) version of your voronoi shatter "BasicDemo.cpp" that can be compiled with the /openMP compiler flag to support multicore processors (tested on VC++2008 and Ubuntu Linux). In case somebody is intersted, here it is:

BasicDemo.cpp

[RBD]

We have been busy working on OpenCL physics implementation (see http://www.youtube.com/watch?v=8jGZv1YYe2c)

Looks very promising Erwin! I just tried downloading the demos (both feb11 & jan27) but unfortunately they don't appear to work on my system with AMD HD4890 GPUs (RV7xx), latest drivers; no collisions happening. ...Haven't looked into it; guessing it's my hardware.

@Flix: thanks. (Haven't tried it, unfortunately my "Standard Edition" VS2008 does not support OpenMP.)