Möller-Trumbore算法-射线三角形相交算法

Möller-Trumbore算法，也被称为射线三角形相交算法（ray-triangle intersection algorithm），是一种用来计算射线和三维空间中三角形相交点的经典算法。它的优点在于计算速度快、存储空间少以及鲁棒性强。这个算法利用向量和矩阵计算的方式来快速得出交点和重心坐标，而无需预计算包含三角形的平面方程。Möller-Trumbore算法通常被应用于计算机图形学中，尤其是涉及到三角形网格的光线跟踪计算。该算法的名字是以发明者Tomas Möller和Ben Trumbore的名字来命名的。

相关问题

破片射线与三角形面元相交算法

破片射线与三角形面元相交算法中，存在一种直接判断的方法，即Möller–Trumbore算法(M-T算法)[1][2。M-T算法通过射线与三角形的相交检测来确定破片射线是否与三角形面元相交。这个算法利用了射线与平面的相交检测以及射线和三角形的相交检测。

具体来说，M-T算法使用了克莱姆法则和三矢量的混合积来判断射线和三角形的相交情况。通过计算射线与三角形的相交点，可以确定是否存在相交。该算法相比传统的求解方法更直接、更快速，并且适用于各种场景。

因此，使用Möller–Trumbore算法可以有效地判断破片射线与三角形面元是否相交。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* [【收藏好文】一文读懂射线与三角形相交算法Moller-Trumbore算法](https://blog.csdn.net/oakchina/article/details/124385464)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *3* [空间射线与三角形相交算法的两种实现](https://blog.csdn.net/charlee44/article/details/104348131)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]

opengl射线与面片相交

### OpenGL 中实现射线与面片相交检测

在OpenGL环境中，为了实现实时交互中的物体选取功能，通常会使用射线拾取技术。当用户点击屏幕某一点时，系统需确定该点对应场景中的哪个对象或其具体位置。

#### 原理概述

鼠标点击事件提供了屏幕坐标(x, y)，而要判断哪一部分几何体被选中，则需要构建一条从摄像机出发穿过视口内指定坐标的直线（即射线），再测试这条射线是否与其他任何三维空间内的图元发生碰撞[^4]。

#### 构建射线

对于给定的窗口坐标$(x,y)$，可以通过逆向追踪的方式获得相应的方向矢量$\vec{d}$：

1. **获取近裁剪面上的位置**：利用`gluUnProject()`函数将屏幕坐标转换成标准化设备坐标(NDC)，进而得到位于近平面处的一点$P_{near}=(x',y',z')$；
2. **计算远裁剪面上的位置**：同样地，在远处平面上找到另一点$P_{far}= (x'',y'',z'')$；
3. **形成射线的方向向量**：由上述两点可得$\vec{d}=\frac{(P_{far}- P_{near})}{|P_{far}- P_{near}|}$；

// C++ code snippet to create a ray from screen coordinates.
void getRayFromScreen(int x, int y, float &ox, float &oy, float &oz,
                      float &dx, float &dy, float &dz){
    GLint viewport[4];
    GLdouble modelview[16], projection[16];
    GLfloat winX, winY;
    
    glGetIntegerv(GL_VIEWPORT, viewport);
    glGetDoublev(GL_MODELVIEW_MATRIX, modelview);
    glGetDoublev(GL_PROJECTION_MATRIX, projection);

    winX = static_cast<float>(x); // Convert mouse position into NDC space
    winY = static_cast<float>(viewport[3]) - static_cast<float>(y);

    GLdouble wxNear, wyNear, wzNear;  // Near plane intersection point
    gluUnProject(winX, winY, 0.0f, modelview, projection, viewport,
                 &wxNear, &wyNear, &wzNear);

    GLdouble wxFar, wyFar, wzFar;     // Far plane intersection point
    gluUnProject(winX, winY, 1.0f, modelview, projection, viewport,
                 &wxFar, &wyFar, &wzFar);

    ox = wxNear; oy = wyNear; oz = wzNear;

    dx = wxFar-wxNear; dy=wyFar-wyNear; dz=wzFar-wzNear;
}

#### 测试射线与三角形相交

一旦拥有了完整的射线定义($O,\vec d$),就可以针对每一个绘制出来的三角形执行相交测试。常用的一种高效算法称为Möller–Trumbore算法，它能够快速判定光线是否会击穿某个特定的三角形，并返回确切的距离参数$t$:

$$t=\frac{\left(\mathbf v_2-\mathbf p\right)\times \left( \mathbf e_1\times (\mathbf r_o+\mathbf t_r_d )\right)} {\|\mathbf e_1\times \mathbf e_2 \| } $$

其中，
- $\mathbf {e}_i$: 边缘边(i=1,2),
- $r_o,r_d$: 射源起点和单位化后的方向向量,
- $(p,v_i)$: 组成目标三角形三个顶点之一及其邻接节点.

如果所得值满足条件$0<t<∞$,则说明确实存在有效交点[^3].

bool intersectTriangle(const Vec3& orig, const Vec3& dir,
                       const Triangle& tri, double* out_t) {
    auto edge1 = tri.v1 - tri.v0;
    auto edge2 = tri.v2 - tri.v0;
    auto h = cross(dir, edge2);
    auto a = dot(edge1, h);

    if (fabs(a) < EPSILON)
        return false;

    auto f = 1 / a;
    auto s = orig - tri.v0;
    auto u = f * dot(s, h);

    if (u < 0 || u > 1)
        return false;

    auto q = cross(s, edge1);
    auto v = f * dot(dir, q);

    if (v < 0 || u + v > 1)
        return false;

    *out_t = f * dot(edge2, q);
    return (*out_t >= 0 && *out_t <= INFINITY);
}