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

Примеры анизотропного разбиения поверхностей
Примеры анизотропного разбиения поверхностей

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

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

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

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

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

Обсудить
Наука и техника00:0225 сентября

Посыпали пеплом

Необратимая катастрофа навсегда изменит жизнь на Земле
01:4820 сентября
Ангела Меркель Без свастик
Немецкие ультраправые впервые с 1945 года оказались у власти
Свобода для скотовода
В лучшем городе США изгнали политиков с полицейскими и погрязли в хаосе
Падший дьявол
Неуловимый наркобарон основал культ убийц и варил человеческие мозги в котле
Виталик БутеринСюрприз от Виталика
Кто убьет традиционную экономику
День пенсионного единства
ПФР поднимает уровень знаний о пенсионной системе по всей России
Пирамида изгоев
Кому выгодна смерть биткоина
Жить будем
Россияне обнищают, зато не умрут с голода
Классическая история
Душевные ролики про самые красивые спорткары XX века
Машины, которые не боятся столкновений
Забытые концепт-кары: ударопрочные «Фиаты»
Побег в будущее
Говорящие рули и электрические ретрокары: будущее по версии Jaguar Land Rover
Mazda CX-5 и Renault Koleos против VW Tiguan и Skoda Kodiaq
Четыре новых кроссовера. Один тест-драйв. Ну, вы поняли