Как быстро подсчитать количество соседних вокселов?

Question

У меня есть 3D-сетка (вокселы), где некоторые вокселы заполнены, а некоторые нет. Трехмерная сетка редко заполнена, поэтому у меня есть набор filledVoxels с координатами (x, y, z) заполненных вокселей. То, что я пытаюсь сделать, это выяснить, для каждого заполненного воксела, сколько соседних вокселей заполнено тоже.

Вот пример:

• filledVoxels содержит вокселей (1, 1, 1), (1, 2, 1) и (1, 3, 1).
• Таким образом, соседние отсчеты:
  • (1,1,1) имеет 1 сосед
  • (1,2,1) имеет 2 соседей
  • (1,3,1) имеет 1 сосед.

Сейчас у меня есть этот алгоритм:

voxelCount = new Map<Voxel, Integer>(); 

for (voxel v in filledVoxels) 
    count = checkAllNeighbors(v, filledVoxels); 
    voxelCount[v] = count; 
end 

checkAllNeighbors() просматривает все 26 вокруг вокселей. Таким образом, в целом я делаю 26 * заполненных запросов Voxels.size(), что довольно медленно.

Есть ли способ сократить количество требуемых поисков? Когда вы смотрите на приведенный выше пример, вы можете видеть, что я проверяю одни и те же voxels несколько раз, поэтому можно было бы избавиться от поиска с помощью некоторого умного кэширования.

Если это помогает в любом случае, вокселы представляют собой вокселизированную трехмерную поверхность (но в ней могут быть дыры). Я обычно хочу получить список всех вокселов, у которых есть 5 или 6 соседей.

Answer 1

Вы можете преобразовать пространство вокселя в octree, в котором каждый узел содержит флаг, который указывает, содержит ли он все заполненные вокселы.

Когда узел не содержит заполненных вокселей, вам не нужно проверять ни одного из его потомков.

Answer 2

Если вы маршируете вдоль вокселов по одному, вы можете сохранить таблицу поиска, соответствующую сетке, так что после того, как вы проверили ее один раз с использованием , вы поместите значение в эту сетку. Для каждого вокселя, в котором вы находитесь, вы можете проверить, действительно ли его значение таблицы поиска, и только позвонить IsFullVoxel(), это не так.

OTOH похоже, что вы не можете избежать итерации по всем соседним вокселям, используя IsFullVoxel() или LUT. Если бы у вас была более априорная информация, это могло бы помочь. Например, если бы вы знали, что было не более х соседних заполненных вокселей, или вы знали, что в каждом направлении находились почти все соседние заполненные вокселы. Например, если вы знаете, что ищете вокселы с 5-6 соседями, вы можете остановиться после того, как найдете 7 полных соседей или 22 пустых соседей.

Я предполагаю, что существует функция IsFullVoxel(), которая возвращает true, если voxel заполнен.

Answer 3

Ум, ваш вопрос не очень ясен. Я предполагаю, что у вас есть список заполненных очков. В этом случае этот будет, который будет очень медленным, потому что вам нужно пройти через него (или использовать какую-то древовидную структуру, например kd-tree, но это все равно будет O(log n)).

Если вы можете (т. Е. Сетка не слишком большой), просто создайте 3d массив bools. 26 поисков в 3d-массиве не должно занимать столько времени (и на самом деле нет способа сократить количество поисков).

На самом деле, теперь, когда я думаю об этом, вы можете сделать его трехмерным массивом longs (64 бит).Каждый 64-битный блок будет содержать 64 (4 х 4 х 4) вокселя. Когда вы проверяете соседей вокселя в середине блока, вы можете сделать одно 64-битное чтение (что будет намного быстрее).

Answer 4

Если большинство ходов на вашей итерации были соседи, вы можете уменьшить свою проверку примерно на 25%, не оглядываясь на те, которые вы только что проверили, прежде чем сделать шаг.

Answer 5

Я бы сказал, что если каждый из ваших запросов медленный (O (размер)), вы должны оптимизировать его путем двоичного поиска в упорядоченном списке (O (log (size))).

Постоянный 26, я бы не стал волноваться. Если вы итерации умнее, вы можете кэшировать что-то и иметь 26 -> 10 или что-то, я думаю, но если вы не профилировали все приложение и не узнали, что это узкое место, я бы сосредоточился на чем-то другом.

