PDA

View Full Version : How to get a hit point vector from a OBB Raycast Test

hashbrown
09-26-2016, 01:22 AM
I'm learning how OBB Raycasting works from this great site (http://www.opengl-tutorial.org/miscellaneous/clicking-on-objects/picking-with-custom-ray-obb-function/). I'm testing against a cube and managed to get everything up and running (intersection test works), but I can't seem to figure out how to get the point of intersection. I'd love to return the exact position the ray first hit the box, or in other words: what position on the target box's normal local space was hit. I'd use these coordinates to stick another game object there. Think sticking c4 on a wall (in a game).

Right now what I do is:

hitpoint.x = targetWorldspace.x + (-delta.x / distance);
hitpoint.y = targetWorldspace.y; // Nothing special
hitpoint.z = targetWorldspace.z + (-delta.z / distance);

... this happens after intersection test passed.

This barely works, the hit point definitely ends up on the right side of the cube, and somewhat close to the correct face. If I don't give the hitpoint some offset, the hitpoint would be in the middle of the target box obviously. I'm very sure I'm doing it wrong. This is what I'm using to test intersection:

bool Collision::OBBIntersection(
Vec3 origin,
Vec3 dir,
Vec3 aabbMin,
Vec3 aabbMax,
GameObject &target,
float &distance,
Vec3 &hitpoint){

float tMin = 0.0f;
float tMax = 100000.0f;

Mat4 model = target.GetTransform().GetModel();

Vec3 targetWorldspace;

targetWorldspace.x = model.mat[0][3];
targetWorldspace.y = model.mat[1][3];
targetWorldspace.z = model.mat[2][3];

Vec3 delta = (targetWorldspace - origin);

{
Vec3 xAxis(model.mat[0][0], model.mat[1][0], model.mat[2][0]);
float e = Trig::Dot(xAxis, delta);
float f = Trig::Dot(dir, xAxis);
if (fabs(f) > 0.001f) {
float t1 = (e + aabbMin.x)/f;
float t2 = (e + aabbMax.x)/f;

if (t1 > t2) {
float w = t1;
t1 = t2;
t2 = w;
}

if (t2 < tMax) {
tMax = t2;
}
if (t1 > tMin) {
tMin = t1;
}
if (tMax < tMin) {
return false;
}
}
else {
if (-e + aabbMin.x > 0.0f || -e + aabbMax.x < 0.0f) {
return false;
}
}
}

{
Vec3 yAxis(model.mat[0][1], model.mat[1][1], model.mat[2][1]);
float e = Trig::Dot(yAxis, delta);
float f = Trig::Dot(dir, yAxis);
if (fabs(f) > 0.001f) {
float t1 = (e + aabbMin.y)/f;
float t2 = (e + aabbMax.y)/f;

if (t1 > t2) {
float w = t1;
t1 = t2;
t2 = w;
}

if (t2 < tMax) {
tMax = t2;
}
if (t1 > tMin) {
tMin = t1;
}
if (tMax < tMin) {
return false;
}
}
else {
if (-e + aabbMin.y > 0.0f || -e + aabbMax.y < 0.0f) {
return false;
}
}
}

{
Vec3 zAxis(model.mat[0][2], model.mat[1][2], model.mat[2][2]);
float e = Trig::Dot(zAxis, delta);
float f = Trig::Dot(dir, zAxis);

if (fabs(f) > 0.001f) {
float t1 = (e + aabbMin.z)/f;
float t2 = (e + aabbMax.z)/f;

if (t1 > t2) {
float w = t1;
t1 = t2;
t2 = w;
}

if (t2 < tMax) {
tMax = t2;
}
if (t1 > tMin) {
tMin = t1;
}
if (tMax < tMin) {
return false;
}
}
else {
if (-e + aabbMin.z > 0.0f || -e + aabbMax.z < 0.0f) {
return false;
}
}
}

distance = tMin;

hitpoint.x = targetWorldspace.x + (-delta.x / distance);
hitpoint.y = targetWorldspace.y;
hitpoint.z = targetWorldspace.z + (-delta.z / distance);

return true;
}

BBeck1
09-28-2016, 07:06 AM
I saw this question yesterday and I kind of let it sit and avoided it because I thought someone else might jump in and answer it better since I don't have the exact answer right off the top of my head. I've done it before, but it's been awhile and not in OGL. I think what I was using at the time had some built in functions for most of it. Still, it's mostly just a math question.

This is starting to come back to me as I Google it a bit. You're basically ray casting and looking for the point of intersection with the given plane. Since you have a box that you are intersecting with, this should be relatively easy. With a more complex shape, you would probably have to first identify which triangle of the collision model you are intersecting with in order to get the plane. With a box, you should be able to determine which side of the box is the closest. If it's an Axis Aligned Bounding Box, it should be almost trivial to do so. If it's an Oriented Bounding Box it will be more difficult but probably not too hard to decide which side the ray might be intersecting with. You could test all six sides, but you probably only want to test the sides visible to the ray because it's probably entering the box on one side and intersecting it again as it leaves, which would give you two points of intersection. Obviously the closest is the place where it first intersects.

Anyway, I think you need to reduce the problem to a ray and a plane. Then you can determine where on that plane the intersection occurred in order to know the point in 3D space where it occurred. This would be in world space. To get back to the object's private space you could use the object's world matrix to translate to there I believe. That is likely an inverse matrix. And to attach an object to that spot, you have to forever keep feeding it the parent object's matrix so that it can be relatively positioned to the parent.

