SAT Question

[lotios611]

I'm trying to implement the SAT and have been having some troubles. Here's some code:

This method returns true no matter what.

Code: Select all

//Collision.cpp
bool Collision::PolygonPolygonCollision(Polygon &a, Polygon &b)
{
	//The axis to project onto
	Vector2 axisToProjectOnto;
	//The minimum and maximum projections of the edges on the axes
	float minA = a.getPoint(0).projectVector(axisToProjectOnto), 
		  maxA = a.getPoint(0).projectVector(axisToProjectOnto), 
		  minB = b.getPoint(0).projectVector(axisToProjectOnto), 
		  maxB = b.getPoint(0).projectVector(axisToProjectOnto);
	//For all of the points in a
	for (int i = 0; i < a.getNumberOfPoints(); i++)
	{
		//Calculate the axes to project onto
		axisToProjectOnto.x = a.getPoint(i).y;
		axisToProjectOnto.y = -a.getPoint(i).x;
		//Project the edges of a onto the axes
		//For All of the points in a
		for (int j = 0; j < a.getNumberOfPoints(); j++)
		{
			//Project the edge onto the axis and figure out the minimum and
			//maximum values for a
			if (a.getPoint(j).projectVector(axisToProjectOnto) < minA)
			{
				minA = a.getPoint(j).projectVector(axisToProjectOnto);
			}
			else if (a.getPoint(j).projectVector(axisToProjectOnto) > maxA)
			{
				maxA = a.getPoint(j).projectVector(axisToProjectOnto);
			}
		}
		if (minA > maxB || maxA < minB)
		{
			return false;
		}
	}
	//For all of the points in b
	for (int i = 0; i < b.getNumberOfPoints(); i++)
	{
		//Calculate the axes to project onto
		axisToProjectOnto.x = b.getPoint(i).y;
		axisToProjectOnto.y = -b.getPoint(i).x;
		//Project the edges of a onto the axes
		//For All of the points in b
		for (int j = 0; j < b.getNumberOfPoints(); j++)
		{
			//Project the edge onto the axis and figure out the minimum and
			//maximum values for b
			if (b.getPoint(j).projectVector(axisToProjectOnto) < minB)
			{
				minB = b.getPoint(j).projectVector(axisToProjectOnto);
			}
			else if (b.getPoint(j).projectVector(axisToProjectOnto) > maxB)
			{
				maxB = b.getPoint(j).projectVector(axisToProjectOnto);
			}
		}
		if (minA > maxB || maxA < minB)
		{
			return false;
		}
	}
	return true;
}

This is how I set up the polygons.

Code: Select all

//Main.cpp
	polygon.addPoint(Vector2(imageX, imageY));
	polygon.addPoint(Vector2(imageX, imageY));
	polygon.addPoint(Vector2(imageX+width, imageY+height));
	polygon2.addPoint(Vector2(image2X, image2Y));
	polygon2.addPoint(Vector2(image2X, image2Y+height2));
	polygon2.addPoint(Vector2(image2X+width, image2Y));

//Polygon.cpp
void Polygon::addPoint(Vector2 point)
{
	point.normalize();
	_points.push_back(point);
	_numberOfPoints++;
}

When explaining, please keep in mind that I'm only 13 so I barely understand this.

[Bakkon]

At first glance:

Code: Select all

polygon.addPoint(Vector2(imageX, imageY));
polygon.addPoint(Vector2(imageX, imageY));
polygon.addPoint(Vector2(imageX+width, imageY+height));

This looks like a line to me.

[lotios611]

Fixed, but it still doesn't work.

[lotios611]

I think I'm doing it really wrong or at least inefficiently but I really want to understand this.

[Ginto8]

ok at the moment I really don't want to read through a bunch of code, but I'll provide you with my implementation:

Vector.h:

Code: Select all

#ifndef VECTOR_H
#define VECTOR_H

#include <cmath>

