5
\$\begingroup\$

I'm trying to code some intersection codes for Oriented Bounding Boxes (OBBs) and axis-aligned bounding boxes (AABBs). I have the OBB-OBB intersection using the Separating Axis Theorem (SAT) and I'm trying to figure out how can I improve this code to the specific case where I know I'm comparing an OBB with an AABB.

This is the code of my function:

bool Collider::isColliding(OBB * one, OBB * other)
{
    TestManager::collisionTests++;
    glm::vec3 oneCenter = one->m_gameObject->getWorldPosition(); // object's pos = collider center
    glm::mat4 oneTransform = glm::scale(one->m_gameObject->getTransform(), one->m_halfSize); // scaling for halfsize
    glm::vec3 otherCenter = other->m_gameObject->getWorldPosition();
    glm::mat4 otherTransform = glm::scale(other->m_gameObject->getTransform(), other->m_halfSize);

    for (int a = 0; a < 3; a++) {
        glm::vec3 l = glm::vec3(oneTransform[a]); // one axis to project on
        float tl = std::abs(glm::dot(l, otherCenter) - glm::dot(l, oneCenter)); // center distance
        float ra = std::abs(glm::dot(l, glm::vec3(oneTransform[0]))) + std::abs(glm::dot(l, glm::vec3(oneTransform[1]))) + std::abs(glm::dot(l, glm::vec3(oneTransform[2])));
        float rb = std::abs(glm::dot(l, glm::vec3(otherTransform[0]))) + std::abs(glm::dot(l, glm::vec3(otherTransform[1]))) + std::abs(glm::dot(l, glm::vec3(otherTransform[2])));
        float penetration = (ra + rb) - tl;
        if (penetration <= 0) { // no overlap
            return false;
        }
    }
    for (int b = 0; b < 3; b++) {
        glm::vec3 l = glm::vec3(otherTransform[b]); // other axis to project on
        float tl = std::abs(glm::dot(l, otherCenter) - glm::dot(l, oneCenter)); // center distance
        float ra = std::abs(glm::dot(l, glm::vec3(oneTransform[0]))) + std::abs(glm::dot(l, glm::vec3(oneTransform[1]))) + std::abs(glm::dot(l, glm::vec3(oneTransform[2])));
        float rb = std::abs(glm::dot(l, glm::vec3(otherTransform[0]))) + std::abs(glm::dot(l, glm::vec3(otherTransform[1]))) + std::abs(glm::dot(l, glm::vec3(otherTransform[2])));
        float penetration = (ra + rb) - tl;
        if (penetration <= 0) { // no overlap
            return false;
        }
    }
    for (int a = 0; a < 3; a++) {
        glm::vec3 aAxis = glm::vec3(oneTransform[a]);
        for (int b = 0; b < 3; b++) {
            glm::vec3 bAxis = glm::vec3(otherTransform[b]);
            if (aAxis != bAxis) {
                glm::vec3 l = glm::cross(aAxis, bAxis); // has flaw when axis are same, result in (0,0,0), solved by if
                float tl = std::abs(glm::dot(l, otherCenter) - glm::dot(l, oneCenter)); // center distance
                float ra = std::abs(glm::dot(l, glm::vec3(oneTransform[0]))) + std::abs(glm::dot(l, glm::vec3(oneTransform[1]))) + std::abs(glm::dot(l, glm::vec3(oneTransform[2])));
                float rb = std::abs(glm::dot(l, glm::vec3(otherTransform[0]))) + std::abs(glm::dot(l, glm::vec3(otherTransform[1]))) + std::abs(glm::dot(l, glm::vec3(otherTransform[2])));
                float penetration = (ra + rb) - tl;
                if (penetration <= 0) { // no overlap
                    return false;
                }
            }
        }
    }
    return true;
}

Hope you can help me.

\$\endgroup\$
4
\$\begingroup\$

Broad Phase collision detection

