DevboyX

Tried rotating my bounding boxes, when my picking stopped working I realized they're meant to be axis aligned only.
Can anyone point me towards code for non AABBs that would also support intersection with a Ray object

Cheers




Re: XNA Game Studio Express Non axis aligned bounding boxes

Derek Nedelman

To intersect a ray with a box that isn't axis aligned, you can just transform the ray into the space for the bounding box (which is the space of the object that uses the box). You can do this by transforming the ray position by the inverse of the object's world matrix, and the direction by the inverse transpose of the world matrix. I don't have any code for you but if you've already written some sort of intersection code then the only changes you need to make are:

  • Don't create an AABB
  • Perform the inverse transformations I already described on the ray for each object, and use the objects bounding box directly.





Re: XNA Game Studio Express Non axis aligned bounding boxes

Newborn

Thanks,

Couple of things

Just to make sure, regarding the direction vector's matrix first transpose then invert or the other way around

Secondly (and sorry for going all linear ;)). I get what the inverse gives us - mathematically speaking. But what does the transpose do

Cheers







Re: XNA Game Studio Express Non axis aligned bounding boxes

Derek Nedelman

It's just a mathematical thing that you need to do to transform directions. Check out http://www.worldserver.com/turk/computergraphics/NormalTransformations.pdf for a far better explanation than I could give. In short, you first invert, then transpose. So it's something like Matrix.Transpose(Matrix.Invert(objectWorldMatrix))

Another option you have is to turn your ray into two endpoints and just transform those with the inverse and then recalculate the new transformed direction from the transformed endpoints





Re: XNA Game Studio Express Non axis aligned bounding boxes

Newborn

OK,

That worked but I have a bug.

When the object is rotated the picking area changes location and is rotated also. The offset is somehow related to the position of the camera (which is set up to always look at the negative z and perpendicular to the XY plane).

I know this is vague and you can't really understand what I'm doing (be happy to answer clarification questions). Does anyone have a clue of what could cause this

This is how I get my original Ray:

public Ray GetCursorPointRay()
{
Matrix proj = Projection;
Vector3 v, rayDirection, rayStart;
//Mouse to 3D point
v.X = (((2.0f * m_InputManager.MouseX) / m_Graphics.PreferredBackBufferWidth) - 1) / proj.M11;
v.Y = -(((2.0f * m_InputManager.MouseY) / m_Graphics.PreferredBackBufferHeight) - 1) / proj.M22;
v.Z = -1.0f;

Matrix m = Matrix.Invert(m_Camera.View);
// Transform the screen space pick ray into 3D space
rayDirection.X = v.X * m.M11 + v.Y * m.M21 + v.Z * m.M31;
rayDirection.Y = v.X * m.M12 + v.Y * m.M22 + v.Z * m.M32;
rayDirection.Z = v.X * m.M13 + v.Y * m.M23 + v.Z * m.M33;
rayDirection.Normalize();

//rayDirection.Normalize();
rayStart.X = m.M41;
rayStart.Y = m.M42;
rayStart.Z = m.M43;

return new Ray(rayStart, rayDirection);
}

And this is my shape intersection code:

public virtual bool Intersects(IntersectionCollection iCollection, Ray ray)
{
if (m_IdentityBoundingBox != null)
{
//Since box is not AABB, convert ray to boxes' local coordinate system
Matrix inv = Matrix.Invert(m_World);
Vector3 rayStart = Vector3.Transform(ray.Position, inv);
Vector3 rayDir = Vector3.Transform(ray.Direction, Matrix.Transpose(inv));
Ray localRay = new Ray(rayStart, rayDir);

//Find intersection
Nullable<float> f = m_IdentityBoundingBox.Intersects(localRay);
if (f.HasValue)
{
Vector3 localIntersectionPoint = localRay.Position + (localRay.Direction * f.Value);
iCollection.Add(new IntersectionInfo(this, Vector3.Transform(localIntersectionPoint, m_World)));iCollection.Add(new IntersectionInfo(this, ray.Position + (ray.Direction * f.Value)));
return true;
//iCollection.Add(new IntersectionInfo(this, Vector3.Add(ray.Position, (Vector3.Multiply(ray.Direction, f.Value)))));
}
else
{
return false;
}

}
}


Thanks

P.S.
I might be missing something but these being forums meant for source code, it's about time they support writing (and pasting!!!) code a little better. Don't you think

[edit]
Edited the code to fix a bug and also change the title to oriented bounding boxes instead of non aligned bounding boxes.





Re: XNA Game Studio Express Non axis aligned bounding boxes

Newborn

Can anyone point out if the code in the previous post is wrong

Cheers







Re: XNA Game Studio Express Non axis aligned bounding boxes

Newborn

Still at it,

Having hit a brick wall when trying the intersection method above (please, won't someone tell me what's wrong there ;)), I decided to try a different approach. A bit about that here followed by some code followed by a question.

I used the code from the butterfly game by catalinzima found at
http://xbox360homebrew.com/blogs/catalinzima/archive/2006/12/12/1699.aspx
The code uses an axes separation algorithm to check OBB intersection. It on turn is based on
Gomez's alogrithm (see http://www.gamasutra.com/features/19991018/Gomez_5.htm (at least I think it is)).
Another resource which is very helpful for someone attempting to grasp axes separation is
http://www.harveycartel.org/metanet/tutorials/tutorialA.html#section1
From the guys who wrote NGame (kicks ***!!). Although the tutorial explains it all in 2D, the principals are the same as 3D and it is beautify crafted with embedded flash visualizations.

Having said all that here's my adopted intersection check code.

public bool CheckIntersection(BoundingBox b2, Matrix world2)
{
// Vector3 sizeA = (b1.Max-b1.Min)*0.5f;
// Vector3 sizeB = (b2.Max-b2.Min)*0.5f;

// Vector3 posA = world1.Translation + b1.Min + sizeA;
// Vector3 posB = world2.Translation + b2.Min + sizeB;
return OBBOverlap(
(m_IdentityBoundingBox.Max - m_IdentityBoundingBox.Min) * 0.5f,
m_World.Translation + (m_IdentityBoundingBox.Min + m_IdentityBoundingBox.Max) * 0.5f,
m_World,
(b2.Max - b2.Min) * 0.5f,
world2.Translation + (b2.Min + b2.Max) * 0.5f,
world2);
}

