2
\$\begingroup\$

This might be more of a math question, but it relates to the development of a simple physics engine I am trying to create.

I have been stumped on this for about a week now, and have been unable to find an answer in any of the SAT tutorials. (http://www.metanetsoftware.com/technique/tutorialA.html#toc, http://gamedevelopment.tutsplus.com/tutorials/collision-detection-using-the-separating-axis-theorem--gamedev-169, etc.)

I understand how SAT is supposed to work, however I am little confused on the math. First, I am finding my normals like so:

Block.prototype.findNormals = function () {

        var axisVectors = new Array();
        var vertices = this.Properties.Vertices;
        var keys = Object.keys(vertices) 

        for( var i = 0; i < keys.length; i++) {
            var last = {x: 0, y: 0};

            axisVectors.push({xComponent: -(vertices[keys[i]].y - last.y), yComponent: (vertices[keys[i]].x - last.x) });

            last = {x: this.x, y: this.y};
        }

        return axisVectors;
    }

I am then precede to project each vertex of the shapes I am testing on those normals.

The problem occurs, and the part of the math that I am not fully understanding, is when I have a situation like so:

axis = (-5, 6)
vertex = (6, 5)

math.dot(vertex, axis)

This results in 0.

Thus my min value for shape1 is always 0. And this results in a false collision.

Can anyone explain the math a little better?

\$\endgroup\$
1
\$\begingroup\$

Your normals are supposed to be the face normals of a polygon. If your vertices are an oriented array in counter clockwise order, then you can easily compute the normal of a face by a 90 degree rotation.

So if we have an edge on a polygon made of the vertices a and b, we know that the edge is oriented from a to b going around the polygon in CCW order. To rotate the edge such that we end up with a vector that points outward from the polygon (of unit length), we need a 90 degree clockwise rotation and one normalization.

Here's the rotation matrix for that in column major:

$$ \begin{bmatrix} cos( 90 ) & sin( 90 ) \\ -sin( 90 ) & cos( 90 ) \\ \end{bmatrix} $$

If you compute sin and cos and multiply this matrix with a vector { x, y } you realize that all you're doing is flipping the x and y component and negating the new y component.

We can write a function for this:

Vector ComputeNormal( Vector a, Vector b )
{
    Vector ab = Normalize( b - a );
    return Vector( ab.y, -ab.x );
}

Don't forget to normalize your normals.

\$\endgroup\$
  • \$\begingroup\$ Ok, I think I am understanding. So as an example, for a square assuming we are starting at the top left corner and morving counter clockwise. We would do something like: vector edge = b.x - a.x; //Finding the edge vector Normalize(edge); return [edge.y, -edge.x] // Simply flipping and negating width this result though, won't it return zero when I try to take the dot product of the result and the edge it is perpendicular with? meaning that the min coordinate on the projection axis will always come out to zero? \$\endgroup\$ – Avery Pfeiffer Jan 13 '15 at 14:45
  • \$\begingroup\$ @AveryPfeiffer You wouldn't do b.x - ax, you would do b - a. There's an important difference between vector and scalar math here. But you are getting close! \$\endgroup\$ – RandyGaul Jan 13 '15 at 22:01

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.