0
\$\begingroup\$

So over the past week I've been scratching my head over SAT (Separating Axis Theorem). I know how it works, but can't seem to get the C# code right. There's always one face or edge that's letting my player through an obstacle.

So I wanted to know if maybe I'm taking the hard way around, and I don't need SAT for what I want to achieve.

My Game Involves:
- 3D Cubes which will sometimes be on an angle (not a multiple of 90)
- Not too many cubes (so I don't need my Collision Detection to be too inexpensive)
- OBB collisions

So what is the best option for me collision-wise? If SAT is my go to option, what would it look like in C#?

EDIT

My Sat code:

var n1 = (bb1.BCK_TOP_LFTCorner - bb1.BCK_BTM_LFTCorner).Normalized();
var n2 = (bb1.BCK_BTM_LFTCorner - bb1.BCK_BTM_RGTCorner).Normalized();
var n3 = (bb1.FRT_BTM_LFTCorner - bb1.BCK_BTM_LFTCorner).Normalized();
var n4 = (bb2.BCK_TOP_LFTCorner - bb2.BCK_BTM_LFTCorner).Normalized();
var n5 = (bb2.BCK_BTM_LFTCorner - bb2.BCK_BTM_RGTCorner).Normalized();
var n6 = (bb2.FRT_BTM_LFTCorner - bb2.BCK_BTM_LFTCorner).Normalized();
var norms = new List<Vector3>() {
     new Vector3(-n1.X, n1.Y,n1.Z),
     new Vector3(n2.X, -n2.Y,n2.Z),
     new Vector3(n3.X, n3.Y,-n3.Z),
     new Vector3(-n4.X, n4.Y,n4.Z),
     new Vector3(n5.X, -n5.Y,n5.Z),
     new Vector3(n6.X, n6.Y,-n6.Z),
};
norms = bb2.Normals;
float max1 = 0;
float min1 = 0;
float max2 = 0;
float min2 = 0;
for (int a = 0; a < norms.Count; ++a)
{
    //Global.Min/Global.Max are simply Math.Min/Math.Max for an array of parameters
    max1 = Global.Max(Vector3.Dot(bb1.Corners[0], norms[a]),
            Vector3.Dot(bb1.Corners[1], norms[a]),
            Vector3.Dot(bb1.Corners[2], norms[a]),
            Vector3.Dot(bb1.Corners[3], norms[a]),
            Vector3.Dot(bb1.Corners[4], norms[a]),
            Vector3.Dot(bb1.Corners[5], norms[a]));
        min1 = Global.Min(Vector3.Dot(bb1.Corners[0], norms[a]),
            Vector3.Dot(bb1.Corners[1], norms[a]),
            Vector3.Dot(bb1.Corners[2], norms[a]),
            Vector3.Dot(bb1.Corners[3], norms[a]),
            Vector3.Dot(bb1.Corners[4], norms[a]),
            Vector3.Dot(bb1.Corners[5], norms[a]));
        max2 = Global.Max(Vector3.Dot(bb2.Corners[0], norms[a]),
            Vector3.Dot(bb2.Corners[1], norms[a]),
            Vector3.Dot(bb2.Corners[2], norms[a]),
            Vector3.Dot(bb2.Corners[3], norms[a]),
            Vector3.Dot(bb2.Corners[4], norms[a]),
            Vector3.Dot(bb2.Corners[5], norms[a]));
        min2 = Global.Min(Vector3.Dot(bb2.Corners[0], norms[a]),
            Vector3.Dot(bb2.Corners[1], norms[a]),
            Vector3.Dot(bb2.Corners[2], norms[a]),
            Vector3.Dot(bb2.Corners[3], norms[a]),
            Vector3.Dot(bb2.Corners[4], norms[a]),
            Vector3.Dot(bb2.Corners[5], norms[a]));


    }
if (max1 < min2)
    return Vector3.Zero;
    // Get nearest face normal to player so that we can add it to player's velocity.
    var rl = new List<Vector3>() {bb2.Front,
        bb2.Back,
        bb2.Top,
        bb2.Bottom,
        bb2.Left,
        bb2.Right };
    var r = rl.IndexOf(rl.OrderBy(c => c.Distance(bb1.Center)).First());
    var returnval = bb2.Normals[r];
    return returnval;
\$\endgroup\$
2
  • \$\begingroup\$ Maybe you should show your code \$\endgroup\$
    – Bálint
    Apr 5, 2017 at 8:53
  • \$\begingroup\$ Okay, I'll make sure to do that when I'm at a computer. \$\endgroup\$
    – user81509
    Apr 5, 2017 at 10:22

1 Answer 1

1
\$\begingroup\$

SAT is a good algorithm for learning narrow phase collision detection, as the code is pretty intuitive.

As to what it would look like in language X, you should simply read a tutorial on SAT and then port it to your language of choice once you understand the algorithm completely.

I would say this though: If you plan to do any sort of accurate physics, you will need additional processing on top of SAT code to compute contact points, and online tutorials are a little spotty on that subject. If you find the additional processing is hard to find/wrap your head around, take a look at:

  1. Gilbert Johnson Keerthi (GJK)
  2. Expanding Polytope Algorithm (EPA)
  3. Minkowski Difference

All these are perhaps a little more difficult to wrap your head around, but they are pretty fast, and provide contact points "out of the box" will no additional processing.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks Ian, a little late to the party, but I'll still research these. \$\endgroup\$
    – user81509
    May 9, 2017 at 10:18

You must log in to answer this question.