Sign in to follow this  
Jouei

Circle to Polygon Collision Detection (Solved)

Recommended Posts

Hi i hope this is the right place for this. First a detail about me i am utterly horribly lost when it comes to anything above basic algebra. So half of what i have for the collision does not make 100% sence to me and i am being host about that. Ok on to the point over the last .... 4 days i have piece together a Poly to Poly collision system. I wanted to add Circle to Poly so i could have stuff roll down hills and all that kind of neat stuff. right now my code is broken some where and i am not sure where as most of what i have read for tutorials or random snippets of code here and there have goten me to where i am now but i am stuck and at a total lose. Here is what i do understand. Using Sat ( Separating Axis theorem )I have been able to Do poly to poly collision detection and as i understand it takes the points of your poly and projects them onto an axis and if there is a separation on any axis there can be no collision. The concept should be some what the same with a Circle you need to project it on to the axis some how and well that is the part i think is busted and does not work right. Here is where i think my probably may lie in one or two of these here functions.

//Some Vector Accessorie functions

        float VectorLength(Vector2 a)
        {
            float length_squared = (a.X * a.X) + (a.Y * a.Y);
            return (length_squared * length_squared);
        }

        Vector2 vectorPerp(Vector2 a)
        {
            Vector2 p = new Vector2(-a.Y, a.X);
            return p;
        }

        Vector2 vectorSub(Vector2 a, Vector2 b)
        {
            Vector2 c = new Vector2(a.X - b.X, a.Y - b.Y);
            return c;
        }

        This is where i think the problem is
        // project sphere along an axis, and find it's dimensions.
        void sphereInterval(Vector2 axis, Vector2 c, float r, ref float min, ref float max)
        {
            float length = VectorLength(axis);
            float cn = Vector2.Dot(axis, c);
            min = cn - (r + length);
            max = cn + (r + length);
        }
       
        Another possible spot could be here more likely the one above

        bool collidePolygonSphereAxis(Vector2 axis, Vector2[] a, Vector2 c, float r)
        {
            float mina = 0, maxa = 0;
            float minb = 0, maxb = 0;

            polygonInterval(axis, a, ref mina, ref maxa);
            sphereInterval(axis, c, r, ref minb, ref maxb);

            return (mina <= maxb && minb <= maxa);
        }



The sphereInterval function is where i think the problem lies as for some reason regardless of the Circle location on the screen i always get a collision. I thank you for your time and for reading this rather boring and ranty post. Best Regards Jouei. [Edited by - Jouei on September 10, 2009 7:29:01 PM]

Share this post


Link to post
Share on other sites
SAT is general and applies to a pair of convex objects. When you have two convex polygons, the number of potential separating directions is finite. This makes it easy to implement an algorithm. When one of the objects is a circle, you no longer have a finite set of directions.

What I would do to test for overlap of circle and polygon (not necessarily convex) is the following.


bool Overlapping (Polygon polygon, Circle circle)
{
if (polygon.Contains(circle.center))
{
return true;
}
for (i = 0; i < polygon.numEdges; ++i)
{
if (Distance(circle.center, polygon.edge[i]) < circle.radius)
{
return true;
}
}
return false;
}


Share this post


Link to post
Share on other sites
I will have to try that :)
I had the idea of checking it verus points of the poly being in the Circle but that would of lead to a case of any segment crossing through the cricle would not be detected. ill will post back after trying that and let you know how it went.

Regards Jouei.

Share this post


Link to post
Share on other sites
I don't know if you've seen this, but they explain circle vs. poly quite well:
http://www.metanetsoftware.com/technique/tutorialA.html

I don't want to hijack your thread but I am having some problems with SAT aswell. My collision detection works like a charm, but when one of my poly (which moves) hits a poly that doesn't move, things aren't working the way they should. I'm not quite sure what I am supposed to do with the minumum translation vector. Right now when I detect a hit, I'm just assigning the minimum translation vector (which I calculated) to the velocity vector I have. What happens is that the object just kinda slides along my static poly for one or two seconds and just stops. It instantly gets a lot slower and just stops on the shape and gets stuck. I was kinda hoping that somebody here might have experienced this too or has had the same problem.

Sorry for posting this here, if you want, I will remove the post and make a thread. But I think its a problems that can be solved quickly since I sure I'm calculating the vector correctly.

Share this post


Link to post
Share on other sites
No its ok that you posted you take the MTD and apply that to your objects postion and that is what keep it from entering the object its colliding against i just do a simple

Poly.Postion -= MTD;

Given that they are two vectors that should be sufficient.

and yes i have seen that tutorial however i am very poor with math i know what i should be doing just not how to get there in all honesty :)

Concepts i understand, the math not so much.

As for what you sugessted Dave Eberly

For distance is this how you function computes it

(BCircle.Postion.X - Edge.X) + (BCircle.Postion.Y - Edge.Y)

Let me know if that is correct.

Also for the edge you function takes is that just a vertice or an actual edge
eg

foo.X = (BCircle.X - BPoly.X)
foo.Y = (BCircle.Y - BPoly.Y)

Edge = (-foo.y,foo.x)

From what i am gettig i need to get the distance of the edge from the Center of the circle and check to see if that is less then the radius.

What i am unsure of is how to get the distance of an edge not just the single point.

Regards Jouei

Share this post


Link to post
Share on other sites
probably best to break it down a little bit.



bool pointInPolygon(const Vector& p, const Vector& n, const Vector* v, int vnum)
{
unsigned int flags=0;
for(int i = 0, j=vnum-1; i < vnum; j=i, i++)
{
Vector en = ((v[i] - v[j]) ^ n);
float sign = (p - v[i]) * en;
if(sign >= 0.0f) flags |= (1 << i);
}
return ((flags == 0) || (flags == (1 << vnum)-1));
}

