Real-Time Physics Simulation Forum

Re: Continuous Collision Detection and Interpenetration

2011-07-26T09:21:01+00:00

Are there english versions of those pdf's around as well for the majority (i think?) of people that don't speak portugeese/spanish.
A bit silly to not do a tech paper in english, but thats a whole other discussion

Statistics: Posted by Karrok — Tue Jul 26, 2011 9:21 am

Re: Continuous Collision Detection and Interpenetration

2011-02-01T15:01:19+00:00

I found this very interesting proyects in Spain:

Collision Detection and Interpenetration using simplicial coverings, JJ Jimenez Delgado's PhD thesis:
http://hera.ugr.es/tesisugr/16446665.pdf

GPUs: Rigid Body Simulation, by Alvaro del Monte Freitas:
http://eprints.ucm.es/10093/1/GPUs_Rigi ... lation.pdf

I've been using the principles of Collision Detection to develop a library for Blender like the existing http://gts.sourceforge.net/.

I belive i'll finish it by the end of the year.

Statistics: Posted by victoriaw — Tue Feb 01, 2011 3:01 pm

Re: Continuous Collision Detection and Interpenetration

2010-04-06T03:40:57+00:00

Hello:

I was doing some research into the collision detection algorithms and came into this:

http://www.sofa-framework.org/download

Sofa is an European project developing simulation tools for medical purposes.
Very interesting indeed.
They have also physics engine but, most interestingly, they present a whole different approach to collision detection:

http://www-ljk.imag.fr/Publications/Bas ... e/main.pdf

It is based not on vectorial projections of the bounding volumes but on images processed on the GPU...and they claim it is very quick...

I hope someone will find this new approach as interesting as I did...

Ra

Statistics: Posted by ndujar — Tue Apr 06, 2010 3:40 am

Re: Continuous Collision Detection and Interpenetration

2007-09-27T12:47:04+00:00

Erwin,

I didn't want to open yet another thread on this ancient topic so I hope this relatively generic thread is appropriate for my question.

I have just found your draft paper http://www.continuousphysics.com/Bullet ... ection.pdf, and your comments that you will return to the CCD problem later this year. Its getting relatively late in the year and I am wondering if you are interested to make some revisions to the above paper. In general I would be interested in some text from you comparing the techniques you list as previous work, and why you did not decide to go with some of the methods that you mention.

Best regards from Zurich,

Adam

Statistics: Posted by Adam Moravanszky — Thu Sep 27, 2007 12:47 pm

Re: Continuous Collision Detection and Non-penetration

2005-11-21T23:50:32+00:00

In conclusion, continuous collision detection in terms of interpolation methods already exist in the world of dynamics, all though the n-body problem is awkward.
/Kenny

Please visit the topic on Kinetic Sweep and Prune for a solution to remove/reduce the awkwardness of the n-body continuous collision detection:

http://www.continuousphysics.com/Bullet ... .php?t=178

Statistics: Posted by Guest — Mon Nov 21, 2005 11:50 pm

Re: Continuous Collision Detection and Non-penetration

2005-07-23T02:40:23+00:00

The idea of continuous collision detection in the game animation world is as far as I know rather new. I only know of Havok and Novodex who do it right now.

Whilst I'm no physics expert, I can say that we used continuous collision in Carmageddon TDR2000 which was started in 1998 - I'm not sure if that ranks as 'new' or not? Actually, we used it prior to that in a little known Australian game called 'Dick Johnson's Touring Car Challenge'. I think Carmageddon 2 (not developed by us) used continuous collision too, but I can't be sure - so they pre-date our use of it.

In our implementation we didn't model rotation between timesteps and the collision sweeping was mostly linear. The solver used Gaussian elimination and was impulse based, and certainly worked well enough for us at the time. In all honestly, I don't know much more than this, as I wasn't the physics/collision guy (I did the renderer).

FYI, I know that TrueAxis physics middleware uses continuous collision, and the guy that did our Carmageddon physics and collision is the brains behind it.

Cheers,
Mark

Statistics: Posted by Mark Wayland — Sat Jul 23, 2005 2:40 am

Re: Gauss' least contraint principle

2005-07-19T11:16:00+00:00

On the other hand in most configurations (in my experience) the number of contact points is often some constant times the number of objects (10 n, works great for me when I pre-allocate storage for contacts:-)

Yes, plus using continuous collision detection typically reduces the number of contact points greatly, because you maintain the objects slightly separated, and because at most 6 contacts points can be independent between any two objects (since there are six degrees of relative freedom)

Statistics: Posted by Stephane Redon — Tue Jul 19, 2005 11:16 am

Continuous Collision Detection and Interpenetration

2005-07-19T06:46:12+00:00

