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

со

Олегу

На правах рукописи

ИОНЕС Андрей Леонидович

ПОСТРОЕНИЕ ОПТИМАЛЬНЫХ ОГРАНИЧИВАЮЩИХ ТЕЛ В КОМПЬЮТЕРНОЙ ГРАФИКЕ

Специальность 05.13.16-Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям науки)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 1998

Работа выполнена в Санкт-Петербургском Государственном Техническом Университете.

Научный руководитель:

доктор физико-математических наук, профессор Л. В. Петухов.

Официальные оппоненты:

доктор физико-математических наук И. В. РОМАНОВСКИЙ, профессор Санкт-Петербургского Государственного Университета

кандидат физико-математических наук Г. Ю. ПАНИНА

старший научный сотрудник Санкт-Петербургского Института Информатики Российской Академии Наук

Ведущая организация:

Санхт-Петербургское отделение математического института им. Стеклова

Защита состоится« » (.■¿¿¿ЛЯ 1998 г. в часов на заседании

специализированного совета Д 063.38.18 в Санкт-Петербургском Государственном Техническом Университете по адресу: ¡95251, С.-Петербург, Политехническая ул., 29

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского Государственного Технического Университета.

Автореферат разослан « ¿^У » био/и? 1998 г.

Ученый секретарь

специализированного совета Д 063.38.18 доктор биологических наук _ А. В. ЗИНКОВСКИЙ

Общая характеристика работы

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

Несмотря на значительное многообразие применений и разницу свойств, большинство указанных систем, выполняемых в реальном времени, имеют много общего. В каждом из них используются средства современной компьютерной графики (как аппаратные, так и программные решения), позволяющие визуализировать в реальном времени, т.е. со скоростью не менее 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).

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

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

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

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

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

Научную новизну составляют следующие результаты работы, являющиеся предметом защиты.

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

2. Доказательство оптимальности описанных произвольно-ориентированных прямоугольников (прямоугольных параллелепипедов), минимальных по периметру (площади поверхности), для выполнения целого ряда базовых алгоритмов обработки трехмерных сцен, а именно, для проведения тестов но видимости по пирамиде зрения, трассировки лучей и, при определенных условиях, для проведения тестов на пересечения объектов.

3. Постановка задачи и анализ проблемы построения оптимальных иерархических ограничивающих тел. Получение критерия оптимальности для 2-уровневых иерархий.

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

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

6. Доказательство теоремы, геометрически характеризующей положение произвольно-ориентированного прямоугольного параллелепипеда (oriented bounding box - ОВВ) минимальной площади поверхности, описанного вокруг выпуклого многогранника. Описание точного алгоритма построения описанного произвольно-ориентированного прямоугольного параллелепипеда, минимального по площади поверхности, вокруг произвольного набора точек в трехмерном пространстве.

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

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

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

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

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

Апробация работы. Научные результаты и основные положения диссертационной работы докладывались и обсуждались на 6-ти международных конференциях -Computational Visual'97 (Мехико, Мексика), 7-ой и 8-ой Центрально-Европейской Конференции по Компьютерной графике и Визуализации (Пльзень, Чехия, 1997, 1998), 15-ой Конференции Еврографкка-Англия (Норидж, Англия, 1997), 6-ой Конференции Скандинавских Стран по Искусственному Интеллекту (Хельсинки, Финляндия, 1997), Конференции по Компьютерной Графике и ее применению (Братислава, Словакия, 1997).

Публикации. По теме диссертации опубликовано 9 работ, список которых приведен в конце автореферата.

Структура и объем диссертации. Диссертация состоит из Введения, 6 глав, и Заключения. В Главе 6 приводятся и анализируются результаты практической работы алгоритмов. Диссертационная работа изложена на 100 листах и содержит 31 рисунок. Список литературы содержит 63 наименования.

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

Во Введении дана общая характеристика работы, приведен обзор литературы и изложено краткое содержание работы.

