 | Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) ( Узнайте, как и когда удалить этот шаблон сообщения )
|
Марширующие тетраэдры - это алгоритм в области компьютерной графики для визуализации неявных поверхностей . Это проясняет небольшую проблему неоднозначности алгоритма марширующих кубов с некоторыми конфигурациями куба. Первоначально он был представлен в 1991 году. [1]
В то время как исходный алгоритм марширующих кубов был защищен патентом на программное обеспечение , маршевые тетраэдры предлагали альтернативный алгоритм, который не требовал патентной лицензии. С даты подачи заявки на патент (5 июня 1985 г.) прошло более 20 лет, и теперь алгоритм маршевых кубов можно использовать свободно. Необязательно, небольшие улучшения марширующих тетраэдров могут быть использованы для исправления вышеупомянутой неоднозначности в некоторых конфигурациях.
В движущихся тетраэдрах каждый куб делится на шесть неправильных тетраэдров путем трехкратного разрезания куба пополам, разрезая по диагонали каждую из трех пар противоположных граней. Таким образом, все тетраэдры имеют одну из главных диагоналей куба. Вместо двенадцати ребер куба у нас теперь девятнадцать ребер: исходные двенадцать, шесть диагоналей граней и главная диагональ. Как и в маршевых кубах , пересечения этих ребер с изоповерхностью аппроксимируются путем линейной интерполяции значений в точках сетки.
Соседние кубы имеют все ребра соединительной грани, включая одну и ту же диагональ. Это важное свойство для предотвращения трещин на визуализированной поверхности, поскольку интерполяция двух различных диагоналей грани обычно дает немного разные точки пересечения. Дополнительным преимуществом является то, что до пяти вычисленных точек пересечения можно повторно использовать при обработке соседнего куба. Сюда входят вычисленные нормали поверхности и другие графические атрибуты в точках пересечения.
Каждый тетраэдр имеет шестнадцать возможных конфигураций, которые можно разделить на три класса: без пересечения, пересечения в одном треугольнике и пересечения в двух (соседних) треугольниках. Несложно перечислить все шестнадцать конфигураций и отобразить их в списках индексов вершин, определяющих соответствующие полосы треугольников .
Сравнение с походными кубиками [ править ]
Марширующие тетраэдры вычисляют до девятнадцати пересечений ребер на куб, тогда как для маршевых кубов требуется только двенадцать. Только одно из этих пересечений не может быть использовано совместно с соседним кубом (тем, что находится на главной диагонали), но совместное использование на всех гранях куба усложняет алгоритм и значительно увеличивает требования к памяти. С другой стороны, дополнительные пересечения обеспечивают немного лучшее разрешение выборки.
Количество конфигураций, определяющих размер обычно используемых справочных таблиц , намного меньше, поскольку на тетраэдр приходится только четыре, а не восемь отдельных вершин. Вместо одного куба нужно обработать шесть тетраэдров. Процесс однозначный, поэтому дополнительная обработка неоднозначности не требуется.
Обратной стороной является то, что мозаика куба с тетраэдрами требует выбора в отношении ориентации тетраэдров, что может создавать искусственные «выпуклости» на изоповерхности из-за интерполяции по диагоналям граней. [2]
Ячейка с алмазной решеткой - альтернативный метод нарезки куба [ править ]
Кубические ячейки, которые необходимо объединить в сетку, также могут быть разрезаны на 5 тетраэдров [3], используя ( алмазную кубическую ) решетку в качестве основы. Кубы сопряжены с каждой стороны с другим, имеющим противоположное расположение тетраэдра вокруг центроида куба. Чередующиеся вершины имеют разное количество пересекающихся тетраэдров, в результате чего сетка может немного отличаться в зависимости от положения. При таком разрезе предоставляются дополнительные плоскости симметрии; наличие тетраэдра вокруг центроида куба также создает очень открытые пространства вокруг точек, находящихся за пределами поверхности.
Алмазный кубик имеет множество визуализаций. Вместо пустых ячеек следует заполнить каждую ячейку чередующимися внутренними тетраэдрами. Для каждого тетраэдра, вписанного в куб, с использованием вершин куба и ребер, пересекающих грани куба, тетраэдр будет занимать 4 точки; остальные 4 точки образуют углы перевернутого тетраэдра; кубические ячейки выложены плиткой так, что положение ячейки (x + y + z + ...) нечетное, используйте единицу, иначе используйте перевернутую; в противном случае близкие ячейки использовали бы другую диагональ для вычисления пересечения.
Расчет цвета на основе системы пространственной текстуры [4] может быть выполнен с использованием текущей позиции фрагмента для выбора из повторяющейся текстуры на основе пар координат Texel_ (графика) (x, y), (y, z) и (x , z) и масштабирование этих значений по абсолютному значению каждого соответствующего компонента нормалей z, x и y соответственно. Удаление текстур можно применить как Texture_splatting , проецируя положение текущего фрагмента в направлении нормали декали на плоскость текстуры, заданную исходной точкой и нормалью, а затем используя направленный вектор вверх или вправо. для вычисления координаты текстуры.
Этот метод можно было бы более точно сравнить с двойным контуром , который указан в разделе Isosurface , как потенциальный метод. Тетраэдры 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 - Марширующие алмазные решетчатые тетраэдры" .
- ^ d3x0r (22 апреля 2020 г.). "Проект Github - Мульти-текстурирование Isosurface" .
- ↑ Lin X (30 декабря 2015 г.). Двойное контурирование коллектора .
Внешние ссылки [ править ]
- Визуализация неявных поверхностей с помощью адаптивных тетраэдризаций (Генрих Мюллер, Майкл Вел)
- Генератор изоповерхностей Миколалысенко, который включает Марширующие Тетраэдры в качестве одного из алгоритмов.
- Генератор изоповерхностей Миколалысенко, затем DCL Marching Tetrahedra в качестве дополнительного алгоритма (WebGL)
- Генератор изоповерхностей Миколалысенко с пространственным текстурированием на основе типа вокселя добавлен в DCL Marching Tetrahedra (WebGL2)
- Регуляризованные маршевые тетраэдры: улучшенное извлечение изоповерхности
