Теорему Нэша приспособили для трехмерной графики

Ученые из Техасского университета придумали алгоритм полигонального представления заданной поверхности, который использует теорему Нэша. Свои результаты ученые представили на конференции SIGGRAPH. Препринт статьи доступен (pdf) на сайте мероприятия.

В компьютерной графике чаще всего объекты представляются в виде набора полигонов - двумерных треугольников, которые прилегают друг к другу сторонами. Чем сильнее искривлена фигура, которую надо изобразить, тем больше полигонов нужно. При этом, если объект достаточно сложен (состоит как из ровных, так и из изогнутых кусков), то для экономии вычислительных мощностей при моделировании разумно на кривые куски тратить больше треугольников меньшего размера, чем на ровные куски. Такое моделирование называется анизотропным.

Главная трудность, которую решали ученые из Техасского университета, была в автоматизации процесса разбиения поверхности на треугольники (в сложных моделях такое обычно делается руками и называется «созданием меша»). Для этого они рассмотрели поверхность с заданной на ней римановой метрикой, то есть правилом, позволяющим считать длины векторов, кривых и углы между ними.

К этой абстрактной поверхности ученые применили теорему, доказанную Джоном Нэшем (известном широкой публике, среди прочего, в качестве главного героя фильма «Игры разума») в 1954 году. Она утверждает, что всякая абстрактная поверхность может быть представлена в виде настоящей поверхности в пространстве достаточно большой размерности так, что длины векторов, кривых и углы на поверхности будут совпадать с длинами векторов, кривых и углами, посчитанными в этом пространстве. Более того, работы Нэша позволяют получить алгоритм построения такого вложения.

Вложив поверхность в достаточно большое пространство, ученые разбили ее на полигоны равномерной сеткой, используя ряд хорошо известных методов. Затем поверхность была спроектирована на «рабочее» пространство - двумерное или трехмерное. По словам ученых, несмотря на кажущуюся сложность их методологии, предложенный алгоритм позволяет получать анизотропное разбиение поверхности быстрее своих аналогов. Авторы работы надеются, что новый алгоритм найдет применение в 3D графике и при моделировании сложных физических процессов.