float closestPointOnPlane(const Vector& p, const Vector& n, const Vector& origin, Vector& closest)
{
float n2 = (n * n);
if(n2 > 1.0E-8f) n /= n2;
float d = ((p - origin) * n);
closest = p - n * (d / n2);
return (d * d) / n2;
}

float closestPointOnEdge(const Vector& p, const Vector& a, const Vector& b, Vector& closest)
{
Vector e = (b - a);
Vector f = (p - a);
float e2 = (e * e);
float t = (f * e) / e2;
if (t < 0.0f) t = 0.0f;
else if (t > 1.0f) t = 1.0f;
closest = a + e * t;
Vector d = (closest - p);
return (d * d);
}

float closestPointOnPolygon(const Vector& p, const Vector* v, int vnum, Vector& closest)
{
Vector n = (v[2] - v[0]) ^ (v[1] - v[0]);

if(pointInPolygon(p, n, v, vnum))
{
return closestPointOnPlane(p, n, v[0], closest);
}

float d2=-1;
for(int i = 0, j = vnum-1; i < vnum; j=i, i++)
{
Vector edge_closest;
float edge_dist2 = closestPointOnEdge(p, v[j], v[i], edge_closest);

if((d2 < 0.0f) || (edge_dist2 < d2))
{
d2 = edge_dist2;
closest = edge_closest;
}
}
return d2;
}


This is 3D. 2D would be somewhat simplified.

[Edited by - oliii on September 13, 2009 5:01:54 AM]

Share this post


Link to post
Share on other sites
as for your collision response using the MTD, you can do this.


float mtd2 = (mtd * mtd); // mtd length squared.

// move polygon away
polygon.position += mtd;

// reflect velocity on collision normal (which is the MTD itself)
const float cor = 0.3f; // coefficient of restitution (in range [0.0f, 1.0f]).

if(mtd2 > 1.0E-8f)
polygon.velocity -= (1.0f + cor) * ((polygon.velocity * mtd) / (mtd2)) * mtd;


EDIT : oh yeah....

Share this post


Link to post
Share on other sites
I would to thank you for your respone Oliii.

I only have one problem i have a hard time converting alot of your code to C# :p
i do actually have that zip of yours and that is how i built the Polygon to Polygon Collision i have right now :) so thanks a bunch there.

but Alas i am still having problems the one underlying problem is that in the code you posted not only to understand less then 1/3 of it :p

but it does not convert to C# almost at all due to the fact that one can not convert the Xna Vector2 type that i have to a float :p

Anyways any thoughts on this.

Also with the last function there the closestPointOnPolygon Would i take the return value and compare it to the radius of the circle ?

As you can see i am still a bit lost sorry about that.

Regards Jouei.

Share this post


Link to post
Share on other sites
See this brief document for computing the distance from a point to a line, ray, or segment (edge). Olii's closestPointOnEdge is an implementation, but note that it returns the squared distance. If performance is an issue, my document mentions that you can defer the division until you actually need it. The modification to Olii's code would be to compute t = f*e without the division. If t < 0, then set the closest point to the corresponding edge endpoint--no division ever occurs. If t > e2, then set the closest point to the corresponding edge endpoint. Again, no division occurs. Otherwise, set t = t/e2 and compute the closest point. Returning squared distance avoids a sqrt call. In my pseudocode, you would compare the returned value to the squared radius of the circle.

Olii posted 3D code for point-in-polygon. The 2D version is well known. I have an implementation at my web site, but you can find others by searching the Internet.

In Olii's code, dot product of vectors is U*V and cross product of vectors is U^V. I am not a fan of overloading these using operators, so if you look at my source code, dot product is U.Dot(V) and cross product is U.Cross(V). [In differential geometry, U.Wedge(V) is not technically the same mathematical concept as U.Cross(V) anyway...]

Share this post


Link to post
Share on other sites
Wow that helped out a lot. Thank you very much all that was very much well appreciated and hey i learned some math on the way there.

Ok, one more final Question is there anyway to get a minimal translation distance from this.

Thanks for your patience with me so far i really do appreciate it.

Regards Jouei.

I gave you dave and oliii a rating but it seems im so low it made next to no impact sorry. ^_^

Share this post


Link to post
Share on other sites
once yo have the closest point on the polygon, you can work out the MTD quite easily, and also the collision test.

If the distance squared is greater than the radius of the sphere squared, no collision, else....




bool collide(const Sphere& sphere, const Polygon& polygon, Vector& mtd)
{
Vector closestPoint;
float distance_squared = closestPointOnPolygon(sphere.position, sphere.radius, polygon.vertices, polygon.numvertices, closestPoint);

if(distance_squared > (sphere.radius * sphere.radius))
return false;

float distance = sqrt(distance_squared);
mtd = (sphere.position - closest) * ((sphere.radius - distance) / distance);
return true;
}


a small demo.

I use Dave Eberly's triangle distance routine. It's more optimised than the code above, and returns a 's' and 't' values, the parametric representation of the point (that you can use to say, interpolate for texture coordinates and so on).

Share this post


Link to post
Share on other sites
Well i got that working nicely now. I would like to thank you all for your input and taking the time to help this math gibbled me.

It seems everything is working as expected i still got a bit to go to improve my collision system but the hard part i believe is done and i am truly grateful for that :)

So thanks again and i will now marked this Post as solved when i get it all done i will probably post all the code and make a doc for it as it is for C# and XNA witch i seem to find is most commonly used by newer game programmers.

Best regards Jouei.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this