Впервые неиерархические ограничивающие тела (сферы) были описаны Clark (1976) и Whitted (1980) для ускорения алгоритмов трассировки лучей, затем были предложены первые алгоритмы с использованием иерархических ограничивающих тел. Позднее многими исследователями были разработаны различные типы ограничивающих тел. Основными типами ограничивающих тел являются сферы, выровненные по координатным осям и произвольно-ориентированные прямоугольные параллелепипеды, и другие. Несмотря на то, что каждый из указанных типов может быть использован для ускорения алгоритмов обработки сцен, некоторые из них

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

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

Структуры данных, предложенные для определения столкновений межд объектами, включают деревья конусов, k-d деревья и 8-деревья (octrees), деревья сфер ; др. Помимо алгоритмов, основанных на иерархиях ограничивающих тел, были такж предложены алгоритмы, использующие BSP-деревья, пространственно-временны границы и четырехмерные тесты. Все эти алгоритмы успешно работают дл выполнения тестов на "отсутствие пересечений" в случае, когда движущиеся объект! находятся далеко друг от друта. Если объекты находятся в непосредственной близост и могут иметь множество точек контакта, производительность указанных алгоритмо значительно уменьшается и они становятся "узким местом" для приложения.

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

Недавно были описаны эффективные алгоритмы определения пересечени объектов, пригодные для использования в приложениях реального времени. В нерву! очередь, это ряд алгоритмов, предложенных Готтсчалком и Манохой, основанных н использовании иерархической структуры данных ограничивающих произвольнс ориентированных прямоугольных параллелепипедов (ОВВТгее). В работе указанны авторов описывается схема построения ОВВ-деревьев, предлагаются эффективны способы проведения тестов на пересечения между сложными объектами, а такж эмпирически показывается, насколько ОВВ-деревья являются асимптотическ лучшими, чем ААВВ-деревья и деревья сфер.

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

б

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

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

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

Т = Nv+ С v + Np*Cp, (1)

где:

Т - общее время, затраченное на обработку;

Nv - количество тестов, выполненных с ограничивающими телами;

Cv - время выполнения одного теста с ограничивающими телами;

Np - количество объектов, обработанных по составляющим полигонам;

Ср - время выполнения обработки по полигонам одного объекта.

С помощью уравнения (1) проводится анализ качества различных иерархических ограничивающих тел, а также описываются общие требования, предъявляемые иерархическим ограничивающим телам. Указывается, что выбранный тип ограничивающих тел - произвольно-ориентированные прямоугольные параллелепипеды (ОВВ) - являются лучшими по сравнению с ограничивающими сферами и выровненными по координатным осям прямоугольными параллелепипедами (axis-aligned bounding boxes - ААВВ).

В главе 2 вводится формальный критерий оптимальности ограничивающих тел.

Определение. Пусть Ко - произвольное тело (объект сцены). Пусть К - выпуклое тело, Ко с К. Тогда К называется ограничивающим телом для тела К0.

Будем также считать, что все объекты сцены Ко являются выпуклыми -действительно, ограничивающее тело К, построенное для Ко, является ограничивающим и для его выпуклой оболочки.

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

Задача. "Критерий оптимальности ограничивающего тела для трассировки лучей".

Дано: Объект сцены (состоящий из множества полигонов).

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

Рассмотрим задачу отсечения по пирамиде зрения с использованием иерархических ограничивающих тел. Операция отсечения с использованием иерархических ограничивающих тел состоит в квалификации ограничивающего тела по пирамиде зрения. В результате квалификации определяется, находится ли ограничивающее тело целиком внутри или снаружи пирамиды зрения, или пересекает ее. Если ограничивающее тело находится целиком внутри пирамиды зрения, то и сам объект, описанный данным телом, находится внутри пирамиды. Кроме того, все объекты поддереву также находятся внутри пирамиды зрения - следовательно, необходимость в их квалификации отпадает. Аналогично, если тело находится целиком снаружи пирамиды зрения, то ни соответствующий ему объект, ни поддерево объектов не видны даже частично, следовательно, их можно исключить из дальнейшей обработки. Если же ограничивающее тело пересекает пирамиду зрения, то нельзя заранее сказать, видны или нет объекты, находящиеся в поддереве, следовательно, процедуру квалификации следует повторить на более низких уровнях иерархии, а при обработке самих объектов, у которых ограничивающие тела квалифицированы как пересекающие пирамиду зрения, необходимо отсекать (clip) каждый полигон объекта. Если ограничивающее тело квалифицируется как пересекающее пирамиду зрения, в то время как объект в действительности находится целиком внутри или снаружи пирамиды, то происходит неправильная квалификация. Несомненно, каждая неправильная квалификация приводит к увеличению времени обработки. Т.о., оптимальным ограничивающим телом является такое тело, для которого мера множества точек в пространстве и направлений зрения, т.е. в трехмерном пространстве {<х, у, а>}, для которых происходит неправильная квалификация, минимальна. Сказанное ведет к следующей постановке задачи:

