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

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

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

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

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).

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

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

d_i = -c_i ◦ S.

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

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

Лекция 16