Skip to main content

Основы алгоритма трассировки лучей. Первая часть.

Практическая реализация алгоритма трассировки лучей

В этой статье я расскажу как в несколько нехитрых шагов достичь вот такого результата

желаемый результат
Ням-ням

Суть алгоритма

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

Схема
Схема Алгоритма Трассировки лучей

Фактически, простейшая схема алгоритма такая

foreach $pixel in $image	// Для каждого пикселя на изображении
	$pixel_pos_3d = get_pixel_position($pixel); // Вычислим его положение в трехмерном пространстве
        $pixel = cast_ray ($observer_point,$pixel_pos_3d - $observer_point); // И пустим луч из точки наблюдения в заданном направлении
end // END OF PIXELS FOREACH

Для вычисления положения пикселей в пространстве можно пользоваться разным техниками. Можно считать линейный сдвиг относительно какой то точки, можно угловой (чтобы получать fish-eye изображения)

function cast_ray($start_point, $direction_point) // Описание функции cast_ray
	foreach $object in $scene_object // Для каждого объекта в сцене
		if ray_intersects_object($object,$start_point,$direction_point); // Определить, пересекается ли луч с объектом
			return 1; // Вернуть 1, если объект пересекается с лучем, продолжить поиск иначе
		end // END OF INTERSECTION
	end // END OF OBJECT FOREACH
	return 0; // Вернуть 0, если пересеченных объектов нет
end // END OF CAST_RAY

С помощью такой простой функции мы получим черно-белую картинку ( массив из 0 и 1), на которой 1 будет соответствовать объекту в данной точке изображения, а 0 — его отсутствию.

Функция определения пересечения зависит от объекта, и реализуется персонально для каждого объекта (класса объектов).
Например она могла выглядеть так:

function ray_intersects_object($object,$start_point,$direction_point); // Функция определения пересечения объекта с лучом
	switch ($object.type) // В зависимости от объекта
		case SPHERE: // Если это, например, сфера
			// { ||z|| = R // Уравенение сферы
			// { z = r.p + t*r.d // уравнение луча в параметрическом виде, где r.p - точка старта, r.d - направление (или вектор скорости), t - параметр расстояния (или время до точки z )
			// Подставим второе уравнение в первое и вспомним, что евклидова норма ||z|| = sqrt(z,z)
			// Таким образом получаем, уравнение следующего вида (преобразования опускаю)
			// a*t**2 + b*t + c = 0 , описание констант ниже
			$ray = ($start_point,$direction_point); // представим луч, как точку исхода и вектор направления (point и direction соответственно)
			$ray.point = $ray.point - $object.position; // перенесем центр координат в центр сферы
			$a = $ray.direction*$ray.direction, // Здесь и далее операция * над векторами - скалярное произведение
			$b = $ray.point*$ray.direction,
			$c = $ray.point*$ray.point - 1,
			$D = $b*$b - $a*$c; // Дискриминант
			if ( $D < zeroThreshold ) return FALSE; // Если меньше некоторого эпсилон (никогда не сравнивайте даблы на чистый ноль!), то не пересекается
			$qD = qSqrt($D), // Иначе вычислим точки пересечения по всем известной формуле корней
			$t1 = ( -$b + $qD)/($a), // Больший корень
			$t2 = ( -$b - $qD)/($a); // Меньший корень
			if ($t1 <= zeroThreshold) // Если больший корень отрицательный, то мы пересекаем сферу в противоположном направлении луча
			return FALSE; // То есть не пересекаем
			$t = ($t2 > zeroThreshold) ? $t2 : $t1; // Если да, то точка пересечения это больший корень, если меньший за точкой старта (мы "внутри сферы"), иначе меньший корень. Точка пересечения пригодится дальше.
			return TRUE;
		end // END OF SPHERE
	end // END OF SWITCH BY OBJECT TYPE
	return FALSE; // Вернем ложь, если типа объекта не известен.
end // END OF INTERSECTION

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

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

Пример черно-белого рейтрейсинга
Черно-белый мир

Фактически, самый простой трассировщик лучей готов. Он умеет отрисовывать белые сферы :). Но нам же нужно сделать еще и красиво!

Освещение

Фоновое освещение

Это просто некоторый цвет, который есть у объекта вне зависимости от того, освещен он или нет.
Фактически, цвет, равный 1 — это было фоновое освещение шара в предыдущем примере

$result_color = $object.ambient_color;

Простое освещение

Освещение представляет собой в простейшем случае набор точечных источников белого света заданной интенсивности. Элементарная модель освещения определяет, освещена ли рассматриваемая точка источником света или нет. Более сложные модели освещения будут рассмотрены далее.

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

