# Physics Simulation Forum

 Page 2 of 2 [ 29 posts ] Go to page Previous  1, 2
 Print view Previous topic | Next topic
Author Message
 Posted: Wed Aug 11, 2010 8:24 am

Joined: Sat Sep 05, 2009 12:26 pm
Posts: 19
fishboy82 wrote:
Nisse and XperienS：
I only know to use CG to solve linear eqaution but don't know how to use it solve LCP,
Could you refer me some Material how to use active set in CG method to solve LCP with unilateral contacts and box constraint like friction？

I guess we are all looking for ways to do that. The paper by Morten Silcowitz-Hansen, Sarah Niebe and Kenny Erleben describes one way - although it doesn't seem fully parallelizable as it involves one GS iteration (LCP solve) in each CG iteration.

Top

 Posted: Thu Aug 12, 2010 9:07 am

Joined: Thu May 18, 2006 9:25 pm
Posts: 26

Yes, all the stuff is coupled into a single system that is PD LCP with box constraints. The parallelizable solver we use is a CG-like LCP solver, not CG itself. It is in fact our extension to a not-well-known optimization algorithm.

Top

 Posted: Thu Aug 12, 2010 9:39 am

Joined: Fri Nov 25, 2005 10:09 am
Posts: 34
Dirk Gregorius
> This is not due to PGS, but due to the stabilization method when solving on the velocity level.
Maybe there's some misunderstanding, I'm telling about FEM systems with high Young's module, and there is no stabilization (it is used for stiff joints such as ball-in-socket and etc.). Actually, we're solving exactly same system with PGS (and it cannot converge within 1000 iterations) and with our solver (it converges to given precision within 150 iterations), so it really seems like instabilities comes from the solver.

Top

 Posted: Thu Aug 12, 2010 12:31 pm

Joined: Sun Jul 03, 2005 4:06 pm
Posts: 756
Location: Bellevue, WA
Ok, I thought you were refering to the rigid-body dynamics. One question I was always thinking about. Did you try to compute the exact solution with CG and then use warmstarted PGS for the actual simulation? I was wondering if the deformation was small PGS might be good enough to cover this.

Top

 Posted: Thu Aug 12, 2010 1:47 pm

Joined: Fri Nov 25, 2005 10:09 am
Posts: 34
Dirk Gregorius
I can't fully understand, what do you mean? Solving on each simulation step only FEM joints with CG and then use this data as warmstarting for full system solved with PGS? Although, we didn't try anything like this, we wanted to solve coupled system. Btw, computing exact solution with CG is not quite possible due to FP-errors.

Top

 Posted: Thu Aug 12, 2010 2:49 pm

Joined: Sun Jul 03, 2005 4:06 pm
Posts: 756
Location: Bellevue, WA
Basically I was thinking of this. You solve the initial system using CG to get a solution within some tolerance. For the next solves you use PGS which is warmstarted with the result from the last frame. Since you have a very good initial solution and if the system is only deforming slowly the results might be good enough.

-Dirk

Top

 Posted: Fri Aug 13, 2010 12:23 pm

Joined: Fri Nov 25, 2005 10:09 am
Posts: 34
Dirk Gregorius
So, you want to solve the system once to get starting initial guess? That might be a good idea for some kind of simulations (e.g. for smooth deformations), but I assume not for interactive ones. Consider a falling body: when sim starts, it has zero strain, hence zero stress. Your IG is 0, and then, as it hits the floor, strain raises roughly. Here, if body's material is stiff enough, we could get with PGS instabilities mentioned above; so if we want to have some guarantees that our sim won't explode, this approach is not very good. Example I presented is quite simple, but same stuff could happen if we pull a body with some ball-socket chain or just apply high force/impulse to a free node of the body. Also, if you propose to use simple CG (w/o any additional actions), it can fail to calculate correct IG if there's limits introduced in the initial configuration.

Top

 Posted: Mon Mar 21, 2011 11:26 am

Joined: Fri Nov 25, 2005 10:09 am
Posts: 34
Sorry guys for such long delay! We wanted to write a full paper with all the proofs and stuff, but after a year of wasted time we realized that we're quite limited on time. Although, we wanted to share the idea with you, so we quickly wrote a sketch which introduces main concepts of our recent research. Hope you'll find it useful. If you'll have suggestions/corrections, please share with us in this forum thread (you can find a link to the sketch there too).

Top

 Posted: Sun Aug 05, 2012 11:37 pm

Joined: Sat Jun 25, 2011 9:11 am
Posts: 4
Location: Trondheim, Norway
XperienS wrote:
fishboy82
About the paper: right now we have only our old paper in Russian

Hi XperienS,

Are you still working on this? It would be great if you shared your latest findings/results as well as publications. We are looking for a software which could handle combined FEM/rigid body simulations and your work in this direction is very impressive. Depending on the state of the work we could discuss some research or commercial collaboration

Could you please also share the Russian version of your paper and possibly other publications on this topic in Russian, if available? I'm sure we'll find someone to interpret it

Top

 Posted: Fri Aug 24, 2012 1:05 pm

Joined: Sun Dec 03, 2006 12:40 am
Posts: 53
Hmm, I don't find a link to a paper. What am I missing?

