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\$
4
  • 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\$ Commented Jun 6, 2017 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\$ Commented Jun 17, 2017 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\$ Commented Jun 17, 2017 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\$ Commented Jul 12, 2017 at 3:31

0

Your Answer

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

Browse other questions tagged or ask your own question.