# Physics Simulation Forum

 All times are UTC

 Page 1 of 3 [ 41 posts ] Go to page 1, 2, 3  Next
 Print view Previous topic | Next topic
Author Message
 Posted: Sat Dec 17, 2011 6:25 pm

Joined: Tue Sep 16, 2008 11:31 am
Posts: 115
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:
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

 Attachments: File comment: Voronoi fracture and shatter basic demo SOURCE CODE (for developers!) VoronoiFractureShatterDemo.zip [6.57 KiB] Downloaded 1552 times

Last edited by RBD on Sun Mar 25, 2012 12:57 am, edited 7 times in total.
Top

 Posted: Mon Dec 19, 2011 3:45 pm

Joined: Tue Sep 16, 2008 11:31 am
Posts: 115
Update!: Video animation of several rendered simple voronoi fracture and shatter tests:
YouTube link ==> Voronoi Fracture and Shatter Lab Tests - Blender & Bullet Physics

Top

 Posted: Tue Dec 20, 2011 6:40 am

Joined: Sun Jul 08, 2007 4:55 am
Posts: 5
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.

Top

 Posted: Fri Dec 23, 2011 3:52 pm

Joined: Tue Sep 16, 2008 11:31 am
Posts: 115
Note that the source code was updated 2011-12-23... see first post in this thread.

Top

 Posted: Wed Dec 28, 2011 12:43 pm

Joined: Tue Dec 25, 2007 1:06 pm
Posts: 315
Just to say that I appreciate your demo very much !

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

Top

 Posted: Wed Dec 28, 2011 7:40 pm

Joined: Tue Sep 16, 2008 11:31 am
Posts: 115
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:
diff.setX(diff.x()*.01);

Top

 Posted: Sun Jan 01, 2012 7:55 pm

Joined: Sun Jan 01, 2012 7:37 pm
Posts: 55
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/

Top

 Posted: Tue Jan 03, 2012 9:28 pm

Joined: Tue Sep 16, 2008 11:31 am
Posts: 115
@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).

Top

 Posted: Wed Jan 04, 2012 2:44 pm

Joined: Wed Jan 04, 2012 2:35 pm
Posts: 1
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

Top

 Posted: Thu Jan 05, 2012 7:40 pm

Joined: Sun Jan 01, 2012 7:37 pm
Posts: 55
@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)

Top

 Posted: Thu Jan 05, 2012 7:42 pm

Joined: Tue Mar 02, 2010 6:13 am
Posts: 66
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.

Top

 Posted: Thu Jan 05, 2012 9:49 pm

Joined: Sun Jan 01, 2012 7:37 pm
Posts: 55
@majestik666, are you referring to dynamica? http://code.google.com/p/dynamica

Top

 Posted: Fri Jan 06, 2012 2:39 am

Joined: Tue Mar 02, 2010 6:13 am
Posts: 66
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

Top

 Posted: Sat Jan 07, 2012 6:21 pm

Joined: Tue Sep 16, 2008 11:31 am
Posts: 115
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 ).

Top

 Posted: Sun Jan 08, 2012 8:21 am

Joined: Tue Dec 25, 2007 1:06 pm
Posts: 315
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 ).
As I stated in a post above, I don't know much about the convex-hull theory... 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... ) .

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...

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 3 [ 41 posts ] Go to page 1, 2, 3  Next

 All times are UTC

#### Who is online

Users browsing this forum: Bing [Bot] and 2 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ BULLET PHYSICS LIBRARY USERS    General Bullet Physics Support and Feedback    Release Announcements    Applications, Games, Demos or Movies using Bullet PHYSICS AUTHORING TOOLS, SERIALIZATION AND STANDARDS    Physics authoring tools, serialization, standards and related topics RESEARCH AND DEVELOPMENT IN COLLISION DETECTION & PHYSICS. Don't post Bullet support questions here!    Research and development discussion about Collision Detection and Physics Simulation    Links, Papers, Libraries, Demos, Movies, Comparisons       Non-technical forum and license/patent discussion    Career Opportunities