namespace g {

using namespace std;

const double PI = 3.14159265358979;

// so that I can use this type in Vector
template<typename T>
class Point2;

// A vector. If you want a combined location and direction, you'll need a Point too.
template<typename T>
struct Vector2 {
    T x,y;

    Vector2() : x(0),y(0) {}
    Vector2(T _x,T _y) : x(_x),y(_y) {}
    Vector2(const Vector2& v) : x(v.x),y(v.y) {}
    Vector2(const Point2<T>& p) : x(p.x),y(p.y) {}
// This is inefficient because of the trig; try not to use it much.
    Vector2(T rot) : x(cos(rot*180/PI)),y(sin(rot*180/PI)) {}

    Vector2 operator-() const { return Vector2(-x,-y); }
    Vector2 operator+(Vector2 other) const { return Vector2(x+other.x,y+other.y); }
    Vector2 operator-(Vector2 other) const { return Vector2(x-other.x,y-other.y); }
    Vector2 operator*(T s) const { return Vector2(x*s,y*s); }
    Vector2 operator/(T s) const { return *this * (1/s); }

    Vector2& operator+=(Vector2 other) { x += other.x; y += other.y; return *this; }
    Vector2& operator-=(Vector2 other) { x -= other.x; y -= other.y; return *this; }
    Vector2& operator*=(T s) { x *= s; y *= s; return *this; }
    Vector2& operator/=(T s) { return *this *= 1/s; }

    bool operator==(Vector2 other) const { return x == other.x && y == other.y; }
    bool operator!=(Vector2 other) const { return !(*this == other); }

    T mag() const { return sqrt(x*x+y*y); }
    Vector2 normalized() const { return *this / this->mag(); }
    Vector2& normalize() { return *this /= this->mag(); }
};

// Typical vector operations (dot product, projection)
template<typename T>
T dotProd(const Vector2<T> A,const Vector2<T> B) { return A.x*B.x+A.y*B.y; }
template<typename T>
Vector2<T> project(const Vector2<T> A,const Vector2<T> B) { return Vector2<T>(A.x*B.x,A.y*B.y); }

// a 2D point
template<typename T>
struct Point2 {
    T x,y;

    Point2(T _x = (T)0,T _y = (T)0) : x(_x),y(_y) {}
    Point2(Vector2<T> v) : x(v.x),y(v.y) {}

    Point2 operator+(Vector2<T> v) const { return Point2(x+v.x,y+v.y); }
    Point2 operator-(Vector2<T> v) const { return Point2(x-v.x,y-v.y); }

    Point2& operator+=(Vector2<T> other) const { x += other.x; y += other.y; return *this; }
    Point2& operator-=(Vector2<T> other) const { x -= other.x; y -= other.y; return *this; }

    bool operator==(Point2 other) const { return x == other.x && y == other.y; }
    bool operator!=(Point2 other) const { return !(*this == other); }

    T abs() const { return sqrt(x*x+y*y); }
};

// Returns a vector that points from A to B.
// Effectively subtraction
template<typename T>
Vector2<T> diff(Point2<T> A,Point2<T> B) { return Vector2<T>(A.x-B.x,A.y-B.y); }

typedef Vector2<float> Vector;
typedef Vector2<int> IntVector;
typedef Point2<float> Point;
typedef Point2<int> IntPoint;

}

#endif

Rect.h:

Code: Select all

#ifndef RECT_H
#define RECT_H

#include "Vector.h"

namespace g {

struct Rect {
    Point center;
    Vector size,scale;
    float rot;
    Point coords[4];

    Rect(Point Center = Point(),Vector Size = Vector(),float Rot = 0.f,Vector Scale = Vector(1.f,1.f)) :
        center(Center),size(Size),scale(Scale),rot(Rot) {}
    Rect(float x,float y,Vector Size = Vector(),float Rot = 0.f,Vector Scale = Vector(1.f,1.f)) :
        center(x,y),size(Size),scale(Scale),rot(Rot) {}
    Rect(float x,float y,float w,float h,float Rot = 0.f,Vector Scale = Vector(1.f,1.f)) :
        center(x,y),size(w,h),scale(Scale),rot(Rot) {}
    Rect(float x,float y,float w,float h,float Rot = 0.f,float scaleX,float scaleY) :
        center(x,y),size(w,h),scale(scaleX,scaleY),rot(Rot) {}
    Rect(const Rect& other) : center(other.center),size(other.size),scale(other.scale),rot(other.rot) {}

