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

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

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

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

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

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

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

Обсудить
«Для них история — игрушка с лозунгом "Вперед! На Берлин!"»
Почему школьник из Нового Уренгоя был прав, пожалев солдат вермахта
Дошел до Берлина
Школьник пожалел солдата вермахта, а его затравили всей Россией
Сирийский сбор
Путин, Эрдоган и Рухани обсудили будущее
Из плоти и стали
Что мы не знаем о ветеранах Афгана и Чечни
Сулейман КеримовЛазурно: российского миллиардера задержали в Ницце
Сулеймана Керимова подозревают в отмывании миллионов евро
Моя семья
Легендарный маньяк и его культ кровавых убийц держали в страхе всю Америку
Судьба генерала: Ратко Младич умрет в тюрьме
Он убивал мусульман тысячами и не щадил даже детей
Кровавая ривьера
Франция отстреливает врагов по всему миру, пока никто не видит
«Как назло у нас есть великое прошлое»
Почему россияне не принимают себя
«Происходящее — форма женского освобождения»
Йоаким Триер о мистической драме про лесбийскую любовь и Бога
Признак оперы
Как Дмитрий Хворостовский стал главным оперным певцом России
Циркуль в глаз
Судьба еврейского художника: от украинских сказок до нацистской выставки
Сомнительное удовольствие
Библейский потоп, ужасные казни и другие забавы в самых странных парках мира
«Не надо меня спасать»
Звездный путешественник нашел тайное племя головорезов, ввязался в войну и выжил
«Девочку из России тут никто не ждет»
История сибирячки, перебравшейся в Нидерланды
Эмилио Эстевес в роли Билли КидаМалыш на миллион
Легендарный головорез Дикого Запада передал привет из прошлого
Что. Вы. Наделали
Как мы потеряли идеальный Porsche и снова его нашли
«Американец», который смог
Самые невероятные версии Chevrolet Corvette, от которых сносит крышу
Мистер Спок
Мы пощупали новейший Aston Martin Vantage и делимся первыми впечатлениями
Из бананов и палок
Что получается, когда машины пытаются делать в Уганде, Кении и других странах
Ловушка для планктона
Тест: Какой офис идеально вам подходит
Это чисто Питер
Сколько стоят квартиры в воспетом Шнуром городе на Неве
Берите две
Пять стран, где ипотеку дают под смешной процент
«Моя бывшая живет на помойке»
Москвич сделал из жены бомжа, и ему не стыдно