Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project!

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

 Re: [Algorithms] Re: 3rd person adventures - The saga continues! From: Erwin Coumans - 2005-11-04 17:38:17 ```As angular velocity increases the algorithm potentially needs more iterations, but it still can calculate the time of impact within a given tolerance. Both approaches require a limit on the angular velocity of 180 degrees per simulation step. If you exceed this you will need to subdivide the motion yourself. In practice your simulation will seldom hit this high velocity. If your simulation stepsize is 30 herz, you can make 16 full rotations per second. Erwin ----- Original Message ----- From: "Jeremiah Zanin" To: Sent: Friday, November 04, 2005 5:19 PM Subject: RE: [Algorithms] Re: 3rd person adventures - The saga continues! > Interesting. > > I'm probably missing something but...If D is "v dot n + rmax * w", does > that > mean as the angular velocity increases, the collision is more conservative > (kind of like an expanding sphere)? And for very high angular velocities, > D > extends beyond the sphere that encloses the object about its center of > mass? > >> -----Original Message----- >> From: gdalgorithms-list-admin@... [mailto:gdalgorithms- >> list-admin@...] On Behalf Of Erwin Coumans >> Sent: Friday, November 04, 2005 2:52 AM >> To: gdalgorithms-list@... >> Subject: Re: [Algorithms] Re: 3rd person adventures - The saga continues! >> >> Both approaches that I mentioned earlier are conservative and don't have >> tunneling problems for rotation and translation. Here is a draft paper >> with >> some details on the rotational case: >> http://www.continuousphysics.com/BulletContinuousCollisionDetection.pdf >> >> Stephane Redon original algebraic ccd (around 2000) was feature based, >> but >> the newer Avatar project uses implicit capsules. However in their gpu >> implementation the capsule got tesselated. >> >> Erwin >> >> ----- Original Message ----- >> From: "Jeremiah Zanin" >> To: >> Sent: Friday, November 04, 2005 3:42 PM >> Subject: RE: [Algorithms] Re: 3rd person adventures - The saga continues! >> >> >> > Right, purely translational sweeps can be "exact" (within numerical >> > error), >> > but rotation still has the problem of tunneling. >> > >> >> -----Original Message----- >> >> From: gdalgorithms-list-admin@... >> [mailto:gdalgorithms- >> >> list-admin@...] On Behalf Of gdalgo@... >> >> Sent: Thursday, November 03, 2005 8:18 PM >> >> To: gdalgorithms-list@... >> >> Subject: [Algorithms] Re: 3rd person adventures - The saga continues! >> >> >> >> >> >> 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. >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> ------------------------------------------------------- >> >> 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=6188 >> > >> > >> > ------------------------------------------------------- >> > 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=6188 >> > >> >> >> >> >> ------------------------------------------------------- >> 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=6188 > > > ------------------------------------------------------- > 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=6188 > ```

 RE: [Algorithms] Re: 3rd person adventures - The saga continues! From: Jeremiah Zanin - 2005-11-04 15:43:24 ```Right, purely translational sweeps can be "exact" (within numerical error), but rotation still has the problem of tunneling. > -----Original Message----- > From: gdalgorithms-list-admin@... [mailto:gdalgorithms- > list-admin@...] On Behalf Of gdalgo@... > Sent: Thursday, November 03, 2005 8:18 PM > To: gdalgorithms-list@... > Subject: [Algorithms] Re: 3rd person adventures - The saga continues! > > > 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. > >> > >> > >> > > > > > ------------------------------------------------------- > 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=6188 ```
 RE: [Algorithms] Re: 3rd person adventures - The saga continues! From: Jeremiah Zanin - 2005-11-04 17:19:32 ```Interesting. I'm probably missing something but...If D is "v dot n + rmax * w", does that mean as the angular velocity increases, the collision is more conservative (kind of like an expanding sphere)? And for very high angular velocities, D extends beyond the sphere that encloses the object about its center of mass? > -----Original Message----- > From: gdalgorithms-list-admin@... [mailto:gdalgorithms- > list-admin@...] On Behalf Of Erwin Coumans > Sent: Friday, November 04, 2005 2:52 AM > To: gdalgorithms-list@... > Subject: Re: [Algorithms] Re: 3rd person adventures - The saga continues! > > Both approaches that I mentioned earlier are conservative and don't have > tunneling problems for rotation and translation. Here is a draft paper > with > some details on the rotational case: > http://www.continuousphysics.com/BulletContinuousCollisionDetection.pdf > > Stephane Redon original algebraic ccd (around 2000) was feature based, but > the newer Avatar project uses implicit capsules. However in their gpu > implementation the capsule got tesselated. > > Erwin > > ----- Original Message ----- > From: "Jeremiah Zanin" > To: > Sent: Friday, November 04, 2005 3:42 PM > Subject: RE: [Algorithms] Re: 3rd person adventures - The saga continues! > > > > Right, purely translational sweeps can be "exact" (within numerical > > error), > > but rotation still has the problem of tunneling. > > > >> -----Original Message----- > >> From: gdalgorithms-list-admin@... > [mailto:gdalgorithms- > >> list-admin@...] On Behalf Of gdalgo@... > >> Sent: Thursday, November 03, 2005 8:18 PM > >> To: gdalgorithms-list@... > >> Subject: [Algorithms] Re: 3rd person adventures - The saga continues! > >> > >> > >> 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. > >> >> > >> >> > >> >> > >> > >> > >> > >> > >> ------------------------------------------------------- > >> 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=6188 > > > > > > ------------------------------------------------------- > > 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=6188 > > > > > > > ------------------------------------------------------- > 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=6188 ```
 Re: [Algorithms] Re: 3rd person adventures - The saga continues! From: Erwin Coumans - 2005-11-04 17:38:17 ```As angular velocity increases the algorithm potentially needs more iterations, but it still can calculate the time of impact within a given tolerance. Both approaches require a limit on the angular velocity of 180 degrees per simulation step. If you exceed this you will need to subdivide the motion yourself. In practice your simulation will seldom hit this high velocity. If your simulation stepsize is 30 herz, you can make 16 full rotations per second. Erwin ----- Original Message ----- From: "Jeremiah Zanin" To: Sent: Friday, November 04, 2005 5:19 PM Subject: RE: [Algorithms] Re: 3rd person adventures - The saga continues! > Interesting. > > I'm probably missing something but...If D is "v dot n + rmax * w", does > that > mean as the angular velocity increases, the collision is more conservative > (kind of like an expanding sphere)? And for very high angular velocities, > D > extends beyond the sphere that encloses the object about its center of > mass? > >> -----Original Message----- >> From: gdalgorithms-list-admin@... [mailto:gdalgorithms- >> list-admin@...] On Behalf Of Erwin Coumans >> Sent: Friday, November 04, 2005 2:52 AM >> To: gdalgorithms-list@... >> Subject: Re: [Algorithms] Re: 3rd person adventures - The saga continues! >> >> Both approaches that I mentioned earlier are conservative and don't have >> tunneling problems for rotation and translation. Here is a draft paper >> with >> some details on the rotational case: >> http://www.continuousphysics.com/BulletContinuousCollisionDetection.pdf >> >> Stephane Redon original algebraic ccd (around 2000) was feature based, >> but >> the newer Avatar project uses implicit capsules. However in their gpu >> implementation the capsule got tesselated. >> >> Erwin >> >> ----- Original Message ----- >> From: "Jeremiah Zanin" >> To: >> Sent: Friday, November 04, 2005 3:42 PM >> Subject: RE: [Algorithms] Re: 3rd person adventures - The saga continues! >> >> >> > Right, purely translational sweeps can be "exact" (within numerical >> > error), >> > but rotation still has the problem of tunneling. >> > >> >> -----Original Message----- >> >> From: gdalgorithms-list-admin@... >> [mailto:gdalgorithms- >> >> list-admin@...] On Behalf Of gdalgo@... >> >> Sent: Thursday, November 03, 2005 8:18 PM >> >> To: gdalgorithms-list@... >> >> Subject: [Algorithms] Re: 3rd person adventures - The saga continues! >> >> >> >> >> >> 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. >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> ------------------------------------------------------- >> >> 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=6188 >> > >> > >> > ------------------------------------------------------- >> > 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=6188 >> > >> >> >> >> >> ------------------------------------------------------- >> 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=6188 > > > ------------------------------------------------------- > 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=6188 > ```
 RE: [Algorithms] Re: 3rd person adventures - The saga continues! From: Jeremiah Zanin - 2005-11-04 22:19:51 ```How do you detect a collision if an object doesn't collide in its starting transformation and ending transformation? Wouldn't the binary search end? > -----Original Message----- > From: gdalgorithms-list-admin@... [mailto:gdalgorithms- > list-admin@...] On Behalf Of > christer_ericson@... > Sent: Friday, November 04, 2005 12:06 PM > To: gdalgorithms-list@... > Subject: RE: [Algorithms] Re: 3rd person adventures - The saga continues! > > > > Jeremiah Zanin wrote: > > Right, purely translational sweeps can be "exact" (within numerical > error), > > but rotation still has the problem of tunneling. > > If you meant this in general (as opposed to a reference to Stephane's > work) > then it's definitely not the case. You can handle arbitrary motion, > without > any tunneling problem, using a binary search approach. > > > Christer Ericson > http://realtimecollisiondetection.net/ > > > > ------------------------------------------------------- > 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=6188 ```
 RE: [Algorithms] Re: 3rd person adventures - The saga continues! From: - 2005-11-04 22:33:37 ```Jeremiah Zanin wrote: > How do you detect a collision if an object doesn't collide in its starting > transformation and ending transformation? Wouldn't the binary search end? You perform the test not with the object shape itself but, for each time interval tested during the binary search, with a different shape that (narrowly) bounds the object over the current time interval in question. Christer Ericson http://realtimecollisiondetection.net/ ```
 RE: [Algorithms] Re: 3rd person adventures - The saga continues! From: Jeremiah Zanin - 2005-11-04 22:49:44 ```I see, so you can get false positives, correct? > -----Original Message----- > From: gdalgorithms-list-admin@... [mailto:gdalgorithms- > list-admin@...] On Behalf Of > christer_ericson@... > Sent: Friday, November 04, 2005 4:37 PM > To: gdalgorithms-list@... > Subject: RE: [Algorithms] Re: 3rd person adventures - The saga continues! > > > Jeremiah Zanin wrote: > > How do you detect a collision if an object doesn't collide in its > starting > > transformation and ending transformation? Wouldn't the binary search > end? > > You perform the test not with the object shape itself but, for each time > interval tested during the binary search, with a different shape that > (narrowly) bounds the object over the current time interval in question. > > > Christer Ericson > http://realtimecollisiondetection.net/ ```
 RE: [Algorithms] Re: 3rd person adventures - The saga continues! From: - 2005-11-04 22:59:26 ```Jeremiah Zanin wrote: > > > How do you detect a collision if an object doesn't collide in its > > > starting transformation and ending transformation? Wouldn't the > > > binary search end? > > > > You perform the test not with the object shape itself but, for each time > > interval tested during the binary search, with a different shape that > > (narrowly) bounds the object over the current time interval in question. > > I see, so you can get false positives, correct? When you reach the termination threshold of your binary search, yes. At that point you would typically assume the objects colliding. Otherwise you may suffer false negatives, which could be (very) bad. Christer Ericson http://realtimecollisiondetection.net/ ```
 Re: [Algorithms] Re: 3rd person adventures - The saga continues! From: Erwin Coumans - 2005-11-04 16:50:30 ```Both approaches that I mentioned earlier are conservative and don't have tunneling problems for rotation and translation. Here is a draft paper with some details on the rotational case: http://www.continuousphysics.com/BulletContinuousCollisionDetection.pdf Stephane Redon original algebraic ccd (around 2000) was feature based, but the newer Avatar project uses implicit capsules. However in their gpu implementation the capsule got tesselated. Erwin ----- Original Message ----- From: "Jeremiah Zanin" To: Sent: Friday, November 04, 2005 3:42 PM Subject: RE: [Algorithms] Re: 3rd person adventures - The saga continues! > Right, purely translational sweeps can be "exact" (within numerical > error), > but rotation still has the problem of tunneling. > >> -----Original Message----- >> From: gdalgorithms-list-admin@... [mailto:gdalgorithms- >> list-admin@...] On Behalf Of gdalgo@... >> Sent: Thursday, November 03, 2005 8:18 PM >> To: gdalgorithms-list@... >> Subject: [Algorithms] Re: 3rd person adventures - The saga continues! >> >> >> 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. >> >> >> >> >> >> >> >> >> >> >> ------------------------------------------------------- >> 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=6188 > > > ------------------------------------------------------- > 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=6188 > ```
 RE: [Algorithms] Re: 3rd person adventures - The saga continues! From: - 2005-11-04 18:02:36 ```Jeremiah Zanin wrote: > Right, purely translational sweeps can be "exact" (within numerical error), > but rotation still has the problem of tunneling. If you meant this in general (as opposed to a reference to Stephane's work) then it's definitely not the case. You can handle arbitrary motion, without any tunneling problem, using a binary search approach. Christer Ericson http://realtimecollisiondetection.net/ ```