🔒 Locked 🎮 Unity

[solved][c++] OBB colission detection problem

Started by d1rk Oct 22, 2009 at 4:41 AM 6 replies 2.5k views

Original Post

Oct 22, 2009 at 4:41 AM

I've written a function to test if two obb's collide but it doesn't work. Well sometimes it works fine but other times it doesn't. So can someone tell me what i'm doing wrong? You can download the demo and see for yourself here. (you can move around with wasd & q->down & e->up) My function takes 4 arguments: two objects(defined as an position and a rotation) and two boxes (defined as a position and a vector to the upperright corner). I've made a picture for clarity:

I use the seperating axes theorem to test if those two boxes collide. But I don't test on the cross product-axes yet because (according to wikipedia) they aren't that important and I want have it working first. My function is quite simple. First I calculate the matrix to rotate & translate from box1 to box2. Then I translate & rotate box2. Then I compare if the two boxes overlap on the x axis. If that's the case then the boxes aren't colliding. If they don't have any overlap go on with the function. Then I do the same thing on the Y and Z axes. And after that I translate & rotate box1. And test on the three axes again. The code:


bool physics::boxboxtest(bbox box1, objectinst obj1, bbox box2, objectinst obj2p)
{
    matrix44<double> transf1naar2 = (-box1.pos).gettransmatrix() * obj1.rot.getterugrotmatrix() * (-obj1.pos).gettransmatrix() * obj2.pos.gettransmatrix() * obj2.rot.getrotmatrix() * box2.pos.gettransmatrix();
/*
get...matrix calculates a matrix with the values of the vector.
so a.gettransmatrix() returns the translationmatrix that moves things in the direction of vector a.
a.getrotmatrix() returns a matrix that rotates points first a[0] degrees around the x axis and then a[1] degrees around the y axis and then a[2] degrees around the z axis.
"terug" is the dutch word for back so a.getterugrotmatrix() returns a matrix to rotate something back so that if vector b is (x,y,z)
b.transform(a.getrotmatrix() * a.getterugrotmatrix()) == b == (x,y,z)

I know i multiply the matrices in the wrong order. But i made my matrix class that way on purpose because it seems more logical to me.
A vector is rotated/translated in the same order as the matrices were multiplied.
*/

    vector3d<double> transfpos2 = vector3d<double>(0,0,0).transform(transf1naar2),
                     transfmax2 = box2.max.transform(transf1naar2) - transfpos2;

    for (short loop=0; loop<3; ++loop)
    {
        double
        min1 = -(box1.max[loop]),
        max1 = box1.max[loop],

        min2 = transfpos2[loop] - fabs(transfmax2[loop]),
        max2 = transfpos2[loop] + fabs(transfmax2[loop]);

        if (max1 < min2 || max2 < min1)
        {
            return false;
        }
    }

    matrix44<double> transf2naar1 = (-box2.pos).gettransmatrix() * obj2.rot.getterugrotmatrix() * (-obj2.pos).gettransmatrix() * obj1.pos.gettransmatrix() * obj1.rot.getrotmatrix() * box1.pos.gettransmatrix();

    vector3d<double> transfpos1 = vector3d<double>(0,0,0).transform(transf2naar1),
                     transfmax1 = box1.max.transform(transf2naar1) - transfpos1;

    for (short loop=0; loop<3; ++loop)
    {
        double
        min2 = -(box2.max[loop]),
        max2 = box2.max[loop],

        min1 = transfpos1[loop] - fabs(transfmax1[loop]),
        max1 = transfpos1[loop] + fabs(transfmax1[loop]);

        if (max1 < min2 || max2 < min1)
        {
            return false;
        }
    }

    return true;
}

