雷三角交叉口

Question

我看到经常推荐使用Moller和Trumbore的Fast Minimum Storage Ray/Triangle Intersection.

问题是,我不介意预先计算和存储任何数量的数据,只要它加速交叉点.

所以我的问题是,不关心记忆,做射线三角交叉的最快方法是什么？

编辑:我不会移动三角形,即它是一个静态场景.

Answer 1

正如其他人所提到的,加快速度的最有效方法是使用加速结构来减少所需的光线 - 三角形交叉点的数量.也就是说,你仍然希望你的光线三角形交叉点很快.如果您很乐意预先计算内容,可以尝试以下方法:

将光线和三角形边线转换为Plücker坐标.这允许您确定您的光线是否通过每边6乘以/加的三角形.您仍然需要将光线起点和终点与三角形平面进行比较(每个点乘以4乘以/加)以确保它实际上击中三角形.

最坏情况运行时费用是26乘以/加总数.另外,请注意,您只需要为每个光线/边缘组合计算一次光线/边缘符号,因此,如果您正在评估网格,则可以使用两次每个边缘评估.

而且,这些数字假设一切都在齐次坐标中完成.您可以通过提前规范化事物来减少乘法次数.

Answer 2

我已经做了很多基准测试，我可以自信地说，最快（已发布）的方法是Havel和Herout发明的方法，该方法在他们的论文然而更快的射线-三角形交叉口（使用SSE4）中进行了介绍。即使不使用SSE，它的速度也大约是Möller和Trumbore的算法的两倍。

我的Havel-Herout的C实现：

    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;
    }