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