Настало время для еще одной комбинированной истории про математику и модные плюшки. А именно про то, что спрятано под капотом у плашки "RTX on", которую можно увидеть в современных игрушках, вернее даже в и их рекламе. А там спрятаны прелюбопытные вещи: заполняющие пространство кривые, кластеризация, одноканальное кодирование, и множество Кантора.
Давайте по порядку. 2018 год запомнился ценителям неким знаменательным событием: Nvidia с большой помпой выкатила первое поколение видеокарт, которые могут в рэйтрейсинг (RT) в реальном времени. Они даже какую-то дурацкую характеристику придумали: "гигалучи в секунду", которых вот типа у них теперь 10, и это гораздо больше, чем было раньше. Но, как по мне, чисто маркетинговый трюк: никаких 10 миллиардов лучей в общем случае их карты как тогда не считали, так и сейчас не считают. Если бы это в принципе было возможно, то мы бы уже имели фотореалистичную виртуальную реальность на автономных шлемах.
 |
| Жызнь с бородой / Жызнь без бороды |
Итак, что такое рэйтрейсинг (трассировка лучей, если по человечески). Это один из способов рендеринга.
Рендеринг - это процесс перевода 3d-сцены в 2-мерное изображение на плоском экране. Базовая единица экрана - пиксель, базовая единица сцены - треугольник. Рендеринг состоит в построении соответствия между треугольниками и пикселями. Пусть первых П штук, а вторых - T, обе величины квадратично растут относительно уровня детализации. Можно помыслить себе гигантскую матрицу размера ПxТ, в которой по одному измерению перечислены пиксели, а по другому треугольники. В этой матрице на (i,j)-месте стоит цвет i-го пикселя, который дает j-й треугольник. Эта матрица очень разреженная: если взять наобум треугольник, то он мало пикселей на экране занимает, если вообще занимает. Для вычисления цвета нужно знать нормаль к поверхности и световой фон, - это отдельная история, о которой я писал раньше.
Есть два типа рендеринга: растеризация и рэйтрейсинг. Они в некотором смысле двойственны друг другу по Даукеру.
При растеризации мы проходим по всем треугольникам сцены, и каждый из них проецируем из точки наблюдателя на экран - начиная от дальних и заканчивая ближними, - чтобы ближние перекрывали дальние. При растеризации одного треугольника мы проходим ровно по тем пикселям, которые задевает треугольник, - и ни по каким больше. То есть мы в итоге перебираем все непустые ячейки нашей ПхТ матрицы, и только их. Число операций, которые для этого требуются, близко к теоретическому минимуму, - а значит этот метод очень шустрый, и практически неулучшаемый. А потому это дефолтный метод в игрушках и 3d-редакторах.
При рэйтрейсинге мы проходим по всем пикселям, через каждый из них от наблюдателя пускаем луч, и проверяем, какие треугольники он пересекает. Берем самый ближний, и его цветом закрашиваем пиксель. Математически как будто то же, что и раньше. Спроецировать треугольник на плоскость так же просто, как и проверить, пересекает ли луч треугольник (про концептуальный взгляд на последнее см. заметку о двойственности Гейла). Но есть нюанс. При наивном рэйтрейсинге надо проверить на пересечение ВСЕ треугольники сцены. Мы же априори не знаем какие из них попадают на камеру, а какие нет. Поэтому при наивном рэйтрейсинге требуется ПхТ операций. Это получается 4-ая степень от детализированности, что убер-дофига. Даже не только для игрушек, но и для какого-нибудь Кэмерона с его "Аватаром".
Казалось бы, на черта нам тогда этот рэйтрейсинг поганый? Потому что он в принципе похож на то, как свет себя ведет в геометрической оптике, а значит с помощью него можно хорошо симулировать физические эффекты: отражения, преломления, да и в целом распространение света. Если мы пустили луч в сцену и он наткнулся на треугольник со свойством зеркальности, то нам достаточно отразить луч (используя значение из карты нормалей): проитерируем пуск луча уже из новой точки и в новом направлении, и посмотрим, на что он наткнется дальше. Или например, если мы хотим понять освещенность какой-то точки сцены, то мы пустим в эту точку луч из источника света - и поймем, натыкается он на пути на препятствие или нет. Вообще отрисовка теней от объектов - это отдельная проблема, которую кое-как решать научились: например, Doom3 прославился довольно эстетичным новым алгоритмом для этого дела. Но вот если бы рэйтрейсинг хорошо работал - то он бы и проблему с тенями автоматом решал.
Остается оптимизировать рэйтрейсинг, так чтобы он работал за разумное время. Первый шаг к решению: засунуть каждый отдельный объект сцены в виртуальный контейнер: под контейнером дальше всегда понимается параллелепипед со сторонами параллельными координатным осям. Допустим, у нас по коридору бежит толпа орков. Прежде чем проверять луч на пересечение с треугольниками одного орка - проверим: а пересекает ли он контейнер, содержащий этого орка? Если пересекает, то да, проверяем треугольники этого орка. Если нет, - не проверяем. Это нам дает приличную оптимизацию: бОльшая часть экранных лучей контейнер не пересекает и мы сэкономили на них кучу вычислений.
Однако мы по прежнему потратим много времени напрасно, когда луч пересекает контейнер. Уважающие себя орки состоят из десятков тысяч треугольников, и все это добро придется обсчитывать. Поэтому идею с контейнером надо довести до совершенства. Разобъем наш контейнер с орком на две половинки: одна содержит одну половину орка (лучшую), другая - оставшуюся. Если луч наткнулся на контейнер, то мы проверим два отдельных подконтейнера. Если мы наткнулись на какую-то из половинок, то проверим четвертинки. И так далее: будем резать нашего орка в контейнере по заветам Больцано, пока не дойдем до отдельных атомов, ой, то есть треугольников. Получаем бинарное дерево из контейнеров: если его высота h, то оно имеет 2^h листьев, и это число примерно сравнимо с числом треугольников n. Для проверки на пересечение лучом нам надо пройтись по дереву и проверить порядка C*h=С*log n контейнеров, а это весьма приятнее чем n, которое было изначально.
Ура, мы придумали идею, которая называется Bounding Volume Hierarchy (BVH). Но конкретная реализация пока не очень хороша вот по какой причине. Треугольная поверхность орка 2-мерная, а больцановское подразбиение работает с 3-мерным пространством. Поэтому большинство кирпичиков, на которые мы нарезали орка, никаких треугольников вообще не содержит. Но луч многие из них все равно пересечет. Поэтому мы в нашем дереве будем ходить не по одной ветке, а по целой куче, и никакого логарифма от числа треугольников на практике не получится.
 |
