How can I speed up the following swept test for two 2D OBBs?

06038bd876add42c26fb4628ff49e1b0
0
Dr_Spankenstein 101 Feb 20, 2010 at 17:49

Hello all,

I am currently using this method for testing each of the 4 axes of separation between two 2D OBBs:

        private static bool IntersectThruAxisSwept(Vector2 axis, CD_OBB2D a, CD_OBB2D b, float t_Enter, float t_Exit, ref float mtv_Distance, ref Vector2 mtv_Axis, ref Contact2D contact)
        {
            // [Separating Axis Theorem]
            // • Two convex shapes only overlap if they overlap on all axes of separation
            // • In order to create accurate responses we need to find the collision vector (Minimum Translation Vector)   
            // • Find if the two boxes intersect along a single axis 
            // • Compute the intersection interval for that axis
            // • Keep the smallest intersection/penetration value
            float a_Min = float.MaxValue;
            float a_Max = float.MinValue;
            float b_Min = float.MaxValue;
            float b_Max = float.MinValue;

            a.CalculateSlab(axis, ref a_Min, ref a_Max);
            b.CalculateSlab(axis, ref b_Min, ref b_Max);

            // Find distance intervals for current two slabs
            // Distance is between slab min/max values
            float d_S0 = a_Min - b_Max;
            float d_S1 = b_Min - a_Max;

            // The distance is positive if the intervals do not overlap
            // Must be >= to 0 and not > 0, otherwise MTV can equal Vector2.Zero and cause NaN
            if (d_S0 >= 0f || d_S1 >= 0f)
            {
                return false;
            }

            // Current distance interval for slabs [A_Min, A_Max] and [B_Min, B_Max]
            float d = (d_S0 > d_S1) ? -d_S0 : d_S1;

            // If d is the smallest distance so far
            if (Math.Abs(d) < Math.Abs(mtv_Distance))
            {
                // Store the distance and the current axis
                mtv_Distance = d;
                mtv_Axis = axis;
            }

            //===========================================================
            //---[Swept Test]--------------------------------------------
            //===========================================================

            // Convert the slab for B into a 1D ray
            float origin = (b_Max + b_Min) * 0.5f;                          // Origin of ray
            float e = (b_Max - b_Min) * 0.5f;                               // Extent of slab B
            float direction = Vector2.Dot(b.Velocity - a.Velocity, axis);   // Direction of ray (projected onto current axis of separation)

            // Expand the slab for A by the extent of the slab for B
            // This transforms a slab/slab collision test into a ray/slab collision test
            a_Min -= e;
            a_Max += e;

            // Do a 1 dimensional collision check on projected axis
            return RaySlabIntersect(a_Min, a_Max, origin, direction, t_Enter, t_Exit, ref contact);
        }

In this case the 4 axes tested are:

[Axes of separation]
1) a.UR - a.UL
2) a.UR - a.LR
3) b.UL - b.LL
4) b.UL - b.UR

Currently I am calculating the slab using the following method:

        public void CalculateSlab(Vector2 axis, ref float min, ref float max)
        {
            // • A slab is the infinite region of space between two planes
            // • For polygonal objects, the positions of the 2 planes can be found by computing
            //   the dot product of the normal (axis) and each object vertex.
            // • The min and max values are then the required scalar values defining the plane positions
            for (int i = 0; i < 4; ++i)
            {
                float d = Vector2.Dot(new Vector2(vertices_World[i].X, vertices_World[i].Y), axis);

                if (d < min)
                {
                    min = d;
                }
                if (d > max)
                {
                    max = d;
                }
            }
        }

However, there must be a faster way of calculating the slabs seeing as I am dealing with two OBBs.

Can anyone suggest a faster way of calculating them please?

2 Replies

Please log in or register to post a reply.

46407cc1bdfbd2db4f6e8876d74f990a
0
Kenneth_Gorking 101 Feb 20, 2010 at 18:59

Why do you need it to be faster? Is it showing up in your profiling?

06038bd876add42c26fb4628ff49e1b0
0
Dr_Spankenstein 101 Feb 20, 2010 at 19:30

Isn’t the calculation of the slab by checking each of the 4 vertices redundant?

I already know that the OBB has the same x for both positive and negative extents, and the same for y?

I.e.

        public Vector2 MaxPoint
        {
            get { return Vector2.Transform(extents, Matrix.CreateRotationZ(rotation)); }
        }

        /// <summary>
        /// Rectangle min point (contained within rectangle extents)
        /// </summary>
        public Vector2 MinPoint
        {
            get { return Vector2.Transform(-extents, Matrix.CreateRotationZ(rotation)); }
        }

Therefore there must be a more optimal way of getting the correct slab?