Удаление невидимых плоскостей


Содержание

Удаление невидимых плоскостей

УДАЛЕНИЕ НЕВИДИМЫХ ЧАСТЕЙ
3.1. Отброс нелицевых граней

Пусть у нас есть объект, внутри которого камера заведомо не окажется. Обычно такие объекты составляют большую часть или всю сцену. Тогда для каждой грани мы можем увидеть только одну ее сторону — лицевую. Грань — плоскость, она делит все 3D пространство на два полупространства. Так вот, лицевую сторону видно только из одного полупространства, из того, в которое «смотрит» нормаль к этой грани, направленная *из* объекта. Проверив, в какое полупространство попадает камера, можно сразу определить, является ли грань лицевой (то есть, может ли камера увидеть лицевую сторону этой грани) и надо ли ее рисовать.

Пусть грань имеет вершины v1, v2, v3 и нормаль (nx,ny,nz). Тогда уравнение плоскости, в которой она лежит, будет иметь вид

d находим из того факта, что v1 в плоскости лежит:

nx*v1.x+ny*v1.y+nz*v1.z+d = 0,
d = -(nx*v1.x+ny*v1.y+nz*v1.z).

Функция nx*x+ny*y+nz*z+d принимает положительные значения по одну сторону от плоскости, отрицательные по другую и равна нулю на самой плоскости. Точка (v1.x+nx,v1.y+ny,v1.z+nz) лежит, очевидно, в том полупространстве, откуда грань видно. Значение функции (назовем ее функцией видимости) в этой точке равно

nx*(v1.x+nx)+ny*(v1.y+ny)+nz*(v1.z+nz)+d =
nx*(v1.x+nx)+ny*(v1.y+ny)+nz*(v1.z+nz)-(nx*v1.x+ny*v1.y+nz*v1.z) =
nx*nx+ny*ny+nz*nz > 0.

Таким образом, если значение функции в какой-то точке больше нуля, то грань из этой точки потенциально видна. Нас интересует видимость грани из нашей камеры, а камера у нас зафиксирована в точке (0,0,-dist). Таким образом, получаем, что грани, для которых

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

Отдельный вопрос — как считать нормали к граням. Точнее, как выбрать одну из двух нормалей, которая будет смотреть из объекта. Обычно эта проблема решается еще на этапе построения 3D моделей — например, пакет 3D Studio записывает вершины граней в порядке A-B-C так, чтобы векторное произведение BA*CA и было нормалью. Еще один способ — выбрать внутренную точку для объекта (либо вручную, либо взять его центр тяжести, либо еще как-нибудь — методов может быть придумано сколько угодно) и использовать ее: если для этой точки функция видимости положительна, то есть грань якобы видна, то надо поменять знак nx, ny и nz.

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

Удаление невидимых плоскостей

5.6 Алгоритмы удаления невидимых линий и поверхностей

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

Выделяют три класса таких алгоритмов:

1. Алгоритмы, работающие в пространстве объекта. Для определения видимости данной поверхности сравнивается ее взаимное расположение с остальными поверхностями объекта в трехмерной сцене.

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

• Алгоритм плавающего горизонта;

• Алгоритм Коэна − Сазерленда;

• Модифицированный вариант алгоритма Коэна − Сазарленда;

• Алгоритм с использованием z-буфера;

• Метод трассировки лучей;

• Алгоритм Вейлера − Азертона.

3. Алгоритмы, формирующие список приоритетов, работают попеременно в обеих системах координат (объекта и изображения).

• Алгоритм Ньюэла − Ньюэла − Санча (алгоритм удаления невидимых граней методом сортировки по глубине;)

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

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

Алгоритм плавающего горизонта

Алгоритм плавающего горизонта чаше всего используется для удаления невидимых линий трехмерного представления функций, описывающих поверхность в виде F(x, у, z) = 0.

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

Алгоритм сначала упорядочивает плоскости z = const по возрастанию расстояния до них от точки наблюдения. Затем для каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая, лежащая на ней, т.е. для каждого значения координаты х в пространстве изображения определяется соответствующее значение y.

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

Алгоритм Коэна − Сазерленда

Алгоритм Коэна − Сазерленда предназначен для отсечения отрезков. Он был разработан Дэном Коэном и Айвеном Сазерлендом в Гарварде в 1966-1968 гг.

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

Окну присваивается код 0000. Конечным точкам отрезка приписывается 4-битный код «вне/внутри» в зависимости от нахождения отрезка в соответствующей подобласти. Каждому биту присваивается значение 1 в соответствии со следующим правилом.

Бит 1 − точка находится выше окна;

Бит 2 − точка находится ниже окна;

Бит 3 − точка находится справа от окна;

Бит 4 − точка находится слева от окна;

Иначе биту присваивается нулевое значение.

Алгоритм определяет код конечных точек отрезка. Если оба кода равны нулю [код1] И [код2] = 0000, то отрезок полностью находится в прямоугольнике. Если битовое И кодов не равно нулю, то отрезок не пересекает прямоугольник (так как это значит, что обе конечные точки отрезка находятся с одной стороны прямоугольника). В прочих случаях алгоритм выбирает конечную точку, находящуюся вне прямоугольника, находит ближайшую к ней точку пересечения отрезка с одной из линий, образующей стороны прямоугольника, и использует эту точку пересечения как новую конечную точку отрезка. Укороченный отрезок снова пропускается через алгоритм.

Рис. 5.12. Разбиение на подобласти в методе Коэна − Сазерленда

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

Читайте также:

  1. D-40 показывает карму, унаследованную по материнской линии, D-45 показывает карму, унаследованную со стороны отца. Они полезны только в королевских картах.
  2. II. Укрупненные показатели по конкретным видам товаров н рынкам
  3. XXI век знаменуется новым подходом к пониманию истории – история как наука, которая может показать пути решения многих проблем современной цивилизации.
  4. Абсолютные и относительные показатели
  5. Абсолютные и относительные статистические показатели
  6. Абсолютные и средние показатели вариации
  7. Абсолютные и средние показатели вариации
  8. Абсолютные показатели
  9. Абсолютный показатель, характеризующий объект А
  10. Аддитивная модель прироста товарооборота по показателям оборачиваемости товаров.
  11. Аддитивный и мультипликативный способы объединения единичных показателей качества в комплексный показатель. Отражение мат.модели КПК иерархической структуры системы показателей.
  12. Алгоритмы расчета показателей экономической эффективности проектов.

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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)] на плоскости экрана, где

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

e3= (sinφ cosq, — cosφ — cosq, sinq), где φє[0, 2π], qє[-π/2, π/2], — углы подобраны так, чтобы плоскость у=у1 была ближе к экранной плоскости, чем у=у2, т.е. у1 к (х), которые выше у к 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 max ) B0 = ( y > y max )

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

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

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

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

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

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

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

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

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

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

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

| следующая лекция ==>
Неравномерная сетка. Изолинии | Модели отражения света

Дата добавления: 2014-01-05 ; Просмотров: 843 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

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

технические науки

  • Абрамова Оксана Федоровна , доцент, доцент

  • Волжский политехнический институт (филиал) Волгоградский государственный технический университет
  • Никонова Надежда Сергеевна , студент
  • Волжский политехнический институт, Волгоградский государственный технический университет
  • КОЭНА-САЗЕРЛЕНДА
  • АЛГОРИТМЫ УДАЛЕНИЯ НЕВИДИМЫХ ЛИНИЙ
  • АЛГОРИТМ ВАРНОКА

Похожие материалы

