Визуализация трехмерных изображений

Лекция 15

Визуализация трехмерных изображений

Проецирование трехмерных объектов на картинную
плоскость

Важнейшей операцией при визуализации трехмерной графики является проектирование, поскольку изображение строится на плоской поверхности экрана.

Проектирование – это преобразование, ставящее в соответствие точкам трехмерного пространства точки на некоторой плоскости, называемой картинной.

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

Параллельное проектирование (рис. 25) Пусть уравнение плоскости задано в виде n_xx + n_yy + n_zz + d = 0, где x, y, z – координаты произвольной точки p этой плоскости. Уравнение плоскости может быть записано в виде скалярного произведения векторов: n=(n_x, n_y, n_z) и p=(x, y, z):   (n, p) + d = 0.

Рассмотрим плоскость π: (n, p) + d = 0  в трехмерном пространстве, на которую будет осуществляться проектирование (картинную плоскость). Пусть задан вектор l, вдоль которого будет осуществляться проектирование. При этом будем считать, что (l, n) ≠ 0.

Для нахождения проекции произвольной точки q на плоскость π проведем через точку q прямую с направляющим вектором l. Точка  пересечения этой прямой с плоскостью π – q_пр – является проекцией точки q на плоскость π вдоль направления l.

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

Координаты произвольной точки q' прямой, проходящей через точку q и имеющей направляющий вектор l:

q' = q + tl,        tÎR.

Тогда параметр t точки пересечения этой прямой и плоскости π можно найти, подставив уравнение прямой в уравнение плоскости:

(q + tl, n) + d = 0.

Отсюда получаем

Зная t, можно найти проекцию точки q по формуле  q_пр = q + tl.

Так как параллельное преобразование является аффинным, то его можно задать при помощи матрицы однородного преобразования.

Приведем матрицу канонического параллельного проектирования, осуществляемого на плоскость Oxy  вдоль оси Oz.

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

Перспективное проектирование (рис. 26). Рассмотрим картинную плоскость π: (n, p) + d = 0 . Пусть задана точка c, которую будем называть центром проектирования. Тогда перспективной проекцией точки q назовем точку q_пр пересечения плоскости π с лучом, выходящим из c и проходящим через q при условии, что точка q лежит в положительном полупространстве относительно плоскости π.

Пусть проекцией точки q является точка q_пр. В силу того, что q_пр лежит на отрезке [q, c], справедлива формула

q_пр = (1 - t)c + tq,                    t Î [0, 1].

Тогда из условия принадлежности проекции плоскости получаем

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

Выпишем каноническое уравнение перспективного преобразования. Пусть центр проектирования равен (0, 0, -1)^Т, а картинная плоскость задается уравнением   z = 1.

Тогда проекцией произвольной точки q = (x, y, z) будет точка q_пр=(x/(z+1), y/(z+1), 1)². Это преобразование осуществляется при помощи матрицы:

поскольку

Таким образом, как произвольное аффинное преобразование, так и параллельное и перспективное проектирование могут быть записаны при помощи матриц однородных преобразований.

Уровни визуализации

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

Условно способы визуализации можно разделить по характеру изображений и по степени сложности соответствующих алгоритмов на уровни:

1) каркасная (проволочная) модель;

2) показ поверхностей в виде многоугольников с плоскими гранями или сплайнов с удалением невидимых точек;

3) показ поверхностей с использованием методов закрашивания объектов для имитации отражения света, затенения, прозрачности, наложения текстур.

Простейшая каркасная модель часто применяется в процессе редактирования объемных объектов.

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

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

Каркасная визуализация

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

Для построения каркасного изображения необходимо:

● получить координаты всех вершин в мировой системе координат;

● преобразовать координаты каждой вершины в экранные координаты в соответствии с выбранной проекцией;

● выполнить цикл вывода в плоскости экрана всех ребер как отрезков прямых или кривых, соединяющих вершины.

Показ с удалением невидимых точек. Классификация
методов

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

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

Эти методы различаются по следующим основным параметрам.

1. По способу представления объектов:

● аналитические (явные и неявные);

● параметрические;

● полигональные.

2. По способу визуализации сцены.

При построении каркасных изображений (wireframe – рисуются только ребра) используются методы удаления невидимых линий (ребер каркасных изображений), для визуализации сплошных изображений (solid – рисуются закрашенные грани) – методы удаления невидимых поверхностей (граней сплошных изображе-
ний).

3. По пространству, в котором производится анализ видимости:

● методы, работающие непосредственно в пространстве самих объектов;