| Наше все. Сперто из презентации (любой) NVidia |
Нам хочется заиметь такую иерархию ограничивающих объемов, чтобы она прицельно задевала поверхность орка, но не трогала пустоту внутри него и вне его. Поэтому кажется, что надо плясать от самого орка, а не от ограничивающего его контейнера.
Давайте отметим центр каждого треугольника. Получили облако точек в R^3, имеющее смутное очертание орка. Теперь нам надо засунуть эти точки в некую древесную иерархию: построить дерево с таким условием, чтобы каждый лист соответствовал точке из облака, и для каждой ноды все ее листы-потомки образовывали некий скученный кластер точек в R^3: чем дальше нода от корня, - тем меньше кластер. По каждому такому кластеру можно очевидным образом построить ограничивающий объем для соответствующего множества треугольников.
Мы пришли буквально к тому, что в высокой науке обучения машин называется задачей иерархической кластеризации. Есть набор точек, надо их объединить вначале в маленькие кластеры, потом в кластеры поболбше, и так далее, пока не дойдем до кластера из всего набора.
Те, кто понимает, что наука об устойчивых гомологиях в размерности 0 решает задачу иерархической кластеризации в произвольном конечном метрическом пространстве, могут в этом месте начать придумывать, как бы продать эту мысль компании Nvidia. Но у меня есть скепсис на этот счет: даже с крутыми tda-шными свистелками скорее всего устойчивые гомологии будут слишком долго считаться. И на gpu вряд ли параллелятся. И дерево там вряд ли получится сбалансированное: не забываем, что наша цель логарифм. Так что тут прямо реально постараться придется.
3d-шники, однако, придумали весьма экстравагантный подход к задаче иерархической кластеризации, - я такого в статьях по анализу данных не встречал. Прежде чем вдаваться в детали, опишу математическую философию, которую я за ним вижу.
Допустим, что облако точек D, которое надо иерархически кластеризовать, сэмплируется из некоторого метрического пространства X. В нашем случае это R^3 с евклидовой метрикой (ну или с чебышевской, если вам хочется, чтобы это лучше согласовывалось с контейнерами-кирпичами и быстрее считалось). Можем даже считать, что все точки лежат в единичном кубе X=[0,1]^3 со стандартной метрикой. Сделаем такой фокус: подберем метрическое пространство Y и отображение f:Y-->X так чтобы выполнялись условия
(1) f сюръективное и липшицево (ну или хотя бы равномерно непрерывное).
(2) задача кластеризации в пространстве Y решается быстро и просто.
Тогда вы можете сделать следующий финт ушами.
- Поднимаете датасет D до датасета D' в пространстве Y.
- Кластеризуете D' в пространстве Y.
- Переносите кластеризацию на исходный датасет.
- Вы великолепны!
Свойство липшицевости гарантирует что любой скученный кластер в Y отображается в скученный кластер в X, поэтому то, что мы получили, - это действительно решение исходной задачи, ну плюс-минус.
Осталось разобраться с таинственной фразой "задача кластеризации в пространстве Y решается быстро". Что это за пространства такие? Тезис: это пространства со старой доброй ультраметрикой. Например, множество Кантора подойдет.
Ультраметрические пространства сами по себе представляют из себя иерархическую структуру. Посмотрите на множество Кантора или канторову пыль: там довольно очевидно, что такое кластеры. Для произвольных ультраметрик есть свойство: если два шара пересекаются, то один лежит внутри другого. Это нас избавляет от ненужных переживаний по поводу (не)транзитивности отношения близости: в ультраметрическом пространстве если x близко к y, а y близко к z, то то x близко к z. В евклиде такое, конечно, не работает, из-за этого теория пространств толерантности - это действительно теория, а не хрен собачий.
Итак, мы понимаем, что надо делать. Накроем отрезок [0,1] множеством Кантора - прямо как в предыдущей заметке, только чуть аккуратнее. Рассмотрим канторовское множество C. Для нас сейчас это множество битовых строчек x=0.x1x2x3... (на практике конечной длины, но теоретически можно и бесконечных). Введем на нем 2-адическую метрику d(x,y) = 2^{-L}, где L - длина максимального общего префикса строчек x и y. Рассмотрим отображение g:C-->[0,1], которое отправляет строчку x в нее же, но рассматриваемую как вещественное число в бесконечной двоичной записи. Отображение g, как нетрудно видеть, не увеличивает расстояния (хотя может сильно сжимать, например, строчки 0.0(1) и 0.1(0) далеки друг от друга в 2-адической метрике, но склеиваются в одно и то же вещественное число).
Для нашей 3d-задачи, стало быть, подойдет отображение f=g^3: C^3 --> [0,1]^3. Мы просто координаты точек нашего орка интерпретируем в 2-адической метрике, и кластеризовать будем именно в этой метрике.
Теперь как это работает на практике. Тут уже пойдет пересказ с использованием слов, более близких к оригинальным работам. Суть в том, чтобы развернуть наше 3-мерное орочье облако точек на прямую. Лю Цысинь оценил бы.
 |
