加速体素化/交集测试

Question

我目前正在研究基于稀疏八叉树的STL体素化。我有一个包含大约100,000个三角形的文件，每个三角形的格式是-[ Point1 x-Point1，Point1y，Point1z，P2x，P2y，P2z，P3x，P3y，P3z ]。

我有一个有效的解决方案，用于船体的体素化，但它非常非常慢(在我的电脑上10秒)。它需要在1秒左右。(8级深度八叉树的整体立体体素化应该需要大约2秒)

现在我正在解析每个三角形的八叉树。对于交叉点检查，我需要计算100,000个三角形中每个三角形的方向边界框。在解析每个三角形的八叉树之前。

仅计算所有100,000个三角形的边界框就需要0.800秒。这真是太长了。我正在使用PyCharm中的“标准”Python3。如果我没记错的话，我认为这是CPython。

for triangle in triangle_list:
    'this variables represent the x,y,z value of all three vertices of the triangle'
    'in tests this method was found to be superior to the 2D array way '

    P1x = triangle[0][0]
    P1y = triangle[0][1]
    P1z = triangle[0][2]
    P2x = triangle[1][0]
    P2y = triangle[1][1]
    P2z = triangle[1][2]
    P3x = triangle[2][0]
    P3y = triangle[2][1]
    P3z = triangle[2][2]

    'the bounding box for the triangle is determined'
    'i used python integrated min max methods to find the smalles x,y,z value for all of the three vertices'


    bbtrxmin = min(P1x, P2x, P3x)
    bbtrxmax = max(P1x, P2x, P3x)
    bbtrymin = min(P1y, P2y, P3y)
    bbtrymax = max(P1y, P2y, P3y)
    bbtrzmin = min(P1z, P2z, P3z)
    bbtrzmax = max(P1z, P2z, P3z)

因为我是一个全新的编程新手，我不知道我可以改变什么来加速这个过程。我已经搜索了另一个算法，但它并没有太大的变化。

我尝试过的东西：

备选方案A：

P1t=triangle[0]
P2t=triangle[1]
P3t=triangle[2]

bbtrxmin = min(P1t[0], P2t[0], P3t[0])
bbtrxmax = max(P1t[0], P2t[0], P3t[0])
bbtrymin = min(P1t[1], P2t[1], P3t[1])
bbtrymax = max(P1t[1], P2t[1], P3t[1])
bbtrzmin = min(P1t[2], P2t[2], P3t[2])
bbtrzmax = max(P1t[2], P2t[2], P3t[2])

备选方案B：

def maX(a , b):
    if a > b:
        return a
    else: 
        return b

def miN(a , b):
    if a < b:
        return a
    else:
        return b  

P1t=triangle[0]
P2t=triangle[1]
P3t=triangle[2]

bbtrxmin = miN(P1t[0], miN(P2t[0], P3t[0]))
bbtrxmax = maX(P1t[0], maX(P2t[0], P3t[0]))
bbtrymin = miN(P1t[1], miN(P2t[1], P3t[1]))
bbtrymax = maX(P1t[1], maX(P2t[1], P3t[1]))
bbtrzmin = miN(P1t[2], miN(P2t[2], P3t[2]))
bbtrzmax = maX(P1t[2], maX(P2t[2], P3t[2]))

备选方案A稍微慢一些，但没有显着差异。备选B大约是1秒(不包括函数的定义)。此操作的目标最大不应超过0.100秒。

您知道如何加快100,000个三角形的简单3D方向边界框的计算速度吗？我必须使用Python，但我可以改变编译器。

你有什么建议可以加速整个STL /八叉树Voxelization过程吗？也许我甚至不需要检查所有的三角形？我读了很多论文，其中大多数都检查了每个三角形，但如果你有什么好主意，我对此持开放态度。

非常提前感谢您。

编辑17.09.2020：

我现在使用PyPy，因为我希望JIT Comiler能显著提高速度。我做了一些测试，结果很好。所有的东西都运行得更快了，但是瓶颈仍然是下面的代码：

bbtrxmax = max(P1x, P2x, P3x)
bbtrymin = min(P1y, P2y, P3y)
bbtrymax = max(P1y, P2y, P3y)
bbtrzmin = min(P1z, P2z, P3z)
bbtrzmax = max(P1z, P2z, P3z)

要确定边界框，请执行以下操作。其余的代码(大约100行不同变量的代码在300ms内运行，这个比特在100,000次重复中花费了4秒。

有什么新的建议吗？

Answer 1

我不是百分之百肯定我明白你在做什么:你需要每个三角形一个边界框还是所有三角形的整体边界框在一起？看起来像是第一个，但只是检查一下。

有几种可能的方法来解决这个问题：

• 尝试使用NumPy数组，因为min()和.max()操作可以在整个数组切片(一维向量、二维数组等)上工作。当需要原始速度时，
• Numba、Cython和f2py可以是很好的选择:对于Cython，您可能希望混合使用Python和C(或者直接用C编写循环)。F2py封装了fortran模块，看起来在您的情况下编写代码将非常容易。