Answer 6

Как утверждает ilya, вы не можете сделать так, чтобы обойти 26 соседних поисков. Вы должны сделать свой самый большой выигрыш в эффективном определении того, заполнен ли данный сосед или нет. Учитывая, что решение грубой силы по существу является O (N^2), у вас есть много возможностей для достижения этой цели. Так как вы должны перебрать все заполненные вокселей по крайней мере один раз, я бы подход, аналогичный следующему:

voxelCount = new Map<Voxel, Integer>(); 
visitedVoxels = new EfficientSpatialDataType(); 

for (voxel v in filledVoxels) 
    for (voxel n in neighbors(v)) 
    if (visitedVoxels.contains(n)) 
     voxelCount[v]++; 
     voxelCount[n]++; 
    end 
    next 
    visitedVoxels.add(v); 
next 

Для вашего эффективного типа пространственных данных, КД-дерево, как это было предложено Zifre, может быть хорошим идея. В любом случае, вы захотите уменьшить свое пространство поиска, разбирая посещаемые вокселы.

Answer 7

Вы можете найти Z-order curve полезную концепцию здесь. Он позволяет (с некоторыми оговорками) сохранять скользящее окно данных вокруг точки, которую вы сейчас запрашиваете, так что, когда вы переходите к следующей точке, вам не нужно выбрасывать многие из уже выполненных запросов ,

Answer 8

Есть ли способ сократить количество требуемых поисков?

Вы, как минимум, придется выполнять в наименьшем 1 поиска в вокселе. Поскольку это минимум, тогда любой алгоритм, который выполняет только один поиск на вокселе, будет соответствовать вашим требованиям.

Одна упрощенная идея состоит в том, чтобы инициализировать массив для хранения счетчика для каждого вокселя, затем посмотреть на каждый воксель и увеличить соседи этого воксела в массиве.

Псевдо C может выглядеть примерно так:

#define MAXX 100 
#define MAXY 100 
#define MAXZ 100 

int x, y, z 
char countArray[MAXX][MAXY][MAXZ]; 

initializeCountArray(MAXX, MAXY, MAXZ); // Set all array elements to 0 

for(x=0; x<MAXX; x++) 
    for(y=0;y<MAXY;y++) 
     for(z=0;z<MAXZ;z++) 
     if(VoxelExists(x,y,z)) 
      incrementNeighbors(x,y,z); 

Вам нужно написать initializeCountArray поэтому устанавливает все элементы массива в 0.

Что еще более важно вы также должны написать incrementNeighbors так что он не будет увеличиваться за пределами массива. Небольшое увеличение скорости здесь только для выполнения вышеописанного алгоритма для всех вокселей на внутреннем пространстве, а затем выполнить отдельный прогон на всех внешних вокселях с измененной процедурой incrementNeighbrs, которая понимает, что соседей с одной стороны не будет.

Этот алгоритм дает 1 поиск по количеству вокселей и не более 26 байтовых добавлений на вокселе. Если ваше пространство вокселей ограничено, это приведет к очень небольшим (относительным) дополнениям. Если ваше пространство воксела очень плотное, вы можете подумать об обратном алгоритме - инициализируйте массив значением 26 для каждой записи, а затем уменьшите соседи, когда воксель не существует.

Результаты для данного воксела (то есть, сколько соседей у ​​меня есть?) Находятся в массиве. Если вам нужно знать, сколько соседей воксел 2,3,5 имеет, просто посмотрите на байт в countArray [2] [3] [5].

Массив будет потреблять 1 байт за воксел. Вы можете использовать меньше места и, возможно, немного увеличить скорость, упаковывая байты.

Существуют лучшие алгоритмы, если вы знаете подробности о своих данных. Например, очень редкое пространство вокселей значительно выиграет от октета, где вы можете пропустить большие блоки поиска, когда вы уже знаете, что внутри не заполнено вокселов. Однако большинство этих алгоритмов по-прежнему требуют, по крайней мере, одного поиска на вокселе, чтобы заполнить их матрицу, но если вы выполняете несколько операций, тогда они могут выиграть больше, чем эта одна операция.