# Physics Simulation Forum

 Page 2 of 3 [ 42 posts ] Go to page Previous  1, 2, 3  Next
 Print view Previous topic | Next topic
Author Message
 Post subject: Re: Soft bodies early previewPosted: Thu Mar 20, 2008 4:35 pm

Joined: Mon Nov 13, 2006 1:44 am
Posts: 78
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.

Top

 Post subject: Re: Soft bodies early previewPosted: Thu Mar 20, 2008 4:55 pm

Joined: Sun Jul 03, 2005 4:06 pm
Posts: 773
Location: Bellevue, WA
Do you have any post-condition you test, such that the volume of the corrected tetrahedron equals the inital volume?

Top

 Post subject: Re: Soft bodies early previewPosted: Thu Mar 20, 2008 5:34 pm

Joined: Mon Nov 13, 2006 1:44 am
Posts: 78
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.

Top

 Post subject: Re: Soft bodies early previewPosted: Fri Mar 21, 2008 5:01 pm

Joined: Wed Jul 27, 2005 10:28 am
Posts: 135
Location: SCEE London
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

Top

 Post subject: Re: Soft bodies early previewPosted: Sat Mar 22, 2008 2:59 am

Joined: Mon Nov 13, 2006 1:44 am
Posts: 78
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.

Top

 Post subject: Re: Soft bodies early previewPosted: Sat Mar 22, 2008 3:05 am

Joined: Wed Jul 27, 2005 10:28 am
Posts: 135
Location: SCEE London
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...

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

Top

 Post subject: Re: Soft bodies early previewPosted: Sat Mar 22, 2008 3:46 am

Joined: Mon Nov 13, 2006 1:44 am
Posts: 78
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.

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:
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)
{
const btScalar   ndet=q.determinant();
if(Sq(ndet-det)>accuracy) det=ndet; else break;
}
s=q.transpose()*m;
}
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... ).

Top

 Post subject: Re: Soft bodies early previewPosted: Sat Mar 22, 2008 3:52 am

Joined: Mon Nov 13, 2006 1:44 am
Posts: 78
>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.

Top

 Post subject: Re: Soft bodies early previewPosted: Sat Mar 22, 2008 7:11 am

Joined: Mon Nov 13, 2006 1:44 am
Posts: 78
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.

Top

 Post subject: Re: Soft bodies early previewPosted: Sat Mar 22, 2008 8:01 am

Joined: Wed Jul 27, 2005 10:28 am
Posts: 135
Location: SCEE London
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

Top

 Post subject: Re: Soft bodies early previewPosted: Sat Mar 22, 2008 9:05 am

Joined: Wed Jul 27, 2005 10:28 am
Posts: 135
Location: SCEE London
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.

Top

 Post subject: Re: Soft bodies early previewPosted: Sat Mar 22, 2008 1:15 pm

Joined: Wed Jul 27, 2005 10:28 am
Posts: 135
Location: SCEE London
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 ). 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.

Top

 Post subject: Re: Soft bodies early previewPosted: Sat Mar 22, 2008 1:20 pm

Joined: Mon Nov 13, 2006 1:44 am
Posts: 78
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?

Top

 Post subject: Re: Soft bodies early previewPosted: Sat Mar 22, 2008 1:28 pm

Joined: Wed Jul 27, 2005 10:28 am
Posts: 135
Location: SCEE London
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

Top

 Post subject: Re: Soft bodies early previewPosted: Sat Mar 22, 2008 1:32 pm

Joined: Mon Nov 13, 2006 1:44 am
Posts: 78
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.

Top

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

#### Who is online

Users browsing this forum: No registered users and 0 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