В настоящее время практически каждый человек старается окружить себя полезными и красивыми вещами, одной из которых является компьютерная графика (ее можно встретить в печатной литературе, на экране телевизора и рекламном плакате, дизайнерском проекте). С развитием компьютерных технологий компьютерная графика все больше проникает в жизни людей, она используется в науке и образовании, бизнесе, киноиндустрии, а также во всевозможных отраслях промышленности [1]. Но не стоит забывать, что изучение компьютерной графики далеко не легкий процесс [2, 3, 4]. В данной статье мы рассмотрим одну из наиболее сложных задач компьютерной графики – удаление невидимых линий и поверхностей.

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

В настоящее время существует множество алгоритмов удаления невидимых линий и поверхностей. Все их можно разделить на три группы:

  • алгоритмы, работающие в пространстве объекта (например, алгоритм Робертса);
  • алгоритмы, работающие в пространстве изображения (алгоритм Коэна-Сазерленда, алгоритм с использованием z-буфера, алгоритм Варнока, Алгоритм Вейлера-Азертона и другие);
  • алгоритмы, работающие попеременно с системами координат как объекта, так и изображения (алгоритм Ньюэла-Ньюэла-Санча).

Проведем сравнительный анализ алгоритмов, работающих в пространстве объекта и в пространстве изображения (табл. 1) [2, 3, 4].

Таблица 1 Сравнительный анализ алгоритмов удаления невидимых линий

Алгоритмы, работающие в пространстве объекта

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

Алгоритмы имеют дело с физической системой координат, в которой описываются данные объекты

Алгоритмы работают с системой координат экрана, на который визуализируются объекты

Высокая точность (точные результаты, которые могут быть ограничены только точностью вычислений)

На точность вычислений влияет разрешающая способность экрана

растет теоретически, как квадрат числа объектов n2

растет теоретически, как nN, где n- количество объектов в сцене,N — число пикселов

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

  • не существует универсального алгоритма, который не ограничивался бы определенным классом линий или поверхностей, необходимых для отображения объектов;
  • практически невозможно выделить наилучший алгоритм, который был бы пригоден для всех типов графических устройств и любых приложений [4, 5].

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

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

Алгоритм Коэна-Сазерленда

Алгоритм Коэна-Сазерленда позволяет определить часть отрезка, пересекающую выделенную прямоугольную область, определяя таким образом видимость и невидимость отрезков. Суть алгоритма заключается в том, что плоскость разбивается на 9 частей прямыми, образующими стороны прямоугольника (рис. 1). Каждая часть имеет свой 4х-битный код. [6]

Рисунок 1 Коды областей Коэна-Сазерленда

Поле вывода (с учетом границ) состоит из точек (x,y), которые удовлетворяют соотношения xl≤x≤xr и yb≤y≤yt . Допустим, что отрезок задан с помощью координат концевых точек (x1,y1) и (x2,y2). В начале алгоритма Коэна-Сазерленда выявляются полностью видимые и невидимые отрезки:

В остальных случаях отрезок может (но не обязан) пересекать поле вывода.

В данном алгоритме каждой концевой точке отрезка присваивается свой код, в зависимости от ее расположения относительно поля вывода. Если коды концов отрезков равны нулю, то он (отрезок) лежит в поле вывода (внутри окна). Для анализа остальных случаев необходимо воспользоваться операцией логического умножения кодов [6, 7].

Илон Маск рекомендует:  Как правильно выбирать ключевые слова

Руководствуясь полученной таблицей истинности, можно утверждать: если произведение концов отрезка принимает значение T (true), то этот отрезок полностью лежит по одну сторону одной из прямых (l, r, t или b), причем, важно отметить, он лежит во внешней стороне относительно поля вывода, следовательно, он полностью невидим. Если же произведение оказалось F(false), то отрезок частично находится в поле вывода [7].

Приведем общую блок-схему алгоритма Коэна-Сазерленда (рис. 2).

Рисунок 2 Блок-схема алгоритма Коэна-Сазерленда

В блок-схеме используются следующие обозначения:

  • GetCode(r) – вспомогательная функция, определения кода точки;
  • C1, C2 — коды точек r1, r2;
  • Intersec(r1,l), Intersec0(r1,l) – вспомогательные функции, поиска пересечения отрезка со сторонами окна при условии, что точка r1 лежит в окне и что обе точки лежат вне окна; если пересечения нет, устанавливает переменную IsVisible в 0, соответственно.

Входными данными являются точки (1), массив координат окна

На выходе получаем новые концевые точки (3), а также значение переменной IsVisible (0 — отрезок видимый)[4].

Теперь приведем блок-схемы и рассмотрим более подробно вспомогательные функции: Intersec(r1,l) и Intersec0(r1,l) (рис. 3, 4).

Рисунок 3 Блок-схема вспомогательной функции Intersec

Воспользуемся методом поиска пересечений, использующим параметрическое уравнение прямой, проходящей через точки:

или в координатном виде:


Определим точку пересечения отрезка с верхней границей окна, которая описывается соотношениями: (6).

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

