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

[k4shik]

Мозг вскипел

[iwuvjhdva]

Да вы чо, это в любом институте на компьютерной графике проходят. Автор крут тем, что сделал трассировку на JavaScript!

[IgorMats]

А также НЕ на JavaSсript это не каждый сделает)

[liveor]

Я уже однажды писал в комментариях к одному посту о том, что наш преподаватель по компьютерной графике в Одесском национальном политехническом университете считает Paint векторным редактором… грустно :(

[AYShestakov]

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

[RostislavDzinko]

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

[AquaXP]

В Safari не работает(

[MYPABEU]

работает (Mac Safari 5)

[Xao]

Айпад не потягал :(

[soulburner]

Следующий по смыслу пост будет «рейтрейстинг на брейнфаке» :)

[dom1n1k]

Строго говоря, это всё же, наверное, ray casting?

[hubhito]

Ray Casting — это другое. Задача ray casting — найти только первое пересечение луча с объектом. На нем постороены движки DooM и Wolf3D.
ru.wikipedia.org/wiki/Ray_casting

[homm]

Исправьте, пожалуйста, синтаксические ошибки: ключевое слово new нельзя использовать в качестве имен функций.

[ankh1989]

Почему нельзя? Chrome ведь выполняет код. Я исправил, ради любопытства и запустил в Firefox. Результат тот же: браузер ест много памяти, грузит процессор и ничего не рисует (если очень подождать то нарисует один квадратик). Или что вы хотели добиться заменой new?

[homm]

Есть еще браузеры, Сафари и Опера. Ваш К.О.

[ankh1989]

Вы определённо правы ) Исправил .new на .create

[homm]

В сафари получилось что-то совсем страшное, что-то не так с геометрией. А в Опере почти все хорошо, но вылез один глюк — не глюк, особенность — не особенность.
Когда вы помещаете imgdata на канву с помошью putImageData (это функция renderarea), у вас в imgdata должны быть значения от 0 до 255. Из-за погрешностей алгоритма у вас там иногда оказываются значения -1 и 256. Опера для этих значений делает «переполнение», Хром и Фаерфокс их обрезают. Решение простое — нужно обрезать значения вручную:

imgdata[base + 0] = color[0] < 0 ? 0 : (color[0] > 255 ? 255 : color[0])
imgdata[base + 1] = color[1] < 0 ? 0 : (color[1] > 255 ? 255 : color[1])
imgdata[base + 2] = color[2] < 0 ? 0 : (color[2] > 255 ? 255 : color[2])

[ankh1989]

Можно картинку из Сафари? Может быть я догадаюсь где ошибка по ней.

Я думал, что image.data округляет значения по определению, а оказывается это фича Хрома. Надо мне документацию почитать по HTML5 )

А вообще замечание правильное: отрицательное значение цвета говорит об ошибке в вычислении коэффициента Ламберта (его нужно как коэффициента Фонга урезать снизу нулём). Имхо, значения цвета нужно не только урезать сверху до 255, но и в конце балансировать яркость: делить оригинальные цвета на максимум, чтобы не было засвеченных областей. Это также спасёт и от чрезмерно тёмных картинок: они станут ярче.

Я исправил код. Можно заново скачать пример.

[homm]

Рендер в сафари.

А в Опере все поломалось. Проблема в файле sphere.js, в первых строчках, где var sp. У вас нет желания почитать про объектную модель js, про прототипы, чтобы привести код в соответствие с идеологией языка?

[ankh1989]

Не догадаюсь :( Что то тут совсем плохо. Хотя говорят, что в Mac Safari 5 работает.

Я тогда оставлю __proto__, он хотя бы работает. Почитаю как нибудь про объектную модель. Вы случайно имеете ввиду не такой код?

function sphere(...)
{
  this.radius = ...
  this.color = ...
}

var s = new sphere(...)

[TheShock]

Такой

[TheShock]

function Sphere(...) {
    this.radius = ...
    this.color = ...
    // Конструктор
}
Sphere.prototype = {
    method1: function () {
        // тело первого метода
    },
    method2: function () {
        // тело второго метода
    },
};

var s = new Sphere(...)

[ankh1989]

Поправил. Можно скачать обновление :)

