Повышение эффективности обработки информации является актуальной задачей компьютерной графики. Требования к реалистичности генерируемых изображений постоянно растут, что, в конечном итоге, приводит к росту вычислительных затрат. В то же время, для многих приложений (например, игровых) необходима очень высокая скорость обработки графической информации. Рост производительности оборудования решает эту проблему, как показывает практика, лишь отчасти.
Один из путей повышения эффективности обработки информации -- применение методов, основанных на многомасштабном представлении графических объектов. Многомасштабное представление -- это многослойная структура, первый слой которой содержит информацию, достаточную для грубого (с низким разрешением) приближения объекта; при добавлении информации из каждого последующего слоя степень детализации постепенно увеличивается, пока объект не будет восстановлен полностью (то есть с максимальным разрешением).
С помощью методов, основанных на многомасштабном представлении, может быть решен широкий круг задач синтеза, анализа и обработки графических объектов. Кроме того, эти методы обеспечивают сокращение объемов данных за счет удаления избыточной и несущественной информации, снижая, тем самым, вычислительные затраты на последующую обработку. Алгоритмы обработки многомасштабных представлений, основанные на вейвлет-анализе (или анализе всплесков), достаточно просты и эффективны в реализации.
Разработка многомасштабных методов анализа и синтеза графических объектов разной структуры. Изучение возможностей адаптации этих методов и реализующих их алгоритмов к особенностям конкретных задач и требованиям приложений. Осуществление с помощью указанных методов процессов многоэтапной обработки графической информации.
В работе рассмотрены новые способы решения нескольких задач компьютерной графики, основанные на многомасштабном представлении информации. Предложен метод адаптивной триангуляции на основе дерева вейвлет-преобразований и его модификация для решения задачи расчета и представления освещенности. Предложено применение B-сплайнового вейвлет-преобразования для обработки и отображения линий уровня. Предложена модель описания стохастических текстур, близкая по структуре к разложению сигнала по вейвлет-базису.
Новым является комплексный подход к применению многомасштабных методов для задач, требующих многоэтапной обработки информации. Предлагается использовать одно и то же представление для решения возможно большего числа подзадач. Такой подход упрощает общую процедуру обработки и повышает эффективность ее реализации. Кроме того, становится возможным расширять функциональные возможности метода, внося в него минимум дополнений.
Дополнительно можно отметить, что в процессе разработки модели текстур была сделана заявка на новое, "функциональное" расширение вейвлет-преобразования. (Однако изучение свойств, возможностей, способов реализации и класса приложений такого расширения является предметом самостоятельного исследования).
Разработаны и доведены до реализации методы решения нескольких актуальных задач компьютерной графики. Реализованные алгоритмы удовлетворяют требованиям и ограничениям, которые были сформулированы при постановке задач. В частности, алгоритм генерации и нанесения текстур разрабатывался с учетом возможной аппаратной реализации в графических ускорителях. Метод построения изолиний внедрен в программный продукт, разработанный для геологических расчетов.
Результаты работы докладывались и обсуждались на:
Основные результаты работы изложены в 5-и научных публикациях.
Во введении обосновывается тема диссертации, ее актуальность и практическая значимость, приводится обзор литературы по теме, кратко излагается содержание работы.
Первая глава содержит краткое описание аппарата вейвлет-преобразований одно- и двумерных дискретных сигналов, который применяется при решении задач, рассматриваемых в последующих главах.
Во второй главе описывается алгоритм построения адаптивных треугольных сеток для представления графических объектов, параметризуемых на плоскости. Алгоритм основан на древовидной структуре многомасштабного анализа информации. Рассматривается модификация этого алгоритма для приложения -- реконструкции функции освещенности по данным, полученным с помощью прямой трассировки лучей методом Монте-Карло.
В третьей главе обсуждается применение вейвлет-анализа для решения задачи построения линий уровня (изолиний) на плоскости, рассматриваются вопросы сглаживания линий, масштабирования и вывода на графическое устройство с заданными характеристиками.
В четвертой главе рассматривается многомасштабная модель для описания некоторого класса стохастических текстур. С помощью этой модели возможно создание как реалистических, так и "абстрактных" изображений-текстур. Алгоритмы, основанные на представленной модели, обеспечивают генерацию и нанесение текстур в реальном времени и допускают аппаратную реализацию.
В заключении формулируются основные результаты работы.
Приложение содержит справочную информацию по основам теории вейвлет-анализа -- многомасштабному анализу и вейвлет-преобразованиям непрерывных сигналов.