Grabduck

Рейтрейсер на JavaScript

:

TitleImage

Знаете ли вы что такое рейтрейсер? Это программа которая рисует трёхмерную сцену на экране так, как её бы увидели вы. Конечно, не совсем так, но некоторые рейтрейсеры умеют рисовать очень правдоподобные картинки, например как в " Аватаре".

Идея рейтрейсера очень простая и в этой статье я раcскажу как устроен этот алгоритм и даже напишу его на JavaScript. Картинки и пример прилагаются.

Как рисуют трёхмерные сцены?

Сегодня, насколько мне известно, есть два метода проектирования трёхмерных сцен на плоский экран. Первый метод основан на матричных преобразованиях. Его идея также простая, он работает быстро, но то что он рисует не похоже на фотографию и годится лишь для игр. Второй метод это рейтрейсинг. Он просто устроен, он легко позволяет изобразить тени, отражения, рефракцию и другие световые эффекты, но он работает очень медленно и потому для игр не годится. Кроме того, алгоритм рейтрейсинга легко распараллеливается: сколько есть процессоров, ровно во столько раз и будет ускорение.

Идея алгоритма

Представьте, что монитор за которым вы сидите это окно, а за окном какая то сцена. Цвет каждого пикселя на мониторе это цвет луча который выходит из глаза, проходит через этот пиксель и сталкивается со сценой. Чтобы узнать цвет каждого пикселя, нужно через каждый пиксель запустить луч и узнать где этот луч сталкивается со сценой. Отсюда название алгоритма: ray-tracing — трассировка лучей.

Получается, что достаточно написать функцию которая по координатам луча — двум точкам в пространстве — вычисляет цвет поверхности куда этот луч попадает. Какие ситуации надо рассмотреть? Их по крайней мере три:

  1. Обычная поверхность. Когда луч сталкивается с такой, то можно сказать, что цвет луча это цвет этой поверхности. Это самый простой случай.
  2. Отражение. Луч может попасть в зеркало и отразиться под тем же углом. Чтобы обработать такую ситуацию, надо уметь отражать луч.
  3. Преломление. Луч может перейти через гранизу двух сред, например из воздуха в воду. При переходе из одной среды в другую, луч преломится. Это явление называют рефракцией.

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

Сцена

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

  1. norm(p) находит нормаль к поверхности предмета в точке p. Нормаль направлена наружу и имеет длину 1.
  2. color(p) говорит какой цвет на поверхности предмета в точке p.
  3. trace(ray) идёт вдоль луча ray и останавливается там где луч пересекает поверхность предмета. Этот метод возвращает координаты пересечения и расстояние от начала луча до точки пересечения.

Вот так выглядят эти методы у сферы:

sphere.norm = function(at)
{	
	return vec.mul(1 / this.r, vec.sub(at, this.q))
}

sphere.trace = function(ray)
{
	var a = ray.from	
	var aq = vec.sub(a, this.q)
	var ba = ray.dir		
	var aqba = vec.dot(aq, ba)	
	
	if (aqba > 0) return
	
	var aq2 = vec.dot(aq, aq)
	var qd = aq2 - this.r * this.r
	var D = aqba * aqba - qd
	
	if (D < 0) return
		
	var t = qd > 0 ? -aqba - Math.sqrt(D) : -aqba + Math.sqrt(D)	
	
	var sqrdist = t * t
	var at = vec.add(a, vec.mul(t, ba))
	
	return {at:at, sqrdist:sqrdist}
}

sphere.color = function(p)
{
	return [1, 0, 0] // red color
}

Смысл отдельных обозначений, вроде this.q, сейчас не важен: вы легко можете написать свою функцию sphere.trace. Существенно только, что написать эти три метода довольно просто. Аналогично описывается куб.

Рейтрейсер

