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

Question

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

Вот пример:

• fillVoxels содержит воксели (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 * fillVoxels.size () поисков, что довольно медленно.

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

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

Answer 1

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

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

Answer 2

Как утверждает Илья, вы мало что можете сделать, чтобы обойти 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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

Answer 6

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

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

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

Answer 7

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

Как минимум, вам нужно будет выполнить минимум 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 байт на воксель. Вы можете использовать меньше места и, возможно, немного увеличить скорость, упаковав байты.

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

Answer 8

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

Если вы можете (т.е. сетка не слишком большая), просто создайте массив массивов bool. 26 поисков в трехмерном массиве не должны занимать так много времени (и на самом деле нет способа сократить количество поисков).

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