//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);
}
Circle to Polygon Collision Detection (Solved)
Author
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.
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]
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.
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) < circle.radius) { return true; } } return false;}
Author
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.
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.
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.
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.
Author
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
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
probably best to break it down a little bit.
This is 3D. 2D would be somewhat simplified.
[Edited by - oliii on September 13, 2009 5:01:54 AM]
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 - v[j]) ^ n); float sign = (p - v) * 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, 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]
as for your collision response using the MTD, you can do this.
EDIT : oh yeah....
float mtd2 = (mtd * mtd); // mtd length squared.// move polygon awaypolygon.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....
Author
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.
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.
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...]
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...]
Author
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. ^_^
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. ^_^
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
