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

    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. Все они циклические — можно поставить на автоповтор и получится нормальная анимация.
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 39
      +9
      Я себе в голове порой плохо представляю 4-ёх мерное пространство, а Вы раз и на Си написали!
      Огромное спасибо за пост!
        0
        Я может не точную аналогию проведу, но мы легко представляем себе 1 2ву и 3х мерные массивы, с 4-5-6 уже сложнее.
        Но в коде с ними ровно как и с первыми по сложности.

        но всё таки проПисать графику да, мышление не только пространственное надо :))
          0
          Ну его (4-х мерное пр-во) мало кто представляет на самом деле. Дело в том, что для математики любое n-мерное пространство легко поддается измерениям и вычислениям. Но я тоже благодарен за пост, повтыкал в ролики с удовольствием, и даже попытался код почитать, вникнуть!
          +10
          Спасибо за пост! С большим интересом прочла Вашу предыдущую заметку — но эта еще интереснее :)Жаль, что видео такие короткие. Стоило бы сделать их зацикленными и длящимися не 3-4 секунды, а 30-40, чтобы за десяток циклов можно было попытаться «грокнуть», «прочувствовать» четырехмерную модель.

          Кстати, сейчас у Вас 4-мерная модель проецируется сначала на трехмерное пространство, а затем — на двумерную плоскость. Может быть, стоит попробовать сделать стереоскопическое видео для анаглифических очков или «техники скрещенного взгляда»? (не знаю, как правильно называется второй, вольно обозванный мною метод)

          Также очень любопытно было бы не только видео, но и программа, позволяющая манипулировать 4-мерными фигурами или разгуливать по 4-мерной сцене (этакий Doom или Wolfenstein 3D).
            +1
            Я старался сделать видео как можно боле короткими, но с таким расчётом, чтобы они были «зацикленными». 4 секунды вращения куба это 40 минут рейтрейсинга. Посмотрите архив ссылку на который я дал в самом конце: там видео в хорошем качестве. Запустите и нажмите «replay» — будет бесконечное видео.

            Предлагаете сделать две картинки из двух рядомстоящих точек? Это скорее работа для простого скрипта на Lua — код рейтрейсера на C не изменится. Нужно лишь сформировать две сцены, отрейтрейсить и совместить их. Проверить последний шаг я не смогу, потому что мне никогда не удавалось увидеть изображение на стереограммах.

            4D-realtime это, конечно, круто, но пока что на обычном PC нельзя сделать даже 3D-realtime. Один кадр 4D делается 5 секунд — до realtime тут далеко :)
              0
              Или просто взять какой-нибудь простой видеоредактор и скопировать в него десять раз то самое 4-секундное видео, полученное в результате рендеринга.
              –1
              Я где-то недавно находил апплет, где можно крутить 4D и смотреть через красносиние очки либо «техникой скрещенного взгляда».
                0
                Была статья с обзором 4D игр. В частности там упоминался шутер Adanaxis. Может присмотрите себе интересное что.
                0
                А как бы понять это четырехмерное пространство? Вики интересно, но если прям учебником бы каким? :) А то совсем не технарь, но для общего развитию хочу. :)
                  +1
                  Я на youtube давно смотрел эту серию из 2 роликов, там максимально доходчиво показывают, я даже в голове сумел представить. Главное внимательно вникать в то, что рассказывают, там специально медленно и с подводящими к пониманию примерами.
                    +3
                    Рекомендую ещё Dimensions, ничего более доходчивого не встречал по данной теме.
                    0
                    «I have endeavoured to present the subject of the higher dimensionality of space in a clear manner, devoid of mathematical subtleties and technicalities…

                    0
                    > На этом видео куб неподвижен, а 4-х мерный наблюдатель пролетает через куб

                    Насколько я понимаю, пролетая через 4-x-мерный куб, наблюдатель, должен пересечь его грани (трехмерные кубы) два раза. Но на видео, кажется, пересекли один раз. Мы что, пролетели через ребро? Или остановились внутри куба? Я запутался
                      0
                      Извините, не разглядел, уж очень быстрое видео. Все верно — мы пролетаем между двумя трехмерными гранями через две противоположные друг другу трехмерные грани
                      +1
                      Вы маньяк)
                        0
                        Не любая связная 4хмерная область останется связной в трехмерной и тем более двухмерной проекции. Для сложных сцен наверное схитрить вашим методом не удастся.
                          0
                          Вы имеете ввиду случай когда часть области за камерой? В любом случае алгоритм в конечном итоге выглядит так: на экране проверется каждый, скажем, 15-й пиксель (у меня это параметр сцены options.thickness) и получается сетка. Затем начинает работать заливка. Мой алгоритм может потерять элементы которые помещаются в квадратик 15×15. Но когда у меня стоит выбор: возможная неточность рендеринга или очень долгий рендеринг, я вынужденно выбираю первое.
                            0
                            Еще есть вероятность, что объект не примитив, но это не наш случай. А сейчас угадываете, начиная заливку из области в которой гарантированно есть проекция или случайно блуждаете по экрану?
                              0
                              Я проверяю пиксели с координатами (15M, 15N) и от тех пикселей где есть попадание, начинаю заливку. 15 это параметр «толщины сцены». Если на сцене есть объекты которые дают маленькую проекцию, то надо взять не 15, а скажем 5, т.е. написать options = {thickness = 5}.
                          +1
                          >Аналогично для трёхмерного зрения: четырёхмерный шар будет казаться наблюдателю трёхмерным эллипсоидом.
                          По-моему он будет трехмерным шаром
                            +1
                            Для некоторых моделей 3-х мерного зрения — возможно.

                            Возьмём 4-х мерный шар и глаз 4-х мерного наблюдателя. Проведём всевозможные лучи из глаза в шар — лучи образуют 4-х мерный конус. Сечения конуса перпендикулярные оси — шары. У наблюдателя есть 3-х мерный ровный экран куда всё проецируется. Если экран перпендикулярен оси эллипса то наблюдатель увидит шар, а если не перпендикулярен то эллипсоид.
                              0
                              Да, в общем-то так же, как и в нашем пространстве, если проектор поставить не под прямым углом к экрану. Но это как-бы искажения, четырехмерный наблюдатель же не увидит «силуэт» четырехмерного шара как эллипс.
                                0
                                По этой причине некоторые люди не умеют рисовать. Когда они рисуют табурет они стараются отобразить на рисунке прямые углы сиденья (они ведь знают, что у табурета квадратное сиденье). Это вопрос терминологии и нестрогих допущений. «Силуэт» до шара дорисует мозг, но проекция все равно останется эллипсом.
                                  0
                                  Но шар (не окружность) на картине всегда рисуют как шар
                                    0
                                    В смысле как окружность а не элипс
                                      0
                                      Пожалуй, для того чтобы проекцией стал эллипс, надо чтобы исходный объект был 4хмерной сферой, а не шаром. Сам попался на ту же ошибку с терминологией. Наверное вы правы.
                                        0
                                        А, действительно, сфера-то в элипсоид, наверное, превращается. Я почему-то только про шар думал. Представить бы теперь это как-то
                                          +2
                                          Тоже попался с терминологией, всё шар себе представить пытался. Насколько я понимаю, чтобы получился элипсоид, нам нужен трехмерный шар в четырехмерном пространстве? Или как его назвать, я уже запутался. В общем, у него не должно быть «высоты», он должен быть «плоским»
                                            0
                                            Должен, например, уметь в писываться в грань гиперкуба. Попробуем представить его в нашей проекции. В ней грань гиперкуба это трапеция, и если в нее была вписана 4D-окружность, не должно ли ее расплющить соответственно? То есть не в эллипсоид, а, как бы вырязиться, что-то типа трапеции с до упора скругленными углами?
                                              0
                                              По идее под «плоским» можно понимать любую сферу, т.е. 4хмерный шар, полый вдоль какого-то направления. Тогда проекция под углом к «полому» направлению будет давать искажения. Частным случаем можно считать как раз 3хмерную сферу вписанную в 3хмерную грань, которую предложили вы.
                              +1
                              Что-то мне прямо нехорошо от Вашего видео. Или уработался, не знаю даже. Прямо голова кружится после просмотра :)
                                0
                                Одно из лучших видео про 4д, на мой взгляд. Пролет через 4д куб вообще впервые вижу, впечатляет.
                                Видел пару игр, где попытались реализовать 4д, но там он состоял из плоских по четвертому измерению 3д обьектов. А с такой точностью отрисовки как у вас можно сделать действительно качественную 4д игру.

                                Почему время на отрисовку такое большое? обьект ведь простой… новые видеокарты 3д изображение обрабатывают до сотни раз в секунду на минимальных настройках. Или 4д обьекты на много порядков сложнее рисовать?
                                  0
                                  Тут штука в том что это честный рейтрейсер.
                                    +4
                                    Видеокарты наверно помогут в этом деле, но вряд ли они что то принципиально изменят. Важное отличие рейтрейсинга 3D и 4D следующее:

                                    — В случае 3D, чтобы найти цвет луча нужно найти где луч пересекается с объектом — это конечное число некоторых математических действий. Здесь не важно где находится объект и как направлен луч.

                                    — В случае 4D всё не так просто. Из камеры вылетает условный луч и летит через 3-х мерную проекцию 4-х мерной сцены. Но ведь мы не знаем как выглядит трёхмерная проекция и не можем простым способом выяснить где луч сталкивается с ней. Получается такая штука: у нас есть функция f(q) = цвет точки в 3-х мерной проекции и есть луч q = p + vt который летит через эту сцену; задача найти интеграл вдоль всего луча от f(p + vt). Если не знать как ведёт себя f, остаются лишь квадратурные формулы работающие за время O(длина луча) — здесь, как видите, ограничена длина луча.

                                    Можно, в принципе, сделать одну немного нечестную оптимизацию: сначала спроецировать 4-х мерную сцену на 3-х мерный экран — получится другая уже трёхмерная сцена — после чего обычным алгоритмом спроецировать это дело на экран. Я уверен, что несложно доказать, что проекция 4-х мерного эллипса это 3-х мерный эллипс оси которого находятся одним матричным умножением; аналогично цилиндр перейдёт в некий «обобщённый цилиндроид» и т.д. Плюсы метода: очень красивая картинка с отражениями/преломлениями. Минусы: эти отражения — отражения 3-х мерной проекции, а не исходной 4-х мерной сцены, к тому же, как я говорил, отражения 4-х мерных объектов находятся внутри 3-х мерных проекций, поэтому корректная проекция это бесконечный набор вложенных объектов которая рендерится за бесконечное время.
                                    0
                                    Спасибо за пост!
                                    Обожаю данную тему, пространства старше 3его меня всегда будоражат. И я вообще считаю, что мы являемся проекцией четырех мерного мира (где время это плоскость и можно видеть все варианты ситуации) на 3 мерное пространство. Я даже по этому поводу стихотворение Плоскость Времени написал, когда меня очень шторило от просмотра фильма Геометрия вселенной
                                      0
                                      Вот интересно, если долго медитировать на такую штуку, возникнет ли _ощущение_ 4D-реальности? И знает ли история людей, у которых возникало подобное ощущение?

                                      P.S. классно бы было на подобную штуку в движении посмотреть в стерео.
                                        0
                                        А с какой скоростью считается полупрозрачное отражение в сфере?
                                          0
                                          Сколько времени уходит на рендеринг видео с отражением? Примерно 4 минуты на кадр. Заметно дольше чем рендеринг по методу «first hit» — «первое столкновение со сценой».
                                          0
                                          Мне текст вашего поста напомнил первый учебник по алгебре, который нам в универе выдали (Кострыкина, кажется, авторства).

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

                                          Естественно, что когда сам занимаешься предметом, то он кажется проще чем на самом деле. Возможно поэтому изложение в этом посте получилось чрезмерно кратким, сложным для восприятия.

                                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                          Самое читаемое