23

I saw that Fast Minimum Storage Ray/Triangle Intersection by Moller and Trumbore is frequently recommended.

The thing is, I don't mind pre-computing and storing any amounts of data, as long as it speeds-up the intersection.

So my question is, not caring about memory, what are the fastest methods of doing ray-triangle intersection?

Edit: I wont move the triangles, i.e. it is a static scene.

2
  • I used the Fast Minimum Storage Ray/Triangle Intersecton by Moller and Trumbore a lot. But it is the first time I know the paper. I think for lots of rays and triangles, apart from space partition techniques, parallel method can be considered at the same time. I'm doing an OpenCL implementation, but I don not know if someone have already do that. Have you heard something about that?
    – squid
    Oct 22, 2014 at 15:26
  • @squid You could try to look at LuxRender's LuxRays here
    – Ecir Hana
    Oct 22, 2014 at 15:40

4 Answers 4

11

As others have mentioned, the most effective way to speed things up is to use an acceleration structure to reduce the number of ray-triangle intersections needed. That said, you still want your ray-triangle intersections to be fast. If you're happy to precompute stuff, you can try the following:

Convert your ray lines and your triangle edges to Plücker coordinates. This allows you to determine if your ray line passes through a triangle at 6 multiply/add's per edge. You will still need to compare your ray start and end points with the triangle plane (at 4 multiply/add's per point) to make sure it actually hits the triangle.

Worst case runtime expense is 26 multiply/add's total. Also, note that you only need to compute the ray/edge sign once per ray/edge combination, so if you're evaluating a mesh, you may be able to use each edge evaluation twice.

Also, these numbers assume everything is being done in homogeneous coordinates. You may be able to reduce the number of multiplications some by normalizing things ahead of time.

2
  • Thank you. By any change, don't you know where a sample code lives? Btw., which acceleration structure do you recommend and why?
    – Ecir Hana
    Nov 1, 2012 at 8:59
  • 2
    A few years ago, the state of the art used highly-optimized k-d trees. Especially for a static scene, this may be your best bet. Re sample code, I found something relevant with Google. No guarantees -- the paper seems oldish, but its explanations seem clear enough, and its benchmarks attribute a significant edge to the Plücker code. Nov 1, 2012 at 20:54
10

I have done a lot of benchmarks, and I can confidently say that the fastest (published) method is the one invented by Havel and Herout and presented in their paper Yet Faster Ray-Triangle Intersection (Using SSE4). Even without using SSE it is about twice as fast as Möller and Trumbore's algorithm.

My C implementation of Havel-Herout:

    typedef struct {
        vec3 n0; float d0;
        vec3 n1; float d1;
        vec3 n2; float d2;
    } isect_hh_data;

    void
    isect_hh_pre(vec3 v0, vec3 v1, vec3 v2, isect_hh_data *D) {
        vec3 e1 = v3_sub(v1, v0);
        vec3 e2 = v3_sub(v2, v0);
        D->n0 = v3_cross(e1, e2);
        D->d0 = v3_dot(D->n0, v0);

        float inv_denom = 1 / v3_dot(D->n0, D->n0);

        D->n1 = v3_scale(v3_cross(e2, D->n0), inv_denom);
        D->d1 = -v3_dot(D->n1, v0);

        D->n2 = v3_scale(v3_cross(D->n0, e1), inv_denom);
        D->d2 = -v3_dot(D->n2, v0);
    }

    inline bool
    isect_hh(vec3 o, vec3 d, float *t, vec2 *uv, isect_hh_data *D) {
        float det = v3_dot(D->n0, d);
        float dett = D->d0 - v3_dot(o, D->n0);
        vec3 wr = v3_add(v3_scale(o, det), v3_scale(d, dett));
        uv->x = v3_dot(wr, D->n1) + det * D->d1;
        uv->y = v3_dot(wr, D->n2) + det * D->d2;
        float tmpdet0 = det - uv->x - uv->y;
        int pdet0 = ((int_or_float)tmpdet0).i;
        int pdetu = ((int_or_float)uv->x).i;
        int pdetv = ((int_or_float)uv->y).i;
        pdet0 = pdet0 ^ pdetu;
        pdet0 = pdet0 | (pdetu ^ pdetv);
        if (pdet0 & 0x80000000)
            return false;
        float rdet = 1 / det;
        uv->x *= rdet;
        uv->y *= rdet;
        *t = dett * rdet;
        return *t >= ISECT_NEAR && *t <= ISECT_FAR;
    }
3
  • Hi, I like the look of this algorithm but I'm a little confused by the parameters here. In "isect_hh_data" do the vec3 n values refer to the vertices of the triangle and the float d values the angle of the ray? What is the purpose of having 2 functions. I see that the first one initialises the struct. Presumably with just a triangle, which is transformed somehow, (and an empty struct)? If so what useful information is stored in the struct between functions. I see "isect_hh" takes this transformed tri and 2 vec3s (presumably the ray) but what are t and uv? Any help wld be greatly appreciated. Jan 16 at 14:04
  • nX refers to the normals of the planes formed by the triangle's vectors and its normals. dX are precomputed dot products. isect_hh_pre precomputes values which are then used in isect_hh to do the intersection check. uv stores the intersection's coordinate and t the signed distance to the intersection. Jan 16 at 14:48
  • ah that makes sense! So essentially the first function will create a precomputed triangle, ready for intersection testing. And then you pair this with a ray. Are the 2 vector parameters for the Ray function origin and vector, or start and end? Also I presume uv is the point on the flat triangle the ray hit. Jan 17 at 0:04
3

One suggestion could be to implement the octree (http://en.wikipedia.org/wiki/Octree) algorithm to partition your 3D Space into very fine blocks. The finer the partitioning the more memory required, but the better accuracy the tree gets.

You still need to check ray/triangle intersections, but the idea is that the tree can tell you when you can skip the ray/triangle intersection, because the ray is guaranteed not to hit the triangle.

However, if you start moving your triangle around, you need to update the Octree, and then I'm not sure it's going to save you anything.

1
  • Thanks! The triangles wont move around. The thing with Octree, and maybe I misunderstand it, is that there may be several triangles in one leaf, right? In that case, I'll still need a fast intersection routine.
    – Ecir Hana
    Oct 31, 2012 at 17:34
2

Found this article by Dan Sunday:

Based on a count of the operations done up to the first rejection test, this algorithm is a bit less efficient than the MT (Möller & Trumbore) algorithm, [...]. However, the MT algorithm uses two cross products whereas our algorithm uses only one, and the one we use computes the normal vector of the triangle's plane, which is needed to compute the line parameter rI. But, when the normal vectors have been precomputed and stored for all triangles in a scene (which is often the case), our algorithm would not have to compute this cross product at all. But, in this case, the MT algorithm would still compute two cross products, and be less efficient than our algorithm.

http://geomalgorithms.com/a06-_intersect-2.html

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.