[ODE] Collisions via Minkowski sums

[Thomas Harte]

This message is in MIME format. Since your mail reader does not understand
this format, some or all of this message may not be legible.

--=_NextPart_Lycos_0308281048945453_ID
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit

Important disclaimer: I'm new to this stuff, and if I state something that 
seems to demonstrate a gross misunderstanding of the mathematics, 
then I have probably grossly misunderstood the mathematics.

John DeWeese:
>It would be a good idea to say what your purposes are, and why you 
must  
>roll your own. Perhaps someone else can lend some insight to the  
>original problem. Tell! Tell!

Well, besides anything else I would like to implement this myself at least 
once for educative reasons, but also it stands to reason that I can do a 
better job with knowledge of the specifics of my engine than a general 
case algorithm can.

In my game dynamic objects are represented by oriented bounding box 
hierarchies (which are generated automatically as a preprocessing step) 
and the static world is a polygon soup which has been octree'd. Besides 
anything else I believe that neither ODE nor tri-collider will help me with 
any sort of hierarchical collision geometry.

>Anyway, Minkowski hulls have some significant limitations. 

I'll respond to these out of order, so excuse the funny quoting...

>Second, since the  
>Minkowsky hull is a pair-wise algorithm, so you must compute a new 
hull  
>for every possible shape you collide with

In one sense this is true, but you implicitly overstate the problem 
slightly. In my game engine, the Minkowski stuff is done only as a final 
processing step - when it is certainly known that two objects overlap. 
Before getting that far a whole host of other tests offer quick 
throwaways if possible. To be entirely specific:

For dynamic objects against dynamic objects, such objects are only 
tested against those which are in the same or a neighbouring node of 
the static level octree. The next test is bounding spheres, which is 
another thing all of my dynamic objects have. As a final attempt to 
avert a full Minkowski thing, the seperating planes test is applied.

Whel testing dynamic objects against the static world, a test against 
every polygon at the relevant octree node is performed. In my engine, 
since dynamic objects tend to be 'small', octree nodes actually overlap a 
little so that only one need be checked in this instance, rather than 
having to check against two if the dynamic object were lying over a 
node boundary.

>First, they  
>are static, which is probably not a problem. . Third, the shapes must 
be  
>static, that is they cannot rotate. That's a pretty serious limitation!  
>Finally, computing a Minkowsky hull in 3D is a rather difficult  
>algorithm to code and get accurate. Maybe you can find some code 
that  
>is already fast and accurate, though.

In my case it isn't such a problem. I'm really only doing box against box 
and box against triangle for now. Unlike, e.g. spheres, the boundaries 
of these objects may be described as convex polygon meshes, so 
generating the Minkowski sum is easy and cheap enough to be done 
every time a collision occurs.

In my world there are a very small number of dynamic objects. In the 
medium term, there are only two and it would be exceptional if there 
were as many as ten in the long term. On average these will collide with 
three or four static polygons per physics update and very rarely with 
each other.

I can calculate all potential boundary bounds of the sum/CSO in 3*4 
vector subtractions. The boundary of the CSO is then the convex hull of 
these points, which I can calculate using something like Quickhull in O
(nlog n) time.