Теперь перейдём к коду рейтрейсера. У него есть несколько основных функций:

  • trace(ray) идёт вдоль луча ray и останавливается там где луч пересекает какой нибудь предмет. Другими словами, эта функция находит ближайшее пересечение луча с предметом. trace возвращает координаты пересечения и расстояние до него, а также ссылку на предмет с кем пересеклись. Я написал эу функцию так:
    rt.trace = function(ray)
    {
    	var p	
    
    	for (var i in rt.objects)
    	{		
    		var obj = rt.objects[i]
    		var ep = obj.trace(ray)
    		
    		if (ep && (!p || ep.sqrdist < p.sqrdist))
    		{
    			p = ep
    			p.owner = obj
    		}
    	}	
    	
    	return p
    }
    

  • inshadow(p, lightpos) проверяет, находится ли точка p в тени от источника света в точке lightpos. Другими словами, эта функция проверяет светит ли lightpos на p. Вот её код:
    rt.inshadow = function(p, lightpos)
    {
    	var q = rt.trace(rt.ray(lightpos, p))
    	return !q || vec.sqrdist(q.at, p) > math.eps
    }
    

    На первом шаге функция выпускает луч из lightpos в точку p и смотрит где этот луч пересекает предметы. На втором шаге функция проверяет, совпадает ли точка пересечения с точкой p. Если не совпадает, значит луч света не добрался до p.

  • color(ray) выпускает луч ray и смотрит где он столкнётся с предметами. В точке столкновения узнаёт цвет поверхности и возвращает его. Вот её код:
    rt.color = function( r )
    {
    	var hit = rt.trace( r )	
    	
    	if (!hit) 
    		return rt.bgcolor
    	
    	hit.norm = hit.owner.norm(hit.at)
    		
    	var surfcol = rt.diffuse(r, hit) || [0, 0, 0]
    	var reflcol = rt.reflection(r, hit) || [0, 0, 0]
    	var refrcol = rt.refraction(r, hit) || [0, 0, 0]
    	
    	var m = hit.owner.mat // material
    	
    	return vec.sum
    	(
    		vec.mul(m.reflection, reflcol),
    		vec.mul(m.transparency, refrcol),
    		vec.mul(m.surface, surfcol)
    	)	
    }
    

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

    1. diffuse — цвет самой поверхности с учётом углов под которыми эту точку освещают источники света и угла под которым луч r упал на неё.
    2. reflection — цвет отражённого луча.
    3. refraction — цвет преломлённого луча.

    Эти три части суммируются с весовыми коэффициентами: цвет поверхности surfcol имеет вес m.surface, цвет отражённого луча reflcol — m.reflection, цвет преломлённого луча — m.transparency. Сумма весовых коэффициентов равна 1. Например, если прозрачность m.transparency = 0 то нет смысла считать преломление.

Осталось рассмотреть способы вычисления цвета в точке. Есть разные подходы к реализации функций diffuse, reflection и refraction. Я рассмотрю несколько из них.

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

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

rt.diffuse = function(r, hit)
{	
	var obj = hit.owner	
	var m = obj.mat
	var sumlight = 0	
		
	for (var j in rt.lights)
	{
		var light = rt.lights[j]
		
		if (rt.inshadow(hit.at, light.at))
			continue
						
		var dir = vec.norm(vec.sub(hit.at, light.at))				
		var cos = -vec.dot(dir, hit.norm)
		sumlight += light.power * cos
	}	
	
	return vec.mul(sumlight, obj.color)
}

Функция перебирает все источники света и проверяет, не находится ли точка hit в тени. Если она на освещённом участке, то вычисляется вектор dir — направление от источника света light к точке hit. Затем функция находит косинус угла между нормалью hit.norm к поверхности в точке hit и направлением dir. Этот косинус равен скалярному произведению dir•hit.norm. Наконец, функция находит освещённость по Ламберту: light.power•cos.

Вот что получается если применить только эту модель освещения:

LambertModelExample

Модель Фонга

Модель Фонга (Phong) как и модель Ламберта описывает освещение точки. В отличие от модели Ламберта, эта модель учитывает под каким углом мы смотрим на поверхность. Освещённость по Фонгу вычисляется так:

  1. Проводим луч от источника света до рассматриваемой точки на поверхности и отражаем этот луч от поверхности.
  2. Находим косинус угла между отражённым лучом и направлением по которому мы смотрим на поверхность.
  3. Возводим этот косинус в некоторую степень и умножаем полученное число на силу источника света.

Согласно этой модели, видимая освещённость точки на поверхности будет максимальной если мы в этой поверхности видим отражение источника света, т.е. он отражается прямо в глаза. Соответсвующий код diffuse:

rt.diffuse = function(r, hit)
{	
	var obj = hit.owner	
	var m = obj.mat
	var sumlight = 0	
		
	for (var j in rt.lights)
	{
		var light = rt.lights[j]
		
		if (rt.inshadow(hit.at, light.at))
			continue
						
		var dir = vec.norm(vec.sub(hit.at, light.at))
		var lr = vec.reflect(dir, hit.norm)
		var vcos = -vec.dot(lr, r.dir)
		
		if (vcos > 0)
		{			
			var phong = Math.pow(vcos, m.phongpower)
			sumlight += light.power * phong
		}			
	}	
	
	return vec.mul(sumlight, obj.color)
}

Вот так это выглядит:

PhongModelExample

Видно, что одного Фонга мало для хорошего освещения, но если взять освещение по Фонгу с одним весовым коэффициентом и добавить к нему освещение по Ламберту с другим весовым коэффициентом, то получится вот такая картинка:

LambertPlusPhong

Код соответствующей функции diffuse я не привожу: он представляет из себя комбинацию предыдущих двух diffuse и его можно найти в файле rt.js в примере.

Отражение

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

rt.reflection = function(r, hit)
{	
	var refl = hit.owner.mat.reflection

	if (refl * r.power < math.eps)
		return
			
	var q = {}
			
	q.dir = vec.reflect(r.dir, hit.norm)		
	q.from = hit.at
	q.power = refl * r.power	
					
	return rt.color(q)
}

vec.reflect = function(a, n)
{
	var an = vec.dot(a, n)	
	return vec.add(a, vec.mul(-2 * an, n))
}

Теперь у каждого предмета должен быть коэффициент отражения — он показывает какая доля энергии луча отражается от поверхности. После написания этой функции получается такая картинка:

Reflection

Преломление

Когда луч света переходит из одной среды в другую, он преломляется. Об этом можно почитать в википедии. Реализация преломления почти такая же как и отражения:

rt.refraction = function(r, hit)
{
	var m = hit.owner.mat
	var t = m.transparency
	
	if (t * r.power < math.eps)
		return
	
	var dir = vec.refract(r.dir, hit.norm, m.refrcoeff)
	
	if (!dir)
		return
		
	var q = {}

	q.dir = dir
	q.from = hit.at
	q.power = t * r.power	
		
	return rt.color(q)
}

vec.refract = function(v, n, q)
{
	var nv = vec.dot(n, v)
	
	if (nv > 0)	
		return vec.refract(v, vec.mul(-1, n), 1/q)
	
	var a = 1 / q
	var D = 1 - a * a * (1 - nv * nv)	
	var b = nv * a + Math.sqrt(D)	
	
	return D < 0 ? undefined : vec.sub(vec.mul(a, v), vec.mul(b, n))
}

Теперь у каждого предмета есть коэффициент прозрачности — доля света которую он пропускает через поверхность, и коэффициент преломления — число участвующее в вычислении направления преломлённого луча.

Refraction

Коэффициент Френеля

Количество отражённого света зависит от угла под которым луч падает на поверхность и коэффициента преломления. Формулу можно посмотреть в википедии. Я не стал учитывать этот эффект в рейтрейсере, потому что он вносил незаметные изменения.

Сглаживание

Если через каждый пиксель запускать один луч, то линии гладкие в трёхмерном пространстве окажутся ступенчатыми на экране после проектирования. Чтобы этого избежать, можно через каждый пиксель запускать несколько лучей, считать для каждого цвет и находить среднее между ними.

Пример

Здесь картинка 1000×1000 (RPS означает Rays Per Second — число лучей которые успевает просчитать браузер за одну секунду), а здесь другая картинка 800×800. Пример можно скачать по этой ссылке. Я сравнил скорость рендеринга в разных браузерах. Получилось следующее:

Opera 33,000 RPS
Chrome 38,000 RPS
Firefox 16,000 RPS
Explorer 20,000 RPS
Safari 13,000 RPS

Я использовал самые последние версии браузеров на 5-ое февраля 2011 года.

Чего нет в этом рейтрейсере?

Я рассмотрел базовые возможности рейстрейсера. Что если предмет стоит перед зеркалом и вы светите в зеркало? Задняя сторона предмета будет освещена отражённым светом. Что если посветить на стеклянный шар? Он соберёт лучи света как линза и на подставке под ним будет светлая точка. Что если в комнате есть только маленькое окошко через которое попадает свет? Вся комната будет слабо, но освещена. Ничего из этого рассмотренный рейтрейсер не умеет, однако это несложно дописать, потому что основная идея рейтрейсера позволяет это сделать.

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