Soft bodies early preview

Please don't post Bullet support questions here, use the above forums instead.
Nathanael
Posts: 78
Joined: Mon Nov 13, 2006 1:44 am

Re: Soft bodies early preview

Post by Nathanael »

Dirk Gregorius wrote:So you do this the following?
c = ( p1 + p2 + p3 + p4 ) / 4
p1 += k * (p1 - c) / |p1 - c|
...
This would be an interesting approach. I am not sure if this is physical correct though. The displacements should be in the direction of the gradients to be kind of "workless"". I need to think about this. The gradients I posted above are the derivatives of C w.r.t p_i where i = 1..4.

Or do you just do this:

c = ( p1 + p2 + p3 + p4 ) / 4
p1 -= c;
...
p1 *= k;
...
p1 += c;
...
Yes i do:
p1=(p1 - c) k + c
etc..
'c' can actually be anywhere inside the tetrahedron, weighed by vertices's mass, even if it doesn't make much sens for a tetrahedral mesh , where tetrahedrons are expected to be the mass carriers, but its to be consistent with other simplex and leave room for tweaking.

As for physical meaning, i am sure that you are right, but I'd like to see both solutions in action , so tomorrow, I'll try to write a small test app to visually check the triangle case.

Nat.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Soft bodies early preview

Post by Dirk Gregorius »

Do you have any post-condition you test, such that the volume of the corrected tetrahedron equals the inital volume?
Nathanael
Posts: 78
Joined: Mon Nov 13, 2006 1:44 am

Re: Soft bodies early preview

Post by Nathanael »

Dirk Gregorius wrote:Do you have any post-condition you test, such that the volume of the corrected tetrahedron equals the inital volume?
Yes, it does check.

Here's a little visual app to see the triangle case with only my 'solution' for the moment.
Attachments
carea.zip
(41.33 KiB) Downloaded 683 times
Antonio Martini
Posts: 126
Joined: Wed Jul 27, 2005 10:28 am
Location: SCEE London

Re: Soft bodies early preview

Post by Antonio Martini »

Nathanael wrote:Yes i do:
p1=(p1 - c) k + c
etc..
'c' can actually be anywhere inside the tetrahedron, weighed by vertices's mass, even if it doesn't make much sens for a tetrahedral mesh , where tetrahedrons are expected to be the mass carriers, but its to be consistent with other simplex and leave room for tweaking.

As for physical meaning, i am sure that you are right, but I'd like to see both solutions in action , so tomorrow, I'll try to write a small test app to visually check the triangle case.
what happens if a vertex belonging to a tetrahedron crosses the opposite face(this can easily happen) and so the center will go outside ? will the rest shape converge to an inverted tetrahedron?

cheers,
Antonio
Nathanael
Posts: 78
Joined: Mon Nov 13, 2006 1:44 am

Re: Soft bodies early preview

Post by Nathanael »

Here's an update of 'carea', including both methods:

- 'com' , that solve the area constraint, but do not minimize displacement.
- 'gradient' the solve the area constraint by displacement along constraint gradients.

Note: Flipping area is not handled. , Keys: 'c' to allow free COM, '+'/'-' to increase/decrease objective area.

Nat.
Attachments
carea.zip
(31.11 KiB) Downloaded 659 times
Antonio Martini
Posts: 126
Joined: Wed Jul 27, 2005 10:28 am
Location: SCEE London

Re: Soft bodies early preview

Post by Antonio Martini »

Nathanael wrote:Some of the demos use polar decomposition the extract a rigid frame from the deformed model, as explained in great details in 'Matrix Animation and Polar Decomposition, Ken Shoemake.', the decomposition implementation method itself come from 'The Polar Decomposition Properties, Applications And Algorithms, Pawel Zielinski, Krystyna Zietak'. Muller make use of it in one paper, but goes beyond linear deformation, and far beyond my understanding... :wink:
a rigid frame can be extracted much faster by using a QR approach. see also figure 2 of :

http://www-evasion.imag.fr/Publications ... /NPF05.pdf

this method is also described in the Physics Based Animation book of Erleben if i remember it correctly.

