Показ с удалением невидимых точек

Каркасная визуализация

Визуализация трехмерных объектов

 

Любой трехмерный объект может быть изображен по-разному и различными способами. В одном случае нужно показать форму объекта, во втором – внутреннюю структуру объекта, в третьем имитировать реальную действительность, в четвертом – возбудить воображение зрителя чем-то неизвестным. Условно разделим способы визуализации по характеру изображений и по степени сложности соответствующих алгоритмов на такие уровни:

1. Каркасная визуализация

2. Показ поверхностей в виде многогранников с плоскими гранями или сплайнов с удалением невидимых точек

3. То же что и для второго уровня, плюс сложное закрашивание объектов для имитации отражения света, затенения, прозрачности, использование текстур.

Простейшая, каркасная, визуализация часто используется в процессе редактирования объемных объектов. Визуализация второго уровня используется для упрощенного показа объемных объектов. Например, для графиков функций z=f(x,y) (в виде рельефа поверхно­сти) часто достаточно показать все грани сетки одним цветом, зато нужно обязательно уда­лить невидимые точки. Это более сложная процедура в сравнении с выводом каркасного изображения.

Сложность процесса графического вывода возрастает по мере приближения к некоторо­му идеалу — созданию полной иллюзии естественных, живых, реалистических изображе­ний. Усилия многих ученых и инженеров всего мира направлены на разработку методов и средств достижения этой цели. Здесь полнее всего ощущается связь компьютерной графики с естественными науками, с дисциплинами, посвященными изучению окружающего мира. Например, для создания реалистических изображений нужно принимать во внимание зако­ны оптики, которые описывают свет и тень, отражение и преломление. Компьютерная гра­фика находится на стыке многих дисциплин и разделов науки.

 

Каркас обычно состоит из отрезков прямых линий — ребер многогранника, хотя можно строить каркас и на основе кривых, в частности сплайновых кривых Безье. Все ребра, кото­рые показаны в окне вывода, видно — как ближние, так и дальние.

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

 

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

Сортировка граней по глубине.Это означает рисование полигонов граней в порядке от самых дальних к ближним. Этот метод не является универсальным, так как иногда нельзя четко различить, какая грань ближе (рис. 7.16). Известны модификации этого метода, которые позволяют корректно рисовать подобные грани. Метод сортировки по глубине эффективен для показа поверхностей, заданных функциями z=f(x,y).

 

 

 

Рис. 7.16. В каком порядке рисовать грани? Поверхность нарисована четырехуголными граниями.

В общем виде алгоритм сортировки по глубине выглядит следующим образом.

Грани после разбиения сортируются по минимальному расстоянию до экранной плоскости, и выводятся в порядке их приближения (z-буфер).

Если же объекты пересекаются, то алгоритм несколько усложняется и проверяется еще ряд тестов перед выводом на экран некоторой грани P. Надо убедиться, что никакая другая грань Q не закроет P.

1. Пересекаются ли проекции граней P и любой другой Q
-на ось Ox?

-на ось Oy?

2. Пересекаются ли проекции этих граней на экранной плоскости?

3. Находится ли грань P по другую сторону плоскости, проходящей через Q, чем начало координат (наблюдатель)?

4. Обратное (2), т.е. находится ли Q по ту же сторону от плоскости, проходящей через P, что и начало координат (наблюдатель)?

 
 

Рис. 7.17. Алгоритм сортировки по глубине.

Если хотя бы один из этих тестов отрицательный, то, значит, грани упорядочены верно, и P сравнивают со следующей гранью в списке, а в противном случае грани меняют местами в списке. Для чего проверяют тесты 3. 4.

Метод плавающего горизонта.Здесь, в отличие от предыдущего метода, грани выво­дятся в последовательности от ближних к самым дальним. На каждом шаге границы граней образуют две ломаные линии — верхний горизонт и нижний горизонт. В течение вывода каждой новой грани рисуется только то, что выше верхнего горизонта, и то, что ниже ниж­него горизонта. Соответственно, каждая новая грань поднимает верхний и опускает нижний горизонты. Этот метод часто используют для показа поверхностей, которые описываются функциями z=f(x,y).

