Идея с ближайшей точкой к камере интересная. А вот это «Такую ближайшую точку (когда границы угла вычислены) можно быстро найти для любого базового объекта, после чего трассировку можно выполнять только для нее — получается одна трассировка на пиксель» я не понял.
Я не заметил ваш комментарий, извиняюсь. Отправьте мне свой e-mail через ЛС и я отправлю вам эти два файла с комментариями. Обновлять zip архив не хочу, потому что я у себя что то менял в коде и сейчас bmp файлы пишутся неправильные, а разбираться в этом сейчас нет времени.
vec.vec это векторное произведение в n-мерном пространстве. Для трёхмерного случая есть простая формула, а в общем случае это считается через определитель. Определитель можно найти методом Гаусса.
Впечатляет. Я ещё заметил, что Lua тратит много времени на заполнение массива в screen.render:
this.pixels[index] = color
Если убрать эту строчку, а также вывод процентов через io.write, то скорость возрастает более чем в три раза. Надо заметить, что для JS это не важно: там вывод на экран и сохранение пикселей не влияет на скорость. Как сказать Lua, что this.pixels это массив фиксированной длины?..
Я наверно запутанно описал свою идею. Она же, но немного по другому.
Пусть у нас есть тессеракт T в 4-х мерном пространстве. Выберем трёхмерный куб M3 — монитор 4-х мерного наблюдателя. Возьмём камеру C не лежащую в трёхмерной плоскости с M3. Спроектируем T на M3 с помощью C и получим проекцию T' — она лежит внутри M3. Теперь возьмём наш двумерный монитор M2 и камеру C2 так, чтобы из этой камеры было видно через M2 проекцию T'. Спроектируем T' на M2 и получим T'' — это то что мы увидим на экране. Реализация этого алгоритма будет делать всё в обратном порядке: выпускать луч из C2, находить пересечение с T', выпускать луч из C через точку пересечения и находить пересечение с T.
Я планирую обойтись без Z-буфера. Визуализацию 3D пока не знаю как лучше сделать: можно сплошной (как на рисунках) а можно и полупрозрачной (будет дольше работать). Смотря как красивее получится.
Мысль очень правильная :) Я не сделал этого по одной причине: боялся, что кто-нибудь откроет файл raytracer.js, увидит там 2000 строчек какого то текста и подумает «ну вот… а говорил, что код рейтрейсера простой — а тут как обычно манускрипт на несколько экранов», хотя большая часть текста будет на самом деле комментариями. Я однажды читал исходник алгоритма BWT написанный автором DjVu (они в свободном доступе) — там столько текста, что… Но если выкинуть комментарии, то окажется, что кода совсем немного.
Мне не сложно прокомментировать: напишите только список файлов в которых вы хотите увидеть комментарии.
Нет, именно всего 4D на 2D. Сделать проекцию трёхмерного среза 4D на 2D можно уже сейчас: нужно просто заменить строку vec.dim = 3 на vec.dim = 4. Получится такая картинка:
Увидеть все 16 вершин не получится: они не лежат в трёхмерном пространстве.
Проецирование 4D я собираюсь делать в два шага: сначала спроецирую 4D на трёхмерный куб (аналог 2-мерного монитора) и затем этот куб спроецирую на плоский экран. Но делать это буду наоборот: буду выпускать лучи из камеры (то место откуда смотрит 3-мерный наблюдатель) лежащей в одном 3-мерном срезе с кубом, лучи будут проходить через куб и через точки пересечения луча с кубом я буду запускать лучи из второй камеры (глаз четырёхмерного наблюдателя) которые пересекаясь с тем 3-мерным кубом ровно в одной точке будут сталкиваться с предметами на сцене (с тессерактом). Это требует N3 лучей где N — ширина кубического монитора. Учитывая, что лучи преломляются и отражаются в среднем 300 раз, надо отрендерить 300•N3 лучей, 0.3 триллиона.
Рейтрейсеру нужно только уметь делать 4 арифметические операции и находить квадратный корень. Все эти пять действий вычисляются процессором, так что их не получится неоптимально реализовать. Другое дело сама среда Lua — сборщик мусора, создание новых объектов, обращения к полям таблиц — может иметь какие то особенности которых я не знаю.
Между Lua и JS есть важное отличие: Lua-программа может взаимодействовать с ОС (записывать файлы например), а также Lua-машину можно расширить любым кодом на любом языке (можно dll подключить и вызывать функции из этой dll прямо из кода на Lua). JS ограничен рамками браузера.
Я тоже фанат Lua и очень хочу найти этот подводный камень :) Этот рейтрейсер на Lua я написал не просто так: я хочу сделать рейстрейсер 4-х мерного пространства, а там нужна производительность хотя бы 1,000,000 RPS. Мне казалось, Lua будет в 20 раз быстрее JS, а оказалось…
У меня есть одна мысль как проектировать 4d на 2d (подход который выбран в википедии для рендеринга тессеракта мне не нравится), но этот метод требует отрейтрейсить хотя бы 0.3 триллиона лучей — JS такое не потянет. Я подумал, что возможно LuaJIT имеет большую производительность, но как показало сравнение (можете посмотреть в маленькой статье которую я только что написал) LuaJIT оказался в 4 раза медленнее Chrome (JavaScript V8). Так что остаётся один вариант: C+Assembler, но запустить такой пример из браузера уже не получится.
Откуда такое огромное количество лучей? Человек с плоским зрением не может увидеть весь тессеракт, в лучшем случае его маленький кусочек. Чтобы увидеть 4d нужно трёхмерное зрение: сначала 4d проецируется на 3d изображение, а затем это 3d можно спроецировать на 2d экран. В википедии сделали нечто подобное: они спроецировали каркас тессеракта на 3d (тривиальная операция которая требует несколько матричных умножений), затем этот каркас обтянули цилиндрами и уже его отрейтрейсили. Фактически получился рейтрейсинг 3d сцены — никакой четырёхмерности там нет.
Если убрать эту строчку, а также вывод процентов через io.write, то скорость возрастает более чем в три раза. Надо заметить, что для JS это не важно: там вывод на экран и сохранение пикселей не влияет на скорость. Как сказать Lua, что this.pixels это массив фиксированной длины?..
Пусть у нас есть тессеракт T в 4-х мерном пространстве. Выберем трёхмерный куб M3 — монитор 4-х мерного наблюдателя. Возьмём камеру C не лежащую в трёхмерной плоскости с M3. Спроектируем T на M3 с помощью C и получим проекцию T' — она лежит внутри M3. Теперь возьмём наш двумерный монитор M2 и камеру C2 так, чтобы из этой камеры было видно через M2 проекцию T'. Спроектируем T' на M2 и получим T'' — это то что мы увидим на экране. Реализация этого алгоритма будет делать всё в обратном порядке: выпускать луч из C2, находить пересечение с T', выпускать луч из C через точку пересечения и находить пересечение с T.
Мне не сложно прокомментировать: напишите только список файлов в которых вы хотите увидеть комментарии.
Увидеть все 16 вершин не получится: они не лежат в трёхмерном пространстве.
Проецирование 4D я собираюсь делать в два шага: сначала спроецирую 4D на трёхмерный куб (аналог 2-мерного монитора) и затем этот куб спроецирую на плоский экран. Но делать это буду наоборот: буду выпускать лучи из камеры (то место откуда смотрит 3-мерный наблюдатель) лежащей в одном 3-мерном срезе с кубом, лучи будут проходить через куб и через точки пересечения луча с кубом я буду запускать лучи из второй камеры (глаз четырёхмерного наблюдателя) которые пересекаясь с тем 3-мерным кубом ровно в одной точке будут сталкиваться с предметами на сцене (с тессерактом). Это требует N3 лучей где N — ширина кубического монитора. Учитывая, что лучи преломляются и отражаются в среднем 300 раз, надо отрендерить 300•N3 лучей, 0.3 триллиона.
Откуда такое огромное количество лучей? Человек с плоским зрением не может увидеть весь тессеракт, в лучшем случае его маленький кусочек. Чтобы увидеть 4d нужно трёхмерное зрение: сначала 4d проецируется на 3d изображение, а затем это 3d можно спроецировать на 2d экран. В википедии сделали нечто подобное: они спроецировали каркас тессеракта на 3d (тривиальная операция которая требует несколько матричных умножений), затем этот каркас обтянули цилиндрами и уже его отрейтрейсили. Фактически получился рейтрейсинг 3d сцены — никакой четырёхмерности там нет.
Я не знаю как тут применить Worker.