Анализ видимости. Постановки задач и примеры алгоритмов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Существуют следующие алгоритмы удаления поверхностей:

·         Алгоритм Робертса

В объектном пространстве первый этап – удаление граней, ребер закрываемых самим телом. Второй этап – проверка видимых ребер на закрытие другими телами. Вычислительная трудоемкость  ~n² (количество объектов в сцепе). Условие алгоритма – все тела выпуклые.            p = [a b c d] - плоскость

                                                           a

                                                           b

 ax + by + cz + d = 0         [ x y z₁ ]   c   = 0     или      [ x y z₁ ] [ p ]^T = 0

                                                           d           

        a₁    .  .  .        a_n

        b₁                              b_n

V =   c₁                              c_n          матрица тела                [ S ] = [ x y z₁ ] 

        d₁                               d_n                 

         

            >

[s]  [p]^T = 0     по какую сторону от плоскости                         

            <

В алгоритме Робертса предполагается, что точки внутри дают > 0.

Чтобы этого добиться нужны коррективные уравнения.

• алгоритм z-буфера;

Основывается на использовании дополнительного массива, буфера в памяти, в котором сохраняются координаты точек 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. Алгоритм построчного сканирования с z-буфером.

Объем памяти для строки буфера кадра 1х1024х3Б для z-буфера 1х1024х20/zбит.

Инициализация: фон для текущей обрабатываемой строки буфера и z _min ( - ¥) для строки z-буфера. Определяется пересечение строк с проекцией на xy с каждого многоугольника,т.е. возникает пара пересечений.

Для каждого пикселя между этими пересечениями (концами пары)  

Сравнение с z в буфере.

Если глубина > z-буфера, то точка отрезка видима,занесение в

кадр и корректировка z-буфера в этой позиции.

Для повышения эффективности можно использовать список 

активных многоугольников.

 

 

 

2.   Интервальный алгоритм построчного сканирования.