Realtime-трассировка лучей
|
Приветы, Томас Людвиг (Thomas Ludwig aka lycium/Quixoft) здесь.
На самом деле я не являюсь экспертом для написания подобной статьи (будучи в возрасте 17-ти лет я не знаток во всем, кроме того, чтобы вызывать неприятности), однако я думаю, что она информативна насколько это возможно. Я рассматриваю данную статью как работу в развитии, так что если вы хотели бы узнать что-нибудь о realtime-трассировке лучей, спрашивайте свободно. Хотя я не на 100% разбираюсь в некоторых аспектах (например, пересечениях с CSG и тором), я обязательно постараюсь найти информацию об этом и, возможно, даже напишу что-нибудь на эту тему. Я сам лично заинтересован в этом вопросе, так что как только узнаю что-нибудь ценное, закину информацию сюда. Если кто-нибудь хорошо разбирается в трассировке лучей и слишком ленив для того, чтобы написать туториал, ОБУЧИТЕ МЕНЯ, и я сделаю это самостоятельно. :) Пожалуйста, имейте ввиду, я изначально предполагаю, что вы ранее уже реализовывали базовый трассировщик лучей и хотите ускорить его. Если вы не делали трассировщик, можете поискать некоторые соответствующие туториалы на Flipcode. Если вы еще не знакомы с данным вопросом, я очень рекомендую начальное руководство по трассировке лучей от Тома Хаммерсли (Tom Hammersley) (это для тех из вас, что как и я, не имеют доступа к приличной библиотеке, в которой есть что-нибудь кроме книг по истории и фантастике). Если появится спрос (по e-mail, намекаю :), я напишу вводный туториал по трассировке лучей (если вам действительно нужна информация, не думайте, что кто-то другой напишет за вас e-mail. Если каждый так поступит, ничего не произойдет :) Довольно трепаться, приступим к делу. Realtime-трассировка лучей Когда Уиттед (Whitted) изобрел трассировку лучей (или по крайней мере обобщенный метод рендеринга как он есть на сегодняшний день), до первой практической реализации трассировщика прошло некоторое время. Главным образом это было из-за значительной вычислительной сложности алгоритма, который однако возможно применить и на медленных машинах. Отметим две основные причины по которым (даже сейчас) трассировка лучей не так популярна, как обычные, основанные на полигонах, методы рендеринга:
1) Алгоритмически, он гораздо медленнее полигональной модели рендеринга.
Несмотря на то, что эти проблемы очень схожи, на самом деле они обособлены друг от друга. Вы можете сколько угодно оптимизировать конвейер трассировки лучей, рано или поздно единственным оставшимся путем увеличения быстродействия станет:
a) Использование повышенной мощности процессора.
Прежде чем заниматься различными методами увеличения скорости трассировки лучей, договоримся о том, что мы должны будем принести в жертву сложность сцены в целях достижения приемлемой величины FPS (даже на современных процессорах). Это означает, что мы, как правило, будем работать с менее чем 16-ю объектами в сцене и ограничимся очень малым числом источников освещения (обычно, двумя). Мы ограничены в решении второй из вышеперечисленных проблем (высокие требования к процессору), так как это зависит от пользователя. Все что мы можем сделать, так это ПОЛНОСТЬЮ использовать преимущества имеющегося процессора, к примеру, используя MMX, SSE и 3Dnow! - инструкции, существующие на многих современных процессорах. Проблема в том, что это выливается в большой объем низкоуровневого кода, специфичного лишь для одной части рендер-конвейера, который привязан к одному типу процессора. Это, как правило, означает БОЛЬШОЕ количество работы, а потому должно рассматриваться в качестве последней меры по оптимизации. Примеры realtime-трассировки лучей На самом деле, существует очень мало дем с realtime-трассировкой, самыми характерными из которых являются:
"Rubicon", "Rubicon 2" // Suburban Creations
Хотя это может показаться и не так, но трассировка лучей в "Spot" действительно поражает, как только вы представите всю геометрическую сложность моделей, проверку теней (спасибо, что автор не настолько сошел с ума, чтобы трассировать неявную поверхность воды ) :) Heaven Seven впечатляет потому, что выглядит намного лучше чем есть на самом деле. Она не проверяет тени на CSG-объектах, она имеет лишь источник освещения (по-видимому; я предчувствую флейм со стороны замечательной команды Exceed на эту тему :), активный в любой момент времени, но и до сих пор она смотрится очень впечатляюще. Rubicon и Rubicon 2 являются примерами высокооптимизированной трассировки лучей, без всяких обманов (cheats). Несмотря на то, что она здорово выглядит, это все еще слишком медленно, чтобы быть realtime (особенно для высоких стандартов демосцены). Я обменялся множеством e-mail-ов с интро-кодером Eberhard Grummt (лидер Suburban Creations, здорово, приятель!) и я могу вас уверить, что на сегодня это самый оптимизированный алгоритм трассировки лучей. Несмотря на это, он все равно остается медленным из-за того, что в нем не применяются некоторые трюки, которые есть у Heaven Seven и Fresnel. Из этого я делаю вывод о необходимости применения обманов для того, чтобы все работало плавно. Те демы были в основном оптимизированы по качеству изображения (протестируйте свой процессор, запустив высококачественную версию Rubicon 1 :). Fresnel и Fresnel 2 идут дальше простого обмана и в действительности используют их как фичу: аппаратное ускорение трассировки. Я знаю, это звучит невероятно, но на самом деле это возможно, и вы получите огромный прирост производительности если вы это сделаете (не говоря уже о билинейной фильтрации, текстурировании с перспективной коррекцией, субпиксельной точности, многом другом). Подобные вещи являются подлинными техническими шедеврами, правда по причинам, не связанным с realtime-трассировкой лучей (вэйвлет-сжатие текстур [текстуры не генерируются, они на самом деле нарисованы и сжаты приблизительно до 2k каждая!], это другая слабо освещаемая тема, уже созревшая для туториала :) Я также обменялся несколькими письмами с Shiva/Kolor (кодер, уважаю!), это другой по-настоящему оптимизированный трассировщик лучей, и, видимо, лучший пример realtime-трейсера на сегодняшний день. Ложка дегтя: суб-семплинг (cheat или фича?) для границ объектов на экране выполнен некорректно и производит мерзкий эффект. Правда при самом низком разрешении разбиения это сложно заметить. Все эти демы вы можете забрать на www.pouet.net (это, кстати, всячески приветствуется :). Итак, без излишних церемоний, давайте посмотрим, что мы можем сделать, чтобы улучшить эффективность алгоритма нашего трассировщика. Оптимизация алгоритма Многие трассировщики используют методы разбиения пространства (например octrees, BSP, KD-деревья, etc.) для ускорения просчета, целью которых является уменьшение числа выполняемых проверок на пересечение. Это абсолютно необходимо для больших сцен (более 500 объектов), а вот для небольших сцен, вроде тех что мы будем использовать, это чересчур. Это мой логический вывод по столь горячо обсуждаемому вопросу. Я не выполнял никаких официальных тестов, однако достаточно уверен, что так оно и есть. Если кто-нибудь имеет другие результаты из тестов, пожалуйста, просветите меня. :) Так что если разбиение пространства хорошо применяется для больших сцен, то для трассировки, которую мы собираемся реализовать в ближайшую пару лет или около этого, оно бесполезно. Кто знает, что будет дальше? Последующие меры состоят из двух подкатегорий:
1) Увеличение эффективности всех тестов на пересечение.
Первое решение является очень действенным: пройдитесь по всем своим алгоритмам и уравнениям и убедитесь, что они действительно оптимальны. Обычно это означает привлечение частных уравнений для определенных объектов (например, не использовать обобщенное квадратное уравнение пересечения для случая пересечения со сферой) и факторизацию уравнений для уменьшения числа операций, требуемых для выполнения пересечения. Очень хорошо оптимизируются случаи, в которых вам требуется лишь определить факт пересечения, не беспокоясь о том, где в точности оно произошло. Теперь я перечислю некоторые примеры введения пространственно-временной связи. Теневые буферы Если вы трассируете экран горизонтальными полосами слева направо, сверху вниз (организация большинства фрейм-буферов), и необходимо выполнить проверку теней для каждого пересечения, вы заметите, что если одна точка затенена, то почти гарантировано, что в тени будет и следующая. Так что для выполнения последовательной проверки на затенение для каждого объекта (согласно закону Мерфи, объект, преграждающий свет, будет последним в списке :) храните указатель на последний преграждающий свет объект. Обман (это для части cheats, но применимо и здесь) заключается только в том, чтобы делать проверку на затенение с каждым вторым пикселом, и если один находится в тени, предположить, что следующий пиксел - тоже и пропустить для него проверку. Предварительное различение Если вы трассируете неявные поверхности и делаете кусочную апроксимацию поверхности интерполируя по сетке, используя квадратичную или кубическую интерполяцию, вы можете воспользоваться тем фактом, что вы трассируете по планарной поверхности (видовая плоскость) и трассируемые точки равномерно расположены (если только вы не используете стохастический сэмплинг, который вы не должны использовать при realtime трассировке лучей :) для того, чтобы проверки на пересечения выполнялись достаточно быстро для работы в реальном времени (вам потребуется определенная инициализация на линию сканирования каждого блока сетки неявной поверхности). Звучит довольно неясно, потому что я хотел включить ссылку на метод, а само описание сделать коротким. В ближайшие несколько лет я не ожидаю увидеть его реализации в realtime :) Ускоряющие трюки В стороне от совершенствования алгоритмов и использования имеющегося компьютера более эффективно за счет специализированных наборов команд, вы также можете прилично увеличить скорость просто немного подумав головой. Если вы видите, что часть вашего кода исполняется особенно долго, спросите себя, существует ли метод, с помощью которого это можно исключить, просчитать заранее, имитировать, и т.д. Некоторые достойные внимания трюки включают в себя: Оптимизация в первом приближении Если любая из величин, которые вы рассчитываете в течение всего хода рендеринга зависит от источника луча и некоторых других величин, которые остаются постоянными для каждого кадра (радиус сферы, позиции объектов и т.д.), вы можете заранее просчитать эти значения и сохранить их в защищенных (private) полях данных структуры объекта, а потом просто использовать их, как только вам потребуется просчет для первичных лучей (лучи исходящие из камеры или глаза). Данный метод работает только для первичных лучей, так как отраженные или преломленные лучи, очевидно, не зависят от позиции камеры. Это означает необходимость написания специализированной процедуры определения пересечения для первичных лучей (или как вы узнаете позже, лучей с фиксированным источником). Это абсолютно необходимая вещь для любого realtime-трассировщика, так как первичные лучи составляют большую часть (относительно, в сравнении с "нормальной" трассировкой лучей) общего числа выпущенных лучей, так как полнота и сложность сцены в нашем случае намного ниже. Оптимизация проверки на затенение Проверки на затенение являются очень прожорливыми, когда вы имеете множество объектов в сцене (n объектов - n проверок на затенение на ОДНО ПЕРЕСЕЧЕНИЕ). Но так как все эти теневые лучи исходят из фиксированного источника (точки пересечения), вы можете заранее сосчитать некоторые значения как это было описано выше. Это должно сохранить вам гигантское количество времени. И снова, это крайне необходимая вещь, так как значительно смягчает потери в скорости, которые возникают при добавлении в сцену каждого нового объекта. Рендерите на половинном (или 1/4) разрешении и интерполируйте Этот метод можно увидеть в Rubicon 1 и 2. Хотя это в действительности не трюк, это также хороший путь увеличения производительности рендеринга. :) Вам не требуется интерполировать обычными квадратами, я слышал о множестве триангулярных схем интерполяции (одна из которых использовалась в деме "I feel like I could" от Spinning Kids'), которые выглядят определенно лучше чем стандартная, основанная на квадратах, интерполяция. Я на самом деле не уверен, есть ли здесь потери в скорости, однако уверен что они должны быть (интерполировать по квадратам проще). Отсюда возникает вопрос, должны ли эти циклы использоваться для совершенствования качества интерполяции, или лучше сократить объем интерполяции и использовать квадраты. Хитро; я считаю, что в него лучше сильно не углубляться... было бы здорово применить несколько конкретных тестов на производительность, жаль, что в сети мало источников информации по трассировке лучей. :) Предварительный расчет покадровых констант Как уже отмечалось во введении, некоторые значения, связанные с пересечениями, являются постоянными для всего кадра (то есть независимы от ориентации луча) и поэтому могут быть рассчитаны заранее. Векторные точечные объекты являются прекрасными целями для этого, так как количество времени за которое числа с плавающей точкой загружаются по медленной системной шине (я использую Celeron и стараюсь избегать работы с 83.3 Мгц системной шиной :), умножаются, суммируются и сохраняются в fp-регистре... это вам не прогулка в парке. Простая загрузка fp-числа из оперативной памяти гораздо компактнее, и к тому же сэкономит вам уйму процессорного времени. Обратные дроби также хороши для предварительного просчета в том случае, если вам приходится много делить на значения покадровых констант. Рендеринг полигональной сетки У вас имеется симпатичная 4К треугольная модель коровы, которую вы хотели бы импортировать в сцену для трассировки лучей (привет Cuban! :) ? В стороне от использования ограничивающего бокса (и BSP) имеется несколько мощных методов оптимизации по времени расчета пересечения, требуемого для подобного объекта. Решение: не трассируйте его. Просто заполните z-буфер трансформированным объектом как он будет выглядеть извне согласно величине расстояния до точки пересечения ("t" как его часто называют) и по любым другим требуемым критериям (цвет, коэффициенты прозрачности, нормали, что угодно) используя стандартный построчный алгоритм. Теперь вы можете трассировать лучи по этому z-буферу, и все будет идеально. Проблемы начнутся, как только вам потребуется выполнить отражение. Если это выпуклый объект, вы можете пропустить всю сетку в проверке на пересечение отраженных лучей, и получить очень простой расчет отражения для объекта! Если же объект не выпуклый, то лучше приготовьте просчитанный для данного объекта BSP, это не сложно, если отражает сам объект, а вот в противном случае все гораздо печальней. :) Я никогда не видел и не слышал ничего об этом, это просто сумасшедшая идея, которая посетила меня недавно пока я принимал душ, так что я даже и не знаю, насколько она могла бы быть полезной. Пересечения теневых лучей здесь также крепкий орешек. Для этого вооружитесь BSP и ограничивающим объектом (не выравнивайте его по осям, вам потребуется ТОЧНОЕ размещение, даже ценой произвольно ориентированного ограничивающего box-а). В общем случае, полигональные сетки не используются в realtime-трассировке, однако с изрядной долей хитрости и хака, это должно сработать. Флаги отбрасывания тени Вы можете здорово улучшить эффективность сцены в том случае, если заранее знаете, какие объекты не будут мешать свету падать на остальные объекты. Это действительно просто реализуется (даже во время проектирования сцены), сильно помогает, так что является насущной необходимостью. К сожалению, довольно трудно автоматически генерировать эти флаги (проверкой всех точек каждой поверхности на каждом временном шаге анимационной последовательности), поэтому об их установке должен позаботиться тот, кто конструирует сцену. Использование итеративного поиска корней с переменной точностью Обычно, когда вы используете итеративный поиск корней (для уравнений пятой и более высоких степеней), вы жестко устанавливаете число итераций (то есть точность) для нахождения корней. У вас мог бы быть код, который увеличивает или уменьшает данную величину исходя из требуемого значения FPS. Небольшая проблема может возникнуть, если машина (или текущая сцена :) по-настоящему медленная, и итеративный подсчет дает неверные корни, которые сваливают программу. Вероятно лучшим решением является исключение объектов высшего порядка по результатам проверки скорости на этапе старта демки. Возможно применение вычислителей на основе формулы Тейлора, которые реально "пожирают" ресурсы процессора, и я боюсь, что в realtime они будут применяться не скоро. Избавьтесь от ООП Каким бы ни было хорошим ООП для трассировки лучей, оно все-таки добавляет массу (мои недавние измерения с помощью VTune меня и вправду испугали) лишнего к типичной (классической?) реализации, в которой каждый объект порождается от базового класса, определяющего несколько виртуальных функций, которые необходимо перекрыть в каждом дочернем классе. Реализация трассировки лучей без ООП выглядит грязной, вроде "хака", но так, конечно, быстрее: я работаю над отдельными реализациями собственного трассировщика для дем (то есть реального времени) и для изготовления высококачественных изображений и видео (для моего последнего проекта Matric, который будет рендерить ролики в локальной сети из двадцати восьми машин на базе Duron 800 МГц/128 Мб). Вы просто держите список различных объектов по типу (например, CSphere cpshere[100], CMesh mesh[100] и т.д.) вместе со счетчиком объектов каждого типа. Некоторые вызовы виртуальных функций для каждого пиксела (если каждому из них требуется ObjectNum-количество проверок на пересечение для операций отражения, то для проверок на затенение их будет в два-три раза больше) являются излишними, это я осознал совсем недавно. Так что приступив кодить трассировщик, вам предстоит сделать серьёзное решение. Не используйте методов разбиения Для обычных сцен (на время написания, будь проклят закон Мура!) пространственное разбиение очень слабо увеличивает производительность в сравнении с теми чрезмерными затратами, которые оно приносит. Обманы (cheats)! Использование обманов (cheats) часто обеспечивает максимальный прирост по скорости, обычно правда теряя в технической удовлетворенности и качестве изображения :) С тех пор как демосцена живет и дышит тем, что делает невозможное, это очень популярный метод ускорения медленного трассировщика лучей. :) Суб-сэмплинг изображений Это, должно быть, самый популярный и распространенный cheat, и основная причина, по которой я пишу эту статью. Я думаю это хороший и "легальный" метод, который действительно заслуживает использования во всех трассировщиках лучей. Он имеет серьёзный потенциал УВЕЛИЧЕНИЯ качества вашего изображения (если вы правильно им воспользуетесь). В основе, вам требуется определить сетку из точек в разрешении гораздо более низком (обычно используются блоки 8х8 или 16х16), чем ваше экранное разрешение. В каждой точке сетки вы ведете расчет по обычному алгоритму трассировки, но с оговоркой: вы на самом деле ничего не рисуете. Вы просто сохраняете идентификаторы пересеченных объектов, координаты U и V текстуры для данного пересечения, аддитивный цвет в данной точке (зеркальное освещение, отраженный цвет + преломленный цвет) и диффузный оттенок в данной точке (просто коэффициент закраски по Ламберту). Теперь, все что вам требуется, так это интерполировать текстуру по квадратам, затем рассчитать полутона с учетом интерполированного коэффициента диффузии, и добавить интерполированный аддитивный цвет. Вот и все! Ну почти, еще можно отметить следующее: Во-первых, что если идентификаторы объектов не одинаковы для всех четырех углов квадрата? Хмм, вот парочка методов, которые можно применить в данном случае: 1.) Первый (и гораздо более быстрый) метод - это рассчитать полный цвет (как если бы вы просчитывали во фрейм-буфере) для всех углов и просто интерполировать с помощью стандартного метода Гуро (или квадратичной интерполяции, решайте сами :) Fresnel 1 и 2 используют данный метод, и я хотел бы поблагодарить Shiva/Kolor за объяснение мне этого метода. 2.) Второй (и более медленный, зато более качественный) метод - разбить квадрат и перетрассировать его, пока все области разбиения не будут иметь одинаковый идентификатор объекта или не будут состоять из одного пиксела (трассируйте не более пяти новых точек :). Для высоких разрешений, очевидно, второй путь может быть довольно медленным, но все равно не настолько, как обычная трассировка! Вы можете еще ускорить этот метод, увеличив начальный размер блока (24х24 или даже 32х32), однако при этом начинает наблюдаться плохое качество картинки (особенно для резких теней, хотя это может быть исправлено добавлением идентификатора тени к идентификатору объекта [убедившись, что при суммировании различных идентификаторов тени и объекта не получались одинаковые, пересекающиеся результаты], спасибо Dman-у за этот совет!) после увеличения размера блока, однако здесь проявляется вторая проблема этого метода. Heaven Seven и все остальные Realtime - трассировщики используют этот метод (за исключением Rubicon 1 и 2). Второй проблемой этого метода является то, что маленькие объекты (меньшие размера вашего блока), полностью содержащиеся внутри блока и не касающиеся углов, будут пропущены. Это на самом деле не столь важно для realtime-трассировки, если только вы не можете избежать использования таких мелких объектов :) Так или иначе, реализуйте это. Так как подобная интерполяция замечательно реализуется средствами 3D-видеокарт (намек :), вы можете последовать примеру Kolor и использовать OpenGL или DirectX для отрисовки квадратов. Таким образом вы не только значительно увеличиваете скорость рендеринга, но также получаете билинейную фильтрацию, суб-пиксельную точность, высококачественную закраску Гуро, прозрачность, все на халяву. Теперь это кое-что значит, и должно стать стандартом для любой демки с realtime-трассировкой :) Если вы все-таки решите использовать программную интерполяцию, я настоятельно рекомендую использовать по крайней мере команды MMX (RGB-закраска Гуро без MMX-а не так хороша), особенно если вы используете программную билинейную фильтрацию (безумие, лучше увеличить параметры детализации и число объектов :) Интерполяция кадра В далеком прошлом я делал несколько тестов с нелинейной кадровой интерполяцией и выяснил, что если сцена сильно не изменяется от кадра к кадру (читай: МЕДЛЕННОЕ движение камеры :), то это выглядит очень впечатляюще (как отдельный эффект :) и экономит массу времени. Что вам нужно, так это рендерить на один кадр вперед, и просто интерполировать между текущим, предыдущим и последующим кадрами, используя кубическую интерполяцию (бета-сплайны тоже неплохо работают, но уж слишком дорог их обсчет). Да, убедитесь, что вы пишете свой интерполятор под MMX. Другим простым трюком может быть рендеринг в ТВ-стиле: просчитывайте строки через одну и интерполируйте (лучше если нелинейно, разница чувствуется) между просчитанными и неизвестными линиями. Совет: для ускорения интерполяции рендерите вертикальные полосы вместо горизонтальны х (разумное использование кеша). Фальсификация объекта Очевидно, что объекты пятого порядка вроде тора вполне возможно имитировать, используя CSGed объекты четвертого порядка. Gamma2/mfx предположительно делает именно так, я не получал точного подтверждения этому. Я не говорю, что это фальшивка, она просто показывает насколько это может быть эффективным (правда с такими сильными фильтрами размытия там все равно много не разглядишь :) Хотя это и не связано с ускорением самой трассировки, это классный трюк (если вы его правильно реализуете). Заключение и ссылки Этот документ далек до своего завершения, но я полон желания опубликовать первую версию. Может быть, я получу некоторые отклики, которые выразятся в виде дополнений к тексту. В сети не очень-то много информации по трассировке лучей для начинающих, которые не имеют докторской степени в математике, английском и информатике, что, конечно же, жаль. Большинство документов которые я прочел на высокоуровневые темы вроде трассировки лучей, вейвлетам и т.д. обычно настолько "шифруются" всякими профессорами, что только другой такой профессор может прочитать и понять их (например, "образ" (image) - "дискретно ограниченная однополярная планарная целочисленная функция". Я должен пособирать цитаты подобные этой, они чертовски забавны), и я только сейчас стал использовать этот "диалект". В любом случае, довольно морали. Если у вас есть какая-нибудь хорошая информация по трассировке лучей на английском языке (в частности та, которая подходит для realtime- трассировки), я был бы очень благодарен, если бы вы написали мне хоть строчку. А вообще, пишите мне в любом случае :) Вот некоторые ссылки, что я собрал по части трассировки лучей, вы найдете, что многие из них имеют советы по ускорению процесса. Просто игнорируйте то, что касается разбиения пространства :)
Туториалы по трассировке лучей на Polygone:
Документация на трассировку лучей от Тома Хаммерсли:
Туториалы на определение пересечений:
Библиотека для работы с пересечениями (множество кода):
RTRT реальность (хорошие исходники дем):
RTRT FAQ:
Приветы и благодарности Я хотел бы поблагодарить всех дружелюбных людей, которые помогли мне научиться realtime-трассировке лучей, особенно лидера Suburban Creations за ответы на все мои действительно глупые и беспрерывные вопросы. Респект! :) Вот еще приветы (я вероятно забыл 99% из них):
Quartz/Kolor (здорово помог во всем :)
Перевод: Невидимка |