Анализ
видимости. Постановки задач и примеры алгоритмов.
Одной из важнейших
задач при визуализации сложных трехмерных сцен является определение того, какие части объектов (ребра, грани), находящихся
в трехмерном пространстве, будут видны при заданном способе проектирования, а
какие закрыты от наблюдателя другими объектами. В качестве возможных видов
проектирования традиционно рассматривается параллельное
и центральное (перспективное). Плоскость,
на которую осуществляется проектирование, называют картинной.
Задача удаления невидимых линий и поверхностей достаточно
сложна и зачастую требует значительных объемов вычислений. Существует большое
число различных методов решения этой задачи, включая и аппаратные.
Эти методы
различаются по следующим основным параметрам.
1.
По способу представления объектов:
● аналитические
(явные и неявные);
● параметрические;
● полигональные.
2.
По способу визуализации сцены.
При построении каркасных изображений (wireframe – рисуются только ребра) используются методы удаления невидимых линий (ребер каркасных изображений), для
визуализации сплошных изображений (solid – рисуются
закрашенные грани) – методы удаления невидимых поверхностей (граней сплошных изображе-
ний).
3.
По пространству, в котором производится анализ видимости:
● методы,
работающие непосредственно в пространстве самих объектов;
● методы,
работающие в пространстве картинной плоскости, т.е. работающие с проекциями объектов.
4.
По виду получаемого результата (его точности):
● набор
видимых областей или отрезков, заданный с машинной точностью (имеет непрерывный
вид);
● информация
о ближайшем объекте для каждого пиксела экрана (имеет
дискретный вид).
Методы первого
класса дают точное решение задачи удаления невидимых линий и поверхностей,
никак не привязанное к растровым свойствам картинной плоскости. Они могут
работать как с самими объектами, выделяя те их части, которые видны, так и с их
проекциями на картинную плоскость, выделяя на ней области, соответствующие
проекциям видимых частей объектов, и, как правило, практически не привязаны к
растровой решетке и свободны от погрешностей дискретизации.
Существуют следующие алгоритмы
удаления поверхностей:
·
Алгоритм Робертса
В объектном пространстве первый этап – удаление граней, ребер закрываемых самим телом. Второй этап – проверка видимых ребер на закрытие другими телами. Вычислительная трудоемкость ~n2 (количество объектов в сцепе). Условие алгоритма – все тела выпуклые. p = [a b c d] - плоскость
a
b
ax + by
+ cz + d = 0
[ x y z1 ] c = 0
или [ x y z1 ] [ p ]T =
0
d
a1 .
. . an
b1 bn
V = c1 cn матрица тела [ S ] = [ x y z1
]
d1 dn
>
[s] [p]T = 0 по какую сторону от плоскости
<
В алгоритме Робертса предполагается, что точки внутри дают > 0.
Чтобы этого добиться нужны коррективные уравнения.
Основывается на использовании дополнительного массива, буфера в памяти, в котором сохраняются координаты точек Z для каждого пиксела растра. Координата Z соответствует расстоянию точек пространственных объектов до плоскости проецирования. Например, она может быть экранной координатой Z в системе экранных координат (X, Y, Z), если ось Z перпендикулярна плоскости экрана.
Рассмотрим алгоритм рисования объектов по этому методу.
Пусть чем ближе точка в пространстве к плоскости проецирования, тем больше значение Z:
ü сначала Z-буфер заполняется минимальными значениями;
ü затем начинается вывод всех объектов, причем порядок вывода объектов не имеет значения – для каждого объекта выводятся все его пикселы в любом порядке;
ü во время вывода каждого пиксела по его координатам (X, Y) находится текущее значение Z в Z-буфере;
ü
если рисуемый пиксел имеет
большее значение Z,
чем значение в Z-буфере,
то, следовательно, эта точка ближе к
наблюдателю. В этом случае пиксел действительно
рисуется, а его
Z-координата записывается
в Z-буфер.
Таким образом, после рисования всех пикселов всех объектов растровое изображение будет состоять из пикселов, которые соответствуют точкам объектов с самыми большими значениями координат Z, т.е. видимые точки ближе всех к зрителю.
Этот метод прост и эффективен благодаря тому, что не требует сортировки объектов или их точек. При рисовании объектов, которые описываются многогранниками или полигональными сетками, манипуляции со значениями Z-буфера легко совместить с выводом пикселов заполнения полигонов плоских граней.
В отличии от алгоритма z-буфера, который может обрабатывать многоугольники, поступающие в произвольном порядке, в алгоритме "художника" многоугольники сначала упорядочиваются в направлении от заднего плана к переднему. В случае когда пары многоугольников не удается достаточно просто упорядочить, они подразделяются на части до тех пор, пока получившиеся части не позволят это сделать. Затем многоугольники проецируются и "раскрашиваются" в буфере кадров в порядке от заднего плана к переднему так, чтобы многоугольники, находящиеся ближе к точке наблюдения, правильно закрывали более удаленные многоугольники и при этом не требовались дополнительные вычисления.
Довольно распространенная характеристика удаленности для грани ABC - это среднее значение z, mid_z = (A.z+B.z+C.z)/3. Вот и весь алгоритм. Просто, и обычно достаточно быстро.
Существует, правда, несколько проблем.
Во-первых, при
некотором расположении граней этот алгоритм вообще не может дать правильного
результата - в каком порядке грани не рисуй, получится неправильно. Вот
стандартный пример.
Во-вторых, при некотором расположении граней
и использовании среднего значения z как
характеристики удаленности алгоритм тоже дает неправильный результат. Пример
чуть ниже. В этом случае горизонтальную грань надо отрисовывать
второй, но по среднему значению z она лежит дальше и
таким образом получается, что ее надо отрисовывать
первой. Возможные пути решения этой проблемы - какие-то изменения характеристики
удаленности, либо моделирование, не вызывающее таких ситуаций.
И наконец, при использовании этого алгоритма
отрисовываются вообще все грани сцены, и при большом
количестве загораживающих друг друга граней мы будем тратить большую часть
времени на отрисовку невидимых в конечном итоге
частей. То есть совершенно впустую. В таком случае целесообразно использовать
какие-то другие методы (например BSP и PVS, порталы, и т.д).
· Алгоритмы построчного сканирования:
Объем памяти для строки буфера кадра 1х1024х3Б для z-буфера 1х1024х20/zбит.
Инициализация: фон для текущей обрабатываемой строки буфера и z min ( - ¥) для строки z-буфера. Определяется пересечение строк с проекцией на xy с каждого многоугольника,т.е. возникает пара пересечений.
Для каждого пикселя между этими пересечениями (концами пары)
Сравнение с z в буфере.
Если глубина > z-буфера, то точка отрезка видима,занесение в
кадр и корректировка z-буфера в этой позиции.
Для повышения эффективности можно использовать список
активных многоугольников.
2. Интервальный алгоритм
построчного сканирования.