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

2 replies to this topic

#1Dr.Spankenstein

New Member

• Members
• 9 posts

Posted 20 February 2010 - 05:49 PM

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?

#2Kenneth Gorking

Senior Member

• Members
• 939 posts

Posted 20 February 2010 - 06:59 PM

Why do you need it to be faster? Is it showing up in your profiling?
"Stupid bug! You go squish now!!" - Homer Simpson

#3Dr.Spankenstein

New Member

• Members
• 9 posts

Posted 20 February 2010 - 07:30 PM

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?

1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users