Методы удаления невидимых поверхностей в задачах визуализации трехмерных сцен большой сложности

В последнее время все большее распространение получают различные системы трехмерной визуализации сложных сцен, позволяющие в реальном времени изменять их конфигурацию. Подобные системы активно используются в компьютерных играх, различных симуляторах, тренажерах, при проектировании архитектурных сооружений и т. п. Характерной особенностью используемых сцен является их высокая сложность — количество граней в сценах может составлять сотни тысяч или даже миллионы. Прослеживается следующая тенденция — сложность сцен растет заметно более высокими темпами, чем мощность графических ускорителей. При этом сложность сцены может быть столь велика, что ее нельзя целиком загрузить в оперативную память. В этом случае нужно обеспечить возможность динамической загрузки видимых частей сцены и удаления из оперативной памяти тех частей, которые в ближайшее время видны не будут. Часто возникает потребность динамического изменения сцены, поддержки различных специальных эффектов, используются специальные процедуры закрашивания и т. п. [10,11]. Нередко сцена состоит из различных фрагментов, имеющих разнородную внутреннюю структуру и разную природу.

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

Мы будем рассматривать следующую задачу: пусть в трехмерном пространстве заданы набор из п выпуклых взаимонепересекающихся граней Р1, Р1,., Рп, положение и ориентация наблюдателя. Будем предполагать, что количество объектов сцены, видимых из любого положения, существенно меньше общего числа объектов в сцене при любой ориентации наблюдателя.

В качестве области видимости наблюдателя (области пространства, объекты из которой только и могут быть видимыми) будем использовать пирамиду V с вершиной в положении наблюдателя. Обычно такая пирамида обрезается по ближней и дальней плоскостям отсечения. Лежащая (хотя бы частично) в пирамиде V грань Р, называется видимой для данного положения и данной ориентации наблюдателя, если на ней существует (хотя бы одна) точка А, лежащая в V и такая, что отрезок, соединяющий положение наблюдателя и эту точку, не пересекает ни одну из граней Р1, Р2,.Р1{, Рм,., Рп. Сцена называется невырожденной, если для любого положения наблюдателя и любой его ориентации количество видимых граней составляет о (п).

Считая сцену невырожденной, требуется определить множество видимых граней для данных положения и ориентации наблюдателя.

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

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

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

Цель работы.

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

Научная новизна работы.

В работе предложены новые эффективные методы определения видимости в сложных полигональных сценах:

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

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

Практическая значимость.

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

Апробация работы и публикации.

Основные результаты диссертации представлены в работах [1,2,3,4]. Отдельные результаты работы были доложены на международной конференции ГрафиКон-98 (Москва, 1998 г.) и на семинаре «Компьютерная графика» на факультете ВМиК (руководитель: проф. Шикин Е.В.), на семинаре по геометрии в целом на механико-математическом факультете МГУ (руководители: проф. Сабитов И. Х, ст.н.с. Розендорн Э.Р.).

Содержание работы.

Диссертационная работа состоит из введения и трех глав.

1. Разработанный метод иерархического 8-буфера является эффективным как по времени работы, так и по требуемой оперативной памяти. Применение данного метода позволяет определять видимость в широком классе сложных трехмерных сцен в реальном времени без их специальной ручной обработки. Данный метод пригоден для использования в различных системах трехмерной визуализации сложных сцен в реальном времени.2. Разработанный метод агрегатных сцен является эффективным методом определения видимости в составных трехмерных сценах как по времени работы, таки по требуемой оперативной памяти. Применение данного метода позволяет легко строить сложные сцены из отдельных фрагментов и учитывать структуру этих фрагментов для более точного определения видимости в реальном времени. Данный метод пригоден для использования в различных системах трехмерной визуализации сложных сцен в реальном времени.