Аналогично запишутся формулы для оставшихся границ окна. Если точка расположена внутри поля вывода, то, в зависимости от знака ly, необходимо искать пересечение либо с верхней, либо с нижней границей поля вывода (окна). Если такие пересечения отсутствуют, необходимо искать пересечения с двумя другими гранями окна (левой и правой стороной). До того как рассматривать выше описанные варианты, необходимо исключить случаи горизонтальных ly = 0 (пересечение с правой или левой границей: (L,y1), (R,y1), в зависимости от знака lx и вертикальных lx = 0 (пересечение с верхней или нижней границей: (x1,B), (x1,T) направлений отрезка.[7, 8]

Рисунок 4 Блок-схема вспомогательной функции Intersec0

Для случая, когда оба конца отрезка лежат вне окна вывода, в начале найдем одну точку пересечения с границей окна и заменим ею один из концов отрезка, а далее будем использовать вышеописанный алгоритм нахождения второй точки. Важно отметить, что первый шаг не в 100% случаев оканчивается успешно, так как с помощью предварительного анализа невозможно исключить все возможные невидимые отрезки. Аналогично предыдущему алгоритму перед поиском точек пересечения с полем вывода выполняется проверка на вертикальное и горизонтальное направление отрезка. Так как часть отрезков была исключена благодаря предварительному анализу, остаются только две возможные ситуации (рис. 5).

Рисунок 5 Отрезки параллельны сторонам поля вывода

Точки пересечения на рисунке 6 определяются очевидным образом.

Далее последовательно рассматриваются 4 случая расположения точки относительно прямых, которые ограничивают поле вывода. При нахождении точки пересечения в любом из вариантов, процесс анализа останавливается, данная точка заменяется новой точкой и вызывается функция Intersec. Если при переборе всех 4х вариантов положительный ответ не был получен, переменная IsVisible получает значение 0.

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

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

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

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

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

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

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

Будем выделять 4 разных многоугольника (рис. 6): внешний (расположен полностью вне окна); внутренний (полностью расположен внутри окна); пересекающий (пересекает хотя бы одну границу окна); охватывающий (окно целиком располагается внутри рассматриваемого прямоугольника) [2, 6].

Рисунок 6 Типы многоугольников: внешний (а), внутренний (b), пересекающий (c), охватывающий (d).

Зная вышеописанные типы многоугольников, можно рассмотреть следующие правила обработки окна. Для каждого окна:

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

В любом другом случае необходимо провести разбиение окна [1,6].

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

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

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

Таблица 2 Сравнительный анализ алгоритмов Коэна-Сазерленда и Варнока

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

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

Пространство, в котором работает алгоритм

Работает в пространстве изображения

Работает в пространстве изображения

Возможность удаления невидимых линий

Возможность удаления невидимых поверхностей

выполняет отсечение за несколько итераций (около 2х)

прямо пропорционально насыщенности изображения

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

Разбиение области стоит прекратить, как только ее размер станет не больше одного пикселя.

Эффективность для сложных сцен

Повышение эффективности алгоритма

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

ограничена разрешающей способностью экрана

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

Список литературы

  1. Абрамова О.Ф., Котов В. В. К вопросу об импорте 3D моделей в программы с использованием графической библиотеки OpenGL [Электронный ресурс] / Котов В. В., Абрамова О.Ф. // Современная техника и технологии. — 2014. — № 1. — C. Режим доступа : http://technology.snauka.ru/2014/01/2965.
  2. Трифанов А.И., Абрамова О.Ф. Реализация собственного метода визуализации водной поверхности «скользящая текстура» / Трифанов А.И., Абрамова О.Ф. // Современные наукоёмкие технологии. — 2013. — № 8 (ч. 1). — C. 96-97.
  3. Абрамова О.Ф. Использование мультимедийных технологий в процессе обучения дисциплине «Компьютерная графика» / Абрамова О.Ф., Белова С.В. // Успехи современного естествознания. — 2012. — № 3. — C. 90.
  4. Абрамова О.Ф. К вопросу о повышении эффективности функционирования тренажёрно-обучающих систем / О.Ф. Абрамова, М.Л. Цыганкова // Открытое и дистанционное образование. — 2014. — № 4. — C. 34-39.
  5. cb.mediaedu.uz – Медиаобразовательный портал – [Электронный ресурс] – Режим доступа : http://cb.mediaedu.uz/cabinet.php?page=courses&urok=90
  6. technomag.edu.ru – Электронное издательство НАУКА и ОБРАЗОВАНИЕ – Издатель ФГБОУ ВПО «МГТУ им. Н.Э. Баумана». Эл № ФС 77 – 48211 — [Электронный ресурс] – Режим доступа : http://technomag.edu.ru/doc/49094.html
  7. Шикин Е. В., Боресков А. В. Компьютерная графика. Полигональные модели. — М.: ДИАЛОГ-МИФИ, 2001.

  8. Шлыков А.А. Практическая реализация алгоритма поиска кратчайшего пути А* для трёхмерных моделей зданий / А.А. Шлыков, О.Ф. Абрамова // Современные наукоёмкие технологии. — 2014. — № 5 (ч. 2). — C. 17-18.
  9. Сиденко Л.А. Компьютерная графика и геометрическое моделирование: Учебное пособие. – СПб.: Питер, 2009. – 224 с.: ил. – (Серия «Учебное пособие»)

Электронное периодическое издание зарегистрировано в Федеральной службе по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор), свидетельство о регистрации СМИ — ЭЛ № ФС77-41429 от 23.07.2010 г.

Соучредители СМИ: Долганов А.А., Майоров Е.В.

Удаление невидимых линий и поверхностей.

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

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

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

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

Алгоритм удаления поверхностей с Z-буфером.

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

Этот алгоритм наиболее простой из всех алгоритмов удаления невидимых поверхностей, но требует большого объема памяти.

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

Рисунок 59: Работа алгоритма с Z-буфером.

Пусть уравнение плоскости имеет вид:

A·x + B·y + C·z + D = 0.

Тогда при C не равном нулю:

Найдем приращение Z-координаты пиксела при шаге по X на dx , помня, что Y очередной обрабатываемой строки — константа.

dz = -(A·(x+dx) + D)/C + (A·x + D)/C = -A·dx/C

но dx = 1, поэтому

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

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

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

Общая схема алгоритма с Z-буфером:

• Инициализировать кадровый и Z-буфера. Кадровый буфер закрашивается фоном. Z-буфер закрашивается минимальным значением Z.

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

• Выполнить, если это было предусмотрено, усреднение изображения с понижением разрешения.

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

Рисунок 60: Соотношение между окном экрана и многоугольником

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

X_min >= W_left и X_max = W_bottom и Y_max — ребра оболочки

W_left, W_right, W_bottom, W_top — ребра окна

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

Удаление невидимых линий и поверхностей с помощью алгоритма Варнока

Обоснование выбора языка программирования ……………….2

Требования к аппаратному обеспечению………………………..2

Основные принципы моделирования трёхмерных объектов. 3


Описание возможностей программы…………………………….19

1. Обоснование выбора языка программирования.

Представленная курсовая работа разработана среде программирования Delphi 6 от Borland. Данный программный продукт предоставляет широкие возможности для создания прикладных программ под Widows, а также Delphi является наиболее удобной средой программирования, т.к. обладает интуитивно понятным интерфейсом, мощной палитрой средств для разработки пользовательского интерфейса. В тоже время, разработка взаимодействия программа — пользователь не требует больших временных затрат, что позволяет сосредоточить внимания на реализации требуемых алгоритмов.

2. Требования к аппаратному обеспечению системы.

ОС Windows 9x/NT/Me/2000/Xp.

Процессор не ниже Pentium 166 Mhz.

HDD Free Space = 300 kb

3. Основные принципы моделирования трёхмерных объектов.

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

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

Существует краткая математическая запись для выражения преобразования координат – матрично-векторное умножение. Трёхмерная точка представляется трёхэлементными векторами-столбцами.

“Масштабирование координат точки означает умножение каждой координаты на постоянную величину.

Масштабирование представляется следующей матрицей преобразования:

Перенос относится к передвижению объекта в новую точку с сохранением ориентации. Для переноса трёхмерной точки необходимо прибавить соответствующие смещения к X, Y, Z-координатам для получения эффекта движения. Таким образом, перенос основан на сложении двух векторов. Перенос можно выразить как матричное умножение, но для этого необходим “математический костыль” – однородные координаты. К трехмерной координате следует добавить ещё одну со значением 1:

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

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

Основные идеи, на которые опирается алгоритм Варнока, обладают большой общностью. Они основываются на гипотезе о способе обработки информации, содержащейся в сцене, глазом и мозгом человека. Эта гипотеза заключается в том, что тратится очень мало времени и усилий на обработку тех областей, которые содержат мало информации. Большая часть времени и труда затрачивается на области с высоким информационным содержимым. В качестве примера рассмотрим поверхность стола, на которой нет ничего, кроме вазы с фруктами. Для восприятия цвета, фактуры и других аналогичных характеристик всей поверхности стола много времени не нужно. Все внимание сосредоточивается на вазе с фруктами. В каком месте стола она расположена? Велика ли она? Из какого материала сделана: из дерева, керамики, пластика, стекла, металла? Каков цвет вазы: красный, синий, серебристый; тусклый или яркий и т. п.? Какие фрукты в ней лежат: персики, виноград, груши, бананы, яблоки? Каков цвет яблок: красный, желтый, зеленый? Есть ли у яблока хвостик? В каждом случае, по мере сужения сферы интереса, возрастает уровень требуемой детализации. Далее, если на определенном уровне детализации на конкретный вопрос нельзя ответить немедленно, то он откладывается на время для последующего рассмотрения. В алгоритме Варнока и его вариантах делается попытка извлечь преимущество из того факта, что большие области изображения однородны, например поверхность стола в приведенном выше примере. Такое свойство известно как когерентность, т. е. смежные области (пиксели) вдоль обеих осей х и у имеют тенденцию к однородности.

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

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

На рис. 1 показан результат простейшей реализации алгоритма Варнока. Здесь окно, содержимое которого слишком сложно изображать, разбито на четыре одинаковых подокна. Окно, в котором что-то есть, подразбивается далее до тех пор, пока не будет достигнут предел разрешения экрана.

рис. №1 “Пример использования алгоритма Варнока”

На рис. 1, a показана сцена, состоящая из двух простых многоугольников. На рис. 1, b показан результат после удаления невидимых линий. Заметим, что горизонтальный прямоугольник частично экранирован вертикальным. На рис. 1, c и d показан процесс разбиения окон на экране с разрешением 256х256. Поскольку 256 = 2^8, требуется не более восьми шагов разбиения для достижения предела разрешения экрана. Пусть подокна рассматриваются в следующем порядке: нижнее левое, нижнее правое, верхнее левое, верхнее правое. Будем обозначать подокна цифрой и буквой,’ цифра – это номер шага разбиения, а буква – номер квадранта. Тогда для окна 1а подокна 2а, 4а, 4с, 5а, 5b оказываются пустыми и изображаются с фоновой интенсивностью в процессе разбиения. Первым подокном, содержимое которого не пусто на уровне пикселей, оказывается 8а. Теперь необходимо решить вопрос о том, какой алгоритм желательно применить: удаления невидимых линий или удаления невидимых поверхностей. Если желательно применить алгоритм удаления невидимых линий, то пиксель, соответствующий подокну 8а, активируется, поскольку через него проходят видимые ребра. В результате получается изображение видимых ребер многоугольников в виде последовательности точек размером с пиксель каждая (рис. 1, е).

Следующее рассмотрение окна, помеченного как 8d на рис. 1, d, лучше всего проиллюстрирует различие между реализациями алгоритмов удаления невидимых линий и поверхностей. В случае удаления невидимых линий окно 8d размером с пиксель не содержит ребер ни одного многоугольника сцены. Следовательно, оно объявляется пустым и изображается с фоновой интенсивностью или цветом. Для алгоритма удаления невидимых поверхностей проверяется охват этого окна каждым многоугольником сцены. Если такой охват обнаружен, то среди охватывающих пиксель многоугольников выбирается ближайший к точке наблюдения на направлении наблюдения, проходящем через данный пиксель. Проверка проводится относительно центра пикселя. Затем этот пиксель изображается с интенсивностью или цветом ближайшего многоугольника. Если охватывающие многоугольники не найдены, то окно размером с пиксель пусто. Поэтому оно изображается с фоновым цветом или интенсивностью. Окно 8d охвачено вертикальным прямоугольником. Поэтому оно изображается с цветом или интенсивностью этого многоугольника. Соответствующий результат показан на рис. 1, f.

Возвратившись к рассмотрению окна 8а на рис. 1, d, покажем, как включить в алгоритм удаления невидимых поверхностей устранение лестничного эффекта. Разбиение этого окна дает четыре подокна с размерами, меньшими, чем размеры пикселя. Только одно из этих подокон – правое верхнее – охвачено многоугольником. Три других пусты. Усреднение результатов для этих четырех подпикселей показывает, что окно 8а размером с пиксель нужно изображать с интенсивностью, равной одной четверти интенсивности прямоугольника. Аналогично пиксель 8Ь следует высвечивать с интенсивностью, равной половине интенсивности прямоугольника. Конечно, окна размером с пиксель можно разбивать более одного раза, чтобы произвести взвешенное усреднение характеристик.

Процесс подразбиения порождает для подокон структуру данных, являющуюся деревом, которое показано на рис. 2 (В алгоритме Варнока впервые была реализована такая структура данных, как кватернарное дерево). Корнем этого дерева является визуализируемое окно. Каждый узел изображен прямоугольником, содержащим координаты левого нижнего угла и длину стороны подокна. Предположим, что подокна обрабатываются в следующем порядке: abcd, т. е. слева направо на каждом уровне разбиения в дереве. На рис. 2 показан активный путь по структуре данных дерева к окну 8а размером с пиксель. Активные узлы на каждом уровне изображены толстой линией. Рассмотрение рис. 1 и 2 показывает, что на каждом уровне все окна слева от активного узла пусты. Поэтому они должны были визуализироваться ранее с фоновым значением цвета или интенсивности. Все окна справа от активного узла на каждом уровне будут обработаны позднее, т. е. будут объявлены пустыми или будут подразделены при обходе дерева в обратном порядке.

рис. №2 “ Дерево разбиения окон”

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

Илон Маск рекомендует:  Структура индексного файла ( idx)

Для рассмотрения более сложных критериев разбиения будет полезно определить способы расположения многоугольников относительно окна. Назовем многоугольник:

внешним, если он находится целиком вне окна;
внутренним, если он находится целиком внутри окна;
пересекающим, если он пересекает границу окна;
охватывающим, если окно находится целиком внутри него.

На рис. 4 показаны примеры всех этих типов многоугольников.

Рис. №3. “Типы многоугольников: внешний (a), внутренний (b), пересекающий (c), охватывающий (d).”

Используя эти определения, можно предложить следующие правила обработки окна:

Для каждого окна:

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

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

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

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

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

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

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

Для реализации этих правил требуются методы определения способа расположения многоугольника относительно окна. В случае прямоугольных окон можно воспользоваться минимаксными или габаритными, с объемлющей прямоугольной оболочкой, тестами для определения, является ли многоугольник внешним по отношению к окну. В частности, если xЛ, xП, yН, yВ определяют четыре ребра окна, а xmin, xmax, ymin, ymax – ребра прямоугольной объемлющей оболочки многоугольника, то этот многоугольник будет внешним по отношению к окну, если выполняется любое из следующих условий:

xmin > xП, xmax yВ, ymax = xЛ, xmax = yН, ymax if  > 4 then  =  – 8
if  then  =  + 8
if  = 0 then ребро многоугольника расщепляется ребром окна, и процесс повторяется с парой полученных отрезков.

Суммируя вклады от отдельных ребер, получаем:

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

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

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

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

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

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

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

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

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

ax + by + cz + d = 0


а координаты угловой точки окна равны (xw, yw), то значение

z = – (d + axw + byw)/c, c 0

равно искомой глубине.

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

При обработке каждого окна алгоритм ищет охватывающие его многоугольники. После обнаружения такого многоугольника запоминается величина z у его самой удаленной от наблюдателя вершины zsmin. При рассмотрении каждого очередного многоугольника в списке сравнивается координата z его ближайшей к наблюдателю вершины –zpmax с zsmin. Если zpmax 5. Описание возможностей программы.

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

Удаление невидимых поверхностей и линий Содержание

II-4. Удаление невидимых поверхностей и линий.pptx

Удаление невидимых поверхностей и линий

Содержание • • • Постановка проблемы Алгоритм Робертса Алгоритм Варнока Алгоритм Вейлера-Азертона Алгоритм плавающего горизонта Метод Z-буфера Алгоритм Художника Алгоритм Ньюэла-Санча Алгоритм трассировки лучей. 2

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

Удаление невидимых поверхностей и линий Постановка проблемы Алгоритмы выбираются в зависимости от решаемой задачи: • для моделирования в реальном времени – быстрые алгоритмы • для формирования сложных реалистичных изображений – более медленные, но «качественные» алгоритмы Единого универсального алгоритма отсечения пока не существует. Существует несколько различных вариантов классификации методов удаления невидимых линий и поверхностей.

Удаление невидимых поверхностей и линий Классификация методов Методы удаления невидимых частей сцены можно классифицировать: • По выбору удаляемых частей: удаление невидимых линий, ребер, поверхностей, объемов. • По порядку обработки элементов сцены: § удаление в произвольном порядке § удаление в порядке определяемом процессом визуализации. По системе координат: § алгоритмы работающие в пространстве объектов, когда каждая из N граней объекта сравнивается с остальными N-1 гранями § алгоритмы работающие в пространстве изображения, когда для каждого пикселя изображения определяется какая из N граней объекта видна

Удаление невидимых поверхностей и линий Классификация методов Также алгоритмы можно классифицировать по способу выбора системы координат или пространства в котором они работают: • Алгоритмы, работающие в объектном пространстве. § Работают с физической системой, в которой описаны объекты – высокая точность. § Для определения видимости данной поверхности сравнивается ее взаимное расположение с остальными поверхностями объекта в трехмерной сцене. • Алгоритмы, работающие в пространстве изображения (экрана). Они основаны на нахождении точки ближайшей поверхности, которую пересекает луч зрения, проходящий через заданную точку на растре. • Алгоритмы, формирующие список приоритетов, работают попеременно в обеих системах координат (объекта и изображения).

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

Удаление невидимых поверхностей и линий Алгоритм Робертса Выпуклый многогранник однозначно определяется набором плоскостей, образующих его грани, поэтому исходными данными для алгоритма являются многогранники, заданные списком своих граней. Грани задаются в виде плоскостей, заданных в канонической форме в объектной системе координат:

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

Удаление невидимых поверхностей и линий Алгоритм Робертса В алгоритме плоскости строятся таким образом, что внутренние точки многогранника лежат в положительной полуплоскости. Это означает, что вектор (abc) является внешней нормалью к многограннику. Из векторов плоскостей строится прямоугольная матрица порядка которая называется обобщенной матрицей описания многогранника: Умножая столбцы матрицы на вектор , получаем n-мерный вектор, если все его компоненты неотрицательны, то точка принадлежит многограннику. Это условие будем запишем в виде

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

Удаление невидимых поверхностей и линий Алгоритм Робертса Каждое из видимых ребер каждого многогранника сравнивается с каждым из оставшихся многогранников для определения того, какая его часть или части, если таковые есть, экранируются этими телами. Для этого в каждую точку ребра проводится отрезок луча, выходящего из точки расположения наблюдателя. Если отрезок не пересекает ни одного из многогранников, то точка видима. Для решения этой задачи используются параметрические уравнения прямой, содержащей ребро, и луча. Так как объем вычислений растет с увеличением числа многоугольников, то желательно по мере возможности сокращать их число, т. е. если мы аппроксимируем некоторую поверхность многогранником, то в качестве граней можно использовать не треугольники, а более сложные многоугольники. Вычислительная трудоемкость алгоритма Робертса растет теоретически, как квадрат числа объектов в сцене.

Удаление невидимых поверхностей и линий Алгоритм Варнока Варнок в 1968 г. предложил алгоритм, работающий не в объектном пространстве, а в пространстве изображения. Он также нацелен на изображение многогранников, а главная идея его основана на гипотезе о способе обработки информации, содержащейся в сцене, глазом и мозгом человека: тратится очень мало времени и усилий на обработку тех областей, которые содержат мало информации. Большая часть времени и труда затрачивается на области с высоким информационным содержимым. В алгоритме Варнока и его вариантах делается попытка воспользоваться тем, что большие области изображения однородны. Такое свойство называют когерентностью, имея в виду, что смежные области (пиксели) вдоль обеих осей х и у имеют тенденцию к однородности.

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

Удаление невидимых поверхностей и линий Алгоритм Варнока Многоугольник, входящий в изображаемую сцену, по отношению к окну будем называть • внешним, если он целиком находится вне окна; • внутренним, если он целиком расположен внутри окна; • пересекающим, если он пересекает границу окна; • охватывающим, если окно целиком расположено внутри него.

Удаление невидимых поверхностей и линий Алгоритм Варнока Для каждого окна: 1. Если все многоугольники сцены являются внешними по отношению к окну, то оно пусто; изображается фоновым цветом и дальнейшему разбиению не подлежит. 2. Если только один многоугольник сцены имеет общие точки с окном и является по отношению к нему внутренним, то окно заполняется фоновым цветом, а сам многоугольник заполняется своим цветом. 3. Если только один многоугольник сцены имеет общие точки с окном и является по отношению к нему пересекающим, то окно заполняется фоновым цветом, а часть многоугольника, принадлежащая окну, заполняется цветом многоугольника.

Удаление невидимых поверхностей и линий Алгоритм Варнока 4. Если только один многоугольник охватывает окно и нет других многоугольников, имеющих общие точки с окном, то окно заполняется цветом этого многоугольника. 5. Если существует хотя бы один многоугольник, охватывающий окно, то среди всех таких многоугольников выбирается тот, который расположен ближе всех к точке наблюдения, и окно заполняется цветом этого многоугольника. 6. В противном случае производится новое разбиение окна. Шаги 1– 4 рассматривают ситуацию пересечения окна только с одним многоугольником. Они используются для сокращения числа подразбиений. Шаг 5 решает задачу удаления невидимых поверхностей. Многоугольник, находящийся ближе всех к точке наблюдения, экранирует все остальные.

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

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

Удаление невидимых поверхностей и линий Алгоритм Вейлера-Азертона В самом общем виде он состоит из четырех шагов: • Предварительная сортировка по глубине. • Отсечение по границе ближайшего к точке наблюдения многоугольника, называемое сортировкой многоугольников на плоскости. • Удаление многоугольников, экранируемых более близкими к точке наблюдения многоугольниками. • Если требуется, то рекурсивное разбиение и новая сортировка. В процессе предварительной сортировки создается список приблизительных приоритетов, причем близость многоугольника к точке наблюдения определяется расстоянием до ближайшей к ней вершины. Затем выполняется отсечение по самому первому из многоугольников.

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

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

Удаление невидимых поверхностей и линий Алгоритм Вейлера-Азертона Этот алгоритм в дальнейшем был обобщен Кэтмулом (1974) для изображения гладких бикубических поверхностей. Его подход заключался в том, что разбиению подвергалась поверхность. Коротко этот алгоритм можно описать так: • Рекурсивно разбивается поверхность до тех пор, пока проекция элемента на плоскость изображения не будет покрывать не больше одного пикселя. • Определить атрибуты поверхности в этом пикселе и изобразить его. Эффективность такого метода, как и алгоритм Варнока, зависит от эффективности разбиений. В дальнейшем этот алгоритм был распространен на сплайновые поверхности.

Удаление невидимых поверхностей и линий Алгоритм плавающего горизонта относится к классу алгоритмов, работающих в пространстве изображения. Алгоритм чаше всего используется для удаления невидимых линий трехмерного представления функций, описывающих поверхность в виде Главная идея метода заключается в сведении трехмерной задачи к двумерной путем пересечения исходной поверхности последовательностью параллельных секущих плоскостей, имеющих постоянные значения координат x, y или z. Секущие плоскости с постоянной координатой

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

Удаление невидимых поверхностей и линий Алгоритм плавающего горизонта Предполагается, что полученные кривые являются однозначными функциями независимых переменных. Спроецируем полученные кривые на плоскость z = 0 Проекция кривых на плоскость z = 0

Удаление невидимых поверхностей и линий Алгоритм плавающего горизонта Алгоритм сначала упорядочивает плоскости z = const по возрастанию расстояния до них от точки наблюдения. Затем для каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая, лежащая на ней, т. е. для каждого значения координаты x в пространстве изображения определяется соответствующее значение y. Алгоритм удаления невидимой линии: Если на текущей плоскости при некотором заданном значении x соответствующее значение у на кривой больше значения y для всех предыдущих кривых при этом значении x, то текущая кривая видима в этой точке; в противном случае она невидима.

Удаление невидимых поверхностей и линий Алгоритм плавающего горизонта Алгоритм достаточно прост в реализации. Для хранения максимальных значений y при каждом значении x используется массив, длина которого равна числу различимых точек (разрешению) по оси x в пространстве изображения. Значения, хранящиеся в этом массиве, представляют собой текущие значения «горизонта». Поэтому по мере рисования каждой очередной кривой этот горизонт «всплывает». Фактически этот алгоритм работает каждый раз с одной линией.

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

Удаление невидимых поверхностей и линий Алгоритм плавающего горизонта Модифицируем алгоритм, включив в него нижний горизонт, который опускается вниз по ходу работы алгоритма. Реализуем его при помощи второго массива, длина которого равна числу различимых точек по оси x в пространстве изображения. Этот массив содержит наименьшие значения y для каждого значения x. Теперь алгоритм имеет вид: если на текущей плоскости при некотором заданном значении x соответствующее значение y на кривой больше максимума или меньше минимума по y для всех предыдущих кривых при этом значении x, то текущая кривая видима; в противном случае кривая невидима.

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

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

Удаление невидимых поверхностей и линий Алгоритм плавающего горизонта Результат работы алгоритма плавающего горизонта для функции в интервале

Удаление невидимых поверхностей и линий Алгоритм, использующий z–буфер Алгоритм, использующий z-буфер, удаления невидимых поверхностей является одним из простейших алгоритмов. Был предложен Эдом Кэтмулом. Алгоритм работает в пространстве изображения. Идея z-буфера является простым обобщением идеи о буфере кадра. Буфер кадра используется для запоминания атрибутов (интенсивности) каждого пикселя в пространстве изображения, z-буфер — это отдельный буфер глубины, используемый для запоминания координаты z или глубины каждого видимого пикселя в пространстве изображения.

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

Удаление невидимых поверхностей и линий Алгоритм, использующий z–буфер Формальное описание алгоритма z-буфера : 1. Заполнить буфер кадра фоновым значением интенсивности или цвета. 2. Заполнить z-буфер минимальным значением z. 3. Преобразовать каждый многоугольник в растровую форму в произвольном порядке. 4. Для каждого Пикселя (x, y) в многоугольнике вычислить его глубину z(x, y). 5. Сравнить глубину z(x, y) со значением Zбуфер(x, y), хранящимся в z-буфере в этой же позиции. Если z(x, y) > Zбуфер(x, y), то записать атрибут этого многоугольника (интенсивность, цвет и т. п. ) в буфер кадра и заменить Zбуфер(x, y) на z(x, y). В противном случае никаких действий не производить.

Удаление невидимых поверхностей и линий Алгоритм, использующий z–буфер Основное преимущество алгоритма — его простота. Алгоритм, использующий z-буфер решает задачу об удалении невидимых поверхностей и делает тривиальной визуализацию пересечений сложных поверхностей. Время работы алгоритма не зависит от сложности сцены. Поскольку габариты пространства изображения фиксированы, оценка вычислительной трудоемкости алгоритма не более чем линейна. Поскольку элементы сцены или картинки можно заносить в буфер кадра или в z-буфер в произвольном порядке, их не нужно предварительно сортировать по приоритету глубины. Это экономит вычислительное время, затрачиваемое на сортировку по глубине.

Удаление невидимых поверхностей и линий Алгоритм, использующий z–буфер Основной недостаток алгоритма – большой объем требуемой памяти. Если сцена подвергается видовому преобразованию и отсекается до фиксированного диапазона значений координат z, то можно использовать z-буфер с фиксированной точностью. Информацию о глубине нужно обрабатывать с большей точностью, чем координатную информацию на плоскости z(x, y), обычно бывает достаточно 20 -ти бит. Например буфер кадра размером 512´ 24 бит в комбинации с z-буфером размером 512´ 20 бит требует почти 1. 5 мегабайт памяти.

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

Удаление невидимых поверхностей и линий Алгоритм, использующий z–буфер Уменьшение требуемой памяти может достигаться разбиением пространства изображения на 4, 16 или больше квадратов или полос. В предельном варианте используется буфер размером в одну строку развертки. Для последнего случая был разработан алгоритм построчного сканирования. Поскольку каждый элемент сцены обрабатывается много раз, то сегментирование Z-буфера, вообще говоря, приводит к увеличению времени, необходимого для обработки сцены.

Удаление невидимых поверхностей и линий Алгоритм художника Метод художника относится к алгоритмам использующие список приоритетов. Такие алгоритмы пытаются получить преимущество посредством предварительной сортировки по глубине или приоритету. Цель такой сортировки в том, чтобы получить окончательный список элементов сцены, упорядоченных по приоритету глубины, основанному на расстоянии от точки наблюдения. Если такой список окончателен, то никакие два элемента не будут взаимно перекрывать друга. Тогда все элементы можно записать в буфер кадра поочередно, начиная с элемента, наиболее удаленного от точки наблюдения. Более близкие к наблюдателю элементы будут затирать информацию о более далеких элементах в буфере кадра. Эффекты прозрачности можно включить в состав алгоритма путем не полной, а частичной корректировки содержимого буфера кадра с учетом атрибутов прозрачных элементов.

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

Удаление невидимых поверхностей и линий Алгоритм художника Рассмотрим применение этого метода на примере изображения поверхности, заданной в виде однозначной функции двух переменных. Пусть поверхность задана уравнением: В качестве картинной плоскости используется плоскость XOY. Зададим сетку узлов на осях координат Тогда представляют собой набор «высот» для данной поверхности по отношению к плоскости XOY.

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

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

Удаление невидимых поверхностей и линий Алгоритм художника При изображении правильного многогранника можно легко упорядочить его грани по глубине; Для произвольного многогранника такая сортировка возможна не всегда. Для простой сцены окончательный список приоритетов может быть получен непосредственно. Многоугольники P, Q, R можно упорядочить по их максимальному или минимальному значению координаты z.


Удаление невидимых поверхностей и линий Алгоритм художника Рассмотрим более сложную сцену: Окончательный список приоритетов по глубине невозможно получить простой сортировкой по z. Если P и Q упорядочены по минимальному значению координаты z (zmin), окажется, что P в списке приоритетов по глубине будет стоять перед Q. При их записи в буфер кадра в таком порядке Q частично закрывает P. Однако фактически P частично закрывает Q.

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

Илон Маск рекомендует:  Ставим пароль на страницу

Удаление невидимых поверхностей и линий Алгоритм художника Аналогичные проблемы возникают и при «протыкании» многоугольников В обоих примерах окончательный список приоритетов невозможно установить сразу.

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

Удаление невидимых поверхностей и линий Алгоритм Ньюэла-Санча В связи с проблемами существовавшими у алгоритма художника Ньюэл М. , Ньюэл Р. и Санча предложили специальный метод сортировки для разрешения конфликтов, возникающих при создании списка приоритетов по глубине. Алгоритм динамически вычисляет новый список приоритетов перед обработкой каждого кадра сцены. При этом не накладывается никаких ограничений на сложность сцены и на тип многоугольников, используемых для описания элементов сцены. Первоначальный алгоритм Ньюэла — Санча был предназначен для обработки трехмерных тел. Его модификация не ограничена рамками многогранников и может обрабатывать тела смешанных типов в рамках одной сцены.

Удаление невидимых поверхностей и линий Алгоритм Ньюэла-Санча Рассмотрим алгоритм Ньюэла-Санча для случая многоугольников: I. Сформировать предварительный список приоритетов по глубине, используя в качестве ключа сортировки значение zmin для каждого многоугольника. Первым в списке будет многоугольник с минимальным значением zmin. Этот многоугольник лежит дальше всех от точки наблюдения, расположенной в бесконечности на положительной полуоси z. Обозначим его через P, а следующий в списке многоугольник — через Q. Для каждого многоугольника P из списка надо проверить его отношение с Q.

Удаление невидимых поверхностей и линий Алгоритм Ньюэла-Санча Если ближайшая вершина P (Pzmax) будет дальше от точки наблюдения, чем самая удаленная вершина Q (Qzmin), т. е. Qzmin ≥ Pzmax никакая часть P не может экранировать Q. P заносится в буфер кадра.

Удаление невидимых поверхностей и линий Алгоритм Ньюэла-Санча Если Qzmin

Краткий курс компьютерной графики: пишем упрощённый OpenGL своими руками, статья 3 из 6

Содержание курса

Улучшение кода

Official translation (with a bit of polishing) is available here.

А что потом? Я разобрал весь материал!

В статьях 7 и 8 мы поговорим о программировании непосредственно под OpenGL. Есть ненулевая вероятность получить краткий курс OpenCL/CUDA в статьях 9+.

Удаление невидимых поверхностей

Знакомьтесь, это мой друг z-buffer головы абстрактного африканца. Он нам поможет убрать визуальные артефакты отбрасывания задних граней, которые у нас оставались в прошлой статье.

Кстати, не могу не упомянуть, что эта модель, которую я использую в хвост и в гриву, была любезно предоставлена замечательным Vidar Rapp.

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

В теории можно не отбрасывать невидимые грани, а просто рисовать всё подряд, начав с самых задних, и заканчивая передними.

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

Перед отрисовкой головы отрисуем что попроще

Давайте представим себе простейшую сцену из трёх треугольников, камера смотрит сверху вниз, мы проецируем наши треугольники на белый экран:

Вот так должен выглядеть рендер этой сцены:

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

Три измерения — это слишком. Y-buffer!

Давайте потеряем одно из измерений, рассмотрим двумерную сцену, полученную пересечением нашей сцены и жёлтой плоскости разреза:

То есть, наша сцена состоит из трёх отрезков (пересечение жёлтой плоскости и каждого из треугольников), а её рендер — это картинка
той же ширины, что и нормальный рендер, но в один пиксель высотой:

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

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

Давайте теперь её рендерить. Напоминаю, рендер — это картинка шириной во всю сцену и высотой в один пиксель. В моём коде я её объявил высотой в 16, но это чтобы не ломать глаза, рассматривая один пиксель на экранах высокого разрешения. Функция rasterize пишет только в первую строчку картинки render.

Итак, я объявил загадочный массив ybuffer ровно в размер нашего экрана (width, 1). Этот массив инициализирован минус бесконечностью. Затем я передаю в функцию rasterize и картинку render, и этот загадочный массив. Как выглядит сама функция?

Очень-очень просто: я прохожу по всем x-координатам между p0.x и p1.x и вычисляю соответствующую y-координату нашей линии.
Затем я проверяю, что у нас в массиве ybuffer по этой координате x. Если текущий пиксель ближе к камере, нежели то, что там сохранено,
то я и его рисую в картинке, и ставлю новую y-координату в игрек-буфере.

Давайте разбираться поэтапно: после вызова растеризатора для первой (красной) линии вот что мы имеем в памяти:

Здесь мерзким фиолетовым цветом отмечена минус бесконечность, это те места, где ни одного пикселя ещё нарисовано не было.
Всё остальное градациями серого, т.к. ybuffer это не цвет, а глубина данного пикселя. Чем белее, тем ближе к камере был данный нарисованный на экране пиксель.

Дальше мы рисуем зелёную линию, вот память после вызова её растеризатора:

Ну и напоследок синюю:

Поздравляю вас, мы нарисовали нашу двумерную сцену! Ещё раз полюбуемся на финальный рендер:

Три измерения — это в самый раз. Z-buffer!

Снимок кода на гитхабе.
Внимание: в этой статье я использую ту же самую версию растеризатора треугольника, что и в предыдущей. Улучшенная версия растеризатора (проход всех пикселей описывающего прямоугольника) будет вскорости любезно предоставлена и описана в отдельной статье уважаемым gbg! Stay tuned.

Поскольку у нас экран теперь двумерный, то z-буфер тоже должен быть двумерным:

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

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

Это просто ужасно, насколько код похож на растеризатор из прошлой статьи. Что изменилось? (Используйте vimdiff и посмотрите).
Vec2 был заменён на Vec3 в вызове функции и сделана проверка if (zbuffer[idx]

Всё! Вот наш настоящий рендер без огрехов отсечения невидимых поверхностей:

Обратите внимание, что backface culling в моём коде оставлен:

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

Стоп, мы только что интерполировали z-координату. А можно добавить ещё чего в нагрузку?

Текстуры! Это будет домашняя работа.

В .obj файле есть строчки vt u v, они задают массив текстурных координат.
Среднее число между слешами в f x/x/x x/x/x x/x/x — это текстурные координаты данной вершины в данном треугольнике. Интерполируете их внутри треугольника, умножаете на ширину-высоту текстурного файла и получаете цвет пикселя из файла текстуры.
Диффузную текстуру брать здесь.

Опорный конспект лекций

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

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

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

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


Возможны следующие случаи :

· грань не закрывает ребро;

· грань полностью закрывает ребро;

· грань частично закрывает ребро (в этом случае ребро разбивается на

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

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

Одним из самых простых алгоритмов удаления невидимых граней и поверхностей является метод Z-буфера (буфера глубины). В силу крайней простоты этого метода (OpenGL) часто встречаются его аппаратные реализации. Сопоставим каждому пикселу (x, y) картинной плоскости его расстояние вдоль направления проектирования z(x, y) — его глубину. Изначально массив глубин инициализируется бесконечностью. Для вывода на картинную плоскость произвольной грани она переводится в свое растровое представление и для каждого пиксела этой грани находится его глубина. В случае, если эта глубина меньше значения глубины, хранящегося в Z-буфере, то этот пиксел рисуется и его глубина заносится в Z-буфер.

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

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

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

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

2.4Принципы построения полутоновых изображений

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

Разработано множество способов закрашивания : гранением, пропорциональное закрашивание, закрашивание по способу Гуро, закрашивание по способу Фонга, закрашивание способом трассировки лучей (лучей зондирования). Эти способы требуют различного количества процессорного времени и, следовательно, обеспечивают различное качество изображения.

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

Однако способ слишком примитивен; закрашенные этим способом объекты выглядят не плавными.

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

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

· вычисление нормалей к поверхности;

· определение нормалей в вершинах путем усреднения нормалей по граням,

которым принадлежит данная вершина;

· вычисление интенсивности в вершинах;

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

Основной недостаток — эффект полосы Маха : на ребрах смежных многоугольников возникает полоса разрыва непрерывности.

Закрашивание по способу Фонга решает проблемы полосы Маха, поскольку предполагает плавное изменение яркости и насыщенности не только вдоль ребер каждого многоугольника, но и по самой поверхности (вдоль сканирующей строки интерполируется значение вектора нормали, который затем используется в модели освещения для вычисления интенсивности пиксела). При этом даже зеркальные блики на поверхностях выглядят вполне правдоподобно (в 3D Studio 4.0 помимо методов Гуро и Фонга добавилось еще закрашивание Metal).

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

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

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

Для придания более естественного вида сцене желательно иметь возможность менять параметры поверхности (в простейшем случае — цвет).

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

· процедурные (сплошные) текстуры.

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

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

Тема 3Удаление невидимых линий и поверхностей

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

Необходимость удаления невидимых линий, ребер, поверхностей или объемов проиллюстрирована рис. 4.1. На рис. 4.1,а приведен типичный каркасный чертеж куба. Каркасный чертеж представляет трехмерный объект в виде штрихового изображения его ребер. Рис. 4.1,а можно интерпретировать двояко: как вид куба сверху, слева или снизу, справа. Для этого достаточно прищуриться и перефокусировать глаза. Удаление тех линий или поверхностей, которые невидимы с соответствующей точки зрения, позволяют избавиться от неоднозначности. Результаты показаны на рис. 4.1,b и с.

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

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

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

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

3.1Алгоритм плавающего горизонта

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

Поскольку в приложениях в основном интересуются описанием поверхности, этот алгоритм обычно работает в пространстве изображения. Главная идея данного метода заключается в свведении трехмерной задачи к двумерной путем пересечения исходной поверхности последовательностью параллельных секущих плоскостей, имеющих постоянные значения координат x, y или z. Например, если указанные параллельные плоскости определяются постоянными значениями z. Функция F(x,у,z) = 0 сводится к последовательности кривых, лежащих в каждой из этих параллельных плоскостей, например к последовательности y = f(x,z) или х = g(y,z), где z постоянно на каждой из заданных параллельных плоскостей.

Итак, поверхность теперь складывается из последовательности кривых, лежащих в каждой из этих плоскостей, как показано на рис. 4.2. Здесь предполагается, что полученные кривые являются однозначными функциями независимых переменных. Если спроецировать полученные кривые на плоскость z = 0, то сразу становится ясна идея алгоритма удаления невидимых участков исходной поверхности. Алгоритм сначала упорядочивает плоскости z = const по возрастанию расстояния до них от точки наблюдения. Затем для каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая, лежащая на ней, т. е. для каждого значения координаты х в пространстве изображения определяется соответствующее значение y. Алгоритм удаления невидимой линии заключается в следующем:

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

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

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

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

Алгоpитм «Плавающий гоpизонт»

Фyнкция? типа y=F(x,z)? Тогда — «плавающим гоpизонтом» ея. Вкpатце: Выделяется 2 массива pазмеpностью = числy точек по гоpизонтали — веpхний и нижний гоpизонты. веpхний инициализиpyется минимально возможным значением, нижний — соотв. максимально возможным.

if( y > веpхний[x] || y s , y s , z s ) лежит на плоскости, то ax s + by s + cz s + d = 0. Если же S не лежит на плоскости, то знак этого скалярного произведения показывает, по какую сторону от плоскости расположена точка. В алгоритме Робертса предполагается, что точки, лежащие внутри тела, дают положительное скалярное произведение.

Пусть F 1 , F 2 , . F n — грани многогранника. Рассмотрим одну из граней. Обозначим вершины, инцидентные грани, через V1, V2, . Vk. Найдем вектор нормали к грани, вычислив векторное произведение любых двух смежных ребер этой грани V 1 V 2 = [x 1 ,y 1 ,z 1 ] и V 2 V 3 = [x 2 ,y 2 ,z 2 ]:

Тогда опорная функция грани имеет вид:

L i (x,y,z) = A i х + B i y + C i z + D

Величина D вычисляется с помощью произвольной точки на плоскости. В частности, если компоненты этой точки на плоскости (х 1 ,y 1 ,z 1 ), то:

D = -(ах 1 + by 1 + cz 1 )

Так как многогранник выпуклый, коэффициенты A i , B i , C i легко выбрать так, чтобы n i (A i , B i , C i ) был вектором внешней нормали. Для этого найдем какую-либо внутреннюю точку, например, барицентр многогранника:

W = (V 1 + V 2 + . + V k )/k

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

Алгоритм Робертса
V1, V2, V3 — вершины многогранника
W — барицентр многогранника
P — точка наблюдения

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

Для каждого тела из приоритетного списка:

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

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

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

Удаление невидимых граней. Алгоритм z-буфера

Это один из простейших алгоритмов удаления невидимых поверхностей. Впервые он был предложен Кэтмулом. Работает этот алгоритм в пространстве изображения.

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

Основной недостаток алгоритма — большой объем требуемой памяти. Если сцена подвергается видовому преобразованию и отсекается до фиксированного диапазона координат z значений, то можно использовать z-буфер с фиксированной точностью. Информацию о глубине нужно обрабатывать с большей точностью, чем координатную информацию на плоскости (x, y); обычно бывает достаточно 20 бит. Буфер кадра размером 512*512*24 бит в комбинации с z-буфером размером 512*512*20 бит требует почти 1.5 мегабайт памяти.

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

Формальное описание алгоритма z-буфера:

1) заполнить буфер кадра фоновым значением интенсивности или цвета;
2) заполнить z-буфер минимальным значением z;
3) преобразовать каждый многоугольник в растровую форму в произвольном порядке;
4) для каждого Пиксел(x, y) в многоугольнике вычислить его глубину z(x, y);
сравнить глубину z(x, y) со значением Zбуфер(x, y), хранящимся в z-буфере в этой же позиции;
5) если z(x, y) > Zбуфер(x, y), то записать атрибут этого многоугольника (интенсивность, цвет и т. п.) в буфер кадра и заменить Zбуфер(x, y) на z(x, y);
6) в противном случае никаких действий не производить.

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

