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

· Удаление нелицевых граней многогранника. Алгоритм Робертса

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

· Вейлера — Азертона.

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

· Методы приоритетов (художника, плавающего горизонта).

· Алгоритмы построчного сканирования для криволинейных поверхностей.

· Метод двоичного разбиения пространства

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

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

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

Неоднозначность восприятия изображения куба

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

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

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

Удаление нелицевых граней многогранника. Алгоритм Робертса

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

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

Внешние нормали тетраэдра

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

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

Умножая столбцы матрицы на вектор , получим n-мерный вектор, и если все его компоненты неотрицательны, то точка принадлежит многограннику. Это условие будем записывать в виде  (имеется в виду умножение вектор-строки на матрицу).

В своем алгоритме Робертс рассматривает только отрезки, являющиеся пересечением граней многогранника.

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

Эту систему можно записать в матричном виде:

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

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

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

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

В отличие от алгоритма Робертса, Варнок в 1968 г. предложил алгоритм, работающий не в объектном пространстве, а в пространстве образа. Он также нацелен на изображение многогранников, а главная идея его основана на гипотезе о способе обработки информации, содержащейся в сцене, глазом и мозгом человека. Эта гипотеза заключается в том, что тратится очень мало времени и усилий на обработку тех областей, которые содержат мало информации. Большая часть времени и труда затрачивается на области с высоким информационным содержимым. Так, например, рассматривая помещение, в котором имеется только картина на стене, мы быстро осматриваем стены, пол и потолок, а затем все внимание сосредоточиваем на картине. В свою очередь, на этой картине, если это портрет, мы бегло отмечаем фон, а затем более внимательно рассматриваем лицо изображенного персонажа, в особенности глаза, губы. Как правило, достаточно детально рассматриваются еще и руки и с чуть меньшим вниманием - одежда.

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

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

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

· внешним, если он целиком находится вне окна;

· внутренним, если он целиком расположен внутри окна;

· пересекающим, если он пересекает границу окна;

· охватывающим, если окно целиком расположено внутри него.

Варианты расположения многоугольника по отношению к окну

Теперь можно в самом общем виде описать алгоритм.

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

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

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

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

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

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

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

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

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

Алгоритм Вейлера-Азертона

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

1. Предварительная сортировка по глубине.

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

3. Удаление многоугольников, экранируемых более близкими к точке наблюдения многоугольниками.

4. Если требуется, то рекурсивное разбиение и новая сортировка.

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

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

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

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

Приведем формальное описание последовательности действий алгоритма, использующего z-буфер:

§ заполнить буфер кадра фоновым значением цвета;

§ заполнить z-буфер минимальным значением z;

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

преобразовать его в растровую форму;

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

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

ax + by + cz + d = 0 или (при c ≠ 0) z = – (ax + by + d ) / c.

За исключением ряда особых случаев расположения такой плоскости, многоугольники целесообразно обрабатывать построчно, переходя по горизонтали от пикселя к пикселю пошагово. На сканирующей строке y = const поэтому на каждом таком шаге приращение (на Δ x) получает только горизонтальная координата. Если пиксель с координатами (x_i , y) уже обработан и определена его глубина z_i , при переходе к следующему пикселю с координатами (x_i+1 , y), где x_i+1 = x_i + Δ x, приращение глубины определяется выражением

z_i+1 – z_i = – (ax_i + a Δ x + by + d ) / c + (ax_i + by + d ) / c = – (a / c) Δ x.

С учетом же того, что Δ x = 1, глубину очередного пикселя можно рассчитать по очень простой формуле:

z_i+1 = z_i – (a / c).

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

Демонстрация метода Z-буфера.

Методы приоритетов (художника, плавающего горизонта)

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

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

Данный алгоритм относится к группе алгоритмов, реализующих удаление невидимых линий и поверхностей. Чаще всего он используется для визуализации трехмерных поверхностей, описываемых функциями вида F (x, y, z) = 0. Главная идея заключается в сведении трехмерной задачи к двумерной: поверхность сечется параллельными и равноотстоящими друг от друга плоскостями, и на экран выводятся линии пересечения (рис.9.1). Так, например, при задании секущих плоскостей постоянными значениями z поверхность представляется совокупностью кривых, которые описываются функциями y = f (x, z) при z = const, т.е. y = f (x). Плоскости z = const сортируют по степени их удаленности от точки наблюдения. Затем поочередно для каждой плоскости, начиная с ближней, строится лежащая на ней кривая. При этом для каждого из значений х, задаваемых в пространстве изображения (в координатной плоскости экрана) с шагом, равным расстоянию между пикселями (т.е. единице), определяется значение у. Если на текущей кривой при конкретном значении х соответствующее значение у больше или, наоборот, меньше, чем значения y для всех предыдущих кривых при том же значении х, то текущая кривая полагается видимой в данной точке; в противном случае она считается невидимой (на рис.10.1 невидимые участки кривых показаны пунктиром).

Для хранения максимальных и минимальных значений у при каждом значении х используются два массива чисел: массив верхнего горизонта и массив нижнего горизонта (они отражают текущее состояние «верхнего горизонта» и «нижнего горизонта» соответственно). Очевидно, что по мере обработки кривых значения в первом массиве могут только увеличиваться («верхний горизонт» всплывает), а во втором – только уменьшаться («нижний горизонт» опускается). При использовании таких массивов текущая кривая в какой-либо точке полагается видимой, если при заданном значении x значение у либо больше соответствующего значения в массиве верхнего горизонта, либо меньше аналогичного значения в массиве нижнего горизонта. Если кривая в данной точке видима, значение у заносится в один из массивов на место прежнего элемента.

Приведем уравнение, соответствующее линейной интерполяции кривой между двумя известными точками с координатами (x_n , y_n) и (x_n+k , y_n+k) (здесь k – шаг задания точек по оси х):

.

При изложенном подходе, когда обрабатываемая текущая кривая появляется слева или справа из-под множества ранее обработанных кривых, может появиться некорректность в изображении поверхности – эффект зазубренного ребра (на рис.10.2 приводящие к искажению фрагменты кривой показаны пунктиром). Избежать такого эффекта можно относительно простым приемом: при обработке каждой текущей кривой (за исключением первой) создаются ложные боковые ребра, соединяющие соответственно крайние левые и крайние правые точки текущей и предыдущей кривых (на рис.9.2 – штрихпунктирные линии). Ложные ребра на экран не выводятся, но ординаты точек на них при тех дискретных значениях x, при которых ребра определены, участвуют в формировании массивов верхнего и нижнего горизонтов (при тех же условиях, что и сами кривые).

С учетом приведенных соображений формальное описание последовательности действий алгоритма плавающего горизонта можно описать примерно так: поочередно для каждой из равноотстоящих друг от друга плоскостей z = const, начиная с ближней от точки наблюдения:

§ определить координаты первой (левой) точки P_n на лежащей в плоскости кривой y = f (x);

§ обработать левое боковое ребро: если точка P_n является первой точкой на первой кривой, то запомнить ее в качестве P_n–1 и закончить обработку; в противном случае создать ребро, соединяющее P_n–1 и P_n , занести, если это требуется, ординаты точек ребра в массивы верхнего и нижнего горизонтов и запомнить P_n в качестве P_{n–1 ;}

§ определить координаты остальных точек на кривой y = f (x) при дискретном изменении x с единичным шагом, в том числе последней (правой) точки Q_n ;

§ если y = f (x) является первой обрабатываемой кривой, занести значения y всех точек на ней для соответствующих x в массивы верхнего и нижнего горизонтов и закончить обработку, если нет, тогда: сравнить для каждой точки на кривой значение y с имеющимися в массивах верхнего и нижнего горизонтов (для соответствующего значения x); если y точки не меньше, чем в массиве верхнего горизонта, или не больше, чем в массиве нижнего горизонта, или значения в массивах отсутствуют, объявить точку видимой и занести y точки в соответствующий массив (или в оба массива); в противном случае объявить точку невидимой;

§ обработать правое боковое ребро: если точка Q_n является последней точкой на первой кривой, то запомнить Q_n в качестве Q_n–1 и закончить обработку; в противном случае создать ребро, соединяющее Q_n–1 и Q_n , занести, если это требуется, ординаты точек ребра в массивы верхнего и нижнего горизонтов и запомнить Q_n в качестве Q_n–1 .

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

Демонстрация алгоритма (Автор Мартынов Николай МИРЭА 2000 г.)

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

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

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

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

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

Разбиение пространства и соответствующее ему дерево

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

Главная идея этого алгоритма была предложена в 1968 г. А.Аппелем, а первая реализация была выполнена в 1971 г.

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

Трассировка параллельными лучами

Трассировка с центральной точкой

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

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

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

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

Создать список объектов, содержащий:

· полное описание объекта: тип, поверхность, характеристики, тип оболочки и т.п.;

· описание оболочки: центр и радиус для сферы или шесть значений для параллелепипеда .

Для каждого трассируемого луча:

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

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

· Найти пересечения со всеми активными объектами.

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

· В противном случае в списке пресечений найти ближайшее к наблюдателю (с максимальным значением z) и определить атрибуты точки.

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