Check ofRay intersection with a ofMeshFace

Pretty self explanatory. I’ve tried many examples of code here, but I couldn’t get one to work.

I have an ofRay (from ofxRay), and a list of of3dPrimitive. I am trying to figure out if the ray intersects a primitive, and if so, to know which primitive the ray intersected with “first” (as in, which one is the closest to the screen).

ofVec3f screenToWorld = camera.screenToWorld(ofVec3f(x, y, 0.0));

std::list<primitive>::iterator iterator;

ofRay ray(camera.getPosition(), screenToWorld - camera.getPosition(), true);

for (iterator = primitives.begin(); iterator != primitives.end(); ++iterator)
{
    if (!shiftHeld)
    {
       iterator->setSelected(false);
    }

    float* distance = 0;

    bool found = iterator->FindIntersection(ray, distance);
}

And my findIntersection looks like this:

bool primitive::calcTriangleIntersection(ofRay ray, float *result) const {

    ofMesh mesh = prim->getMesh();
    std::vector<ofMeshFace> indices = mesh.getUniqueFaces();

    for (std::vector<ofMeshFace>::iterator i = indices.begin(); i != indices.end(); ++i)
    {
        ofMeshFace face = *i;

        // Detection here

        if (detected intersection)
        {
            *result = distance;
            return true;
        }
    }
    return false;
}

I’ve tried so many things, but none of them works. I’m also drawing my rays to the screen, so I know for a fact that they are indeed created correctly and go in the right direction for an infinite distance

Just to be clear, I removed a lot of the code to make this easily readable. I’m only missing the
// Detection Here
part in the second method, because I have no idea how to make it work.

This should be

float distance = 0.0f;
bool found = iterator->FindIntersection(ray, &distance);

The distance has to be allocated, so when you do [quote=“Kaito_Kid, post:1, topic:26101”]
if (detected intersection)
{
*result = distance;
return true;
}
[/quote]

*result pointer dereference can work.

What is it in your code that does not work? The ray - face intersection?

I can change that part if its a standard or something, but what doesn’t work is really detecting the intersection. No matter what code I try, be it from mathematical formulas or from a code snippet found on this forum, I always either get a ton of false positives or a ton of false negatives, and never get an even remotely accurate boolean telling me if there was an intersection.

Well… you have to help me out here… try to reduce your problem to a working minimum, and if it still does not work then post the new specific problem.

I would recommend starting with a ray (0,0,0) -> (0,0,-1) intersecting with a known triangle, in the x,y plane, placed in a -z coord that you are sure the ray is intersecting. Check that the algorithm works and work up from there.

This attempt was created using this algorithm: http://geomalgorithms.com/a06-_intersect-2.html#intersect3D_RayTriangle()

I can see, from drawing my primitive to the screen as a wireframe, and the ray, that the ray truly goes inside the primitive (which is an ofBoxPrimitive in that case). Yet, the function always returns false.

My modifications to the algorithm basically apply that algorithm to all the faces (triangles) of the primitive (this is because in the future, this will have to work for any 3d object), and applying the algorithm to all the primitives. It should return true as soon as it find a face that intersects with the ray, and return false otherwise.

bool primitive::checkIntersectionTriangleRay(ofRay ray, ofPoint* inter)
{
	ofMesh mesh = prim->getMesh();
	std::vector<ofMeshFace> indices = mesh.getUniqueFaces();

	for (std::vector<ofMeshFace>::iterator i = indices.begin(); i != indices.end(); ++i)
	{
		ofMeshFace triangle = *i;

		ofVec3f   u, v, n;              // triangle vectors
		ofVec3f   dir, w0, w;           // ray vectors
		float     r, a, b;              // params to calc ray-plane intersect

										// get triangle edge vectors and plane normal
		u = triangle.getVertex(1) - triangle.getVertex(0);
		v = triangle.getVertex(2) - triangle.getVertex(0);
		n = u * v;              // cross product
		if (!(n == ofVec3f(0, 0, 0)))           // if triangle is not degenerate
		{

			dir = ray.getEnd() - ray.getStart();              // ray direction vector
			w0 = ray.getStart() - triangle.getVertex(0);
			a = -dot(n, w0);
			b = dot(n, dir);
			if (!(fabs(b) < SMALL_NUM))
			{     // if ray is not parallel to triangle

				// get intersect point of ray with triangle plane
				r = a / b;
				if (!(r < 0.0))                    // ray goes toward the triangle
				{
					// for a segment, also test if (r > 1.0) => no intersect

					*inter = ray.getStart() + r * dir;            // intersect point of ray and plane

													// is I inside T?
					float    uu, uv, vv, wu, wv, D;
					uu = dot(u, u);
					uv = dot(u, v);
					vv = dot(v, v);
					w = *inter - triangle.getVertex(0);
					wu = dot(w, u);
					wv = dot(w, v);
					D = uv * uv - uu * vv;

					// get and test parametric coords
					float s, t;
					s = (uv * wv - vv * wu) / D;
					if (!(s < 0.0 || s > 1.0))         // I is inside T
					{
						t = (uv * wu - uu * wv) / D;
						if (!(t < 0.0 || (s + t) > 1.0))  // I is inside T
							return true;                       // I is in T
					}
				}
			}
		}
	}
	return false;
}

I have also tried a couple other methods, including sachaamm’s answer here: Is there a library for detecting mouse over 3d objects?

This one also gives me false every single time. Both algorithms are similar in process, so the problem is probably the same one.

Do you know where the algorithm decides that the ray does not hit the triangle? Did you try debugging the code? Check all if conditions that discard the ray, and make sure it is a correct discard. If its not, then you’ve found your bug.

Check:
if (!(n == ofVec3f(0, 0, 0))) // if triangle is not degenerate
if (!(fabs(b) < SMALL_NUM))
if (!(r < 0.0)) // ray goes toward the triangle
if (!(s < 0.0 || s > 1.0)) // I is inside T
if (!(t < 0.0 || (s + t) > 1.0)) // I is inside T

Wild guess is that the normals are the source of the problem.