## RE: [Algorithms] Distance between box and triangle

 RE: [Algorithms] Distance between box and triangle From: - 2004-11-29 17:29:27 ```From what I understand (haven't looked at Minkowski differences or GJK until now), GJK is just an optimization so that you don't have to check the distance to the entire convex hull of the Minkowski Difference. Since speed is not that important am I correct in assuming that the following code would be the easiest to implement: 1. Find the set of differences between the triangle and the box 2. Form the convex hull of this set 3. Find the shortest distance to the origin from the convex hull /A.B. -----Original Message----- From: Paul_Firth@... [mailto:Paul_Firth@...] Sent: den 29 november 2004 17:37 To: gdalgorithms-list@... Subject: Re: [Algorithms] Distance between box and triangle gdalgorithms-list-admin@... wrote on 29/11/2004 16:12:47: > Have you looked at Minkowski sums? I used to have a really good web link for > graphical examples using Java but have since lost it. :( I'm sure it came > from this list though. I have a page at http://www.pfirth.co.uk/collision.html and http://www.pfirth.co.uk/minkowski.html which might be of use... :-) If you only want positive distance, GJK will be the fastest way to compute this. Probably. If not, you could either explicitly form the MD from the two shapes and take the minimum from the origin to each face of the MD as the minimum distance between the two, or you could use Gino van den Bergen's EPA algorithm (which is similar to GJK and takes the output of GJK as its input). Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify postmaster@... This footnote also confirms that this email message has been checked for all known viruses. ********************************************************************** Sony Computer Entertainment Europe ------------------------------------------------------- SF email is sponsored by - The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://productguide.itmanagersjournal.com/ _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 ########################################### This message has been scanned by F-Secure Anti-Virus for Microsoft Exchange. For more information, connect to http://www.F-Secure.com/ ```

 RE: [Algorithms] Distance between box and triangle From: Davies, Matt - 2004-11-29 16:38:52 ```Hi, the site you might be referring to is: http://www.pfirth.co.uk/collision.html Cheers Matt Davies -----Original Message----- From: Martin Piper [mailto:martin.piper@...] Sent: 29 November 2004 16:13 To: gdalgorithms-list@... Subject: Re: [Algorithms] Distance between box and triangle Have you looked at Minkowski sums? I used to have a really good web link for graphical examples using Java but have since lost it. :( I'm sure it came from this list though. Martin Piper http://www.ReplicaNet.com - Network middleware powering games. ----- Original Message ----- From: To: Sent: Monday, November 29, 2004 3:54 PM Subject: [Algorithms] Distance between box and triangle > Hi, > > does anyone know where I can find code that computes the distance between a > box and a triangle. I was first thinking about extending David Eberly's > rectangle to triangle distance code, but I think the original code is too > long as it is (every case written out explicitely). I'm also thinking about > formulating the problem as a quadtratic programming problem with constraints > but haven't been able to find a small free solver that is easy to integrate > into my code. Any pointers would be much appreciated. > > /A.B. > ########################################### > > This message has been scanned by F-Secure Anti-Virus for Microsoft Exchange. > For more information, connect to http://www.F-Secure.com/ > > > ------------------------------------------------------- > SF email is sponsored by - The IT Product Guide > Read honest & candid reviews on hundreds of IT Products from real users. > Discover which products truly live up to the hype. Start reading now. > http://productguide.itmanagersjournal.com/ > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 ------------------------------------------------------- SF email is sponsored by - The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://productguide.itmanagersjournal.com/ _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 _____________________________________________________________________ This e-mail has been scanned for viruses by MCI's Internet Managed Scanning Services - powered by MessageLabs. For further information visit http://www.mci.com --- Incoming mail is certified Virus Free. Checked by AVG anti-virus system (http://www.grisoft.com). Version: 6.0.801 / Virus Database: 544 - Release Date: 24/11/2004 --- Outgoing mail is certified Virus Free. Checked by AVG anti-virus system (http://www.grisoft.com). Version: 6.0.801 / Virus Database: 544 - Release Date: 24/11/2004 ```
 RE: [Algorithms] Distance between box and triangle From: - 2004-11-29 17:29:27 ```From what I understand (haven't looked at Minkowski differences or GJK until now), GJK is just an optimization so that you don't have to check the distance to the entire convex hull of the Minkowski Difference. Since speed is not that important am I correct in assuming that the following code would be the easiest to implement: 1. Find the set of differences between the triangle and the box 2. Form the convex hull of this set 3. Find the shortest distance to the origin from the convex hull /A.B. -----Original Message----- From: Paul_Firth@... [mailto:Paul_Firth@...] Sent: den 29 november 2004 17:37 To: gdalgorithms-list@... Subject: Re: [Algorithms] Distance between box and triangle gdalgorithms-list-admin@... wrote on 29/11/2004 16:12:47: > Have you looked at Minkowski sums? I used to have a really good web link for > graphical examples using Java but have since lost it. :( I'm sure it came > from this list though. I have a page at http://www.pfirth.co.uk/collision.html and http://www.pfirth.co.uk/minkowski.html which might be of use... :-) If you only want positive distance, GJK will be the fastest way to compute this. Probably. If not, you could either explicitly form the MD from the two shapes and take the minimum from the origin to each face of the MD as the minimum distance between the two, or you could use Gino van den Bergen's EPA algorithm (which is similar to GJK and takes the output of GJK as its input). Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify postmaster@... This footnote also confirms that this email message has been checked for all known viruses. ********************************************************************** Sony Computer Entertainment Europe ------------------------------------------------------- SF email is sponsored by - The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://productguide.itmanagersjournal.com/ _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 ########################################### This message has been scanned by F-Secure Anti-Virus for Microsoft Exchange. For more information, connect to http://www.F-Secure.com/ ```
 RE: [Algorithms] Distance between box and triangle From: - 2004-11-30 12:01:58 ```gdalgorithms-list-admin@... wrote on 29/11/2004 17:30:05: > From what I understand (haven't looked at Minkowski differences or GJK until > now), GJK is just an optimization so that you don't have to check the > distance to the entire convex hull of the Minkowski Difference. Since speed > is not that important am I correct in assuming that the following code would > be the easiest to implement: > > 1. Find the set of differences between the triangle and the box > 2. Form the convex hull of this set > 3. Find the shortest distance to the origin from the convex hull Mmmm, good question. Maybe not - the vertex vs face and face vs vertex cases are really simple (just the same as in 2d on my page), but when it comes down to edge vs edge it gets more complex; Only a subset of all edge vs edge combinations form MD faces which lie on the convex hull of the MD. To detect which pairs you need, you must do some maths to test for intersection of the great arcs formed by the dual space projection of the edges onto the unit sphere. This sounds like a nightmare, but its not too bad actually. Once you find the edges in question they form faces of the MD just like the vertex face pairs did, and then its the minimum distance to each. Of course, as others have noted: if you don't need penetration distance (i.e. only you need only positive distance), then you can just take the minimum of distance between feature pairs of triangle and box. Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify postmaster@... This footnote also confirms that this email message has been checked for all known viruses. ********************************************************************** Sony Computer Entertainment Europe ```
 RE: [Algorithms] Distance between box and triangle From: Per Vognsen - 2004-11-29 17:34:44 ```> -----Original Message----- > From: gdalgorithms-list-admin@... [mailto:gdalgorithms- > list-admin@...] On Behalf Of Andreas.Brinck@... > Sent: Monday, November 29, 2004 12:30 PM > To: gdalgorithms-list@... > Subject: RE: [Algorithms] Distance between box and triangle >=20 > From what I understand (haven't looked at Minkowski differences or GJK > until > now), GJK is just an optimization so that you don't have to check the > distance to the entire convex hull of the Minkowski Difference. Since > speed > is not that important am I correct in assuming that the following code > would > be the easiest to implement: No. Explicitly computing the Minkowski sum is a lot of work. One of the nice things about GJK is that it never explicitly computes the Minkowski sum. > 1. Find the set of differences between the triangle and the box > 2. Form the convex hull of this set > 3. Find the shortest distance to the origin from the convex hull Per ```
 RE: [Algorithms] Distance between box and triangle From: Richard Mitton - 2004-11-29 17:42:50 ```1) Split box into triangles 2) For each triangle in box: Perform triangle-triangle distance check And, to perform a triangle-triangle distance check: http://www.magic-software.com/Source/Distance/WmlDistTri3Tri3.cpp "Haven't Tried It Though" (tm) -- ()() Richard Mitton .:. rmitton@... ( '.') (")_(") xbox jester .:. climax action [kingston] > -----Original Message----- > From: gdalgorithms-list-admin@... > [mailto:gdalgorithms-list-admin@...] On > Behalf Of Andreas.Brinck@... > Sent: 29 November 2004 15:55 > To: gdalgorithms-list@... > Subject: [Algorithms] Distance between box and triangle > > Hi, > > does anyone know where I can find code that computes the > distance between a box and a triangle. I was first thinking > about extending David Eberly's rectangle to triangle distance > code, but I think the original code is too long as it is > (every case written out explicitely). I'm also thinking about > formulating the problem as a quadtratic programming problem > with constraints but haven't been able to find a small free > solver that is easy to integrate into my code. Any pointers > would be much appreciated. > > /A.B. > ########################################### > > This message has been scanned by F-Secure Anti-Virus for > Microsoft Exchange. > For more information, connect to http://www.F-Secure.com/ > > > ------------------------------------------------------- > SF email is sponsored by - The IT Product Guide Read honest & > candid reviews on hundreds of IT Products from real users. > Discover which products truly live up to the hype. Start reading now. > http://productguide.itmanagersjournal.com/ > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > ```