Jump to content
  • Advertisement
Sign in to follow this  
Grant1219

2D polygon collision bug

This topic is 4230 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I used a Code Project tutorial to make this simple collision system and made sure the code did the same thing as the sample code for the tutorial, but there seems to be one last bug I haven't been able to find. The bug is most likely within the CPoly::Collision(...) function, so a lot of this code is just extra, but if anyone can figure out what is going wrong I'd really appreciate it.
class CVec2D
{
public:
    float x, y;
    float magnitude;

    CVec2D() {}
    CVec2D(float xPos, float yPos) : x(xPos), y(yPos) {}
    ~CVec2D() {}
    float Magnitude() {return sqrt(x * x + y * y);}
    void Normalize() {x = x / Magnitude(); y = y / Magnitude();}
    float DotProduct(CVec2D vec) {return x * vec.x + y * vec.y;}
};

struct CollisionResult
{
    bool collided, willCollide;
    CVec2D translateVec;
};

class CPoly
{
private:
    vector<CVec2D> m_points, m_sides;
    float m_radius;

    void ProjectPoly(CVec2D axis, CPoly &poly, float &min, float &max)
    {
    	// project all the polygon's points onto the axis using the dot product
    	float dp = axis.DotProduct(poly.GetPoint(0));
    	min = dp;
    	max = dp;
    	for(int i = 0; i < poly.PointAmount(); i++)
    	{
    	    dp = poly.GetPoint(i).DotProduct(axis);
    	    if(dp < min) min = dp;
	    else if(dp > max) max = dp;
	}
    }
    float IntervalDist(float min, float max, float min2, float max2)
    {
	if(min < min2) return min2 - max;
	else return min - max2;
    }
public:
    CPoly() {}
    ~CPoly() {}

    void AddPoint(float x, float y) {m_points.push_back(CVec2D(x, y));}
    void Clear() {m_points.clear();}
    int PointAmount() {return m_points.size();}
    int SideAmount() {return m_sides.size();}
    CVec2D GetPoint(int index) {return m_points[index];}
    CVec2D GetSide(int index) {return m_sides[index];}
    void BuildSides()
    {
    	CVec2D v1, v2;
    	m_sides.clear();
    	for(int i = 0; i < m_points.size(); i++)
    	{
    	    v1 = m_points;
	    if(i + 1 < m_points.size()) v2 = m_points[i + 1];
	    else v2 = m_points[0];
	    m_sides.push_back(CVec2D(v2.x - v1.x, v2.y - v1.y));
	}
	// find the minimum radius that surrounds the polygon
	float currentMax = 574969476.0;
	CVec2D cen = Center();
	for(int i = 0; i < m_points.size(); i++)
	{
	    float side1, side2;
	    side1 = fabs(m_points.x - cen.x);
	    side2 = fabs(m_points.y - cen.y);
	    float dist = sqrt(side1 * side1 + side2 * side2);
	    if(dist > currentMax) currentMax = dist;
	}
	m_radius = currentMax;
    }
    CVec2D Center()
    {
	float xTotal = 0, yTotal = 0;
	for(int i = 0; i < m_points.size(); i++)
	{
	    xTotal += m_points.x;
	    yTotal += m_points.y;
	}
	float xCenter = xTotal / m_points.size();
	float yCenter = yTotal / m_points.size();
	return CVec2D(xCenter, yCenter);
    }
    float Radius() {return m_radius;}
    CollisionResult Collision(CPoly &poly, CVec2D velocity)
    {
	CollisionResult result;
	result.collided = true;
	result.willCollide = true;
	result.translateVec = CVec2D(0, 0);
	// check circle collision first
	CVec2D cen1 = Center(), cen2 = poly.Center();
	if(pow(cen1.x - cen2.x, 2) + pow(cen1.y - cen2.y, 2) > pow(Radius() + poly.Radius(), 2))
	{
	    result.collided = false;
	    result.willCollide = false;
	    return result;
	}
	float minIntervalDist = 4294967295;
	CVec2D translationAxis(0, 0);
	CVec2D side(0, 0), transAxis(0, 0);
	// loop through all the sides
	for(int i = 0; i < m_sides.size() + poly.SideAmount(); i++)
	{
	    if(i < m_sides.size()) side = m_sides;
	    else side = poly.GetSide(i - m_sides.size());

	    // find the sides normal
	    CVec2D axis = CVec2D(-side.y, side.x);
            /*
            without this Normalize() here the collision detection works perfect,
            but if they touch the one poly is "teleported" a few thousand pixels away
            
            with it here the collision detection has a few bugs, but the repositioning of the poly works fine
            */
	    axis.Normalize();

	    float min = 0, max = 0, min2 = 0, max2 = 0;
	    ProjectPoly(axis, *this, min, max);
	    ProjectPoly(axis, poly, min2, max2);

	    if(IntervalDist(min, max, min2, max2) > 0) result.collided = false;

	    // check if the polygons will collide
	    float velocityProj = axis.DotProduct(velocity);

       	    if(velocityProj < 0) min += velocityProj;
	    else max += velocityProj;

	    float intervalDist = IntervalDist(min, max, min2, max2);
	    if(intervalDist > 0) result.willCollide = false;

	    // nothing collides
	    if(!result.collided && !result.willCollide) break;

	    intervalDist = fabs(intervalDist);
	    if(intervalDist < minIntervalDist)
	    {
		minIntervalDist = intervalDist;
		translationAxis = axis;
		CVec2D vec(Center().x - poly.Center().x, Center().y - poly.Center().y);
		if(vec.DotProduct(translationAxis) < 0)
		{
		    translationAxis.x = -translationAxis.x;
		    translationAxis.y = -translationAxis.y;
		}
	    }
        }
	if(result.willCollide)
	{
	    // calc the translate vector for the polygon
	    CVec2D translateVec(translationAxis.x * minIntervalDist, translationAxis.y * minIntervalDist);
	    result.translateVec = translateVec;
	}
	return result;
    }
};

