На этом шаге мы рассмотрим алгоритм базовой операции обратной трассировки лучей.

    Запишем базовую операцию обратной трассировки лучей в виде функции, которую назовем ЛУЧ. Она вычисляет значение интенсивности для текущего трассируемого луча. Для описания функции используем псевдокод, близкий по синтаксису языку С.

интенсивность ЛУЧ (номер итерации ind, тип луча,
    направление луча dir, номер объекта no)
{
  Находим точку пересечения луча с ближайшим объектом.
  Если точка найдена, то
  {
    no = номер пересекаемого объекта.
    Вычисляем нормаль к видимой стороне поверхности объекта.
    Если (Kd > 0) то	// задано свойство диффузного отражения
    {
      Id = Интенсивность для диффузного отражения.
    }
    Если (Ks > 0) то // зеркальные блики от источников света
    {
      Определяем направление отраженного луча dirR.
      Is = Интенсивность зеркальности.
    }
    Если (Кr > 0) то // зеркальное отражение других объектов
    {
      Определяем направление отраженного луча dirR.
      Ir = ЛУЧ (ind+1, отраженный, dirR, no).
    }
    Если (Kt > 0) то // объект полупрозрачный
    {
      Определяем направление преломленного луча dirT.
      It = ЛУЧ (ind+1, преломленный, dirT, no).
    }
    return Ka Ia С + Kd Id C + Ks Is + Kr Ir + Kt It.
  }
  иначе
  {
    Это означает, что луч уходит в свободное пространство. 
    return значение интенсивности по умолчанию.
  }
}

    Функция ЛУЧ представлена здесь в схематичном и достаточно обобщенном виде (хотя и не в самом общем - например, здесь не предусмотрено диффузное преломление). Для правильного функционирования процесса обратной трассировки необходимо предусмотреть еще некоторые действия, которые не описаны в тексте функции. Так, например, необходимо предусмотреть, чтобы при трассировке первичного луча можно было бы получить изображение источников света, не заслоняемых другими объектами. Кроме того, когда выпускается преломленный луч от границы внутрь некоторого объекта, и далее, когда он достигнет внешней границы, то в этот момент можно заблокировать появление зеркального луча, направленного внутрь объекта (например, при моделировании стеклянной линзы, заданной в виде объема, ограниченного некоторой поверхностью). Также следует предусмотреть, чтобы зеркальный луч мог быть выпущен при трассировке преломленного луча, но только если луч пересекает иной объект, нежели тот, от границы объема которого началось преломление (например, при изображении рыбок в аквариуме). Для этого предусмотрены аргументы тип луча и номер объекта. Для предотвращения "зацикливания" (например, при попадании луча внутрь пространства, ограниченного зеркальными стенками) предусмотрен аргумент номер итерации. Этот же аргумент можно использовать для распознавания первичного луча.

    Вы, наверное, уже заметили, что определение функции ЛУЧ является рекурсивным, то есть в теле функции присутствуют вызовы этой же функции. Так можно достаточно просто моделировать все дерево лучей: сначала первичный луч, затем - порождающиеся вторичные, третичные и так далее. Весь процесс обратной трассировки для одной точки изображения представляется в виде единственной строчки

  I = ЛУЧ (1, первичный, направление проецирования, 0).

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

    В ходе трассировки лучей необходимо определять точки пересечения прямой линии луча с объектами. Способ определения точки пересечения зависит от того, какой это объект, и каким образом он представлен в некоторой графической системе. Так, например, для объектов, представленных в виде многогранников и полигональных сеток, можно использовать известные методы определения точки пересечения прямой и плоскости, рассматриваемые в аналитической геометрии [1]. Однако если ставится задача определения пересечения луча с гранью, то необходимо еще, чтобы найденная точка пересечения лежала бы внутри контура грани.

    Известны несколько способов проверки произвольной точки на принадлежность полигону. Рассмотрим две разновидности, в сущности, одного и того же метода (рисунок 1).

Рис.1. Точка является внутренней, если:
а - точка принадлежит секущему отрезку, б - число пересечений нечетно

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

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

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

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

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

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

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

    На следующем шаге мы закончим изучение этого вопроса.

Предыдущий шаг Содержание Следующий шаг