Not true in my opinion. the TOI can still be correctly calculated. However more internal iterations are needed, so the calculation is more expensive.

Sure you can make more internal iterations. However, you need to control how many iterations you are willing to take. You have the same problems and tradeoffs as in every iterative root search algorithm.

So, yes you can get a accurate TOI within some pre-scribed epsilon, but can you make a guarantee to always deliver the result within say 5 iterations?

Another problem with taking internal iterations is that this may be a source to parameter tuning. I am a strong beliver in trying to create out-of-the-box simulators. In the sense they work and deliver high-performance no matter what you throw in their face. As an example many physics game-engines are known for requiring people to manually tweak mass-ratios and external forces, in order to not cause blow-up, and do I need to say anything about penalty methods:-)

Don't agree. Basically the error of the solver has to be within the envelope/tolerance. A pivoting solver should bound the error properly. If your solver is an iterative solver all you need to to for a higher stack is increase the number of iterations, or increase the quality another way (preconditioning). So it just becomes a bit slower, but hey, you wanted higher stack. Just add a multiprocessor machine to the task. Another solution, which DOOM3 uses is to never integrate the position into penetration. This leads to visible delays, but doesn't cause a halt.

It seems to me that you are making the assumption that we are talking about constraint based simulation. I am not, I was talking generally about how TOIs behave.

In a high stack boxes at the bottom tend to be squezed more closely together (smaller separation) than in the top. This means separation distances go to zero while the frequency of impulse trains go up. Of course in the limit such contacts are ``resting'' (static) contacts and it make sense to deal with these using constraint based simulation.

So, I guess the question here is how to combine a constraint-based simulation and a conservative advancement scheme based on TOIs. I assume that you would ignore TOIs from static constacts and only consider dynamic (colliding) contacts.

The problem with this, as I see it, is how do you determine what contacts are static? Of course you can exploit the results from you constraint solver to do this, but please elaborate on this:-)

Regarding your comments on performance and quality. Iterative methods based on matrix splitting all have linear convergence. This sucks big time moreover you can not predict the actual convergence speed, since it varies depending on your configuration. Besides, finding a preconditioner for a matrix-splitting scheme is difficult (I have tried for some time:-) especially since methods such as Gauss-Seidel and Jacobi are preconditioners themselves (lookup residual error correction methods). To summarize, using something like 10e6 iterations will not be good enough, and no preconditioner really exist.

Direct methods (i.e. pivoting methods) tend to have quadratic convergence and they are as such very attractive. However the cost of each iteration is often similar to solving a linear system.

This can be solved: Time warp splits the groups, so it is not a global dependency problem. Then again, for the small time steps, there is the envelope/tolerance which can be tweaked.

Yeah you can break dependencies between independent groups. And yes time-warp seems to be a very good idea for conservative advancement. However, I want to do simulations with 10.000 objects all being in mutally dependent contact. In such a context time-warp will just give you a big book-keeping overhead.

To summarize:

Conservative advancement based on TOIs and constraint based simulation may solve the problems Mirtich had with impulse-based simulation in this context. However I would like some details on such a scheme:-)

I have a hard time seeing how accurate TOIs can be computed while at the same time keeping a bound on performance. If an epsilon solution is used I have some difficulty in seeing that this would not end up in endless parameter tuning.

Statistics: Posted by kenny — Tue Jul 19, 2005 6:46 am

Re: Gauss' least contraint principle

2005-07-19T05:56:12+00:00

This is an (in my opinion ) extremely elegant way to formulate frictionless constrained dynamics problems. It is mathematically equivalent to the LCP approach, which formulates the problem in the contact space (since the unknowns are the contact forces and accelerations), but might have some algorithmic advantages.

I agree, a few comments though:

Interactive worlds need friction.

As I recall the formulation is done in object space, which may be advantageous since the number of objects is likely to be much smaller than the number of contact points. However you need to run collision detection to detect the contacts in the first place, so the overall performance (I believe) of such a simulator is going to be dominated by the number of contact points anyway.

On the other hand in most configurations (in my experience) the number of contact points is often some constant times the number of objects (10 n, works great for me when I pre-allocate storage for contacts:-)

Statistics: Posted by kenny — Tue Jul 19, 2005 5:56 am

Re: Continuous Collision Detection and Non-penetration

2005-07-19T05:44:29+00:00

If "continuous collision detection" means ensuring that no collision will be missed, and the contact time will be computed, then some references above might not be exactly continuous... snip...again, maybe a definition problem?

Good point; I was working with the definition: Given two instances in time (starting and ending frames) what goes on inbetween? In that sense the cited people in my previous post all did work related to that question.

Statistics: Posted by kenny — Tue Jul 19, 2005 5:44 am