Jump to content
  • Advertisement
Sign in to follow this  
Spa8nky

Finding the AABB surface normal from an intersection point on AABB

This topic is 3279 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello folks, If I know the point of intersection on an AABB, is there a easy way of obtaining the surface normal using that point? The following is the ray/AABB intersection test I am using:
        private bool IntersectAABB(CD_AxisAlignedBoundingBox aABB, ref Contact contact)
        {
            float t_Min = 0.0f;
            float t_Max = float.MaxValue;   // Maximum distance ray can travel (makes it a segment, otherwise it would be infinite)
            
            float ood = 0.0f;
            float t1 = 0.0f;
            float t2 = 0.0f;

            // For all 3 slabs
            if (Math.Abs(Direction.X) < float.Epsilon)
            {
                // Ray is parallel to slab.  No hit if origin (p in book) not within slab
                if (Origin.X < aABB.MinPoint.X || Origin.X > aABB.MaxPoint.X)
                {
                    return false;
                }
            }
            else
            {
                // Compute intersection t value of ray with near and far plane of slab
                ood = 1.0f / Direction.X;
                t1 = (aABB.MinPoint.X - Origin.X) * ood;
                t2 = (aABB.MaxPoint.X - Origin.X) * ood;

                // Make (t1) be intersection with near plane, (t2) with far plane
                if (t1 > t2)
                {
                    Swap(ref t1, ref t2);
                }

                // Compute the intersection of slab intersection intervals
                t_Min = Math.Max(t_Min, t1);
                t_Max = Math.Min(t_Max, t2);

                // Exit with no collision as soon as slab intersection becomes empty
                if (t_Min > t_Max)
                {
                    return false;
                }
            }
            if (Math.Abs(Direction.Y) < float.Epsilon)
            {
                // Ray is parallel to slab.  No hit if origin (p in book) not within slab
                if (Origin.Y < aABB.MinPoint.Y || Origin.Y > aABB.MaxPoint.Y)
                {
                    return false;
                }
            }
            else
            {
                // Compute intersection t value of ray with near and far plane of slab
                ood = 1.0f / Direction.Y;
                t1 = (aABB.MinPoint.Y - Origin.Y) * ood;
                t2 = (aABB.MaxPoint.Y - Origin.Y) * ood;

                // Make (t1) be intersection with near plane, (t2) with far plane
                if (t1 > t2)
                {
                    Swap(ref t1, ref t2);
                }

                // Compute the intersection of slab intersection intervals
                t_Min = Math.Max(t_Min, t1);
                t_Max = Math.Min(t_Max, t2);

                // Exit with no collision as soon as slab intersection becomes empty
                if (t_Min > t_Max)
                {
                    return false;
                }
            }
            if (Math.Abs(Direction.Z) < float.Epsilon)
            {
                // Ray is parallel to slab.  No hit if origin (p in book) not within slab
                if (Origin.Z < aABB.MinPoint.Z || Origin.Z > aABB.MaxPoint.Z)
                {
                    return false;
                }
            }
            else
            {
                // Compute intersection t value of ray with near and far plane of slab
                ood = 1.0f / Direction.Z;
                t1 = (aABB.MinPoint.Z - Origin.Z) * ood;
                t2 = (aABB.MaxPoint.Z - Origin.Z) * ood;

                // Make (t1) be intersection with near plane, (t2) with far plane
                if (t1 > t2)
                {
                    Swap(ref t1, ref t2);
                }

                // Compute the intersection of slab intersection intervals
                t_Min = Math.Max(t_Min, t1);
                t_Max = Math.Min(t_Max, t2);

                // Exit with no collision as soon as slab intersection becomes empty
                if (t_Min > t_Max)
                {
                    return false;
                }
            }

            // Ray intersects all 3 slabs
            // Only update contact parameters if this is the closest intersected so far
            if (contact.KeepClosest(t_Min))
            {
                contact.location = Origin + t_Min * Direction;
                //contact.normal

                // Only allow this test to return true if the primitive tested is the closest to the ray origin
                return true;
            }
              
            return false;
        }

Thanks.

Share this post


Link to post
Share on other sites
Advertisement
This will be a rather cursory answer, but you can track the collision normal by updating it each time you update the 'near' t value (that is, every time you update the near t value, you set the normal to the normal corresponding to the current slab and slab side - at the end of the function, if there was an intersection, you'll have the correct normal for the intersection as well).

Also, when implementing these sorts of algorithms it can be useful if your vector class supports indexed access in addition to (or instead of) named element access. With indexed access, you could collapse the three 'slab' code blocks into a single loop, thereby reducing code duplication.

Share this post


Link to post
Share on other sites
Quote:

Also, when implementing these sorts of algorithms it can be useful if your vector class supports indexed access in addition to (or instead of) named element access. With indexed access, you could collapse the three 'slab' code blocks into a single loop, thereby reducing code duplication.


Tell me about it. XNA enforces the .X .Y .Z parameters unfortunately so I will have to make time to create a Vector3 from an array of 3 points and add all the relevant methods such as cross product, dot product, etc.

I will try your method when I am back from work, it seems sensible to me to do it this way and not all that cursory as you said.

I am still interested in a method that can return a normal from a point of intersection with an AABB, if anyone knows of such.

Thank you jyk.

Share this post


Link to post
Share on other sites
Quote:
I am still interested in a method that can return a normal from a point of intersection with an AABB, if anyone knows of such.
Do you mean a function that, given an AABB and a point on the AABB (and no other information), returns the normal corresponding to that point?

If so, I think such a function should be fairly easy to construct. You might start by transforming the query point to the AABB's local space by subtracting the AABB center from the point. You can then identify which 'slab' the point corresponds to by examining the elements of the transformed point in turn; the element whose magnitude is closest to the box extent in that direction will correspond to the slab. Then, the sign of the element will give you the side of the slab, and you have your normal. (I haven't actually tried this method, but it seems correct.)