Vector3 v;
Vector3 T;
Matrix R;
public bool OBBOverlap(
Vector3 a,
Vector3 Pa,
Matrix matrixA,
Vector3 b,
Vector3 Pb,
Matrix matrixB)
{
//translation, in parent frame
v = Pb - Pa;
T.X = Vector3.Dot(v, matrixA.Right);
T.Y = Vector3.Dot(v, matrixA.Up);
T.Z = Vector3.Dot(v, matrixA.Backward);

R = matrixA * matrixB;

/*ALGORITHM: Use the separating axis test for all 15 potential
separating axes. If a separating axis could not be found, the two
boxes overlap. */
//A's basis vectors
float ra, rb;
float t;

ra = a.X;
rb = Vector3.Dot(b, new Vector3(Math.Abs(R.M11), Math.Abs(R.M12), Math.Abs(R.M13)));
t = Math.Abs(T.X);
if (t > ra + rb)
return false;

ra = a.Y;
rb = Vector3.Dot(b, new Vector3(Math.Abs(R.M21), Math.Abs(R.M22), Math.Abs(R.M23)));
t = Math.Abs(T.Y);
if (t > ra + rb)
return false;

ra = a.Z;
rb = Vector3.Dot(b, new Vector3(Math.Abs(R.M31), Math.Abs(R.M32), Math.Abs(R.M33)));
t = Math.Abs(T.Z);
if (t > ra + rb)
return false;

//B's basis vectors
ra = Vector3.Dot(a, new Vector3(Math.Abs(R.M11), Math.Abs(R.M21), Math.Abs(R.M31)));
rb = b.X;
t = Math.Abs(Vector3.Dot(T, new Vector3(Math.Abs(R.M11), Math.Abs(R.M21), Math.Abs(R.M31))));
if (t > ra + rb)
return false;

ra = Vector3.Dot(a, new Vector3(Math.Abs(R.M12), Math.Abs(R.M22), Math.Abs(R.M32)));
rb = b.Y;
t = Math.Abs(Vector3.Dot(T, new Vector3(Math.Abs(R.M12), Math.Abs(R.M22), Math.Abs(R.M32))));
if (t > ra + rb)
return false;

ra = Vector3.Dot(a, new Vector3(Math.Abs(R.M13), Math.Abs(R.M23), Math.Abs(R.M33)));
rb = b.Z;
t = Math.Abs(Vector3.Dot(T, new Vector3(Math.Abs(R.M13), Math.Abs(R.M23), Math.Abs(R.M33))));
if (t > ra + rb)
return false;

//9 cross products

//L = A0 x B0
ra = a.Y * Math.Abs(R.M31) + a.Z * Math.Abs(R.M21);
rb = b.Y * Math.Abs(R.M13) + b.Z * Math.Abs(R.M12);
t = Math.Abs(T.Z * R.M21 - T.Y * R.M31);
if (t > ra + rb)
return false;

//L = A0 x B1
ra = a.Y * Math.Abs(R.M32) + a.Z * Math.Abs(R.M22);
rb = b.X * Math.Abs(R.M13) + b.Z * Math.Abs(R.M11);
t = Math.Abs(T.Z * R.M22 - T.Y * R.M32);
if (t > ra + rb)
return false;
//L = A0 x B2
ra = a.Y * Math.Abs(R.M33) + a.Z * Math.Abs(R.M23);
rb = b.X * Math.Abs(R.M12) + b.Y * Math.Abs(R.M11);
t = Math.Abs(T.Z * R.M23 - T.Y * R.M33);
if (t > ra + rb)
return false;
//L = A1 x B0
ra = a.X * Math.Abs(R.M31) + a.Z * Math.Abs(R.M11);
rb = b.Y * Math.Abs(R.M23) + b.Z * Math.Abs(R.M22);
t = Math.Abs(T.X * R.M31 - T.Z * R.M11);
if (t > ra + rb)
return false;
//L = A1 x B1
ra = a.X * Math.Abs(R.M32) + a.Z * Math.Abs(R.M12);
rb = b.X * Math.Abs(R.M23) + b.Z * Math.Abs(R.M21);
t = Math.Abs(T.X * R.M32 - T.Z * R.M12);
if (t > ra + rb)
return false;
//L = A1 x B2
ra = a.X * Math.Abs(R.M33) + a.Z * Math.Abs(R.M13);
rb = b.X * Math.Abs(R.M22) + b.Y * Math.Abs(R.M21);
t = Math.Abs(T.X * R.M33 - T.Z * R.M13);
if (t > ra + rb)
return false;
//L = A2 x B0
ra = a.X * Math.Abs(R.M21) + a.Y * Math.Abs(R.M11);
rb = b.Y * Math.Abs(R.M33) + b.Z * Math.Abs(R.M32);
t = Math.Abs(T.Y * R.M11 - T.X * R.M21);
if (t > ra + rb)
return false;
//L = A2 x B1
ra = a.X * Math.Abs(R.M22) + a.Y * Math.Abs(R.M12);
rb = b.X * Math.Abs(R.M33) + b.Z * Math.Abs(R.M31);
t = Math.Abs(T.Y * R.M12 - T.X * R.M22);
if (t > ra + rb)
return false;
//L = A2 x B2
ra = a.X * Math.Abs(R.M23) + a.Y * Math.Abs(R.M13);
rb = b.X * Math.Abs(R.M32) + b.Y * Math.Abs(R.M31);
t = Math.Abs(T.Y * R.M13 - T.X * R.M23);
if (t > ra + rb)
return false;
/*no separating axis found,
the two boxes overlap */

return true;


}

This worked just fine but since this intersects two OBBs and I was in the market for 3D mouse picking I attempted to follow Gomez's instructions here:
http://www.gamasutra.com/features/19991018/Gomez_6.htm
and convert my ray to a line segment, intersect that with an OBB thus getting the picking routine:

public Ray WorldToLocalRay(Ray worldRay)
{
Matrix inv = Matrix.Invert(m_World);
Vector3 rayStart = Vector3.Transform(worldRay.Position, inv);
Vector4 rayDir = Vector4.Transform(new Vector4(worldRay.Direction, 0), Matrix.Transpose(inv));
Ray localRay = new Ray(rayStart, new Vector3(rayDir.X, rayDir.Y, rayDir.Z));
return localRay;
}