[homm]

Хотя говорят, что в Mac Safari 5 работает.

У меня на Маке и на Виндовс одинаковый результат.

[moooV]

Это просто великолепно! Нет слов.

[dshster]

Осталось реализовать radiosity. На самом деле я думал, что это чудовищно сложный алгоритм, особенно отражения/преломления. Но судя по исходному коду… Сплошная математика.

[ankh1989]

Сделать radiosity совсем несложно: примерно 5-10 строчек кода. Нужно из каждой точки выпустить N (большое число) лучей во все стороны и найти среднее. Но представьте сколько это будет работать на JS… Если бы код был хотя бы на Lua, я бы попробовал, а на JS не рискну )

[SleepingLion]

Прекрасно работает в firefox 4b10, только результат немного отличается от примера.

[TheShock]

Потому что одного луча на пиксель — недостаточно =(

[ankh1989]

Точно )

[galaxy]

Поставьте побольше Rays per pixel для сглаживания. А вообще у автора что-то с округлением, слишком уж рваные края получаются…

[flexoid]

Chromium 8.0, результат в точности такой же, только RPS за 11 тысяч.

[dmandreev]

IE9 beta1 16тыс. RPS (P9500 2,5GHz)

[flexoid]

Хохо.
Mobile Intel® Core™ i3-330M (3M Cache, 2.13 GHz)

[dmandreev]

Упс сорри. Думал там прямой линк.

[Sannis]

Так RPS (RPP?) разное. Чем больше, тем более гладкими будут границы.

[glamcoder]

курсач по машграфу в Бауманке? :) если да, то Курову привет.
а вообще Вы молодец, что на JavaScript решились. неординарный выбор, зато кроссплатформенный
кстати, не пробовали в C++ переводить? насколько возрастет производительность?

[glamcoder]

ну то ВМК ж

[sha1dy]

«не пробовали в C++ переводить? насколько возрастет производительность?» — а вы как думаете?

[ABrandt]

Раз 50 я думаю.

[ankh1989]

Не, это я для интереса написал ) Сам учусь на мехмате, но там такую курсовую никогда не зададут.

[chill84]

Работает в safari4, если исправить obj.new = function на var obj = function

[homm]

Есть еще такая давнишняя реализация: jupiter909.com/mark/jsrt.html
Дкмаю, тоже будет интересно посмотреть.

[DjOnline]

Да, работает быстрее.

[Lockal]

В комментарии врывается рейтрейсер реального времени на WebGL на том же javascript.

[Lockal]

Вероятно, это должно помочь: www.opennet.ru/opennews/art.shtml?num=29301

На крайний случай графика будет переложена на Mesa, но это всё равно быстрее.

[ankh1989]

Запустилось на Firefox 4 Beta. Супер ) Там наверно оптимизации на ассемблере не ниже SSE4.2 )

[persei]

скорее, там использование GPU и шейдеров )

[Gesper]

а в FF4b10 работает примерно в 3 раза медленнее.
i5-650 (3.2GHz) 4Gb RAM, Win7-64
Chrome 8.0.552.237 — 18067 RPS
Firefox 4.0b10 — 6248 RPS

[Gesper]

мда, пришел домой, запустил на домашнем ноуте (C2Duo T6600, 2.2GHz) — 8422 RPS
не зря мне давно хотелось ноут поменять

[ankh1989]

У меня вообще морально устаревший Dual-Core 2.0 GHz выдаёт 16,000 RPS. Тут наверно дело в браузере.

[Dunadan]

Отличный топик.
С большим удовольствием слежу за Вашими статьями.

[Valistar]

А теперь делаем это в виде модуля для системы распределенных вычислений, миллион пользователей запускают у себя в браузере страничку, считают, отсылают посчитанное на сервер и на сервере создается 3D video.

Можно его же им и тут же показывать.

[loginsin]

