## [Algorithms] Re: 3rd person adventures - The saga continues!

 [Algorithms] Re: 3rd person adventures - The saga continues! From: - 2005-11-04 02:17:59 ```Stephane Redon's ccd is feature based, so no swept capsules there. You can use another ccd approach based on an extension of raycasting the Minkowski sum. See Gino van den Bergens paper on this topic: https://www.cmpevents.com/Sessions/GD/ContinuousCollisionDetection1.ppt Both this and Redon's method are implemented in my Bullet continuous collision detection library. It includes pure linear (swept) and angular motion too. Supported shapes are triangle, sphere,box,triangle,capsule,cylinder,cone etc. http://www.continuousphysics.com/Bullet/ Regards, Erwin Coumans Bill Baxter writes: > Have you looked at Stephane Redon's work on continuous collision detection? > I'm pretty sure he does swept capsules. He makes it tractable by assuming a > particular form for the rotation between frames, namely an exponential map. > So it's not using the "correct" rotation to represent the inter-frame > motion, but that's not such a big deal because without actually running your > simulator at finer timesteps you have no way of knowing what the correct > motion is anyway. In the end it comes out to be solutions of fairly > low-order polynomials. And I think he does some interval math / Sturm > sequence type things to avoid actually having to find the roots. > > Anyway, his stuff is worth a look if you haven't seen it already. > > --bb > > On 11/4/05, Jeremiah Zanin wrote: >> >> Swept capsule vs. triangle is pretty tricky and I haven't seen it >> documented >> anywhere. I implemented it by breaking down the problem into smaller >> problems (line segment vs plane, sphere vs plane, circle vs line segment, >> sphere vs line segment, sphere vs point). I'm not sure how to do a swept >> capsule that accounts for rotation other than relying on detecting the >> collision due to penetration. I'm wondering how many games actually use a >> swept capsule instead of a series of spheres... >> >> > >> > Usually, this (character collision i mean) is done by doing a swept (in >> > time, not space) capsule vs triangles test - but this is difficult to >> get >> > right; there are a lot of cases to deal with. Especially if your capsule >> > is rotating. >> > ... >> > Cheers, Paul. >> >> >> ```

 RE: [Algorithms] 3rd person adventures - The saga continues! From: Gino van den Bergen - 2005-11-02 14:50:02 ```Actually, you need to count independent edge directions and face normal directions. Here, two directions A and B are independent iff A !=3D = lambda * B for any positive or negative parameter lambda. So, for the triangular prism you have 4 edge directions and 4 face normal directions. This results in 2 x 4 face normal directions plus 4 x 4 edge-edge combinations which makes a total of 24 possible separating axes. A SAT of 24 axis tests is quite doable and should in most cases beat any implementation of GJK. Gino van den Bergen=20 http://www.dtecta.com -----Original Message----- From: gdalgorithms-list-admin@... [mailto:gdalgorithms-list-admin@...] On Behalf Of Paul_Firth@... Sent: Wednesday, November 02, 2005 2:22 PM To: gdalgorithms-list@... Subject: RE: [Algorithms] 3rd person adventures - The saga continues! gdalgorithms-list-admin@... wrote on 02/11/2005=20 13:08:48: > Alen, >=20 > Thanks for the explanation... So, let me see if I get this clear: >=20 > Using the example of the triangular prism, I have the following > features: >=20 > Sides: 3 x Rectangle > Top/Bottom: 2 x Triangle > Edges: 9 x Edge > Points: 6 x Point > --------------------------- > Total: 20 features >=20 > So, if I want to test the intersection of two triangular prisms, I have > to do 20x20=3D400 tests, considering every possibility, and then go around > the math, trying to join tests, etc? >=20 > Is this a correct assessement? Its feature pairs you need to count... i.e. vertex/face, face/vertex,=20 edge/edge So, 6*5 + 5*6 + 9*9 =3D 141 I think... Although some of the edge vs edge tests will be redundent. You might be better off considering using GJK for this kind of thing. Ta, 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.Net email is sponsored by: Tame your development challenges with Apache's Geronimo App Server. Download it for free - -and be entered to win a 42" plasma tv or your very own Sony(tm)PSP. Click here to play: http://sourceforge.net/geronimo.php _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 ```
 RE: [Algorithms] 3rd person adventures - The saga continues! From: Jeremiah Zanin - 2005-11-03 15:32:56 ```Swept capsule vs. triangle is pretty tricky and I haven't seen it documented anywhere. I implemented it by breaking down the problem into smaller problems (line segment vs plane, sphere vs plane, circle vs line segment, sphere vs line segment, sphere vs point). I'm not sure how to do a swept capsule that accounts for rotation other than relying on detecting the collision due to penetration. I'm wondering how many games actually use a swept capsule instead of a series of spheres... > > Usually, this (character collision i mean) is done by doing a swept (in > time, not space) capsule vs triangles test - but this is difficult to get > right; there are a lot of cases to deal with. Especially if your capsule > is rotating. > ... > Cheers, Paul. ```
 Re: [Algorithms] 3rd person adventures - The saga continues! From: Bill Baxter - 2005-11-03 23:59:13 Attachments: Message as HTML ```Have you looked at Stephane Redon's work on continuous collision detection? I'm pretty sure he does swept capsules. He makes it tractable by assuming a particular form for the rotation between frames, namely an exponential map. So it's not using the "correct" rotation to represent the inter-frame motion, but that's not such a big deal because without actually running you= r simulator at finer timesteps you have no way of knowing what the correct motion is anyway. In the end it comes out to be solutions of fairly low-order polynomials. And I think he does some interval math / Sturm sequence type things to avoid actually having to find the roots. Anyway, his stuff is worth a look if you haven't seen it already. --bb On 11/4/05, Jeremiah Zanin wrote: > > Swept capsule vs. triangle is pretty tricky and I haven't seen it > documented > anywhere. I implemented it by breaking down the problem into smaller > problems (line segment vs plane, sphere vs plane, circle vs line segment, > sphere vs line segment, sphere vs point). I'm not sure how to do a swept > capsule that accounts for rotation other than relying on detecting the > collision due to penetration. I'm wondering how many games actually use a > swept capsule instead of a series of spheres... > > > > > Usually, this (character collision i mean) is done by doing a swept (in > > time, not space) capsule vs triangles test - but this is difficult to > get > > right; there are a lot of cases to deal with. Especially if your capsul= e > > is rotating. > > ... > > Cheers, Paul. > > > ```
 [Algorithms] Re: 3rd person adventures - The saga continues! From: - 2005-11-04 02:17:59 ```Stephane Redon's ccd is feature based, so no swept capsules there. You can use another ccd approach based on an extension of raycasting the Minkowski sum. See Gino van den Bergens paper on this topic: https://www.cmpevents.com/Sessions/GD/ContinuousCollisionDetection1.ppt Both this and Redon's method are implemented in my Bullet continuous collision detection library. It includes pure linear (swept) and angular motion too. Supported shapes are triangle, sphere,box,triangle,capsule,cylinder,cone etc. http://www.continuousphysics.com/Bullet/ Regards, Erwin Coumans Bill Baxter writes: > Have you looked at Stephane Redon's work on continuous collision detection? > I'm pretty sure he does swept capsules. He makes it tractable by assuming a > particular form for the rotation between frames, namely an exponential map. > So it's not using the "correct" rotation to represent the inter-frame > motion, but that's not such a big deal because without actually running your > simulator at finer timesteps you have no way of knowing what the correct > motion is anyway. In the end it comes out to be solutions of fairly > low-order polynomials. And I think he does some interval math / Sturm > sequence type things to avoid actually having to find the roots. > > Anyway, his stuff is worth a look if you haven't seen it already. > > --bb > > On 11/4/05, Jeremiah Zanin wrote: >> >> Swept capsule vs. triangle is pretty tricky and I haven't seen it >> documented >> anywhere. I implemented it by breaking down the problem into smaller >> problems (line segment vs plane, sphere vs plane, circle vs line segment, >> sphere vs line segment, sphere vs point). I'm not sure how to do a swept >> capsule that accounts for rotation other than relying on detecting the >> collision due to penetration. I'm wondering how many games actually use a >> swept capsule instead of a series of spheres... >> >> > >> > Usually, this (character collision i mean) is done by doing a swept (in >> > time, not space) capsule vs triangles test - but this is difficult to >> get >> > right; there are a lot of cases to deal with. Especially if your capsule >> > is rotating. >> > ... >> > Cheers, Paul. >> >> >> ```
 Re: [Algorithms] Re: 3rd person adventures - The saga continues! From: Bill Baxter - 2005-11-04 02:39:41 Attachments: Message as HTML ```Ok, I was mixing two things up -- the orignal CCD work of Stephane's, about which I know a little, plus this: http://gamma.cs.unc.edu/Avatar/ about which I don't actually know too much, but from the pictures it sure makes it look like CCD with capsules. Erwin, when you refer to "Redon's ccd" are you including the above work as well? --bb On 11/4/05, gdalgo@... wrote: > > > Stephane Redon's ccd is feature based, so no swept capsules there. > > You can use another ccd approach based on an extension of raycasting the > Minkowski sum. See Gino van den Bergens paper on this topic: > https://www.cmpevents.com/Sessions/GD/ContinuousCollisionDetection1.ppt > > Both this and Redon's method are implemented in my Bullet continuous > collision detection library. It includes pure linear (swept) and angular > motion too. Supported shapes are triangle, > sphere,box,triangle,capsule,cylinder,cone etc. > > http://www.continuousphysics.com/Bullet/ > > Regards, > Erwin Coumans > > > > Bill Baxter writes: > > > Have you looked at Stephane Redon's work on continuous collision > detection? > > I'm pretty sure he does swept capsules. He makes it tractable by > assuming a > > particular form for the rotation between frames, namely an exponential > map. > > So it's not using the "correct" rotation to represent the inter-frame > > motion, but that's not such a big deal because without actually running > your > > simulator at finer timesteps you have no way of knowing what the correc= t > > motion is anyway. In the end it comes out to be solutions of fairly > > low-order polynomials. And I think he does some interval math / Sturm > > sequence type things to avoid actually having to find the roots. > > > > Anyway, his stuff is worth a look if you haven't seen it already. > > > > --bb > > > > On 11/4/05, Jeremiah Zanin wrote: > >> > >> Swept capsule vs. triangle is pretty tricky and I haven't seen it > >> documented > >> anywhere. I implemented it by breaking down the problem into smaller > >> problems (line segment vs plane, sphere vs plane, circle vs line > segment, > >> sphere vs line segment, sphere vs point). I'm not sure how to do a > swept > >> capsule that accounts for rotation other than relying on detecting the > >> collision due to penetration. I'm wondering how many games actually us= e > a > >> swept capsule instead of a series of spheres... > >> > >> > > >> > Usually, this (character collision i mean) is done by doing a swept > (in > >> > time, not space) capsule vs triangles test - but this is difficult t= o > >> get > >> > right; there are a lot of cases to deal with. Especially if your > capsule > >> > is rotating. > >> > ... > >> > Cheers, Paul. > >> > >> > >> > > > > > ```