I also just wanted to comment about PGS. It was previously in this thread stated that PGS provides smooth convergence with improving results for each iteration. There is no guarantee for this. PGS can be noisy and cyclic, and also completely stop converging and just fluctuate around the same error. Obviously, it can also diverge!
If it at all works, it typically gives some convergence for the first 1-30 iterations in MBD problems, but beyond this it is notoriously inefficient and doesn't improve that much even for hundreds or even thousands of iterations. This of course all depends on the spectral radius of the problem and the nature of the LCP, but my general experience is that it sucks for anything but perhaps large contact systems, where few other methods can be used at all.

Top

 Posted: Mon Aug 27, 2012 8:30 pm

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3744
Location: California, USA
KenB wrote:
If it at all works, it typically gives some convergence for the first 1-30 iterations in MBD problems, but beyond this it is notoriously inefficient and doesn't improve that much even for hundreds or even thousands of iterations.

In my experience, decreasing/subdividing the time step seems to help improve convergence of PGS better than increasing the number of iterations.
Is that something you looked into?

Top

 Posted: Mon Aug 27, 2012 9:46 pm

Joined: Tue Feb 20, 2007 4:56 pm
Posts: 179
KenB wrote:
This of course all depends on the spectral radius of the problem and the nature of the LCP, but my general experience is that it sucks for anything but perhaps large contact systems, where few other methods can be used at all.

I don't know that it necessarily "sucks", but it's fairly well known that PGS has the general limitation that mass ratios should be kept near unity, and that a long chain of stiff constraints is going to take an unacceptably long time to converge. On the other hand, part of the reason it works so well for contact systems is because it seamlessly handles over-constrained systems.

Top

 Posted: Fri Aug 31, 2012 12:15 am

Joined: Fri Nov 25, 2005 10:09 am
Posts: 34
IvarHeyguen
> Are you still working on this? It would be great if you shared your latest findings/results as well as publications.
Sorry, but we abandoned the project quite a long time ago; we had some results like working GPU-accelerated simulator (you can see the demos at the beginning of the thread), but that is basically all that we have.

> Could you please also share the Russian version of your paper and possibly other publications on this topic in Russian, if available? I'm sure we'll find someone to interpret it
Of course, glad you're interested _Link_. Sorry for the total lack of markup there, this is kind of draft. Please, do not hesitate to ask if you'll have questions (better via e-mail, we do not visit the forums too frequently).

KenB
> Hmm, I don't find a link to a paper. What am I missing?
There is actually no link to the paper, because we didn't manage to translate it from russian. We only have a paper on CG-based solver _here_ along with the source code, and the paper mentioned above. The thing is, at the end we came up with almost the same formulation as Servin et al. (I cannot remember details right now, probably adding corotation or maybe decomposition for easier solver implementation, or something), so if you're interested, you can look at their paper and our source code.

> I also just wanted to comment about PGS ... Obviously, it can also diverge!
For most constraint dynamic formulations (for our combined rigid body/FEM) the convergence of PGS has solid proof in Murty's LCP webbook (well he doesn't prove anything for rigid bodies of course our system just satisfies convergence conditions), but indeed PGS convergence is unsatisfactory for our problem, that's why we developed CG-based box MLCP solver for our case (based on Dostal's work).

> It was previously in this thread stated that PGS provides smooth convergence with improving results for each iteration. There is no guarantee for this
Most likely, it was stated for GS (LS, not LCP solver, for which, each iteration is effectively transforming the error term by iteration matrix, hence if the spectral radius for this "iteration" matrix - not the original one - is < 1 then GS converges, and provides smooth convergence curve), for PGS, projection I think can spoil the picture with some spiking, but it should be anyway below some conservative bound if convergence criterion is satisfied, and the projected gradient norm will be a lot smoother than the one for CG-based solvers (based on empiric results).

> but my general experience is that it sucks for anything but perhaps large contact systems, where few other methods can be used at all
Agreed I think I mentioned that earlier, for some large FEM systems with not-so-much contacts, PGS fails and requires more than a thousand iterations (esp. considering its "the more iterations, the less convergence steps"), again - that is why we decided to use another solver.

Top

 Posted: Fri Aug 31, 2012 10:46 am

Joined: Thu May 18, 2006 9:25 pm
Posts: 26
IvarHeyguen,

it's not even a paper but a draft that even lacks propper formatting. But our approach turned to be very similar to http://www.physics.umu.se/digitalAssets ... sigrad.pdf paper, so perhaps you can first read it. We used a different solver, however, based on Dostal's MPRGP solver. And we used co-rotation and some plasticity tricks like Mueller describes. Also we derived the contsrints in some way different from the paper mentioned above, and I am still not sure if there is any significant difference in the resulting formulas. Also we algebraically diagonalized the constraint-force mixing matrix (the force-dependent multiplier in the constraint formulation), which naively appears to be tridiagonal, but we did so for the specific Hooke's law formulation that is valid for isotropic materials only. Also we used regularization to avoid numerical instability at degenerate solutions..

Top

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

#### Who is online

Users browsing this forum: Google Feedfetcher and 1 guest

 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