Конспект лекций по компьютерной графике. Конспект лекций по дисциплине Компьютерная графика
 Скачать 16.3 Mb.
|
7.2. Визуализация трехмерных объектовЛюбой трехмерный объект может быть изображен по-разному и различными способами. В одном случае нужно показать форму объекта, во втором – внутреннюю структуру объекта, в третьем имитировать реальную действительность, в четвертом – возбудить воображение зрителя чем-то неизвестным. Условно разделим способы визуализации по характеру изображений и по степени сложности соответствующих алгоритмов на такие уровни: 1. Каркасная визуализация 2. Показ поверхностей в виде многогранников с плоскими гранями или сплайнов с удалением невидимых точек 3. То же что и для второго уровня, плюс сложное закрашивание объектов для имитации отражения света, затенения, прозрачности, использование текстур. Простейшая, каркасная, визуализация часто используется в процессе редактирования объемных объектов. Визуализация второго уровня используется для упрощенного показа объемных объектов. Например, для графиков функций z=f(x,y) (в виде рельефа поверхности) часто достаточно показать все грани сетки одним цветом, зато нужно обязательно удалить невидимые точки. Это более сложная процедура в сравнении с выводом каркасного изображения. Сложность процесса графического вывода возрастает по мере приближения к некоторому идеалу — созданию полной иллюзии естественных, живых, реалистических изображений. Усилия многих ученых и инженеров всего мира направлены на разработку методов и средств достижения этой цели. Здесь полнее всего ощущается связь компьютерной графики с естественными науками, с дисциплинами, посвященными изучению окружающего мира. Например, для создания реалистических изображений нужно принимать во внимание законы оптики, которые описывают свет и тень, отражение и преломление. Компьютерная графика находится на стыке многих дисциплин и разделов науки. 7.2.1 Каркасная визуализацияКаркас обычно состоит из отрезков прямых линий — ребер многогранника, хотя можно строить каркас и на основе кривых, в частности сплайновых кривых Безье. Все ребра, которые показаны в окне вывода, видно — как ближние, так и дальние. Для построения каркасного изображения надо знать координаты всех вершин в мировой системе координат. Потом превратить координаты каждой вершины в экранные координаты в соответствии с выбранной проекцией. Потом выполнить цикл вывода в плоскости экрана всех ребер как отрезков прямых (или кривых), соединяющих вершины. 7.2.2 Показ с удалением невидимых точекЗдесь мы будем рассматривать поверхности в виде многогранников или полигональных сеток. Известны такие методы показа с удалением невидимых точек: сортировка граней по глубине, метод плавающего горизонта, метод Z-буфера и т.п. Сортировка граней по глубине. Это означает рисование полигонов граней в порядке от самых дальних к ближним. Этот метод не является универсальным, так как иногда нельзя четко различить, какая грань ближе (рис. 7.16). Известны модификации этого метода, которые позволяют корректно рисовать подобные грани. Метод сортировки по глубине эффективен для показа поверхностей, заданных функциями z=f(x,y).  Рис. 7.16. В каком порядке рисовать грани? Поверхность нарисована четырехуголными граниями. В общем виде алгоритм сортировки по глубине выглядит следующим образом. Грани после разбиения сортируются по минимальному расстоянию до экранной плоскости, и выводятся в порядке их приближения (z-буфер). Если же объекты пересекаются, то алгоритм несколько усложняется и проверяется еще ряд тестов перед выводом на экран некоторой грани P. Надо убедиться, что никакая другая грань Q не закроет P.
-на ось Oy?
 Рис. 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, т.е. у1<у2. Из этого следует, что линия 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 (ближняя половина). Однако за повышение скорости здесь приходится платить точностью вычисления глубины -она уменьшается вдвое.