public bool CheckIntersection(Ray ray, float lengthAlongRay)
{
Ray localRay = WorldToLocalRay(ray);
Vector3 midPoint = localRay.Position + ((localRay.Direction * lengthAlongRay) / 2.0f);
float hl = lengthAlongRay / 2.0f;
float r;
float t;

Vector3 boxExtents = (m_IdentityBoundingBox.Max - m_IdentityBoundingBox.Min) * 0.5f;
Vector3 boxPos = m_World.Translation + (m_IdentityBoundingBox.Min + m_IdentityBoundingBox.Max) * 0.5f;
Vector3 T = boxPos - midPoint;

if (Math.Abs(T.X) > boxExtents.X + hl * Math.Abs(localRay.Direction.X))
return false;

if (Math.Abs(T.Y) > boxExtents.Y + hl * Math.Abs(localRay.Direction.Y))
return false;

if (Math.Abs(T.Z) > boxExtents.Z + hl * Math.Abs(localRay.Direction.Z))
return false;

/* NOTE: Since the separating axis is
perpendicular to the line in these
last four cases, the line does not
contribute to the projection. */

//l.cross(x-axis)

r = boxExtents.Y * Math.Abs(localRay.Direction.Z) + boxExtents.Z * Math.Abs(localRay.Direction.Y);

if (Math.Abs(T.Y * localRay.Direction.Z - T.Z * localRay.Direction.Y) > r)
return false;

//l.cross(y-axis)

r = boxExtents.X * Math.Abs(localRay.Direction.Z) + boxExtents.Z * Math.Abs(localRay.Direction.X);

if (Math.Abs(T.Z * localRay.Direction.X - T.X * localRay.Direction.Z) > r)
return false;

//l.cross(z-axis)

r = boxExtents.X * Math.Abs(localRay.Direction.Y) + boxExtents.Y * Math.Abs(localRay.Direction.X);

if (Math.Abs(T.X * localRay.Direction.Y - T.Y * localRay.Direction.X) > r)
return false;

return true;
}

For a detailed explanation of why WorldToLocalRay uses Vector4 see
http://www.unknownroad.com/rtfm/graphics/rt_normals.html.
It didn't really matter in the end, but this is a good thing to know ;)

Finally, I put all this info here for 2 reasons.
A) Give anyone walking in my footsteps a fighting chance.
B) I still can't get it to work :) If anyone can tell me why I'd be happy. When I use the mouse picking method, it always hits in an offset to the actual object.

Cheers







Re: XNA Game Studio Express Non axis aligned bounding boxes

Michael Morton

Collision between a ray and an oriented bounding box is the same as a ray with an axis aligned bounding box. Simply transform the ray by the inverse transform of the oriented bounding box then check the collision with the ray and AABB.






Re: XNA Game Studio Express Non axis aligned bounding boxes

habier

hi NewBorn,

im using Gomez's code too. Im trying to understand how it works, and i think i know it now. But i must to be giving incorrect parameters to this function. The function use to work, and use to detect the collision, but lot of times it detect collision where there isnt a collision yet (the boxes are near but there is a good separation still, however the collision is detected).

I "imagine" the box in this way:

v7 ----- v6

/ / | (and v3 is the vertex not vissible)

/ / |

v4-------v5 v2

| | /

| | /

v0 ----- v1

Having the Gomez's function:

//check if two oriented bounding boxes overlap
unsigned int OBBOverlap
(
//A
TVertex& a, //extents
TVertex& Pa, //position
TVertex* A, //orthonormal basis
//B
TVertex& b, //extents
TVertex& Pb, //position
TVertex* B //orthonormal basis
)

Im taking orthonormal basis for the box (parameters A,B) as:

x = normalize(v2-v3)

y = normalize(v7-v3)

z = normalize(v0-v3)

Im taking extents (parameters a,b) as:

extents = fabs((v6-v0)/2)

And positions (parameteres Pa and Pb) as:

pos = v0 + extents (center of the box)

I think it should work but i guess im giving some incorrect param. Sometimes (with some positions of second box relative to first box) the function is detecting collision

where there isnt it. Both boxes are near but im seeing clearly there is a good separation between them yet.

Could you help me Am i doing a incorrect thing

Thanks in advance.