Разработка и исследование методов определения видимости полигонов в реальном времени при отрисовке трехмерных объектов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Надолинский, Никита Александрович

• Надолинский, Никита Александрович
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Надолинский, Никита Александрович

ВВЕДЕНИЕ.

1. ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ ОПРЕДЕЛЕНИЯ ВИДИМОСТИ ПОЛИГОНОВ В РЕАЛЬНОМ ВРЕМЕНИ ПРИ ОТРИСОВКЕ ТРЕХМЕРНЫХ ОБЪЕКТОВ.И

1.1. Анализ характеристик методов удаления невидимых поверхностей.

1.1.1. Использование когерентных связей.

1.1.2. Соотношение визуализируемой части геометрии к общей.

1.1.3. Количество перекрытий.

1.2. Методы оптимизации.

1.2.1. Отсечение нелицевых граней.

1.2.2. Ограничивающие тела.

1.2.3. Разбиение пространства.!.

1.2.4. Иерархические структуры.

1.3. Удаление невидимых поверхностей.

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

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

1.3.3. Сортировка по глубине. Метод художника.

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

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

1.5. Выводы.

2. ОРГАНИЗАЦИЯ ПОЛИГОНОВ В ОБЪЕКТНОМ ПРОСТРАНСТВЕ.

2.1. Описание метода двоичного разбиения пространства.

2.2. Построение дерева на основе пространственного разбиения граней.

2.3. Механизм обхода двоичного дерева полигонов.

2.4. Пространственное отсечение задних поверхностей и групп поверхностей.

2.6. Механизм отображения двоичного дерева полигонов.

2.7. Выводы.

3. ОРГАНИЗАЦИЯ ПОЛИГОНОВ В ОТОБРАЖАЕМОМ ПРОСТРАНСТВЕ.

3.1. Описание метода двухпроходной растеризации на основе иерархического тайлинга полигонов.

3.2. Механизм бинарных масок.

3.3. Механизм отсечений по границам экрана.

3.4. Механизм растеризации.

3.5. Механизм текстурирования.

3.6. Выводы.

4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МОДЕЛИ СИСТЕМЫ ОПРЕДЕЛЕНИЯ ВИДИМОСТИ ПОЛИГОНОВ, ЕЕ ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ И СРАВНЕНИЕ С АНАЛОГАМИ.

4.1. Программные оптимизации.

4.2. Экспериментальное исследование программной модели, сравнение с аналогами.

4.3. Выводы.

Введение диссертации (часть автореферата) на тему «Разработка и исследование методов определения видимости полигонов в реальном времени при отрисовке трехмерных объектов»

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

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

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

Актуальность темы

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

Около 5 лет назад появился рынок мобильных компьютеров (КПК), которые также нуждаются в отрисовке больших объемов данных. Здесь дела обстоят гораздо хуже, чем на настольных системах, потому как в КПК нет геометрических процессоров. Опыт показывает, что в ближайшее время полноценные геометрические процессоры (GPU - geometry processing unit) с архитектурой и возможностями, аналогичными nVidia GeForce3Ti, с vs 1.0 и ps 1.0 вряд ли появится в мобильных устройствах, из-за проблем с энергопотреблением и выделением тепла. Следовательно, сейчас трехмерная графика реального времени на КПК практически не развита, по сравнению с настольными системами.

Таким образом, развитие трехмерной графики реального времени, за счет средств центрального процессора (CPU - central processing unit) на платформе мобильных компьютеров, с возможностью отрисовки больших объемов данных, является очень актуальной задачей. Появление такого метода может вывести платформу мобильных компьютеров на совершенно новый уровень задач, способствовать развитию трехмерных ГИС, игровых, а также любых других приложений, использующих вывод на экран сложных геометрических данных.

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

Целью работы является разработка и исследование методов удаления невидимых поверхностей, позволяющих отображать сложные трехмерные сцены на платформе мобильных компьютеров, средствами CPU.

Исходя из основной дели данной работы, определяется перечень основных задач:

1. Разработка целочисленного метода организации геометрических данных в объектном пространстве на основе двоичных деревьев.

2. Разработка метода двухпроходного расчета видимости частей изображения на основе иерархического тайлинга.

3. Разработка нового метода расчета видимости треугольников на основе бинарного маскирования.

4. Разработка целочисленного метода растеризации и текстурирования треугольников с учетом особенностей архитектуры центрального процессора мобильных устройств.

5. Экспериментальные оценки основных характеристик программной модели системы отрисовки геометрических данных в сравнении с существующими аналогами.

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

Научная новизна диссертационной работы заключается в следующем:

1. Разработан метод определения видимости и масштабной отбраковки полигонов в объектном пространстве на основе двоичных деревьев

2. Впервые разработан метод определения видимости треугольников в отображаемом пространстве на основе иерархического тайлинга с применением бинарного маскирования участков изображения.

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

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

Практическая ценность работы

Практическая значимость результатов диссертации заключается в следующем:

1. Разработанный метод удаления невидимых поверхностей может быть использован для отображения сложных трехмерных геометрических данных в реальном времени.

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

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

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

2. Метод организации геометрических данных в объектном пространстве на основе бинарных деревьев. Масштабная отбраковка полигонов.

3. Метод определение видимости полигонов в отображаемом пространстве на основе иерархического тайлинга с использованием бинарного маскирования участков изображения.

4. Целочисленный метод растеризации и текстурирования треугольников с учетом особенностей архитектуры центрального процессора мобильных устройств.

5. Экспериментальные оценки основных характеристик программной модели системы отрисовки геометрических данных в сравнении с существующими аналогами.

Использование результатов. Результаты, полученные в ходе работы над диссертацией, были использованы при проведении научно-исследовательской работы «Построение трехмерных схем железнодорожных станций» по договору с НТЦ «ИНТЕХ» по заказу ОАО РЖД в 2005 году.

Апробация работы. По теме диссертации опубликовано 20 научных статей и тезисов докладов. Основные результаты, полученные в ходе работы над диссертацией, были представлены на:

1. Всероссийской конференции студентов, аспирантов и молодых ученых "Технологии Microsoft в теории и практике программирования", (МГТУ им. Н.Э. Баумана, г. Москва) 2005 и 2006 года.

2. Первой ежегодной научной конференции студентов и аспирантов базовых кафедр южного научного центра РАН, (Южный Научный Центр РАН, г. Ростов-на-Дону) 2005 года.

3. Всероссийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" (ТРТУ, г. Таганрог) 2005 и 2006 года.

4. Всероссийской научной конференции с международным участием "Новые информационные технологии. Разработка и аспекты применения" (ТРТУ, г. Таганрог) 2004 года.

Аннотация работы. Диссертационная работа представлена четырмя значимыми главами.

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

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

Во второй главе разработан метод представления геометрических данных в объектном пространстве на основе двоичного разбиения пространства. Метод двоичного разбиения пространства принадлежит к классу алгоритмов разбиения n-мерного пространства. Скорость работы достигается за счет разбиения исходного пространства и проведения предварительных вычислений (при наличии определенных геометрических ограничений). На вход метода поступает набор треугольников. С помощью рекурсивного алгоритма создается бинарное дерево. Организация геометрических данных на основе бинарного дерева позволяет подавать геометрию на растеризацию в точном порядке от более удаленных к менее удаленным или от менее удаленных к более удаленным объектам. Данное дерево может быть использовано в задаче обнаружения столкновений или крупномасштабной отбраковки невидимых объектов. Двоичное дерево разбивает пространство на выпуклые подпространства, используя разделяющие плоскости, параллельные треугольникам, входящим в состав исходного набора геометрии.

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

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

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

В четвертой главе рассматривается программная модель разработанной системы, в которой реализованы следующие методы:

• Построение двоичного дерева в объектном пространстве и обход дерева в порядке, необходимом для подачи геометрии на блок растеризации в порядке строго от ближних полигонов к дальним.

• Двухпроходный рендеринг в отображаемом пространстве на основе иерархического тайлинга изображения и механизма двоичных масок для быстрой растеризации.

• Текстурирование и попиксельная освещенность треугольников с учетом корректировки при проецировании, вычисляемые в пространстве целых чисел.

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

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

Заключение диссертации по теме «Теоретические основы информатики», Надолинский, Никита Александрович

4.3. Выводы

SGL позволяет отрисовывать до 1 ООО ООО видимых треугольников в секунду, что является очень высоким показателем для мобильных устройств. SGL превосходит по качеству изображения и по скорости работы все коммерческие реализации OpenGL ES, EDGE и др. Прирост в скорости отрисовки составляет от 300% до 1500% с использованием FFP. Программируемая архитектура, поддерживаемая SGL, реализована в мобильных устройствах впервые, и не поддерживается конкурирующими библиотеками.

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

ЗАКЛЮЧЕНИЕ

Целью работы является разработка и исследование методов удаления невидимых поверхностей, позволяющих отображать сложные трехмерные сцены на платформе мобильных компьютеров, средствами CPU.

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

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

2. Разработан более эффективный метод двухпроходного расчета видимости частей изображения на основе иерархического тайлинга. Иерархический тайлинг необходим для быстрой отбраковки рассчитанных частей изображения.

3. Впервые разработан метод расчета видимости треугольников на основе бинарных охватывающих масок. Бинарные маски позволяют максимально быстро определить, какие пиксели треугольника будут видимы в текущем кадре.

4. Разработан более эффективный целочисленный метод растеризации треугольников с учетом особенностей архитектуры центрального процессора КПК. Этот метод позволяет растеризовать треугольники в 5-6 раз быстрее метода инкрементального сканирования.

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

Список литературы диссертационного исследования кандидат технических наук Надолинский, Никита Александрович, 2007 год

1. Надолинский Н.А. "Трехмерные геоинформационные системы". Материалы VI Всеросийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления". Сборник тезисов. Таганрог: Изд-во ТРТУ, 2002. с.119

2. Надолинский Н.А. "Программная реализация трехмерных сцен". Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР".

3. Материалы международной научно-технической конференции "Интеллектуальные САПР". Сборник статей. Таганрог: Изд-во ТРТУ, 2001, №4, с.342

4. Надолинский Н.А. "Метод удаления невидимых поверхностей с динамически изменяемым уровнем детализации сцены". Известия ТРТУ. Специальный выпуск "Естественные и гуманитарные науки". Таганрог: Изд-во ТРТУ, 2006, №9, с.25.

5. Агапьев Б. Д. и др. "Обработка экспериментальных данных" Кафедры экспериментальной физики СПбГТУ, 2001.

6. Игнатенко А. Геометрическое моделирование сплошных тел. On-line журнал "Графика и Мультимедиа".

7. Роджерс Д. Математические основы машинной графики / Д. Роджерс, Дж. Адаме. М: Мир, 2001.

8. Роджерс, Дэвид. Алгоритмические основы машинной графики: Пер. с англ. / Д. Роджерс.-М.: Мир, 1989.

9. Рони Я. Рендеринг объемов в реальном времени Университет шт. Огайо, США Открытые Системы №5(19)/96.

10. Ян Ф., и др. Удаленная визуализация 16.11.1999 Открытые системы, № 11-12/1999

11. Hudson Т., Manocha D., Cohen J., Lin M., Hoff К, Zhang H. Accelerated occlusion culling using shadow frustra. In Proc. 13th Annu. ACM Sympos. Comput. Geom., 1997

12. Borshukov, G.D., New Algorithms for Modeling and Rendering Architecture from Photographs., M.S Thesis, EECS department, UC Berkeley, 1997.

13. Cipolla, R., D. Robertson, and E. Boyer. Photobuilder 3D Models of Architectural Scenes from Uncalibrated Images. Procedings of Conference on Multimedia Computing and Systems. 1999.

14. Horry, Y., K.I. Anjyo, and K. Arai. Tour into the picture: Using a spidery mesh interface to make animation from a single image. Procedings of SIGGRAPH 1997.

15. K.Turkowski., Y.X.a., Creating image-basedVRusing a self-calibrating fish-eye lens. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'97), San Juan, Puerto Rico, June 1997.

16. Kang, S.B. and R. Szeliski. 3-D scene data recovery using omnidirectional multibaseline stereo. Procedings of EEE Computer Society Conference on Computer Vision and Pattern Recognition. 1996. San Francisco, California.

17. Kutulakos, K. and S. Seitz, A Theory of Shape by Space Carving. International Journal of Computer Vision, 2000. 38(3).

18. Pollefeys, M., R. Koch, M. Vergauwen, B. Deknuydt, and L.V. Gool. Three-dimensional scene reconstruction from images. Procedings of SPIE Electronic Imaging, Three-Dimensional Image Capture and Applications III, SPIE Proceedings series. 2000.

