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

Введение.

Глава 1. Основные методы удаления невидимых линии и поверхностей

1.1 Основные понятия.

1.2 Основные методы оптимизации.

1.3 Метод трассировки лучей.

1.4 Метод z-буфера.

1.5 Методы упорядочения.

1.6 Метод построчного сканирования.

1.7 Метод Варнака.

1.8 Метод Вейлера-Эйзертона.

1.9 Специальные методы оптимизации.

1.10 Работа со сценами большой сложности.

1.11 Метод иерархического z-буфера.

1.12 Иерархическое наложение полигонов с использованием масок закрытия.

1.13 Метод иерархических карт загораживания.

1.14 Подход, использованный в системе Crystal Space.

1.15 Система UMBRA.

1.16 Требования к методу удаления невидимых поверхностей.

Глава 2. Метод л- -буфера. Иерархический л' -буфер. Основные геометрические свойства s-буфера.

Глава 3. Метод агрегатных сцен.

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

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

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

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

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

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

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

1. Боресков А.В. Метод иерархического s-буфера.// Программирование. 1998 N4 с 77-80

2. Боресков А.В. Использование порталов для создания агрегатных сцен // Труды конференции ГрафиКон 98

3. Боресков А.В. О некоторых геометрических свойствах s-буфера.// Программирование. 1999 N3 с 67-69

4. Боресков А.В. Использование порталов для создания агрегатных сцен // Вестник МГУ 2000, N 1

5. Шикин Е.В., Боресков А.В. Компьютерная графика. Динамика, реалистические изображения. // М, Диалог-МИФИ, 1995

6. Шикин Е.В., Боресков А.В. Компьютерная графика. Полигональные моделию // М., Диалог-МИФИ, 2000

7. Э. Гамма, Р. Хелм, Р. Джонсон, Дж. Влиссидес. Приемы объектно-ориентированного проектирования. Паттерны проектирования. // Санкт-Петербург, Изд-во Питер, 20018. www.umbra.fi.9. http://crystal.sourceforge .net.

8. Tomas Moller, Eric Haines. Real-Time Rendering. // A.K. Peters, 1999

9. David H. Eberly. 3D Game Endine Design. // Morgan Kaufmaim Publishers, 2001

10. Timo Aila. Surrender umbra: A visibility determination framework for dynamic environments. Master's thesis, Helsinki University of Technology, October 2000.

11. Loren Carpenter. The a-buffer, an antialiased hidden surface method. // SIGGRAPH '84 Proceedings, vol 18, pages 103-108

12. James Clark. Hierarchical geometric model for visible surface algorithms. // Communications of ACM, 19(10):547-554, October 1976

13. Foley, van Dam,. Feiner, and Hughes. Computer Graphics: Principles and Practice. // Addison-Wesley, second edition, 1990

14. Andrey Glassner. Space subdivision for fast ray tracing. // IEEE Computer Graphics and Applications, 1984

15. Ned Greene. Hierarchical polygon tiling with coverage masks. // Proceedings of SIGGRAPH'96, pages 65-74, August 1996.

16. Ned Greene and Michael Kass. Hierarchical z-buffer visibility. // Proceedings of SIGGRAPH'93, pages 231-240,1993

17. Ivan Sutherland, Robert Sproull, and Robert Schumacher. A characterization of ten hidden-surface algorithms. //ACM Computer Surverys, 6, 1974

18. Seth Teller. Visibility Computations in Densly Occluded Polyhedral Environments. PhD thesis, CS Division, UC Berkeley, October 1992, Tech Report UCB/CSD-92-708

19. Seth Teller and Carlo Sequin. Visibility preprocessing for interactive walkthoughs. // Computer Garphics (Proceedings of SIGGRAPH'91), 25(4):61-69, July 1991

20. John Warnock. A hidden surface algorithm for computer generated half-tone pictures. // Technical Report RADC-TR-69-249, Dept. Of CS University of Uta, June 1969

21. Kevin Weiler and Peter Atherton. Hidden surface removal using polygon area sorting. // Proceedings of SIGGRAPH'77, 11(2):214-222, July 1977

22. Hansong Zhang. Effective Occlusion Culling for Interactive Display of Arbitrary Models. //PhD thesis, Department of Computer Science, University of North Carolina at Chapel Hill, 1998

23. Hansong Zhang, Dinesh Manocha, Thomas Hudson and Kenneth E. Holl III. Visibility culling using hiereachical occlusion maps // Proceedings of SIGGRAPH'97, pages 77-88, August 1997