Real-time voronoi fracture and shatter for Bullet Physics

Show what you made with Bullet Physics SDK: Games, Demos, Integrations with a graphics engine, modeler or any other application
RBD
Posts: 141
Joined: Tue Sep 16, 2008 11:31 am

Real-time voronoi fracture and shatter for Bullet Physics

Post by RBD » Sat Dec 17, 2011 6:25 pm

YouTube link ==> Video demonstration of uses for voronoi fracture and shatter and voronoi cell point placement examples.

I took a shot at writing a voronoi fracture and shatter function based on the simplest brute force algorithm I could come up with inspired by Bullet Physics. Being brute force, all voronoi cell points are considered, not just nearest neighbors, therefore we can get well chiseled shards.

Here is my high level simplified algorithm:

Code: Select all

foreach current_point in voronoi_cell_points
    planes = collection of source convex object faces represented as plane equations
    max_distance = (furthest vertex from current_point) * 2
    foreach other sorted_point by distance from current_point
        if distance > max_distance
            break # rest of sorted points too far, we're done with this current point
        add new plane to planes, normal and distance = -(sorted_point - current_point) / 2
        collect vertices (3-plane intersections) by planes that fall inside all planes only
        delete planes that fell outside
        max_distance = (furthest vertex from current_point) * 2
    we now have vertices and/by planes for one voronoi 3D shard,
    process vertices by plane (sort counter-clockwise, etc.) to get faces and edges
For the attached demo I'm supplying an optimized cuboid fracture and shatter function. The algo only works with source convex polys, but the optimized bounding box shatter function presented here should be universally useable in conjunction with boolean functions for polygon meshes.
Note that since voronoi cell shards are always convex shapes, you can use highly optimized convex clipping on your polygon meshes instead of generalized boolean intersection.
If you know of a good open source convex clipping routine (intersection between convex hull and polymesh), or have one to contribute, please let us know, thank you.

The code attached here takes advantage of a relatively new Bullet Physics feature: btConvexHullComputer (Ole Kniemeyer). The voronoi shards brute force math entails some precision errors which normally would be dealt with by vertex merging and other corrections, however with btConvexHullComputer we get solid shards that have reliable counter-clockwise faces and edges every time.

In real-time games you'll be limited primarily by the number of rigid bodies you can simulate; but this code can fracture a cuboid into 32 completed btRigidBody meshed shards in less than 1/60th of a second (I suggest using targeted linear velocity voronoi random point spray).
When you run the demo, look at the console for performance timing on the voronoi fracture and shatter. Note that the time displayed is the total time it took to fracture and compute all of the 3D shards, triangulated meshes, volumes, centers of mass and create Bullet Physics rigid bodies.
Currently this is all running single-threaded as well, and considering the brute force simplicity, the process could be broken down into threads and performance significantly increased. Also, I'm certain it can be further optimized as it is.

I was hoping to produce a more full featured class and demo months ago, however I didn't get around to it, as these things go.
The code presented here does the important part and considering its straightforwardness it should be easy to understand and fairly simple to make use of in other projects.

I used Erwin's BasicDemo as a template; you can very quickly compile and test the attached as a drop in replacement for BasicDemo (make a backup copy of the originals)
The functions at the top of the demo do all of the voronoi fracture and shatter work, specifically voronoiBBShatter() along with getVerticesInsidePlanes(), see source comments.

Notes from the top of the BasicDemo file:
  • Reset scene (press spacebar) to generate new random voronoi shattered cuboids
  • Check console for total time required to: compute and mesh all 3D shards, calculate volumes and centers of mass and create rigid bodies
  • Modify VORONOIPOINTS define to change number of potential voronoi shards
  • Note that demo's visual cracks between voronoi shards are NOT present in the internally generated voronoi mesh! (I double-checked this)


If you use this algorithm/code, optimize/improve it, would be nice if you let us know, thanks.

NOTE: Attachment is demo source code only, for developers...
UPDATE: Source code updated 2011-12-23: higher tolerance for long thin shards (splinters).
Update: Minor update 2012-01-07 to restore same step order as algorithm
UPDATE: 2012-01-10 Add voronoiConvexHullShatter() to source code (not demoed) (Thanks Flix for idea). Update 2, same day: replaced getPlaneEquationsFromVertices with convexHullComputer

