Jump to content

  • Log In with Google      Sign In   
  • Create Account

We need your help!

We need 7 developers from Canada and 18 more from Australia to help us complete a research survey.

Support our site by taking a quick sponsored survey and win a chance at a $50 Amazon gift card. Click here to get started!


Irlan Robson

Member Since 08 May 2012
Offline Last Active Today, 06:52 AM

Posts I've Made

In Topic: Problem Implementing Separating Axis Theorem

20 August 2015 - 08:01 AM

d07RiV is correct.

 

I would instead keep a 3x3 rotation matrix inside the transform class and rotate the normals using it. This is much more faster and you don't need to normalize the normals (in both ways).

 

Test a box-box collision since it is easy to inspect the face and edge normals.


In Topic: Problem Implementing Separating Axis Theorem

20 August 2015 - 06:52 AM

Test all your collision routines separately for only two objects. This is much more transparently.

 

 

 


// Check if they overlap
if(projection1.max < projection2.min || projection2.max < projection1.min) {
return false;
}

 

This look suspecious. If the projection does overlap then you should keep looking for some other axis.

 

You should look for a separating axis coming for the first and the second shape normals, and not only the first.

 

I encourage you to run the code I've posted first in order to make sure your math and your normals are correct. 

 

Example:

        // Check if there is a separating axis coming from the first hull axes.
        if ( !TestFaces(_psiShape0, _psiShape1) ) {
                // Axis found, exit no collision.
                return false;
        }
        // Check if there is a separating axis coming from the second hull axes.
        if ( !TestFaces( _psiShape1, _psiShape0 ) ) {
                // Axis found, exit no collision.
                return false;
        }
        // Check if there is a separating axis coming from the cross products of the edge normals.
        if ( !TestEdges( _psiShape0, _psiShape1 ) ) {
                // Axis found, exit no collision.
                return false;
        }
        // No axis found, exit with collision.
        return true;

In Topic: Problem Implementing Separating Axis Theorem

19 August 2015 - 02:33 PM

This is an old  brute-force SAT:

struct PROJECTION {
                float fMin;
                float fMax;
                bool Overlap(const PROJECTION& _pOther) const {
                        return !(fMax < _pOther.fMin || _pOther.fMax < fMin);
                }
};
 
bool CSat::TestFaces(const CShapeInstance* _psiShape0, const CShapeInstance* _psiShape1) const {
        const CConvexPolyhedron* pcpConvex0 = static_cast<const CConvexPolyhedron*>(_psiShape0->m_psShape);
        const CConvexPolyhedron* pcpConvex1 = static_cast<const CConvexPolyhedron*>(_psiShape1->m_psShape);
 
        for (unsigned int I = 0; I < pcpConvex0->m_ui32TotalFaces; ++I) {
                CVector3 vAxis = _psiShape0->m_mTransform.Rotation() * pcpConvex0->m_pvFaces[I];
 
                PROJECTION pProj0;
                PROJECTION pProj1;
                Project(pcpConvex0, _psiShape0->m_mTransform, vAxis, pProj0);
                Project(pcpConvex1, _psiShape1->m_mTransform, vAxis, pProj1);
 
                if (!pProj0.Overlap(pProj1)) {
                        return false;
                }
        }
 
        return true;
}
 
void CSat::Project(const CConvexPolyhedron* _pcpHull, const CMatrix4x4& _mTransform, const CVector3& _vAxis, PROJECTION& _pProj) const {
        _pProj.fMin = _pProj.fMax = _vAxis.Dot(_mTransform * _pcpHull->m_pvVerts[0]);
        for (unsigned int I = 1; I < _pcpHull->m_ui32TotalVerts; ++I) {
                float fProj = _vAxis.Dot(_mTransform * _pcpHull->m_pvVerts[I]);
                if (fProj < _pProj.fMin) {
                        _pProj.fMin = fProj;
                }
                if (fProj > _pProj.fMax) {
                        _pProj.fMax = fProj;
                }
        }
}
 
bool CSat::TestEdges(const CShapeInstance* _psiShape0, const CShapeInstance* _psiShape1) const {
        const CConvexPolyhedron* pcpConvex0 = static_cast<const CConvexPolyhedron*>(_psiShape0->m_psShape);
        const CConvexPolyhedron* pcpConvex1 = static_cast<const CConvexPolyhedron*>(_psiShape1->m_psShape);
 
        for (unsigned int I = 0; I < pcpConvex0->m_ui32TotalEdges; ++I) {
                CVector3 vAxis0 = _psiShape0->m_mTransform.Rotation() * pcpConvex0->m_pvEdges[I].vNormal;
 
                for (unsigned int J = 0; J < pcpConvex1->m_ui32TotalEdges; ++J) {
                        CVector3 vAxis1 = _psiShape1->m_mTransform.Rotation() * pcpConvex1->m_pvEdges[J].vNormal;
 
                        CVector3 vAxis = vAxis0.Cross(vAxis1);
 
                        PROJECTION pProj0;
                        PROJECTION pProj1;
                        Project(pcpConvex0, _psiShape0->m_mTransform, vAxis, pProj0);
                        Project(pcpConvex1, _psiShape1->m_mTransform, vAxis, pProj1);
 
                        if (!pProj0.Overlap(pProj1)) {
                                return false;
                        }
                }
        }
 
        return true;
}
 
bool CSat::Intersect(const CShapeInstance* _psiShape0, const CShapeInstance* _psiShape1) {
       if ( !TestFaces(_psiShape0, _psiShape1) ) {
                return false;
        }
        if ( !TestFaces( _psiShape1, _psiShape0 ) ) {
                return false;
        }
        if ( !TestEdges( _psiShape0, _psiShape1 ) ) {
                return false;
        }
        return true;
}

This thread discusses different issues with SAT as well optimizations in order to put in production:

 

http://www.gamedev.net/topic/667499-3d-sat-problem/


In Topic: Box stacking

10 August 2015 - 02:24 PM

d07RiV, seeing your demo considering the boxes density it looks correct to me (at least visually).


In Topic: Box stacking

07 August 2015 - 08:11 PM

(Without encouraging you to copy code) here's a quick thing to do: compare your code against any of the following engines:

 

https://github.com/irlanrobson/Bounce

https://github.com/RandyGaul/qu3e/

 

These libraries (as said by the authors) were inspired by Box2D.

 

See b3ContactGraph.cpp line 175 for the contact caching part. Using your idea you switch from

 

if (p1->id.key == p2->id.key) ...

 

to

 

if ( LenghSquared(p1->position - p2->position) < tolerance ) ...


PARTNERS