So, if you have a side of the bounding box it is going to be formed by two triangles. Two sides of the triangle can be treated as vectors. In other words, you have four vertices that form two triangles. Throw one triangle away to leave three vertices. It doesn't matter which because I'm assuming they are all co-planar. You just need 3 vertices to form two vectors that share a vertex at their base.

Two vectors with a common tail is something you will use over and over again for the vector cross product. Normalize both vectors (I think this is required) and then get their vector cross product. This will give you a normal that faces straight out of the plane they live on. It's the plane of that box face.

In game math, planes are described by a normal that points straight out of the plane and a point that lives on the plane. I believe you can use the shared vertex as the point that lives on the plane. So now you have a plane object that describes that side of the box and you can do ray casting against it.

I think you pretty much already had at least a line. You have a point from which the ray is cast. Then you have the vector (probably normalized) that is the direction the line goes in. The ray is considered infinite; it goes on forever. The first question is whether it intersects with the plane at all. And if it does, what point in 3D space does the intersection occur?

I believe you can use the "LinePlaneIntersection" function found here (http://wiki.unity3d.com/index.php/3d_Math_functions) for this. When I first looked at this, I thought it was C++ (apparently I've been jumping back and forth between languages too much). It's C#. C# scripting for Unity to be more precise. That shouldn't matter. You should be able to translate it to C++ and it's a math problem, not a coding problem. So, the language shouldn't matter. "c++ line plane intersection" turns up quite a bit on a Google search for maybe a C++ version of the same thing.

Anyway, a function like that should return a 3D point of intersection. The distance to that point is your distance to the point of collision. I would probably use the object's world matrix to translate that position into the object's private local space (relative position to the object itself). I think you use an inverse matrix for that as inverse matrices work like subtraction when you multiply them. Then I would use that to build an attachment matrix relative to the parent object.

The parent object would have it's matrix to position and orient it. Then I would have the attachment point matrix which is translated to the attachment point in local coordinates. You could even orient it if you want to make it face a different direction or something using this. Then to get the attached object's position and orientation, I would multiply/combine the parent matrix and the attachment matrix to give a world matrix for the attached object in world space.

Anyway, hope that helps as it's basically an educated guess. As I said, I've done some similar things before, but it's been awhile and not in OGL.

BBeck1
09-28-2016, 07:27 AM
Just to reiterate: you multiply matrices together to combine them, which is like addition. You multiply a matrix times an inverse matrix in order to uncombine them, which is like subtraction. I think I cover that in my matrix video briefly. A * B = C and A * Inverse(C) = B

I find this to be un-intuitive, but that's just how matrices are. Once you get it, it's just kind of par for the course.

But the real reason I'm continuing here is that I just realized one way you might determine which sides of the box are visible, even with an OBB. If you do the vector cross product on every side you should be able to get a face normal for every face of the box. Those that face 90 degrees or more away from the direction of the ray being cast cannot possible "face", or be visible, from the vantage point of the ray.

Lot's of math here. Maybe there's a more efficient way, but this should work. And for some of this stuff, you just have to do the math and there isn't a way to reduce it further. On this though, I'm kind of "winging it" here and "shooting from the hip" with this answer. So, it would not surprise me at all if there are some ways to do this more efficiently. Until then though, this should get you there.

BBeck1
09-28-2016, 07:51 AM
Oh, it also occurs to me that you can further simplify this problem because we are dealing with cubes. Assuming the visual cube is axis aligned, that is aligned with it's world matrix (which is not necessarily the case), we can use the cube's world matrix to get all of the vectors to describe all of the face planes. The direction is just the forward, right, and up vectors from the cube's matrix. You can multiply by -1 to get the opposite vectors for the other 3 faces. Half the cube width (it's radius?) is the offset distance from the center to the point on the plane. Viola, you have the 6 planes of the cube.

Also, since these are infinite planes it is possible that the ray intersects with all of the planes of the faces that are facing the ray since those infinite planes overlap.

I think it's impossible for the ray to "actually" intersect more than one cube face that is facing the ray (and one that is facing away). Maybe the angles between the vectors can tell you which one of the possible 3 it is? Otherwise, you would have to test the distance of the point of intersection with the size of the face to see if the point of intersection on the plane is actually inside the face or outside of the face.

Silence
09-29-2016, 01:37 AM
Try this (https://en.wikipedia.org/wiki/M%C3%B6ller%E2%80%93Trumbore_intersection_algorith m). You'll just have to adapt a bit. What is returned is the parameter in the parametric equation of a directed line (O+t*V).

hashbrown
09-29-2016, 12:14 PM
Wow I thought this question was going to remain on 0 replies. Thank you Beck and Silence. I actually just figured it out here at work during lunch, I didn't know you guys replied. My solution is simple, it won't work for moving objects, but if it's stationary, it will. In my case this will do (for now). I'll use a wall and c4 as an example.

Check out the intersection test I shared on the opening post. I pass in the ray origin and dir..and I figured that should be enough information to place my c4 where I need it. So I started at the origin, added the dir and multiplied by the calculated distance.

hitpoint.x = origin.x + dir.x * distance;
hitpoint.y = origin.y + dir.y * distance;
hitpoint.z = origin.z + dir.z * distance;

That's it. The c4 ends up exactly at the point of contact, only that half of the c4 is inside the wall...so I guess I need to give the c4 an offset by half the its own size. I'll have to wait until getting home (lunch over). I will read both of your solutions, since at some point, it would be nice to make it work with moving objects. Nonetheless I have a solution in mind I'd like to try.