Недавно я делал простой рейтрейсер 3-х мерных сцен. Он был написан на JavaScript и был не очень быстрым. Ради интереса я написал рейтрейсер на C и сделал ему режим 4-х мерного рендеринга — в этом режиме он может проецировать 4-х мерную сцену на плоский экран. Под катом вы найдёте несколько видео, несколько картинок и код рейтрейсера.
Зачем писать отдельную программу для рисования 4-х мерной сцены? Можно взять обычный рейтрейсер, подсунуть ему 4D сцену и получить интересную картинку, однако эта картинка будет вовсе не проекцией всей сцены на экран. Проблема в том, что сцена имеет 4 измерения, а экран всего 2 и когда рейтрейсер через экран запускает лучи, он охватывает лишь 3-х мерное подпространство и на экране будет виден всего лишь 3-х мерный срез 4-х мерной сцены. Простая аналогия: попробуйте спроецировать 3-х мерную сцену на 1-мерный отрезок.
Получается, что 3-х мерный наблюдатель с 2-х мерным зрением не может увидеть всю 4-х мерную сцену — в лучшем случае он увидит лишь маленькую часть. Логично предположить, что 4-х мерную сцену удобнее разглядывать 3-х мерным зрением: некий 4-х мерный наблюдатель смотрит на какой то объект и на его 3-х мерном аналоге сетчатки образуется 3-х мерная проекция. Моя программа будет рейтрейсить эту трёхмерную проекцию. Другими словами, мой рейтрейсер изображает то, что видит 4-х мерный наблюдатель своим 3-х мерным зрением.
Особенности 3-х мерного зрения
Представьте, что вы смотрите на кружок из бумаги который прямо перед вашими глазами — в этом случае вы увидите круг. Если этот кружок положить на стол, то вы увидите эллипс. Если на этот кружок смотреть с большого расстояния, он будет казаться меньше. Аналогично для трёхмерного зрения: четырёхмерный шар будет казаться наблюдателю трёхмерным эллипсоидом. Ниже пара примеров. На первом вращаются 4 одинаковых взаимноперпендикулярных цилиндра. На втором вращается каркас 4-х мерного куба.
Перейдём к отражениям. Когда вы смотрите на шар с отражающей поверхностью (на ёлочную игрушку, например), отражение как бы нарисовано на поверхности сферы. Также и для 3-х мерного зрения: вы смотрите на 4-х мерный шар и отражения нарисованы как бы на его поверхности. Только вот поверхность 4-х мерного шара трёхмерна, поэтому когда мы будем смотреть на 3-х мерную проекцию шара, отражения будут внутри, а не на поверхности. Если сделать так, чтобы рейстрейсер выпускал луч и находил ближайшее пересечение с 3-х мерной проекцией шара, то мы увидим чёрный круг — поверхность трёхмерной проекции будет чёрная (это следует из формул Френеля). Выглядит это так:
Для 3-х мерного зрения это не проблема, потому что для него виден весь этот 3-х мерный шар целиком и внутренние точки видны также хорошо как и те, что на поверхности, но мне надо как то передать этот эффект на плоском экране, поэтому я сделал дополнительный режим рейтрейсера когда он считает, что трёхмерные объекты как бы дымчатые: луч проходит через них и постепенно теряет энергию. Получается так:
Тоже самое верно для теней: они падают не на поверхность, а внутрь 3-х мерных проекций. Получается так, что внутри 3-х мерного шара — проекции 4-х мерного шара — может быть затемнённая область в виде проекции 4-х мерного куба, если этот куб отбрасывает тень на шар. Я не придумал как этот эффект передать на плоском экране.
Оптимизации
Рейтрейсить 4-х мерную сцену сложнее чем 3-х мерную: в случае 4D нужно найти цвета трёхмерной области, а не плоской. Если написать рейтрейсер «в лоб», его скорость будет крайне низкой. Есть пара простых оптимизаций, которые позволяют сократить время рендеринга картинки 1000×1000 до нескольких секунд.
Первое, что бросается в глаза при взгляде на такие картинки — куча черных пикселей. Если изобразить область где луч рейтрейсера попадает хоть в один объект, получится так:
Видно, что примерно 70% — черные пиксели, и что белая область связна (она связна потому что 4-х мерная сцена связна). Можно вычислять цвета пикселей не по порядку, а угадать один белый пиксель и от него сделать заливку. Это позволит рейтрейсить только белые пиксели + немного черных пикселей которые представляют собой 1-пиксельную границу белой области.
Вторая оптимизация получается из того, что фигуры — шары и цилиндры — выпуклы. Это значит, что для любых двух точек в такой фигуре, соединяющий их отрезок также целиком лежит внутри фигуры. Если луч пересекает выпуклый предмет, при этом точка A лежит внутри предмета, а точка B снаружи, то остаток луча со стороны B не будет пересекать предмет.
Ещё несколько примеров
Здесь вращается куб вокруг центра. Шар куба не касается, но на 3-х мерной проекции они могут пересекаться.
На этом видео куб неподвижен, а 4-х мерный наблюдатель пролетает через куб. Тот 3-х мерный куб что кажется больше — ближе к наблюдателю, а тот что меньше — дальше.
Ниже классическое вращение в плоскостях осей 1-2 и 3-4. Такое вращение задаётся произведением двух матриц Гивенса.
Как устроен мой рейтрейсер
Код написан на ANSI C 99. Скачать его можно здесь. Я проверял на ICC+Windows и GCC+Ubuntu.
На вход программа принимает текстовый файл с описанием сцены.
scene =
{
objects = -- list of objects in the scene
{
group -- group of objects can have an assigned affine transform
{
axiscyl1,
axiscyl2,
axiscyl3,
axiscyl4
}
},
lights = -- list of lights
{
light{{0.2, 0.1, 0.4, 0.7}, 1},
light{{7, 8, 9, 10}, 1},
}
}
axiscylr = 0.1 -- cylinder radius
axiscyl1 = cylinder
{
{-2, 0, 0, 0},
{2, 0, 0, 0},
axiscylr,
material = {color = {1, 0, 0}}
}
axiscyl2 = cylinder
{
{0, -2, 0, 0},
{0, 2, 0, 0},
axiscylr,
material = {color = {0, 1, 0}}
}
axiscyl3 = cylinder
{
{0, 0, -2, 0},
{0, 0, 2, 0},
axiscylr,
material = {color = {0, 0, 1}}
}
axiscyl4 = cylinder
{
{0, 0, 0, -2},
{0, 0, 0, 2},
axiscylr,
material = {color = {1, 1, 0}}
}
После чего парсит это описание и создаёт сцену в своём внутреннем представлении. В зависимости от размерности пространства рендерит сцену и получает либо четырёхмерную картинку как выше в примерах, либо обычную трёхмерную. Чтобы превратить 4-х мерный рейтрейсер в 3-х мерный надо изменить в файле vector.h параметр vec_dim с 4 на 3. Можно его также задать в параметрах командной строки для компилятора. Компиляция в GCC:
cd /home/username/rt/
gcc -lm -O3 *.c -o rt
Тестовый запуск:
/home/username/rt/rt cube4d.scene cube4d.bmp
Если скомпилировать рейтрейсер с vec_dim = 3, то он выдаст для сцены cube3d.scene обычный куб.
Как делалось видео
Для этого я написал скрипт на Lua который для каждого кадра вычислял матрицу вращения и дописывал её к эталонной сцене.
axes =
{
{0.933, 0.358, 0, 0}, -- axis 1
{-0.358, 0.933, 0, 0}, -- axis 2
{0, 0, 0.933, 0.358}, -- axis 3
{0, 0, -0.358, 0.933} -- axis 4
}
scene =
{
objects =
{
group
{
axes = axes,
axiscyl1,
axiscyl2,
axiscyl3,
axiscyl4
}
},
}
Объект group помимо списка объектов имеет два параметра аффинного преобразования: axes и origin. Меняя axes можно вращать все объекты в группе.
Затем скрипт вызывал скомпилированный рейтрейсер. Когда все кадры были отрендерены, скрипт вызывал mencoder и тот собирал из отдельных картинок видео. Видео делалось с таким расчётом, чтобы его можно было поставить на автоповтор — т.е. конец видео совпадает с началом. Запускается скрипт так:
luajit animate.lua
Ну и напоследок, в этом архиве 4 avi файла 1000×1000. Все они циклические — можно поставить на автоповтор и получится нормальная анимация.