Know Any O(ln N) Convex Poly-Circle Overlap Tests?
Author
I'm interested in performing an overlap test between a convex polygon (with verts stored in clockwise order) and a circle. The test should return the depth and contact normal.
There are a number of brute force methods that can be done in O(N) time (testing overlap on all the edges and all the verts, for instance), but I'd rather perform the test faster.
One way would be to generate the Voronoi diagram for the poly (a la the Metanet tutorials) and then build a trapezoidal map on top of that, which can be used to determine which Voronoi region the circle's center is in in O(ln N) time. Once you know which Voronoi region the center's in, the rest is easy.
The problems with that method are that it has a pretty big constant associated with it, and it doesn't sound too fun to program up. Does anyone know any simpler methods for doing the same thing?
John Edwards
use the Separating Axis Theorem,
and test it againts side of the convex polygon, because
end of the day, u'll be testing against the sides, so do it against the sides,
then, u can get the normal easily, via a normal to the side itself (I assume your doing 2D, sounds like it anyway! (-vy, vx)), that will be the collision normal. Then...
check whether the end of the penetration vector is inside the polygon and if it is, u can return that penetration length because it is now a valid collison.
Although this way will fail if parts of the circle is engulfing the polygon on oneside and the parts on another side of the same polygon. The trick to solve this is to get the shortest "valid" point from polygon (use SAT again!) and immediately place the circle there. so no penetration occurs.
Or u could make convex poly's using triangles and use metanets way of checking collision with triangles (n' other fancy shapes) using the tiles. I find using metanets solution of tiles in 2D very super. because its sooo fast in flash itself and when tried in C++ using ogl/dx or any api, its even faster (than flash) and u can make laaarge maps with super game play.
I really hope this helped man.
and test it againts side of the convex polygon, because
end of the day, u'll be testing against the sides, so do it against the sides,
then, u can get the normal easily, via a normal to the side itself (I assume your doing 2D, sounds like it anyway! (-vy, vx)), that will be the collision normal. Then...
check whether the end of the penetration vector is inside the polygon and if it is, u can return that penetration length because it is now a valid collison.
Although this way will fail if parts of the circle is engulfing the polygon on oneside and the parts on another side of the same polygon. The trick to solve this is to get the shortest "valid" point from polygon (use SAT again!) and immediately place the circle there. so no penetration occurs.
Or u could make convex poly's using triangles and use metanets way of checking collision with triangles (n' other fancy shapes) using the tiles. I find using metanets solution of tiles in 2D very super. because its sooo fast in flash itself and when tried in C++ using ogl/dx or any api, its even faster (than flash) and u can make laaarge maps with super game play.
I really hope this helped man.
Author
The SAT is nice, and all. I'm using a version of it for swept circle vs. polygon collisions, but that method takes O(N), and I swear plain overlap (velocity = 0) tests don't need to take that long. Now, my polygons are all pretty simple (3-6 sides, in general), so it could be that O(ln N) methods have constants terms that are too large to make them worth while. If anyone has actually experimented with O(ln N) methods and discovered that they are slower than SAT-type methods for 3-6 sided polygons, I'd be glad to hear it. I'd be most glad, however, to hear about a slick O(ln N) algorithm that actually does increase collision detection speeds.
John Edwards
John Edwards
Author
Okay, I've figured out a method that more-or-less meets the criteria:
David Eberly defines a function called ExtremeVert in his game physics book that returns the index of the vertex with the largest projection onto a given direction vector in O(ln N) time for convex polygons with clockwise (or counter-clockwise) ordered vertices.
If you pass ExtremeVert the vector pointing from the polygon's center to the circle's center, it returns the vertex that (as much as we need it to be) is, or is in the edge that is the the closest feature to the center of the circle.
That means, to find the overlap, we just have to overlap-test against two edges and a vertex (which takes constant time).
This algorithm takes O(ln N) and doesn't require any elaborate data structures, so it satisfies my requirements. If people know better methods, I'd still be interested in hearing them, though.
John Edwards
David Eberly defines a function called ExtremeVert in his game physics book that returns the index of the vertex with the largest projection onto a given direction vector in O(ln N) time for convex polygons with clockwise (or counter-clockwise) ordered vertices.
If you pass ExtremeVert the vector pointing from the polygon's center to the circle's center, it returns the vertex that (as much as we need it to be) is, or is in the edge that is the the closest feature to the center of the circle.
That means, to find the overlap, we just have to overlap-test against two edges and a vertex (which takes constant time).
This algorithm takes O(ln N) and doesn't require any elaborate data structures, so it satisfies my requirements. If people know better methods, I'd still be interested in hearing them, though.
John Edwards
You probably could even adapt Eberly's algorithm to return point closest to circle center directly, without hacks... (i guess his method uses some kind of binary search that will work directly with distances too).
Author
Eberly uses a binary search to find where the direction vector dotted with the edge vector changes signs. It certainly would be nice to adapt the algorithm to find the closest point, though, since using ExtremeVert can break down when the circle's center is inside the polygon. Practically speaking, it's only a problem for oblong polygons with a lot of vertices, which won't come up too often, but it would still be nice to have an algorithm that works in all cases.
John Edwards
John Edwards
I didn't read the whole thread, but if you're looking for an effective method for finding the closest point on a 2D convex polygon to a point (the first step in a discrete circle vs. polygon test), you might look into the Dobkin-Kirkpatrick hierarchy. In 3D it's a bit complicated, but the 2D version is quite straightforward. It's useful for other queries (such as extremal vertex) as well.
Quote:Original post by PistachioPro
Eberly uses a binary search to find where the direction vector dotted with the edge vector changes signs. It certainly would be nice to adapt the algorithm to find the closest point, though, since using ExtremeVert can break down when the circle's center is inside the polygon. Practically speaking, it's only a problem for oblong polygons with a lot of vertices, which won't come up too often, but it would still be nice to have an algorithm that works in all cases.
John Edwards
if you mostly have polygons with few vertices, O(n) algorithms may be overally faster than O(log(n)) (that's because actual times will be like a*n_b versus c*log(n)+d ; this "O" only tells you how it behaves with large n)
Try finding the edge where difference of distances between edge vertices and circle center changes sign(i.e. distance(vertice1,circle_center)-distance(vertice2, circle_center)) (like this dot product it changes sign on closest and farthest).
As for cases when circle center is on inside, the problem is that a: this way circle could be not intersecting any edges at all, b: from inside, it is concave and not convex.
[Edited by - Dmytry on April 2, 2006 4:05:37 AM]
Author
@ jyk: I've looked around for information on Dobkin-Kirkpatrick hierarchies, and I found a lot of papers using them, but no information on how to build them. Do you have a link?
@Dmytry: Yeah, I know that when dealing with small input sizes O(ln N) algorithms are often slower than O(N), but I figured there might be some simple binary search-type method for finding the closest vertex to a point that would shave off a few dot products from the overlap calculation (which might reduce total collision calculation time by 10%, or more).
As far as searching on distance(vertice1,circle_center)-distance(vertice2, circle_center) is concerned, I don't know how to do that, since that value isn't strictly increasing or decreasing around the polygon.
Unless it turns out I can get a hold of an explanation of Dobkin-Kirkpatrick hierarchies, and it looks like they're worthwhile, I'll probably just do an O(N) search through all the vertices for the one that has the smallest squared distance to the circle center.
Thanks for the suggestions, though. This has been an interesting exercise.
John Edwards
@Dmytry: Yeah, I know that when dealing with small input sizes O(ln N) algorithms are often slower than O(N), but I figured there might be some simple binary search-type method for finding the closest vertex to a point that would shave off a few dot products from the overlap calculation (which might reduce total collision calculation time by 10%, or more).
As far as searching on distance(vertice1,circle_center)-distance(vertice2, circle_center) is concerned, I don't know how to do that, since that value isn't strictly increasing or decreasing around the polygon.
Unless it turns out I can get a hold of an explanation of Dobkin-Kirkpatrick hierarchies, and it looks like they're worthwhile, I'll probably just do an O(N) search through all the vertices for the one that has the smallest squared distance to the circle center.
Thanks for the suggestions, though. This has been an interesting exercise.
John Edwards
yep, it doesn't strictly increase or decrease but the point is that on one side it is positive and on other side it is negative, and it crosses zero on closest and farthest points. Same as with this dot product in the Eberly's algorithm you told about(btw, unless edge vector is normalized, it too isn't strictly increasing or decreasing). For binary search you only need sign, i.e. what vertice on the edge is closest to the circle center, value itself does not matter. Binary search works like that: take an interval that has positive value on one end and negative on other, split it in two halves and check whever value in center has positive value or negative. Use sub-interval that has different signs on ends. To find closest and not farthest point you need to choose "side" of interval that has closer distances.
Since you have Eberly's algorithm, i would recommend to try to look into it and understand. It should be trivial to change it to do what you want; i don't have this book nearby, but know approximately how it works.
Since you have Eberly's algorithm, i would recommend to try to look into it and understand. It should be trivial to change it to do what you want; i don't have this book nearby, but know approximately how it works.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