    void calcCoords();

private:
    Vector relCoords[4];
    Point _center;
    Vector _size,_scale;
    float _rot;
};

struct Collision {
    bool colliding;
    Vector axis;

    Collision(bool col,Vector _axis = Vector()) : colliding(col),axis(_axis) {}
    operator void*() { return colliding ? this : 0; }
};

// tells if there's a collision; if collisionAxis == true, then it also returns the axis of minimal overlap.
Collision colliding(Rect& A,Rect& B,bool collisionAxis = false);

}

#endif

Rect.cpp:

Code: Select all

#include "Rect.h"
#include <cmath>

using namespace std;

float mod(float x,float y) {
    while(x > y)
        x-=y;
    while(x < y)
        x+=y;
    return x;
}

float& clamp(float& x,float min,float max) {
    x = mod(x,max-min);
    x += min;
    return x;
}

namespace g {

void Rect::calcCoords() {
    if(size == _size && rot == _rot && scale == _scale) {
        if(center != _center)
            for(int i=0;i<4;++i) {
                coords[i] = center+relCoords[i];
            }
        return;
    }
    _center = center;
    _size = size;
    _rot = rot;
    _scale = scale;

    Vector scaledSize(size.x*scale.x,size.y*scale.y);
    clamp(rot,0.f,360.f);
    Vector v[4] = { scaledSize,
                     Vector(-scaledSize.x,scaledSize.y),
                     -scaledSize,
                     Vector(scaledSize.x,-scaledSize.y) };
    if(rot == 0.f) {
        for(int i=0;i<4;++i)
            relCoords[i] = v[i];
    } else if(rot == 90.f) {
        relCoords[1] = v[0];
        relCoords[2] = v[1];
        relCoords[3] = v[2];
        relCoords[0] = v[3];
    } else if(rot == 180.f) {
        relCoords[2] = v[0];
        relCoords[3] = v[1];
        relCoords[0] = v[2];
        relCoords[1] = v[3];
    } else if(rot == 270.f) {
        relCoords[3] = v[0];
        relCoords[0] = v[1];
        relCoords[1] = v[2];
        relCoords[2] = v[3];
    } else {
        double rad = rot*180/pi;
        float sine = sin(rad),cosine = cos(rad);
        for(int i=0;i<4;++i) {
            relCoords[i] = Vector(dotProd(Vector(cosine,-sine),v[i]),dotProd(Vector(sine,cosine),v[i]));
        }
    }
    for(int i=0;i<4;++i) {
        coords[i] = center+relCoords[i];
    }
}

Collision colliding(Rect& A,Rect& B,bool collisionAxis) {
    // clamp rotation to 0-360
    clamp(A.rot,0.f,360.f);
    clamp(B.rot,0.f,360.f);

    // circular
    if((A.center-B.center).abs() > (A.size+B.size).mag())
        return Collision(false);
    // AABB
    if(mod(A.rot,180.f) == mod(B.rot,180.f)) {
        Vector minDist = A.size+B.size;
        Vector dist = A.center-B.center;
        dist = Vector(abs(dist.x),abs(dist.y));

        if(dist.x >= minDist.x || dist.y >= minDist.y)
            return Collision(false);
        return dist.x < dist.y ? Collision(true,collisionAxis ? diff(A.coords[0],A.coords[1]).normalized()) : Collision(true,diff(A.coords[1],A.coords[2]).normalized());
    }
    if(mod(A.rot,90.f) == mod(B.rot,90.f)) {
        Rect tmp = A;
        float temp = tmp.center.x;
        tmp.center.x = tmp.center.y;
        tmp.center.y = temp;
        tmp.rot += 90;
        return colliding(tmp,B);
    }

    A.calcCoords();
    B.calcCoords();

    Vector axis[4] = { diff(A.coords[0],A.coords[1]),
                       diff(A.coords[1],A.coords[2]),
                       diff(B.coords[0],B.coords[1]),
                       diff(B.coords[1],B.coords[2]) };
    for(int i=0;i<4;++i) {
        float AminMax[2],BminMax[2];
        for(int j=0;j<4;++j) {
            float Ax = project(Vector(A.coords[j]),axis[i]).mag(),Bx = project(Vector(A.coords[j]),axis[i]).mag();
            if(j == 0 || Ax < AminMax[0])
                AminMax[0] = Ax;
            if(Ax > AminMax[1])
                AminMax[1] = Ax;
            if(j == 0 || Bx < BminMax[0])
                AminMax[0] = Bx;
            if(Bx > BminMax[1])
                BminMax[1] = Bx;
        }
        if(AminMax[0] >= BminMax[1] || AminMax[1] <= BminMax[0])
            return Collision(false);
    }
    if(collisionAxis) {
        Vector Acenter(A.center),Bcenter(B.center);
        float min;
        int minRef;
        for(int i=0;i<4;++i) {
            float x = abs(project(Acenter,axis[i]).mag()-project(Bcenter,axis[i]).mag());
            if(i == 0 || x < min) {
                min = x;
                minRef = i;
            }
        }
        return Collision(true,axis[minRef]);
    }
    return Collision(true);
}

}