19. Scharstein, D., Stereo vision for view synthesis. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'96), San Francisco, California, June 1996.

20. Seitz, S.a.C.D. Photorealistic Scene Reconstruction by Voxel Coloring. Procedings of Computer Vision and Pattern Recognition Conference, p. 1997.

21. Taylor, C., P. Debevec, and J. Malik. Reconstructing Polyhedral Models of Architectural Scenes from Photographs. Procedings of ECCV '96: Fourth European Conference on Computer Vision, 1996.

22. Trucco, E. and A. Verri, Introductory Techniques for 3-D Computer Vision. 1998, New Jersey: Prentice Hall.

23. PhotoModeler. http://www.PhotoModeler.com

24. Canoma. http://www.canoma.com.

25. Liebowitz, D., A. Criminisi, and A. Zisserman. Creating Architectural Models from Images. Procedings of Eurographics 1999, Computer Graphics Forum. 1999.

26. Lengyel., J., The convergence of graphics and vision. Technical report, IEEE Computer, July 1998.

27. Cyberware, Inc. Available from: www.cyberware.com

28. Kang, S.B., A survey of image-based rendering techniques. VideoMetrics , SPIE, 1999.3641: p. 2-16.

29. Kurt Akeley and T. Jermoluk. High-Performance Polygon Rendering. Computer Graphics (SIGGRAPH 88 Conference Proceedings), volume 22, number 4, pages 239-246. August 1988.

30. Kurt Akeley. RealityEngine Graphics. SIGGRAPH 93 Conference Proceedings, pages 109-116. August 1993. ISBN 0-89791-601-8.

31. Loren Carpenter. The A-buffer, an Antialiased Hidden Surface Method. Computer Graphics, (SIGGRAPH 84 Conference Proceedings), volume 18, number 3, pages 103-108. July 1984. ISBN 0-89791-138-5.

32. Michael Deering and S. Nelson, Leo: A System for Cost Effective 3D Shaded Graphics. SIGGRAPH 93 Conference Proceedings, pages 101-108. August 1993.

33. Henry Fuchs. Distributing a Visible Surface Algorithm over Multiple Processors. Proceeding of the 6th ACM-IEEE Symposium on Computer Architecture, pages 58- 67. April, 1979.

34. Henry Fuchs et al. Fast Spheres, Shadows, Textures, Transparencies, and Image Enhancements in Pixel-Planes. Computer Graphics, (SIGGRAPH 85 Conference Proceedings), volume 19, number 3, pages 111-120. July 1985.

35. Paul Haeberli and Kurt Akeley. The Accumulation Buffer: Hardware Support for High-Quality Rendering. Computer Graphics, (SIGGRAPH 90 Conference Proceedings), volume 24, number 4, pages 309-318. August 1990. ISBN 0-89791-344-2.

36. Chandlee Harrell and F. Fouladi. Graphics Rendering Architecture for a High Performance Desktop Workstation. SIGGRAPH 93 Conference Proceedings, pages 93-100. August 1993.

37. Michael Kelley, K. Gould, B. Pease, S. Winner, and A. Yen. Hardware Accelerated Rendering of CSG and Transparency. SIGGRAPH 94 Conference Proceedings, pages 177-184.1994.

38. Abraham Mammen. Transparency and Antialiasing Algorithms Implemented with the Virtual Pixel Maps Technique. IEEE Computer Graphics and Applications, 9(4), pages 43-55. July 1989. ISBN 0272-1716.

39. Steven Molnar, John Eyles, and John Poulton. PixelFlow: High-Speed Rendering Using Image Composition. Computer Graphics, (SIGGRAPH 92Conference Proceedings), volume 26, number 2, pages 231-240. July 1992.

40. F. Park. Simulation and Expected Performance Analysis of Multiple Processor Z-Buffer Systems. Computer Graphics, (SIGGRAPH 80 Conference Proceedings), pages 48-56.1980.

41. Thomas Porter and Tom Duff. Compositing Digital Images. Computer Graphics, (SIGGRAPH 84 Conference Proceedings), volume 18, number 3, pages 253-259. July 1984. ISBN 0-89791-138-5.

42. Andreas Schilling. A New Simple and Efficient Antialiasing with Subpixel Masks. Computer Graphics, (SIGGRAPH 91 Conference Proceedings), volume 25, number 4, pages 133-141. July 1991.

