[issue90] Glue / Fracture rigid bodies discussion

nanocell
Posts: 8
Joined: Mon Jan 18, 2010 1:34 pm
Location: Sydney, Australia

[issue90] Glue / Fracture rigid bodies discussion

I am opening this thread to start a discussion about ideas for achieving glue / fracturing of rigid bodies and to avoid spamming the issue tracker (http://code.google.com/p/bullet/issues/detail?id=90).

If you use a procedural voronoi fracture then calculating the connectivity is trivial since the connectivity is simply the dual of the voronoi diagram, i.e., the delaunay triangulation. While this might be quite cool for performing runtime fractures one should just keep in mind to allow for artists to create prefractured geometry which may, or may not, have been created by a voronoi fracture.

The trick would be to somehow automatically calculate neighbours. I have worked on a project to do exactly this from within Houdini. We naively constructed a 'connectivity graph' by performing a 3D deluanay triangulation on the centroids of all the "chunks". We would then perform shock / impact propagation along those edges and break them when they exceeded certain 'strength' thresholds and so forth.
The problem with this naive connectivity graph construction is that pieces in fairly close proximity (but not actually touching) should not be connected but the Delaunay triangulation simply connects all the centroids regardless of whether the pieces are touching or not.

I have another idea which might actually create a much more reliable connectivity graph. Note that this method is not necessarily suitable for on-the-fly connectivity calculation (it might get slow) but its should work quite well as an offline method.
Consider a wall that has been fractured into a bunch of chunks (http://chestofbooks.com/architecture/Bu ... es-185.jpg). Take each chunk and scale it outward (along the normals?) to get a slightly bigger version of each chunk. This is to make sure that each chunk is touching its neighbour. Now perform a collision detection step. We don't need impulses / forces resolved here. We just want the collision pairs between the chunks. This set of collision pairs can now be used to build a graph that defines the connectivity between the chunks. Each collision pair will essentially define an edge in the graph. Note that we can ignore multiple collisions between chunk A and B; we just want to know whether they collide or not -- one is enough.

So, what do you guys/gals think? Does the chunk-scaling method sound viable?

CheerZ,
Van Aarde.
Last edited by nanocell on Fri Jul 30, 2010 4:01 pm, edited 1 time in total.

Erwin Coumans
Posts: 4073
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: [issue90] Glue / Fracture rigid bodies discussion

During SIGGRAPH this week, there was a talk called 'blowing \$h!t up', about the movie 2012. In that talk, Digital Domain discussed how they added pre-fracturing objects to Bullet, based on btCompoundShape.

They tried 3 different ways to connect parts: spherical extrusion, nearest neighbours and full connectivity. One easy way to compute the nearest neighbours is to calculate contact points (using the collision dispatcher). They also allowed artists to paint 'weights' to the connections, so they can make parts stronger so they don't fall apart so easily.

The other interesting part of this talk was the method how they break things apart: they simulate the individual child shapes of the btCompoundShape, without constraints, and afterwards measure the offset and applied impulse. Based on this information, and on the weighted connectivity, they decide if and when to split the btCompoundShape into multiple parts.

Have you tried this method?
This should be fairly easy to implement, so we'll look into providing an implementation soon. See http://code.google.com/p/bullet/issues/detail?id=90 for the progress.
Thanks,
Erwin

nanocell
Posts: 8
Joined: Mon Jan 18, 2010 1:34 pm
Location: Sydney, Australia

Re: [issue90] Glue / Fracture rigid bodies discussion

Hey, that's all really interesting! I hope you took extensive notes!

Okay, so given what you've just written, the "nearest neighbours" is the technique that I was trying to describe. Could you elaborate a bit more on the other two methods (spherical extrusion and full connectivity) ... just for the sake of curiosity?

That is a very interesting method for "breaking apart" the buildings and definitely worth remembering. We didn't have an elaborate system like that though (we had a fairly short time frame in which to build the tool and churn out the shots). We just allowed the artists to fracture and then generate/create connections and their strengths, or 'weights' which could be animated over the sequence to allow for much more artistic control over the destruction.

I'll definitely be keep my on this feature. And thanks for the feedback!

CheerZ,
Van Aarde.

Erwin Coumans
Posts: 4073
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: [issue90] Glue / Fracture rigid bodies discussion

The demo allows you to toggle between 'glue' and 'fracture' mode using the F key..

A new class btFractureBody derived from btRigidBody maintains connectivity and mass information for child shapes in the btCompoundShape.
The connectivity between child shapes in a btCompoundShape is computed using contact points using the world->contactPairTest() query.

In fracture mode, if a rigid body collides with a btFractureBody and it exceeds some threshold, it will try to break connections. Then it will recompute connectivity, and if there are 2 or more parts it will spawn new btFractureBody for each, and remove the original. It uses union find to detect disconnected parts after fracture.

In glue mode, when a rigid body collides with a btFractureBody, they will merge together.
Thanks,
Erwin

nanocell
Posts: 8
Joined: Mon Jan 18, 2010 1:34 pm
Location: Sydney, Australia

Re: [issue90] Glue / Fracture rigid bodies discussion

I saw the update in the bug tracker! Really exciting!!

I'm hoping to get some time to test this over the weekend.

Thanks for all the effort!

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

Re: [issue90] Glue / Fracture rigid bodies discussion

We actually implemented glue here using compound shapes
and using the contactAddedCallback, it does require a fair bit of tweaking
but you can get pretty good results (removing contacts,etc...)

I'm currently implementing a second method using breaking constraints
which also requires some changes into the solver, maybe i could publish
my breaking constraint code as a patch , unless it's already planned ? (Erwin?)

Francois

nanocell
Posts: 8
Joined: Mon Jan 18, 2010 1:34 pm
Location: Sydney, Australia

Re: [issue90] Glue / Fracture rigid bodies discussion

What is the performance like when using constraints as glue, with say, 100+ objects in the compound shape?

Sharing the code, if you can, would be great whether it's planned or not. At the very least we can play with it .

The glue/fracture implementation I worked on previously was done with custom connectivity structures, compound shapes and a number of modifications around the solver but it was quite surprisingly snappy. Unfortunately I don't have access to those tools anymore so I can't post exact timing info and if I had to thumb-suck it, I'd probably get it wrong

sparkprime
Posts: 508
Joined: Fri May 30, 2008 2:51 am
Location: Ossining, New York
Contact:

Re: [issue90] Glue / Fracture rigid bodies discussion

Am I right to assume from this discussion that the connectivity network is only used to detect which parts are on the 'left' and 'right' of a disconnection in order to form two separate rigid bodies, and that the network is not used to compute stress and work out which links fail when given forces are applied to the different parts.

nanocell
Posts: 8
Joined: Mon Jan 18, 2010 1:34 pm
Location: Sydney, Australia

Re: [issue90] Glue / Fracture rigid bodies discussion

In the implementation that I worked on we used the connectivity graph for force propagation and removed the connections when the force exceeded some user defined value. If a "chunk", or set of chunks (still connected to each other), would have no more links that "connected" to the main rigid body, it would split them off to form their own rigid body...more or less Keep in mind that this implementation was fairly "basic" in term of *real* dynamics. We opted for artistic control rather than "physically based" simulations.

So, the graph described how the child shapes relate to each other. Once they get separated into two rigid bodies, two separate connectivity graphs would form.

But you can use it however you want to use it

hth

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

Re: [issue90] Glue / Fracture rigid bodies discussion

I cannot post glue code per say because it's proprietary,
but the other day I was running a vehicle crashing into a building
the building being 5000+ meshes and it ran at a few fps, which
is more than acceptable for my environment (film).
I did too make quite a few modifications to the solver for stability,etc
but the idea is very close to what Erwin posted as btFractureBody
with a lot more control over the glue strength etc