Удаление невидимых линий

· Лекция 9. Удаление невидимых линий.

1 Задача преодоление неоднозначности

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

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

2.2 Алгоритм Ньюэла М., Ньюэла Р.и Санча

2.3 Алгоритм, использующий Z-буфер

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

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

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

Рекомендуемые материалы

Рисунок . Ликвидация неоднозначности визуального представления модели

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

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

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

Выбор подходящего алгоритма зависит от нескольких факторов:

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

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

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

Рассматриваемые алгоритмы можно классифицировать по системе координат в которой они работают:

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

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

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

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

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

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

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

Алгоритм обычно работает в пространстве изображения.

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

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

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

            

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

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

Алгоритм удаления невидимой линии заключается в следующем:

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

Невидимые участки показаны пунктиром на рисунке 3.

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

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

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

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

 

Ньюэл М., Ньюэл Р.и Санча

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

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

Рис 1. Установление приоритетов для многоугольников.

Для простой сцены, вроде той, что показана на рис. 1, а, окончательный список приоритетов можно получить непосредственно. Например, эти многоугольники можно упорядочить по их максимальному или минимальному значению координаты z. Однако уже для сцены, показанной на рис.1, b, окончательный список приоритетов по глубине невозможно получить простой сортировкой по z. Если Р и Q с рис. 1, b упорядочены по минимальному значению координаты z (z_min), окажется, что P в списке приоритетов по глубине будет стоять перед Q. Если их записать в буфер кадра в таком порядке, то получится, что Q частично экранирует Р. Однако фактически Р частично экранирует Q. Правильный порядок в списке приоритетов будет тогда, когда Р и Q поменяются местами.

Другие трудности показаны на рис. 2. Здесь многоугольники циклически перекрывают друг друга. На рис. 2, а Р находится впереди Q, который лежит впереди R, который, в свою очередь, находится впереди Р. На рис. 2, b Р экранирует Q, a Q экранирует Р. Аналогичное циклическое экранирование возникает при протыкании многоугольников.

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

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

Рис. 2. Циклически перекрывающиеся многоугольники.

Алгоритм Ньюэла-Нюэла-Санча

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

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

· Для каждого многоугольника Р из списка надо проверить его отношение с Q:

1. если ближайшая вершина Р (Рz_max) будет дальше от точки наблюдения, чем самая удаленная вершина Q (Qz_min), т.е. Qz_min >= Рz_max и никакая часть Р не может экранировать Q. Занести Р в буфер кадра (рис.1, а);

2. если Qz_min < Рz_max потенциально P экранирует не только Q, но также и любой другой многоугольник типа Q из списка, для которого Qz_min < Рz_max. Тем самым образуется множество [Q]. Однако Р может фактически и не экранировать ни один из этих многоугольников. Если последнее верно, то Р можно заносить в буфер кадра. Для ответа на этот вопрос используется серия тестов, следующих по возрастанию их вычислительной сложности.

Эти тесты ниже формулируются в виде вопросов. Если ответ на любой вопрос будет положительным, то Р не может экранировать {Q}. Поэтому Р сразу же заносится в буфер кадра.

Вот эти тесты:

a. Верно ли, что прямоугольные объемлющие оболочки Р и Q не перекрываются по х ?

b. Верно ли, что прямоугольные оболочки Р и Q не перекрываются по у ?

c. Верно ли, что Р целиком лежит по ту сторону плоскости, несущей Q, которая расположена дальше от точки наблюдения (рис.3,а)?

d. Верно ли, что Q целиком лежит по ту сторону плоскости, несущей P, которая ближе к точке наблюдения (рис. 3, b)?

e. Верно ли, что проекции Р и Q не перекрываются?

Каждый из этих тестов применяется к каждому элементу {Q}. Если ни один из них не дает положительного ответа и не заносит Р в буфер кадра, то Р может закрывать Q.

Поменять Р и Q местами, пометив позицию Q в списке. Повторить тесты с новым списком. Это дает положительный результат для сцены с рис. 1, b.

Рис. 3. Тесты для перекрывающихся многоугольников.

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

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

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

Алгоритм использующий Z-буфер

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

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

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

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

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

 

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

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

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

· преобразовать каждый многоугольник в растровую форму в произвольном порядке;

· для каждого Пиксел(x, y) в многоугольнике вычислить его глубину z(x, у);