If you think the problem is in the matrix or vector classes you can download the source files here: vector.hpp matrix.hpp I hope everything is clear now. Sorry for my bad English (I'm Dutch). And thank you for reading (and hopefully replying on) my long post. /////////////////////////// Edit /////////////////////////// I made a little mistake in my dotproduct function that ruined my code. Even though all the code below (this post) isn't completly bug-free this was the biggest bug and making my code working was easy. Oliii, thank you for your help. This is the working code:


inline void projeigenas (bbox box, unsigned char as, double& min, double& max)
{
    min = box.pos[as] - box.max[as];
    max = box.pos[as] + box.max[as];
}

inline void projas (bbox box, vector3d<double> as, double& min, double& max)
{
    double
    mid = scalairproduct(box.pos, as),
    afstand = scalairproduct(box.max, as.abs());

    min = mid - afstand;
    max = mid + afstand;
}

inline bool testeigenas(bbox box1, matrix44<double> mat1, bbox box2, matrix44<double> terugmat2, vector3d<double> posverschil, unsigned char as)
{
    vector3d<double> rotas = mat1.getrotkolom(as);
    double min1, min2, max1, max2, verschil = scalairproduct(posverschil, rotas);

    projeigenas(box1, as, min1, max1);
    rotas = rotas.transform(terugmat2);
    projas(box2, rotas, min2, max2);

    if (max1 < min2+verschil || max2+verschil < min1)
    {
        return false;
    }
    return true;
}

inline bool testas(bbox box1, matrix44<double> terugmat1, bbox box2, matrix44<double> terugmat2, vector3d<double> posverschil, vector3d<double> as)
{
    double min1, min2, max1, max2, verschil = scalairproduct(posverschil, as);

    vector3d<double> rotas = as.transform(terugmat1);
    projas(box1, rotas, min1, max1);
    rotas = as.transform(terugmat2);
    projas(box2, rotas, min2, max2);

    if (max1 < min2+verschil || max2+verschil < min1)
    {
        return false;
    }
    return true;
}

bool physics::boxboxtest(bbox box1, objectinst* obj1p, bbox box2, objectinst* obj2p)
{
    objectinst obj1 = *obj1p, obj2 = *obj2p;

    obj1.pos += obj1.beweging;
    obj2.pos += obj2.beweging;

    obj1.rot += obj1.draaing;
    obj2.rot += obj2.draaing;

    matrix44<double> mat1 = obj1.rot.getrotmatrix();
    matrix44<double> mat2 = obj2.rot.getrotmatrix();
    matrix44<double> terugmat1 = obj1.rot.getterugrotmatrix();
    matrix44<double> terugmat2 = obj2.rot.getterugrotmatrix();

    for (unsigned char loop=0; loop<3; ++loop)
    {
        if(!testeigenas(box1, mat1, box2, terugmat2, obj2.pos - obj1.pos, loop))
        {
            return false;
        }
        if(!testeigenas(box2, mat2, box1, terugmat1, obj1.pos - obj2.pos, loop))
        {
            return false;
        }
        for (short loop2=0; loop2<3; ++loop2)
        {
            if(!testas(box1, terugmat1, box2, terugmat2, obj2.pos - obj1.pos,
               kruisproduct(mat1.getrotkolom(loop), mat2.getrotkolom(loop2)) ))
            {
                return false;
            }
        }
    }
    return true;
}

matrix class:


#ifndef matrix_bib
#define matrix_bib
#include <string>
#include "basisbib.hpp"

template <class getal> class vector3d;

template <class getal>
class matrix44
{
    getal coords[4][4];

    public:

    void maakeenheidsm ()
    {
        coords[0][0] = 1; coords[0][1] = 0; coords[0][2] = 0; coords[0][3] = 0;
        coords[1][0] = 0; coords[1][1] = 1; coords[1][2] = 0; coords[1][3] = 0;
        coords[2][0] = 0; coords[2][1] = 0; coords[2][2] = 1; coords[2][3] = 0;
        coords[3][0] = 0; coords[3][1] = 0; coords[3][2] = 0; coords[3][3] = 1;
    }
    matrix44()
    {
        maakeenheidsm();
    }

    void set (getal coordsbuff[][4])
    {
        for (int kolom=0; kolom<4; ++kolom)
        {
            for (int rij=0; rij<4; ++rij)
            {
                coords[rij][kolom] = coordsbuff[rij][kolom];
            }
        }
    }
    matrix44(getal coordsbuff[][4])
    {
        set(coordsbuff);
    }

    void set (getal xx, getal yx, getal zx, getal wx, getal xy, getal yy, getal zy, getal wy, getal xz, getal yz, getal zz, getal wz, getal xw, getal yw, getal zw, getal ww)
    {
        coords[0][0] = xx; coords[0][1] = yx; coords[0][2] = zx; coords[0][3] = wx;
        coords[1][0] = xy; coords[1][1] = yy; coords[1][2] = zy; coords[1][3] = wy;
        coords[2][0] = xz; coords[2][1] = yz; coords[2][2] = zz; coords[2][3] = wz;
        coords[3][0] = xw; coords[3][1] = yw; coords[3][2] = zw; coords[3][3] = ww;
    }
    matrix44 (getal xx, getal yx, getal zx, getal wx, getal xy, getal yy, getal zy, getal wy, getal xz, getal yz, getal zz, getal wz, getal xw, getal yw, getal zw, getal ww)
    {
        coords[0][0] = xx; coords[0][1] = yx; coords[0][2] = zx; coords[0][3] = wx;
        coords[1][0] = xy; coords[1][1] = yy; coords[1][2] = zy; coords[1][3] = wy;
        coords[2][0] = xz; coords[2][1] = yz; coords[2][2] = zz; coords[2][3] = wz;
        coords[3][0] = xw; coords[3][1] = yw; coords[3][2] = zw; coords[3][3] = ww;
    }

    matrix44 operator = (matrix44 temp)
    {
        for (int kolom=0; kolom<4; ++kolom)
        {
            for (int rij=0; rij<4; ++rij)
            {
                coords[rij][kolom] = temp(rij, kolom);
            }
        }
        return *this;
    }

    getal& operator () (unsigned int x, unsigned int y)
    {
        return coords[x][y];
    }

    matrix44 operator * (matrix44 temp)
    {
        matrix44 temp2;
        for (int kolom=0; kolom<4; ++kolom)
        {
            for (int rij=0; rij<4; ++rij)
            {
                temp2(rij,kolom) = coords[rij][0] * temp(0,kolom) + coords[rij][1] * temp(1,kolom) + coords[rij][2] * temp(2,kolom) + coords[rij][3] * temp(3,kolom);
            }
        }
        return temp2;
    }

    string output()
    {
        return ("<table><tr><td rowspan =\"4\" style =\"font-size: 95px; padding:0px; font-family:Calibri;\">[</td><td>"
                           + stringvan<getal>(coords[0][0]) + "</td><td>" + stringvan<getal>(coords[0][1]) + "</td><td>" + stringvan<getal>(coords[0][2]) +  "</td><td>" + stringvan<getal>(coords[0][3]) + "</td><td rowspan =\"4\" style =\"  font-size: 95px; padding:0px; font-family:Calibri;\">]</td></tr>" +
                "<tr><td>" + stringvan<getal>(coords[1][0]) + "</td><td>" + stringvan<getal>(coords[1][1]) + "</td><td>" + stringvan<getal>(coords[1][2]) +  "</td><td>" + stringvan<getal>(coords[1][3]) + "</td></tr>" +
                "<tr><td>" + stringvan<getal>(coords[2][0]) + "</td><td>" + stringvan<getal>(coords[2][1]) + "</td><td>" + stringvan<getal>(coords[2][2]) +  "</td><td>" + stringvan<getal>(coords[2][3]) + "</td></tr>" +
                "<tr><td>" + stringvan<getal>(coords[3][0]) + "</td><td>" + stringvan<getal>(coords[3][1]) + "</td><td>" + stringvan<getal>(coords[3][2]) +  "</td><td>" + stringvan<getal>(coords[3][3]) + "</td></tr><table>");

    }

    vector3d<getal> getrotrij (unsigned char x)
    {
        return vector3d<getal>(coords[x][0], coords[x][1], coords[x][2]);
    }
    vector3d<getal> getrotkolom (unsigned char x)
    {
        return vector3d<getal>(coords[0][x], coords[1][x], coords[2][x]);
    }
    vector3d<getal> getverplaatsing ()
    {
        return vector3d<getal>(coords[0][3], coords[1][3], coords[2][3]);
    }
};

#endif

vector class:


#ifndef vector_bib
#define vector_bib
#include <string>
#include "basisbib.hpp"
#include "matrix.hpp"

using namespace std;

template <class getal>
class vector2d
{
    getal coords[2];

    public:

    inline vector2d()
    {
        coords[0] = 0;
        coords[1] = 0;
    }
    inline vector2d(getal x, getal y)
    {
        coords[0] = x;
        coords[1] = y;
    }
    inline vector2d(getal coordsbuff[2])
    {
        coords[0] = coordsbuff[0];
        coords[1] = coordsbuff[1];
    }

    inline getal* get()
    {
        return coords;
    }

    inline getal& operator [] (unsigned int temp)
    {
        return coords[temp];
    }
    inline getal x()
    {
        return coords[0];
    }
    inline getal y()
    {
        return coords[1];
    }

    inline vector2d operator + (vector2d temp)
    {
        vector2d temp2;
        temp2.coords[0] = coords[0] + temp.coords[0];
        temp2.coords[1] = coords[1] + temp.coords[1];
        return temp2;
    }
    inline vector2d operator - (vector2d temp)
    {
        vector2d temp2;
        temp2.coords[0] = coords[0] - temp.coords[0];
        temp2.coords[1] = coords[1] - temp.coords[1];
        return temp2;
    }
    inline vector2d operator * (vector2d temp)
    {
        vector2d temp2;
        temp2.coords[0] = coords[0] * temp.coords[0];
        temp2.coords[1] = coords[1] * temp.coords[1];
        return temp2;
    }
    inline vector2d operator / (vector2d temp)
    {
        vector2d temp2;
        temp2.coords[0] = coords[0] / temp.coords[0];
        temp2.coords[1] = coords[1] / temp.coords[1];
        return temp2;
    }

    inline vector2d operator = (vector2d temp)
    {
        coords[0] = temp.coords[0];
        coords[1] = temp.coords[1];
        return *this;
    }

    inline vector2d operator += (vector2d temp)
    {
        coords[0] += temp.coords[0];
        coords[1] += temp.coords[1];
        return *this;
    }
    inline vector2d operator -= (vector2d temp)
    {
        coords[0] -= temp.coords[0];
        coords[1] -= temp.coords[1];
        return *this;
    }
    inline vector2d operator *= (vector2d temp)
    {
        coords[0] *= temp.coords[0];
        coords[1] *= temp.coords[1];
        return *this;
    }
    inline vector2d operator /= (vector2d temp)
    {
        coords[0] /= temp.coords[0];
        coords[1] /= temp.coords[1];
        return *this;
    }

    inline vector2d operator * (getal temp)
    {
        vector2d temp2;
        temp2.coords[0] = coords[0] * temp;
        temp2.coords[1] = coords[1] * temp;
        return temp2;
    }
    inline vector2d operator / (getal temp)
    {
        vector2d temp2;
        temp2.coords[0] = coords[0] / temp;
        temp2.coords[1] = coords[1] / temp;
        return temp2;
    }
    inline vector2d operator *= (getal temp)
    {
        coords[0] *= temp;
        coords[1] *= temp;
        return *this;
    }
    inline vector2d operator /= (getal temp)
    {
        coords[0] /= temp;
        coords[1] /= temp;
        return *this;
    }

    inline bool operator == (vector2d temp)
    {
        return (coords[0] == temp.coords[0] && coords[1] == temp.coords[1]);
    }
    inline bool operator != (vector2d temp)
    {
        return !(coords[0] == temp.coords[0] && coords[1] == temp.coords[1]);
    }
    inline bool operator < (vector2d temp)
    {
        return (coords[0] < temp.coords[0] && coords[1] < temp.coords[1]);
    }
    inline bool operator > (vector2d temp)
    {
        return (coords[0] > temp.coords[0] && coords[1] > temp.coords[1]);
    }
    inline bool operator <= (vector2d temp)
    {
        return (coords[0] <= temp.coords[0] && coords[1] <= temp.coords[1]);
    }
    inline bool operator >= (vector2d temp)
    {
        return (coords[0] >= temp.coords[0] && coords[1] >= temp.coords[1]);
    }

    inline void set(getal x, getal y)
    {
        coords[0] = x;
        coords[1] = y;
    }
    inline void set(getal coordsbuff[2])
    {
        coords[0] = coordsbuff[0];
        coords[1] = coordsbuff[1];
    }
    inline void set(vector2d temp)
    {
        *this = temp;
    }

    inline void operator () (getal x, getal y)
    {
        coords[0] = x;
        coords[1] = y;
    }
    inline void operator () (getal coordsbuff[2])
    {
        coords[0] = coordsbuff[0];
        coords[1] = coordsbuff[1];
    }
    inline void operator () (vector2d temp)
    {
        *this = temp;
    }
};

template <class getal>
class vector3d
{
    getal coords[3];

    public:

    inline vector3d()
    {
        coords[0] = 0;
        coords[1] = 0;
        coords[2] = 0;
    }
    inline vector3d(getal x, getal y, getal z)
    {
        coords[0] = x;
        coords[1] = y;
        coords[2] = z;
    }
    inline vector3d(getal coordsbuff[3])
    {
        coords[0] = coordsbuff[0];
        coords[1] = coordsbuff[1];
        coords[2] = coordsbuff[2];
    }

    inline getal* get()
    {
        return coords;
    }

    inline getal& operator [] (unsigned int temp)
    {
        return coords[temp];
    }

    inline getal x()
    {
        return coords[0];
    }
    inline getal y()
    {
        return coords[1];
    }
    inline getal z()
    {
        return coords[2];
    }

    inline vector3d operator + (vector3d temp)
    {
        vector3d temp2;
        temp2.coords[0] = coords[0] + temp.coords[0];
        temp2.coords[1] = coords[1] + temp.coords[1];
        temp2.coords[2] = coords[2] + temp.coords[2];
        return temp2;
    }
    inline vector3d operator - (vector3d temp)
    {
        vector3d temp2;
        temp2.coords[0] = coords[0] - temp.coords[0];
        temp2.coords[1] = coords[1] - temp.coords[1];
        temp2.coords[2] = coords[2] - temp.coords[2];
        return temp2;
    }
    inline vector3d operator * (vector3d temp)
    {
        vector3d temp2;
        temp2.coords[0] = coords[0] * temp.coords[0];
        temp2.coords[1] = coords[1] * temp.coords[1];
        temp2.coords[2] = coords[2] * temp.coords[2];
        return temp2;
    }
    inline vector3d operator / (vector3d temp)
    {
        vector3d temp2;
        temp2.coords[0] = coords[0] / temp.coords[0];
        temp2.coords[1] = coords[1] / temp.coords[1];
        temp2.coords[2] = coords[2] / temp.coords[2];
        return temp2;
    }

    inline vector3d operator = (vector3d temp)
    {
        coords[0] = temp.coords[0];
        coords[1] = temp.coords[1];
        coords[2] = temp.coords[2];
        return *this;
    }

    inline vector3d operator += (vector3d temp)
    {
        coords[0] += temp.coords[0];
        coords[1] += temp.coords[1];
        coords[2] += temp.coords[2];
        return *this;
    }
    inline vector3d operator -= (vector3d temp)
    {
        coords[0] -= temp.coords[0];
        coords[1] -= temp.coords[1];
        coords[2] -= temp.coords[2];
        return *this;
    }
    inline vector3d operator *= (vector3d temp)
    {
        coords[0] *= temp.coords[0];
        coords[1] *= temp.coords[1];
        coords[2] *= temp.coords[2];
        return *this;
    }
    inline vector3d operator /= (vector3d temp)
    {
        coords[0] /= temp.coords[0];
        coords[1] /= temp.coords[1];
        coords[2] /= temp.coords[2];
        return *this;
    }

    inline vector3d operator * (getal temp)
    {
        vector3d temp2;
        temp2.coords[0] = coords[0] * temp;
        temp2.coords[1] = coords[1] * temp;
        temp2.coords[2] = coords[2] * temp;
        return temp2;
    }
    inline vector3d operator / (getal temp)
    {
        vector3d temp2;
        temp2.coords[0] = coords[0] / temp;
        temp2.coords[1] = coords[1] / temp;
        temp2.coords[2] = coords[2] / temp;
        return temp2;
    }
    inline vector3d operator *= (getal temp)
    {
        coords[0] *= temp;
        coords[1] *= temp;
        coords[2] *= temp;
        return *this;
    }
    inline vector3d operator /= (getal temp)
    {
        coords[0] /= temp;
        coords[1] /= temp;
        coords[2] /= temp;
        return *this;
    }

    inline bool operator == (vector3d temp)
    {
        return (coords[0] == temp.coords[0] && coords[1] == temp.coords[1] && coords[2] == temp.coords[2]);
    }
    inline bool operator != (vector3d temp)
    {
        return !(coords[0] == temp.coords[0] && coords[1] == temp.coords[1] && coords[2] == temp.coords[2]);
    }
    inline bool operator < (vector3d temp)
    {
        return (coords[0] < temp.coords[0] && coords[1] < temp.coords[1] && coords[2] < temp.coords[2]);
    }
    inline bool operator > (vector3d temp)
    {
        return (coords[0] > temp.coords[0] && coords[1] > temp.coords[1] && coords[2] > temp.coords[2]);
    }
    inline bool operator <= (vector3d temp)
    {
        return (coords[0] <= temp.coords[0] && coords[1] <= temp.coords[1] && coords[2] <= temp.coords[2]);
    }
    inline bool operator >= (vector3d temp)
    {
        return (coords[0] >= temp.coords[0] && coords[1] >= temp.coords[1] && coords[2] >= temp.coords[2]);
    }

    inline void set (getal x, getal y, getal z)
    {
        coords[0] = x;
        coords[1] = y;
        coords[2] = z;
    }
    inline void set (getal coordsbuff[3])
    {
        coords[0] = coordsbuff[0];
        coords[1] = coordsbuff[1];
        coords[2] = coordsbuff[2];
    }
    inline void set (vector3d temp)
    {
        *this = temp;
    }

    inline void operator () (getal x, getal y, getal z)
    {
        coords[0] = x;
        coords[1] = y;
        coords[2] = z;
    }
    inline void operator () (getal coordsbuff[3])
    {
        coords[0] = coordsbuff[0];
        coords[1] = coordsbuff[1];
        coords[2] = coordsbuff[2];
    }
    inline void operator () (vector3d temp)
    {
        *this = temp;
    }

    inline vector3d operator - ()
    {
        return vector3d(-coords[0], -coords[1], -coords[2]);
    }

    inline vector3d abs()
    {
        return vector3d((coords[0]>0) ? coords[0] : -coords[0], (coords[1]>0) ? coords[1] : -coords[1], (coords[2]>0) ? coords[2] : -coords[2]);
    }

    inline vector3d unitvector ()
    {
        getal lengte = sqrt(double(coords[0]*coords[0]+coords[1]*coords[1]+coords[2]*coords[2]));
        return *this/lengte;
    }

    inline getal lengte()
    {
        return getal(sqrt(double(coords[0]*coords[0] + coords[1]*coords[1] + coords[2]*coords[2])));
    }

    inline string output ()
    {
        return "(" + stringvan<getal>(coords[0]) + " | " + stringvan<getal>(coords[1]) + " | " + stringvan<getal>(coords[2]) + ")";
    }

    inline getal laagste ()
    {
        return (((coords[0]<coords[1]) ? coords[0] : coords[1])<coords[2]) ? ((coords[0]<coords[1]) ? coords[0] : coords[1]) : coords[2];
    }
    inline getal hoogste ()
    {
        return (((coords[0]>coords[1]) ? coords[0] : coords[1])>coords[2]) ? ((coords[0]>coords[1]) ? coords[0] : coords[1]) : coords[2];
    }

    inline vector3d getas (unsigned int temp)
    {
        vector3d<getal> temp2(0,0,0);
        temp2[temp] = coords[temp];
        return temp2;
    }

    inline vector3d roteer(vector3d rot)
    {
        vector3d temp2(coords);
        if (rot[0] != 0)
        {
            temp2(temp2.x(), temp2[1]*gcos(rot[0]) - temp2[2]*gsin(rot[0]), temp2[1]*gsin(rot[0]) + temp2[2]*gcos(rot[0]));
        }
        if (rot[1] != 0)
        {
            temp2(temp2[2]*gsin(rot[1]) + temp2[0]*gcos(rot[1]), temp2.y(), temp2[2]*gcos(rot[1]) - temp2[0]*gsin(rot[1]));
        }
        if (rot[2] != 0)
        {
            temp2(temp2[0]*gcos(rot[2]) - temp2[1]*gsin(rot[2]), temp2[0]*gsin(rot[2]) + temp2[1]*gcos(rot[2]), temp2.z());
        }
        return temp2;
    }

    inline vector3d roteer(matrix44<getal> buffmat)
    {
        vector3d buffvec;
        buffvec[0] = coords[0] * buffmat(0,0) + coords[1] * buffmat(0,1) + coords[2] * buffmat(0,2);

        buffvec[1] = coords[0] * buffmat(1,0) + coords[1] * buffmat(1,1) + coords[2] * buffmat(1,2);

        buffvec[2] = coords[0] * buffmat(2,0) + coords[1] * buffmat(2,1) + coords[2] * buffmat(2,2);
        return (buffvec);
    }

    inline vector3d transform(matrix44<getal> buffmat)
    {
        vector3d buffvec;
        buffvec[0] = coords[0] * buffmat(0,0) + coords[1] * buffmat(0,1) + coords[2] * buffmat(0,2) + buffmat(0,3);

        buffvec[1] = coords[0] * buffmat(1,0) + coords[1] * buffmat(1,1) + coords[2] * buffmat(1,2) + buffmat(1,3);

        buffvec[2] = coords[0] * buffmat(2,0) + coords[1] * buffmat(2,1) + coords[2] * buffmat(2,2) + buffmat(2,3);
        return (buffvec);
    }

    inline matrix44<getal> getrotmatrix()
    {
        return matrix44<getal>
        (
            1, 0, 0, 0,
            0, gcos(coords[0]), -gsin(coords[0]), 0,
            0, gsin(coords[0]),  gcos(coords[0]), 0,
            0, 0, 0, 1
        ) * matrix44<getal>
        (
            gcos(coords[1]),  0, gsin(coords[1]), 0,
            0, 1, 0, 0,
            -gsin(coords[1]), 0, gcos(coords[1]), 0,
            0, 0, 0, 1
        ) * matrix44<getal>
        (
            gcos(coords[2]),  -gsin(coords[2]), 0, 0,
            gsin(coords[2]),   gcos(coords[2]), 0, 0,
            0, 0, 1, 0,
            0, 0, 0, 1
        );
    }

    inline matrix44<getal> getterugrotmatrix()
    {
        return matrix44<getal>
        (
            gcos(-coords[2]), -gsin(-coords[2]), 0, 0,
            gsin(-coords[2]),  gcos(-coords[2]), 0, 0,
            0, 0, 1, 0,
            0, 0, 0, 1
        ) * matrix44<getal>
        (
            gcos(-coords[1]),  0, gsin(-coords[1]), 0,
            0,                 1, 0,                0,
            -gsin(-coords[1]), 0, gcos(-coords[1]), 0,
            0, 0, 0, 1
        ) * matrix44<getal>
        (
            1, 0, 0, 0,
            0, gcos(-coords[0]), -gsin(-coords[0]), 0,
            0, gsin(-coords[0]),  gcos(-coords[0]), 0,
            0, 0, 0, 1
        );
    }

    inline matrix44<getal> gettransmatrix()
    {
        return matrix44<getal>
        (
            1, 0, 0, coords[0],
            0, 1, 0, coords[1],
            0, 0, 1, coords[2],
            0, 0, 0, 1
        );
    }

    inline matrix44<getal> getschlmatrix()
    {
        return matrix44<getal>
        (
            coords[0], 0, 0, 0,
            0, coords[1], 0, 0,
            0, 0, coords[2], 0,
            0, 0, 0, 1
        );
    }
};

template <class getal>
getal scalairproduct(vector2d<getal> v1, vector2d<getal> v2)
{
    return v1[0] * v2[0] + v1[1] * v2[1];
}

template <class getal>
getal scalairproduct(vector3d<getal> v1, vector3d<getal> v2)
{
    return v1[0] * v2[0] + v1[1] * v2[1] + v1[2] * v2[2];
}

template <class getal>
vector3d<getal> kruisproduct(vector3d<getal> v1, vector3d<getal> v2)
{
    return vector3d<getal> (v1[1]*v2[2]-v1[2]*v2[1], v1[2]*v2[0]-v1[0]*v2[2], v1[0]*v2[1]-v1[1]*v2[0]);
}

#endif

[Edited by - d1rk on November 7, 2009 10:58:16 AM]

Litheon

Oct 22, 2009 at 2:17 PM

ha, nog niemand heeft gereageerd.

Oliii has a nice document + demo about OBB vs OBB collision, link check out the "Cube collisions + exact contact point calculation" for 3D and there are some other downloads where 2D SAT is explained in detail + source code.

Sorry, don't have the time at the moment to check your code.

oliii

Oct 23, 2009 at 3:02 AM

in 3D, the cross axes are important. If your boxes are basically flat on a plane, then they are not.

here is an example.

TBH, for the SAT with oriented boxes, you don't need that transform malarkey. If you have problems with your SAT, it could be where you are not getting the expected results. It's a bit too early to sift through the code.

In the code, the

Vector m_orientation[3]

is basically similar to a 3x3 transform matrix, or rotation matrix. The axes of the box will be either the columns or the rows of your transform matrix.

Debugging this can be a step by step process. Check if the values make sense for a number of unit tests. Start with boxes as if they were in 2D, so that the lack of cross axis-tests don't affect the results.

d1rk

Oct 24, 2009 at 4:14 AM

I've rewritten most of my code and it has slightly better results now. It also tests on the cross-product axes.

It handles boxes that move only over the x and y axis and that are only rotated around the z axis fine. It doesn't work with boxes that are rotated and/or moved in other ways.

You can see it for yourself in the demo. (paste the .exe in the folder of the demo of the starpost)

[source lang=cpp]bool testoverlap(bbox box1, vector3d<double> pos1, matrix44<double> mat1, bbox box2, vector3d<double> pos2, matrix44<double> mat2, vector3d<double> axis){    // rotate the axis into object-space    vector3d<double> rotaxis1 = axis.transform(mat1);    double    //project the middle point onto the axis    mid1 = dotproduct(pos1, axis) + dotproduct(box1.pos, rotas1),    //project the biggest distance from the middle-point onto the axis    distance1 = dotproduct(box1.max, rotas1.abs()),    //min1 is the projection of the middle point minus the biggest distance    min1 = mid1 - distance1,    //max1 is the projection of the middle point plus the biggest distance    max1 = mid1 + distance1;    //do the same with the second box    vector3d<double> rotaxis2 = axis.transform(mat2);    double    mid2 = dotproduct(pos2, axis) + dotproduct(box2.pos, rotaxis2),    distance2 = dotproduct(box2.max, rotaxis2.abs()),    min2 = mid2 - distance2,    max2 = mid2 + distance2;    // if there is no overlap    if (max1 < min2 || max2 < min1)    {        return false;    }    return true;}bool physics::boxboxtest(bbox box1, objectins* obj1, bbox box2, objectinst obj2){    //calculate the matrices to rotate to an object and to rotate back from it    matrix44<double> mat1 = obj1.rot.getrotmatrix();    matrix44<double> mat2 = obj2.rot.getrotmatrix();    matrix44<double> mat1terug = obj1.rot.getterugrotmatrix();    matrix44<double> mat2terug = obj2.rot.getterugrotmatrix();    // calculate the axes (assen in dutch) of the boxes    // getas returns the x, y or z axis as vector    // so vector<double>(1, 2, 3).getas(1) would be (0, 2, 0)    // then those axis are rotated into world-space    vector3d<double> assen1[3] =    {        box1.max.getas(0).transform(mat1terug),        box1.max.getas(1).transform(mat1terug),        box1.max.getas(2).transform(mat1terug)    }, assen2[3] =    {        box2.max.getas(0).transform(mat2terug),        box2.max.getas(1).transform(mat2terug),        box2.max.getas(2).transform(mat2terug)    };    for (short loop=0; loop<3; ++loop)    {        // check for overlap on the axes of the first box        if(!testoverlap(box1, obj1.pos, mat1, box2, obj2.pos, mat2, assen1[loop]))        {            return false;        }        // check for overlap on the axes of the second box        if(!testoverlap(box1, obj1.pos, mat1, box2, obj2.pos, mat2, assen2[loop]))        {            return false;        }        // check for overlap on the cross-product(kruisproduct) axes        for (short loop2=0; loop2<3; ++loop2)        {            if(!testoverlap(box1, obj1.pos, mat1, box2, obj2.pos, mat2, kruisproduct(assen1[loop], assen2[loop2])))            {                return false;            }        }    }    //if there was no axis where there was no overlap then the boxes are colliding.    return true;}

oliii

Oct 24, 2009 at 5:49 AM

 distance1 = dotproduct(box1.max, rotas1.abs()),    //min1 is the projection of the middle point minus the biggest distance    min1 = mid1 - distance1,    //max1 is the projection of the middle point plus the biggest distance    max1 = mid1 + distance1;

This looks wrong to me.

 vector3d<double> assen1[3] =    {        box1.max.getas(0).transform(mat1terug),        box1.max.getas(1).transform(mat1terug),        box1.max.getas(2).transform(mat1terug)    };    vector3d<double> extent1((box1.max - box1.min) * 0.5);       distance1 = fabs(dotproduct(assen1[0], rotas1) * extent1.x) +                fabs(dotproduct(assen1[1], rotas1) * extent1.y) +                fabs(dotproduct(assen1[2], rotas1) * extent1.z);vector3d<double> assen2[3] =    {        box2.max.getas(0).transform(mat2terug),        box2.max.getas(1).transform(mat2terug),        box2.max.getas(2).transform(mat2terug)    };    vector3d<double> extent2((box2.max - box2.min) * 0.5);    distance2 = fabs(dotproduct(assen2[0], rotas2) * extent2.x) +                fabs(dotproduct(assen2[1], rotas2) * extent2.y) +                fabs(dotproduct(assen2[2], rotas2) * extent2.z);

All this transform stuff is doing my head in tbh! Anything could go wrong there.

d1rk

Oct 26, 2009 at 11:10 AM

I rewrote my code again, because I wanted to split it up into several functions and I wanted to get rid of most transforms. But it still isn't working.

//this function calculates the min and max values of a box projected on the x, y, or z axis in object spaceinline void projownaxis (bbox box, unsigned char axis, double& min, double& max){    min = box.pos[axis] - box.max[axis];    max = box.pos[axis] + box.max[axis];}//this function calculates the min and max values of a box projected on an axisinline void projaxis (bbox box, vector3d<double> axis, double& min, double& max){    double    mid = dotproduct(box.pos, axis),    afstand = dotproduct(box.max, axis.abs());    min = mid - afstand;    max = mid + afstand;}//this function tests if two boxes overlap on one of the axes of the first boxbool testownaxis(bbox box1, matrix44<double> terugmat1, bbox box2, matrix44<double> mat2, vector3d<double> posverschil, unsigned char axis){    //puts one of the columns of the matrix in the vector    //rotaxis is the x, y or z axis of the first box rotated into world-space    vector3d<double> rotaxis = terugmat1.getrotkolom(axis);    //verschil is the distance between box1 and box2    double min1, min2, max1, max2, verschil = dotproduct(posverschil, rotaxis );    //calculates box1's min and max values (on his own axis)    projeigenas(box1, axis, min1, max1);    //rotates the axis(wich was in world space) into box2's object space    rotaxis = rotaxis.transform(mat2);    //calculates box1's min and max values    projas(box2, rotaxis, min2, max2);    // if there is no overlap return false, else rturn true    if (max1 < min2+verschil || max2+verschil < min1)    {        return false;    }    return true;}bool testaxis(bbox box1, matrix44<double> mat1, bbox box2, matrix44<double> mat2, vector3d<double> posverschil, vector3d<double> axis){    //verschil is the distance between box1 and box2    double min1, min2, max1, max2, verschil = dotproduct(posverschil, axis);    //rotates the axis into box1's object space    vector3d<double> rotaxis = axis.transform(mat1);    projas(box1, rotaxis, min1, max1);    //rotates the axis into box2's object space    rotaxis = axis.transform(mat2);    projas(box2, rotaxis, min2, max2);    // if there is no overlap return false, else rturn true    if (max1 < min2+verschil || max2+verschil < min1)    {        return false;    }    return true;}bool physics::boxboxtest(bbox box1, objectinst obj1, bbox box2, objectinst obj2){    //calculates the matrix for rotating something from world-space into the object space of object 1    matrix44<double> mat1 = obj1.rot.getrotmatrix();    //calculates the matrix for rotating something from world-space into the object space of object 2    matrix44<double> mat2 = obj2.rot.getrotmatrix();    //calculates the matrix for rotating something from the object space of object 1 into world-space    matrix44<double> terugmat1 = obj1.rot.getterugrotmatrix();    //calculates the matrix for rotating something from the object space of object 2 into world-space    matrix44<double> terugmat2 = obj2.rot.getterugrotmatrix();    for (unsigned char loop=0; loop<3; ++loop)    {        //tests on the axes of the first box        if(!testownaxis(box1, terugmat1, box2, mat2, obj2.pos - obj1.pos, loop))        {            return false;        }        //tests on the axes of the second box        if(!testownaxis(box2, terugmat2, box1, mat1, obj1.pos - obj2.pos, loop))        {            return false;        }        //tests on the cross-axes        for (short loop2=0; loop2<3; ++loop2)        {            if(!testaxis(box1, mat1, box2, mat2, obj2.pos - obj1.pos,               // calculates the cross product of the columns of the matrices to rotate from object space to world space               kruisproduct(terugmat1.getrotkolom(loop), terugmat2.getrotkolom(loop2)               )))            {                return false;            }        }    }    return true;}

And again i've included a .exe

[Edited by - d1rk on October 26, 2009 11:10:41 AM]

oliii

Oct 26, 2009 at 7:32 PM

Quote:

//this function calculates the min and max values of a box projected on an axisinline void projaxis (bbox box, vector3d<double> axis, double& min, double& max){    double    mid = dotproduct(box.pos, axis),    afstand = dotproduct(box.max, axis.abs());    min = mid - afstand;    max = mid + afstand;}

This is definitely wrong. The projected 'extent' of the box is not box.max dot product axis.abs().

Quote:

//this function calculates the min and max values of a box projected on the x, y, or z axis in object spaceinline void projownaxis (bbox box, unsigned char axis, double& min, double& max){    min = box.pos[axis] - box.max[axis];    max = box.pos[axis] + box.max[axis];}

What is max exactly? Is that the halfsize of the box?

then try that, maybe...

Quote:

//this function calculates the min and max values of a box projected on an axisinline void projaxis (bbox box, matrix44<double> terugmat1, vector3d<double> axis, double& min, double& max){    vector3d<double> ax = terugmat1.getrotkolom(0);    vector3d<double> ay = terugmat1.getrotkolom(1);    vector3d<double> az = terugmat1.getrotkolom(2);    double afstandx = box.max.x * abs(dotproduct(ax, axis));    double afstandy = box.max.y * abs(dotproduct(ay, axis));    double afstandz = box.max.z * abs(dotproduct(az, axis));    double afstand = afstandx + afstandy + afstandz;    double mid = dotproduct(box.pos, axis);    min = mid - afstand;    max = mid + afstand;}

d1rk

Nov 3, 2009 at 1:57 PM

Max is indeed the halfsize. Now I have nearly the same code as you posted and it still isn't working.

void projaxis (bbox box, matrix44<double> mat, vector3d<double> axis, double& min, double& max){    double afstandx = box.max[0] * fabs(dotproduct(mat.getrotkolom(0), axis));    double afstandy = box.max[1] * fabs(dotproduct(mat.getrotkolom(1), axis));    double afstandz = box.max[2] * fabs(dotproduct(mat.getrotkolom(2), axis));    double afstand = afstandx + afstandy + afstandz;    double midx = box.pos[0] * dotproduct(mat.getrotkolom(0), axis);    double midy = box.pos[1] * dotproduct(mat.getrotkolom(1), axis);    double midz = box.pos[2] * dotproduct(mat.getrotkolom(2), axis);    double mid = midx + midy + midz;    min = mid - afstand;    max = mid + afstand;}bool testaxis(bbox box1, matrix44<double> mat1, bbox box2, matrix44<double> mat2, vector3d<double> posverschil, vector3d<double> axis){    double min1, min2, max1, max2, verschil = dotproduct(posverschil, axis);    projas(box1, mat1, axis, min1, max1);    projas(box2, mat2, axis, min2, max2);    if (max1 < min2+verschil || max2+verschil < min1)    {        return false;    }    return true;}bool physics::boxboxtest(bbox box1, objectinst obj1, bbox box2, objectinst obj2){    //calculates the matrix for rotating something from the object space of object 1 into world-space    matrix44<double> terugmat1 = obj1.rot.getterugrotmatrix();    //calculates the matrix for rotating something from the object space of object 2 into world-space    matrix44<double> terugmat2 = obj2.rot.getterugrotmatrix();    for (unsigned char loop=0; loop<3; ++loop)    {        if(!testaxis(box1, terugmat1, box2, terugmat2, obj2.pos - obj1.pos, terugmat1.getrotkolom(loop)))        {            return false;        }        if(!testaxis(box1, terugmat1, box2, terugmat2, obj2.pos - obj1.pos, terugmat2.getrotkolom(loop)))        {            return false;        }        for (short loop2=0; loop2<3; ++loop2)        {            if(!testaxis(box1, terugmat1, box2, terugmat2, obj2.pos - obj1.pos, crossproduct(terugmat1.getrotkolom(loop), terugmat2.getrotkolom(loop2))))            {                return false;            }        }    }    return true;}

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.