Предисловие (Abstract)
В компьютерной графике реального времени часто объекты изображаются без теней, что приводит к тому, что объект как бы не закреплён в окружающей его обстановке. Тень несёт очень много информации — фактически, она представляет объект с другой точки зрения и закрепляет его в сцене. Данная статья ставит своей целью рассмотреть наиболее распространённые сейчас алгоритмы построения теней в реальном времени (далее просто построения теней). Здесь не будут рассмотрены алгоритмы построения псевдо-теней, не имеющих ничего общего с объектом, её отбрасывающим, в связи с простотой и бесперспективностью этого направления.
Вступление (Introduction)
В отличие от локального освещения, тени являются одним из эффектов глобального освещения. Для их построения необходимо учитывать не столько свойства материала и ориентацию одного треугольника, сколько взаимное расположение всех треугольников в сцене. Современные графические укорители работают на уровне не выше треугольников и ничего не знают о наличие сцены, поэтому тени не поддерживаются ими напрямую и вся подготовительная работа ложится на плечи программиста. Но, тем не менее, в наиболее распространённых алгоритмах практически все стадии построения тени реализуются именно через графический ускоритель.
Тени бывают чёткие (hard shadows) и мягкие (soft shadows). Чёткие тени получаются, когда имеется точечный источник или источник направленного параллельного света. В этом случае, согласно геометрической оптике Френеля, тень получается, как показано на рис.1.1:
Я не буду вдаваться в волновую оптику для объяснения возникновения мягких теней, а ограничусь только протяжёнными источниками света. Согласно всё той же геометрической оптике Френеля, в случае наличия протяжённого источника света, от объекта получается не одна тень, а целая серия теней, которые накладываются друг на друга и образуют более или менее затемнённые области, как показано на рис. 1.2, которые и составляют основную тень (umbra) и область полутени (penumbra).
Все существующие алгоритмы построения теней позволяют строить чёткие тени, но некоторые из них позволяют размыть полученную тень, создавая как бы псевдо-мягкую тень.
Существует несколько основных подходов к построению теней, которые мы рассмотрим в этой статье:
- Преобразование модели "на землю" и отрисовка её как тени.
- Построение теневой маски объекта и проективное наложение её на другие объекты.
- Теневые объёмы.
- Использование информации о глубине (depth buffer).
Т.к. основным местом использования алгоритмов теней в реальном времени являются компьютерные игры, то в дальнейшем, для удобства, я буду приводить примеры именно на них.
Преобразование "на землю"
Фактически, это первый алгоритм построения тени, который был применён в играх. (Turok II, Shogo, etc.). Он отличается простотой реализации и хорошим качеством получаемой тени. Этот алгоритм был впервые описан Джимом Блинном [BLIN88]. В своей статье он описал уравнения для проектирования полигона "на землю", т.е. на плоскость z=0, в направлении от источника света. Он рассмотрел два случая:
- Источник на бесконечности (параллельный направленный свет)
- Локальный источник (точечный источник недалеко от объекта)
Этот метод использует геометрическое взаимоотношение источника света и полигона, т.е. подобные треугольники, для вычисления проекции каждого полигона модели "на землю". "Теневые полигоны" должны быть рассчитаны для каждого источника света, т.е. если объект освещается N источниками света, то необходимо рассчитать N его "теневых проекций".
Источник на бесконечности
В случае бесконечно удалённого источника света мы предполагаем, что лучи света, приходящие к объекту, полностью параллельны. Это позволит нам решить уравнение проекции только раз и применять полученное решение ко всем вершинам объекта.
Общая постановка задачи:
Имея точку источника света 
и вершину объекта 
, мы хотим получить проекцию вершины объекта на плоскость z=0, т.е. точку тени 
Из подобных треугольников получаем: 
решая это уравнение относительно 
, получаем:
если принять, что L это вектор из точки P к источнику света, то точку S можно выразить как
т.к. мы производим проекцию на плоскость z=0, то уравнение (2.3) можно переписать в следующем виде:
решая (2.3) относительно 
, получаем
Теперь имея координаты точки P в мировом координатном пространстве, можно получить её проекцию на плоскость z=0 просто путём умножения на матрицу 
Локальный источник
Уравнение (2.6) для бесконечно удалённого источника света может быть обобщено для случая, когда источник света находится на конечном расстоянии от объекта. В этом случае нам понадобятся дополнительные вычисления на каждую вершину, т.к. каждая вершина имеет, в общем случае, своё собственное направление на источник света. Тем не менее, в этом случае мы тоже можем перенести большую часть вычислений в матрицу
Если L это точка расположения источника света, то (2.3) принимает вид:
и снова нам необходимо произвести проекцию на плоскость z=0, т.ч.
Если использовать гомогенизацию после преобразования, то (2.11) можно записать в виде матрицы
Опять, имея координаты точки P в мировом координатном пространстве, можно записать:
после чего провести гомогенизацию точки 
для получения проекции точки P на плоскость z=0.
Построение теневой маски и проективное наложение
Этот метод является логическим продолжение предыдущего, но, в отличие от него, обладает целым рядом преимуществ.
Объект, который отбрасывает тень (shadow caster) тем или иным способом рисуется с точки зрения источника света чёрным цветом в белую текстуру. Размер текстуры зависит от того, насколько мелкие элементы объекта мы хотим видеть в тени (например, в игре Drakan: Order of the flame "теневая" текстура была размером примерно 32х32 пиксела).
Представьте себе плоскость, перпендикулярную направлению на источник света и расположенную сразу за объектом по лучу света — это и есть текстура, в которую производится отрисовка объекта. Для того, чтобы получить проекцию объекта на эту текстуру, применим элементы стандартного конвейера трансформации. Предположим, что текстура, в которую нам необходимо нарисовать объект, это экран. Тогда последовательность преобразований становится просто очевидной (стандартный конвейер преобразования): пространство объекта => мировое пространство => пространство камеры (у нас это источник света) => проективное пространство => нормализованное проективное пространство => экранное пространство.
Для наших целей необходимо модифицировать матрицы переходов в пространство камеры, проективное пространство и в экранное пространство.
Пространство камеры
Практически, это обыкновенная матрица камеры, но только расположена эта виртуальная камера в точке нахождения источника света и направлена на shadow caster. В случае бесконечно удалённого источника света виртуальная камера может располагаться в любой точке на прямой между shadow caster и источником света (обычно её выбирают близко к shadow caster).
Проективное пространство
Эта матрица существенно зависит от того, является ли источник света локальным или бесконечно удалённым. Для бесконечно удалённого источника света это матрица ортографического преобразования:
где width, height и depth это ширина, высота и глубина проективного объёма. В этом случае (ортографическое преобразование) не требуется гомогенизация.
Для локального источника света необходима матрица перспективного преобразования:
где 
— угол зрения, aspect — отношение ширины к высоте экрана (при отрисовке в квадратную текстуру aspect=1), far и near — дальняя и ближняя стенки проективного объёма соответственно. После перспективного преобразования необходима гомогенизация, как и в случае локального источника при преобразовании "на землю".
Для качественной картинки рекомендуется выбирать проективный объём таким образом, чтобы он максимально плотно охватывал shadow caster и не оставлял зазоров.
Экранное пространство
Здесь всё просто — модель из нормализованного проективного пространства должна лечь в квадратную текстуру с минимальными зазорами.
После того, как shadow caster нарисован в текстуру, необходимо эту текстуру наложить на затенённые объекты (shadow receiver). Для этого можно воспользоваться технологией проективного наложения текстур, которая легко реализуется на современном железе. Для избежания повторения теневой текстуры необходимо выставить clamp или border color для режима "обёртки" текстуры.
В результате мы получаем тень от одного объекта (shadow caster) на другом (shadow receiver). Что ещё хочется сделать с этой тенью:
- Размыть её (получить псевдо-мягкую тень). Для этого необходимо размыть теневую текстуру. Сделать это можно несколькими способами:
- "Вручную" путём наложения какого-нибудь blur-фильтра. Такой подход удобен при программной отрисовке самой теневой текстуры.
- Использовать железо. Можно отрисовать текстуру саму в себя со смещением, либо сгенерировать mip-level.
- Уводить тень в прозрачность на основе расстояния до источника света. К сожалению, реализовать это без vertex shader при помощи железа невозможно. Единственное, что можно здесь сделать для улучшения вида тени, так это сделать её не угольно чёрной, а равномерно полупрозрачной.
- Минимизировать затраты на отрисовку тени. Это достигается при использовании какой-либо технологии LOD — просто выбирается оптимально-минимальный уровень у shadow caster и вся теневая текстура рисуется именно с этим уровнем.
Теневые объёмы
При освещении сцены в тени оказываются те объекты, которые попадают внутрь т.н. теневого объёма. Теневой объём — это представление пространства за объектом, из которого не наблюдается источник света, в виде полигонального объекта (см. рис. 4.1). Впервые этот алгоритм был описан в [Crow77]. 
Для того, чтобы точка была затенена, луч света должен войти в теневые объёмы большее число раз, нежели выйти из них, т.е. остаться внутри хотя бы одного теневого объёма. Для упрощения нашей задачи можно принять, что не луч света от источника должен проделать этот путь, а луч от наблюдателя. При таком упрощении возникает несколько неприятных случаев, которые мы рассмотрим отдельно.
Алгоритм можно разделить на два явных действия: построение "теневой маски" (т.е. маски освещённых и затенённых областей 2-х мерной картинки) и отрисовка сцены с использованием теневой маски. Предлагается реализация, которую можно разбить на три стадии
Первая стадия
На этой стадии мы просто рисуем всю сцену таким образом, как будто она вся затенена. Все последующие стадии служат цели добавления освещения в картинку. Участки картинки, которые так и не будут освещены в последующих проходах, останутся затенёнными.
Вторая стадия
На этой стадии мы должны построить теневую маску, используя информацию о 3-х мерных теневых объёмах. Для создания и хранения теневой маски нам понадобится буфер шаблонов (stencil buffer).
Построение оптимальных теневых объёмов является само по себе достаточно сложной задачей, которая выходит за рамки данного обзора. Описание одного из алгоритмов построения силуэта, который необходим для построения оптимального теневого объёма, можно найти, например, в [SAND00]. Здесь для описания работы метода мы воспользуемся простым способом создания теневого объёма от каждого треугольника в модели.
Итак, нам необходимо подсчитать для каждой точки разность того, сколько раз луч от наблюдателя пересёк положительно ориентированные полигоны теневого объёма и отрицательно ориентированные. Это производится за два прохода. На первом проходе мы рисуем все теневые объёмы (мы не записываем точку ни в цветовой буфер, ни в буфер глубины) с нормальным (для нашего приложения) отбрасыванием треугольников (back face culling). Каждая точка, которая проходит тест по глубине, увеличивает значение в буфере шаблонов на 1. На втором проходе меняем back face culling на противоположный — рисоваться будут задние стенки теневых объёмов. Теперь каждая точка, которая проходит тест по глубине, будет уменьшать значение в буфере шаблонов на 1. В итоге после этих двух проходов мы имеем в буфере шаблонов нулевые значения для освещённых областей и значения больше нуля для затенённых.
Третья стадия
На этой стадии у нас уже проведены все предварительные приготовления — есть и затенённая сцена и теневая маска. Остаётся последний штрих — отрисовать ещё раз всю сцену освещённой, используя проверку по буферу шаблонов. Не забудьте вернуть режим back face culling в нормальный :-).
Вторую и третью стадии следует повторять для каждого источника света, но при этом следует очищать только буфер шаблонов перед второй стадией. Ни цветовой буфер, ни буфер глубины на этих стадиях мы не очищаем.
Чтобы этот алгоритм можно было использовать, необходимо решить ещё несколько вопросов. Например, если наблюдатель уже находится внутри теневого объёма, то необходимо инвертировать результат теневой маски. Если теневой объём пересекает ближнюю плоскость отсечения проективного объёма, то часть теневой маски необходимо инвертировать, а часть — нет. Также, есть очень неприятный эффект, который возникает из-за совпадения передней стенки теневого объёма с реальным объектом, его отбрасывающим. В этом случае, из-за конечной точности представления глубины, часть пикселей на передней стенке теневого объёма будет затенена, а часть — нет…
Все эти проблемы имеют решения, но их рассмотрение выходит за рамки данного обзора.
Использование информации о глубине
Пожалуй, идея этого метода является наиболее простой из всех, описанных в этой статье. Этот метод базируется на идее о том, что затенённые точки — это те, которые "спрятаны" от источника света. Другими словами, это "hidden surfaces" с точки зрения источника света. 
Для того, чтобы определить невидимые поверхности с точки зрения источника света, необходимо отрисовать всю сцену с точки зрения источника света в буфер глубины. После этого в буфере глубины мы будем иметь глубину "ближайших" к источнику света точек. Сохраним буфер глубины для дальнейшего использования. Теперь необходимо отрисовать всю сцену с точки зрения наблюдателя, проделывая следующую проверку: если глубина точки, переведённая в систему координат источника света, больше значения, которое мы сохранили из буфера глубины на предыдущей стадии, значит, точка затенена. В противном случае точка освещена.
Но это только идея. Если железо не поддерживает специфических функций (сохранение и доступа к буферу глубины, сравнение глубины с сохранённым значением, и т.д.), то реализовать его "в лоб" практически невозможно. Но т.к. метод очень привлекательный, то было разработано множество способов того, как "обмануть проклятую железку". Мы рассмотрим здесь один из них (один из наиболее удачных).
Итак, предполагаем, что имеющееся железо не даёт доступа к буферу глубины, у него нет никаких возможностей сравнивать значения, кроме сравнения по альфа-каналу. Единственное, что требуется от железа, так это возможность смены цветового буфера для текущей отрисовки (render target) и 2-х текстурный растеризатор.
На рис. 5.2. изображена сцена с точки зрения источников света (не образ глубины), а на рис. 5.3. — сцена с точки зрения наблюдателя с построенными тенями.
Как и в предыдущем методе, алгоритм можно разделить на два явных действия: построение теневой маски и отрисовка сцены с использованием теневой маски. Предлагается реализация, которую можно разбить на три стадии:
Первая стадия
На этой стадии мы получим образ глубины сцены с точки зрения источника света. Для этого мы отрисуем сцену в текстуру (как в другой render target). Для получения глубины мы воспользуемся текстурой 256х1х32, в которой значения размещены от 0 до 255 в альфа-канале (цветовые значения нас не интересуют). Чтобы текстура легла необходимым для нас образом, сгенерим текстурные координаты как позиция в пространстве камеры с последующей трансформацией
После такой отрисовки, в текстуре мы имеем образ глубины сцены с дискретом в 1/256.
Вторая стадия
Здесь мы создадим теневую маску, базируясь на сравнении глубины. Для этого мы наложим первую текстуру (256х1х32) на объект способом, сходным с первой стадией, и наложим вторую текстуру, полученную на первой стадии, проективным методом. После чего, в каждой точке вычтем значения альфа-канала первой текстуры из второй и отрисуем в теневую маску с проверкой по альфа-каналу. Точки, которые пройдут эту проверку, запишем в теневую маску как 1, а которые не пройдут оставим в 0.
Для наложения первой текстуры необходимо сгенерировать текстурные координаты как позиция в пространстве камеры с последующей трансформацией:
где 
— это обратная матрица камеры, 
— матрица камеры из первой стадии (матрица камеры от источника света), 
— матрица проективного преобразования от источника света, 
— матрица выбора (5.2). Связка 
просто переводит модель из пространства текущей камеры в пространство камеры источника света.
Проективное наложение второй текстуры осуществляется следующим образом:
которая центрирует сгенерённые текстурные координаты по текстуре (т.к. текстурные координаты сгенерятся в диапазоне [-1;1], а нам необходимо [0;1]).
Матрицы 
и можно заранее объединить в одну матрицу:
После этого остаётся только отрисовать сцену, проставляя значения в буфер шаблонов.
Третья стадия
Имея теневую маску, на этой стадии мы просто отрисовываем сцену по тому же принципу, как и в предыдущем методе.
При построении теней от многих источников света используется подход, аналогичный предыдущему методу.
Если "железо" позволяет накладывать 3 или 4 текстуры за один проход, то построение теневой маски можно совместить с построение карты освещения.
Каким бы хорошим и привлекательным не казался этот метод, он всё же таит в себе несколько неприятностей. Самая главная из них — это ошибочное самозатенение, которое возникает из-за недостаточной точности представления глубины через альфа-канал, как показано на рис. 5.4.
Существует несколько методик "обхода" этой проблемы, но все они страдают прегрешениями, т.ч. оставляю читателям придумать свой подход.
Заключение
Рассмотренные методы представляют собой далеко не полный список того, что было придумано в области построения теней в реальном времени, но, тем не менее, я постарался рассмотреть наиболее популярные и перспективные методы.
Приложение
В качестве дополнительного материала предлагается небольшая статья о проективных текстурах (projective texture).
Литература
- [Crow77] — Franklin C. Crow. Shadow algorithms for computer graphics. In Computer Graphics (SIGGRAPH '77 Proceedings), pages 242-248, July 1977.
- [WILL78] — Williams, L., "Casting Curved Shadows on Curved Surfaces", Computer Graphics, vol. 12, no. 3, pp270-4, 1978.
- [BLIN88] — Blinn, James, "Me and my (fake) shadow", IEEE Computer Graphics and Applications, January 1988.
- [SAND00] — P. Sander, X. Gu, S. Gortler, H. Hoppe, J. Snyder., "Silhouette Clipping", Computer Graphics (SIGGRAPH 2000 Proceedings), pages 327-334
Virtual Warrior