Трассировка пути (англ. path tracing) — методика рендеринга в компьютерной графике, которая стремится симулировать физическое поведения света настолько близко к реальному, насколько это возможно. Трассировка пути является продвинутым частным случаем традиционной трассировки лучей (англ. ray tracing), алгоритм которой трассирует лучи в направлении от виртуальной камеры сквозь пространство; луч «отскакивает» от предметов до тех пор, пока полностью не поглотится или рассеется. Качество изображений, получаемых при помощи метода трассировки пути, как правило, лучше, чем качество изображений, полученных другими методами рендеринга, однако трассировка пути требует гораздо больших затрат вычислительных ресурсов.

Трассировка пути является наиболее простым, наиболее точным с физической стороны и наиболее медленным по производительности методом рендеринга. Трассировка пути естественным способом воспроизводит множество оптических эффектов, которые тяжело достижимы или вообще недостижимы другими методиками рендеринга: построение теней, глубина резкости изображаемого пространства (англ. depth of field), шевелёнка (англ. motion blur), каустика, окружающее затенение и непрямое освещение. Осуществление этих оптических эффектов при помощи трассировки пути намного проще, чем при помощи других методик.

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

Уравнение рендеринга и его применение в компьютерной графике было представлено Джеймсом Кадзией (англ. James Kajiya) в 1986 году^[1]. Эта презентация была первым описанием алгоритма трассировки пути. Позже в этом году Лафортюн (англ. Lafortune) предложил много усовершенствований алгоритма, в том числе путём двунаправленной трассировки пути^[2].

Metropolis light transport^[англ.], метод возмущений ранее найденных путей для увеличения производительности в сложных сценах, был представлен в 1997 году Эриком Вичем (англ. Eric Veach) и Леонидасом Гимбасом (англ. Leonidas J. Guibas)^[3].

Через некоторое время графические процессоры достигли такого уровня развития, что смогли вызвать интерес к ним в плане перенесения на них расчётов трассировки пути. Тим Пюрселл (англ. Tim Purcell) в 2002 году первым представил алгоритм глобального освещения, который работал на графическом процессоре^[4]. В 2009 году Владимир Койлазов продемонстрировал первую коммерческую реализацию алгоритма трассировки пути, работающую на графическом процессоре^[5]. Этому способствовало созревание GPGPU-ориентированных инструментов программирования, таких как CUDA и OpenCL.

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

Такое поведение математически описано в уравнении рендеринга. Данное уравнение пытается решить алгоритмы трассировки пути.

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

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

  Color TracePath(Ray ray, count depth) {
    if (depth >= MaxDepth) {
      return Black;  // Bounced enough times.
    }

    ray.FindNearestObject();
    if (ray.hitSomething == false) {
      return Black;  // Nothing was hit.
    }

    Material material = ray.thingHit->material;
    Color emittance = material.emittance;

    // Pick a random direction from here and keep going.
    Ray newRay;
    newRay.origin = ray.pointWhereObjWasHit;

    // This is NOT a cosine-weighted distribution!
    newRay.direction = RandomUnitVectorInHemisphereOf(ray.normalWhereObjWasHit);

    // Probability of the newRay
    const float p = 1 / (2 * M_PI);

    // Compute the BRDF for this ray (assuming Lambertian reflection)
    float cos_theta = DotProduct(newRay.direction, ray.normalWhereObjWasHit);
    Color BRDF = material.reflectance / M_PI;

    // Recursively trace reflected light sources.
    Color incoming = TracePath(newRay, depth + 1);

    // Apply the Rendering Equation here.
    return emittance + (BRDF * incoming * cos_theta / p);
  }

  void Render(Image finalImage, count numSamples) {
    foreach (pixel in finalImage) {
      foreach (i in numSamples) {
        Ray r = camera.generateRay(pixel);
        pixel.color += TracePath(r, 0);
      }
      pixel.color /= numSamples;  // Average samples.
    }
  }

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

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

• Обстрел лучами (Shooting rays) из источников света и создавать пути в сцене. Путь прерывается случайным числом шагов-отскоков луча. Затем свет направляется на проектируемый пиксель результирующего изображения. Во время этого метода рендеринга миллионы путей создаются и на изображении запоминаются результаты просчета путей, вносящих вклад.
• Сбор лучей (Gathering rays) из точки на поверхности. Луч выстреливается сквозь пиксели изображения и скачет по сцене, пока не встретит на своём пути источник света. Свет из источника света тогда посылается по направлению пикселов изображения. Процесс создания пути называется «семплингом». Одна точка поверхности обычно получает от 800 семплов (до 3 тысяч). Финальная картинка переводится с помощью арифметических действий, не простым суммированием семплов.

