Представление фотона

Фотон, по версии Йенсена, представляет собой следующую структуру:

	struct Photon {
		float pos[3];               // положение в пространстве
		short plane;                // разделяющая плоскость (в kd-дереве)
		unsigned char theta, phi;   // направление
		float power[3];             // энергия
	} Photon;

	phi = 256 * atan(dy, dx) / (2*PI);
	theta = 256 * acos(dx) / PI;
			

Построение фотонной карты

После того, как трассировка фотонов завершена и сформирован массив (список) из сохранённых фотонов, производится построение фотонной карты в виде некоторой структуры пространственного разбиения. Этот этап вспомогательный и служит для того, чтобы на следующем шаге в произвольной точке пространства можно было быстро найти k ближайших фотонов.

Хенрик Ванн Йенсен, автор метода фотонных карт, рекомендует для хранения фотонной карты использовать структуру данных под названием kd-tree [4] (дословно, «k-мерное дерево»). k-мерное дерево можно себе представить как бинарное дерево, разбивающее пространство размерности k плоскостями, параллельными осям координат. Детали построения, балансировки и поиска в kd-деревьях описаны в соответствующем разделе книги Хенрика. В нашем случае, когда мы будем говорить «kd-tree» или «kd-дерево», иметься в виду будет, соответственно «3d-tree» и «3d-дерево».

Рисунок 3. Наглядное представление структуры 3d-tree.

Поиск k ближайших фотонов

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

Первый – динамически определять радиус сбора (как расстояние до самого дальнего из k ближайших фотонов, см. рис. 3). Шум в этом случае распределён по всему изображению равномерно, т.к. там, где фотонов мало, радиус сбора большой, а там, где много – маленький.

Рисунок 4 (с сайта www.ray-tracing.ru). Сбор k ближайших фотонов с динамически выбираемым радиусом сферы.

Второй путь – использовать константный радиус. В этом случае освещение собирается с k фотонов, попавших в этот радиус. Этот способ менее предпочтителен, т.к. он даёт большой шум.