ALL
.pdf
Методы и алгоритмы трехмерной графики
Для описания сложных поверхностей часто используют сплайны.
Сплайн – это специальная функция, более всего пригодная для аппроксимации отдельных фрагментов поверхности. Несколько сплайнов образовывают модель сложной поверхности.
Обычно используют кубические сплайны.
Третья степень — наименьшая из степеней, позволяющих описывать любую форму, и при стыковке сплайнов можно обеспечить непрерывную первую производную — такая поверхность будет без изломов в местах стыка.
Сплайны часто задают параметрически.
Запишем формулу для компоненты х(s,t) кубического сплайна в виде многочлена третьей степени параметров s и t:
х(s,t) = а11 s3t3 + а12 s3t2 + а13 s3t + а14 s3 +
+ а21 s2t3 + а22 s2t2 + а23 s2t + а14 s2 +
+ а31 st3 + а32 st2 + а33 st + а34 s +
+ а41 t3 + а42 t2 + а43 t + а44
В математической литературе можно ознакомиться со способами определения
коэффициентов аij для сплайнов, которые имеют заданные свойства. Примеры анализа и синтеза сплайнов в матричной форме приведены в [19, 28].
Методы и алгоритмы трехмерной графики
Рассмотрим одну из разновидностей сплайнов— сплайн Безье. Приведем его сначала в обобщенной форме — степени т х п [19]:
,
где Рij — опорные точки-ориентиры, 0 s 1, 0 t 1,aС!!im и Сjn — коэффициенты биномаbНьютона, они рассчитываются по формуле:
|
Ca |
|
|
|
b!(a b)! |
||
Кубический сплайн Безье - т = 3, n = 3. Для его определения необходимо 16 точек-ориентиров Рij (рис,); коэффициенты Сim, Сjn равны 1,3,3,1 при i,j = 0,1,2,3.
Аналитическая модель в целом наиболее пригодна
для многих операций анализа поверхностей.
Положительные черты модели:
1. легкая процедура расчета координат каждой точки
поверхности, нормали;
2. |
небольшой объем информации для описания |
|
|
достаточно сложных форм. |
|
|
Недостатки : |
Рис. Кубические сплайны Безье |
1.сложные формулы описания с использованием функций, которые медленно вычисляются на компьютере, снижают скорость выполнения операций отображения;
2.невозможность в большинстве случаев применения данной формы описания непосредственно для построения изображения поверхности.
В таких случаях поверхность отображают как многогранник, используя формулы аналитического описания для расчета ко ординат вершин граней в процессе отображения, что уменьшает скорость сравнительно с полигональной моделью описания.
Векторная полигональная модель
Для описания пространственных объектов здесь используются такие элементы: вершины;
отрезки прямых (векторы), полилинии, полигоны, полигонаные поверхности (рис.).
Элемент "вершина" (vertex) — главный элемент описания, все другие являются производными. При использовании трехмерной декартовой системе координаты вершин определяются как (x, y, z). Каждый объект однозначно определяется координатами собственных вершин.
•Вершина может моделировать отдельный точечный объект, размер которой не имеет значения, а также может использоваться в качестве конечных точек для линейных объектов и полигонов.
Рис. Базовые элементы векторно-полигональной модели
Двумя вершинами задается вектор. Несколько векторов составляют полилинию.
Полилиния может моделировав отдельный линейный объект, толщина которого не учитывается, а также может представлять контур полигона.
Полигон моделирует площадный объект. Один полигон может описывать плоскую грань объемного объекта.
Несколько граней составляют объемный объект в виде полигональной поверхности — многогранник или незамкнутую поверхность (в литературе часто употребляется название "полигональная сетка"),
Методы и алгоритмы трехмерной графики
Векторная полигональная модель наиболее распространена в современных системах трехмерной КГ. Ее используют в системах автоматизированного проектирования, в компьютерных играх и тренажерах, в САПР, геоинформационных системах и т. д.
Структуры данных, которые используются в векторной полигональной модели.
В качестве примера объекта рассмотрим куб. Рассмотрим, как организовать описание объекта в структурах данных.
Первый способ. Сохраняем все грани в отдельности (рис.)
Рис.. Первый способ описания куба
Грань A = {(XA0, YA0 , ZA0), (XA1, YA1 , ZA1), (XA2, YA2 , ZA3), (XA3, YA3 , ZA3)}
Грань B = {(XB0, YB0 , ZB0), (XB1, YB1 , ZB1), (XB2, YB2 , ZB3), (XB3, YB3 , ZB3)}
Грань C = {(XC0, YC0 , ZC0), (XC1, YC1 , ZC1), (XC2, YC2 , ZC3), (XC3, YC3 , ZC3)}
Грань D = {(XD0, YD0 , ZD0), (XD1, YD1 , ZD1), (XD2, YD2 , ZD3), (XD3, YD3 , ZD3)}
Грань E = {(XE0, YE0 , ZE0), (XE1, YE1 , ZE1), (XE2, YE2 , ZE3), (XE3, YE3 , ZE3)}
Грань F = {(XF0, YF0 , ZF0), (XF1, YF1 , ZF1), (XF2, YF2 , ZF3), (XF3, YF3 , ZF3)}
Методы и алгоритмы трехмерной графики
Рис. Номера вершин
Второй способ описания. Для такого варианта координаты восьми вершин сохраняются без повторов. Вершины пронумерованы (рис.), а каждая грань дается в виде списка индексов вершин (указателей на вершины).
Оценим затраты памяти:
П2 = 8 3 Рв + 6 4 Риндекс
где Рв – разрядность координат вершин, Риндекс – разрядность индексов.
Третий способ описания (рис.).
Этот способ (в литературе его иногда называют линейно-узловой моделью) основывается на иерархии: вершины – ребра – грани.
Оценим затраты памяти:
П3 = 8 3 Рв + 12 2 Ринд.вершин + 6 4 Ринд. ребер
где Рв – разрядность координат, Ринд.вершин и Ринд. ребер – разрядность индексов вершин и ребер соответственно.
Методы и алгоритмы трехмерной графики
Рис.. Линейно-узловая модель
Для сравнения объемов памяти этих трех вариантов необходимо определиться с разрядностью данных.
Пусть разрядность координат и индексов составляет четыре байта. Например, тип чисел с плавающей точкой float для координат и целому типу long для индексов. Тогда затраты памяти в байтах составляют:
П1= 6х4х3х4= 288,
П2= 8х3х4+6х4х4= 192,
П3= 8х3 х4+ 12х2х4+6х4х4=288.
Пусть для координат отведено 8 байтов (тип с плавающей точкой double), а для индексов — 4 байта. Тогда:
6х4х3х8=576,
8х3х8 +6х4х4 ==288,
8х3х8 +12х2х4+6х4х4= 384.
Методы и алгоритмы трехмерной графики
Когда разрядность для координат больше, чем для индексов, то ощутимо преимущество второго и третьего вариантов. Наиболее экономичным можно считать второй вариант. Это для куба.
Для других типов объектов соотношение вариантов может быть иным. Кроме того, необходимо учитывать варианты построения структур данных: использован ли единый массив для всех объектов, или же для каждого объекта предназначен отдельный массив и т.д..
Скорость вывода полигонов. Если для полигонов необходимо рисовать линию контура и точки заполнения, то первый и второй варианты близки по быстродействию — и контуры, и заполнения рисуются одинаково.
Отличия в том, что для второго варианта сначала надо выбирать индекс вершины, замедляет процесс вывода. В обоих случаях для смежных граней повторно рисуется общая часть контура.
Для третьего варианта можно — каждую линию рисовать только один раз, если в массивах описания ребер предусмотреть бит, означающий, что это ребро уже нарисовано. Преимущество третьего варианта по быстродействию.
При этом решаем проблему искажения стиля линий, если линии контуров не сплошные.
Топологический аспект. Представим, что имеется несколько смежных граней. Что будет, если изменить координаты одной вершины в структурах данных? Результат приведен на рис..
Методы и алгоритмы трехмерной графики
Первый, второй и третий варианты
Рис. Результат изменения координат одной вершины
Поскольку для второго и третьего вариантов каждая вершина сохраняется в одном экземпляре, то изменение ее координат автоматически приводит к изменению всех граней, в описании которых сохраняется индекс этой вершины. Это полезно, например, в геоинформационных, системах при описании соседних земельных участков или других смежных объектов.
Подобного результата можно достичь и при структуре данных, соответствующей первому
варианту. Можно предусмотреть поиск других вершин, координаты которых совпадают с координатами точки A.
Иначе говоря, поддержка такой операции может быть обеспечена как структурами данных, так и алгоритмически.
Однако когда нужно разъединить смежные грани, то для второго и третьего вариантов это сложнее, чем для первого — необходимо записать в массивы новую вершину, новые ребра и определить индексы в массивах граней.