2

我正在编写一些操作 3D 三角形网格的代码。导入网格数据后，我需要“统一”空间中同一点的顶点。

我一直假设 numpy 数组将是存储和操作数据的最快方式，但我似乎无法找到一种快速构建顶点列表同时避免添加重复条目的方法。

因此，要测试方法，创建一个 3x30000 数组，其中包含 10000 个唯一行：

import numpy as np
points = np.random.random((10000,3))
raw_data = np.concatenate((points,points,points))
np.random.shuffle(raw_data)

这可以很好地近似网格数据，每个点都作为一个小平面顶点出现 3 次。在统一的同时，我需要建立一个唯一顶点列表；如果一个点已经在列表中，则必须存储对它的引用。

到目前为止，我使用 numpy 所能想到的最好的方法如下：

def unify(raw_data):
    # first point must be new
    unified_verts = np.zeros((1,3),dtype=np.float64)
    unified_verts[0] = raw_data[0]
    ref_list = [0]

    for i in range(1,len(raw_data)):
        point = raw_data[i]     
        index_array = np.where(np.all(point==unified_verts,axis=1))[0]

        # point not in array yet
        if len(index_array) == 0:
            point = np.expand_dims(point,0)
            unified_verts = np.concatenate((unified_verts,point))
            ref_list.append(len(unified_verts)-1)

        # point already exists
        else:
            ref_list.append(index_array[0])

    return unified_verts, ref_list

使用 cProfile 进行测试：

import cProfile
cProfile.run("unify(raw_data)")

在我的机器上，它在 5.275 秒内运行。我虽然使用 Cython 来加速它，但从我读过的内容来看，Cython 通常不会比 numpy 方法运行得快得多。关于如何更有效地做到这一点的任何建议？

4

1 回答 1

2

Jaime 展示了一个巧妙的技巧，可用于将 2D 数组视为 1D 数组，其中项目对应于 2D 数组的行。这个技巧可以让您将 numpy 函数应用到高维数组中，这些函数将一维数组作为输入（例如np.unique）。

如果行的顺序unified_verts无关紧要（只要 ref_list 相对于 ref_list 是正确的unifed_verts），那么您可以np.unique像这样使用 Jaime 的技巧：

def unify2(raw_data):
    dtype = np.dtype((np.void, (raw_data.shape[1] * raw_data.dtype.itemsize)))
    uniq, inv = np.unique(raw_data.view(dtype), return_inverse=True)
    uniq = uniq.view(raw_data.dtype).reshape(-1, raw_data.shape[1])
    return uniq, inv

在可以从(or )raw_data的返回值重构的意义上，结果是相同的：unifyunify2

unified, ref = unify(raw_data)
uniq, inv = unify2(raw_data)
assert np.allclose(uniq[inv], unified[ref])  # raw_data

在我的机器上，unified, ref = unify(raw_data)大约需要 51.390 秒，而uniq, inv = unify2(raw_data)需要大约 0.133 秒（约 386 倍加速）。

于 2013-06-24T10:53:25.083 回答