射线相交检测

Introduction

我们可以将也给射线写成:$R = O + Dt$，其中，$O$为射线的起始点，$D$为射线的方向。同时我们可以利用重心坐标公式，将一个三角面片上的点，用其三个角的坐标所表示：$P_t = (1-u-v)V_0 + uV_1 + vV_2$

bari

基于以上公式，我们可以将求射线与面片的交点坐标，转换为求解：

$O+Dt = (1-u-v)V_0 + uV_1 + vV_2 \tag{1}$

整理公式（1）我们可以得到：

$\begin{bmatrix} v_1 - v_0 \\ v_2 - v_0 \\ -D \end{bmatrix}^T \begin{bmatrix} u \\ v \\ t\end{bmatrix} = \begin{bmatrix} O- V_0\end{bmatrix}^T \tag{2}$

我们也可以参考引用[1]，通过克莱姆法则来继续化简公式减少计算量。但由于我的项目是在数据预处理阶段来进行此过程，就没考虑性能问题。

Code

具体代码如下：

%matplotlib notebook
from mpl_toolkits.mplot3d import axes3d
import matplotlib.pyplot as plt
import numpy as np

# 判断是否相交
def isCross(tri, ray, isPlot=False):
    '''
        tir: 3*3代表三角面片
        ray: 2*3代表射线
    '''
    v0 = tri[0]
    v1 = tri[1]
    v2 = tri[2]
    o = ray[0]
    d = ray[1]
    hasCrossPoint = True
    A = np.stack(((v1-v0).T, (v2- v0).T, (-d).T), axis=1)
    detA = np.linalg.det(A)
    b = (o - v0).T
    
    if detA < 0:
        b = -1 * b
        detA = -detA
    
    if detA < 1e-5:
        print('平行，不相交\n')
        hasCrossPoint = False
       
    x = np.linalg.solve(A, b)
    
    if x[0] < 1e-5 or (x[0] + x[1]) > 1:
        print('无相交点\n')
        hasCrossPoint = False

    if hasCrossPoint:
        crossP = np.around((1-x[0]-x[1]) * v0 + x[0]*v1 + x[1] * v2)
        print('相交点为：[{},{},{}]\n'.format(crossP[0],crossP[1],crossP[2]))    
    if isPlot:
        # 打开画图窗口1，在三维空间中绘图
        fig = plt.figure(1)
        ax = fig.gca(projection='3d')

        # 将数组中的前两个点进行连线
        figure = ax.plot(ray[:, 0], ray[:, 1], ray[:, 2], c='r', zorder=1)

        # 画出三角面片
        ax.plot_trisurf(tri[:,0], tri[:,1], tri[:,2], linewidth=0.2, antialiased=True, zorder=2)
        
        # 画出相交点
        if hasCrossPoint:
            crossP1 = np.expand_dims(crossP, axis=0)
            ax.plot(crossP1[:,0], crossP1[:,1], crossP1[:,2], 'o', color='tab:brown' ,markersize=10)   
        plt.show()
    return

o = np.array([0, 0, 0])
d = np.array([150, 260, 450])
d2 = np.array([30, 100, 300])

ray = np.stack((o, d), axis=0)
ray2 = np.stack((o, d2), axis=0)

v0 = np.array([30, 80, 60])
v1 = np.array([100, 70, 80])
v2 = np.array([70, 120, 400])

tri = np.stack((v0, v1, v2), axis=0)
isCross(tri, ray, True) # 相交点为：[51.0,89.0,154.0]
isCross(tri, ray2, True) # 无相交点

ray的效果图

ray2的效果图

参考

[1]、射线和三角形的相交检测-C++实现