cheers,
Antonio
Nathanael
Posts: 78
Joined: Mon Nov 13, 2006 1:44 am

Re: Soft bodies early preview

Post by Nathanael »

Antonio Martini wrote: a rigid frame can be extracted much faster by using a QR approach. see also figure 2 of :
http://www-evasion.imag.fr/Publications ... /NPF05.pdf
this method is also described in the Physics Based Animation book of Erleben if i remember it correctly.
Thanks the the link, i didn't knew about it.

QR decomposition seen interesting, but as noted in paper, there's a bias depending on vertex order, that can be a problem for resting bodies, a bias is already introduced by the solver (in the 'Bunny', if friction is not set >0.9, it never come rest due to constraints order bias).
Now for speed, polar decomposition is actually quit fast, that's O(vertices) to build the matrix, cost shared by QR decomposition, (though
the O of QR may be faster), then the decomposition itself (Higham's method):

Code: Select all

static inline void			PolarDecompose(	const btMatrix3x3& m,
											btMatrix3x3& q,
											btMatrix3x3& s)
{
static const btScalar	half=(btScalar)0.5;
static const btScalar	accuracy=(btScalar)0.00001;
static const int		maxiterations=64;
btScalar				det=m.determinant();
if(!btFuzzyZero(det))
	{
	q=m;
	for(int i=0;i<maxiterations;++i)
		{
		q=Mul(Add(q,Mul(q.adjoint(),1/det).transpose()),half);
		const btScalar	ndet=q.determinant();
		if(Sq(ndet-det)>accuracy) det=ndet; else break;
		}
	s=q.transpose()*m;
	s=Mul(Add(s,s.transpose()),(btScalar)0.5);
	}
	else
	{
	q.setIdentity();
	s.setIdentity();
	}
}
usually stop after ~12 iterations, and there is way the accelerate it further via a scaling factor (and better implementation... :wink: ).
Nathanael
Posts: 78
Joined: Mon Nov 13, 2006 1:44 am

Re: Soft bodies early preview

Post by Nathanael »

>Thinking about it, the M matrix is symmetric, there must exist a better (non iterative) way to extract a polar decomposition. if polar >decomposition ever become a bottleneck, i should get back to it.

Never mind, that's wrong.

Nat.
Nathanael
Posts: 78
Joined: Mon Nov 13, 2006 1:44 am

Re: Soft bodies early preview

Post by Nathanael »

Antonio Martini wrote: what happens if a vertex belonging to a tetrahedron crosses the opposite face(this can easily happen) and so the center will go outside ? will the rest shape converge to an inverted tetrahedron?
Keep in mind that i don't use tetrahedrons yet, so what's follow is more guesses than hard evidences.

In the case of sign inversion, we can view the situation from the static point of view, or the dynamic one.
The static view, in are facing an inverted tetrahedron without any knowledge of its past states, so we need to choose which vertex to flip (or which plane to flip about), my guess is the least displacement is the best choice here.
The dynamic view is more interesting, now we may treat the situation more like a collision, may be the vertex with the highest velocity is a good choice.
Or is there a 'standard'/'best' way to handle that?

Nat.
Antonio Martini
Posts: 126
Joined: Wed Jul 27, 2005 10:28 am
Location: SCEE London

Re: Soft bodies early preview

Post by Antonio Martini »

Nathanael wrote:Now for speed, polar decomposition is actually quit fast, that's O(vertices) to build the matrix, cost shared by QR decomposition
given the same O(...) you can still have a much faster method than the other one. just count how many matrix muls, determinants and iterations there are in that code, and it is still iterative.If the output of your code is not a orthonormal matrix you may need to orthonormalize the frame anyway, for example run 3-4 fixed iterations to guess a rough orientation and then make the resulting matrix orthonormal. When i switched between the 2 methods in a FEM solver i never noticed any artifacts and the QR code is just 4-5 lines of code without any iterations. However it can be argued that we are not talking about a FEM solver here so it's difficult to tell without trying it out.

cheers,
Antonio
Antonio Martini
Posts: 126
Joined: Wed Jul 27, 2005 10:28 am
Location: SCEE London

Re: Soft bodies early preview

Post by Antonio Martini »

Nathanael wrote: In the case of sign inversion, we can view the situation from the static point of view, or the dynamic one.
suppose a tetrahedron having nodes {a,b,c,d} is squashed in a such way that node a lies on the opposite face defined by b,c,d, this can easily happen after contact at reasonable speed for example, the smaller the tetrahedron compared to its linear displacement the easier it can happen. We have a tetrahedron having zero volume that would look like a triangle, given that you are trying to restore the volume by using a displacement relative to the mass center node a will never be able to escape b,c,d apparently? i called it a tetrahedron to give it more intuition but you can call it 4 nodes having a volume conservation constraint enforced on them.

cheers,
Antonio
Last edited by Antonio Martini on Sat Mar 22, 2008 1:30 pm, edited 2 times in total.
Antonio Martini
Posts: 126
Joined: Wed Jul 27, 2005 10:28 am
Location: SCEE London

Re: Soft bodies early preview

Post by Antonio Martini »

Nathanael wrote:- the demos named 'TorusMatch' and 'BunnyMatch' use polar decomposition to extract linear transforms (just rotation for the moment) from the deformed model, and 'pulling' vertices's toward the reference shape, see 'shape matching' from Matthias Muller (him again :wink: ). Still no tetrahedron.
i am reading the thread starting from the end :) i see so you extract one transform per object? i remember that the shape matching paper needed clusters of vertices and extracted the transform for single clusters and there were some artifacts that needed to be fixed.