UPDATE: new Bullet 2.80 includes VoronoiFractureDemo! ...see my notes about this demo.
Attachments
VoronoiFractureShatterDemo.zip
Voronoi fracture and shatter basic demo SOURCE CODE (for developers!)
(6.57 KiB) Downloaded 3789 times
Last edited by RBD on Sun Mar 25, 2012 12:57 am, edited 7 times in total.

RBD
Posts: 141
Joined: Tue Sep 16, 2008 11:31 am

Re: Real-time voronoi fracture and shatter for Bullet Physic

Post by RBD » Mon Dec 19, 2011 3:45 pm

Update!: Video animation of several rendered simple voronoi fracture and shatter tests:
YouTube link ==> Voronoi Fracture and Shatter Lab Tests - Blender & Bullet Physics

AD-Edge
Posts: 5
Joined: Sun Jul 08, 2007 4:55 am

Re: Real-time voronoi fracture and shatter for Bullet Physic

Post by AD-Edge » Tue Dec 20, 2011 6:40 am

Some impressive demonstrations.
Looks forward to having a play around with it :)

Wouldnt mind seeing some tests which really push the simulation as well, in terms of the amount of shatter detail I guess.

RBD
Posts: 141
Joined: Tue Sep 16, 2008 11:31 am

Re: Real-time voronoi fracture and shatter for Bullet Physic

Post by RBD » Fri Dec 23, 2011 3:52 pm

Note that the source code was updated 2011-12-23... see first post in this thread.

Flix
Posts: 456
Joined: Tue Dec 25, 2007 1:06 pm

Re: Real-time voronoi fracture and shatter for Bullet Physic

Post by Flix » Wed Dec 28, 2011 12:43 pm

Just to say that I appreciate your demo very much :D !

P.S. Now I'm downloading the updated version. Anyway, although I don't know much about the Voronoi theory (and how to extract the planes to be able to extend the demo to general convex meshes), I was able to create 'long thin shards' by setting all the points on the bottom of the cuboid (it was funny to play with their position and see the result...).
B.T.W. The renderer you used in your videos is very attractive for the eyes :!:

RBD
Posts: 141
Joined: Tue Sep 16, 2008 11:31 am

Re: Real-time voronoi fracture and shatter for Bullet Physic

Post by RBD » Wed Dec 28, 2011 7:40 pm

Thanks.
BTW if anyone else wants to try chopping/splintering (depends on random ratio) you could simply add a line like this to the demo, right below "btVector3 diff = bbmax - bbmin;":

Code: Select all

diff.setX(diff.x()*.01);

kloplop321
Posts: 55
Joined: Sun Jan 01, 2012 7:37 pm

Re: Real-time voronoi fracture and shatter for Bullet Physic

Post by kloplop321 » Sun Jan 01, 2012 7:55 pm

This is really cool!

I wonder how well this could be implemented in a theoretically complete OpenCL implementation(including Bullet Physics).

Are you still working on this? What are you releasing under?(I see copyright to you, and I see zlib for the bullet part, but not you)

Additionally, how involved is this with HACD? (Hierarchical Approximate Convex Decomposition of 3D Meshes)
http://sourceforge.net/projects/hacd/

RBD
Posts: 141
Joined: Tue Sep 16, 2008 11:31 am

Re: Real-time voronoi fracture and shatter for Bullet Physic

Post by RBD » Tue Jan 03, 2012 9:28 pm

@kloplop321: The brute force math lends itself well to OpenCL.
Not currently working on it (released this code in response to an e-mail from Erwin). Released under same license as Bullet Physics…
This is not related to HACD. I bring up HACD as a post scriptum to my video primarily to raise awareness of HACD (also presented in juxtaposition to the "assisted voronoi convex decomposition" concept I presented in the video).

blenderdude
Posts: 1
Joined: Wed Jan 04, 2012 2:35 pm

Re: Real-time voronoi fracture and shatter for Bullet Physic

Post by blenderdude » Wed Jan 04, 2012 2:44 pm

Hi Phymec,

This is brilliant, do you know if anyone is taking this on as it would be a shame to just let this disappear into oblivion as I think Blender could really do with some proper shattering. I've been looking into creating realistic shattering for a while now, I wish I knew how to implement the code you've provided but I'm very new to the coding side of things.

All the best

Adam

kloplop321
Posts: 55
Joined: Sun Jan 01, 2012 7:37 pm

Re: Real-time voronoi fracture and shatter for Bullet Physic