Двунаправленная трассировка лучей комбинирует Shooting и Gathering в одном алгоритме и это даёт более быструю сходимость изображению (быстрее и меньше шума). Эти 2 метода генерации путей трассируются независимо и потом начало выстрелянного пути (shooting path) соединяется с хвостом пути сбора лучей (gathering path). Учитывается затухание света при каждом отскоке луча и запоминается в пикселях изображения. Эта техника кажется на первый взгляд парадоксально медленной, но это из-за того, что считается сразу 2 пути. На практике же — наоборот, дополнительная скорость сходимости изображения компенсирует замедления, возникающие из-за необходимости выпускать новые и новые лучи.

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

Вич и Гуибас дали более точное описание двунаправленной трассировке пути^[3]:

Эти методы генерируют два подпути: один — начиная от источника света, а второй — от объектива виртуальной камеры. Потом они <методы> рассматривают все пути, которые получены путём соединения каждого префикса одного подпути с каждым суффиксом другого подпути. Это ведёт к семейству различных важных методик выборки, которые затем комбинируются для минимизации расхождений.

Оригинальный текст (англ.)

These methods generate one subpath starting at a light source and another starting at the lens, then they consider all the paths obtained by joining every prefix of one subpath to every suffix of the other. This leads to a family of different importance sampling techniques for paths, which are then combined to minimize variance.

Трассировщик пути постоянно производит выборку (англ. sampling — семплинг) пикселей изображения. Изображение становится различаемым только тогда, когда проведено несколько выборок на один пиксель, вплоть до 100 выборок на пиксель. Как правило, для обычных изображений и для уменьшения цифрового шума до приемлемого уровня делают около 5000 выборок. Однако для патологических^[англ.] случаев количество выборок становится намного больше. Процесс рендеринга может занять часы и дни в зависимости от сложности сцены и производительности аппаратного и программного обеспечения. Современные реализации графических процессоров обещают от 1 до 10 миллионов выборок в секунду, что делает возможным сгенерировать относительно бесшумное изображение приемлемого качества в течение нескольких секунд или минут. Цифровой шум создаёт особую проблему для анимации, создавая, как правило, нежелательный эффект «зернистости» изображения.

Группа методов Metropolis light transport^[англ.] слегка изменяют ранее оттрассированные успешные пути и производит более важные для изображения выборки первыми. Это может привести к снижению шумности изображения и снижению количества выборок.

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

Отражающие способности поверхностей — количество отраженного света, его направление и цвет, — моделируются с использованием двулучевой функции отражательной способности. Эквивалентом перенесённого света (света, прошедшего через объект) является функция двунаправленного поверхностного рассеивания отражения (англ. Bidirectional scattering distribution function). Трассировщик пути может воспользоваться всеми преимуществами сложных, тщательно смоделированных или вычисленных функций распределения, которые определяют внешний вид («материал», «текстура» и «затенённость» в терминах компьютерной графики) объекта.

• This «Introduction to Global Illumination» has some good example images, demonstrating the image noise, caustics and indirect lighting properties of images rendered with path tracing methods. It also discusses possible performance improvements in some detail.
• SmallPt is an educational path tracer by Kevin Beason. It uses 99 lines of C++ (including scene description). This page has a good set of examples of noise resulting from this technique.
• Pat Hanrahan. Monte Carlo Path Tracing (англ.). Стэнфордский университет (21 мая 2002). Дата обращения: 18 июля 2010. Архивировано 2 мая 2012 года.
• Progressive path tracing with V-Ray (англ.). spot3d.com. Дата обращения: 18 июля 2010. Архивировано 2 мая 2012 года.
• Weas. Применение Progressive Path Tracing в модуле VRay  (неопр.). 3DMir.ru. Дата обращения: 18 июля 2010.
• Clanek Tomase Toegela (cyberdime — перевод на русск. язык). Руководство по Yaf-Ray:: Трассировка пути (Path tracing) - PT  (неопр.). blender3d.org.ua (15 сентября 2007). Дата обращения: 18 июля 2010. Архивировано 2 мая 2012 года.