Задача. "Критерий оптимальности ограничивающего тела для отсечения по пирамиде зрения ".

Дано: Объект сцены (состоящий из множества полигонов)

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

Задача выбора оптимальных ограничивающих тел может быть решена с помощью методов интегральной геометрии.

Будем обозначать лучи символом й. Положение луча может определяется координатами начала (х, у) и направлением 9. Плотность лучей задается соотношением:

¿10 <±с л с!у с1 в. '

Пусть Ко - выпуклое тело (объект сцены), К - его некоторое ограничивающее тело, К0сК.

Введенное выше понятие эффективности ограничивающих тел для трассировки лучей определяется мерой т множества лучей, пересекающих К и не пересекающих К0\

т=т(С; в ПК* 0,в пК0 = 0).

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

т = К0 = 0) = ¡¿в = ¡склфлЛв.

Данный интеграл, взятый по всем точкам плоскости (х, у) и направлениям в, бесконечен. Для сравнения относительной асимптотической эффективности ограничивающих тел, вычислим вначале меру т (Я) внутри некоторого описанного круга Сц с радиусом Л и центром в точке О, О £ Ко-

т(Я) = т{С;вп К * о К0 = 0,(х,у) е С„) = |еГС = \dxKdyAde.

В работе доказана следующая теорема, устанавливающая асимггготическую оценку меры т(И).

Теорема. ("Оценкамеры т(Л)"). Пусть К/, К2 - выпуклые ограничивающие тела с периметрами I / и соответственно. Пусть гП](К) и т2(И) - интегралы (2),

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

вычисленные для указанных тел. Тогда если < 12, то 3 К0 такое, что V Я > выполнено следующее неравенство: т1(К) < т2(К).

Следствие ("Критерий оптимальности для трассировки лучей, выполняемой с помощью ОВВ"): ОВВ является оптимальным для трассировки лучей тогда и только тогда, когда его периметр минимален среди всех описанных ОВВ.

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

