Специалистами университета Южной Каролины (USC) разработан новый алгоритм сжатия крупных файлов 3D-изображений. Новая технология найдет применение в компьютерной анимации, видеоиграх и в цифровой графике вообще, добавляя реалистичности трехмерным объектам.
Авторы нового алгоритма, названного "Вариационное приближение формы" (Variational Shape Approximation) - доцент инженерной школы Витебри университета Южной Каролины Матье Дебран (Mathieu Desbrun) и двое его коллег, сообщает "CNews.ru".
Алгоритм позволяет получать высокоточные "сетчатые" модели объемных объектов, занимающие на порядок меньший объем, чем существующие, но при этом полностью совместимые с уже имеющимися технологиями отображения и обработки трехмерных цифровых изображений.
Как правило, информация о форме трехмерного объекта передается в виде сети из треугольников. При этом для "естественного" представления формы объекта число элементов трехмерного изображения оказывается очень большим. Обработка таких изображений требует больших затрат машинных ресурсов и времени. При этом треугольниками заполняется вся поверхность - даже сравнительно плоские ее участки.
Дебран предложил упростить структуру сети, по возможности, в пределах допустимой точности, объединяя треугольники и заменяя их другими плоскими многоугольниками. При этом плоские элементы могут быть заменены одним многоугольником, в то время как участки с большой кривизной требует представления с большим числом элементов. Для этого используется процедура, известная как "кластеризация Ллойда" (Lloyd Clustering) по имени предложившего ее в 1959 году Стюарта Ллойда. С помощью этого метода алгоритм Дебрана сегментирует объект на непересекающиеся области, после чего проверяет, удовлетворяет ли такое представление объекта требуемой точности, и оптимизирует сегментацию с помощью небольшого числа итераций.
Алгоритм Дебрана открывает новые горизонты компьютерной графики. В частности, становится возможным детализировать с высокой точностью отдельные участки поверхности объекта - например, глаза, в то время как другие черты лица останутся прорисованными относительно грубо.
