Re: [Algorithms] Computing the penetration distance

[Jamie F. <j.f...@re...>]

Possible problem there: P and Q may not be the points you're interested in next
time round. Probably a decent enough approximation most of the time, but worth
bearing in mind.

Also, I'm fairly sure there's no efficiency problem with step 3: affine
transformations can be included transparently in the GJK calculation (IIRC, Gino
van den Bergen's paper explains quite well). And if you've got efficient
adjacency structures and temporal coherence, there shouldn't be any need for
discarding vertices for step 4, 'cos your cached points will be almost correct.

I think :)

Jamie


Pierre Terdiman wrote:

> Uh, and I missed it ? ....ahem. Thanks.
>
> Else I think I can do something like that:
> 1) on collision, compute the closest points P and Q, and the separating
> plane H from previous frame
> 2) compute two planes parallel to H, one of them contains P's new position,
> the other contains Q's new position
> 3) reflect the two objects through the two planes
> 4) compute the closest points with GJK, for the two reflected objects. The
> penetration distance is the distance between those two new closest points.
>
> Now, the problem is to do 3) efficiently, discarding some useless vertices
> on the fly so that 4) is fast as well.
>
> Pierre
>
> ----- Original Message -----
> From: Jamie Fowlston <j.f...@re...>
> To: <gda...@li...>
> Sent: Wednesday, October 11, 2000 9:48 PM
> Subject: Re: [Algorithms] Computing the penetration distance
>
> > There's a modified GJK which returns penetration under some circumstances;
> bit
> > rushed for time at the mo, but I think you can get it (or at least
> something
> > relatedly interesting :) from
> >
> > http://users.comlab.ox.ac.uk/stephen.cameron/distances.html
> >
> > 3rd reference.
> >
> > Jamie
> >
> >
> > Pierre Terdiman wrote:
> >
> > > Ok,
> > >
> > > Before diving into the funny hell of LCP programs and all those painful
> > > little things, I'd give penalty methods a chance - à la David Wu. So, I
> need
> > > to estimate (or better, compute accurately) the penetration distance
> > > between, say two convex polytopes, even if it would be better if I were
> able
> > > to derive it for any pair of non-convex objects.
> > >
> > > GJK gives you the closest-points and the exact distance when no
> collision
> > > occurs. But all bets are off when the polytopes collide. I've looked
> into my
> > > archives, and I don't have the faintest, slightest, little reference
> > > regarding that topic. Hence, before cooking up my own wacked solution, I
> > > feel obliged to ask the list : would you have one or two links for
> me...?
> > >
> > > Thanks, list.
> > >
> > > Pierre
> > >
> > > PS: don't bother telling me to forget penalty methods.
> > >
> > > _______________________________________________
> > > GDAlgorithms-list mailing list
> > > GDA...@li...
> > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> >
> > -Virus Scanned and cleared ok
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

-Virus Scanned and cleared ok