Алгоритм, чтобы увидеть, связаны ли два вокселя

11

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

Например (чтобы проиллюстрировать ситуацию в 2D), где # - заполненный квадрат:

  1 2 3
a # # #
b # #
c # # #

Если я выберу a3 и c3, я хочу как можно быстрее определить, связаны ли они; если между заполненными пикселями есть путь между a3 и c3. (Реальная ситуация, конечно, в трехмерной сетке вокселей.)

Я посмотрел на алгоритмы заливки и поиска пути, но я не уверен, какой выбрать. Оба выполняют ненужную работу: Flood fill пытается заполнить все воксели, но это не нужно. Алгоритмы поиска пути обычно связаны с поиском кратчайшего пути, что также не является необходимым. Мне нужно только знать , если это путь.

Какой алгоритм я должен использовать?

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

Брэм Вессен
источник
В вашем примере будет правильный путь от a3 до с3 быть следующим: c3->c2->b2->a2->a3?
это правильно
Брэм Вессен

Ответы:

12

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

С A * обычно первый путь, который вы найдете, является самым коротким, поэтому он не выполняет дополнительную работу после того, как он уже найден.

введите описание изображения здесь

Для некоторых оптимизаций, проверьте мой ответ здесь .

MichaelHouse
источник
Похоже, что он действительно стреляет вперед, пока не достигнет той стены, а потом как-то подкрадывается
GameDev-er
1
@ GameDev-er Да, это из-за эвристики. Если бы не было препятствия, это был бы очень быстрый поиск, почти прямой.
MichaelHouse
При лучшей сортировке узлов это расширит путь, ближайший к последнему узлу. Если у вас есть быстрая структура данных для упорядочения узлов, сортируйте их по расстоянию до цели для наиболее прямого пути.
MichaelHouse
9

Если вы готовы выполнить некоторую предварительную обработку и сэкономить на стоимости хранения, то разделение вокселей на связанные группы во время сборки дает очевидный ответ на вопрос «есть ли путь вообще». Существует путь между двумя вокселями, если они находятся в одной группе. Проблема с этим, очевидно, заключается в том, что вам нужно где-то хранить групповую информацию, и это зависит от вашего макета данных. Если вы храните простой список, вы можете просто разбить его на несколько списков, по одному для каждой пространственно связанной группы. Если вы организуете какую-то BVH, то вы, вероятно, могли бы получить достаточно хорошую эффективность, если бы могли сказать «все воксели в этом узле и ниже принадлежат группе X».

В качестве альтернативы, вы можете выполнить некоторую пространственную предварительную разбивку и сохранить несколько меньший набор вокселей «концентратора» для каждой подключенной группы. Затем вы можете найти путь от вашего исходного и целевого вокселей до их ближайшего концентратора, который должен быть намного короче / дешевле для расчета пути. Если вы можете найти путь от вокселя к вокселю-концентратору, то этот воксел является частью группы вокселей-концентраторов. С помощью интеллектуального выбора этих узловых вокселей вы можете минимизировать количество обходов пути. Например, сфера может иметь в центре только один воксел-концентратор, но длинная тонкая группа может иметь воксел-концентратор через каждые X вокселей по всей ее длине. Если ваши исходные и целевые вокселы находятся на обоих концах длины, им нужно всего лишь пройти не более X вокселей, чтобы найти концентратор, и хотя между началом и концом длины может быть огромное количество вокселей,

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

MrCranky
источник
1
Это правильный ответ, но для эффективной реализации его не следует хранить в виде списка. Добавьте указатель на каждый воксел, который указывает на его «представительный воксел», который вы устанавливаете с помощью алгоритма union-find. Это постоянная стоимость хранения на один воксель и, в основном, линейная по количеству ребер для вычислительных затрат.
Нил Г
Интересные идеи, но есть две вещи, которые могут осложнить ситуацию. Во-первых, содержимое сетки вокселей заранее неизвестно, поэтому для создания вокселей-концентраторов мне также потребуется алгоритм, который может определить, какие вокселы должны быть концентраторами.
Брэм Вессен
1
Вторая проблема заключается в том, что алгоритм необходим сразу после удаления одного вокселя, чтобы определить, разбита ли группа, в которую он входил, на более мелкие группы из-за удаления этого вокселя.
Брэм Вессен
@BramVaessen Если вы ищете все попарно взаимосвязанные взаимосвязи - и, в частности, разбиваются ли группы - тогда это несколько другой вопрос, чем просто достижимость (хотя достижимость - самый простой способ добиться этого); Я бы посоветовал добавить больше деталей о том, что вам нужно, к исходному вопросу, так как это может дать лучшие ответы на «проблему, стоящую за вопросом».
Стивен Стадницкий,
Чтобы сохранить его в чистоте, я задал свою первоначальную проблему в другом вопросе здесь gamedev.stackexchange.com/questions/50953/…
Брэм
4

Я не очень знаком с вокселями, но думаю, что вы можете получить довольно хорошую производительность, используя лучший алгоритм поиска, такой как A *. Проблема с использованием A * в этом случае состоит в том, что эвристический метод, который обычно используется, предназначен для определения приоритетов поиска кратчайшего пути, а не просто «любого пути» как можно быстрее.

Вам может повезти, если использовать альтернативную эвристику, которая расширяет меньше узлов, таких как

f (p) = g (p) + w (p) * h (p)

где w> = 1. вы уменьшаете значение 'w', чем ближе вы подходите к цели, тем самым придавая больший приоритет стоимости пути 'g', чем ближе вы подходите к искомому вокселю.

Надеюсь, это поможет!

Мэтью Р.
источник