Подобрать бы челюсть и вытереть слюнки с клавиатуры после такого топика!

[kichik]

Свойство __proto__ не стандартное. Для совместимости с ECMAScript, лушче использовать Object.create, примерно так:

return Object.create(cube, {a:{value:a}, b:{value:b}, color:{value:color}, mat:{value:material}});

[TheShock]

Ну, на самом деле, лучше было бы перейти на нормальное создание объектов.

[kichik]

И это тоже :) Пришлось поломать голову в понимании, как связаны объекты и почему не работает в рамках ES5

[RiderSx]

Посмотреть не качая: ridersx.ru/bench/

[SVlad]

В Опере работает довольно резво, вот только с цветами что-то странное:

Как будто произошло переполнение цветовых разрядов.

[SVlad]

Здесь уже ответили

[ankh1989]

Поправил.

[SVlad]

Извините, не туда ответил

[Dubor]

РЕЙТРЕЙСЕР! НА JAVASCRIPT!!!

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

У меня ломка детских стереотипов и вообще когнитивный диссонанс =)

[last1hopeful]

к сожалению из моих 4х ядер используется только одно :( А так прикольно. мы в институте делали движок на raytrace ускоряемый с помощью cuda :)

[SmallTalk]

Как круто-то.
Даешь в следующей версии фотонные карты и каустику!

[ankh1989]

Вы готовы ждать 10 дней пока JS завершит рассчитывать фотонную карту? :) Вот здесь несколько картинок полученных на POV Ray — это оптимизированный рейтрейсер в виде нормальной программы (exe файл на Windows). Так вот, он строит одну такую картинку 8-10 часов.

Мне кажется нет смысла «прокачивать» этот рейтрейсер. Цель статьи ведь была доказать, что рейтрейсер это просто и не важно на каком языке он написан. Следующую статью по рейтрейсингу я посвящу многомерным пространствам — интересно ведь на тень от тессеракта поглядеть :)

[Sannis]

Можно попробовать Node.js :)

[ankh1989]

Предлагаете облачные вычисления всем Хабром? :)

[Sannis]

Не, без фанатизма :)

[FlexFerrum]

Проекция многомерного пространства на плоскость… Да, посмотреть будет очень интересно. :)

[qmax]

Ждём!

А кроме проекции многомерного на плоскость будет не менее интересно посмотреть проекцию на (3d) пространство.
Но такое без WebGL уже никак.

[ankh1989]

У меня есть одна мысль как проектировать 4d на 2d (подход который выбран в википедии для рендеринга тессеракта мне не нравится), но этот метод требует отрейтрейсить хотя бы 0.3 триллиона лучей — JS такое не потянет. Я подумал, что возможно LuaJIT имеет большую производительность, но как показало сравнение (можете посмотреть в маленькой статье которую я только что написал) LuaJIT оказался в 4 раза медленнее Chrome (JavaScript V8). Так что остаётся один вариант: C+Assembler, но запустить такой пример из браузера уже не получится.

Откуда такое огромное количество лучей? Человек с плоским зрением не может увидеть весь тессеракт, в лучшем случае его маленький кусочек. Чтобы увидеть 4d нужно трёхмерное зрение: сначала 4d проецируется на 3d изображение, а затем это 3d можно спроецировать на 2d экран. В википедии сделали нечто подобное: они спроецировали каркас тессеракта на 3d (тривиальная операция которая требует несколько матричных умножений), затем этот каркас обтянули цилиндрами и уже его отрейтрейсили. Фактически получился рейтрейсинг 3d сцены — никакой четырёхмерности там нет.

[Mrrl]

astr73.narod.ru/pics/4D/4d_sph_001.jpg

Вот первая попытка 4D рейтрейсинга. Пока на сцене только сферы (три маленьких лежат на большой). Вычисляется цвет точек объекта, а при визуализации показывается ближайшая точка из тех, которые могли бы попасть в данный пиксель. В результате, например, зеленая сфера видна целиком (она ближе, чем белая сфера, проектирующаяся в то же место), но ее отражение в белой сфере видно лишь частично — только те его точки, которые оказались ближе других точек белой сферы. Аналогичные эффекты с тенями.

