КГ_4глава (Компьютерная графика)

ГЛАВА 4

Методы и алгоритмы трехмерной графики

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

4.1. Модели описания поверхностей

Рассмотрим, как можно представлять форму трехмерных объектов в систе­мах КГ. Для описания формы поверхностей могут использоваться разнооб­разные методы. Сделаем обзор некоторых из них.

Аналитическая модель

Аналитической моделью будем называть описание поверхности математиче­скими формулами. В КГ можно использовать много разновидностей такого описания. Например, в виде функции двух аргументов z = f(х, у). Можно использовать уравнение F (х, у, z) = 0.

Зачастую используется параметрическая форма описания поверхности. За­пишем формулы для трехмерной декартовой системы координат (х, у, z):

где s » t— параметры, которые изменяются в определенном диапазоне, функции F_x, F_y и F_z будут определять форму поверхности.

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

В качестве примера рассмотрим аналитическое описание поверхности шар. Сначала как функцию двух аргументов:

Затем в виде уравнения:

А также в параметрической форме:

Для описания сложных поверхностей часто используют сплайны. Сплайн — это специальная функция, более всего пригодная для аппроксимации отдель­ных фрагментов поверхности. Несколько сплайнов образовывают модель сложной поверхности. Другими словами, сплайн — эта тоже поверхность, но такая, для которой можно достаточно просто вычислять координаты ее точек, Обычно используют кубические сплайны. Почему именно кубические? По­тому, что третья степень — наименьшая из степеней, позволяющих описы­вать любую форму, и при стыковке сплайнов можно обеспечить непрерыв­ную первую производную — такая поверхность будет без изломов в местах стыка. Сплайны часто задают параметрически. Запишем формулу для компо­ненты x(s,t) кубического сплайна в виде многочлена третьей степени пара­метров s и t

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

Рассмотрим одну из разновидностей сплайнов— сплайн Безье. Приведем его сначала в обобщенной форме — степени т х п [19]:

где Р_ij — опорные точки-ориентиры, коэффициенты бинома Ньютона, они рассчитываются по формуле:

Кубический сплайн Безье соответствует значениям т = 3, п = 3. Для его определения необходимо 16 точек-ориентиров Р_ij (рис. 4.1); коэффициенты С_im С_jn равны 1,3,3,1 при i,j = 0,1,2,3.

Рис. 4.1. Кубические сплайны Безье

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

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

ординат вершин граней в процессе отображения, что уменьшает скоро! сравнительно с полигональной моделью описания.

Векторная полигональная модель

Для описания пространственных объектов здесь используются такие элементы: вершины; отрезки прямых {векторы); полилинии, полигоны; полигононые поверхности (рис. 4.2).

Элемент "вершина" (vertex) — главный элемент описания, все другие являются производными. При использовании трехмерной декартовой системы координаты вершин определяются как (х_i, у_i, z_i) Каждый объект однозначно определяется координатами собственных вершин.

Рис. 4.2. Базовые элементы векторно-полигональной модели

Вершина может моделировать отдельный точечный объект, размер которой не имеет значения, а также может использоваться в качестве конечных точёк для линейных объектов и полигонов. Двумя вершинами задается вектор. Н^ сколько векторов составляют полилинию. Полилиния может моделировать отдельный линейный объект, толщина которого не учитывается, а также может представлять контур полигона. Полигон моделирует площадный объект. Один полигон может описывать плоскую грань объемного объекта. Несколько граней составляют объемный объект в виде полигональной поверхности— многогранник или незамкнутую поверхность (в литературе часта употребляется название "полигональная сетка").

Векторную полигональную модель можно считать наиболее распространен! ной в современных системах трехмерной КГ. Ее используют в системах автоматизированного проектирования, в компьютерных играх и тренажерах* в САПР, геоинформационных системах и тому подобное.

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

I Первый способ. Сохраняем все грани в отдельности (рис. 4.3).

Рис. 4.3. Первый способ описания куба

Схематично это изобразим на рис. 4.4.

Рис. 4.4. Отдельные грани

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

Рассчитаем объем памяти, необходимый для описания куба следующим образом:

где Р_в — разрядность чисел, необходимая для представления координат.

Шесть граней здесь описываются 24 вершинами. Такое представление избы­точно — каждая вершина записана трижды. Не учитывается то, что у граней есть общие вершины.

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

Рис. 4.5. Номера вершин

Рис. 4.6. В массивах граней сохраняются индексы вершин Оценим затраты памяти:

где Р_в — разрядность координат вершин, Р_индекс — разрядность индексов.

Третий способ описания (рис. 4.7). Этот способ (в литературе его иногда на­зывают линейно-узловой моделью) основывается на иерархии: вершины-ребра-грани.

Оценим затраты памяти:

где Р_в — разрядность координат, разрядность индексов вершин и ребер соответственно.

Рис. 4.7. Линейно-узловая модель

Для сравнения объемов памяти этих трех вариантов необходимо определить­ся с разрядностью данных. Предположим, что разрядность координат и ин­дексов составляет четыре байта. Это соответствует, например, типу чисел с плавающей точкой float для координат и целому типу long для индексов (на­звания этих типов на компьютерном языке С, C++). Тогда затраты памяти в байтах составляют:

Пусть для координат отведено 8 байтов (тип с плавающей точкой double), a для индексов — 4 байта. Тогда:

Когда разрядность для координат больше, чем для индексов, то ощутимо преимущество второго и третьего вариантов. Наиболее экономичным можно считать второй вариант. Необходимо заметить, что такой вывод мы сделали для куба. Для других типов объектов соотношение вариантов может быть иным. Кроме того, необходимо учитывать такие варианты построения струк­тур данных: использован ли единый массив для всех объектов, или же для каждого объекта предназначен отдельный массив (при объектно-ориен­тированном стиле программирования каждый объект можно сохранять в отдельном классе). Это может обуславливать разную необходимую разрядность для индексов.

А теперь сравним эти три разновидности векторной полигональной модели, учитывая другие аспекты.

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