python - 加快体素化/相交测试

问题描述

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

我有一个船体体素化的工作解决方案，但它非常慢（在我的电脑上需要 10 秒）。它需要大约 1 秒。（具有 8 级深八叉树的总实体体素化大约需要 2 秒）

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

仅计算所有 100,000 个三角形的边界框就需要大约 0.800 秒。那是很长的路。我正在使用 PyCharm 中的“标准”Python 3。如果我没记错的话，我认为它是 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 / Octree 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 行不同变量的代码在 300 毫秒内运行，这一位需要 4 秒以上的 100,000 次重复。

有什么新建议吗？

标签： pythonoptimizationbounding-boxtriangulationvoxel

python - 加快体素化/相交测试

问题描述

解决方案

推荐阅读