СОДЕРЖАНИЕ

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

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

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

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

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

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

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

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

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

Рис. 3.1. Множество многоугольников с общим ребром.

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

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

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

P = ((X1,Y1,Z1), (X2,Y2,Z2), ..., (XN,YN,ZN)).

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

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

При использовании этого представления каждый узел полигональной сетки запоминается лишь один раз в списке вершин V=((X1,Y1,Z1),...,(XN,YN,ZN)). Многоугольник определяется списком указателей (или индексов) в списке вершин. Многоугольник составленный из вершин 3, 5, 7 и 10 этого списка представляется как P=(3,5,7,10). На рисунке 3.2 приведен пример такого представления. Оно имеет ряд преимуществ по сравнению с явным заданием многоугольников. Поскольку каждая вершина многоугольника запоминается только один раз, удается сэкономить значительный объем памяти. Кроме того, координаты вершины можно легко изменять. Однако все еще не просто отыскивать многоугольники с общими ребрами; последние при изображении всей полигональной фигуры по прежнему рисуются дважды. Эти проблемы можно решить, если описывать ребра в явном виде.

В этом представлении имеется список вершин V, однако будем рассматривать многоугольник не как список указателей на список вершин, а как совокупность указателей на элементы списка ребер, в котором ребра встречаются лишь один раз. Каждое ребро в списке ребер указывает на две вершины в списке вершин, определяющие это ребро, а также на один или два многоугольника, которым это ребро принадлежит. Таким образом, описываем многоугольник как P=(E1,..,EN), а ребро как E=(V1,V2,P1,P2). Если ребро принадлежит только одному многоугольнику, то либо P1 либо P2 – пусто. На рисунке 3.3 приведен пример такого представления.

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

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

В некоторых случаях ребра полигональных сеток есть общими для более чем двух многоугольников (рис.3.1). Рассмотрим, например, случай в картографии, когда такие подразделы, как области, районы и т.д., могут принадлежать одновременно нескольким многоугольникам. Если учесть раздел городов на районы, избирательные участки ,то это число существенным образом возрастет. Аналогично в некоторых трехмерных приложениях, таких, как описание ячеистой структуры металлического слоя, ребра принадлежат, по крайней, мере трем многоугольникам. Для таких приложений описания ребер могут быть расширены, чтобы включить произвольное число многоугольников: E=(V1,V2,P1,P2,...,PN).

При работе с многоугольниками используют уравнение плоскости, в которой лежит многоугольник.

Уравнение плоскости в пространстве имеет вид Ax+By+Cz+D=0. Для задачи плоскости достаточно трех точек.

Если заданы 3 точки, то имеем систему уравнений:

Если три точки не колинеарны, то уравнение имеет решение относительно А, В, С и D, если присвоить какое-то значение одному из коэффициентов. Например, предположим, что D=1 и решим систему уравнений.

Более рациональное решение основывается на том, что, если точки Р1, Р2, Р3 и (x,y,z) находятся в одной плоскости, то

Отсюда следует, что неизвестные коэффициенты А, В, С и D равны соответствующим детерминантам. Вычисление последних разрешает достаточно легко задать плоскость в координатном пространстве.