Лекции по "Компьютерной графике"

Пирамида  зрения 

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

Удаление  нелицевых граней

Если  поверхность задана гранями, то, очевидно, что грани, нормали которых составляют с направлением проектирования острый угол, будут отвернуты от наблюдателя и, следовательно, невидны. Такие грани называются нелицевыми. Нормали лицевых граней направлена на наблюдателя. При параллельном проектировании для нелицевых граней , где N – нормаль, L - направление проектирования (вглубь экрана). При перспективном проектировании для нелицевых граней , где N,D – параметры плоскости, V – точка схода (положение наблюдателя). Для треугольников в экранном пространстве нелицевые грани можно определить по знаку pdp двух его ребер . Если требуется вывести каркасную модель, то будут невидны те ребра, которые принадлежат только нелицевым граням. Удаление нелицевых граней решает задачу удаления невидимых линий полностью только когда требуется вывести один выпуклый полиэдр. В остальных случаях это лишь дополнительное средство, которое, тем не менее, позволяет в среднем в два раза сократить количество обрабатываемых граней. 

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

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

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

Такой алгоритм требует O(N²) времени. Его можно немного ускорить, если описать вокруг граней некоторые ограничивающие тела (обычно это либо параллелепипеды (в картинной плоскости– прямоугольники), с ребрами параллельными осям координат, AABB (Axis Aligned Bounding Box), либо сферы (в картинной плоскости – окружности)). Тогда достаточно сначала проверить пересечение этих тел, и только если они пересекаются, проверять пересечение ребра с гранью. Можно ограничивать не только отдельные ребра или грани, но и их группы (например, объекты), и проверять сначала пересечение тел для групп, и только если они пересекаются – для отдельных объектов. Таким образом, можно построить целую иерархию ограничивающих тел.  

Алгоритм  Аппеля 

Алгоритм  использует понятие количественной невидимости точки – количество лицевых граней, закрывающих данную точку. Очевидно, что видны будут  только те точки, для которых количественная невидимость равна нулю. Для полигональных поверхностей, количественная невидимость изменяется только на контурных линиях проекций этих поверхностей на экран. Это верно только для непересекающихся поверхностей. Контурная линия поверхности образуется ребрами, для которых одна грань лицевая, а другая нелицевая (либо ее просто нет). Для определения видимости ребер некоторой поверхности сначала непосредственно определяется количественная невидимость одной из ее вершин, далее прослеживается изменение количественной невидимости вдоль ребер, выходящих из этой точки. Она изменяется на единицу при прохождении ребра за линией контура. Во входящих точках – увеличивается, в выходящих – уменьшается (для этого контур должен быть направленным). Части ребер с нулевой количественной невидимостью сразу рисуются. Операция повторяется для вершин на концах этих ребер (для них количественная невидимость уже определена) пока не будут проверены все вершины и ребра поверхности.

Алгоритм  Варнака 

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

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

Алгоритм Художника 

Это еще  один пример метода грубой силы. Полигоны просто сортируются и выводятся  в порядке от дальних к ближним. Таким образом, ближайшие к наблюдателю  полигоны рисуются поверх дальних и  получается правильная картина. Такой алгоритм подходит только для отображения сплошных поверхностей, не для каркасных. Сортировка полигонов тоже вещь нетривиальная. Если сортировать вдоль оси Z, то всегда может быть случай неправильной сортировки. Или вообще ее невозможности. Тем не менее, алгоритм достаточно прост и часто используется при небольшом количествах полигонов, одним из его достоинств является возможность обрабатывать полупрозрачные объекты. Предыдущие алгоритмы требуют значительной модификации для такой возможности. Полупрозрачный объект выводится по формуле С=С*t+Cг*(1-t), где С – текущий цвет пикселя, Cг – цвет пикселя прозрачной грани, t – коэффициент прозрачности [0..1]. Очевидно, что для формирования правильной картинки необходимо знать цвет предыдущего пикселя. 

Использование бинарного разбиения  пространства для  сортировки полигонов 

Если в наборе полигонов выбрать одну, то ее плоскость  разбивает все пространство на две  части. Предположим, что эта плоскость  не пересекает остальные полигоны, значит, одна часть полигонов будет лежать с одной стороны от плоскости, а другая – с другой. Тогда, в зависимости, от того, с какой стороны от плоскости находится наблюдатель, можно однозначно определить порядок отрисовки этих групп полигонов. Сначала рисуются полигоны из полупространства, в котором нет наблюдателя, затем полигон с плоскости, и наконец – полигоны из полупространства, в котором находится наблюдатель ((B,C),A,(D,E,F)). Чтобы правильно отсортировать все полигоны – нужно построить дерево таких разбиений. Такое дерево и называется деревом двоичного разбиения пространства (BSP-tree binary space partitioning tree).

      В качестве узлов такого дерева выступают  плоскости (и полигоны лежащие на них), а в качестве листьев –  области, ограниченные этими плоскостями. Для отрисовки дерева его просто обходят, определяя каждый раз положение наблюдателя относительно плоскостей узлов. (B,C,A,F,D,E).

      Для общих случаев, в одной плоскости  могут лежать несколько полигонов (порядок их вывода не имеет значения), плоскости могут пересекать полигоны, тогда такие полигоны режут на две части и каждую добавляют в свое полупространство. При построении дерева стараются, чтобы разница в количестве узлов слева и справа от текущего было минимальной и разрезанных полигонов было как можно меньше. Тогда оно будет сбалансированным, при этом глубина дерева будет минимальной, это обеспечивает минимум проверок плоскостей. Идеальное решение этой задачи требует слишком много времени, поэтому очередная разбивающая плоскость выбирается по максимуму весовой функции f=lie-a*|left-right|-b*cross, где lie – кол-во полигонов лежащих в плоскости, left,right - кол-во полигонов слева и справа от плоскости, cross - кол-во полигонов, которые пересекаются плоскостью, a,b – какие-то весовые коэффициенты. 
 

