Sign in to follow this  
mind in a box

Ray/Line intersection in 3D

Recommended Posts

mind in a box    887
I found an enormous number of threads discussing how to do this in 2D, but none of them seemed to have a nice solution for the 3rd dimension.

What I would like to do is to get the intersection between a ray and a line. Why?
In my engine's editor you need to be able to select meshes, even when you are in wireframe mode (Like when you have multiple viewports open).
And in wireframe mode you can't just intersect the triangles of a mesh, this would give pretty confusing results.

It is also important that I can specify a fake-width of the line, because 1px space for clicking something isn't much! [grin]

My idea of how to do this is to have a plane instead of the line (In shape of a line, though), rotated to face the direction of the camera.
Only problem with this: I'm not very good at such vector math and have no idea of how to figure out the planes coordinates.

Would be great if someone could help me out.

Share this post


Link to post
Share on other sites
Darg    213
One option would be to render the wireframe to an image, rendering each line with the required thickness and its object ID as the colour. Once done it would simply be a matter of checking which colour is underneath the current mouse location.

This image would only have to be rendered when the user tries to select an object.

Share this post


Link to post
Share on other sites
taz0010    277
The problem you're trying to solve is to calculate the distance between a ray and a line segment. When the ray approaches closer than some chosen value, you regard the line segment as hit.
I did exactly this in my editor using the information on the website below:

http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm

They describe infinite line to infinite line distances, and segment to segment distances, but don't provide an implementation of the ray to line segment test. I created my own by making a few modifications to their code. Here it is:


float Intersection::rayToLineSegment(RAY_TO_LINE_SEGMENT& info,const Vec3& rayOrigin,const Vec3& rayVec,const Vec3& lineStart,const Vec3& lineEnd){
Vec3 u = rayVec;
Vec3 v = lineEnd - lineStart;
Vec3 w = rayOrigin - lineStart;
float a = u.dot(u); // always >= 0
float b = u.dot(v);
float c = v.dot(v); // always >= 0
float d = u.dot(w);
float e = v.dot(w);
float D = a*c - b*b; // always >= 0
float sc, sN, sD = D; // sc = sN / sD, default sD = D >= 0
float tc, tN, tD = D; // tc = tN / tD, default tD = D >= 0

// compute the line parameters of the two closest points
if (D < epsilon) { // the lines are almost parallel
sN = 0.0; // force using point P0 on segment S1
sD = 1.0; // to prevent possible division by 0.0 later
tN = e;
tD = c;
}
else { // get the closest points on the infinite lines
sN = (b*e - c*d);
tN = (a*e - b*d);
if (sN < 0.0) { // sc < 0 => the s=0 edge is visible
sN = 0.0;
tN = e;
tD = c;
}
}

if (tN < 0.0) { // tc < 0 => the t=0 edge is visible
tN = 0.0;
// recompute sc for this edge
if (-d < 0.0)
sN = 0.0;
else {
sN = -d;
sD = a;
}
}
else if (tN > tD) { // tc > 1 => the t=1 edge is visible
tN = tD;
// recompute sc for this edge
if ((-d + b) < 0.0)
sN = 0;
else {
sN = (-d + b);
sD = a;
}
}
// finally do the division to get sc and tc
sc = (abs(sN) < epsilon ? 0.0f : sN / sD);
tc = (abs(tN) < epsilon ? 0.0f : tN / tD);

// get the difference of the two closest points
Vec3 dP = w + (sc * u) - (tc * v); // = S1(sc) - S2(tc)
info.iFracRay = sc;
info.iFracLine = tc;
return dP.length(); // return the closest distance
}

Share this post


Link to post
Share on other sites
andur    781
You could just do a normal ray-triangle intersection and calculate how far away from each of the edges the click is. If its too far from the edges, then just pass the ray through and don't count that as an intersection. This would also let you easily give the user the option of whether or not they want their mouse-clicks to be able to pass through the wireframe geometry (I personally wouldn't want/expect that to happen).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this