Share this post


Link to post
Share on other sites
Quote:

You can then identify which 'slab' the point corresponds to by examining the elements of the transformed point in turn; the element whose magnitude is closest to the box extent in that direction will correspond to the slab. Then, the sign of the element will give you the side of the slab, and you have your normal.


I have tried that and have come up with the following:


contact.location = Origin + t_Min * Direction;
contact.normal = contact.location - aABB.Position;

if (contact.normal.X == -aABB.Extents_HalfWidth.X)
{
contact.normal = Vector3.Left;
}
if (contact.normal.X == aABB.Extents_HalfWidth.X)
{
contact.normal = Vector3.Right;
}
if (contact.normal.Y == -aABB.Extents_HalfWidth.Y)
{
contact.normal = Vector3.Down;
}
if (contact.normal.Y == aABB.Extents_HalfWidth.Y)
{
contact.normal = Vector3.Up;
}
if (contact.normal.Z == -aABB.Extents_HalfWidth.Z)
{
contact.normal = Vector3.Forward;
}
if (contact.normal.Z == aABB.Extents_HalfWidth.Z)
{
contact.normal = Vector3.Backward;
}



Is this what you meant, or is there a more elegant way of the above (besides from indexing the (X,Y,Z))?

If this is the most sensible way then I should change the if statement from == to within a range of.

Share this post


Link to post
Share on other sites
Quote:
Original post by Spa8nky
Quote:

You can then identify which 'slab' the point corresponds to by examining the elements of the transformed point in turn; the element whose magnitude is closest to the box extent in that direction will correspond to the slab. Then, the sign of the element will give you the side of the slab, and you have your normal.


I have tried that and have come up with the following:

*** Source Snippet Removed ***

Is this what you meant, or is there a more elegant way of the above (besides from indexing the (X,Y,Z))?

If this is the most sensible way then I should change the if statement from == to within a range of.
That's close, but you'll almost certainly need to introduce a tolerance to get reasonable results. Furthermore, rather than using a fixed epsilon as the tolerance, I would just take the 'closest' slab; this way, the algorithm will always (or at least should always) return a valid result, and you won't need to worry about choosing an appropriate epsilon value.

Also, I wouldn't use the 'normal' variable temporarily as in your example, as that could cause confusion (if not incorrect behavior).

Here's some pseudocode (not tested):
vector3 GetNormal(vector3 point, AABB box)
{
vector3 normal = zero_vector();
float min_distance = max_float();
point -= box.center;

for (int i = 0; i < 3; ++i) {
float distance = abs(box.extents - abs(point));
if (distance < min_distance) {
min_distance = distance;
normal = sign(point) * cardinal_axis(i);
}
}

return normal;
};

Share this post


Link to post
Share on other sites
Awesome, many thanks.

I think I'm going to have to create my own Vector3 class this weekend as the indexing is just too good not to have.

Share this post


Link to post
Share on other sites
Just confirming that your method works, here is the working code:


public Vector3 GetNormalFromPoint(Vector3 point)
{
Vector3 normal = Vector3.Zero;
float min = float.MaxValue;
float distance;

point -= Centre;

distance = Math.Abs(Extents.X - Math.Abs(point.X));
if (distance < min)
{
min = distance;
normal = Math.Sign(point.X) * Vector3.UnitX; // Cardinal axis for X
}
distance = Math.Abs(Extents.Y - Math.Abs(point.Y));
if (distance < min)
{
min = distance;
normal = Math.Sign(point.Y) * Vector3.UnitY; // Cardinal axis for Y
}
distance = Math.Abs(Extents.Z - Math.Abs(point.Z));
if (distance < min)
{
min = distance;
normal = Math.Sign(point.Z) * Vector3.UnitZ; // Cardinal axis for Z
}

return normal;
}



If I were to use a float[3] for Vector3 then how would I construct the class given that the float[3] parameter must have a name and therefore something like box.extents cannot exist?

box.extents.float can though, or have I missed something obvious?

Share this post


Link to post
Share on other sites
Quote:
If I were to use a float[3] for Vector3 then how would I construct the class given that the float[3] parameter must have a name and therefore something like box.extents cannot exist?

box.extents.float can though, or have I missed something obvious?
I'm not quite following - my C# is a little rusty though, so maybe I'm just not understanding. In any case though, you probably won't want to give up the Vec3 class (since presumably there's a fair amount of functionality associated with it).

Here's another option you could consider though. Go ahead and use Vec3, and make a 'free' (static member in C#, I guess) function that takes a Vec3 and an integer index as arguments, and returns the specified element. In pseudocode, it might look like this:
float element(Vec3 v, int i) {
switch (i) {
case 0: return v.X;
case 1: return v.Y;
case 2: return v.Z;
}
}
You can then use this function where indexed access is needed (or would be convenient).

Share this post


Link to post
Share on other sites
Hi jyk,

I can create a Vector3 class extension as follows:


public static float Element(this Vector3 vector3, int i)
{
switch (i)
{
case 0:
return vector3.X;
case 1:
return vector3.Y;
case 2:
return vector3.Z;
default:
return 0;
}
}



The thing that puzzled me about the elements was the fact that in many books a Vector3 would be referred to as (for example):

Plane.Normal[n] where n is 0, 1 or 2.
Triangle.A[n]
AABB.Extents[n]
etc.

How would I create a Vector3 class that allows for this as I can only figure out a method that would allow me to create a *.Normal.Elements[n] or Triangle.A.Elements[n].

In other words it would be necessary to refer to the array of points by a parameter name (in this case Elements) rather than accessing it directly through "[]"

Thanks again.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!