Алгоритм марширующих тетраэдров: визуализация неявных поверхностей.

Введение

Марширующий тетраэдр — это алгоритм в области компьютерной графики для визуализации неявных поверхностей. Он устраняет незначительную проблему неоднозначности алгоритма марширующих кубов для некоторых конфигураций кубов. Алгоритм был впервые представлен в 1991 году. В то время как оригинальный алгоритм марширующих кубов был защищен программным патентом, марширующий тетраэдр предлагал альтернативный алгоритм, не требующий патентной лицензии. С момента подачи заявки на патент (5 июня 1985 года) прошло более 20 лет, и алгоритм марширующих кубов теперь может использоваться свободно. При необходимости незначительные улучшения марширующего тетраэдра могут быть использованы для исправления вышеупомянутой неоднозначности в определенных конфигурациях. В алгоритме марширующего тетраэдра каждый куб разделяется на шесть нерегулярных тетраэдров путем разрезания куба пополам трижды, диагонально проходя через каждую из трех пар противоположных граней. Таким образом, все тетраэдры имеют одну из главных диагоналей куба. Вместо двенадцати ребер куба теперь у нас девятнадцать ребер: исходные двенадцать, шесть диагоналей граней и главная диагональ. Как и в алгоритме марширующих кубов, пересечения этих ребер с изоповерхностью аппроксимируются линейной интерполяцией значений в узлах сетки. Соседние кубы имеют все общие ребра на соединяющей грани, включая одну и ту же диагональ. Это важное свойство предотвращает появление трещин на отрисованной поверхности, поскольку интерполяция двух различных диагоналей грани обычно дает немного отличающиеся точки пересечения. Дополнительным преимуществом является то, что до пяти вычисленных точек пересечения можно повторно использовать при обработке соседнего куба, включая вычисленные нормали поверхности и другие графические атрибуты в точках пересечения. Каждый тетраэдр имеет шестнадцать возможных конфигураций, которые делятся на три класса: отсутствие пересечения, пересечение в одном треугольнике и пересечение в двух (смежных) треугольниках. Можно легко перечислить все шестнадцать конфигураций и сопоставить их со списками индексов вершин, определяющими соответствующие треугольные полосы.

Marching tetrahedra is an algorithm in the field of computer graphics to render implicit surfaces. It clarifies a minor ambiguity problem of the marching cubes algorithm with some cube configurations. It was originally introduced in 1991. While the original marching cubes algorithm was protected by a software patent, marching tetrahedrons offered an alternative algorithm that did not require a patent license. More than 20 years have passed from the patent filing date (June 5, 1985), and the marching cubes algorithm can now be used freely. Optionally, the minor improvements of marching tetrahedrons may be used to correct the aforementioned ambiguity in some configurations. In marching tetrahedra, each cube is split into six irregular tetrahedra by cutting the cube in half three times, cutting diagonally through each of the three pairs of opposing faces. In this way, the tetrahedra all share one of the main diagonals of the cube. Instead of the twelve edges of the cube, we now have nineteen edges: the original twelve, six face diagonals, and the main diagonal. Just like in marching cubes, the intersections of these edges with the isosurface are approximated by linearly interpolating the values at the grid points. Adjacent cubes share all edges in the connecting face, including the same diagonal. This is an important property to prevent cracks in the rendered surface, because interpolation of the two distinct diagonals of a face usually gives slightly different intersection points. An added benefit is that up to five computed intersection points can be reused when handling the neighbor cube. This includes the computed surface normals and other graphics attributes at the intersection points. Each tetrahedron has sixteen possible configurations, falling into three classes: no intersection, intersection in one triangle and intersection in two (adjacent) triangles. It is straightforward to enumerate all sixteen configurations and map them to vertex index lists defining the appropriate triangle strips.

Сравнение с марширующими кубиками

Марширующий тетраэдр вычисляет до девятнадцати пересечений рёбер на куб, в то время как марширующие кубы требуют только двенадцать. Лишь одно из этих пересечений не может быть использовано совместно со смежным кубом (пересечение на главной диагонали), однако совместное использование на всех гранях куба усложняет алгоритм и значительно увеличивает требования к памяти. С другой стороны, дополнительные пересечения обеспечивают немного более высокое разрешение при дискретизации. Количество конфигураций, определяющих размер обычно используемых таблиц поиска, значительно меньше, поскольку в каждом тетраэдре участвует всего четыре, а не восемь отдельных вершин. Вместо одного куба необходимо обработать шесть тетраэдров. Процесс однозначен, поэтому дополнительная обработка неоднозначности не требуется. Недостатком является то, что при разбиении куба на тетраэдры необходимо выбирать ориентацию тетраэдров, что может приводить к появлению искусственных "неровностей" на изоповерхности из-за интерполяции по диагоналям граней.

