Pull to refresh

Рейтрейсер четырёхмерного пространства

Algorithms *
TitlePic

Недавно я делал простой рейтрейсер 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-х мерного куба.




Cube4D

Перейдём к отражениям. Когда вы смотрите на шар с отражающей поверхностью (на ёлочную игрушку, например), отражение как бы нарисовано на поверхности сферы. Также и для 3-х мерного зрения: вы смотрите на 4-х мерный шар и отражения нарисованы как бы на его поверхности. Только вот поверхность 4-х мерного шара трёхмерна, поэтому когда мы будем смотреть на 3-х мерную проекцию шара, отражения будут внутри, а не на поверхности. Если сделать так, чтобы рейстрейсер выпускал луч и находил ближайшее пересечение с 3-х мерной проекцией шара, то мы увидим чёрный круг — поверхность трёхмерной проекции будет чёрная (это следует из формул Френеля). Выглядит это так:

ReflectionFirstHit

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

image



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

Оптимизации



Рейтрейсить 4-х мерную сцену сложнее чем 3-х мерную: в случае 4D нужно найти цвета трёхмерной области, а не плоской. Если написать рейтрейсер «в лоб», его скорость будет крайне низкой. Есть пара простых оптимизаций, которые позволяют сократить время рендеринга картинки 1000×1000 до нескольких секунд.

Первое, что бросается в глаза при взгляде на такие картинки — куча черных пикселей. Если изобразить область где луч рейтрейсера попадает хоть в один объект, получится так:

Map

Видно, что примерно 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. Все они циклические — можно поставить на автоповтор и получится нормальная анимация.
Tags:
Hubs:
Total votes 107: ↑105 and ↓2 +103
Views 15K
Comments Comments 39