Оптимизация алгоритма

Одним из наиболее распространённых модификаций алгоритма z-буфера является алгоритм иерархического z-буфера. Назовём грань скрытой (невидимой) по отношению к z-буферу, если для всех её точкек их глубины не меньше соответствующих значений в z-буфере (при попытке вывести такую грань в z-буфер ничего не изменится). Куб (прямоугольный параллелепипед) назовём скрытым по отношению к z-буферу, если все его лицевые грани являются скрытыми. Теперь объединим несколько граней сцены и обведём вокруг них куб. Для вывода этих граней в z-буфер проверяется, является ли этот куб скрытым по отношению к z-буферу. Если это так, что и все грани, объединённые кубом являются скрытыми по отношению к z-буферу и не выводятся в него, сокращая количество вычислений и ненужных операций сравнения. Если же это не так, то всё равно не все грани, объединённые кубом являются видимыми и этот куб разбивается на части, а затем для каждой части выполняются такие же операции сравнения. Таким образом реализация данного алгоритма может выглядеть следующим образом. Вокруг всей сцены описывается куб, он разбивается на 8 частей (тоже кубы), а каждая из частей, в свою очередь, разбивается ещё на 8 частей и так до тех пор, пока количество граней в кубе не станет меньше заданного числа, при котором уже нет смысла в дальнейшей разбивке на части. Далее для вывода очередного куба в z-буфер для него проверяется, является он скрытым или нет. Если да, то все грани, объединённые этим кубом игнорируются, а если нет, то соответствующая проверка выполняется для всех его частей и т.д

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

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL