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

Question

У меня есть 3D-сетка (воксели), где некоторые воксели заполнены, а некоторые нет. 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* заполненных поисков Vize..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

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

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

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

Answer 5

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

Answer 6

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

Answer 7

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

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

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

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

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