Компьютерные игры станут реалистичнее
Специалистами университета Южной Каролины (USC) разработан новый алгоритм сжатия крупных файлов 3Алгоритм позволяет получать высокоточные «сетчатые» модели объемных объектов, занимающие на порядок меньший объем, чем существующие, но при этом полностью совместимые с уже имеющимися технологиями отображения и обработки трехмерных цифровых изображений.
Как правило, информация о форме трехмерного объекта передается в виде сети из треугольников. При этом для «естественного» представления формы объекта число элементов трехмерного изображения оказывается очень большим. Обработка таких изображений требует больших затрат машинных ресурсов и времени. При этом треугольниками заполняется вся поверхность даже сравнительно плоские ее участки.
Дебран предложил упростить структуру сети, по возможности, в пределах допустимой точности, объединяя треугольники и заменяя их другими плоскими многоугольниками. При этом плоские элементы могут быть заменены одним многоугольником, в то время как участки с большой кривизной требуют представления с большим числом элементов. Для этого используется процедура, известная как «кластеризация Ллойда» (Lloyd Clustering), по имени предложившего ее в 1959 году Стюарта Ллойда. С помощью этого метода алгоритм Дебрана сегментирует объект на непересекающиеся области, после чего проверяет, удовлетворяет ли такое представление объекта требуемой точности, и оптимизирует сегментацию с помощью небольшого числа итераций.
Алгоритм Дебрана открывает новые горизонты компьютерной графики. В частности, становится возможным детализировать с высокой точностью отдельные участки поверхности объекта например, глаза, в то время как другие черты лица останутся прорисованными относительно грубо.