Несмотря на кажущуюся простоту, эта задача является достаточно сложной. Существует 2 основных подхода к решению задачи: первый – заключается в определении точек объекта (пикселей), которые вдоль направления проектирования ближе всего расположены к картинной плоскости; второй – заключается в непосредственном сравнении объектов друг с другом для выяснения видимых частей. Существует много смешанных методов, которые объединяют оба эти подхода. О  тсечение нелицевых гранейПусть для каждой грани объекта задан единичный вектор внешней нормали  , а вектор  - задает направление проектирования. Если нормаль грани с вектором составляет тупой угол, то эта грань заведомо не может быть видна.При параллельном проектировании: это можно записать как скалярное произведение  . Рис. 7.18. Лицевые и нелицевые грани При центральном проектировании : с центром в точке Е, для любой точки Р вектор проектирования  , а для определения, является ли грань лицевой или нет? Достаточно взять любую точку Р на ней и проверить условие . Знак этого скалярного произведения не зависит от выбора точки грани, а определяется тем, в каком полупространстве относительно плоскости, содержащей данную грань, лежит центр проектирования.Если строится только один выпуклый многогранник, то задача может быть решена этим способом. Если строится комбинация объектов, то используя этот подход можно хотя бы сократить вдвое количество рассматриваемых граней. Алгоритм: 1 – сначала отбрасываются все ребра, обе грани которых не являются лицевыми, т.е. они заведомо невидны. 2 – проверяются все оставшиеся ребра со всеми гранями многоугольника на закрывание:
А  лгоритм можно значительно сократить (имеем в виду количество проверок) если экранную плоскость разбить на клетки, и для каждой клетки составить список граней, проекции которых имеют непустое пересечение с этой клеткой. Тогда для произвольного ребра сначала находятся все клетки, в которые попадает проекция этого ребра, и, следовательно, рассматриваются не все грани, а только те, которые содержатся в списке данных клеток. При этом подходе требуется время для разбиения и составления списка, но алгоритм работает эффективней. А  лгоритм Аппеля. Рис. 7.19. Контурная линия Здесь вводится понятие количественной невидимости, как количество граней, закрывающих вершину (точку). Если количественная невидимость равна нулю, то точка видима. Количественная невидимость точек ребра при прохождении так называемой контурной линии может изменяться. Берется какая-нибудь вершина и прослеживается изменение количественной невидимости вдоль каждого из ребер, выходящих из этой вершины. Эти ребра проверяются на прохождение позади контурной линии. Где количественная невидимость равна нулю, ребро сразу рисуется. Если не равно нулю, то проверяется количественная невидимость для всех ребер, выходящих из новой вершины, и. т. д. Этот алгоритм более эффективен, чем алгоритм Робертса, так как количество ребер, входящих в контурную линию, намного меньше общего числа ребер. Методы двоичного разбиения пространства. Пусть некоторая плоскость в объектном пространстве разбивает множество всех граней на два не пересекающихся множества (кластера) по одну и по другую сторону от этой плоскости. При этом очевидно, что ни одна из этих граней, лежащих в пространстве, не содержащем наблюдателя, не может закрыть собой грань, находящуюся в другом полупространстве (где наблюдатель). Сначала выводятся грани из дальнего кластера, затем из ближнего. Разбиение продолжается до тех пор, пока в каждом кластере не останется по одной грани. Обычно в качестве разбивающей плоскости рассматривают плоскость, проходящую через одну из граней. При этом реально множество граней разбивается не на 2 части, а на 4:
Каждый узел дерева разбиения граней можно представить структурой. Процесс построения дерева заключается в выборе грани, проведении через нее плоскости и разбиение всех граней. В процессе выбора граней следует придерживаться 2 критериев:
Эти критерии взаимоисключающие - и надо выбрать компромисс. Преимущество этого метода - полная независимость от положения центра проектирования, что необходимо при построении изображений одной сцены, но с разных точек наблюдения. Метод построчного сканирования. Это еще один метод, который успешно используется для создания компьютерных игр (типа прохода по лабиринту, когда вся сцена представляет собой прямоугольный лабиринт с постоянной высотой пола и потолка и набором вертикальных стен). Рассматривается сечение сцены горизонтальной (вертикальной) п  лоскостью, проходящей через центр проектирования.Каждая линия - однозначно определяет одну вертикальную плоскость. Среди всех пересечений видимым будет только одно – ближайшее – плоскостью, проходящей через центр проектирования. Каждая линия – однозначно определяет одну вертикальную плоскость. Среди всех пересечений видимым будет только одно – ближайшее.   Рис. 7.20. Построчное сканирование Алгоритм Варнака (Вариока). Вся видимая часть картинной плоскости разбивается на 4 равные части и проверяется:
Когда ни одно из условий не выполнено, часть разбивается еще на 4 части и т. д., пока размер части больше, чем размер пикселя. Когда часть равна одному пикселю, явно находится ближайшая к ней грань и закрашивается.
Рис. 7.21. Части алгоритма Варнака Отсечение отрезка. Алгоритм Сазерленда-Кохена. Рассмотрим теперь случай, когда необходимо отсечь линии, выходящие за границы окна вывода. Простой и эффективный алгоритм отсечения отрезков по границе произвольного прямоугольника называется алгоритмом Сазерленда - Кохена. Он заключается в разбиении всей плоскости на 9 областей. Определив, в какие области попали концы отрезка, легко понять, где именно необходимо отсечение. Для точки Р ( х ,у ) соответствует 4 - битовый код , причем каждый бит соответствует определенному положению . КОД: В3 В2 В1 В0 В3 = (х B2 = (x > x max ) B0 = ( y > y max ) Идея алгоритма заключается в том, что отрезок анализируется на предмет пересечения поочередно со всеми сторонами окна. Если пересечение существует, то отбрасывается часть отрезка между концом Р1 (вн. окна) и найденной точкой пересечения Рn (Xn , Yn). Причем в алгоритме отсечения рассматриваются только те отрезки, видимость которых неочевидна. F -переменная, определяющая вид отрезка, причем:  0, отрезок горизонтальный  -1, отрезок вертикальный  1, иначе |
рань не закрывает ребро и оно выводится.
рань полностью закрывает ребро и оно удаляется из списка рассматриваемых.
рань частично закрывает ребро, тогда ребро разбивается на части, из которых видимыми могут быть не более двух частей. Само ребро удаляется из списка, но в список проверенных ребер добавляются те его части, которые не закрываются гранью.