(объект

направление зрения 9

точка зрения ('.У)

тело Ко сцены)

ограничивающее тело К

пирамида зрения с углом раствора 2у

Рис. 1. Пирамида зрения на плоскости

При перспективной проекции на экран область видимости задается пирамидой зрения. Пусть угол пирамиды (неограниченного углового сектора в случае плоскости) равен 2у.

Будем обозначать угловые сектора символом В. Положение сектора с фиксированным угловым раствором может быть определено направлением в его средней линии и координатами (х, у) точки основания (Рис. 1). Тогда плотность множества угловых секторов будет определяться соотношением:

с1В =с!х лф лс1в.

Пусть К0 - выпуклое тело (объект сцены), К - его некоторое ограничивающее тело, КеаК.

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

т =т0(В; ВпК*0В пК0 = 0) + т,(В; В пК * 0, К <? В, К0 с В).

Чем больше указанная мера т, тем менее эффективным является ограничивающее тело. Мера т может быть вычислена как интеграл плотности угловых секторов ¿В по соответствующему множеству:

т - тс + /и, = + = ^ск лф'лс]9л ¿у л с!в.

Яг-,л>0>ггпКо=0 бпКк0,Х<гЯ.ХосЯ

Этот интеграл, взятый по всем точкам плоскости (х, у) и направлениям зрения 0, бесконечен. Для сравнения относительной асимптотической эффективности ограничивающих тел, вычислим вначале меру т(Ю внутри некоторого описанного круга Сц с радиусом Я и центром в точке О, О е Ко'.

т(Щ = та(Я) + т,(Я) = ] & л ¿у л + \с!х л ¿у л ¿10. (3)

В работе доказана следующая теорема, устанавливающая асимптотическую оценку меры т(Я).

Теорема. ("Оценкамеры т(И) ") Пусть К/, К2 - выпуклые ограничивающие тела с периметрами и соответственно. Пусть т\(Я) и т2(Щ - интегралы (3), вычисленные для указанных теп. Тогда если I/ < 1.2, то 3 Яо такое, что V Я > Я0 выполнено следующее неравенство: ¡»¡(Я) < т2(К).

Следствие ("Критерий оптимальности для отсечения по пирамиде зрения, выполняемых с помощью ОВВ"): ОВВ является оптимальным для отсечения по пирамиде зрения тогда и только тогда, когда его периметр минимален среди всех описанных ОВВ.

Далее, в работе эмпирически показывается применимость критерия оптимальности для задачи определения пересечений объектов.

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

Пусть Ки К2 - два выпуклых пересекающихся тела, К с К/ п К2. В работе показано, что мера т множества лучей (?, пересекающих оба тела К; и К2, но не пересекающих К, асимптотически равна:

т(в; впК, впК1 ¿0, СпК=0) = ^гЬг-Ьсн-и (4)

где Ьсн - периметр выпуклой оболочки К/ <иК2.

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

Пусть К - отрезок длины 21, и ограничивающее тело верхнего уровня иерархии А'/ - это окружность, построенная на отрезке, как на диаметре. Пусть ограничивающие тела являются окружностями. Построение ограничивающего тела для тела К без учета наличия тела К/ даст окружность К2 = К]. Рассмотрим далее семейство окружностей К2(К) с центрами на прямой, перпендикулярной отрезку К, и являющихся ограничивающими телами для К: К сК-/И) (Рис. 2). Ясно, что К > I. Непосредственные вычисления дают следующее выражение для меры гп (4) как функции от Я (с параметром Г):

т(Л) = 2(й -1)+ л(1 + £.)-2-Д^К2 - Р ^у^ . (5)

График функции т(Я) схематически показан на Рис. 3. Чем меньше значение меры т(К), тем лучше ограничивающее тело. Таким образом, анализ функции т(К) показывает следующий удивительный результат: любая ограничивающая окружность, не равная АГ/ (оптимальной в смысле локального критерия), является лучшей в смысле иерархического критерия. Оптимальная ограничивающая окружность (соответствующая минимуму функции т(И)) является приблизительно на 40% лучше локально-оптимальной окружности

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

т(Щ

I Я

Рис. 3. Схематический график функции т(Я), иллюстрирующий "качество " ограничивающих окружностей К2(К) в смысле введенной меры. Чем меньше значение меры т(Я), тем лучше ограничивающее тело.

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

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

Задача М1ТШЕСТ-С(ЖУ. ("Построение описанного прямоугольника минимального периметра вокруг выпуклого многоугольника").

Дано: Произвольный выпуклый п-угольник Р„.

Требуется: Построить прямоугольник К минимального периметра, описанный вокруг многоугольника Р„.

Доказывается следующая теорема:

Теорема. Пусть Р„ - произвольный выпуклый многоугольник, а К - описанный прямоугольник. Пусть и Р - периметр и площадь прямоугольника /?; а, Ъ -вещественные числа, а>0, Ь>0. Функция Р - а*Б + Ь*Р достигает своего минимума тогда, когда по крайней мере одна сторона Я совпадает с одной из сторон Р„.

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

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

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

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

Задача МШЛЕСТ. ("Построение описанного прямоугольниха минимального периметра вокруг произвольного набора точек").

Дано: Множество 5из /Уточекна плоскости.

Требуется: Построить прямоугольник Я минимального периметра, описанный вокруг множества точек

В работе приводится алгоритм решения этой задачи со сложностью ОСЫ^ЬГ).

Для получении нижней оценки сложности задачи МПЧЯЕСТ используется сведение к ней задачи о поиске максимального промежутка (МАХОАР). А именно, доказывается следующая теорема:

Теорема. Задача МАХОАР сводима за линейное время к задаче МШКЕСТ: МАХОАР а:И МШЯЕСТ, и, следовательно, для построения описанного многоугольника для произвольного множества N точек на плоскости требуется время

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

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

Теорема. Пусть Р„ - произвольный выпуклый многогранник, а В • описанный прямоугольный параллелепипед минимальной площади поверхности. Тогда существуют по крайней мере два ребра е;, е2 многогранника Р„, таких, что в/ с/и е; сгД где_/} /2 -две соседние грани прямоугольного параллелепипеда В.

С использованием последней теоремы, в работе предложена схема точного алгоритма построения оптимальных ОВВ в трехмерном пространстве. Сложность описанного алгоритма 0(Ы3). Так как эта сложность слишком высока для практического использования алгоритма даже на этапе препроцессинга, в работе приводятся 4 приближенных алгоритма построения оптимальных ОВВ. Первый из них, имеющий сложность 0(Ы1о£^Ч), был впервые описан в работе Готгсчалка и Манохи и базируется на вычислении порядковых статистик и матрицы ковариантности. Кроме того, в главе описаны 3 новых приближенных алгоритма, имеющих сложность 0(Ы2), 0(Ы1о§Ы+к*>Г) и 0(Ы1о£^М), соответственно. В работе (Глава 4) проводится анализ

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

В главе 5 рассматриваются методы выполнения базовых операций с использованием построенных ОВВ.

Выше было рассмотрено базовое уравнение (1). используемое для анализа сложности алгоритмов, выполняющихся на иерархических структурах. Было указано, что использование иерархий простейших ограничивающих тел - сфер и выровненных по координатным осям прямоугольным параллелепипедам (ААВВ) позволяет выполнять большинство операций очень быстро. В главе 5 показывается, что и выполнение базовых операций с использованием более сложных структур - ОВВ-деревьев - может быть реализовано весьма эффективно.

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

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

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

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

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

Далее, в главе приводится сравнение эффективности различных приближенных алгоритмов построения оптимальных ОВВ.

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

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

Публикации по теме диссертации.

1. С. Жуков, А. Ионес, "Моделирование поведения интеллектуальных персонажей в 3D пространстве в реальном времени", Труды каф. «Прикладная математика», СПбГТУ, 1996, стр. 167-174.

2. S. Zhukov, A. Iones: "Procedural Intellectual Animation of 3D Characters over Complex Terrain in Real-Time", Proceedings of Computational Visual'97, published on CD-ROM (Mexico, Mexico).

3. S. Zhukov, A. Iones: "Open 3D animation system based on procedural motion generation", in Proc. of WSCG'97 - Central European conference on Computer Graphics and Visualization'97, pp. 632-639 (Plzen, Czech Rep.).

4. S. Zhukov, A. Iones: "Real-Time Behavior Control of Intelligent 3D Agents", in Proc. of 15th Eurographics-TJK Conference, pp. 101-115 (UK, Norwich, 1997)

5. S. Zhukov, A. Iones, G. Kronin: "On a Practical Use of Light Maps in Real-Time Applications.", in Proc. of SCCG'97 (Slovakia, Bratislava, 1997)

6. S. Zhukov, A. Iones: "Real-Time Behavioral Control of Intelligent 3D Agents in Complex Synthetic Environment", in Proc. of SCAI'97 (FEN, Helsinki, 1997)

7. S. Zhukov, A. Iones, G. Kronin: "Navigation of intelligent characters in complex 3D synthetic environment in real-time applications", in Proc. ofWSCG'98 - Central European conference on Computer Graphics and Visualization'98, pp. 456-463 (Plzen, Czech Rep.).

8. S. Zhukov, A. Iones, G. Kronin: "Using Light Maps to create realistic lighting in real-time applications", in Proc. of WSCG'98 - Central European conference on Computer Graphics and Visualization'98, pp. 464-471 (Plzen, Czech Rep.)

9. A. Iones, S. Zhukov, A. Krupkin "Building optimal bounding volumes for real-time 3D visualization", GKPO'98 (Borki, Poland) / Machine Graphics & Vision, N 7, vol. 1/2, 1998, pp. 84-92