Есть ли другой/лучший алгоритм создания воксельной сетки, чем Greedy Meshing? ⇐ Python

[Anonymous]

Для проекта, над которым я работаю, у меня есть большие воксельные данные, которые мне нужно визуализировать в сетке.
Во время поиска я быстро нахожу статью «Сетка в игре Minecraft», написанную Миколалисенко еще в 2012 году, и, согласно моим исследованиям, кажется, это единственный источник, на который все ссылаются, чтобы ответить на этот вопрос.
Он описывает три алгоритма решения этой проблемы: глупый, отбракованный и жадный.
Два первых на самом деле неэффективны, поэтому я сделал версию кода, который он предоставил для моего проекта, на Python с двумя изменениями:

• Я использую Numba для ускорения вычислений.
• Я напрямую вычисляю вершины треугольников вместо четырехугольников, чтобы соответствовать нашей реализации функции построения сетки.

Код: Выделить всё

@njit()
def greedy_mesh(volume, dims):
def f(i, j, k):
return(volume[i + dims[0] * (j + dims[1] * k)])

points = []
# Sweep over 3-axes
for d in range(3):
u = (d + 1) % 3
v = (d + 2) % 3
x = [0, 0, 0]
q = [0, 0, 0]
mask = [0] * (dims[u] * dims[v])

q[d] = 1

x[d] = -1
while x[d] < dims[d]:
n = 0
x[v] = 0
x[u] = 0
# Compute mask
while x[v] < dims[v]:
while x[u] < dims[u]:
a = f(x[0], x[1], x[2]) if x[d] >= 0 else False
b = f(x[0] + q[0], x[1] + q[1], x[2] + q[2]) if x[d] < (dims[d] - 1) else False

mask[n] = a != b
n += 1

x[u] += 1

x[u] = 0
x[v] += 1

x[d] += 1

n = 0
# Generate mesh for mask using lexicographic ordering
for j in range(0, dims[v]):
i = 0
while i < dims[u]:
if (n < len(mask)) and mask[n]:
w = 1
# Compute width
while (n + w < len(mask)) and (mask[n + w] and ((i + w) < dims[u])):
w += 1

done = False
h = 1
# Compute height (slighty awkward according to the autor)
while (j + h) <  dims[v]:
for k in range(0, w):
if not mask[n + k + h * dims[u]]:
done = True
break

if done:
break

h += 1

# New quad
x[u] = i;
x[v] = j;
du = [0, 0, 0]
dv = [0, 0, 0]

du[u] = w
dv[v] = h

# Triangles
A = (x[0],
x[1],
x[2])
B = (x[0] + du[0],
x[1] + du[1],
x[2] + du[2])
C = (x[0] + du[0] + dv[0],
x[1] + du[1] + dv[1],
x[2] + du[2] + dv[2])
D = (x[0] + dv[0],
x[1] + dv[1],
x[2] + dv[2])

points.extend([A, B, C])
points.extend([A, C, D])

# Zero-out mask
for l in range(0, h):
for k in range(0, w):
mask[n + k + l * dims[u]] = False

i += w
n += w

else:
i += 1
n += 1

# Unique set of points
vertices = [i for i in set(points)]

# Points
indices = []
for p in points:
indices.append(vertices.index(p))

return np.array(vertices), np.array(indices).reshape(-1, 3)

Я еще раз протестировал свой код, используя примеры, предоставленные Миколалисенко, и он работал отлично.
Но затем я попытался загрузить воксельные данные большего размера из нашего проекта (~ 300x300x300), и теперь алгоритм обрабатывает данные примерно 5 секунд. Честно говоря, я довольно быстр, но недостаточно для использования, и у нас гораздо большие наборы данных.
После небольшого описания, и без особого удивления, большая часть времени вычислений приходится на создание вершин и их индексов в конце. К сожалению, именно так была создана функция построения сетки, и я не могу изменить эту функцию.
Это, наконец, подводит меня к моему вопросу: существует ли сегодня алгоритм построения сетки вокселов лучше, чем жадное создание сетки, который мог бы помочь мне выполнить мои требования?
Даже если я считаю, что не существует оптимального решения для такого рода задач (немного похоже на проблему P = NP), я не могу найти альтернативные алгоритмы в Интернете даже при поиске научных статей.
Есть ли у вас какие-либо предложения или ссылки по моей проблеме?

Подробнее здесь: https://stackoverflow.com/questions/723 ... dy-meshing