It looks like you are using this for what is called broad phase collision detection. This is the step in collision detection that is used to determine candidate pairs for the narrow phase that does the actual collision detection (Quick Summary)

As this is a bounding box text (especially if you are involving AABB) it looks like you're just trying to see whether to go through the actual intersection routing of the two shapes or not. If you can just stick with AABB in general, the math gets a lot easier and therefore faster. Also moving forward you can employ AABB-trees (they are space partinioning trees) to find all intersection candidates for one object with a tree query rather than a pairwise check.

\$\endgroup\$
  • \$\begingroup\$ Yes, I have the AABB-AABB intersection code. The point is that I have to do also the OBB case (not my decision :( ) and I know that in some way Is possible to adjust the OBB-OBB case to make it fit to the AABB-OBB case saving some operations but I can not figure out what I have to change. \$\endgroup\$ – Carlos Hdez Barbera Apr 24 '18 at 9:59
  • \$\begingroup\$ At the end both ABB and OBB are just boxes, i'd convert one into the other and then run the appropriate code. Without knowing which of your objects here is in what coordinate system it's hard to give a better answer. I don't know if there is a faster algorithm that can do ABB-OBB intersections. You could convert from your ABB representation into your OBB representation and do the OBB-OBB test. Otherwise just build an ABB around your OBB and run the ABB-ABB test. If you construct and OBB from your ABB box, you shouldn't need to "adjust" the OBB-OBB case you should be able to run it as is. \$\endgroup\$ – Harald Scheirich Apr 24 '18 at 12:50
3
\$\begingroup\$

Brain dump:

  • The lines are a bit long. I have to consistently scroll to see a full line. While this is exacerbated by the narrow space alotted here on site, some of these lines are just really long :/
  • A lot of the comments there just seem to be an excuse to not use proper, explicit variable names. Example one:

    glm::vec3 l = glm::vec3(oneTransform[a]); // one axis to project on
    

    How about the following instead:

    glm::vec3 projectionAxis = glm::vec3(oneTransform[a]);
    

    Similar considerations apply for tl, ra and rb. They're better off as centerDistance, oneProjectedDistance and otherProjectedDistance respectively. (Maybe radiusOne and radiusOther could also be considered).

    On that note: a could just be axis


Last but not least, I am wondering why you're not doing this in a shader...
In my (admittedly amateur) understanding the shader is basically intended to quickly perform floating point math with little branching on the GPU.

That might also make the code look a little less clunky. Consider:

for (int axis = 0; axis < 3; axis++) 
{
    vec3 projectionAxis = oneTransform[axis].xyz;
    float distance = abs(projectionAxis.dot(otherCenter) - projectionAxis.dot(oneCenter));
    float radius_a = abs(projectionAxis.dot(oneTransform[0].xyz)) 
                    + abs(projectionAxis.dot(oneTransform[1].xyz))
                    + abs(projectionAxis.dot(oneTransform[2].xyz));
    // ...

This reads quite a bit cleaner to me, because the parens are easier to follow and it's somewhat easier to grasp the involved coordinates at one look.

And now that at least I can cleaner see what exactly is going on, I can't help but wonder whether this could be expressed as something like the following:

(Disclaimer: I've only done some quick checks with wolframalpha to see whether the dimensions match up)

vec3 radius_a_vec = abs(transpose(oneTransform) * projectionAxis);
float radius_a = radius_a_vec.x + radius_a_vec.y + radius_a_vec.z;

This makes the maths a bit harder to understand, but it immensely simplifies looking at the code...

\$\endgroup\$
  • 1
    \$\begingroup\$ With regard to your shader question, (this all depends on measurement) but latency is an issue when running code that is mixed between CPU and GPU, You might spend more time marshalling this data back and forth between the GPU and the CPU than actually calculating it. This is definitely a candidate for CPU parallelization, these intersection tests are usually independent of each other. \$\endgroup\$ – Harald Scheirich Apr 24 '18 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.