Sergio Valverde:
>Your exposition remind me the GJK algorithm for locating the closests
>points between two convex sets. There is also a paper of SOLID's 
author
>(don't remember the name, Gino I think) about finding the penetration
>depth. Anyway, those algorithms are very prone to numerical 
innacuracies
>so they require careful programming.
John DeWeese:
>BTW, when I say Minkowski hull, I'm referring to the hull operation  
>that occurs after you clip the Minkowsky sum.

Since the boundaries of my Minkowski sums are expressible in terms of 
points and planes, I can find the pentration depth (which is the point on 
the boundary closest to the origin) analytically rather than numerically. 
GJK or any derived method isn't necessary for my case, for this reason.

>BTW2, ODE can take multiple contact points, so if you find a  
>penetration region, perhaps you should put several contact points  
>randomly around that region instead of summarizing the contact with 
one  
>point.

Yeah, this is probably the best way forwards. It means being a bit 
smarter about total friction, but whatever. How do other people ensure 
consistant friction, by the way?

-Thomas

When words aren't enough - Vodafone live! A new world of colour, sounds, picture messages and information on your mobile. <a href="http://ad.doubleclick.net/clk;4909903;7724245;q?http://www.vodafone.co.uk/live">
Click here</a> to find out more.


--=_NextPart_Lycos_0308281048945453_ID
Content-Type: message/rfc822
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

Return-Path: <ode-admin@q12.org>
Received: from hook.org (dsl-ep-209-115-250-i14-cgy.nucleus.com [209.115.250.14])
	by lmin08.st1.spray.net (Postfix) with ESMTP id EEBF425015
	for <ThomasHarte@lycos.co.uk>; Thu, 27 Mar 2003 20:10:00 +0100 (MET)
Received: from webserver.computershop.calgary.ab.ca (mailman@localhost [127.0.0.1])
	by hook.org (8.12.6/8.12.6) with ESMTP id h2RItFpC008943;
	Thu, 27 Mar 2003 11:55:16 -0700 (MST)
Received: from ict.usc.edu (ict.usc.edu [128.125.133.33])
	by hook.org (8.12.6/8.12.6) with ESMTP id h2RIqopC000581
	for <ode@q12.org>; Thu, 27 Mar 2003 11:52:51 -0700 (MST)
Received: from ict.usc.edu ([192.168.192.216])
	by ict.usc.edu (8.11.6/8.11.2) with ESMTP id h2RIrUm09643
	for <ode@q12.org>; Thu, 27 Mar 2003 10:53:30 -0800 (PST)
Subject: Re: [ODE] Collisions via Minkowski sums
Content-Type: text/plain; delsp=yes; charset=US-ASCII; format=flowed
Mime-Version: 1.0 (Apple Message framework v551)
From: John DeWeese <deweese@ict.usc.edu>
To: ode@q12.org
Content-Transfer-Encoding: 7bit
In-Reply-To: <1048776154007329@lycos-europe.com>
Message-Id: <66BECD5E-6085-11D7-A951-000A27B389D4@ict.usc.edu>
X-Mailer: Apple Mail (2.551)
Sender: ode-admin@q12.org
Errors-To: ode-admin@q12.org
X-BeenThere: ode@q12.org
X-Mailman-Version: 2.0.6
Precedence: bulk
List-Help: <mailto:ode-request@q12.org?subject=help>
List-Post: <mailto:ode@q12.org>
List-Subscribe: <http://q12.org/mailman/listinfo/ode>,
	<mailto:ode-request@q12.org?subject=subscribe>
List-Id: Open Dynamics Engine Mailing List <ode.q12.org>
List-Unsubscribe: <http://q12.org/mailman/listinfo/ode>,
	<mailto:ode-request@q12.org?subject=unsubscribe>
List-Archive: <http://q12.org/pipermail/ode/>
X-Original-Date: Thu, 27 Mar 2003 10:53:30 -0800
Date: Thu, 27 Mar 2003 10:53:30 -0800

It would be a good idea to say what your purposes are, and why you must  
roll your own. Perhaps someone else can lend some insight to the  
original problem. Tell! Tell!

Anyway, Minkowski hulls have some significant limitations. First, they  
are static, which is probably not a problem. Second, since the  
Minkowsky hull is a pair-wise algorithm, so you must compute a new hull  
for every possible shape you collide with. Third, the shapes must be  
static, that is they cannot rotate. That's a pretty serious limitation!  
Finally, computing a Minkowsky hull in 3D is a rather difficult  
algorithm to code and get accurate. Maybe you can find some code that  
is already fast and accurate, though.

BTW, when I say Minkowski hull, I'm referring to the hull operation  
that occurs after you clip the Minkowsky sum.

BTW2, ODE can take multiple contact points, so if you find a  
penetration region, perhaps you should put several contact points  
randomly around that region instead of summarizing the contact with one  
point.

On Thursday, March 27, 2003, at 06:42 AM, Thomas Harte wrote:

> The built in collision stuff in ODE isn't really suitable for my  
> purposes, so
> I have been rolling my own. A little reading on the subject from  
> various
> papers across the internet has revealed that forming the Minkowski sum
> of one of my objects and the negation of the other allows me to easily
> (given that my objects are broken into convex quantities) extract, in
> ODE terms, penetration depth and contact normal.
>
> I haven't read anything on faking a contact 'point' as ODE likes to  
> think,
> so at the minute my plan is to calculate the overlap region - which
> intuition tells me will also be convex - and take the centroid of that.
>
> Has anyone on this list any experience in this sort of field? Am I  
> thinking
> along the right lines?
>
> -Thomas
>
> When words aren't enough - Vodafone live! A new world of colour,  
> sounds, picture messages and information on your mobile. <a  
> href="http://ad.doubleclick.net/clk;4909903;7724245;q?http:// 
> www.vodafone.co.uk/live">
> Click here</a> to find out more.
>

_______________________________________________
ODE mailing list
ODE@q12.org
http://q12.org/mailman/listinfo/ode



--=_NextPart_Lycos_0308281048945453_ID--