617_Zabelin_L.JU._Osnovy_komp'juternoj_grafiki_

10.4.Основные типы проекций

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

из одной точки. При параллельном центр бесконечно удаленная точка и лучи проецирования параллельны. Центральные проекции выглядят более реалистичными по сравнению с параллельными, но не пригодны для определения размеров [19].

Рисунок 10.4.1. – Центральное проецирование

Рисунок 10.4.2. – Параллельное проецирование

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

71

Рисунок 10.4.3. – Точки схода

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

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

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

11.ВИЗУАЛИЗАЦИЯ ОБЪЕМНЫХ ИЗОБРАЖЕНИЙ

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

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

А) Каркасная (проволочная) модель. Простейшая каркасная модель часто применяется в процессе редактирования объемных объектов.

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

72

В) То же, что и для второго уровня, плюс сложное закрашивание объектов; для имитации отражения света, затенения, прозрачности, использование текстур. Сложность процесса графического вывода возрастает по мере приближения к созданию полной иллюзии естественных, живых, реалистичных изображений. Усилия многих ученых и инженеров во всем мире направлены на разработку методов и средств достижения этой цели. В этом плане наиболее полно ощущается связь компьютерной графики с естественными науками, с дисциплинами, посвященными изучению окружающего нас мира. Например, для создания реалистичных изображений необходимо учитывать законы оптики, описывающие свет и тень, отражение и преломление.

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

Для построения каркасного изображения надо знать координаты всех вершин в мировой системе координат. Потом преобразовать координаты каждой вершины в экранные координаты в соответствии с выбранной проекцией. Затем выполнить цикл вывода в плоскости экрана всех ребер как отрезков прямых (или кривых), соединяющих вершины. Для представления каркасных моделей можно использовать следующий способ, при котором не используется качество растрового дисплея – возможность закраски поверхностей. Наиболее известный ранний алгоритм – алгоритм Робертса (1963г.). Работает с только выпуклыми телами в пространстве объектов. Каждый объект сцены представляется многогранным телом, полученным в результате пересечения плоскостей. Т.е. тело описывается списком граней, состоящих из ребер, которые в свою очередь образованы вершинами. Вначале из описания каждого тела удаляются нелицевые плоскости, экранированные самим телом. Затем каждое из ребер сравнивается с каждым телом для определения видимости или невидимости. Т.е. объем вычислений растет как квадрат числа объектов в сцене. Наконец вычисляются новые ребра, полученные при протыкании телами друг друга.

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

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

Классификация алгоритмов удаления: А) По выбору удаляемых частей:

невидимых линий,

ребер,

поверхностей,

объемов.

Б) По порядку обработки элементов сцены:

удаление в произвольном порядке,

в порядке, определяемом процессом визуализации.

73

В) По системе координат:

алгоритмы, работающие в пространстве объектов, когда каждая из N

граней объекта сравнивается с остальными N-1 гранями (объем вычислений » N2),

алгоритмы, работающие в пространстве изображения, когда для каждо-

го пикселя изображения определяется – какая из N граней объекта видна (при разрешении экрана M×M объем вычислений » M2 ×N).

11.3. Сортировка граней по глубине

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

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

Рисунок 11.3.1. – Сортировка граней по глубине

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

Oz.

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

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

Пересекаются ли их проекции на ось Оу?

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

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

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

74

Если хотя бы на один из этих вопросов получен отрицательный ответ, то считаем что эти две грани - Р и Q упорядочены верно, и сравниваем Р со следующей гранью. В противном случае считаем, что эти грани необходимо поменять местами, для чего проверяются следующие тесты:

Находится ли грань Q по другую сторону от плоскости, проходящей через грань Р, чем начало координат?

Находится ли грань Р по ту же сторону от плоскости, проходящей через грань Q, что и начало координат?

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

11.4.Метод плавающего горизонта

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

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

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

11.6. Метод Z-буфера

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

75

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

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

Основной недостаток алгоритма с Z-буфером – дополнительные затраты памяти. Другие недостатки алгоритма с Z-буфером заключаются в том, что поскольку пиксели в буфер заносятся в произвольном порядке, то возникают трудности с реализацией эффектов прозрачности или просвечивания

11.7 Алгоритм разбиения области Варнака

