Полигональные сетки

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

· Объем требуемой памяти;

· Простота идентификации ребер, инцидентных вершине;

· Простота идентификации многоугольников, которым принадлежит дан­ное ребро;

· Простота процедуры поиска вершин, образующих ребро;

· Легкость определения всех ребер, образующих многоугольник;

· Простота получения изображения полигональной сетки;

· Простота обнаружения ошибок в представлении (например, отсутствие ребра или вершины или многоугольника).

Рассмотрим три способа описания полигональных сеток.

Явное задание многоугольников

Каждый многоугольник можно представить в виде списка координат его вершин:

P = ((x₁, y₁, z₁), (x₂, y₂, z₂), … , (x_n, y_n, z_n))

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

Полигональная сетка изображается путем вычерчивания ребер каждого многоуголь­ника, однако это приводит к тому, что общие ребра рисуются дважды – по одному разу для каждого из многоугольников.

Задание многоугольников с помощью указателей в список вершин

При использовании этого представления каждый узел полигональной сетки запомина­ется лишь один раз в спи­ске вершин V =((x₁, y₁, z₁), … , (x_n, y_n, z_n)). Многоугольник опре­деляется списком указателей (или индексов) в спи­ске вершин. Многоугольник, составленный из вершин 3, 5, 7 и 10 этого списка, представляется как Р = (3, 5, 7, 10).

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