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
Flix
Posts: 456
Joined: Tue Dec 25, 2007 1:06 pm

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

Post by Flix »

RBD wrote:Haven't looked into it; guessing it's my hardware.
That's the same that's happening to me...
RBD wrote:(Haven't tried it, unfortunately my "Standard Edition" VS2008 does not support OpenMP.)
I didn't know it, but if you have some time to waste, you may try and see if the pieces you're missing are present in some Windows SDK version (see: http://stackoverflow.com/questions/8656 ... 5-standard, but I don't know if it works for you). Or you may try other (free) compilers that support it (http://openmp.org/wp/openmp-compilers/).
BTW: I think this is (only) the second time I use openMP in a program, so I don't know if it's worth struggling for making it work... these are just some info I've found on the web. :?

[Edit:] Specific instructions about Visual C++ 2008 Express and openMP can be found here: http://kenny-tm.xanga.com/651048063/par ... 8-express/.
Last edited by Flix on Sun Mar 18, 2012 7:57 am, edited 1 time in total.
wormszer
Posts: 3
Joined: Fri Oct 07, 2011 9:07 pm

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

Post by wormszer »

I tried running the code with bullet 2.79 downloaded from the website, but I am getting a stack overflow in quick sort. I have not modified anything. Anyone else have this issue?
I duplicated the basicdemo project and modified the cmake a little otherwise i haven't changed anything.

Line 129: sortedVoronoiPoints.quickSort(pointCmp);

Anyone else having this issue?

Thanks
wormszer
Posts: 3
Joined: Fri Oct 07, 2011 9:07 pm

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

Post by wormszer »

I replaced the btAlignedObjectArray::quickSort with btAlignedObjectArray::heapSort and seems to work fine. Guessing there is a bug with btAlignedObjectArray::quickSort.

If I have some more time I will see if I can dig into it more.
Flix
Posts: 456
Joined: Tue Dec 25, 2007 1:06 pm

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

Post by Flix »

wormszer wrote:I tried running the code with bullet 2.79 downloaded from the website, but I am getting a stack overflow in quick sort. I have not modified anything. Anyone else have this issue?[...]I replaced the btAlignedObjectArray::quickSort with btAlignedObjectArray::heapSort and seems to work fine. Guessing there is a bug with btAlignedObjectArray::quickSort.
I suggest you replace the files btAlignedObjectArray.h and btAlignedObjectArray.cpp of the bullet 2.79 version with the ones in the Bullet SVN repository and see if quicksort works. I'd change them in any case, because AFAIR there were issues with the assignment operator that were fixed in the SVN repository and that can lead to crashes that are difficult to debug (http://bulletphysics.org/Bullet/phpBB3/ ... ectArray.h).
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

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

Post by Erwin Coumans »

There was a bug in the quickSort. It is fixed in latest trunk and in Bullet 2.80 rev 2527. Apparently the sort went into an infinite recursion and to avoid this, the pivot element should not be included when sorting the sub partitions.

This voronoi fracture demo is great, I included it in Bullet 2.80, under Demos/VoronoiFractureDemo. I added automatic constraint generation between the parts, with a breakable threshold and increased solver iterations.

If you downloaded Bullet 2.80 release early (rev 2526) please re-download for this fix.
Thanks!
Erwin
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

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

Post by Erwin Coumans »

majestik666 wrote:What is the penalty of transferring the data back to main memory ?
It comes at a cost, but it is still worth doing the simulation on the GPU.

Note that the current GPU rigid body pipeline only support approximate convex shapes, I haven't integrated concave triangle mesh support yet (there are some internal prototypes with more features).

If you have more questions about the GPU stuff, it is probably better to create a new topic in the "General Bullet Physics Support and Feedback" section.
Thanks,
Erwin
RBD
Posts: 141
Joined: Tue Sep 16, 2008 11:31 am

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

Post by RBD »

Erwin Coumans wrote:I included it in Bullet 2.80, under Demos/VoronoiFractureDemo. I added automatic constraint generation between the parts, with a breakable threshold and increased solver iterations.
Thanks Erwin, the breakable constraints are very impressive! :D

Note to others about the new VoronoiFractureDemo included in the latest release/svn of Bullet Physics library:
- The VoronoiFractureDemo demo adds a collision margin to all voronoi shards to provide more stable, less "sticky" collisions. Therefore the VoronoiFractureDemo demo will indeed produce actual gaps/cracks between voronoi shards (do not use these for boolean operations). Also Keep in mind that adding a collision margin increases the amount (2X) of time to generate voronoi shards. So by changing (near the top of VoronoiFractureDemo):
#define CONVEX_MARGIN 0.04
to:
#define CONVEX_MARGIN 0.0
Voronoi shard generation will approximately double in speed (and will not have actual gaps/cracks between shards).

- The VoronoiFractureDemo features breakable constraints. Breakable constraints are a very cool feature for pre-fractured shards to stay together until actual collisions break them apart based on impact/collision location and strength. But there is some performance cost for this to the simulation. Alternatively, to avoid this overhead, and to make your voronoi fractures look more realistic, you may want to consider doing voronoi fractures in real-time, on demand, at collision time; this involves simply spraying some voronoi points from the collision/impact location and generating standard rigid body voronoi shards (no constraints) in real-time. This has the advantage that damage looks impact specific, with more, smaller shards near the impact point; and not much performance penalty on the simulation. In the videos at the top of this thread, you can see some examples of collision targeted voronoi shatters (not the random point distribution ones); constraints were not used in those videos, voronoi shattering was simply performed at collision time based on impact location.
But with this demo I'm also thinking it might be possible to combine breakable constraints with real-time targeted voronoi shatter; this could provide both impact specific voronoi fracturing and clumping of shards so that they may break off in seemingly non-convex clusters, and be all ready for some secondary shattering (when they fall to the ground or whatever).
Flix
Posts: 456
Joined: Tue Dec 25, 2007 1:06 pm

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

Post by Flix »

RBD wrote:Therefore the VoronoiFractureDemo demo will indeed produce actual gaps/cracks between voronoi shards (do not use these for boolean operations). Also Keep in mind that adding a collision margin increases the amount (2X) of time to generate voronoi shards.
Interesting... if this is the case I think I'll always use real-time fracturing with zero collision margin.
RBD wrote: [...] But there is some performance cost for this to the simulation.
I agree, I don't think I'll ever use pre-fracturing and pre-merging (through fixed breakable constraints), unless the number of shards is very low. In cases when real-time fracturing takes too long, I'd simply use pre-fracturing plus run-time replacement. I like the fact that in the demo only a few shards can be released on collision (possibly leaving a concave shape in place), but I think it's too expensive (grouping the remaining shards into a compound shape would be more efficient, although the code required to fracture them is more difficult to maintain, like in the first Bullet Fracture Demo). Anyway the new demo shows an alternative, and it's the first Bullet demo with a breakable fixed constraint in action.
Domi
Posts: 4
Joined: Fri Apr 06, 2012 2:10 am

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

Post by Domi »

Hi,

A too big CONVEX_MARGIN value crashes the VoronoiFracture demo.

The crash occurs because the convex hull computer does not generate a hull for some shard. I am guessing, the shard is too small. Is there a way to estimate or even constrain the minimum shard size, so it is ensured that margin != 0 will never cause a crash?

Edit:
I am thinking, Perlin noise could help here, since it's features are all equal in size but I would not know how. Does anyone have any ideas?
An alternative would be a simple random/rejection algorithm that rejects points which are not at least 2 * margin away from all other points.
I guess I semi-answered my question :)
Flix
Posts: 456
Joined: Tue Dec 25, 2007 1:06 pm

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

Post by Flix »

Domi wrote:A too big CONVEX_MARGIN value crashes the VoronoiFracture demo. The crash occurs because the convex hull computer does not generate a hull for some shard. I am guessing, the shard is too small. Is there a way to estimate or even constrain the minimum shard size, so it is ensured that margin != 0 will never cause a crash?
According to the documentation of btScalar btConvexHullComputer::compute(const float* coords, int stride, int count, btScalar shrink, btScalar shrinkClamp) (LinearMath/btConvexHullComputer.h):

Code: Select all

		/*
		Compute convex hull of "count" vertices stored in "coords". "stride" is the difference in bytes
		between the addresses of consecutive vertices. If "shrink" is positive, the convex hull is shrunken
		by that amount (each face is moved by "shrink" length units towards the center along its normal).
		If "shrinkClamp" is positive, "shrink" is clamped to not exceed "shrinkClamp * innerRadius", where "innerRadius"
		is the minimum distance of a face to the center of the convex hull.

		The returned value is the amount by which the hull has been shrunken. If it is negative, the amount was so large
		that the resulting convex hull is empty.

		The output convex hull can be found in the member variables "vertices", "edges", "faces".
		*/
 btScalar btConvexHullComputer::compute(const float* coords, int stride, int count, btScalar shrink, btScalar shrinkClamp);
So you can probably use something like this to ensure that the computing is OK:

Code: Select all

if (convexHC->compute(&vertices[0].getX(), sizeof(btVector3), vertices.size(),margin,0.0)<0) convexHC->compute(&vertices[0].getX(), sizeof(btVector3), vertices.size(),0.0,0.0);
This way you try to use 'margin' when computing the hull indices, and if it doesn't work, you compute another hull using 'margin'=0. Hope it works, but I'm not sure if this approach (of shrinking the hull by its margin) is 100% correct :?
RBD
Posts: 141
Joined: Tue Sep 16, 2008 11:31 am

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

Post by RBD »

Domi, that's what convexHC->compute's shrinkClamp parameter is for… give it a minimum value, and you could use convexHC->compute's return value to set your rb's collision margin. If you do not want RBs smaller than your margin, you could simply skip (don't creat rbs) shards when convexHC->compute returns < 0.0.
Crackerjack55
Posts: 3
Joined: Mon Sep 24, 2012 11:42 pm

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

Post by Crackerjack55 »

Hey there ladies and gentlemen,

I was wondering if anyone has created a demo that implements the convex hull shatter function?
My attempts to do so have failed so far, I have a bounding box that shatters into fragments,
however when I try to fracture those fragments, two identical shards are created in the same space and collide dramatically
Even better has anyone managed to implemented dynamic recurring shattering where a bounding
box is fractured and the subsequent shards can also fracture?

I would love to look at anyone's implementations that are available

Please and thank you
Flix
Posts: 456
Joined: Tue Dec 25, 2007 1:06 pm

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

Post by Flix »

Crackerjack55 wrote:I was wondering if anyone has created a demo that implements the convex hull shatter function?
As far as I remember I used it to fracture pyramids and ellipsoids in the OpenMP version I posted here some time ago (you can extract the related code and use it in the non-OpenMP version if you like... it should work).
Crackerjack55 wrote:Even better has anyone managed to implemented dynamic recurring shattering where a bounding
box is fractured and the subsequent shards can also fracture?
Never tried.
Crackerjack55
Posts: 3
Joined: Mon Sep 24, 2012 11:42 pm

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

Post by Crackerjack55 »

Thanks to flix for your response, I'll look into your implementation very soon :)
wing64
Posts: 1
Joined: Sat Nov 23, 2013 3:00 pm

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

Post by wing64 »

@RBD: I follow implement from your example. see video :-)
http://youtu.be/NiIZE9Zsix4
Post Reply