Трассировка лучей 

Алгоритм состоит в том, что  для каждого пиксела в экране определяется ближайшая грань. Для  этого проверяется пересечение  проектирующей прямой, проходящей центр  пикселя, с гранями всех объектов в сцене и находится ближайшая. Алгоритм достаточно универсален, может работать как с объектами, заданными поверхностями, так и с конструктивной геометрией. Он позволяет эффективно обрабатывать полупрозрачные полигоны. В общем случае, алгоритм требует O(CN) времени, но если применить некоторые оптимизации, вроде иерархии описанных вокруг объектов тел или BSP можно свести время выполнения к O(ClogN), что означает практическую независимость от сложности сцены. Для этого алгоритма можно очень эффективно использовать когерентность, например, если найдено пересечение прямой для текущего пикселя с некоторой гранью, то прямая для соседнего тоже скорее всего пересечется с этой гранью. Значит, можно сначала проверить пересечение с этой гранью, и если оно имеет место, проверять не весь отрезок, а только его часть от наблюдателя до точки этого пересечения. Можно построить иерархию описывающих тел, и проверять пересечение луча сначала с ними, а затем с объектами. Наконец, можно использовать и когерентность по времени, хранить указатели на грани для каждого пиксела, и сначала проверять пересечение с ними, только это требует достаточно много памяти.  

Алгоритм  Z-буфера 

Как и  предыдущий, алгоритм ищет ближайшую  грань для каждого пиксела. Только делает это несколько иначе. Заводится  двумерный массив, каждый элемент  которого соответствует одному пикселу. Этот массив и называется Z-буфером (или буфером глубины). Сначала в него заносят максимальную глубину. Затем отрисовывают все грани сцены. При рисовании очередного пиксела грани, ели значение глубины этого пиксела меньше, чем значение в Z-буфере, то пиксел рисуется, и значение его глубины заносится в Z-буфер.

void PPZB(x,y,z){ if (z<ZBuffer[y][x])  { ZBuffer[y][x]=z; PP(x,y);  } }

Как правило, расчет глубины осуществляется при растеризации очередной грани, т.о. этот алгоритм удаления невидимых поверхностей, практически не требует дополнительных вычислений и выполняется за время O(N). Из-за своей простоты, он хорошо подходит для реализации на графических акселераторах. Тем не менее, алгоритм требует растеризовать все грани в сцене, тогда, как большинство из них могут быть полностью невидимыми, поэтому, как правило, в дополнение к нему используют какие-то дополнительные алгоритмы отброса заведомо невидимых объектов и граней. Кроме того, здесь тоже можно использовать когерентность. Например, если построить вокруг группы граней AABB и проверить по Z-буферу, виден ли он (проверить, все соответствующие ему пикселы, не занося значения в Z-буфер). Если он невиден, то и грани внутри него не видны.

Опять же лучше построить иерархию описывающих тел. Например, описать вокруг всех граней в сцене AABB, затем рекурсивно разбивать его на 8 частей, до тех пор, пока в количество полигонов в текущем AABB не станет достаточно малым, чтобы дальнейшее деление не имело смысла. Получится дерево, узлы – AABB, листья – AABB со списком полигонов в них. Далее, берется начальный AABB дерева (корневой), проверяется на попадание в пирамиду зрения, затем проверяется по Z-буферу, если оказывается, что он виден – тоже самое проделывается для каждого из восьми дочерних AABB. В конце концов, выводятся полигоны в листьях дерева. Важным является порядок обхода дочерних AABB, сначала выводятся ближайшие к наблюдателю, а затем более дальние. Порядок определяется положением наблюдателя относительно плоскостей, разделяющих родительский AABB на дочерние (как в BSP). Выгода от рисования от ближних к дальним в том, что отрисованные  ближние грани будут закрывать дальние.

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

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

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

      Для алгоритма Z-буфера можно использовать совершенно различные параметры, характеризующие глубину. Обычно используются либо координата Z (проекция точки на ось вглубь экрана OZ), либо обратная ей величина 1/Z. Обратную величину можно линейно интерполировать вдоль экрана при перспективном проектировании. Более подробно об этом будет рассказано в лекции, посвященной закрашиванию и наложению  текстур. Чтобы сохранить увеличение значения в Z-буфере с увеличением расстояния до объекта, используют величину 1-k/Z.