● методы, работающие в пространстве картинной плоскости, т.е. работающие с проекциями объектов.

4. По виду получаемого результата (его точности):

● набор видимых областей или отрезков, заданный с машинной точностью (имеет непрерывный вид);

● информация о ближайшем объекте для каждого пиксела экрана (имеет дискретный вид).

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

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

Однако следует иметь в виду, что непрерывные методы, как правило, достаточно сложны.

Методы второго класса (point-sampling methods) дают приближенное решение задачи удаления невидимых линий, определяя видимость только в некотором наборе точек картинной плоскости – в точках растровой решетки. Они очень сильно привязаны к растровым свойствам картинной плоскости и фактически заключаются в определении для каждого пиксела той грани, которая является ближайшей к нему вдоль направления проектирования. Изменение разрешения приводит к необходимости полного перерасчета всего изображения.

Простейший вариант дискретного метода имеет временные затраты порядка Cn, где C – общее количество пикселов экрана,
n – число объектов.

Всем методам второго класса традиционно свойственны ошибки дискретизации (aliasing artifacts). Однако, как правило, дискретные методы отличаются простотой реализации.

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

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

Очень распространенной структурой данных в задачах удаления невидимых линий и поверхностей являются различные типы деревьев: двоичные (BSP-trees), четверичные (Quadtrees), восьмеричные (Octtrees) и др.

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

Рассмотрим поверхности в виде многогранников или полигональных сеток. Для показа с удалением невидимых точек известны следующие методы: сортировка граней по глубине, метод плавающего горизонта, метод Z-буфера, алгоритм Робертса, алгоритм художника и др.

Сортировка граней по глубине предполагает рисование полигонов и граней от самых дальних к самым близким. Он не является универсальным, поскольку иногда нельзя четко различить, какая грань ближе. Метод сортировки по глубине эффективен для показа поверхностей, заданных функциями z = f(x,y).

Метод плавающего горизонта. Грани выводятся в последовательности от ближайших к самым дальним. На каждом шаге границы граней образуют две ломаные линии – верхний горизонт и нижний горизонт. Во время вывода каждой новой грани рисуется только то, что выше верхнего горизонта, и то, что ниже нижнего горизонта. Каждая новая грань поднимает верхний и опускает нижний горизонты. Этот метод часто используется для показа поверхностей, описываемых явным уравнением  z = f (x, y).

Метод Z-буфера основывается на использовании дополнительного массива, буфера в памяти, в котором сохраняются координаты точек Z для каждого пиксела растра. Координата Z соответствует расстоянию точек пространственных объектов до плоскости проецирования. Например, она может быть экранной координатой Z в системе экранных координат (X, Y, Z), если ось Z перпендикулярна плоскости экрана.

Рассмотрим алгоритм рисования объектов по этому методу.

Пусть чем ближе точка в пространстве к плоскости проецирования, тем больше значение Z:

● сначала Z-буфер заполняется минимальными значениями;

● затем начинается вывод всех объектов, причем порядок вывода объектов не имеет значения – для каждого объекта выводятся все его пикселы в любом порядке;

● во время вывода каждого пиксела по его координатам (X, Y) находится текущее значение Z в Z-буфере;

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

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

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

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

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

Идентификация i-й грани заключается в оценке угла видимости j_i=Ð N_i S_i между векторами наблюдателя S_i и внешней нормали N_i. Ячейка является лицевой при остром угле видимости, и это быстро определяется из условия  N_i ◦ S_i > 0 без вычисления самого угла. Порядок вывода лицевых граней произволен.

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

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

Незамкнутая выпуклая каркасная поверхность также может быть изображена модифицированным методом Робертса, если внутренним сторонам ячеек присвоить высший приоритет и определять их видимость по правилу  N_i ◦ S_i < 0, где  N_i – внешняя нормаль к плоскости i-й ячейки.

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

Метод основан на вычислении удаленности (глубины) d_i центров ячеек c_i (в разных вариантах алгоритма используются и другие опорные точки ячеек) от наблюдателя, сортировке и выводе ячеек в порядке уменьшения элементов вектора d. При наблюдателе, находящемся в конечной точке S, глубина точки c_i равна расстоянию

d_i = | c_i - S |,

а в вычислительном аспекте более эффективно использовать квадрат расстояния как скалярное произведение:

d_i² = (c_i - S) ◦ (c_i - S).

Бесплатная лекция: "7. Мутагенез и полиплоидия" также доступна.

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

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

d_i = -c_i ◦ S.

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

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