python - 使用 numpy/scipy 将 3D 点的最近点投影到 3D 三角形

Question

如何使用 numpy/scipy 计算一个点到 N 个三角形的最近投影？

现在我将创建一个函数来计算单个三角形的投影，basically this ，然后迭代整个三角形数组。但在我开始这样做之前，我想知道 scipy 中是否已经有一个内置的解决方案。像这样的东西:

# DREAMY PSEUDOCODE
import numpy as np
N_TRIANGLES = 1000

point = np.random.rand(3) * 100 #random 3d point
triangles = np.random.rand(N_TRIANGLES,3,3) * 100 #array of triangles

from scipy.spatial import pointToTriangles
projections = pointToTriangles(point,triangles)

这是一张可以帮助您形象化的图片:

在上图中，中间的红点是我的查询“点”，蓝点是“三角形”np.array() 中定义的每个三角形的顶点。绿点代表我想要的结果。它们是“点”在定义的三角形上最接近的投影，我希望将此信息作为点数组返回。

干杯!

Answer 1

这是我想出的代码。我在 scipy 中找不到任何可以直接帮助我的东西，这个解决方案比查询 CGAL 快大约 2 倍。它不处理折叠的三角形，但可以通过检查边长度并返回最长边上最近的点来解决这个问题。

import numpy as np

def pointsToTriangles(points,triangles):
    
    with np.errstate(all='ignore'):
        
        # Unpack triangle points
        p0,p1,p2 = np.asarray(triangles).swapaxes(0,1)
                
        # Calculate triangle edges
        e0 = p1-p0
        e1 = p2-p0
        a = np.einsum('...i,...i', e0, e0)
        b = np.einsum('...i,...i', e0, e1)
        c = np.einsum('...i,...i', e1, e1)
        
        # Calculate determinant and denominator
        det = a*c - b*b
        invDet = 1. / det
        denom = a-2*b+c
        
        # Project to the edges
        p  = p0-points[:,np.newaxis]
        d = np.einsum('...i,...i', e0, p)
        e = np.einsum('...i,...i', e1, p)
        u = b*e - c*d
        v = b*d - a*e
        
        # Calculate numerators
        bd = b+d
        ce = c+e
        numer0 = (ce - bd) / denom
        numer1 = (c+e-b-d) / denom
        da = -d/a
        ec = -e/c
        
        
        # Vectorize test conditions
        m0 = u + v < det
        m1 = u < 0
        m2 = v < 0
        m3 = d < 0
        m4 = (a+d > b+e)
        m5 = ce > bd
        
        t0 =  m0 &  m1 &  m2 &  m3
        t1 =  m0 &  m1 &  m2 & ~m3
        t2 =  m0 &  m1 & ~m2
        t3 =  m0 & ~m1 &  m2
        t4 =  m0 & ~m1 & ~m2
        t5 = ~m0 &  m1 &  m5
        t6 = ~m0 &  m1 & ~m5
        t7 = ~m0 &  m2 &  m4
        t8 = ~m0 &  m2 & ~m4
        t9 = ~m0 & ~m1 & ~m2
        
        u = np.where(t0, np.clip(da, 0, 1), u)
        v = np.where(t0, 0, v)
        u = np.where(t1, 0, u)
        v = np.where(t1, 0, v)
        u = np.where(t2, 0, u)
        v = np.where(t2, np.clip(ec, 0, 1), v)
        u = np.where(t3, np.clip(da, 0, 1), u)
        v = np.where(t3, 0, v)
        u *= np.where(t4, invDet, 1)
        v *= np.where(t4, invDet, 1)
        u = np.where(t5, np.clip(numer0, 0, 1), u)
        v = np.where(t5, 1 - u, v)
        u = np.where(t6, 0, u)
        v = np.where(t6, 1, v)
        u = np.where(t7, np.clip(numer1, 0, 1), u)
        v = np.where(t7, 1-u, v)
        u = np.where(t8, 1, u)
        v = np.where(t8, 0, v)
        u = np.where(t9, np.clip(numer1, 0, 1), u)
        v = np.where(t9, 1-u, v)
        
        
        # Return closest points
        return (p0.T +  u[:, np.newaxis] * e0.T + v[:, np.newaxis] * e1.T).swapaxes(2,1)

    

一些测试数据将 100 个点投影到 10k 个三角形:

    import numpy as np
    import cProfile
    
    N_TRIANGLES = 10**4 # 10k triangles
    N_POINTS    = 10**2 # 100 points
    points      = np.random.random((N_POINTS,3,)) * 100
    triangles   = np.random.random((N_TRIANGLES,3,3,)) * 100
    
    cProfile.run("pointsToTriangles(points,triangles)") # 54 function calls in 0.320 seconds

这很快就会占用大量内存，因此在处理大型数据集时，最好一次迭代一个点或三角形。