В общем виде метод выглядет следующим образом.

Пусть надо построить график функции двух переменных Z=f(x, y), в виде сетки координатных осей.

При параллельном проектировании проекций вертикальной линии является вертикальная линия.

Любая точка P(x, y, z) переходит в точку [(p,e1), (p, e2)] на плоскости экрана, где

e1= (cosφ, sinφ, 0)

e2= (sinφ, sinq, - cosφ sinq, cosq), а направление проектирования:

e3= (sinφ cosq, - cosφ - cosq, sinq), где φє[0, 2π], qє[-π/2, π/2], - углы подобраны так, чтобы плоскость у=у1 была ближе к экранной плоскости, чем у=у2, т.е. у12.

Из этого следует, что линия Z=f(x, yj), не закрывает линию Z=f(x, yi).

Тогда возможен алгоритм, когда линии рисуются в порядке удаления (возрастания у) и при рисовании очередной линии рисуется только та ее часть, которая не закрывается ранее нарисованной.

Для определения частей линий Z=f(x, yк), которые не закрываются ранее нарисованными, вводятся линии горизонта.

Пусть проекцией линии Z=f(x, yк) на плоскость экрана является линия у=ук(х), где (х, у) – это координаты на экране. Тогда линии горизонта определяются как:

На экране рисуются только те части линии у=ук), которые выше укmax) или ниже укmin).

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

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

Для определения порядка вывода граней считают, что грань, лежащая в полосе не может закрыть грань из полосы

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

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

Метод Z-буфера сейчас очень популярен благодаря простоте и эффективности. Совре­менные ЗD-акселераторы аппаратно поддерживают этот метод как на уровне операции, так и памяти. Видеоадаптер имеет собственную память для Z-буфера, доступ к которой осуще­ствляется быстрее, чем к оперативной памяти компьютера. В конвейере графического про­цессора и манипуляции со значениями Z-буфера легко совместить с другими пиксельными операциями для вывода полигонов. Существует разновидность этого метода - для ускоре­ния вычислений используется не Z, а обратное значение (W-буфер).

Укажем некоторые проблемы использования метода Z-буфера.

1. Необходимость выделения дополнительной памяти. Для Z-буфера необходима память объем которой соответствует размерам растра изображения и точности чтения координаты Z. Используют обычно 32, 24 или 16 битов на один пиксел Z-буфера. Например для Z-буфера 1024x768x32 нужно 3 Мбайта. Сейчас такие затраты памяти не
считаются существенными. Если объем памяти _ критичен, то кадровый и Z-буфер разделяют на фрагменты (тайлы) и выполняют визуализацию для любого фрагмента отдельно. Файловая организация Z-буфера может использоваться также и для повышения скорости визуализации.

2. Полная инициализация Z-буфера (запись "самых дальних" значений) перед началом вывода того кадра уменьшает скорость анимации. Тем не менее, часто используется та­кой прием - инициализировать Z-буфер один раз для пары кадров. Это возможно, если разделить полный диапазон значений Z пополам. Например, если полный диапазон зна­чений от 0 до 1, то в первом кадре работать со значениями Z, смещенными в интервал от 1 до 0.5 (дальняя половина), а в следующем кадре — от 0.5 до 0 (ближняя половина). Однако за повышение скорости здесь приходится платить точностью вычисления глуби­ны -она уменьшается вдвое.

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

4. Проблемы с выводом полупрозрачных объектов.

5. Использовать в качестве расстояния координату 2 нельзя при углах обзора 180 градусов и больше. Для цилиндрических и сферических проекций лучше использовать радиаль­ное расстояние от текущей точки объекта до точки схода лучей проецирования.

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

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

второй – заключается в непосредственном сравнении объектов друг с другом для выяснения видимых частей.

Существует много смешанных методов, которые объединяют оба эти подхода.

 

Отсечение нелицевых граней

 

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

При параллельном проектировании: это можно записать как скалярное произведение .

Рис. 7.18. Лицевые и

нелицевые грани