Алгоритм работает в пространстве изображения и анализирует область на экране дисплея на наличие в них видимых элементов. Если в окне нет изображения, то оно просто закрашивается фоном. Если же в окне имеется элемент, то проверяется, достаточно ли он прост для визуализации. Если объект сложный, то окно разбивается на более мелкие, для каждого из которых выполняется тест на отсутствие и/или простоту изображения. Рекурсивный процесс разбиения может продолжаться до тех пор, пока не будет достигнут предел разрешения экрана [22].

Можно выделить четыре случая взаимного расположения окна и многоугольника:

многоугольник целиком вне окна,

многоугольник целиком внутри окна,

многоугольник пересекает окно,

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

76

Рисунок 11.7.1. – Четыре случая взаимного расположения окна и многоугольника

Соотношения между окном экрана (сплошная рамка) и многоугольником (штриховая рамка)

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

все многоугольники сцены – внешние по отношению к окну. В этом случае окно закрашивается фоном;

имеется всего один внутренний или пересекающий многоугольник. В этом случае все окно закрашивается фоном и затем часть окна, соответствующая внутреннему или пересекающему окну закрашивается цветом многоугольника;

имеется единственный охватывающий многоугольник. В этом случае окно закрашивается его цветом.

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

Влюбых других случаях процесс разбиения окна продолжается. При растре 1024×1024 и делении стороны окна пополам требуется не более 10 разбиений. Если достигнуто максимальное разбиение, но не обнаружено ни одного из приведенных выше четырех случаев, то для точки с центром в полученном минимальном окне (размером в пиксель) вычисляются глубины оставшихся многоугольников и закраску определяет многоугольник, наиболее близкий к наблюдателю. При этом для устранения лестничного эффекта можно выполнить дополнительные разбиения и закрасить пиксель с учетом всех многоугольников, видимых в минимальном окне.

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

77

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

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

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

здесь X min , X max , Ymin , Ymax – ребра оболочки

WЛ , WП , WH , WB – ребра окна

Для внешнего многоугольника достаточно выполнение любого из следующих условий:

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

Рисунок 11.7.2. – Ошибочное определение внешнего многоугольника как пересекающего при использовании прямоугольной оболочки

Проверка на пересечение окна многоугольником может быть выполнена проверкой на расположение всех вершин окна по одну сторону от прямой, на которой расположено ребро многоугольника. Пусть ребро многоугольника задано точками P1(x1,y1,z1) и P2(x2,y2,z2), а очередная вершина окна задается

78

точкой P3(x3,y3,z3). Векторное произведение вектора P1P3 на вектор P1P2, равное (x3-x1)(y2-y1) - (y3-y1)(x2-x1) будет меньше 0, равно 0 или больше 0, если вершина лежит слева, на или справа от прямой P1P2. Если знаки различны, то окно и многоугольник пересекаются. Если же все знаки одинаковы, то окно лежит по одну сторону от ребра, т.е. многоугольник может быть либо внешним, либо охватывающим.

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

Если суммарный угол равен 0, то многоугольник - внешний. Если же угол равен N×360°, то многоугольник охватывает окно N раз. Простейшая иллюстрация приведена на рисунках 11.7.3. и 11.7.4. ниже.

C

E D

Рисунок 11.7.3. – Многоугольник ABCDE – охватывающий суммарный угол равен 360°

D C

Рисунок 11.7.4. – Многоугольник ABCD – внешний суммарный угол равен 0°

79

11.8. Алгоритм трассировки лучей

При рассмотрении этого алгоритма предполагается, что наблюдатель находится на положительной полуоси Z, а экран дисплея перпендикулярен оси Z и располагается между объектом и наблюдателем [22].

Удаление невидимых (скрытых) поверхностей в алгоритме трассировки лучей выполняется следующим образом:

сцена преобразуется в пространство изображения,

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

вычисляются и упорядочиваются по Z координаты точек пересечения объектов с лучом. В простейшем случае для непрозрачных поверхностей без отражений и преломлений видимой точкой будет точка с максимальным значением Z-координаты. Для более сложных случаев требуется

сортировка точек пересечения вдоль луча.

Наиболее важная часть алгоритма – процедура определения пересечения, которая в принципе выполняется Rx×Ry×N раз (здесь Rx,Ry – разрешение дисплея по X и Y, соответственно, а N – количество многоугольников в сцене).

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

При использовании прямоугольной оболочки определяется преобразование, совмещающее луч с осью Z. Оболочка подвергается этому преобразованию, а затем попарно сравниваются знаки Xmin с Xmax и Ymin с Ymax. Если они различны, то есть пересечение луча с оболочкой.

Рисунок 11.8.1. – Алгоритм трассировки лучей

80