Thread: [Algorithms] Dynamic Plane Shifting BSP Traversal Problem
Brought to you by:
vexxed72
From: Damian C. <dam...@gm...> - 2009-02-17 07:13:17
|
Hi all, I've come across a collision detection use case which I cannot get to work with dynamic plane shifting when recursing a BSP tree. The paper I've read which I'm trying to implement is Stan Melax's Dynamic Plane Shifting BSP Traversal, found here: http://www.melax.com/melaxbsp.pdf. The use case is when two planes are close to, but not, perpendicular to one another. The shifting of the plane results in a plane that formerly was in front of the other plane when the tree was built, but now is behind it, due to the shift. This results in a false positive and you collide with "thin air". Apparently this is the algorithm used for collision detection in MDK2 and NWN, so it must work. I must have misunderstood Stan's paper, or my implementation is wrong. My implementation works for every other use case I've thrown at it. For a full explanation of the use case I've outlined everything with diagrams and text on this web page: http://damiancoventry.com/BSPProblem/DynamicPlaneShiftingBSPTraversalProblem.htm Surely this algorithm can handle this use case, and surely others have encountered this before? ~Damian(); |
From: pontus b. <her...@ho...> - 2009-02-17 23:50:22
|
Hi, I'm currently in the process of debugging a line- infinite cylinder intersection routine, but since I didn't write it myself I thought I'd go back to the books and compare the solution to the one I found in Real-time Collision Detection by Christer Ericson. The current implementation seems heavily lifted from that book but differ when it comes to describing the b term of the second order polynomial as well as when calculating the discriminant. The discriminant part is where I get confused because to me the it looks like implemenation I have is correctly calculating it while the version in Real-time Collision Detection is not. Is far as the textbooks tell me the discriminant from a second order polynomial is equal to b^2 - 4ac and the implementation I'm having troubles with define it likewise float blah = b * b - 4.0f * a * c; if (blah < 0.0f) return false; Makes sense, but then I checked the version from the book and it looks like this. float discr = b * b – a * c; if (discr < 0.0f) return 0; Now here's finally my question, where did the 4 in 4 * a * c go? Isn't it needed for some reason? I thought it may have gotten lost in the presses but there isn't anything about in on the errata pages either so I guess this is still correct then? If it is correct, I would be very happy if someone could explain why and under what circumstances it is because it might be what is breaking the routine I'm debugging. Regards, Pontus Birgersson Shortfuse Games _________________________________________________________________ Hetaste modetipsen & härligaste skönhetstesterna! http://salongk.msn.se/ |
From: Smith, M. X <Mat...@di...> - 2009-02-18 02:54:33
|
Looking at the text, the equation being solved is: ax^2 + 2bx + c = 0. If you roll the 2b through the whole equation, you would get: (2b [+-] sqrt(4b^2 - 4ac)) / 2a. Factor the 4's out of the sqrt, and all the 2's cancel. - Matt ________________________________ From: gda...@li... [mailto:gda...@li...] On Behalf Of pontus birgersson Sent: Tuesday, February 17, 2009 4:50 PM To: gda...@li... Subject: [Algorithms] Line-Cylinder intersection problem Hi, I'm currently in the process of debugging a line- infinite cylinder intersection routine, but since I didn't write it myself I thought I'd go back to the books and compare the solution to the one I found in Real-time Collision Detection by Christer Ericson. The current implementation seems heavily lifted from that book but differ when it comes to describing the b term of the second order polynomial as well as when calculating the discriminant. The discriminant part is where I get confused because to me the it looks like implemenation I have is correctly calculating it while the version in Real-time Collision Detection is not. Is far as the textbooks tell me the discriminant from a second order polynomial is equal to b^2 - 4ac and the implementation I'm having troubles with define it likewise float blah = b * b - 4.0f * a * c; if (blah < 0.0f) return false; Makes sense, but then I checked the version from the book and it looks like this. float discr = b * b - a * c; if (discr < 0.0f) return 0; Now here's finally my question, where did the 4 in 4 * a * c go? Isn't it needed for some reason? I thought it may have gotten lost in the presses but there isn't anything about in on the errata pages either so I guess this is still correct then? If it is correct, I would be very happy if someone could explain why and under what circumstances it is because it might be what is breaking the routine I'm debugging. Regards, Pontus Birgersson Shortfuse Games ________________________________ Långtråkigt? Mängder av sköna spel att fördriva tiden med! MSN Spelhallen <http://www.king.com/servlet/SelectServlet?partner=msn.se&language=sv> |
From: pontus b. <her...@ho...> - 2009-02-18 08:26:52
|
Thanks for the replies! From: jsc...@sl... To: gda...@li... Date: Tue, 17 Feb 2009 16:24:28 -0800 Subject: Re: [Algorithms] Line-Cylinder intersection problem In this case the 4 constant isn't required because it won't change the positive or negative result that is tested. Are you sure about this because discriminant < 0 evaluates to b^2 - 4ac < 0 which can be written as b^2 < 4ac, so is there no possibility that the 4 would change the result of that expression? Date: Wed, 18 Feb 2009 01:40:50 +0000 From: Mat...@di... To: gda...@li... Subject: Re: [Algorithms] Line-Cylinder intersection problem Looking at the text, the equation being solved is: ax^2 + 2bx + c = 0. If you roll the 2b through the whole equation, you would get: (2b [+-] sqrt(4b^2 - 4ac)) / 2a. Factor the 4's out of the sqrt, and all the 2's cancel. - Matt Yeah but all you did there was change what b means because ordinarily you write it as ax^2 + bx + c = 0 (no 2*bx). Are you saying that Christer did the same thing in his implementation perhaps? _________________________________________________________________ |
From: pontus b. <her...@ho...> - 2009-02-18 10:10:57
|
Yeah but all you did there was change what b means because ordinarily you write it as ax^2 + bx + c = 0 (no 2*bx). Are you saying that Christer did the same thing in his implementation perhaps? Looking at it closer I see that's exactly what he is doing. Thanks for the help! From: her...@ho... To: gda...@li... Date: Wed, 18 Feb 2009 08:26:49 +0000 Subject: Re: [Algorithms] Line-Cylinder intersection problem Thanks for the replies! From: jsc...@sl... To: gda...@li... Date: Tue, 17 Feb 2009 16:24:28 -0800 Subject: Re: [Algorithms] Line-Cylinder intersection problem In this case the 4 constant isn't required because it won't change the positive or negative result that is tested. Are you sure about this because discriminant < 0 evaluates to b^2 - 4ac < 0 which can be written as b^2 < 4ac, so is there no possibility that the 4 would change the result of that expression? Date: Wed, 18 Feb 2009 01:40:50 +0000 From: Mat...@di... To: gda...@li... Subject: Re: [Algorithms] Line-Cylinder intersection problem Looking at the text, the equation being solved is: ax^2 + 2bx + c = 0. If you roll the 2b through the whole equation, you would get: (2b [+-] sqrt(4b^2 - 4ac)) / 2a. Factor the 4's out of the sqrt, and all the 2's cancel. - Matt Yeah but all you did there was change what b means because ordinarily you write it as ax^2 + bx + c = 0 (no 2*bx). Are you saying that Christer did the same thing in his implementation perhaps? _________________________________________________________________ |
From: Smith, M. X <Mat...@di...> - 2009-02-18 15:17:23
|
> From: jsc...@sl... > > Are you sure about this because discriminant < 0 evaluates to b^2 - 4ac < 0 which can be written as b^2 < 4ac, > so is there no possibility that the 4 would change the result of that expression? His equation is: ax^2 + 2bx + c = 0 That isn't quite in the quadratic equation form. To get it to match, we replace 2b with b'. ax^2 + b'x + c = 0. That becomes: ( b' [+-] sqrt(b'^2 - 4ac) ) / 2a Replace b' with 2b: (2b [+-] sqrt(4b^2 - 4ac) ) / 2a The descriminant becomes 4b^2 - 4ac. - Matt |
From: <chr...@pl...> - 2009-02-18 18:51:18
|
pontus birgersson <her...@ho...> wrote on 02/17/2009 03:50:12 PM: > > The current implementation seems heavily lifted from that book but > differ when it comes to describing the b term of the second order > polynomial as well as when calculating the discriminant. The > discriminant part is where I get confused because to me the it looks > like implemenation I have is correctly calculating it while the > version in Real-time Collision Detection is not. [...] Matthew Smith explained it well already, but I thought I'd stress that the "textbook" way of solving quadratic equations, using the form ax^2 + bx + c = 0 is much less convenient than using the form ax^2 + 2bx + c = 0. (Note the extra "2" in front of "b".) The latter is what I used throughout the book. In fact, if you are to memorize a quadratic formula, IMO the best formulation is x^2 + 2bx + c = 0 for which the solutions are given by the very simple expression x = -b +- sqrt(b^2 - c). If there's an "a" constant in front of the squared term, you can just divide through with it. Simplifying the solution then gives: x = (-b +- sqrt(b^2 - ac)) / a. The latter formula has the discriminant d = b^2 - ac, which is what's used in the line-cylinder test (as explained on page 196). Christer Ericson, Director of Tools and Technology Sony Computer Entertainment, Santa Monica |
From: Jim S. <jsc...@sl...> - 2009-02-18 00:51:15
|
In this case the 4 constant isn't required because it won't change the positive or negative result that is tested. ----- Original Message ----- From: pontus birgersson To: gda...@li... Sent: Tuesday, February 17, 2009 3:50 PM Subject: [Algorithms] Line-Cylinder intersection problem Hi, I'm currently in the process of debugging a line- infinite cylinder intersection routine, but since I didn't write it myself I thought I'd go back to the books and compare the solution to the one I found in Real-time Collision Detection by Christer Ericson. The current implementation seems heavily lifted from that book but differ when it comes to describing the b term of the second order polynomial as well as when calculating the discriminant. The discriminant part is where I get confused because to me the it looks like implemenation I have is correctly calculating it while the version in Real-time Collision Detection is not. Is far as the textbooks tell me the discriminant from a second order polynomial is equal to b^2 - 4ac and the implementation I'm having troubles with define it likewise float blah = b * b - 4.0f * a * c; if (blah < 0.0f) return false; Makes sense, but then I checked the version from the book and it looks like this. float discr = b * b – a * c; if (discr < 0.0f) return 0; Now here's finally my question, where did the 4 in 4 * a * c go? Isn't it needed for some reason? I thought it may have gotten lost in the presses but there isn't anything about in on the errata pages either so I guess this is still correct then? If it is correct, I would be very happy if someone could explain why and under what circumstances it is because it might be what is breaking the routine I'm debugging. Regards, Pontus Birgersson Shortfuse Games ------------------------------------------------------------------------------ Långtråkigt? Mängder av sköna spel att fördriva tiden med! MSN Spelhallen ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, CA -OSBC tackles the biggest issue in open source: Open Sourcing the Enterprise -Strategies to boost innovation and cut costs with open source participation -Receive a $600 discount off the registration fee with the source code: SFAD http://p.sf.net/sfu/XcvMzF8H ------------------------------------------------------------------------------ _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Marius E. <mar...@ir...> - 2009-02-18 12:49:29
|
Hello, this seems to be a case of extra-long extrusion that Melax is 'fixing' by beveling. In this case, it's the very sharp edge between plane 1 and plane 5 that gets extruded further than you'd intuitively think. Much like the right corner in figure 3 of Melax' paper. This is an inherent problem of the algorithm because it only expands planes, never lines or points - it doesn't 'really' work with distance to volumes this way. -Marius Quoting Damian Coventry <dam...@gm...>: > Hi all, > > I've come across a collision detection use case which I cannot get to work > with dynamic plane shifting when recursing a BSP tree. > > The paper I've read which I'm trying to implement is Stan Melax's Dynamic > Plane Shifting BSP Traversal, found here: http://www.melax.com/melaxbsp.pdf. > > The use case is when two planes are close to, but not, perpendicular to one > another. The shifting of the plane results in a plane that formerly was in > front of the other plane when the tree was built, but now is behind it, due > to the shift. This results in a false positive and you collide with "thin > air". > > Apparently this is the algorithm used for collision detection in MDK2 and > NWN, so it must work. I must have misunderstood Stan's paper, or my > implementation is wrong. My implementation works for every other use case > I've thrown at it. > > For a full explanation of the use case I've outlined everything with > diagrams and text on this web page: > http://damiancoventry.com/BSPProblem/DynamicPlaneShiftingBSPTraversalProblem.htm > > Surely this algorithm can handle this use case, and surely others have > encountered this before? > > ~Damian(); > |
From: Damian C. <dam...@gm...> - 2009-02-19 19:11:40
|
Bevelling seems like it's the solution to the problem alright. I think I should have read the paper more thoroughly, because this paragraph from the paper sums it up succintly: "Although it may not always seem necessary, this beveling step is very important, even if the initial boundary representation contains no acutely convex angles. Our initial experiments in altering the plane equations, where we had not included the beveling step, were unsuccessful. The movement of characters in our video game was blocked in the strangest places as if someone had randomly placed invisible walls in the scene. This happens because the BSP compilation process splits polygons and creates cells with sharp angles in unexpected places. Beveling solved this problem and made the dynamic plane shifting technique viable." "randomly placed invisible walls" is definitely what I'm suffering. So off I go to implement bevelling... :-) Cheers for the reply Marius, ~Damian(); On Thu, Feb 19, 2009 at 1:18 AM, Marius Elvert <mar...@ir...>wrote: > Hello, > > this seems to be a case of extra-long extrusion that Melax is 'fixing' > by beveling. In this case, it's the very sharp edge between plane 1 > and plane 5 that gets extruded further than you'd intuitively think. > Much like the right corner in figure 3 of Melax' paper. > This is an inherent problem of the algorithm because it only expands > planes, never lines or points - it doesn't 'really' work with distance > to volumes this way. > > -Marius > > Quoting Damian Coventry <dam...@gm...>: > > > Hi all, > > > > I've come across a collision detection use case which I cannot get to > work > > with dynamic plane shifting when recursing a BSP tree. > > > > The paper I've read which I'm trying to implement is Stan Melax's Dynamic > > Plane Shifting BSP Traversal, found here: > http://www.melax.com/melaxbsp.pdf. > > > > The use case is when two planes are close to, but not, perpendicular to > one > > another. The shifting of the plane results in a plane that formerly was > in > > front of the other plane when the tree was built, but now is behind it, > due > > to the shift. This results in a false positive and you collide with > "thin > > air". > > > > Apparently this is the algorithm used for collision detection in MDK2 and > > NWN, so it must work. I must have misunderstood Stan's paper, or my > > implementation is wrong. My implementation works for every other use > case > > I've thrown at it. > > > > For a full explanation of the use case I've outlined everything with > > diagrams and text on this web page: > > > http://damiancoventry.com/BSPProblem/DynamicPlaneShiftingBSPTraversalProblem.htm > > > > Surely this algorithm can handle this use case, and surely others have > > encountered this before? > > > > ~Damian(); > > > > > > > ------------------------------------------------------------------------------ > Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, > CA > -OSBC tackles the biggest issue in open source: Open Sourcing the > Enterprise > -Strategies to boost innovation and cut costs with open source > participation > -Receive a $600 discount off the registration fee with the source code: > SFAD > http://p.sf.net/sfu/XcvMzF8H > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > |
From: Jay S. <Ja...@va...> - 2009-02-24 23:13:56
|
The bevelling doesn't completely solve the problem though. In order to shrink a sphere down to a point you need to spherically extend (i.e. convolve with a sphere) the BSP geometry. Or to put it another way - you need to add bevel planes to the BSP for every potential separating axis. For a polyhedron (instead of a sphere) this is finite and can be precomputed, but for a sphere you either need something other than a BSP or an infinite number of planes. Quake2 (and Half-Life 2) use this technique for boxes, adding bevel planes for each potential separating axis. You could possibly do the inifinite number of planes thing by adding some procedural bevel planes. So their normals would get computed as a function of the static features and the swept sphere query. I haven't implemented that but I think it would work. But you may end up solving quadratics in order to compute the normals which kind of defeats the simplicity of this technique. The actual collision manifold for the sphere expanded tree is curved along each edge and at each vertex of the original BSP. Anyway, the technique in the paper just adds some average planes. So while that will still give you usable collision detection, the shape that is actually hitting the BSP is some kind of space-varying polyhedron, not a sphere (meaning it's a polyhedron, but a different polyhedron in different parts of the space because the bevels depend only on the static geometry). But that approximates a sphere and should be workable if you don't need it to be exactly a sphere. Jay ________________________________ From: Damian Coventry [mailto:dam...@gm...] Sent: Thursday, February 19, 2009 11:12 AM To: Game Development Algorithms Subject: Re: [Algorithms] Dynamic Plane Shifting BSP Traversal Problem Bevelling seems like it's the solution to the problem alright. I think I should have read the paper more thoroughly, because this paragraph from the paper sums it up succintly: "Although it may not always seem necessary, this beveling step is very important, even if the initial boundary representation contains no acutely convex angles. Our initial experiments in altering the plane equations, where we had not included the beveling step, were unsuccessful. The movement of characters in our video game was blocked in the strangest places as if someone had randomly placed invisible walls in the scene. This happens because the BSP compilation process splits polygons and creates cells with sharp angles in unexpected places. Beveling solved this problem and made the dynamic plane shifting technique viable." "randomly placed invisible walls" is definitely what I'm suffering. So off I go to implement bevelling... :-) Cheers for the reply Marius, ~Damian(); On Thu, Feb 19, 2009 at 1:18 AM, Marius Elvert <mar...@ir...<mailto:mar...@ir...>> wrote: Hello, this seems to be a case of extra-long extrusion that Melax is 'fixing' by beveling. In this case, it's the very sharp edge between plane 1 and plane 5 that gets extruded further than you'd intuitively think. Much like the right corner in figure 3 of Melax' paper. This is an inherent problem of the algorithm because it only expands planes, never lines or points - it doesn't 'really' work with distance to volumes this way. -Marius Quoting Damian Coventry <dam...@gm...<mailto:dam...@gm...>>: > Hi all, > > I've come across a collision detection use case which I cannot get to work > with dynamic plane shifting when recursing a BSP tree. > > The paper I've read which I'm trying to implement is Stan Melax's Dynamic > Plane Shifting BSP Traversal, found here: http://www.melax.com/melaxbsp.pdf. > > The use case is when two planes are close to, but not, perpendicular to one > another. The shifting of the plane results in a plane that formerly was in > front of the other plane when the tree was built, but now is behind it, due > to the shift. This results in a false positive and you collide with "thin > air". > > Apparently this is the algorithm used for collision detection in MDK2 and > NWN, so it must work. I must have misunderstood Stan's paper, or my > implementation is wrong. My implementation works for every other use case > I've thrown at it. > > For a full explanation of the use case I've outlined everything with > diagrams and text on this web page: > http://damiancoventry.com/BSPProblem/DynamicPlaneShiftingBSPTraversalProblem.htm > > Surely this algorithm can handle this use case, and surely others have > encountered this before? > > ~Damian(); > ------------------------------------------------------------------------------ Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, CA -OSBC tackles the biggest issue in open source: Open Sourcing the Enterprise -Strategies to boost innovation and cut costs with open source participation -Receive a $600 discount off the registration fee with the source code: SFAD http://p.sf.net/sfu/XcvMzF8H _______________________________________________ GDAlgorithms-list mailing list GDA...@li...<mailto:GDA...@li...> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Jon W. <jw...@gm...> - 2009-02-24 23:48:37
|
Jay Stelly wrote: > The bevelling doesn't completely solve the problem though. In order > to shrink a sphere down to a point you need to spherically extend > (i.e. convolve with a sphere) the BSP geometry. Or to put it another > way - you need to add bevel planes to the BSP for every potential > separating axis. The word for that kind of expansion of geometry is "Minkowski sum". You get some Google hits on that, but most of them are not quite real-time or implementation-oriented enough for games. Color me confused, though: I have previously collided spheres against geometry in a BSP tree, and it works just fine without the plane shifting -- without any artifacts. Is there some other benefit you are trying to get out of the plane shifting than avoiding having to do sphere/polygon tests (i e, live with only the slightly faster sphere/plane tests)? It seems to me that the cost of sphere/poly tests, once culled based on a BSP, is such a small cost as to be negligible, and certainly not worth all the hours that have been spent on it already even on this list :-) Sincerely, jw |
From: Damian C. <dam...@gm...> - 2009-02-25 23:23:01
|
Jay Stelly: You're right, it's not going to nicely map to a sphere's surface, it's just an approximation. It's a fast approximation, which is the real selling point - you get reasonable collisions for not much CPU. Since my last email to this list I have been successful with this technique and have the so-called 'zero volume cells' algorithm working. It kicks butt. I have suffered no noticeable performance hit and I'm colliding spheres and cylinders nicely. Jon Watte: This technique solves more than just spheres. Yes, for just spheres, you don't need to jump through these hoops. With this technique you can implement any convex shape for which you can calculate a point tangential to a plane. So an AABB, a cylinder, and yes a sphere too. I suppose if you had a translating, rotating box you collide that too. ~Damian(); On Wed, Feb 25, 2009 at 6:19 PM, Gregory Junker <gj...@da...> wrote: > @ Jon -- the OP is at the bottom; the person you are replying to is not the > OP. > > Greg > > > -----Original Message----- > > From: Jon Watte [mailto:jw...@gm...] > > Sent: Tuesday, February 24, 2009 3:48 PM > > To: Game Development Algorithms > > Subject: Re: [Algorithms] Dynamic Plane Shifting BSP Traversal Problem > > > > Jay Stelly wrote: > > > The bevelling doesn't completely solve the problem though. In order > > > to shrink a sphere down to a point you need to spherically extend > > > (i.e. convolve with a sphere) the BSP geometry. Or to put it another > > > way - you need to add bevel planes to the BSP for every potential > > > separating axis. > > > > The word for that kind of expansion of geometry is "Minkowski sum". You > > get some Google hits on that, but most of them are not quite real-time > > or implementation-oriented enough for games. > > > > Color me confused, though: I have previously collided spheres against > > geometry in a BSP tree, and it works just fine without the plane > > shifting -- without any artifacts. Is there some other benefit you are > > trying to get out of the plane shifting than avoiding having to do > > sphere/polygon tests (i e, live with only the slightly faster > > sphere/plane tests)? > > It seems to me that the cost of sphere/poly tests, once culled based on > > a BSP, is such a small cost as to be negligible, and certainly not worth > > all the hours that have been spent on it already even on this list :-) > > > > Sincerely, > > > > jw > > > > > > > -------------------------------------------------------------------------- > > ---- > > Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, > > CA > > -OSBC tackles the biggest issue in open source: Open Sourcing the > > Enterprise > > -Strategies to boost innovation and cut costs with open source > > participation > > -Receive a $600 discount off the registration fee with the source code: > > SFAD > > http://p.sf.net/sfu/XcvMzF8H > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > > > ------------------------------------------------------------------------------ > Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, > CA > -OSBC tackles the biggest issue in open source: Open Sourcing the > Enterprise > -Strategies to boost innovation and cut costs with open source > participation > -Receive a $600 discount off the registration fee with the source code: > SFAD > http://p.sf.net/sfu/XcvMzF8H > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > |
From: Damian C. <dam...@gm...> - 2009-02-26 00:31:20
|
I haven't performed any profiling; currently I have only a frame rate counter and the 'feel' from a player's perspective when loading up a fair amount of moving cylinders. Stan's paper has graphs, statistics and quite indepth testing that reports microsecond timings if you want the actual performance impact of this algorithm. The paper is from 2001, so I'm sure many more techniques have come along since them. What approach did you take to implement colliding translating, rotating boxes against poly meshes? ~Damian(); On Thu, Feb 26, 2009 at 12:48 PM, Jon Watte <jw...@gm...> wrote: > Damian Coventry wrote: > > Jon Watte: This technique solves more than just spheres. Yes, for just > > spheres, you don't need to jump through these hoops. With this > > technique you can implement any convex shape for which you can > > calculate a point tangential to a plane. So an AABB, a cylinder, and > > yes a sphere too. I suppose if you had a translating, rotating box > > you collide that too. > > But I already collide translating, rotating boxes against poly meshes. > Is there really a noticeable speed improvement from not having to do the > final box/poly test, assuming the BSP does all the broad-phase culling? > > Sincerely, > > jw > > > > ------------------------------------------------------------------------------ > Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, > CA > -OSBC tackles the biggest issue in open source: Open Sourcing the > Enterprise > -Strategies to boost innovation and cut costs with open source > participation > -Receive a $600 discount off the registration fee with the source code: > SFAD > http://p.sf.net/sfu/XcvMzF8H > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > |
From: Jon W. <jw...@gm...> - 2009-02-26 00:44:48
|
Damian Coventry wrote: > The paper is from 2001, so I'm sure many more techniques have come > along since them. What approach did you take to implement colliding > translating, rotating boxes against poly meshes? I just sweep the rotated box, I don't collide the actual "corkscrew" shape, so yes, I'm cheating :-) Sincerely, jw |
From: Gregory J. <gj...@da...> - 2009-02-25 05:45:52
|
@ Jon -- the OP is at the bottom; the person you are replying to is not the OP. Greg > -----Original Message----- > From: Jon Watte [mailto:jw...@gm...] > Sent: Tuesday, February 24, 2009 3:48 PM > To: Game Development Algorithms > Subject: Re: [Algorithms] Dynamic Plane Shifting BSP Traversal Problem > > Jay Stelly wrote: > > The bevelling doesn't completely solve the problem though. In order > > to shrink a sphere down to a point you need to spherically extend > > (i.e. convolve with a sphere) the BSP geometry. Or to put it another > > way - you need to add bevel planes to the BSP for every potential > > separating axis. > > The word for that kind of expansion of geometry is "Minkowski sum". You > get some Google hits on that, but most of them are not quite real-time > or implementation-oriented enough for games. > > Color me confused, though: I have previously collided spheres against > geometry in a BSP tree, and it works just fine without the plane > shifting -- without any artifacts. Is there some other benefit you are > trying to get out of the plane shifting than avoiding having to do > sphere/polygon tests (i e, live with only the slightly faster > sphere/plane tests)? > It seems to me that the cost of sphere/poly tests, once culled based on > a BSP, is such a small cost as to be negligible, and certainly not worth > all the hours that have been spent on it already even on this list :-) > > Sincerely, > > jw > > > -------------------------------------------------------------------------- > ---- > Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, > CA > -OSBC tackles the biggest issue in open source: Open Sourcing the > Enterprise > -Strategies to boost innovation and cut costs with open source > participation > -Receive a $600 discount off the registration fee with the source code: > SFAD > http://p.sf.net/sfu/XcvMzF8H > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Jon W. <jw...@gm...> - 2009-02-25 23:48:59
|
Damian Coventry wrote: > Jon Watte: This technique solves more than just spheres. Yes, for just > spheres, you don't need to jump through these hoops. With this > technique you can implement any convex shape for which you can > calculate a point tangential to a plane. So an AABB, a cylinder, and > yes a sphere too. I suppose if you had a translating, rotating box > you collide that too. But I already collide translating, rotating boxes against poly meshes. Is there really a noticeable speed improvement from not having to do the final box/poly test, assuming the BSP does all the broad-phase culling? Sincerely, jw |