16+
ComputerPrice
НА ГЛАВНУЮ СТАТЬИ НОВОСТИ О НАС




Яндекс цитирования


Версия для печати

Модуль поиска не установлен.

Алгоритмическая графика

19.05.2004

Алексей Калютов

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

Американская ассоциация SIGGRAPH (аббревиатура SIG расшифровывается как объединение (группа) по специализации) каждый год публикует объемистые Труды, которые включают доклады по наиболее передовым и перспективным разработкам и направлениям исследований. Несмотря на то что конференции проходят в США, эта ассоциация является последовательно интернациональной и объединяет специалистов из различных стран мира. Тематика докладов чрезвычайно разнородная и охватывает весь круг вопросов, связанных с компьютерной графикой как таковой, причём эта тенденция сохраняется почти с самого начала проведения конференций. Но всё же в эволюции тем можно отыскать определённые закономерности. Первое, что бросается в глаза, - это увеличение удельной доли докладов, посвящённых дальнейшей, более детальной разработке задач, которые в подавляющем большинстве были сформулированы в промежуток времени 1975-1990 гг. (см. таблицу 1 ). Это ясно свидетельствует о том, что многие старые проблемы всё ещё не имеют окончательного решения.

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

Почему именно имитация реальных объектов и явлений, а не их моделирование в компьютерной графике является более плодотворным методом решения разнообразных задач?

Рис. 1. Фрактальный папоротник

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

С другой стороны, для компьютерной графики прямое моделирование (то есть численное решение уравнений) является расточительным с точки зрения вычислительных затрат, ведь всё, что нужно получить, это изображение на экране монитора. Иными словами, компьютерная графика допускает подмену физически корректных моделей явлений и объектов их достаточно реалистическим имитациями. Создание, программирование поведения таких имитаций является сегодня одним из основных объектов внимания алгоритмической графики (algorithmic graphics, programmed graphics - отдельная ветвь компьютерной графики, в которой графический объект - изображения, 3D-модели и проч. - генерируется исключительно компьютером). Вообще говоря, имитация не обязательно должна соответствовать чему-нибудь реальному; в таком случае генерируемые с её помощью изображения относятся скорее к сфере искусства.

Следует отметить, что значимость алгоритмической графики выходит далеко за пределы собственно визуализации различных объектов: она может помочь в более глубоком понимании действительных законов, лежащих в основе того или иного явления. Например, алгоритм, по которому генерируется лист папоротника (рис. 1), неявно заключает в себе информацию о свойствах реального растения - прототипа.

Алгоритмы и технологии

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

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

Рис. 2. Вода, льющаяся в стакан

