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

Алгоритм состоит в том, что для каждого пиксела в экране определяется ближайшая грань. Для этого проверяется пересечение проектирующей прямой, проходящей центр пикселя, с гранями всех объектов в сцене и находится ближайшая. Алгоритм достаточно универсален, может работать как с объектами, заданными поверхностями, так и с конструктивной геометрией. Он позволяет эффективно обрабатывать полупрозрачные полигоны. В общем случае, алгоритм требует O(CN) времени, но если применить некоторые оптимизации, вроде иерархии описанных вокруг объектов тел или BSP можно свести время выполнения к O(ClogN), что означает практическую независимость от сложности сцены. Для этого алгоритма можно очень эффективно использовать когерентность, например, если найдено пересечение прямой для текущего пикселя с некоторой гранью, то прямая для соседнего тоже скорее всего пересечется с этой гранью. Значит, можно сначала проверить пересечение с этой гранью, и если оно имеет место, проверять не весь отрезок, а только его часть от наблюдателя до точки этого пересечения. Можно построить иерархию описывающих тел, и проверять пересечение луча сначала с ними, а затем с объектами. Наконец, можно использовать и когерентность по времени, хранить указатели на грани для каждого пиксела, и сначала проверять пересечение с ними, только это требует достаточно много памяти.