| Никаких ненужных ассоциаций не предполагалось |
Рассмотрим заполняющую пространство кривую, а именно Z-кривую (aka кривая Мортона) h:[0,1]-->[0,1]^3. Она определяется так:
h(0.x1x2x3...)=(0.x1x4x7..., 0.x2x5x8..., 0.x3x6x9...).
Расселили, короче, постояльцев отеля Гильберта по трем отелям. Тут есть некая беда с точками вида 0.A0(1)=0.A1(0): точка одна, а последовательности разные. Из-за этой беды кривая получается разрывной, но вы это и на картинке можете увидеть. Но важно, что мы можем сделать обратное построение: точку
(x,y,z) = (0.x1x2..., 0.y1y2..., 0.z1z2...)
из 3-мерного куба свернуть в одно число 0.x1y1z1x2y2z2... Уплотнили постояльцев трех отелей Гильберта в один отель. Такой способ кодирования трех вещественных каналов в один канал называется кодом Мортона. Это довольно известная вещь, используется в том числе для кодирования адресов в базах данных; да и вообще каждый раз, когда физическая размерность памяти меньше, чем размерность данных, которые вы в нее пытаетесь запихнуть.
На практике у нас все вещественные координаты - это конечные двоичные дроби, поэтому код Мортона каждой точки орка - это конечная битовая строка какой-то фиксированной длины, например, 60 бит. Имея конечный набор битовых строчек, можно построить сжатое префиксное дерево (оно же radix tree, оно же Patricia trie). Вот оно и объявляется искомой иерархической кластеризацией для точек орка.
 |
