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

Лекция 14

Методы и алгоритмы трехмерной графики.
Модели описания поверхностей

Понятие "трехмерная графика" подразумевает не способы построения собственно трехмерных объектов, а их изображения на плоскости. Истинно трехмерные способы отображения объектов пока что недостаточно широко распространены.

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

Аналитическая модель поверхности

Аналитической моделью называется описание поверхности математическими формулами:

z=f(x,y) – описание с помощью функции,

F(x,y,z)=0 – описание с помощью неявного уравнения.

Зачастую используется параметрическая форма описания поверхности:

Рекомендуемые материалы

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

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

Параметрическое описание можно задать таким образом, что формула не будет существенно изменяться (усложняться) при поворотах поверхности,  и ее масштабировании.

В качестве примера рассмотрим аналитическое описание поверхности шара.

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

– третья степень – наименьшая из степеней, позволяющих описывать любую форму;

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

Сплайны, как правило, задают параметрически.

Рассмотрим одну из разновидностей сплайнов – сплайн Безье. В обобщенной форме (степени m*n):

где P_ij – опорные точки-ориентиры, 0 £ s £ 1,  0 £ t £ 1,  C_mⁱ и C_n^j  – коэффициенты бинома Ньютона, которые рассчитываются по формуле

Кубический сплайн Безье соответствует значениям m=3, n=3. Для его определения необходимо 16 точек-ориентиров P_ij; коэффициенты C_mⁱ и C_n^j  равны 1, 3, 3, 1  при  i, j = 0, 1, 2, 3.

Аналитическая модель наиболее пригодна для многих операций анализа поверхностей.

Достоинства  модели (с позиций КГ):

● легкость расчета координат каждой точки поверхности, нормали;

● небольшой объем данных для описания достаточно сложных форм.

Недостатки:

● сложность формул описания с использованием функций, которые медленно вычисляются на компьютере, снижают скорость выполнения операций отображения;

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

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

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

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

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

Двумя вершинами задается вектор.

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

Несколько граней составляют объемный объект в виде полигональной поверхности – многогранник или незамкнутую поверхность (в литературе часто используется название "полигональная сетка").

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

Положительные черты векторной полигональной модели:

● удобство масштабирования объектов. При увеличении или уменьшении объекты выглядят более качественно, чем при растровых моделях описания. Диапазон масштабирования определяется точностью аппроксимации и разрядностью чисел для представления координат вершин;

● небольшой объем данных для описания простых поверхностей, которые адекватно аппроксимируются плоскими гранями;

● необходимость вычислять только координаты вершин при преобразованиях систем координат или перемещении объектов;

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

Недостатки:

● сложность алгоритмов визуализации для создания реалистичных изображений; сложность алгоритмов выполнения топологических операций, таких, например, как разрезы;

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

Воксельная модель

Воксельная модель – это трехмерный растр. Подобно тому, как пикселы располагаются на плоскости двумерного изображения, вокселы образуют трехмерные объекты в определенном объеме. Воксел – это элемент объема (voxel – volume element).

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

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

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

Недостатки воксельной модели:

● большое количество информации, необходимой для представления объемных данных (например, объем 256х256х256 имеет небольшую разрешающую способность, но требует свыше
16 млн вокселов);

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

● как и для любого растра, возникают проблемы при увеличении или уменьшении изображения. Например, при увеличении ухудшается качество изображения.

Равномерная сетка

Эта модель описывает координаты отдельных точек поверхности следующим способом. Каждому узлу сетки с индексами
(i, j)  приписывается значение высоты z_ij. Индексам (i, j)  отвечают определенные значения координат (x, y). Расстояние между узлами одинаковое – dx  по оси x,  dy по оси  y. Фактически такая модель – это двумерный массив, растр, матрица, каждый элемент которой сохраняет значение высоты.

Не каждая поверхность может быть представлена этой моделью. Если в каждом узле (i, j) записывается только одно значение высоты, то это означает, что поверхность описывается однозначной функцией  z = f (x, y). Иначе говоря, это такая поверхность, которую каждая вертикаль пересекает только один раз. Не могут моделироваться также вертикальные грани. Необходимо заметить, что сетка может быть задана не только в декартовых координатах. Например, для того чтобы описать поверхность шара однозначной функцией, можно использовать полярные координаты. С помощью равномерной сетки часто описывают рельеф земной поверхности.

Положительные черты равномерной сетки:

● простота описания поверхностей;

● возможность быстро узнать высоту любой точки поверхности простой интерполяцией.

Недостатки равномерной сетки:

● поверхности, которые соответствуют неоднозначной функции высоты в узлах сетки, не могут быть смоделированы;

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

Неравномерная сетка. Изолинии

Неравномерной сеткой называется модель описания поверхности в виде множества отдельных точек {(x₀, y₀, z₀), (x₁, y₁, z₁), …,(x_n-1, y_n-1, z_n-1)}, принадлежащих поверхности. Эти точки могут быть получены, например, в результате измерений поверхности какого-нибудь объекта с помощью определенного оборудования. Такую модель можно считать обобщением для некоторых рассмотренных выше моделей. Например, векторная полигональная модель и равномерная сетка могут считаться разновидностями неравномерной сетки.

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

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

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

● находим первые три самые близкие друг к другу точки - получаем одну плоскую треугольную грань;

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

Это – общая схема триангуляции. В литературе можно встретить множество алгоритмов триангуляции, сводящихся к описаному выше. Один из наиболее распространенных – триангуляция Делоне.

Описание поверхности треугольными гранями можно уже считать разновидностью векторной полигональной модели. В англоязычной литературе для ее названия используется аббревиатура TIN (Triangulated Irregular Network). После триангуляции получаем полигональную поверхность, отображение которой выполнить уже достаточно просто.

Рассмотрим еще один из вариантов описания поверхности – изолинии высоты. Любая изолиния состоит из точек, представляющих одно числовое значение какого-то показателя, в данном случае значение высоты. Изолинии высоты также можно рассматривать как контуры разреза поверхности горизонтальными плоскостями (поэтому для изолиний высоты часто применяется название "горизонтали"). Описание поверхности изолиниями высоты часто используется, например в картографии. Для описания поверхности можно использовать не только изолинии высоты, но и другие, например x- или y-изолинии.

В компьютерных системах изолинии часто описываются векторно – полилиниями. Используются также изолинии в виде сплайновых кривых.

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

Положительные черты неравномерной сетки:

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

● применение изолиний на картах и планах позволяет наглядно отображать рельеф поверхности.

Недостатки:

● невозможность или сложность выполнения многих операций над поверхностями;

● сложность алгоритмов преобразования в другие формы описания поверхностей.

Моделирование объектов в системах КГ

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

Для повышения скорости визуализации (рендеринга) на практике многоугольники разбивают на простейшие фигуры – треугольники, поскольку они обладают двумя важнейшими свойствами: всегда выпуклые и всегда плоские. Этот процесс получил название тесселяция сложных поверхностей (High Order Surface Tessellation).

Ещё посмотрите лекцию "Лекция 18" по этой теме.

Многие  программы  трехмерной графики позволяют строить

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

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

Если вектор нормали направлен к плоскости визуализации, эта сторона объекта считается передней и проецируется на плоскость. В противном случае треугольник не отображается, так как считается невидимым.

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

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