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

Трассировка лучей

Трассировка лучей - метод грубой силы (метод, не учитывающий специфику обрабатываемого объекта).

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

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

Случай, если точка расположена не в бексконечности (перспективная проекция).

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

Определение пересечений

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

Одно из решений - погружение объектов в выпуклую "оболочку". Например сферическую, или в форме параллепипеда. Таким образом, можем проверить пересечения луча с объектом (оболочкой).
Если луч не пересекает оболочки, то объект можно откинуть, и не искать пересечения луча и этого объекта.

Сферический тест

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

Габаритный тест

Тест при прямоугольной оболочке

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

• Выполнение габаритного теста с прямоугольной оболочкой в трехмерном пространстве требует большого объема вычислений.
• Следует проверить пересечение по меньшей мере с тремя бексконечностями плоскостями (я не понял о чем речь)
• Более медленный, чем со сферической оболочкой.

Алгоритм

1. Создание списка объектов. 
   а) Полное описание объекта (тип, пов-ть, хар-ки)
   б) Описание сферической оболочки.
   в) Флаг прямоугольной оболочки (если нужны габаритные тесты)
2. Для каждого луча выполнить:
   2.1. Для каждого объекта выполнить тест со сферич. оболочкой. 
        Если объект проходит тест, то заносим его в список активных объектов.
   2.2. Если список пуст, изобразить пиксель цветом фона. Иначе,
        перенос и поворот луча для совмещения с OZ (запомнить преобразование)
3. Для каждого активного объекта:
   3.1. Если поднят флаг прямоугольной оболочки, преобразовать эту оболочку в СК луча
        и выполнить соответствующий тест.
   3.2. Преобразовать объект в СК луча, определить его пересечение с лучом. 
        Занести все пересечения в список пересечений.
4. Если список пуст, то ставим пиксель цветом фона. Иначе, определить zmax
   для списка пересечений. 
5. Вычислить обратное преорбазование. Определяем с его помощью т. пересечения в
   исходной СК. Нарисовать пиксель с атрибутами объекта и модели освещения.
   // Пятый пункт для определения видимости не нужен.

Возможные модификации

1. Кластерные группы пространственно связанных объектов
Название ебнутое, но вроде не сложно.

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

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

2. Упорядочение по приоритету. Используется для сокращения числа объектов, для которых вычисляются пересечения.

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

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

Предыдущий вопрос: 34. Алгоритм построчного сканирования, использующий Z буфер. Интервальные методы построчного сканирования (основные предпосылки).