| Префиксное дерево, спертое из статьи Карраса |
Итак что мы по сути сделали? Мы посмотрели на кривую Мортона как на отображение не из отрезка, а из множества Кантора h:C-->[0,1]^3. Оно мало того что непрерывное (тут нет проблемы с 0.A0(1) и 0.A1(0), это уже разные точки), так еще и липшицево. То есть мы реально наш датасет поднимаем на множество Кантора, ну а ноды префиксного дерева - это и есть кластеры на множестве Кантора.
Если у вас все написанное до сих пор не сложилось в голове воедино, попробуйте решить такое упражнение по элементарной топологии. Докажите, что декартов куб множества Кантора гомеоморфен множеству Кантора. То есть вообще-то не важно, поднимаете ли вы ваш датасет в трехмерное 2-адическое пространство (покоординатно) или в одномерное. Так что эта история про разворачивание 3-мерного пространства на 1-мерную прямую к сути происходящих феноменов отношения реально не имеет: ваша цель - бинарное дерево, а дерево - это нечто 2-адическое, а в адическом пространстве размерности вообще нет. Однако 3d-шники любят везде затирать про упорядочивание объектов вдоль заполняющей кривой. Не ну а чё, звучит фантастично.
А если же написанное все-таки сложилось воедино, то вы имеете полное право мне сказать: "Ба, так очевидно, иерархическая кластеризация - это дерево, а дерево - это ультраметрика, поэтому решить задачу иерархической кластеризации - это и означает удачно подменить заданную метрику ультраметрикой. Так что весь написанный выше текст - это пересыпание слов из миски теор.информатики в миску топологии". Окей, математики обычно тем и занимаются, что сводят содержательные утверждения к банальным тавтологиям. Таков путь.
Вообще говоря, в алгоритме с префиксным деревом тоже нет гарантии, что результат получится сбалансированным. Его еще надо бы оптимизировать, и для этого тоже куча классных идей используется. Важно, однако, что вычисление префиксного дерева от кодов Мортона можно параллелить на видеокарте. Есть такой крутой чувак Теро Каррас, он лет 10 назад очень активно писал статьи на эту тему, см. например https://research.nvidia.com/publication/2012-06_maximizing-parallelism-construction-bvhs-octrees-and-k-d-trees У меня такое впечатление, что текущие успехи Nvidia на ниве рэйтрейсинга во многом основаны на его наработках, - хотя, конечно, понять, какие конкретно алгоритмы там гоняются, нам не дано. Есть открытые презентации, например https://www.anandtech.com/show/13282/nvidia-turing-architecture-deep-dive/5 из которых ясно, что BVH - это действительно ключевая для них тема, их RT-ядра специально заточены именно на работу с иерархией объемов. Если объект в сцене движется, то перестраивать иерархию для него в каждом кадре надо заново: отсюда и возникают очень высокие требования к производительности. Удивительно, однако, что эта байда в итоге заработала!
Даже несмотря на всё написанное, пускать в реальном времени луч для каждого пикселя люди пока не умеют. Пускают только часть лучей, а остальное достраивают с помощью нейросеток. Инференс нейросетки - это умножение матриц, и вот для последнего в RTX-карты насыпали тензорных ядер, которые до этого в игрушках были особо не нужны. Подробности про нейронки я не изучал, однако сомневаюсь, что там что-то геометрически интересное происходит. Если кто-то в теме, change my mind.
Чего по итогу. Рэйтрейсинг - математически интересная тема, и замечательно, что ее стали раскручивать маркетологи. Нужен ли реально этот рейтрейсинг в тех играх, где он есть сейчас, - ну как-то хз. Технология есть, хорошие примеры использования (в смысле лучше чем "зацените нашу мокрую лужу, и черную темноту") пока не созрели. Вот на Portal 3, где фокусы со светом были бы инкорпорированы в игровую механику, я бы посмотрел. Жаль, что игра с таким названием и номером никогда не выйдет.
Комментариев нет:
Отправить комментарий