[miguello]

"… цвет луча который выходит из глаза..." конечно, феерично, но топик классный. Автору респект и плюсик в карму.

Отдельная просьба — когда-то в детстве баловался в 3dMax, еще в первых его версиях. при создании нового материала никогда не понимал, что значат все эти названия, даже не помню сейчас. Но вот Phong там по-моему точно было. Можете рассказать побольше про эти все параметры, которые я рандомно двигал пока не получал искомое?

[ankh1989]

Спасибо :)

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

• вектор ray луча
• вектор dir направленный от точки к источнику света
• вектор view направленный от глаза к точке
• вектор norm нормали в данной точке

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

Вот например Ламберт. Цвет Ламберта просто равен cos(dir, norm) * k где k это некоторая константа, скажем сила источника света умноженная на цвет поверхности. Модель Ламберта описывает диффузное отражение: луч света падает на шероховатую поверхность и равномерно рассеивается во все стороны, поэтому в формуле Ламберта не важно чему равен view — свет всё равно рассеивается во все стороны равномерно.

Фонг, Блинн, Френель просто предлагают другие формулы.

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

[ZnW]

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

[ankh1989]

Это основы векторной алгебры: почитайте про векторное умножение, скалярное умножение и т.д.

[whoozle]

Нереально круто! :D

[heruvim]

классно! можно прикрутить к серверному JS и потом запустить на компах с GPU

[vanxant]

Мощная статья, но все-таки теплое с мягким не путайте) Матричные преобразования используются для афинных преобразований 3д-вершин — повороты объектов, их переносы, отсечение и все такое. В играх используется текстурирование и освещение — как грубая модель заранее расчитанного рейтрейсинга. Зато очень быстрое.

[vgrichina]

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

Вы путаете вместе методы проецирования, растеризации и освещения.

К слову ray tracing далеко не единственный метод получения реалистичного освещения, смотрите en.wikipedia.org/wiki/Global_illumination

Кстати например в рендерере который использует Пиксар рейтрейсинг используется далеко не в первую очередь – en.wikipedia.org/wiki/PhotoRealistic_RenderMan

[vgrichina]

Я добавлю даже больше – рейтрейсинг чуть менее чем полностью не годится для расчета рассеяного освещения.

Там нужны другие алгоритмы global illumination, например en.wikipedia.org/wiki/Radiosity_(3D_computer_graphics)

[lashtal]

Не совсем верно. Наиболее точный global illumination получается как раз рейтрейсингом (если точнее, bidirectional path tracing, использующий Metropolis-Hastings algorithm) — maxwell render, fryrender, kerkythea и т.д.
Следом идут интерполирующие алгоритмы, например, в vray — light cache + irradiance mapping. Они просчитывают только часть точек сцены, и пытаются расчитать освещение между ними.
Радиосити, как и photon mapping можно считать морально устаревшими на данный момент…

[AHDPEu]

Прикрутить Worker, на вебките есть. Можно ускорить рендер на порядок

[ankh1989]

Я видел только то, что Worker-ы позволяют запускать минимум один js файл. Мне же нужно запустить много раз одну функцию с разными параметрами:

for (var y = 0; y < height; y += 100)
  new thread(renderarea(0, y, width, 100))

Я не знаю как тут применить Worker.

[AHDPEu]

nerget.com/rayjs-mt/rayjs.html
Специально нашел вам пример ретрейсинга с воркерами

[ankh1989]

Спасибо, буду изучать.

[Vlad911]

Чёрт возьми! Это лучшая статья про реализацию алгоритма рейтрейсинга!
Ну и конечно огромный респект, что реализовано на JS.

[masai]

Вообще, прозрачная сфера должна переворачивать изображение. См., например, ray-tracing.ru/articles202.html

[ankh1989]

Если я возьму стеклянный шарик и посмотрю через него на букву W на бумаге, то увижу M?

[masai]

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

[wartur]

Одно слово, на JS круто, помню писал курсач по этому.