function cast_ray($ray) // Описание функции cast_ray
	$min_distance = MAX_FLOAT; // Некоторое значение для первого сравнения
	$id = -1; // Идентификатор ближнего объекта
	foreach $object in $scene_object // Для каждого объекта в сцене
		($has_int, $distance) = ray_intersects_object($object,$ray); // Определить, пересекается ли луч с объектом
		if $has_int && $distance < $min_distance // Если новый объект пересечен и ближе уже найденного
			$min_distance = $distance; // Запомним новое расстояние
			$id = $object; // и этот объект
		end // END IF HAS_INTERSECTION
	end // END OF OBJECT FOREACH
	$result_color = 0;
	if $id != -1 // Если нашли объект
		$result_color += $id.ambient_color;
		$int_point = $ray.point + t*$ray.direction; // Вычислим точку пересечения
		foreach $light in $light_list // Для каждого источника света
			$direction = $light.position - $int_point; // Вычислим направление на этот источник
			$shadowed = false; // Сначала точка не в тени
			foreach $object in $scene_object // Для каждого объекта в сцене
				($has_int, $distance) = ray_intersects_object($object,$ray); // Определить, пересекается ли луч на источник света с объектом (в тени ли точка)	
				if $has_int // Если да
					$shadowed = true; // Объект в тени
					break; // Дальше можно не искать
				end // END IF HAS INTERSECTION
			end // END OF OBJECTS FOREACH
			if ! $shadowed // Если точка не в тени
				$result_color += $id.diffuse_color*$light.intensity; // То добавим к цвету интенсивность света ****
			end // END IF NOT SHADOWED
		end // END OF LIGHTS FOREACH
	end // END OF OBJECT FOUND
	return $result_color; // Вернуть результирующий цвет
end // END OF CAST_RAY

**** В этом месте можно реализовать всякие плюшки, типа зависимости интенсивности света от расстояния до источника

Таким образом, разместив в сцене 5 источников света с интенсивностями 0.2, можно получить картинку в оттенках серого с 6 цветами.

Пример визуализации в оттенках серого
Мир в оттенках серого

Модель Ламберта

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

Сначала нам понадобится функция расчета нормали сферы в точке на ее поверхности. Это очень простая задача ( проще только для плоскости ), так как нормаль в данной точке — это просто нормализованный вектор от центра до точки ( в учебных целях, мы считаем, что в этом случаем мы никогда не рассчитываем нормаль в центре сферы).
Напишем функцию получения нормалей объекта:

funciton get_object_normal ( $object, $point) // Функция получения номрали объекта $object в точке $point
	switch ($object.type) 
		case SPHERE: //  Если это сфера
			return vector_normalize($point - $object.position); // Вернем нормализованный вектор от центра до точки
		end // END OF SPHERE
	end // END OF SWITCH BY OBJECT TYPE
end // END OF GET OBJECT NORMAL

Дальше, интенсивность модели Ламберта записывается, как скалярное произведение вектора нормали на нормализованный вектор из точки до источника света. Если скалярное произведение меньше нуля, то объект самозатенен (ну и он должен был отлететь еще на этапе поиска источника) поэтому интенсивность падающего света в этой точке равно 0
Формула для вычисления модели Ламберта: I_l = I_0 * max(0,( L , N )), где I_0 — Интенсивность источника, ( L, N) — скалярное произведение векторов направления на источник света и нормали.

Для этого поменяем всего одну строчку в предыдущем алгоритме обработки луча

if ! $shadowed // Если точка не в тени
// ---	$result_color += $id.diffuse_color*$light.intensity; // То добавим к цвету интенсивность света ****
// +++
	$result_color += $id.diffuse_color*$light.intensity*max(0,(vector_normalize($direction)*get_object_normal($id,$int_point))); // Вычислим модель Ламберта
end // END IF NOT SHADOWED
Пример визуализации модели Ламберта
Мир в модели Ламберта ( 3 источника )

Модель Wrap-Around

Небольшая модификация модели Ламберта, позволяющая источнику освещать объект немного за границей основной тени
Формула для вычисления модели Ламберт Wrap-Around : I_w = I_0 * max(0,( L , N ) + f)/( 1 + f ), где f — параметр, определяющий, насколько источник света может заглядывать за границу. f=0 — это стандартная модель Ламберта. f=1 — источник может освещать весь объект.

Модель Фонга

Модель Фонга — одна из самых распространенных моделей в трехмерной графике, хотя существуют и более точные модели освещения. Эта модель позволяет отображать блики на объектах, и она зависит от положения наблюдателя.

Эта модель рассчитывает, насколько хорошо наблюдатель видит источник света в отражении объекта. Для этого луч, падающий от источника света на рассматриваемую точку, отражается относительно касательно поверхности к этой точке. Далее вычисляется скалярное произведение отраженного луча и луча, ведущего от рассматриваемой точки до наблюдателя. Итоговая формула:

I_p = I_0 * ( max (0, L_m , V ) )^s Где L_m — отраженный вектор, V — вектор на наблюдателя, s — параметр материала для данного объекта, определяет скорость затухания блика, при удалении от пика.

if ! $shadowed // Если точка не в тени
		$surfaceNormal = get_object_normal($id,$int_point);
		$ld = (vector_normalize($direction);
		$result_color += $id.diffuse_color*$light.intensity*max(0,(vector_normalize($direction)*surfaceNormal)); // Модель Ламберта 
		$L_m = vector_normalize(2*$surfaceNormal*($ld*$surfaceNormal) - $ld); // Вычислим отраженный вектор по правилу треугольника $Ld + $L_m = 2*(L_d,N)*N
		result_color +=	$id.specualr_color * $light.intensity * max ( 0 , L_m * ( -$direction) ) ^ $object.shininess;
end // END IF NOT SHADOWED

Пример визуализации модели Фонга
Модель Фонга (shininess =1 )

Пример визуализации модели Фонга
Модель Фонга (shininess =10 )

Пример визуализации модели Фонга
Модель Фонга (shininess =50 )

Другие модели освещения

Другие модели освещения можно посмотреть у гугла, вики или, например, здесь. Их я оставляю на самостоятельное изучение.

Читать дальше (вторая часть)