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

Обновлено: 06.07.2024

Для построения правильного изображения ЗЭ-объектов необходимо уметь определять, какие части объектов (ребра, грани) будут видны при заданном проектировании, а какие будут закрыты другими гранями объектов.

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

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

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

Алгоритм Робертса для удаления невидимых ребер

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

содержимое экрана:

содержимое y-буфера:

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

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

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

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

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

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

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

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

Это просто ужасно, насколько код похож на растеризатор из прошлой статьи. Что изменилось? (Используйте vimdiff и посмотрите).
Vec2 был заменён на Vec3 в вызове функции и сделана проверка if (zbuffer[idx]<P.z);
Всё! Вот наш настоящий рендер без огрехов отсечения невидимых поверхностей:

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

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

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

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

Вот пример того, что должно получиться:

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

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

aх + by + cz + d = 0

Если любая точка S(x_s, y_s, z_s) лежит на плоскости, то ax_s + by_s + cz_s + d = 0. Если же S не лежит на плоскости, то знак этого скалярного произведения показывает, по какую сторону от плоскости расположена точка. В алгоритме Робертса предполагается, что точки, лежащие внутри тела, дают положительное скалярное произведение.

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

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

Так как многогранник выпуклый, коэффициенты A_i, B_i, C_i легко выбрать так, чтобы n_i(A_i, B_i, C_i) был вектором внешней нормали. Для этого найдем какую-либо внутреннюю точку, например, барицентр многогранника:

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

выделим одну из граней многогранника
Vec1.X = V1.X - V2.X; Vec2.X = V3.X - V2.X; Vec1.Y = V1.Y - V2.Y; Vec2.Y = V3.Y - V2.Y; Vec1.Z = V1.Z - V2.Z; Vec2.Z = V3.Z - V2.Z;	/ для этой грани найдем координаты двух векторов, которые лежат в плоскости грани
A = Vec1.Y·Vec2.Z - Vec2.Y·Vec1.Z; B = Vec1.Z·Vec2.X - Vec2.Z·Vec1.X; C = Vec1.X·Vec2.Y - Vec2.X·Vec1.Y; D = -(A·V1.X + B·V1.Y + C·V1.Z);	/ вычислим коэффициенты уравнения плоскости
m = -Sign(A·W.X + B·W.Y + C·W.Z + D);	/ коэффициент, изменяющий знак плоскости
A = A·m; B = B·m; C = C·m; D = D·m;	/ корректируем направление плоскости
if A·P.X + B·P.Y + C·P.Z + D > 0 then грань видима; отобразить грань else грань невидима

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поле вывода (с учетом границ) состоит из точек (x,y), которые удовлетворяют соотношения x_l≤x≤x_r и y_b≤y≤y_t . Допустим, что отрезок задан с помощью координат концевых точек (x₁,y₁) и (x₂,y₂). В начале алгоритма Коэна-Сазерленда выявляются полностью видимые и невидимые отрезки:

отрезок полностью принадлежит полю вывода, если его концы удовлетворяют условиям (x_l≤x₁≤x_r ,y_b≤y₁≤y_t и x_l≤x₂≤x_r, y_b≤y₂≤y_t);
отрезок является полностью невидимым, если его оба конца лежат:

справа от ребра r (x₁>x_r, x₂>x_r);
слева от ребра l (x₁l, x₂l);
снизу от ребра b (y₁b, y₂b);
сверху от ребра t (y₁>y_t, y₂>y_t).

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

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

$w=\<L,R,B,T\> ; \vec=(x_2-x_1,y_2-y_1)\equiv(l_x,l_y)$
(2).

$\vec<r_ На выходе получаем новые концевые точки >=(x_,y_), \vec>=(x_,y_ <20])$
(3), а также значение переменной IsVisible (0 - отрезок видимый)[4].

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

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

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

$\vec =(x_1,y_1),\vec=(x_2,y_2): \vec=\vec+s(\vec-\vec),s\in[-\infty,+\infty]$
(4),

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

, , , (5).

$L\leq x\leq R,y=T$

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

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

$s_T=\frac<T-y_1> ,L\leq x_1+s_T l_x\leq R$
(7).

$\vec<r_1> Аналогично запишутся формулы для оставшихся границ окна. Если точка$
расположена внутри поля вывода, то, в зависимости от знака l_y, необходимо искать пересечение либо с верхней, либо с нижней границей поля вывода (окна). Если такие пересечения отсутствуют, необходимо искать пересечения с двумя другими гранями окна (левой и правой стороной). До того как рассматривать выше описанные варианты, необходимо исключить случаи горизонтальных l_y = 0 (пересечение с правой или левой границей: (L,y₁), (R,y₁), в зависимости от знака l_x и вертикальных l_x = 0 (пересечение с верхней или нижней границей: (x₁,B), (x₁,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х)

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

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

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

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

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

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

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

легкая в случае прямоугольных окон и выпуклых многоугольников;
усложняется, если многоугольники невыпуклые

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

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

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

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