cheers,
Antonio

EDIT: if you are using one rigid frame per body then i agree you need something accurate. I was thinking about one rigid frame per tetrahedron or set of particles. However if you use only one rigid frame and move the vertices out from the object mass center it would not work well for many important cases. make a long straight cylinder and bend it in a U shape, the mass center is in the middle and it looks like that the intermediate "pulled" shapes would look very bad before the object, if we are lucky will go back to the original shape. have i missed something again?:) for such object the extracted orientation would be useless.
Last edited by Antonio Martini on Sat Mar 22, 2008 2:05 pm, edited 3 times in total.
Nathanael
Posts: 78
Joined: Mon Nov 13, 2006 1:44 am

Re: Soft bodies early preview

Post by Nathanael »

Antonio Martini wrote:When i switched between the 2 methods in a FEM solver i never noticed any artifacts and the QR code is just 4-5 lines of code without any iterations. However it can be argued that we are not talking about a FEM solver here so it's difficult to tell without trying it out.
what method are you using for QR decomposition, wikipedia list: Gram-Schmidt, Householder, Givens. you said 5 lines, is that Gram-Schmidt?
Antonio Martini
Posts: 126
Joined: Wed Jul 27, 2005 10:28 am
Location: SCEE London

Re: Soft bodies early preview

Post by Antonio Martini »

Nathanael wrote:
Antonio Martini wrote:When i switched between the 2 methods in a FEM solver i never noticed any artifacts and the QR code is just 4-5 lines of code without any iterations. However it can be argued that we are not talking about a FEM solver here so it's difficult to tell without trying it out.
what method are you using for QR decomposition, wikipedia list: Gram-Schmidt, Householder, Givens. you said 5 lines, is that Gram-Schmidt?
the comments on figure 2 of the paper i posted earlier explain how it is computed.

but if you have only one rigid frame per object i dont think it is a good idea to use QR.

cheers,
Antoio
Nathanael
Posts: 78
Joined: Mon Nov 13, 2006 1:44 am

Re: Soft bodies early preview

Post by Nathanael »

Antonio Martini wrote:We have a tetrahedron having zero volume that would look like a triangle, given that you are trying to restore the volume by using a displacement relative to the mass center node a will never be able to escape b,c,d apparently? i called it a tetrahedron to give it more intuition but you can call it 4 nodes having a volume conservation constraint enforced on them.
You absolutely right, actually it's even worse, the scaling factor is function of V/V0 , the shape begin to behave very badly much sooner than the case you mention (you can see that on triangle by running 'carea' few post before).
But even using gradient directions, volume inversion do happen, is there a good, fast method to handle that?.

Nat.
Post Reply