4
\$\begingroup\$

I wonder if someone is familiar with ray/triangle intersection algorithms and can help me optimize them?

Here are my implementations of two ray/triangle intersection algorithms in C. The first is the well-known Möller-Trombore algorithm:

inline bool
isect_mt_b(vec3 o, vec3 d,
           vec3 v0, vec3 v1, vec3 v2,
           float *t, vec2  *uv) {

    vec3 e1 = v3_sub(v1, v0);
    vec3 e2 = v3_sub(v2, v0);
    vec3 pvec = v3_cross(d, e2);
    vec3 tvec = v3_sub(o, v0);
    vec3 qvec;
    uv->x = v3_dot(tvec, pvec);
    float det = v3_dot(e1, pvec);
    if (det > 0) {
        if (uv->x < 0 || uv->x > det)
            return false;
        qvec = v3_cross(tvec, e1);
        uv->y = v3_dot(d, qvec);
        if (uv->y < 0 || uv->x + uv->y > det)
            return false;
    } else if (det < 0) {
        if (uv->x > 0 || uv->x < det)
            return false;
        qvec = v3_cross(tvec, e1);
        uv->y = v3_dot(d, qvec);
        if (uv->y > 0 || uv->x + uv->y < det)
            return false;
    } else {
        return false;
    }
    float inv_det = 1 / det;
    *t = v3_dot(e2, qvec) * inv_det;
    uv->x *= inv_det;
    uv->y *= inv_det;
    return *t >= ISECT_NEAR && *t <= ISECT_FAR;
}

I'm not pasting the source for v3_cross, v3_dot and friends. They are all declared using the inline keyword for maximum performance. It should be obvious what they do if you know that they operate on a vec3 struct containing three float fields; x, y and z. The second less known one is Segura-Feita algorithm:

inline float
v3_sign_3d(vec3 p, vec3 q, vec3 r) {
    return v3_dot(p, v3_cross(q, r));
}
inline bool
isect_sf01(vec3 o, vec3 d,
           vec3 v0, vec3 v1, vec3 v2,
           float *t, vec2  *uv) {
    vec3 v0o = v3_sub(v0, o);
    vec3 v1o = v3_sub(v1, o);
    vec3 v2o = v3_sub(v2, o);
    float w2 = v3_sign_3d(d, v1o, v0o);
    float w0 = v3_sign_3d(d, v2o, v1o);
    bool s2 = w2 >= 0.0f;
    bool s0 = w0 >= 0.0f;
    if (s2 != s0)
        return false;
    float w1 = v3_sign_3d(d, v0o, v2o);
    bool s1 = w1 >= 0.0f;
    if (s2 != s1)
        return false;
    uv->x = w1 / (w0 + w1 + w2);
    uv->y = w2 / (w0 + w1 + w2);
    vec3 v0v1 = v3_sub(v1, v0);
    vec3 v0v2 = v3_sub(v2, v0);
    vec3 n = v3_cross(v0v1, v0v2);
    *t = v3_dot(n, v0o) / v3_dot(n, d);
    return *t >= ISECT_NEAR && *t <= ISECT_FAR;
}

It is described in this paper and my sample code comes from this webpage.

Any performance tips are greatly appreciated. :)

\$\endgroup\$
  • 3
    \$\begingroup\$ My best performance tip is: performance tips other than this one are mostly worthless. Have a performance goal. Measure your performance under lab conditions and use a profiler to discover the slowest thing. Use that to guide your optimizations. Once you've reached your goal, find some other way to spend your valuable time. \$\endgroup\$ – Eric Lippert Jun 6 '17 at 23:08
  • \$\begingroup\$ Möller & Trombore give a reference C implementation in their paper, which has (i) explanatory comments; and (ii) avoids duplication of code between the det > LINALG_EPSILON and det < -LINALG_EPSILON branches. \$\endgroup\$ – Gareth Rees Jun 17 '17 at 15:09
  • \$\begingroup\$ That is correct. But now how their code performs a division in the beginning of the flow, while my code only does it in the end. \$\endgroup\$ – Björn Lindqvist Jun 17 '17 at 17:50
  • \$\begingroup\$ I suspect if (det > 0) { baa() } else if (det < 0) { ram() } else { ewe() } can be replaced with if (signbit(det)) { baa2() } else { ram2() }. \$\endgroup\$ – chux Jul 12 '17 at 3:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.