Маршевые кубические неоднозначности против маршевого тетраэдра

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

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

В алгоритме маршевых тетраэдров вместо куба используются шесть тетраэдров с триангуляциями для каждого тетраэдра. Но предположим, что я должен реализовать алгоритм маршевых кубов, но для каждой из 256 триангуляций просто выберите ту, которая является "суммой" (объединением) триангуляций тетраэдра куба? Насколько я знаю, это то, что делают маршевые тетраэдры - так почему это волшебным образом фиксирует двусмысленности?

Есть 16 уникальных случаев, я думаю, и 240 других - это просто отражения/повороты тех 16. Я помню, как где-то читал какой-то документ, чтобы разрешить двусмысленности, вам нужно 33 случая. Может ли это быть связано с тем, почему маршевые тетраэдры как-то не страдают от проблем?

Итак, вопросы:

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

Я чувствую, что здесь что-то не хватает. Спасибо.

Ответ 1

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

В ответ на мои вопросы:

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

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

Ответ 2

Чтобы ответить на вопрос "Почему маршевые тетраэдры имеют двусмысленность?" необходимо понять, почему возникают двусмысленности в первую очередь в маршевых кубах.

Неоднозначность может возникать, когда есть две диагонально противоположные "положительные" вершины и две диагонально противоположные "отрицательные" вершины в кубе. Мне потребовалось некоторое время, чтобы обдумать его, но проблема с двусмысленностью заключается в том, что они теоретически позволяют создавать изосорные пятна для смежных кубов, которые несовместимы друг с другом. Это очевидная часть. Интересная часть состоит в том, что два соседних изосормических пятна из двух неоднозначных конфигураций несовместимы, если (и только если) один из них разделяет "отрицательные" вершины, а другой разделяет "положительные" вершины.

Вот соответствующая цитата из книги Рейфаля Венгера "Геометрия изоповерхностей, топология и алгоритмы" (не может размещать более двух ссылок, поэтому я объединил все соответствующие изображения из книги в одиночный):

Граница кубического трехмерного изосурческого патча определяет изоконтур на каждой из квадратов квадратов кубов. Если некоторые конфигурации isosurface patch разделяет отрицательные вершины на грани, а смежные конфигурации изоповерхностного патча разделяют положительные, то края изоповерхности на общей фасете не будут выровнены. изострафические пятна на рис. 2.16 не разделяют положительные вершины на любой грани. Кроме того, полученная поверхностная поверхность патчей в любом повороте или отражении конфигураций также не отдельные положительные вершины на любой грани. Таким образом, изострадные пятна в любых двух смежных кубах правильно выровнены по их границам. одинаково действительный, но комбинаторно отличный, изоповерхностный стол может быть сгенерированные с использованием изосорных пятен, которые не разделяют отрицательные вершины на любой квадратной грани.

Это означает, что если все используют неоднозначные конфигурации, следуют одному и тому же шаблону (т.е. всегда отделяют "отрицательные" вершины), то невозможно создать топологически неправильную поверхность. И проблемы возникнут, если вы используете конфигурации "из обоих миров" для одной изоповерхности.

Поверхность, построенная с использованием той же модели разрешения неоднозначности, по-прежнему может содержать нежелательные ошибки, такие как this (взято из "Эффективная реализация случаев маршевых кубов с топологическими гарантиями" статьи Томаса Левинера Хелио Лопеса, Антонио Уилсона Виейры и Гевана Тавареса), но это будет, как вы сказали, водонепроницаемым.

Для этого вам нужно будет использовать таблицу поиска на основе 22 уникальных конфигураций (не стандартных 14 или 15), показанных на рисунке 2.16.

Теперь, вернемся к первому вопросу - почему Маршевые тетраэдры не страдают от двусмысленностей? По той же причине не будет никаких двусмысленностей в маршевых кубах, если это сделано так, как описано выше, - потому что вы произвольно решили использовать один из двух доступных вариантов неоднозначного разрешения конфигурации. В Marching Cubes совсем не очевидно (по крайней мере для меня, пришлось много копать), что это даже вариант, но в Marching Tetrahedrons это делается для вас самим алгоритмом, Вот еще цитата из книги Рефаэля Венгера:

Регулярные кубы сетки имеют неоднозначную конфигурацию, в то время как тетраэдрического разложения нет. Что случилось с двусмысленным конфигурации? Эти конфигурации разрешаются выбором триангуляции. Например, на рис. 2.31 первая триангуляция дает изосульфический пластырь с двумя компонентами, соответствующими 2B-II на рис. 2.22, в то время как вторая дает изоповерхностный патч с одним компонент, соответствующий 2B-I.

Обратите внимание, как кубы нарезаны на тетраэдры двумя способами на рисунке 2.31. Выбор этого нарезки или другого - секретный соус, который устраняет двусмысленности.

Можно спросить себя - если проблему двусмысленности можно решить, просто используя тот же шаблон для всех кубов, то почему существует так много книг и статей о более сложных решениях? Зачем мне нужен Asymptotic Decider и все такое? Насколько я могу судить, все сводится к тому, что вам нужно достичь. Если для вас достаточно топологической корректности (как и в отсутствие отверстий), вам не нужны все продвинутые вещи. Если вы хотите разрешить проблемы, подобные тем, которые показаны в статье "Эффективная реализация маршевых кубов", показанной выше, вам необходимо погрузиться глубже.

Я настоятельно рекомендую прочитать соответствующие главы книги Рефаэля Венгера "Геометрия изоповерхностей, топология и алгоритмы", чтобы лучше понять природу этих алгоритмов, каковы проблемы, с чем возникают проблемы и как они могут быть решены.

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

Ответ 3

Возьмем следующий пример 2d (который вводит неопределенности):

Если мы разделим этот квадрат на два треугольника, мы получим разные результаты в диагонали, которую мы решили разделить на квадрат. По диагонали 0-0 мы получаем треугольники (010,010), а для диагонали 1-1 получаем треугольники (101, 101). Очевидно, что разная разбивка квадрата приводит к разным результатам. Либо правильно, и это одинаково для 3D-кубов.

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