Полигональная сетка: различия между версиями

'''Полигональная сетка''' ({{жарг|меш}} от {{lang-en|polygon mesh}}) — это совокупность вершин, рёбер и граней, которые определяют форму [[Многогранник|многогранного объекта]] в [[Трёхмерная графика|трехмернойтрёхмерной компьютерной графике]] и объёмном моделировании. Гранями обычно являются [[треугольник]]и, [[четырехугольникчетырёхугольник]]и или другие простые [[Выпуклый многоугольник|выпуклые многоугольники]] (полигоны), так как это упрощает [[рендеринг]], но сетки могут также состоять и из наиболее общих вогнутых многоугольников, или многоугольников с дырками.

Учение о полигональных сетках — это большой подраздел компьютерной графики и геометрического моделирования. Множество операций, проводимых над сетками, может включать [[Булева алгебра|булеву алгебру]], сглаживание, упрощение и многие другие. Разные представления полигональных сеток используются для разных целей и приложений. Для передачи полигональных сеток по сети используются сетевые представления, такие как «потоковые» и «прогрессивные» сетки. ОбъемныеОбъёмные сетки отличаются от полигональных тем, что они явно представляют и поверхность и объём структуры, тогда как полигональные сетки явно представляют лишь поверхность, а не объём. Так как полигональные сетки широко используются в компьютерной графике, для них разработаны алгоритмы [[Трассировка лучей|трассировки лучей]], [[Обнаружение столкновений|обнаружения столкновений]] и [[Динамика (физика)|динамики твердыхтвёрдых тел]].

Объекты созданные с помощью полигональных сеток должны хранить разные типы элементов, такие как вершины, ребрарёбра, грани, полигоны и поверхности. Во многих случаях хранятся лишь вершины, ребрарёбра и либо грани, либо полигоны. Рендерер может поддерживать лишь трех-сторонниетрёхсторонние грани, так что полигоны должны быть построены из их множества, как показано на рис. 1. Однако многие рендереры поддерживают полигоны с четырьмя и более сторонами, или умеют триангулировать полигоны в треугольники на лету, делая необязательным хранение сетки в триангулированной форме. Также в некоторых случаях, таких как моделирование головы, желательно уметь создавать и трехтрёх- и четырех-сторонниечетырёхсторонние полигоны.

'''Поверхности''', чаще называемые '''группами сглаживания''', полезны, но не обязательны для группирования гладких областей. Представьте себе цилиндр с крышками, такой как жестяная банка. Для гладкого затенения сторон, все [[Нормаль|нормали]] должны указывать горизонтально от центра, тогда как нормали крышек должны указывать в +/-(0,0,1) направлениях. Если рендерить как единую, [[Затенение по Фонгу|затененнуюзатенённую по Фонгу]] поверхность, вершины складок имели бы неправильные нормали. Поэтому, нужен способ определения где прекращать сглаживание для того, чтобы группировать гладкие части сетки, также, как полигоны группируют трёхсторонние грани. Как альтернатива предоставлению поверхностей/групп сглаживания, сетка может содержать другую информацию для расчёта тех же данных, такая как разделяющий угол (полигоны с нормалями выше этого предела либо автоматически рассматриваются как отдельные группы сглаживания, либо по отношению к ребру между ними применяется какая-либо техника, как например разделение или скашивание). Также, полигональные сетки с очень высоким разрешением менее подвержены проблемам, для решения которых требуются группы сглаживания, так как их полигоны настолько малы, что нужда в них пропадает. Кроме того, другая альтернатива существует в возможности просто отсоединения самих поверхностей от оставшейся части сетки. Рендереры не пытаются сглаживать ребрарёбра между несмежными полигонами.

* ПолуреберныеПолурёберные сетки: способ похож на "крылатое" представление, за исключением того, что используется информация обхода лишь половины грани.

* {{термин?|ЧетырехреберныеЧетырёхрёберные сетки}}, которые хранят ребрарёбра, полуребраполурёбра и вершины без какого-либо указания полигонов. Полигоны прямо не выражены в представлении, и могут быть найдены обходом структуры. Требования по памяти аналогичны полуребернымполурёберным сеткам.

Выбор структуры данных определяется применением, необходимой производительностью, размером данных, операциями, которые будут выполняться. К примеру, легче иметь дело с треугольниками, чем с многоугольниками общего вида, особенно в [[Вычислительная геометрия|вычислительной геометрии]]. Для определённых операций необходимо иметь быстрый доступ к топологической информации, такой как ребрарёбра или соседние грани; для этого требуются более сложные структуры, такие как "крылатое" представление. Для аппаратного рендеринга нужны компактные, простые структуры; поэтому в API низкого уровня, такие как [[DirectX]] и [[OpenGL]] обычно включена таблица углов (веер треугольников).

Моделирование требует лёгкого обхода всех структур. С сеткой использующей список граней очень легко найти вершины грани. Также, список вершин содержит список всех граней связанных с каждой вершиной. В отличие от вершинного представления, и грани и вершины явно представлены, так что нахождение соседних граней и вершин постоянно по времени. Однако, ребрарёбра не заданы явно, так что поиск всевсё ещё нужен, чтобы найти все грани, окружающие заданную грань. Другие динамические операции, такие как разрыв или объединение грани, также сложны со списком граней.

Представленное Брюсом Баумгартом в 1975, '''"Крылатое" представление''' явно представляет вершины, грани и ребрарёбра сетки. Это представление широко используется в программах для моделирования для предоставления высочайшей гибкости в динамическом изменении геометрии сетки, потому что могут быть быстро выполнены операции разрыва и объединения. Их основной недостаток - высокие требования памяти и увеличенная сложность из-за содержания множества индексов.

"Крылатое" представление решает проблему обхода от ребра к ребру и обеспечивает упорядоченное множество граней вокруг ребра. Для любого заданного ребра число исходящих рёбер может быть произвольным. Чтобы упростить это, "крылатое" представление предоставляет лишь четыре, ближайшие ребра по часовой и против часовой стрелки на каждом конце ребра. Другие ребрарёбра можно обойти постепенно. Поэтому информация о каждом ребре напоминает бабочку, поэтому представление называется "крылатым". Рисунок 4 показывает пример параллелепипеда в "крылатом" представлении. Полные данные по ребру состоят из двух вершин (конечные точки), двух граней (по каждую сторону), и четыре ребра("крылья" ребра).

|align=center|Все ребрарёбра грани

|align=center|Все ребрарёбра вокруг вершины

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

''Прогрессивные сетки'' передают данные о вершинах и гранях с повышающимся уровнем детализации. В отличие от ''потоковых сеток'', прогрессивные сетки дают общую форму целого объекта, но на низком уровне детализации. Дополнительные данные, новые ребрарёбра и грани, прогрессивно увеличивают детализацию сетки.