Современные алгоритмы позволяют сравнительно просто сжимать цифровой звук, графику и видео, однако сложные файлы 3-мерных объектов все еще вызывают проблемы при сжатии. И вот недавно Мэтью Дезбран (Mathieu Desbrun) из Университета Южной Калифорнии разработал мощный алгоритм сжатия больших файлов, представляющих 3-мерные формы, используемые в мультипликации, видеоиграх и других видах компьютерной графики. Свое решение он планирует представить на летней сессии SIGGRAPH'2004 (siggraph.org/s2004), которая состоится в Лос-Анджелесе 8-12 августа.

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

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

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

Дезбран попытался обойти трудности, использовав открытый в 1959 году метод "кластеризации Ллойда". В новом алгоритме он используется для автоматической сегментации объекта на группы не перекрывающихся связанных областей. Затем эти альтернативные большие зоны, называемые "прокси" ("proxies", т.е. приближения), проверяются на то, как хорошо они соответствуют объекту, и последовательно оптимизируются за небольшое количество итераций. При этом в процессе оптимизации можно управлять результатом, например, в соответствии с замыслом художника или мультипликатора.

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

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

Сергей САНЬКО

Пресс-релиз: usc.edu/uscnews/story.php?id=10311.