我看到经常推荐 Moller 和 Trumbore 的Fast Minimum Storage Ray/Triangle Intersection 。
问题是，我不介意预先计算和存储任何数量的数据，只要它可以加快交叉路口的速度。
所以我的问题是，不关心内存，进行射线三角形相交的最快方法是什么？
编辑：我不会移动三角形，即它是一个静态场景。
问问题
20829 次
4 回答
10
正如其他人所提到的，加快速度的最有效方法是使用加速结构来减少所需的射线三角形交叉点的数量。也就是说，您仍然希望您的射线三角形相交速度快。如果您乐于预先计算内容，可以尝试以下方法：
将您的射线线和三角形边缘转换为Plücker 坐标。这使您可以确定您的射线线是否以每条边 6 次乘法/加法通过三角形。您仍然需要将您的光线起点和终点与三角形平面（每点 4 个乘法/加法）进行比较，以确保它实际上击中了三角形。
最坏情况下的运行时间开销是 26 次乘法/加法的总和。另外，请注意，您只需为每个光线/边缘组合计算一次光线/边缘符号，因此如果您正在评估网格，您可以使用每个边缘评估两次。
此外，这些数字假设一切都是在齐次坐标中完成的。您可以通过提前对事物进行规范化来减少乘法的数量。
于 2012-10-31T21:35:26.290 回答
8
我已经做了很多基准测试，我可以自信地说，最快（已发布）的方法是 Havel 和 Herout 发明并在他们的论文Yet Faster Ray-Triangle Intersection (Using 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;
}
于 2017-06-30T02:33:04.903 回答
3
一个建议可能是实施八叉树 (http://en.wikipedia.org/wiki/Octree) 算法将您的 3D 空间划分为非常精细的块。分区越精细，所需的内存就越多，但树的准确性就越高。
您仍然需要检查射线/三角形的交点，但想法是树可以告诉您何时可以跳过射线/三角形的交点，因为保证射线不会击中三角形。
但是，如果您开始四处移动三角形，则需要更新八叉树，然后我不确定它是否会为您节省任何东西。
于 2012-10-31T17:13:10.773 回答
2
找到丹星期天的这篇文章：
根据直到第一次拒绝测试完成的操作计数，该算法的效率比 MT（Möller & Trumbore）算法略低，[...]。然而，MT 算法使用两个叉积，而我们的算法只使用一个叉积，而我们使用的那个计算三角形平面的法线向量，这是计算线参数rI所必需的。但是，当已经为场景中的所有三角形预先计算并存储了法线向量时（通常是这种情况），我们的算法根本不需要计算这个叉积。但是，在这种情况下，MT 算法仍然会计算两个叉积，并且效率低于我们的算法。
于 2014-11-01T02:05:19.570 回答