Знаете ли вы что такое рейтрейсер? Это программа которая рисует трёхмерную сцену на экране так, как её бы увидели вы. Конечно, не совсем так, но некоторые рейтрейсеры умеют рисовать очень правдоподобные картинки, например как в "Аватаре".
Идея рейтрейсера очень простая и в этой статье я раcскажу как устроен этот алгоритм и даже напишу его на JavaScript. Картинки и пример прилагаются.
Как рисуют трёхмерные сцены?
Сегодня, насколько мне известно, есть два метода проектирования трёхмерных сцен на плоский экран. Первый метод основан на матричных преобразованиях. Его идея также простая, он работает быстро, но то что он рисует не похоже на фотографию и годится лишь для игр. Второй метод это рейтрейсинг. Он просто устроен, он легко позволяет изобразить тени, отражения, рефракцию и другие световые эффекты, но он работает очень медленно и потому для игр не годится. Кроме того, алгоритм рейтрейсинга легко распараллеливается: сколько есть процессоров, ровно во столько раз и будет ускорение.
Идея алгоритма
Представьте, что монитор за которым вы сидите это окно, а за окном какая то сцена. Цвет каждого пикселя на мониторе это цвет луча который выходит из глаза, проходит через этот пиксель и сталкивается со сценой. Чтобы узнать цвет каждого пикселя, нужно через каждый пиксель запустить луч и узнать где этот луч сталкивается со сценой. Отсюда название алгоритма: ray-tracing — трассировка лучей.
Получается, что достаточно написать функцию которая по координатам луча — двум точкам в пространстве — вычисляет цвет поверхности куда этот луч попадает. Какие ситуации надо рассмотреть? Их по крайней мере три:
- Обычная поверхность. Когда луч сталкивается с такой, то можно сказать, что цвет луча это цвет этой поверхности. Это самый простой случай.
- Отражение. Луч может попасть в зеркало и отразиться под тем же углом. Чтобы обработать такую ситуацию, надо уметь отражать луч.
- Преломление. Луч может перейти через гранизу двух сред, например из воздуха в воду. При переходе из одной среды в другую, луч преломится. Это явление называют рефракцией.
Каждая из этих ситуаций легко обрабатывается, поэтому написать рейстрейсер не сложно.
Сцена
На сцене есть два вида объектов: предметы которые нужно нарисовать на экране и источники света. Для простоты будут только шары, кубы (параллелепипеды) и точечные источники света которые равномерно светят во всех направлениях вокруг себя. Любой предмет должен уметь три вещи или, говоря другими словами, иметь три метода:
- norm(p) находит нормаль к поверхности предмета в точке p. Нормаль направлена наружу и имеет длину 1.
- color(p) говорит какой цвет на поверхности предмета в точке p.
- 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) ) }
Сначала функция находит точку столкновения луча с ближайшим предметом и вычисляет нормаль к поверхности в этой точке (если такой точки не нашлось, то луч прошёл мимо всех предметов и можно вернуть цвет фона, скажем чёрный). В точке столкновения цвет суммируется из трёх частей:
- diffuse — цвет самой поверхности с учётом углов под которыми эту точку освещают источники света и угла под которым луч r упал на неё.
- reflection — цвет отражённого луча.
- 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.
Вот что получается если применить только эту модель освещения:
Модель Фонга
Модель Фонга (Phong) как и модель Ламберта описывает освещение точки. В отличие от модели Ламберта, эта модель учитывает под каким углом мы смотрим на поверхность. Освещённость по Фонгу вычисляется так:
- Проводим луч от источника света до рассматриваемой точки на поверхности и отражаем этот луч от поверхности.
- Находим косинус угла между отражённым лучом и направлением по которому мы смотрим на поверхность.
- Возводим этот косинус в некоторую степень и умножаем полученное число на силу источника света.
Согласно этой модели, видимая освещённость точки на поверхности будет максимальной если мы в этой поверхности видим отражение источника света, т.е. он отражается прямо в глаза. Соответсвующий код 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)
}
Вот так это выглядит:
Видно, что одного Фонга мало для хорошего освещения, но если взять освещение по Фонгу с одним весовым коэффициентом и добавить к нему освещение по Ламберту с другим весовым коэффициентом, то получится вот такая картинка:
Код соответствующей функции 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))
}
Теперь у каждого предмета должен быть коэффициент отражения — он показывает какая доля энергии луча отражается от поверхности. После написания этой функции получается такая картинка:
Преломление
Когда луч света переходит из одной среды в другую, он преломляется. Об этом можно почитать в википедии. Реализация преломления почти такая же как и отражения:
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))
}
Теперь у каждого предмета есть коэффициент прозрачности — доля света которую он пропускает через поверхность, и коэффициент преломления — число участвующее в вычислении направления преломлённого луча.
Коэффициент Френеля
Количество отражённого света зависит от угла под которым луч падает на поверхность и коэффициента преломления. Формулу можно посмотреть в википедии. Я не стал учитывать этот эффект в рейтрейсере, потому что он вносил незаметные изменения.
Сглаживание
Если через каждый пиксель запускать один луч, то линии гладкие в трёхмерном пространстве окажутся ступенчатыми на экране после проектирования. Чтобы этого избежать, можно через каждый пиксель запускать несколько лучей, считать для каждого цвет и находить среднее между ними.
Пример
Здесь картинка 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 года.
Чего нет в этом рейтрейсере?
Я рассмотрел базовые возможности рейстрейсера. Что если предмет стоит перед зеркалом и вы светите в зеркало? Задняя сторона предмета будет освещена отражённым светом. Что если посветить на стеклянный шар? Он соберёт лучи света как линза и на подставке под ним будет светлая точка. Что если в комнате есть только маленькое окошко через которое попадает свет? Вся комната будет слабо, но освещена. Ничего из этого рассмотренный рейтрейсер не умеет, однако это несложно дописать, потому что основная идея рейтрейсера позволяет это сделать.
Можно заметить, что для вычисления всех функций — освещение по Ламберту, по Фонгу, отражение и преломление — требуют лишь умения складывать векторы, умножать их на число и находить скалярное произведение. Эти операции над векторами не зависят от размерности пространства и значит можно написать рейтрейсер четырёхмерного пространства, внеся некоторые изменения код.