При центральном проектировании : с центром в точке Е, для любой точки Р вектор проектирования , а для определения, является ли грань лицевой или нет? Достаточно взять любую точку Р на ней и проверить условие . Знак этого скалярного произведения не зависит от выбора точки грани, а определяется тем, в каком полупространстве относительно плоскости, содержащей данную грань, лежит центр проектирования.

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

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

Алгоритм:

1 – сначала отбрасываются все ребра, обе грани которых не являются лицевыми, т.е. они заведомо невидны.

2 – проверяются все оставшиеся ребра со всеми гранями многоугольника на закрывание:

 

- грань не закрывает ребро и оно выводится.

- грань полностью закрывает ребро и оно удаляется из списка рассматриваемых.

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

 

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

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

При этом подходе требуется время для разбиения и составления списка, но алгоритм работает эффективней.

 
 

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

Рис. 7.19. Контурная линия

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

Если количественная невидимость равна нулю, то точка видима.

Количественная невидимость точек ребра при прохождении так называемой контурной линии может изменяться.

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

Этот алгоритм более эффективен, чем алгоритм Робертса, так как количество ребер, входящих в контурную линию, намного меньше общего числа ребер.

 

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

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

Сначала выводятся грани из дальнего кластера, затем из ближнего.

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

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

- грань лежит на плоскости;

- пересекает плоскость;

- в положительном пространстве;

- в отрицательной области;

Каждый узел дерева разбиения граней можно представить структурой.

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

- получить более сбалансированное дерево;

- минимизировать количество разбиений.

Эти критерии взаимоисключающие - и надо выбрать компромисс.

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

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

Рассматривается сечение сцены горизонтальной (вертикальной) плоскостью, проходящей через центр проектирования.

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

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

   
 
 
 
 
 
 
 
 
 
 
 


Рис. 7.20. Построчное сканирование

Алгоритм Варнака (Вариока).Вся видимая часть картинной плоскости разбивается на 4 равные части и проверяется:

- эта часть полностью накрывается проекцией ближайшей грани;

- часть не покрывается проекцией ни одной грани.

Когда ни одно из условий не выполнено, часть разбивается еще на 4 части и т. д., пока размер части больше, чем размер пикселя.

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

   
     
     
   

Рис. 7.21. Части алгоритма Варнака

 

Отсечение отрезка. Алгоритм Сазерленда-Кохена.Рассмотрим теперь случай, когда необходимо отсечь линии, выходящие за границы окна вывода.

Простой и эффективный алгоритм отсечения отрезков по границе произвольного прямоугольника называется алгоритмом Сазерленда - Кохена. Он заключается в разбиении всей плоскости на 9 областей. Определив, в какие области попали концы отрезка, легко понять, где именно необходимо отсечение. Для точки Р ( х ,у ) соответствует 4 - битовый код , причем каждый бит соответствует определенному положению .

 

КОД: В3 В2 В1 В0

В3 = (х <x min) B1 = (y < y min)

B2 = (x > x max ) B0 = ( y > y max )

 

Идея алгоритма заключается в том, что отрезок анализируется на предмет пересечения поочередно со всеми сторонами окна. Если пересечение существует, то отбрасывается часть отрезка между концом Р1 (вн. окна) и найденной точкой пересечения Рn (Xn , Yn). Причем в алгоритме отсечения рассматриваются только те отрезки, видимость которых неочевидна.

F -переменная, определяющая вид отрезка, причем:

0, отрезок горизонтальный

-1, отрезок вертикальный

1, иначе

 

 

Глава 8. Реалистическое представление сцен

Основные направления реалистического представления сцен трехмерной графики определяются как:
· синтез реалистичных изображений,

· реалистическое оживление синтезированных объектов (анимация).

В этом разделе будут рассмотрены только некоторые базовые методы синтеза реалистических изображений:

· Модели освещения
· Модели закраски
· Трассировка лучей
· Имитация микрорельефа

· Механизмы отражения света

Другие методы синтеза – прозрачность, тени, задание фактуры, излучательность и т.д. выносятся на самостоятельное изучение.