Марширующие тетраэдры
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
Марширующие тетраэдры — алгоритм в области компьютерной графики для рендеринга неявных поверхностей . Это проясняет небольшую проблему неоднозначности алгоритма марширующих кубов с некоторыми конфигурациями кубов. Первоначально он был представлен в 1991 году. [1]
В то время как исходный алгоритм марширующих кубов был защищен патентом на программное обеспечение , марширующие тетраэдры предлагали альтернативный алгоритм, не требующий патентной лицензии. Прошло более 20 лет с даты подачи заявки на патент (5 июня 1985 г.), и алгоритм марширующих кубов теперь можно использовать свободно. При желании можно использовать незначительные улучшения маршевых тетраэдров для исправления вышеупомянутой двусмысленности в некоторых конфигурациях.
В маршевых тетраэдрах каждый куб разбивается на шесть неправильных тетраэдров путем трехкратного разрезания куба пополам, разрезая по диагонали каждую из трех пар противоположных граней. Таким образом, все тетраэдры имеют общую одну из главных диагоналей куба. Вместо двенадцати ребер куба теперь у нас девятнадцать ребер: исходные двенадцать, шесть диагоналей граней и главная диагональ. Так же, как и в маршевых кубах , пересечения этих ребер с изоповерхностью аппроксимируются линейной интерполяцией значений в узлах сетки.
Соседние кубики имеют общие ребра соединяющейся грани, включая одну и ту же диагональ. Это важное свойство для предотвращения трещин на визуализированной поверхности, поскольку интерполяция двух различных диагоналей грани обычно дает несколько разные точки пересечения. Дополнительным преимуществом является то, что при обработке соседнего куба можно повторно использовать до пяти вычисленных точек пересечения. Сюда входят вычисленные нормали поверхности и другие графические атрибуты в точках пересечения.
Каждый тетраэдр имеет шестнадцать возможных конфигураций, которые делятся на три класса: без пересечения, пересечение в одном треугольнике и пересечение в двух (соседних) треугольниках. Несложно перечислить все шестнадцать конфигураций и сопоставить их со списками индексов вершин, определяющими соответствующие треугольные полосы .
Сравнение с походными кубиками
[ редактировать ]Марширующие тетраэдры вычисляют до девятнадцати пересечений ребер на куб, тогда как для марширующих кубов требуется только двенадцать. Только одно из этих пересечений не может быть общим с соседним кубом (тот, который находится на главной диагонали), но совместное использование всех граней куба усложняет алгоритм и значительно увеличивает требования к памяти. С другой стороны, дополнительные пересечения обеспечивают несколько лучшее разрешение выборки.
Количество конфигураций, определяющих размер обычно используемых справочных таблиц , намного меньше, поскольку на тетраэдр задействовано только четыре, а не восемь отдельных вершин. Вместо одного куба необходимо обработать шесть тетраэдров. Этот процесс однозначен, поэтому дополнительная обработка неоднозначностей не требуется.
Обратной стороной является то, что замощение куба тетраэдрами требует выбора ориентации тетраэдров, что может привести к образованию искусственных «выпуклостей» на изоповерхности из-за интерполяции по диагоналям граней. [2]
Ячейка с ромбовидной решеткой — альтернативный метод нарезки куба
[ редактировать ]Кубические ячейки, которые нужно построить в сетку, также можно разрезать на 5 тетраэдров. [3] используя ( алмазно-кубическую в качестве основы ) решетку. Кубы сопрягаются с каждой стороны с другой, у которой тетраэдр расположен противоположно центроиду куба. Перемежающиеся вершины имеют разное количество пересекающихся тетраэдров, что приводит к немного разной сетке в зависимости от положения. При таком разрезе создаются дополнительные плоскости симметрии; Наличие тетраэдра вокруг центроида куба также создает очень открытые пространства вокруг точек, находящихся за пределами поверхности.
Алмазный куб имеет множество визуализаций. Вместо пустых ячеек каждая ячейка должна быть заполнена чередующимися внутренними тетраэдрами. Для каждого тетраэдра, вписанного в куб, используя вершины куба и ребра, пересекающие грани куба, тетраэдр займет 4 точки; остальные 4 точки образуют углы перевернутого тетраэдра; кубические ячейки выложены таким образом, что позиция ячейки (x+y+z+...) нечетная, используйте одну, иначе используйте инвертированную; в противном случае для вычисления пересечения рядом с ячейками будет использоваться другая диагональ.
Расчет цвета на основе пространственной текстурной системы. [4] можно сделать, используя текущую позицию фрагмента для выбора из повторяющейся текстуры на основе пар координат текселей (x,y), (y,z) и (x,z) и масштабируя эти значения по абсолютному значению каждого соответствующего компонента. нормалей z, x и y соответственно. Декалькирование текстуры можно применять как нанесение текстур путем проецирования положения текущего фрагмента в направлении нормали декали на плоскость текстуры, заданную исходной точкой и нормалью, а затем с использованием направления «вверх» или «вправо». вектор для вычисления координат текстуры.
Эту технику можно было бы более близко сравнить с двойным контурированием , которое указано в разделе «Изоповерхности» как потенциальная техника. Тетраэдры DCL включают дополнительные расчеты диагоналей граней куба, тогда как двойное контурирование не требуется. Этот метод также не учитывает ситуации, когда две ближайшие точки «внутри» поверхности находятся на комбинированном расстоянии < 1 от поверхности, где они должны создавать две точки на краю вместо 1; соответствующая модификация — Manifold Dual Contouring . [5]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Акио Дои, Акио Койде. « Эффективный метод триангуляции равнозначных поверхностей с использованием тетраэдрических ячеек ». IEICE Транзакции информации и систем, Том E74-D № 1, 1991 г.
- ^ Чарльз Д. Хансен; Крис Р. Джонсон (2004). Руководство по визуализации . Академическая пресса. стр. 9–11. ISBN 978-0-12-387582-2 .
- ^ d3x0r (14 апреля 2020 г.). «Проект Github — марширующие тетраэдры с ромбовидной решеткой» . Гитхаб .
{{cite web}}: CS1 maint: числовые имена: список авторов ( ссылка ) - ^ d3x0r (22 апреля 2020 г.). «Проект Github — мультитекстурирование изоповерхностей» . Гитхаб .
{{cite web}}: CS1 maint: числовые имена: список авторов ( ссылка ) - ^ Лин Икс (30 декабря 2015 г.). Двойной контуринг коллектора . [ мертвая ссылка на YouTube ]
Внешние ссылки
[ редактировать ]- Визуализация неявных поверхностей с использованием адаптивных тетраэдризаций (Генрих Мюллер, Михаэль Веле)
- Генератор изоповерхностей Миколалисенко, который включает в себя маршевые тетраэдры в качестве одного из своих алгоритмов.
- Генератор изоповерхностей Миколалисенко, затем DCL Marching Tetrahedra в качестве дополнительного алгоритма (WebGL)
- Генератор изоповерхностей Миколалисенко с пространственным текстурированием на основе типа вокселей, добавленный в DCL Marching Tetrahedra (WebGL2).
- Регуляризованные маршевые тетраэдры: улучшенное извлечение изоповерхностей.