43. Jay Torborg and James Kajiya. Talisman: Commodity Realtime 3D Graphics for the PC. SIGGRAPH 96 Conference Proceedings, pages 353363.1996.

44. G. Watkins. A Real-Time Visible Surface Algorithm. Computer Science Department, University of Utah, UTECH-CSC-70-101. June 1970.

45. Lance Williams. Pyramidal Parametrics. SIGGRAPH 83 Conference Proceedings, pages 1-11. July 1983.

46. G. Abram, L. Westover, and T. Whitted, "EcientAlias-Free Rendering using Bit-Masks and Look-Up Tables" Proceedings of SIGGRAPH *85, July 1985, 53-59.

47. L. Carpenter, "The A-buffer, an Antialiased HiddenSurface Method" Proceedings of SIGGRAPH '84 , July 1984.

48. E. Catmull, "A Subdivision Algorithm for ComputerDisplay of Curved Surfaces" PhD Thesis, Report UTEC-CSc-74-133, Computer Science Dept., University of Utah, Salt LakeCity, Utah, Dec. 1974.

49. E. Catmull, "A Hidden-Surface Algorithm with Anti-Aliasing" Proceedings of SIGGRAPH 1% , Aug. 1978, 6-11.

50. R. Cook, "Stochastic Sampling in Computer Graphics" ACM Transactions on Graphics, Jan. 1986,51-72.

51. M. A. Z. Dippe and E. H. Wold, "Antialiasingthrough Stochastic Sampling" Proceedings of SIGGRAPH 85, July 1985,69-78.

52. E. Fiume, A. Fournier, and L. Rudolph, "A ParallelScan Conversion Algorithm with Anti-Aliasing for a General-Purpose Ultracomputer" Proceedings of SIGGRAPH '83 , Julyl983,141-150.

53. E. Fiume, "Coverage Masks and Convolution Tables forFast Area Sampling" Graphical Models and Image Processing, 53(1), Jan. 1991, 2530.

54. J. Foley, A. van Dam, S. Feiner, and J. Hughes, Computer Graphics, Principles and Practice, 2nd edition, Addison-Wesley, Reading, MA, 1990.

55. H. Fuchs, J. Kedem, and B. Naylor, "OnVisible Surface Generation by a Priori Tree Structures", June 1980,124-133.

56. N. Greene, M. Kass, and G. Miller, "Hier-archical Z-Buffer Visibility" July 1993,231-238.

57. N. Greene and M. Kass, "Error-Bounded An-tialiased Rendering of Complex Environments", July 1994, 59-66.

58. N. Greene, "Hierarchical Rendering of Complex Environments" PhD Thesis, Univ. of California at Santa Cruz, ReportNo. UCSC-CRL-95-27, June 1995.

59. N. Greene, "Naked Empire" ACM Siggraph Video Re-view Issue 115: The Siggraph '96 Electronic Theater, August 1996.

60. P. Haeberli and K. Akeley, "The AccumulationBuffer: Hardware Support for High-Quality Rendering", Aug. 1990,309-318.

61. A. Kaufman, "3D Scan Conversion Algorithms forVoxel-Based Graphics", Oct. 1986, 45-75.

62. D. Meagher, "The Octree Encoding Method for Efficient Solid Modeling" PhD Thesis, Electrical Engineering Dept., Rensselaer Polytechnic Institute, Troy, New York, Aug. 1982.

63. B. Naylor, "Interactive Solid Geometry Via PartitioningTrees", May 1992, 11-18.

64. B. Naylor, "Partitioning Tree Image Representation andGeneration from 3D Geometric Models", May 1992,201-212.

65. D. Rogers, Procedural Elements for Computer Graphics, McGraw-Hill, New York, 1985.

66. P. Sabella and M. Wozny, "Toward Fast Color-Shaded Images of CAD/CAM Geometry", 3(8), Nov. 1983,60-71.

67. S. Teller, "Visibility Computations in Densely OccludedPolyhedral Environments" PhD Thesis, Univ. of California atBerkeley, Report No. UCB/CSD 92/708, Oct. 1992.

68. J. Warnock, "A Hidden Surface Algorithm for Com-puter Generated Halftone Pictures" PhD Thesis, ■ ComputerScience Dept., University of Utah, TR 4-15, June 1969.