35. Алгоритм определения видимых поверхностей путем трассировки лучей. - p1xelse/CG GitHub Wiki

(сайт: https://www.intuit.ru/studies/courses/70/70/lecture/2102?page=5)

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

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

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

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

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

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

Также применяется габаритный тест. Удобно провести преобразование, которое совместит трассирующий луч с осью Oz. Тогда останется исследовать знаки xmin, xmax и ymin, ymax прямоугольной оболочки. если они меняются в каждой паре - фиксируем возможное пересечение.

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

Основные шаги алгоритма [что-то странное со смешением оболочек и очерёдностью шагов] Версия Куруша

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

2.1. для каждого активного объекта:

  • если поднят флаг прямоуг-теста - производим (надо преобразовать оболочку).
  • преобразуем объект в ск луча, определяем пересечения с лучом. заносим все пересечения в список пересечений.

2.2. определяем zmax списка пересечений (если пуст, ставим цвет фона).

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

Основные шаги алгоритма [оригинальное представление из источника]

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

  1. полное описание объекта: тип, поверхность, характеристики, тип оболочки и т.п.;
  2. описание оболочки: центр и радиус для сферы или шесть значений для параллелепипеда (Xmin, Xmax, Y..., Z...)

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

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

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

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

две модификации для повышения быстродействия

1-й модифик кластерные группы пространственно связанных объектов.... кошмар

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

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

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

image image