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

      Из-за того, что размер и точность чисел  ограничен, необходимо наложить некоторые условия на глубину. Обычно, глубина хранится в виде целого числа, принимающего значения [0..ZBmax]. Тогда, если глубна характеризуется Z- координатой, значение для Z-буфера рассчитывается по формуле V(Z)=Z/Zmax* ZBmax. Цена младшего разряда (дискретность) d для числа V будет Zmax/ZBmax (500/65536~0.01). Для обратной величины V(Z)=(1-k/Z)* ZBmax. Здесь k вычисляется исходя из Zmin. ZV=0 => k=Zmin. Цена младшего разряда не постоянна V(Z+d)-V(Z)=1 => d=Z*Z/(k*ZBmax-Z) = Z*Z/(Zmin*ZBmax-Z) . С увеличением Z цена возрастает, и максимальная цена будет в Zmax (500*500/(0.1*65535-500)=41), а минимальная в Zmin (d=Zmin/(ZBmax-1))=0.1/65536=1e-6), это значит, что последние объекты в последних 40 метрах будут иметь одинаковое значение глубины. Чтобы избежать этого выбирают меньшие Zmax и большие Zmin(100,1=>0.15). Либо увеличение разрядной сетки (до 24-х или 32-х разрядов (500,0.1,24 => 500*500/0.1*16000000=0.15)).

      В общем случае алгоритм Z-буфера не позволяет работать с полупрозрачными объектами. Обычно их выводят после вывода непрозрачных, в порядке от дальних к ближним, проверяя Z-буфер. Но можно несколько модифицировать и сам алгоритм, для этого в каждом пикселе добавляется упорядоченный по глубине список прозрачных пикселей. Если в обычном Z-буфере каждому пикселу соответствует пара (С,Z), где C-цвет, Z-глубина, то в модифицированном - (С,Z,t,next), где t-степень прозрачности, next – указатель на следующий элемент в списке. Сначала строится Z-буфер, а затем рисуются все пиксели со списками от дальнего элемента к ближнему.

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

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

Методы  построчного сканирования 

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

        
 
 
 
 
 
 
 
 
 

      Определить, какие грани попадают в строку i очень просто, достаточно определить, попадает ли Y-координата центров пикселей этой строки в интервал  между минимальной и максимальной Y-координатами точек грани Ymin<= i+0.5 <Ymax. Можно поступить следующим образом, при растеризации очередной грани, вместо того, чтобы рисовать спан его заносят в список спанов соответствующей ему строки (ListSpans[i]). Но это требует больших затрат по памяти (нужно хранить все спаны всех граней). Можно работать более эффективно, если воспользоваться когерентностью в картинной плоскости. Достаточно занести каждую грань в списки тех строк, в которые попадает ее первый спан (ListFaces[i]). Строки выводятся последовательно сверху вниз, существует список активных граней ActiveFaces. При переходе на очередную строку i из этого списка выбрасываются все грани, которые заканчиваются в этой строке (Ymax < i+0.5) и заносятся все грани из списка начинающихся в этой строке ListFaces[i]. Затем рассчитываются спаны для всех граней из ActiveFaces.  В каждой грани нужно хранить все параметры для формирования следующего спана (s1,s2,k1,k2 и т.д.).

      Наконец, можно хранить списки не граней а  ребер. Есть списки начинающихся ребер  ListEdges[i] и список активных ребер ActiveEdges. Очевидно, что ребра каждой грани можно разделить на три группы: левые, правые и горизонтальные. Горизонтальные ребра – не пересекают горизонтальных прямых, проходящих через центры пикселов и отбрасываются. Левые ребра ограничивают грань слева, правые – справа. Для каждой строки грань ограничена ровно двумя ребрами – левым и правым. Поэтому для получения спана нужно лишь знать эту пару, для этого в ребро заносят указатели на грань, а в грани – два указателя на активные ребра.

        При переходе на очередную строку i из списка ActiveEdges выбрасываются все ребра, которые заканчиваются в этой строке (Ymax < i+0.5) и заносятся все ребра из списка начинающихся в этой строке ListEdges[i]. Указатели на закончившиеся ребра удаляются из соответствующих полей граней, которым они соответствуют, а указатели на начинающиеся ребра наоборот заносятся в эти поля. Затем рассчитываются спаны для всех граней, которым соответствуют ребра из ActiveEdges. При этом, пары ребер можно определить либо выбирая из списка только левые (это определяется при расчете ребер) и строя спаны от них до соответствующих правых ребер. Либо отсортировать активные ребра по возрастанию x, тогда первое встреченное ребро будет левым, для него следует выбрать правое, и пометить, его, чтобы не выбрать снова.

struct Edge { Face *face; float x,dx; int Ymax; Edge *next,*prev; };

struct Face { Edge *active_edges[2]; }; 
 
 

 
 
 
 
 
 
 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Одномерный  Z-буфер 

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

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

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

Список  видимых спанов (S-буфер) 

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

• проекции спанов на строку не пересекаются;
• спан полностью закрыт другим спаном –  он игнорируется;
• спан частично закрыт другим спаном –  он отсекается;
• два спана пересекаются – они оба отсекаются;

 

        
 
 
 

      Здесь тоже можно использовать когерентность, например, заносить видимые спаны (на предыдущей строке, кадре) раньше невидимых.  

Сортировка  ребер 

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

      0:

       A:AC

      B:AC,BD

      C:CG,BD

      D:CG,DF

      E:EI,CG,DF

      F:EI,CG,FH

      G:EI,FH

      H:EI

      I: 
 
 
 
 
 
 

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

      Этот алгоритм позволяет выводить и полупрозрачные полигоны.  
 

Метод потенциально видимых  множеств PVS (Potentially Visible Set) 

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

Метод порталов 

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

• отобразить все объекты текущего объема;
• отсечь все порталы, ведущие из текущего объема по текущему порталу и рекурсивно вызвать себя для каждого объема, в который ведут эти порталы;

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

      

        
 
 
 
 
 
 
 
 

Метод иерархических подсцен 

      Похож на метод порталов, только порталы  в этом случае связывают не выпуклые объемы одной сцены, а несколько  подсцен. Причем каждая сцена может  храниться и выводиться наиболее подходящим для нее образом. Например, внутренние помещения могут использовать PVS и BSP, а открытые поверхности – сортировку. Каждая такая подсцена должна уметь выводить себя через портал произвольной формы, при этом все ее грани отсекаются по этому порталу. Вывод подсцен происходит рекурсивно, как и в предыдущем случае. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Общая схема визуализации сцены 

        
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Лекция  13 

Наложение текстур 

Текстура  – это плоское изображение, которое  накладывается на грани объектов. При этом каждой точке объекта соответствует пара координат на текстуре (u,v). Текстура обычно представляет собой двумерный массив значений цвета, его элементы называют текселами (texture element). Текстурные координаты (u,v) стараются делать независимыми от размеров этого массива, как правило, координаты (0,0) соответствуют верхнему левому, а (1,1) правому нижнему углу текстуры.

Текстуру  накладывают при растеризации граней, при этом центру каждого пиксела  соответствует пара (u,v) по которой из текстуры выбирается определенный элемент u’=u*usize,v’=v*vsize и его цвет заносится в пиксел. С=Texture[v’][u’]. Если одна из координат (u’,v’) выходит за пределы массива, то можно поступить несколькими способами: