## Re: [Algorithms] Approximating collision times

 Re: [Algorithms] Approximating collision times From: Adam Paul Coates - 2002-12-28 22:00:57 ```Okay - I have the paper in a box somewhere - I'll double check that. I'm using GJK, which doesn't mind too much when the objects penetrate, and the contact plane computation doesn't worry about penetration either, so whatever it is, penetration shouldn't be a problem, so long as it's small. I've implemented an impulse based system before and found the same slowdown (Yuck!) I'm looking more along the lines of Baraff's constraint schemes - having glanced at Tokamak, it looks like you're handling resting contact very well - is this based on Baraff's QP formulation? Right now, I'm solving things iteratively, but it's not the most robust scheme; just curious :) Thanks for the notes, I'll check it out! Adam C. On Sat, 28 Dec 2002, David Lam - Tokamak wrote: > I haven't look at Stephane Redon's work so I cant comment on that.
But I have worked on the Impulse scheme by Brian Mirtich. If you haven't
http://www.cs.berkeley.edu/~jfc/mirtich/impulse.html
; It describes a scheme for estimating the Time of Impact (TOI) by using
the following information:
-objects' dynamic information (linear and angular velocity)
-shortest distance between the 2 objects (using CD algoritm called Lin-Canny)
-bounding radius of the 2 objects
In practice, when use in games, this scheme suffer a few problems.
In particular, when 2 objects are in near static contact, you get a series of
very small time-steps, causing your simulator to slow down alot. And precision
problem could also cause your objects to have penetrated when at the TOI.
So I would recommend that when using Impulse, have a minimum time-step
plus a back-stepping scheme as well.
David Lam
http://www.tokamakphysics.com
; ```

 Re: [Algorithms] Approximating collision times From: David Lam - Tokamak - 2002-12-28 12:05:43 Attachments: Message as HTML ```SSBoYXZlbid0IGxvb2sgYXQgU3RlcGhhbmUgUmVkb24ncyB3b3JrIHNvIEkgY2FudCBjb21tZW50 IG9uIHRoYXQuDTxicj4KQnV0IEkgaGF2ZSB3b3JrZWQgb24gdGhlIEltcHVsc2Ugc2NoZW1lIGJ5 IEJyaWFuIE1pcnRpY2guIElmIHlvdSBoYXZlbid0DTxicj4Kc2VlbiBpdCBhbHJlYWR5IGhlcmUn cyB0aGUgbGluaw08YnI+Cmh0dHA6Ly93d3cuY3MuYmVya2VsZXkuZWR1L35qZmMvbWlydGljaC9p bXB1bHNlLmh0bWwNPGJyPgpJdCBkZXNjcmliZXMgYSBzY2hlbWUgZm9yIGVzdGltYXRpbmcgdGhl IFRpbWUgb2YgSW1wYWN0IChUT0kpIGJ5IHVzaW5nIA08YnI+CnRoZSBmb2xsb3dpbmcgaW5mb3Jt YXRpb246DTxicj4KLW9iamVjdHMnIGR5bmFtaWMgaW5mb3JtYXRpb24gKGxpbmVhciBhbmQgYW5n dWxhciB2ZWxvY2l0eSkNPGJyPgotc2hvcnRlc3QgZGlzdGFuY2UgYmV0d2VlbiB0aGUgMiBvYmpl Y3RzICh1c2luZyBDRCBhbGdvcml0bSBjYWxsZWQgTGluLUNhbm55KQ08YnI+Ci1ib3VuZGluZyBy YWRpdXMgb2YgdGhlIDIgb2JqZWN0cw08YnI+CkluIHByYWN0aWNlLCB3aGVuIHVzZSBpbiBnYW1l cywgdGhpcyBzY2hlbWUgc3VmZmVyIGEgZmV3IHByb2JsZW1zLg08YnI+CkluIHBhcnRpY3VsYXIs IHdoZW4gMiBvYmplY3RzIGFyZSBpbiBuZWFyIHN0YXRpYyBjb250YWN0LCB5b3UgZ2V0IGEgc2Vy aWVzIG9mDTxicj4KdmVyeSBzbWFsbCB0aW1lLXN0ZXBzLCBjYXVzaW5nIHlvdXIgc2ltdWxhdG9y IHRvIHNsb3cgZG93biBhbG90LiBBbmQgcHJlY2lzaW9uDTxicj4KcHJvYmxlbSBjb3VsZCBhbHNv IGNhdXNlIHlvdXIgb2JqZWN0cyB0byBoYXZlIHBlbmV0cmF0ZWQgd2hlbiBhdCB0aGUgVE9JLg08 YnI+ClNvIEkgd291bGQgcmVjb21tZW5kIHRoYXQgd2hlbiB1c2luZyBJbXB1bHNlLCBoYXZlIGEg bWluaW11bSB0aW1lLXN0ZXANPGJyPgpwbHVzIGEgYmFjay1zdGVwcGluZyBzY2hlbWUgYXMgd2Vs bC4NPGJyPgpEYXZpZCBMYW0NPGJyPgp3d3cudG9rYW1ha3BoeXNpY3MuY29tDTxicj4K ```
 Re: [Algorithms] Approximating collision times From: Adam Paul Coates - 2002-12-28 22:00:57 ```Okay - I have the paper in a box somewhere - I'll double check that. I'm using GJK, which doesn't mind too much when the objects penetrate, and the contact plane computation doesn't worry about penetration either, so whatever it is, penetration shouldn't be a problem, so long as it's small. I've implemented an impulse based system before and found the same slowdown (Yuck!) I'm looking more along the lines of Baraff's constraint schemes - having glanced at Tokamak, it looks like you're handling resting contact very well - is this based on Baraff's QP formulation? Right now, I'm solving things iteratively, but it's not the most robust scheme; just curious :) Thanks for the notes, I'll check it out! Adam C. On Sat, 28 Dec 2002, David Lam - Tokamak wrote: > I haven't look at Stephane Redon's work so I cant comment on that.
But I have worked on the Impulse scheme by Brian Mirtich. If you haven't
http://www.cs.berkeley.edu/~jfc/mirtich/impulse.html
; It describes a scheme for estimating the Time of Impact (TOI) by using
the following information:
-objects' dynamic information (linear and angular velocity)
-shortest distance between the 2 objects (using CD algoritm called Lin-Canny)
-bounding radius of the 2 objects
In practice, when use in games, this scheme suffer a few problems.
In particular, when 2 objects are in near static contact, you get a series of
very small time-steps, causing your simulator to slow down alot. And precision
problem could also cause your objects to have penetrated when at the TOI.
So I would recommend that when using Impulse, have a minimum time-step
plus a back-stepping scheme as well.
David Lam
http://www.tokamakphysics.com
; ```