· сравнить глубину z(x, у) со значением Z буфер( x, у), хранящимся в z -буфере в этой же позиции;

· если z(х, у) > Z буфер (х, у), то записать атрибут этого многоугольника (интенсивность, цвет и т. п.) в буфер кадра и заменить Z буфер( х, у) на z ( х, у);

· в противном случае никаких действий не производить;

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

Интервальный алгоритм построчного сканирования

В алгоритме построчного сканирования с использованием z-буфера глубина многоугольника вычисляется для каждого пиксела на сканирующей строке. Количество вычислений глубины можно уменьшить, если использовать понятие интервалов, впервые введенных в алгоритме Ваткинса. На рис. 1, а показано пересечение многоугольников со сканирующей плоскостью. Решение задачи удаления невидимых поверхностей сводится к выбору видимых отрезков в каждом из интервалов, полученных путем деления сканирующей строки проекциями точек пересечения ребер. Из рисунка видно, что возможны только три варианта:

Рис. 1. Интервалы для построчного сканирования.

Интервал пуст, как, например, интервал 1 на рис. 1.а. - изображается фон.

Интервал содержит лишь один отрезок, как, например, интервалы 2 и 4 на рис. 1.а. - изображаются атрибуты многоугольника, соответствующего отрезку.

Интервал содержит несколько отрезков, как, например, интервал 3 на рис. 1.а. В этом случае вычисляется глубина каждого отрезка в интервале. Видимым будет отрезок с максимальным значением г. В этом интервале будут изображаться атрибуты видимого отрезка.

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

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

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

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

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

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

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

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

· Если требуется, то рекурсивное подразбиение и окончательная сортировка для устранения всех неопределенностей.

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

Рис. 4.44. Отсечение многоугольников по приоритетам для алгоритма удаления невидимых поверхностей Вейлера — Азертона.

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

С помощью алгоритма отсечения Вейлера — Азертона все многоугольники отсекаются по границам отсекающего многоугольника. Фактически это двумерная операция отсечения проекций отсекающего и отсекаемого многоугольников. Та часть каждого отсекаемого многоугольника, которая оказывается внутри отсекающего, если она имеется, попадает во внутренний список. Оставшаяся часть, если таковая есть, попадает во внешний список. Этот этап алгоритма является сортировкой на плоскости или ху -сортировкой. Затем, сравниваются глубины всех вершин многоугольнов из внутреннего списка с глубиной отсекающего многоугольника. Если глубина ни одной из этих вершин не будет больше Zmin отсекающего, то все многоугольники из внутреннего списка экранируются отсекающим многоугольником. Эти многоугольники удаляются, и изображается внутренний список. Заметим, что во внутреннем списке остался лишь отсекающий многоугольник. Работа алгоритма затем продолжается с внешним списком.

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

Более полной иллюстрацией этого алгоритма послужит следую­щий простой пример

Рис. 4.46. Условие возникновения ошибочного результата в предварительной сортировке по z.

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

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

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

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

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

Рис. 4

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

Чтобы избавиться от ненужного поиска пересечений, производится проверка пересечения луча с объемной оболочкой рассматриваемого объекта. И если луч не пересекает оболочки, то не нужно больше искать пересечений этого объекта с лучом. В качестве оболочки можно использовать прямоугольный параллелепипед или сферу, рис. 5. Факт пересечения трехмерного луча со сферой определяется очень просто. В частности, если расстояние от центра сферической оболочки до луча превосходит радиус этой сферы, то луч не пересекает оболочки. Следовательно, он не может пересечься и с объектом.

Рис. 5. Объемлющие оболочки

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

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

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

· Подготовка данных для сцены;

· Создать список объектов, содержащий по меньшей мере следующую информацию:

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

o Описание сферической оболочки: центр и радиус. Флаг прямоугольной оболочки.  Если этот флаг поднят,  то будет выполнен габаритный тест с прямоугольной оболочкой, если же он опушен, то тест выполняться не будет. Заметим, что габаритный тест необходим не для всех объектов, например для сферы он не нужен.

o Описание  прямоугольной  оболочки:

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

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

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

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

· Если пересечения с лучом нет, то перейти к следующему объекту.

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

Вместе с этой лекцией читают "7. Принципы деятельности библиотек".

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

· В противном случае определить Zmax. для списка пересечений.

· jlВычислить преобразование, обратное комбинированному преобразованию.

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

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

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