Post by kloplop321 » Thu Jan 05, 2012 7:40 pm

@blenderdude
The shattering at the moment seems to be manually applied, and it is just pre-splitting stationary objects, which when disturbed, breaks apart.
It needs a lot of custom tweaking on the frames that involve shattering.

I hope to take this and come up with a means to have shatter-able objects, where weakness could potentially be painted. Along with weak constraints which can make things hang or hold together loosely so it doesn't just fall apart things to gravity alone. I don't know if my anticipated work could be ported back to where it could be used in blender.

But that's at least my idea to eventually implement. I don't know if someone will beat me to it. (I've got a lot of other things on my to-do list)

User avatar
majestik666
Posts: 66
Joined: Tue Mar 02, 2010 6:13 am

Re: Real-time voronoi fracture and shatter for Bullet Physic

Post by majestik666 » Thu Jan 05, 2012 7:42 pm

In our implementation of bullet for maya we do dynamic fracturing with voronoi.
Can't tell you much about it, but the idea is to take the contact points from the callback
check if the collision momentum is strong enough to shatter an object and then spread
points in space starting from the contact point.
This works pretty well.

kloplop321
Posts: 55
Joined: Sun Jan 01, 2012 7:37 pm

Re: Real-time voronoi fracture and shatter for Bullet Physic

Post by kloplop321 » Thu Jan 05, 2012 9:49 pm

@majestik666, are you referring to dynamica? http://code.google.com/p/dynamica

User avatar
majestik666
Posts: 66
Joined: Tue Mar 02, 2010 6:13 am

Re: Real-time voronoi fracture and shatter for Bullet Physic

Post by majestik666 » Fri Jan 06, 2012 2:39 am

no

we wrote our own maya plugin which is a fair bit more evolved
than dynamica for our fx purposes here.

I haven't looked at dynamica in a quite a while though, so not
sure what is in there now...

F

RBD
Posts: 141
Joined: Tue Sep 16, 2008 11:31 am

Re: Real-time voronoi fracture and shatter for Bullet Physic

Post by RBD » Sat Jan 07, 2012 6:21 pm

Note: minor cosmetic code update this weekend (2012-01-07) to move back (from old tests, sorry) the outside planes delete step to where it belongs, as per the algorithm.
kloplop321 wrote:It needs a lot of custom tweaking on the frames that involve shattering.
Not sure what you are referring to... keep in mind the videos were illustrative examples of point placement and step by step elaborations of the voronoi fracture and shatter use process (in Blender).
It's actually fairly simple to do targeted points spray voronoi shatter at collision time in real-time with Bullet Physics, no manual intervention or "custom tweaking" required.
Your idea of painted weaknesses and using constraints is very interesting, but a lot more involved.

If anyone wants to help with this project, what would be really useful right now is a fast convex hull to non-convex triangle mesh intersection routine to add to this (instead of using generalized boolean). Doing the voronoi convex hull clipping step on a triangle mesh should actually be pretty straightforward since the voronoi cells calculation step already provides us with our convex clipping planes. The challenge is properly filling the outside edges of our clipped mesh with faces to end up every time with solid pieces without holes (minding the uvs would be a good bonus :P).

Flix
Posts: 456
Joined: Tue Dec 25, 2007 1:06 pm

Re: Real-time voronoi fracture and shatter for Bullet Physic

Post by Flix » Sun Jan 08, 2012 8:21 am

RBD wrote:If anyone wants to help with this project, what would be really useful right now is a fast convex hull to non-convex triangle mesh intersection routine to add to this (instead of using generalized boolean). Doing the voronoi convex hull clipping step on a triangle mesh should actually be pretty straightforward since the voronoi cells calculation step already provides us with our convex clipping planes. The challenge is properly filling the outside edges of our clipped mesh with faces to end up every time with solid pieces without holes (minding the uvs would be a good bonus :P).
As I stated in a post above, I don't know much about the convex-hull theory... :cry: Just to better understand the question: is such a routine needed for speeding up the algorithm or to extend it to be applied to generic (non-convex, but closed) meshes ? (UV support would be great in either case... :D ) .

I ask because I've tried to combine your code with the HACD library to decompose concave meshes: it doesn't work, because the HACD decomposed convex meshes overlap (and I guess other convex decomposition libraries behave in the same way...).

Hope somebody can find the routine you're looking for... :?

Post Reply