I probably did a few things wrong, but if anyone notices them please point them out, I don't like my code being not-so-good.

[Falco Girgis]

Man, oh man oh man... Some of you guys SERIOUSLY need to start using rotation matrices and stop throwing sin/cos in your calculations. I honestly can't tell what the fuck is going on when people are calculating their orientation of their vertices on the fly inside of their linear algebra routines.

[dandymcgee]

Man, oh man oh man... Some of you guys SERIOUSLY need to start using rotation matrices and stop throwing sin/cos in your calculations. I honestly can't tell what the fuck is going on when people are calculating their orientation of their vertices on the fly inside of their linear algebra routines.

That would make a great tutorial for your mini series.

[Falco Girgis]

Man, oh man oh man... Some of you guys SERIOUSLY need to start using rotation matrices and stop throwing sin/cos in your calculations. I honestly can't tell what the fuck is going on when people are calculating their orientation of their vertices on the fly inside of their linear algebra routines.

That would make a great tutorial for your mini series.

Seriously guys, look:

Say you have a vector2. Multiply this vector2 times a rotation matrix with angle theta to get the new, ROTATED vector:




SHAZAAM! You never even SEE sin/cos in any calculations whatsoever. Linear algebra (as I see it) is a way of geometrically abstracting trigonometry away from your math. That shit is gross!

[schwarb]

SHAZAAM! You never even SEE sin/cos in any calculations whatsoever. Linear algebra (as I see it) is a way of geometrically abstracting trigonometry away from your math. That shit is gross!

Totally agree. It make things so much easier to read and understand later on for both you and anyone else that needs to read your code. Not to mention you'll understand why matrices are interesting in the first place.

[Ginto8]

Man, oh man oh man... Some of you guys SERIOUSLY need to start using rotation matrices and stop throwing sin/cos in your calculations. I honestly can't tell what the fuck is going on when people are calculating their orientation of their vertices on the fly inside of their linear algebra routines.

That would make a great tutorial for your mini series.

Seriously guys, look:

Say you have a vector2. Multiply this vector2 times a rotation matrix with angle theta to get the new, ROTATED vector:




SHAZAAM! You never even SEE sin/cos in any calculations whatsoever. Linear algebra (as I see it) is a way of geometrically abstracting trigonometry away from your math. That shit is gross!

I was actually doing that... just without abstracting away the calculation. I guess I should have put in a rotate() function for my vectors.