Симуляция жидкостей
(Полное описание алгоритма в: Matthias Muller, David Charypar and Markus Gross. Particle-Based Fluid Simulation for Interactive Applications

http://graphics.ethz.ch/Downloads/Publications/Papers/2003/mue03b/p_Mue03b.pdf)

Алгоритмы имитации движения воды в реках, ручьях, водопадах, водоворотах, дождях или же в обыкновенном стакане лишь отчасти базируются на традиционной математической модели жидкости. В классической гидродинамике движение жидкости наиболее точно описывается уравнением Навье - Стокса, но его структура для любого указанного выше случая будет чрезвычайно сложной, и численное решение займёт слишком много времени.

В основе используемой имитации лежит технология, получившая название гидродинамики сглаженных частиц (Smoothed Particle Hydrodynamics, SPH). Первоначально она разрабатывалась для нужд теоретической астрофизики, но позднее нашла совершенно неожиданное применение в качестве эффективного метода решения задач газо- и гидродинамики (SPH-метод интенсивно разрабатывается с начала 90-х гг. с целью использования его вместо традиционных точных, но медленных сеточных методов). Динамика жидкости моделируется системой, состоящей из множества частиц, а её свободная поверхность (т.е. поверхность раздела двух сред - жидкой и газообразной) - сглаженной поверхностью, проходящей через центры граничных частиц. Во всех остальных точках свойства жидкости аппроксимируются с помощью функции специального вида, которая учитывает вклад от каждой из частиц, составляющих систему. В имитации используются некоторые свойства реальных жидкостей, в частности, её несжимаемость и непрерывность (в рамках этой модели это означает, что расстояние между соседними частицами не может сильно отклоняться от некоторой средней величины), стремление минимизировать свою поверхность (это свойство естественным образом реализуется в данной имитации) и др. Как правило, система, состоящая из нескольких тысяч частиц, уже достаточно реалистично имитирует динамику жидкости, вплоть до таких моментов, как образование отдельных капель при слишком сильных ударах (рис. 2).

Почему такая система может служить для имитации различных жидкостей? Ответ заключается в наличии у подобных систем очень большого числа степеней свободы (пропорциональном количеству частиц) или, иными словами, в её возможности в нормальных условиях принимать практически любую форму. А это как раз и является одним из основных свойств любого жидкого тела.

Таблица 2. Простой вариант правил перехода

Симуляция облаков
(Полное описание алгоритма в: Yoshinori Dobashi, Kazufumi Kaneda, Hideo Yamashita, Tsuyoshi Okita, Tomoyuki Nishita. A Simple, Efficient Method for Realistic Animation of Clouds

http://nis-lab.is.s.u-tokyo.ac.jp/~nis/cdrom/sig00_cloud.pdf )

Алгоритм основан на концепции клеточных автоматов - воображаемых машин, которые в докомпьютерную эпоху (в первой половине ХХ в.) использовались для демонстрации работы того или иного алгоритма.

Пространство, которое предполагается "заполнить" облаками, разбивается на отдельные объемы - вокселы. Каждый воксел является элементарной клеткой, а вся совокупность клеток образует клеточный автомат. Каждой клетке ставятся в соответствие три логические переменные - влажность (hum), наличие тумана (cld) и активизация перехода (act), каждая из которых может принимать значения 0 или 1. Так, hum = 1 означает, что влажность воздуха в соответствующем вокселе достигла точки насыщения, т.е. величины, достаточной для конденсации воды в капельки жидкости; act = 1 - что в данном объеме происходит конденсация воды; cld = 1 - что в данном объеме есть туман. Эволюция облака симулируется путём задания некоторых простых правил перехода, в соответствии с которыми нужно изменять на каждом шаге значения указанных выше переменных. Правила перехода имитируют воздействие на облако ветра, поднимающегося от земли теплого воздуха и других факторов. На каждом шаге "облачное пространство" подвергается рендерингу, который осуществляется в два этапа: на первом вычисляется интенсивность света от внешних источников (Солнца, Луны и т.п.) в центре каждого воксела, на втором происходит собственно рендеринг изображения - каждый воксел в свою очередь заменяется сферическим объемом некоторого заданного радиуса, причем яркость всех точек этого объема интерполируется в зависимости от значения переменной cld для него (если cld = 1, т. е. объем заполнен туманом, она равномерно уменьшается к краю).

Один из возможных вариантов правил перехода представлен в Таблице 2. А вообще эти правила могут задаваться произвольным образом и определять, в свою очередь, разнообразные эффекты, типа постепенного возникновения или исчезновения облаков и т.п.

Перед началом работы алгоритма значения переменных hum и act определяются случайным образом, а cld полагается равным нулю. Другие подробности алгоритма можно найти непосредственно в оригинальной статье (см. рис. 3).

Рис. 3. Облачный покров, созданный с помощью описанного выше метода

Симуляция песчаных гряд и барханов
(Полное описание алгоритма в: Koichi Onoue, Tomoyuki Nishita. A Method for Modeling and Rendering Dunes with Wind-ripples

http://nis-lab.is.s.u-tokyo.ac.jp/~nis/cdrom/pg/onoue.pdf )

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

Волнистая поверхность песчаных гряд имитируется с помощью карты высот, которая генерируется следующим образом. Исходная карта высот заполняется случайными значениями (эти значения суть относительная высота песчаной гряды в данной точке). Перенос отдельных песчинок имитируется путём уменьшения значения высоты в соответствующей точке карты (песчинка поднялась в воздух) и его увеличением в некоторой другой точке (месте "падения" песчинки). Такие вычисления проводятся для каждой точки карты высот, и весь процесс повторяется до тех пор, пока не стабилизируется искомый рельеф "песчаной ряби" (этот процесс является сходящимся, т.е. рано или поздно приводит к какому-то результату). Форма барханов имитируется аналогичным образом. Отличие состоит только в выборе другой функции, определяющей "дальность полёта" песчинки: очевидно, что это расстояние будет больше с наветренной стороны барханов, чем с подветренной (см. рис. 4).

Рис. 4. Пустынный ландшафт, сгенерированный программой, реализующей изложенный выше алгоритм

Рис. 5

Симуляция подводного освещения
(Полное описание алгоритма в: Kei Iwasaki, Yoshinori Dobashi, Tomoyuki Nishita. Efficient Rendering of Optical Effects within Water Using Graphics Hardware

http://nis-lab.is.s.u-tokyo.ac.jp/~nis/cdrom/pg/pg2001_iwa.pdf )

Основная особенность подводного освещения заключается в своеобразной игре света на дне и на любых погружённых в воду объектах, возникающей из-за динамичного появления и исчезновения областей концентрации светового излучения (так называемых каустик света). Кроме того, следует учитывать тот факт, что в морской воде происходит очень сильное рассеяние света, обуславливающее особый цвет воды и "проявление" лучей света в виде белесых полос.

Основная идея, положенная в основу имитации подводного освещения, заключается в разбиении всего подводного пространства на большое число треугольных призм (в оригинальной работе они называются объемами освещённости - illumination volume), боковые рёбра которых определяются как продолжения преломленных на участке поверхности воды лучей от внешнего источника света (см. рис. 5). Затем каждая полученная таким образом призма разбивается на несколько субобъемов (sub-volume) меньшего размера, а те в свою очередь - на три треугольные пирамиды. Таким образом, исходная призма оказывается разделённой на множество отдельных пирамид. Такое разделение выполняется для того, чтобы в конечном итоге эффективнее применить стандартные функции 3D-графики для Гуро-интерполяции освещённости каждой точки поверхности пирамид. Разбиение на субобъемы продиктовано соображениями повышения реалистичности конечного результата: интерполяция освещённостей по методу Гуро является линейной, в то время как ослабление интенсивности света в воде имеет экспоненциальный характер.

В представленной модели рассеянный в воде свет имитируется гранями отдельных пирамид, а каустики света получаются как "побочный эффект" благодаря пересечению объемов освещённости: очевидно, что все точки, принадлежащие одновременно нескольким световым объемам, будут иметь повышенную яркость. Достоинством данного метода является не только чрезвычайно высокая реалистичность подводного освещения, но и возможность проводить рендеринг в реальном времени (в основном благодаря тому, что алгоритм почти полностью легко осуществить с помощью стандартных функций, которые поддерживаются большинством современных графических ускорителей). Для сравнения нужно отметить, что рендеринг сцены, подобной представленной на рис. 6, с использованием алгоритмов Ray Tracing & Radiosity требует на несколько порядков больше времени и ресурсов.

Рис. 6. Пример подводной сцены

Обзор ресурсов в Интернете

Далее приведён краткий обзор некоторых сайтов в Интернете, где можно найти разнообразную информацию об алгоритмической графике. Конечно, следует иметь в виду, что полное описание всех ресурсов, посвящённых данной тематике, доступных через Глобальную сеть, во много раз превысило бы размеры этой статьи.

http://www.siggraph.org

Сайт ассоциации SIGGRAPH. Ссылки на полнотекстовые версии некоторых представленных на конференциях работ можно найти на http://cglab.cs.nthu.edu.tw/chinese/member/hks.html и http://grail.cs.washington.edu/pub/abstracts.html, а также - с большой вероятностью - на персональных страничках авторов.

http://www.efg2.com/Lab/Library/SimulationAndModeling.htm

Ресурс, посвящённый моделированию и использованию симуляций в самых различных областях науки и техники.

http://www.cfdreview.com/

Ресурс, посвящённый вычислительной гидродинамике: новости, статьи, ссылки на другие ресурсы.

http://www.jnani.org/mrking/writings/

На сайте представлены статьи Майка Кинга; в некоторых из них рассматриваются методы работы различных художников - "алгоритмистов", использующих компьютер для создания своих произведений (Programmed Graphics in Computer Art and Animation); освещаются некоторые алгоритмы имитации природных объектов и явлений (Manipulating Parameters for Algorithmic Image Generation).

http://ojuice.net/

Ресурс, посвящённый такому любопытному и интересному явлению, как демо-мейкингу, основанному на программировании и графике. Многие демонстрации базируются на весьма неординарных алгоритмах. По приведённому выше адресу можно ознакомиться с дополнительной информацией по данному вопросу, а свежие демонстрации всегда можно найти на ftp.scene.org.

http://www.lactamme.polytechnique.fr/Mosaic/escripteurs/AVirtualSpaceTimeTravelMachine.Ang.FV.html

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

http://www.planetside.co.uk/

Одна из программ, применяемых для автоматической генерации трёхмерных ландшафтов - Terragen, - может служить примером использования фрактальных алгоритмов для создания земной и водной поверхностей, экосистем и проч. Программы такого рода (здесь следует упомянуть профессиональный графический пакет Animatek World Builder, http://www.animatek.com/) постоянно совершенствуются, и в будущие версии наверняка будут включены технологии, описанные в настоящей статье.



статьи
статьи
 / 
новости
новости
 / 
контакты
контакты