Введение к работе
Актуальность темы. Возросшие вычислительные мощности современных компьютеров позволяют создавать интерактивные трехмерные графические приложения (программы), способные обрабатывать сиены значительной сложности в реальном времени. Такими приложениями являются, например, трехмерные тренажеры и симуляторы, такие, как тренажеры летчиков, капитанов судов, водителей автомобилей и т.п., а также видеоигры. Другими примерами трехмерных приложений, выполняемых не обязательно в режиме реального времени, являются программные продукты, предназначенные для применения а медицине, астрономии, архитектуре и т.д. В настоящей диссертационной работе будут рассматриваться проблемы, связанные с разработкой приложений реального времени.
Несмотря на значительное многообразие применений и разіїшгу свойств, большинство указанных систем, выполняемых в реальном времени, имеют много общего. В каждом из них используются средства современной компьютерной графики (как аппаратные, так и программные решения), позволяющие визуализировать в реальном времени, т.е. со скоростью не менее 10-12 кадров в секунду сложные трехмерные сцены. Целью трехмерной визуализации является предоставление пользователю программного продукта возможности присутствовать в виртуальном пространстве, перемещаться В- нем, наблюдать его, а также взаимодействовать с объектами, находящимися и "живущими" в воссозданном мире.
Разработка каждого трехмерного приложения является сложной технической задачей. Рассмотрим основные проблемы, которые необходимо решить при проектировании подобных программ. Во-первых, необходимо определить тип и сложность трехмерных пространств, а также объектов, находящихся в них, которые необходимо визуализировать. Далее, необходимо определить базовые структуры данных представления сцен и объектов, а также алгоритмы их обработки. Наконец, следует определить способ задания данных для программы, т.е. необходимо решить, каким образом можно подготовить (сконструировать) трехмерные сцены и объекты.
В настоящее время существует значительное количество методов задания трехмерных сцен, различающихся по способу представления поверхностей. Наиболее распространенным является представление поверхностей с помощью набора плоских многоугольников (полигонов). Для представления участков гладких поверхностей используется их разбиение на многоугольники или треугольники. Другим способом представления поверхностей является разбиение на сплайновые участки. В приложениях реального времени чаще всего используется представление сцен с помощью набора полигонов, т.к. подобные геометрические объекты являются наиболее простыми и удобными для обработки.
Процесс создания трехмерной сцены называется моделированием. Существует множество программных продуктов, позволяющих эффективно конструировать
трехмерные сцены и объекты. Среди таких систем находятся Softimage Creative Environment, Alias Wavefront, 3D Studio, AutoCAD и другие. Отметим, что хотя все эти системы позволяют моделировать трехмерные сцены и объекты, данные, которые ими генерируются, не являются в достаточной степени удобными для обработки в реальном времени. Дело в том, что в процессе моделирования порождается набор неупорядоченных многоугольников, так называемый "полигональный суп", Генерируемые многоугольники могут быть невыпуклыми, самопересекающимися, с несвязными контурами (т.е. с внутренними дырами) и т.д. Важнейшей задачей является упорядочивание набора многоугольников на этапе предобработки и конвертации сцен.
Еще несколько лет назад, до появления графических акселераторов (специального аппаратного обеспечения, предназначенного для ускорения отображения трехмерных сцен), вычислительные мощности персональных компьютеров не позволяли обрабатывать в реальном времени сцены, состоящие более чем из 1-2 тысяч полигонов и десятка мало-лолигональных объектов. При этом эффективно на экран выводилось не более 200-500 полигонов. Для повышении эффективности обработки было разработано множество технологий, позволявших во многих случаях вообще отказаться от использования трехмерных объектов и использовать вместо них соответствующим способом подготовленные двумерные изображения (спрайты). Использование спрайтов позволяло значительно уменьшить количество выводимых полигонов, но ухудшало общее качество графики, а также накладывало жесткие ограничения на возможные перемещения в пространстве. Основными процедурами, занимавшими большую часть процессорного времени, являлись определение порядка вывода полигонов на экран (сортировка видимых полигонов) и собственно программная растеризация (рисование) текстурированных полигонов.
Появление аппаратных ускорителей для персональных компьютеров явилось революционным шагом в развитии интерактивных трехмерных приложений. Использование ускорителей решило большинство из описанных выше проблем, т.к. с их помощью возможно выводить до 600 000 - 1 000 000 полигонов в секунду. Таким образом, собственно вывод полигонов на экран перестал быть узким местом систем. Тем не менее, существенно возросшая сложность трехмерных сцен потребовала разработки специальных методов (структур данных и алгоритмов) для их обработки.
Во многих современных приложениях сцены состоят из многих тысяч объектов и десятков тысяч полигонов. Несомненно, для того, чтобы обеспечить работу приложения в реальном времени, требуется разработать (или усовершенствовать имеющиеся) базовые алгоритмы обработки сцен. Среди базовых алгоритмов одними из наиболее важных являются алгоритмы отсечения объектов по пирамиде зрения (viewing frustum culling), определение столкновений между двигающимися объектами (collision detection) и трассировка лучей (ray shooting).
Данные операции являются ключевыми для многих приложений, и их неэффективная реализация может стать препятствием в достижении необходимой
скорости работы. Одним из способов ускорения работы базовых алгоритмов является использование эффективных ограничивающих тел. Ограничивающее тело — это "простое" геометрическое тело (прямоугольник или круг в 2D, сфера или прямоугольный параллелепипед в 3D), содержащее объект сцены. При использовании ограничивающих тел ускорение алгоритмов происходит за счет того, что некоторые тесты можно вначале произвести с ограничивающим телом (служащим грубой аппроксимацией формы реального объекта) и в результате этого предсказать результат точного (и более долго выполняющегося) теста, производимого со всеми полигонами объекта. Например, если луч не пересекает ограничивающее тело, то он не пересекает и сам объект. В данной диссертационной работе в качестве ограничивающих тел используются произвольно-ориентированные прямоугольные параллелепипеды.
Данное исследование было начато с практической точки зрения из-за необходимости улучшить эффективность работы алгоритмов, используемых в реальном приложении. В процессе работы было выявлено, что многие задачи являются важными проблемами, рассматриваемыми в области Вычислительной геометрии. Несмотря на то, что в данной области уже было получено множество результатов, многие задачи еще не являются исследованными в достаточной мере. Среди них находятся проблемы построения оптимальных ограничивающих многоугольников (многогранников), минимальных по периметру или площади. В работе формулируется и успешно решается ряд задач указанного класса. В частности, полученная геометрическая характеризация описанных многоугольников (многогранников) позволила разработать эффективные алгоритмы, успешно примененные для решения практических задач. Было выявлено, что разработанные методики являются успешно применимыми не только для обработки трехмерных сцен в реальном времени, но и для ускорения вычислений на этапе препроцессинга - например, для расчета карты глобальной видимости (необходимой для создания подсистемы искусственного интеллекта и навигации в трехмерном пространстве) и освещенности пространства (например, в методе radiosity).
Цель и задачи исследования. Основной целью работы является решение задачи построения оптимальных ограничивающих тел, получение критериев оптимальности ограничивающих тел, разработка эффективных алгоритмов построения таких ограничивающих тел на этапе предобработки сцен, анализ сложности алгоритмов, а также разработка и анализ алгоритмов обработки ограничивающих тел, выполняемых в реальном времени.
Методы исследования. Для решения поставленных задач использованы методы вычислительной геометрии, интегральной геометрии, теории сложности алгоритмов, компьютерной графики, а также моделирование на компьютере.
Научную новизну составляют следующие результаты работы, являющиеся предметом защиты.
-
Математическая формализация задачи построения оптимальных ограничивающих тел с использованием точных методов интегратьной геометрии. В рамках введенной формализации, разработка критерия оценки оптимальности ограничивающих тел.
-
Доказагельство оптимальности описанных произвольно-ориентированных прямоугольников (прямоугольных параллелепипедов), минимальных по периметру (площади поверхности), для выполнения целого ряда базовых алгоритмов обработки трехмерных сцен, а именно, для проведения тестов по видимости по пирамиде зрения, трассировки лучей и, при определенных условиях, для проведения тестов на пересечения объектов.
-
Постановка задачи и анализ проблемы построения оптимальных иерархических ограничивающих тел. Получение критерия оптимальности для 2-уровневых иерархий.
-
Доказательство теоремы, позволяющей геометрически охарактеризовать положение прямоугольника минимального периметра, описанного вокруг выпуклого многоугольника. Разработка эффективного (оптимального) алгоритма построения описанных прямоугольников вокруг выпуклых многоугольникоз, а также вокруг произвольного набора точек на плоскости.
-
В рамках вычислительной модели алгебраических деревьев решений, получение нижней оценки сложности для задачи построения описанного прямоугольника минимального периметра.
-
Доказательство теоремы, геометрически характеризующей положение произвольно-ориентированного прямоугольного параллелепипеда (oriented bounding box - ОВВ) минимальной площади поверхности, описанного вокруг выпуклого многогранника. Описание точного алгоритма построения описанного произвольно-ориентированного прямоугольного параллелепипеда, минимального по площади поверхности, вокруг произвольного набора точек в трехмерном пространстве.
-
Разработка приближенных алгоритмов построения описанного произвольно-ориентированного прямоугольного параллелепипеда, минимального по площади поверхности, вокруг произвольного набора точек в пространстве. Алгоритмы отличаются по своей вычислительной сложности и качеству приближения построенных параллелепипедов.
-
Анализ результатов практического применения описанных алгоритмов, сравнения качества ограничивающих тел, построенных с использованием различных точных и приближенных алгоритмов, а также сравнение с ранее известными алгоритмами других авторов.
Практическая ценность работы состоит в разработке универсальной структуры данных ограничивающих тел - минимальных по площади поверхности ограничивающих произвольно-ориентированных прямоугольных параллелепипедов, а
также в описании алгоритмов работы с указанной структурой данных как на этапе построения во время предобработки, так и на этапе использования в реальном времени. Использование разработанных методов (структур данных и алгоритмов их обработки) позволяет существенно повысить производительность трехмерных приложений. Сравнение эффективности работы реальных приложений, использующих ОВВ-деревья, построенных с помощью описанных в работе алгоритмов, а также построенных по алгоритмам, предложенным другими авторами, показывает значительное превосходство описанных в работе методов.
Достоверность результатов обеспечивается использованием в диссертационной работе строгих методов вычислительной геометрии, теории сложности алгоритмов и интегральной геометрии. Полученные в работе теоретические результаты подтверждаются данными, полученными при измерении эффективности работы реально работающих программных продуктов.
Апробация работы. Научные результаты и основные положения диссертационной работы докладывались и обсуждались на 6-ти международных конференциях -Computational Visual'97 (Мехико, Мексика), 7-ой и 8-ой Центрально-Европейской Конференции по Компьютерной графике и Визуализации (Пльзень, Чехия, 1997, 1998), 15-ой Конференции Еврографика-Англкя (Норидж, Англия, 1997), 6-ой Конференции Скандинавских Стран по Искусственному Интеллекту (Хельсинки, Финляндия, 1997), Конференции по Компьютерной Графиже и ее применению (Братислава, Словакия, 1997).
Публикации. По теме диссертации опубликовано 9 работ, список которых приведен в конце автореферата.
Структура и объем диссертации. Диссертация состоит из Введения, 6 глав, и Заключения. В Главе 6 приводятся и анализируются результаты практической работы алгоритмов. Диссертационная работа изложена на 100 листах и содержит 31 рисунок. Список литературы содержит 63 наименования.