Алмазная решетчатая ячейка - альтернативный метод резки кубиков

Кубические ячейки, подлежащие триангуляции, также могут быть разделены на 5 тетраэдров, используя в качестве основы (ромбоэдрическую) решетку. Кубы соединяются по каждой стороне с другим кубом, имеющим противоположную ориентацию тетраэдра относительно центра куба. Чередующиеся вершины имеют разное количество пересекающихся с ними тетраэдров, что приводит к незначительно отличающейся сетке в зависимости от положения. При таком разделении обеспечиваются дополнительные плоскости симметрии; наличие тетраэдра вокруг центра куба также создает открытые пространства вокруг точек, находящихся вне поверхности. Ромбоэдрическая решетка имеет различные способы визуализации. Вместо пустых ячеек каждая ячейка должна быть заполнена чередующимися внутренними тетраэдрами. Для каждого тетраэдра, вписанного в куб, использующего вершины куба и ребра, пересекающие грани куба, тетраэдр занимает 4 точки; остальные 4 точки образуют вершины инвертированного тетраэдра; кубические ячейки располагаются таким образом, чтобы положение ячейки (x+y+z+) было нечетным, используйте один вариант, иначе – инвертированный; в противном случае соседние ячейки использовали бы другую диагональ для вычисления пересечения. Расчет цвета на основе системы пространственных текстур может быть выполнен с использованием текущей позиции фрагмента для выбора из повторяющейся текстуры на основе пар координат Texel (графических) (x, y), (y, z) и (x, z) и масштабирования этих значений на абсолютную величину каждого соответствующего компонента нормали – z, x и y соответственно. Наложение текстур (декалирование) может быть применено как растеризация текстур путем проецирования позиции текущего фрагмента в направлении нормали декали на плоскость текстуры, заданную начальной точкой и нормалью, а затем использования направленного вектора "вверх" или "вправо" для вычисления координат текстуры. Эта техника ближе всего к двойному контуру, который указан в разделе Isosurface, как потенциальный метод. Тетраэдры DCL включают дополнительные вычисления для диагоналей на гранях куба, в то время как двойной контур этого не требует. Этот метод также не учитывает ситуацию, когда две близкие точки "внутри" поверхности находятся на суммарном расстоянии менее 1 от поверхности, в этом случае они должны генерировать две точки на ребре вместо одной; соответствующая модификация – многогранный двойной контур.

The cubical cells to be meshed can also be sliced into 5 tetrahedra, using a (Diamond cubic) lattice as a basis. Cubes are mated on each side with another that has an opposite alignment of the tetrahedron around the centroid of the cube. Alternating vertices have a different number of tetrahedra intersecting on it, resulting in a slightly different mesh depending on position. When sliced this way, additional planes of symmetry are provided; having a tetrahedron around the centroid of the cube also generates very open spaces around points that are outside of the surface. Diamond cubic has a variety of visualizations. Instead of empty cells, every cell should be filled, with alternating inner tetrahedrons. For each tetrahedron inscribed in a cube, using the vertices of the cube and edges that cross the faces of the cube, the tetrahedron will occupy 4 points; the other 4 points form the corners of an inverted tetrahedron; the cubic cells are tiled such that the position of the cell (x+y+z+ ) is odd, use one, else use the inverted; otherwise near cells would use a different diagonal to compute the intersection. Calculation of color based on a spacial texture system can be done using the current fragment position to select from a repeating texture based on the pairs of Texel (graphics) coordinates (x,y), (y,z) and (x,z) and scaling those values by the absolute value of each respective component of the normal z, x, and y respectively. Texture decalling can be applied as Texture splatting by projecting the position of the current fragment in the direction of the decal' normal, to the plane of the texture given by an origin point and normal, then using a 'up' or 'right' directional vector to compute the texture coordinate. This technique would be more closely compared with dual contouring which is listed under Isosurface, as a potential technique. DCL tetrahedra involves additional calculations for the diagonals across cube faces, where dual contouring does not. This technique also has not addressed when two near points 'inside' a surface are a combined distance < 1 from the surface, where they should generate two points on the edge instead of 1; the related modification is Manifold Dual Contouring.