Share this post


Link to post
Share on other sites
Advertisement
Could you describe the bug you're noticing? Is collision not working altogether, only part of the time, or something else? If you're receiving a runtime error, post that as well.

Share this post


Link to post
Share on other sites
I'll give you a visual example since it will be easier for you to see the bug.

The dotted line is where it stops the polygon, the bug only happens when the side has that kind of slant(on either side).
Photo Sharing and Video Hosting at Photobucket

Share this post


Link to post
Share on other sites
From the diagram you drew, it looks like you are using bounding boxes for collisions. Since this will be in 2D, you might want to consider using pixel perfect collision detection.

The pixel perfect collisions will solve the irregular shapes colliding with other irregular shapes. You can find lots of info by just googling it, or do a forum search.

Share this post


Link to post
Share on other sites
I'm not using bounding boxes, I'm projecting the polygons points onto a line and seeing if they overlap.

Also, for some reason I thought using pixel perfect collision detection was too slow for a bunch of objects. How many objects can pixel perfect collision handle? I'm guessing quite a lot with todays hardware. I'll google around for some more info. Thanks.

EDIT:
I'd much rather get this polygon collision system working because rotating and such would be much easier than with bitmasks, and I really don't need pixel perfect collision anyway.

[Edited by - Grant1219 on May 16, 2007 6:06:59 PM]

Share this post


Link to post
Share on other sites
Another way that you could try is to use line intersections. Its pretty accurate and I believe its simple to code up. Just make sure you look up intersecting two line segments.

Basically what you do is have each object have a bounding circle that is larger than the object. Then see if one object is within the other bounding circle. If its not, that one is ignored and check the remaining objects.

If its inside the circle, then you check whether each side of one object intersects the sides of the other one. It may seem like it is slow (and is with MANY MANY lines and objects) but you can do some checks to toss out ones that for sure will not intersect (thats what the bounding circles are for). Also, there might be some checks when actually checking if the lines intersect or not that can speed it up.

Take a look at http://www.processinghacks.com/hacks/detecting-line-to-line-intersection and look at the segIntersection() function. That should help out.

What kind of objects are you using? Are they all random or completely irregular?

As for your questions about pixel perfect collision, I believe it can handle many objects one screen if you are smart about HOW and WHAT objects to test. Like adding bounding boxes/circles that are larger than the object and you can easily check what ones MIGHT collide and narrow it down from there. Again, I'm not an expert with the pixel perfect collisions, I just read about then and these are my views on it. And with todays hardware, I'm sure that it isn't enough to slow it down.

Share this post


Link to post
Share on other sites
Well the line intersection test method seems to be fine as far as detecting the collision, but how would I know where to move the colliding polygon to get it out of the other polygon?

Share this post


Link to post
Share on other sites
What lines are you projecting them onto? If you haven't already, you might want to check out the N Tutorial on collision detection (google it). It looks to me like you're projecting them onto the x and y axes, when you should be projecting them onto lines parallel to every edge of both polygons.

Share this post


Link to post
Share on other sites
I'm projecting the lines onto the perpendicular axes of each side.


CVec2D axis = CVec2D(-side.y, side.x);
axis.Normalize();
float min = 0, max = 0, min2 = 0, max2 = 0;
ProjectPoly(axis, *this, min, max);
ProjectPoly(axis, poly, min2, max2);



This is the tutorial I used, link. I have looked at the N Tutorials collision tutorial and it uses the same method I think (the Separating Axis Method).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!