Полосы треугольников в треугольных сетях

Введение

Набор треугольников с общими вершинами в треугольной сетке.

В компьютерной графике треугольная полоса — это подмножество треугольников в треугольной сетке, имеющих общие вершины, и более эффективный способ хранения информации о сетке. Она эффективнее неиндексированных списков треугольников, но обычно не быстрее, а иногда и медленнее индексированных списков треугольников. Основная причина использования треугольных полос — сокращение объема данных, необходимого для создания последовательности треугольников. Количество вершин, хранящихся в памяти, уменьшается с 3N до N + 2, где N — количество треугольников, которые необходимо отрисовать. Это позволяет экономить дисковое пространство и быстрее загружать данные в оперативную память. Например, четыре треугольника на диаграмме, без использования треугольных полос, пришлось бы хранить и интерпретировать как четыре отдельных треугольника: ABC, CBD, CDE и EDF. Однако, используя треугольную полосу, их можно сохранить просто как последовательность вершин ABCDEF. Эта последовательность будет декодирована как набор треугольников с вершинами ABC, BCD, CDE и DEF, хотя точный порядок чтения вершин не будет следовать слева направо, так как это привело бы к тому, что соседние треугольники будут ориентированы в противоположных направлениях.

Недвижимость и строительство

Из определения следует, что подпоследовательность вершин треугольной полосы также представляет собой треугольную полосу. Однако, если эта подполоса начинается с четной вершины (при нумерации с единицы), то полученные треугольники изменят свою ориентацию. Например, подполоса BCDEF будет представлять треугольники: BCD, CED, DEF. Аналогично, изменение порядка вершин полосы приведет к тому же набору треугольников, если полоса имеет четное число вершин (например, полоса FEDCBA будет представлять те же треугольники FED, ECD, DCB, CAB, что и исходная полоса). Однако, если полоса имеет нечетное число вершин, то полоса с измененным порядком вершин будет представлять треугольники с противоположной ориентацией. Например, изменение порядка вершин полосы ABCDE приведет к полосе EDCBA, которая представляет треугольники EDC, DBC, CBA. Преобразование произвольной многоугольной сетки в одну длинную полосу до недавнего времени было в целом невозможно. Обычно треугольные полосы аналогичны набору петель ребер, а полюса на модели представлены треугольными веерами. Инструменты, такие как Stripe или FTSG, представляют модель в виде нескольких полос. Оптимальная группировка набора треугольников в последовательные полосы является NP-полной задачей. В качестве альтернативы, полный объект можно описать как вырожденную полосу, содержащую треугольники нулевой площади, которые программное обеспечение или аппаратное обеспечение отбросит. Вырожденные треугольники фактически вводят разрывы или "скачки" в полосу. Например, сетка на диаграмме может быть представлена как ABCDDFFEDC, которая будет интерпретироваться как треугольники ABC, CBD, CDD, DDF, DFF, FFE, FED, DEC (вырожденные треугольники выделены курсивом). Обратите внимание, как эта полоса сначала строит два треугольника слева, затем перезапускается и строит оставшиеся два справа. Хотя разрывы в треугольных полосах всегда можно реализовать повторной отправкой вершин, некоторые API явно поддерживают эту функцию. IRIS GL поддерживала Swaps (переворачивание двух последовательных вершин в полосе), функцию, на которую полагались ранние алгоритмы, такие как алгоритм SGI. В последнее время OpenGL/DirectX могут отрисовывать несколько треугольных полос без вырожденных треугольников, используя функцию примитивной перезагрузки.

It follows from definition that a subsequence of vertices of a triangle strip also represents a triangle strip. However, if this substrip starts at an even (with 1 based counting) vertex, then the resulting triangles will change their orientation. For example a substrip BCDEF would represent triangles: BCD,CED,DEF. Similarly, reversal of strips’ vertices will result in the same set of triangles if the strip has an even number of vertices. (e. g. strip FEDCBA will represent the same triangles FED,ECD,DCB,CAB as the original strip). However, if a strip has an odd number of vertices then the reversed strip will represent triangles with opposite orientation. For example, reversal of a strip ABCDE will result in strip EDCBA which represents triangles EDC, DBC, CBA). Converting a general polygon mesh to a single long strip was until recently generally not possible. Usually the triangle strips are analogous to a set of edge loops, and poles on the model are represented by triangle fans. Tools such as Stripe or FTSG represent the model as several strips. Optimally grouping a set of triangles into sequential strips has been proven NP complete. Alternatively, a complete object can be described as a degenerate strip, which contains zero area triangles that the processing software or hardware will discard. The degenerate triangles effectively introduce discontinuities or "jumps" to the strip. For example, the mesh in the diagram could also be represented as ABCDDFFEDC, which would be interpreted as triangles ABC CBD CDD DDF DFF FFE FED DEC (degenerate triangles marked with italics). Notice how this strip first builds two triangles from the left, then restarts and builds the remaining two from the right. While discontinuities in triangle strips can always be implemented by resending vertices, APIs sometimes explicitly support this feature. IRIS GL supported Swaps (flipping two subsequent vertices in a strip), a feature relied on by early algorithms such as the SGI algorithm. Recently OpenGL/DirectX can render multiple triangle strips without degenerated triangles using Primitive Restart feature.