Сделай Сам Свою Работу на 5

Представление пространственных форм





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

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



При втором способе описания трехмерных форм поверхность может быть разбита на куски, каждый из которых будет описан параметрическим бикубическим уравнением. Поэтому такие поверхности называют параметрические бикубические поверхности.

 

Рис. 7.1. Параметрический бикубический кусок

Параметрические бикубические куски (рис. 7.1), из которых состоят эти поверхности, описываются координатами точек с помощью трех уравнений (по одному для х, у и z). Каждое из уравнений имеет две переменные (два параметра), причем показатели степени при них не выше третьей (отсюда название бикубический). Уравнение для X будет выглядеть следующим образом:



В матричной форме уравнение для Х можно описать как: X(S,t)=SCxTT, где S=[S3 S2 S 1] T=[t3 t2 t 1]

Аналогично записываются уравнения для Y и Z.

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

При использовании обоих методов трехмерное тело представляется в виде замкнутой поверхности.

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

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

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

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

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

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

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

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



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

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

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

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

P = ((x1, y1, z1), (x2, y2, z2), … , (xn, yn, zn))

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

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

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

При использовании этого представления каждый узел полигональной сетки запоминается лишь один раз в списке вершин V =((x1, y1, z1), … , (xn, yn, zn)). Многоугольник определяется списком указателей (или индексов) в списке вершин. Многоугольник, составленный из вершин 3, 5, 7 и 10 этого списка, представляется как Р = (3, 5, 7, 10).

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

7.1.3. Явное задание ребер

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

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

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

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

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.