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

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

Никитина Л.Д. , Никитин И.Н. Фраунгоферовский Институт Медиакоммуникаций, Санкт Августин, Германия

Клименко С.В. Институт Физики Высоких Энергий, Протвино, Россия

Ключевые слова:

анализ видимости (visibility test), исключение заслоненных объектов (occlusion culling), виртуальные окружения (virtual environments).

Аннотация

Проведение анализа видимости объектов в реальном времени необходимо для виртуальных окружений, в которых интерактивно визуализируются большие множества данных. В таких сценах большая часть объектов обычно заслонена другими, и их исключение из графической обработки может значительно ускорить процесс обновления изображения. В данной работе мы представляем нашу реализацию алгоритма исключения заслоненных объектов в системе виртуального окружения Аванго [1]. Программный модуль анализа видимости в реальном времени выполняет обновление списка видимых объектов посредством цветового кодирования и либо аппаратурного, либо программного ги-стограммирования соответствующего цветового буфера. Используя механизм распределенных приложений Аванго, процессы отрисовки и анализа видимости па-раллелизованы на различные компьютеры, работающие в операционных средах Irix и Linux. В результате применения нашего метода к архитектурной модели, содержащей 260 тыс. текстурированных треугольников, достигается ускорение графики от 8 до 32 стерео-кадров в секунду.

1 Введение

Для создания ощущения полного погружения в виртуальную реальность требуется высокая степень детализации сцены. Увеличение объема данных интенсифицирует графическую нагрузку, требуя новых подходов к ускорению графики. Важным параметром является так называемая сложность по глубине (depth complexity), т.е. число слоев изображения, находящихся под каждым пикселем на экране. Фактически этот

параметр характеризует напрасную работу графической системы, потраченную на отрисовку невидимых объектов (как известно, при отрисовке непрозрачных объектов стандартной техникой Z-буферизации только один слой изображения остается видимым, но время тратится на отрисовку всех слоев). Широко используемые методы предварительного отбора, реализованные во всех современных графических обработчиках, такие как выделение объема видимости (viewing frustum culling) и стирание обратных сторон (backface culling) не уменьшают сложность по глубине значительно. Переключение уровеней детализации (level-of-detail switching) уменьшает сложность по глубине только у достаточно удаленных объектов. Алгоритмы исключения заслоненных объектов, которые имеют целью уменьшение сложности по глубине в идеальном случае до единицы, могут значительно ускорить процесс графической обработки. Эти алгоритмы реализованы только в некоторых графических системах.

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

2 Обзор предыдущих работ

Множество эффективных методов было разработано для анализа видимости и исключения заслоненных объектов. Специально предназначенный для архитектурных моделей помещений, .метод ячеек и порталов [2] подразделяет здание на комнаты или ячейки, видимые только сквозь небольшие дверные проемы или окна, также называемые порталами. Данные о видимости для каждой ячейки вычисляются заранее и затем используются в реальном времени для исключе-

ния заслоненных объектов. Другая техника с интенсивной стадией предварительных вычислений, алгоритм приоритетно-послойной проекции [3] вычисляет для каждой ячейки вероятность быть заслоненной другими объектами, для данной точки зрения, и либо совершенно исключает маловероятно видимые объекты, либо итеративно уточняет информацию об их видимости, используя анализ видимости в реальном времени. Анализ видимости также используется в технике, основанной на восьмеричных деревьях [4]. Пространство объектов подразделяется на иерархию 23-кубов, приписывая каждый примитив к содержащему его кубу наименьшего размера. Кубы обрабатываются рекурсивно в порядке от передних к задним, каждый раз проверяя, являются ли грани куба видимыми или скрытыми уже изображенными примитивами. Эта проверка выполняется, используя трафаретный буфер (stencil) или специальный флаг видимости, реализованый в некоторых графических картах. Если куб видим, то приписанные к нему примитивы отрисовываются и рекурсия продолжается. Другая техника, часто используемая в комбинации с восьмеричными деревьями в пространстве объектов, это реализованная на плоскости изображения Z-пирамида [4]. Исходный Z-буфер берется в качестве первого уровня пирамиды. Последующие уровни имеют вдвое меньший размер по х- и y-измерениям по сравнению с предыдущими. Четыре соседних значения Z с каждого уровня комбинируются в одно значение для следующего уровня, выбирая Z, наиболее удаленное от наблюдателя. Существует эффективная реализация этой процедуры с помощью текстурных отображений [5]. Для каждого примитива находится уровень Z-пирамиды, на котором этот примитив отвечает одному пикселю. Если ближайшее значение Z примитива находится дальше, чем значение Z в этом пикселе, примитив скрыт. В противном случае примитив отрисовывается и производится обновление всех уровней Z-пирамиды. В аппаратно реализованном алгоритме, использующем флаг видимости фирмы Hewlett Packard [6], в графической карте имеется обратная связь, позволяющая проверить, была ли сделана попытка записи в Z-буфер во время графической обработки данного примитива, без фактического изменения содержимого Z- и цветового буферов. Эта возможность позволяет проверять, был ли ограничивающий куб объекта заслонен другими объектами, и в этом случае исключить объект из дальнейшей отрисовки. Такой метод является эффективным только после сортировки объектов от ближних к дальним, которая выполняется, например, в алгоритме восьмеричных деревьев. Также как и другие методы, основанные на использовании ограничивающих кубов, этот метод существенно консервативен, т.е. он производит излишнюю отрисовку тех скрытых объектов, чей ограничивающий куб видим. Анализ ви-

димости в трафаретном буфере [7] организован сходным образом, но допускает реализацию на любых графических картах посредством стандартного OpenGL. Ограничивающий куб объекта направляется в трафаретный буфер, при активированном Z-тесте, но без записи в Z-буфер. Если ограничивающий куб объекта не оставил отпечатка в трафаретном буфере, значит он заслонен и содержащийся в нем объект не будет отрисован. Недостатком этого метода является медленное чтение содержимого трафаретного буфера. В работе [7] проблема решается сэмплированием буфера. Техники гистограммирования [3] также могут быть использованы для решения аналогичной проблемы при чтении цветового буфера. Некоторые другие техники отмечены в обзорной работе [8], описывающей большинство предыдущих работ по ускорению графики с помощью анализа видимости.

Некоторые из описанных техник аппаратно реализованы в HP, ATI и Nvidia графических системах и используются в программных продуктах OpenGL Optimizer [9], OpenSG Plus [10] и Jupiter [11]. Однако большинство программных продуктов, использующих графы сцены, таких как IRIS/OpenGL Performer, не имеют встроенной реализации алгоритма исключения заслоненных объектов. Главным препятствием является то, что существующие техники исключения заслоненных объектов требуют анализа данных, которые возвращаются графическими обработчиками после отрисовки каждого примитива. Такой анализ возможен в OpenGL, но плохо вписывается в концепции Performer.

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

В данной работе мы описываем реализацию алгоритма исключения заслоненных объектов в системе разработки виртуальных окружений Аванго. Метод не использует специальных аппаратных особенностей и реализован посредством стандартного OpenGL на Irix и Linux платформах. Параллельное исполнение процессов графической обработки и анализа видимости используется для достижения большего ускорения. Результирующее графическое ускорение достаточно для

выполнения прогулок в больших виртуальных окружениях в реальном времени.

3 Аванго

Аванго - это графическая система и программная среда [1] для создания распределеных интерактивных приложений виртуальной реальности. Аванго использует язык программирования C+—h для определения двух категорий объектов - узлы и датчики. Узлы составляют объектно-ориентированный граф сцены, который осуществляет представление изображаемой геометрической модели. Датчики обеспечивают связь с реальным миром и используются для ввода данных с внешних устройств в приложение. Все объекты Аванго -полевые контейнеры, представляющие информацию о своем состоянии в виде совокупности полей. Аванго использует язык сценариев Scheme [13] для объединения объектов в граф сцены, а также вводит понятие графа потоков данных, концептуально ортогонального графу сцены и служащего для определения взаимодействия между обьектами, а также для ввода в сцену реальных данных, необходимых для моделирования интерактивного поведения. Объекты Аванго обладают универсальным потоковым интерфейсом, который позволяет записывать в поток сами обьекты и информацию об их состоянии и впоследствии реконструировать эти данные из потока. Этот интерфейс является одним из основных строительных блоков, используемых для реализации распределения объектов. Распределенные обьекты Аванго создаются в распределенных сегментах общедоступной памяти (distributed shared memory), которые поддерживаются синхронизаванными посредством сетевой инфраструктуры нижнего уровня. Такая модель обеспечивает требуемую прозрачность сети, чтобы объекты были видимы всеми участвующими процессами и взаимодействовали так же эффективно, как и при исполнении на локальном компьютере.

Аванго основан на графической системе OpenGL Performer, которая обеспечивает наиболее качественное исполнение приложения, и удовлетворяет специальным требованиям, возникающим при разработке приложений для виртуального окружения. Если аппаратное обеспечение позволяет, Performer использует множественные процессоры и множественные графические конвейеры. Мы используем реализацию Аванго на графических станциях SGI и Linux-PC.

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

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

4 Реализация алгоритма исключения заслоненных объектов

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

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

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

av-mover

N

ОСНОВНОЙ БНШЕР

ПИ

--

ДАННЫЕ

точке зрения

дянные о видимости

гряф сцены

pfMaterial pfGeoSetcV'^cx-MflTeP'-'fl''^ pfGeoState

UICX . ГРЯф . модя.

КОНТРОЛЬНЫЙ БУШЕР

КОПИЯ ГРЯфЯ

pfGeode pfGeoSet

pfMaterial

pfGeoState

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

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

Операция гистограммирования, т.е. подсчет числа пикселей каждого цвета, присутствующих в буфере кадров, поддерживается большинством графических карт и может быть вызвана командой OpenGL glHistogram. Эта операция заполняет четыре отдельные одномерные гистограммы, соответствующие RGBA каналам, что дает возможность присвоить цветовые коды не более чем 255 х 4 = 1020 объектам (цвет фона не используется для кодирования). Аппаратная операция гистограммирования полноэкранного изображения требует довольно много времени, см. Таблицу 1.

Таблица 1: время, требуемое для операции гистограммирования

1024x768 экран 512x384 экран

аппарат. програм. аппарат. програм.

Onyx2 195MHz InfiniteReality2 41мс 36мс 17мс 15мс

Athlon 1.3GHz GeForce Quadro2Pro 86мс 87мс 17мс 25мс

N-1

гтвых _

Sn =

— N ^ ^вх

N Z^ п-к.

к=0

ле мы фактически выполняем статистическое уточнение входных данных по N измерениям для близких положений точки зрения. В результате этого выходные данные равны площадям, которые занимают объекты в контрольном буфере, известным с погрешностью .меньше одного пикселя (средне-квадратичная погрешность 5*ых ~ 1/%/Ж). Данный статистический механизм аналогичен технике устранения лестничных артефактов, эффективно увеличивающей разрешение экрана. Это достигается ценой небольшого увеличения консерватизма метода: те объекты, которые были видимыми, но стали скрытыми в результате перемещения камеры, в течение некоторого времени будут отрисовываться в скрытом состоянии.

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

Другая возможность - это копирование содержимого цветового буфера в оперативную память и выполнение его гистограммирования с помощью программного обеспечения. В этом случае может быть заполнена многомерная гистограмма (2D...4D), предоставляющая до 2564 — 1 « 4млрд. цветовых кодов, достаточных для любого приложения. Однако гистограммирование полного экрана с помощью программного обеспечения также требует много времени.

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

Фильтр низких частот усредняет входные данные 5*Пх (число пикселей каждого цвета на п-том кадре) на протяжении заданного числа кадров N:

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

Рис.2. Точность прогноза как функция опережения.

Прогнозирующие фильтры широко используются в приложениях, в частности, при отслеживании движения различных объектов для автономной и ассистируе-мой навигации [14]. Прогнозирующие алгоритмы включены в современные микропроцессоры для ускорения конвейера исполнения команд [15]. Аналогичные подходы также используются для стабилизации различных численных методов в теории динамических систем [16, 17]. В нашем случае, прогнозирующий фильтр используется для экстраполяции матрицы точки зрения на к будущих кадров. Для этой цели мы строим полином п-того порядка, приближающий р последних точек зрения методом наименьших квадратов, и продолжаем его в ближайшее будущее. Для достаточно гладкого движения, которое производит ау-шоувт, метод дает хороший прогноз при п = 2, р = 20. Точность метода представлена на рис.2. Здесь

^Ч = \ч измеренное — Ч предсказанноеI

- погрешность вращательной компоненты матрицы точки зрения в пространстве кватернионов, усредненное по N ~ 104 кадрам на протяжении 5 мин прогулки

о

о

k

k

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

Окончательно, решение о видимости объекта принимается, используя логическое или:

(^предыдущ > ^порог) или (^следукщ > ^порог),

где ¿пЫХдыдущ - ближайшие имеющиеся данные о видимости в прошлом, 5свлыехдующ - ближайшие данные в будущем, по отношению к настоящему моменту времени. В результате этого на пути камеры, соединяющем две точки, в которых имеются данные о видимости, объект считается видимым, если он видим по крайней мере в одной из этих точек. Это решение также ведет к небольшому увеличению консерватизма метода, включая в процесс отрисовки те объекты, которые невидимы в данный момент, но станут видимыми на следующих кадрах. Кроме того, в случае если объект становится видимым только на короткий промежуток времени между двумя последовательными контрольными точками, он не будет отрисован вообще. Эта ситуация, однако, встречается крайне редко и из-за короткого промежутка времени между контрольными точками 1/30 сек) визуально не воспринимается.

Замечание: Как дополнительный метод для ускорения отрисовки контрольного буфера можно использовать стандартный алгоритм переключения уровней детализации, чтобы исключить удаленные объекты, занимающие слишком малую площадь на экране (например Б < 0.01рх2) из процессов отрисовки контрольного буфера и, следовательно, основного буфера. Если в сцене присутствуют полупрозрачные объекты, их можно исключить из графа сцены контрольного буфера и безусловно отрисовать в основном буфере. Динамические объекты могут быть обработаны аналогично. Можно также включить динамические объекты в процесс отрисовки контрольного буфера, вводя для них необходимые опережающие фазовые сдвиги, если объекты двигаются по предопределенным траекториям или их движение достаточно регулярно, чтобы быть эффективно прогнозируемым.

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

5 Результаты

Для тестирования метода мы выполняем прогулку в модели древнего города Колония Ульпия Траяна (рис.3), созданной студентами строительного факультета университета г.Дортмунд [18]. Модель содержит 260тыс текстурированных треугольников в 1,200 объектах, и без ускорения отрисовывается на компьютере SGI/Onyx2 со скоростью 8 кадров в секунду. Рис.4 иллюстрирует результаты применения алгоритма по исключению заслоненных объектов для точки зрения, расположенной в левом нижнем углу изображения. Сцена слева была подвергнута только отбору по объему видимости и содержит 86тыс треугольников, в то время как сцена справа после отбора по объему видимости и исключения заслоненных объектов содержит всего 4тыс треугольников. Содержимое цветового буфера, использованного для измерения сложности по глубине, показано на рис.5. До исключения заслоненных объектов сложность по глубине сконцентрирована в узкой полосе вдоль горизонта, где достигает значений 30...46. После исключения заслоненных объектов сложность по глубине становится почти равномерно распределенной по площади экрана, нигде не превышая значение 9. Рис.7 представляет скорость кадров вдоль заданного пути камеры, проходящего вблизи сложного объекта. Без исключения заслоненных объектов скорость кадров изменяется значительно, обнаруживая перегрузку графики, в то время как исключение заслоненных объектов делает эту зависимость почти постоянной.

Факторы ускорения, измеренные для данной модели в различных конфигурациях аппаратуры, приводятся в таблице 2. Максимальное значение ускорения сильно зависит от состава модели и используемого графического аппаратного обеспечения. В частности, достаточно скрыть стеной очень сложный объект, чтобы уменьшить сложность по глубине в сотни или тысячи раз. Однако, время отрисовки в этом случае не будет уменьшено в то же самое число раз, поскольку при малых временах отрисовки важную роль начинает играть время заполнения (filling time) графической карты. Это время необходимо для отрисовки одной фасеты, спроецированной на полный экран (что составляет около 0.3 миллисекунд для 1024x768 экрана на графической карте InfiniteReality2). Сцены со сложностью по глубине, всюду по экрану равной единице, не могут быть отрисованы быстрее.

Рис.6 приводит внутреннюю статистику системы Performer для графических процессов до и после исключения заслоненных объектов. Жирная белая горизонтальная линия, помеченная "d-5", показывает фактическое время отрисовки. Используемые нами алгоритмы ускорения делают эту линию значительно короче. На правом изображении за этой линией следует

жирная серая линия, которая показывает время, необходимое аппаратуре для завершения процесса отрисов-ки, включающее, в частности, время заполнения.

Сравнение с другими техниками. Прежде всего необходимо подчеркнуть, что фактор ускорения для любой техники исключения заслоненных объектов сильно зависит от модели, используемой для тестирования. Модели, плотно заполненные заслоняющими друг друга объектами, такие как модели современных городов, демонстрируют лучшие характеристики. Приведенные ниже количественные характеристики дают широкую оценку возможностей для нескольких существующих техник, однако, они были получены разными исследовательскими группами для разных моделей. Работа [10] дает оценку факторов ускорения для трех техник в применении к модели из 750тыс примитивов при скорости обновления изображения 6Гц: анализ видимости в трафаретном буфере (1.12), анализ видимости в Z-буфере (1.148), использование НР-флага видимости (1.338). В работе [11] факторы ускорения 1.5...4 получены с использованием НР-флага для модели из 600тыс...11млн треугольников при 1..12Гц. Работа [7] представляет факторы ускорения 2.6... 7 для анализа видимости в трафаретном буфере, полученные на ряде моделей, содержащих 450тыс...5млн треугольников при скорости кадров 1...2Гц. В работе [5] использование Z-пирамид произвело фактор ускорения 5 для модели из 300тыс...1млн примитивов при 8..12Гц. Работа [3] приводит фактор ускорения 12 для модели из 1млн треугольников при 12Гц, полученный с помощью приоритетно-послойного проекционного алгоритма, используя прямое сканирование 512x512 цветового буфера, и в два раза меньшие характеристики для его аппаратурного гистограммирования. Работа [12] демонстрирует фактор ускорения 28 при 60Гц для урбанистической модели из 2млн примитивов, полученный с помощью распределенной схемы вычислений для 2.5-мерной техники анализа видимости.

Рис.3. Архитектурная модель, использованная для проверки алгоритма. Слева — изображение в основном буфере (до и после исключения заслоненных объектов получаются идентичные изображения), справа - изображение в контрольном буфере.

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

отмеченного окружностью слева внизу.

Рис.5. Распределение сложности по глубине: до (слева) и после (справа) использования алгоритма.

Рис.6. Статистика Performer для этих случаев (пояснения см. в тексте).

Таблица 2: факторы ускорения

ЧИСТОТА, Гц

Рис.7. Скорость кадров вдоль пути камеры.

основной буфер контрольный буфер фактор ускорения

2x1024x768 512x384 мин сред макс

Onyx2 300MHz Onyx2 195MHz 1.7 4 52*

InfiniteReality2 InfiniteReality2

активное стерео Athlon 1.3GHz GeForce Quadro2Pro 1.7 4 52*

HP 2GHz Athlon 1.3GHz

Fire GL4 GeForce Quadro2Pro 1.3 2.5 10*

пассивное стерео

* ограничено скоростью заполнения графической карты.

6 Заключение

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

Благодарность. Данная работа поддержана грантами РФФИ 01-07-90327 и 02-01-01139.

Список литературы

[1] H. Tramberend, Avocado: A Distributed Virtual Reality Framework, Proc. of the IEEE Virtual Reality, 1999.

[2] D. Luebke, C. Georges, Portals and mirrors: Simple, fast evaluation of potentially visible sets. 1995 Symposium on Interactive 3D Graphics, ACM SIGGRAPH, April 1995, pp.105-106.

[3] J. Klosowski, C. Silva, Efficient Conservative Visibility Culling using the Prioritized-Layered Projection Algorithm, IEEE Transactions on Visualization and Computer Graphics, Vol. 7, No. 4, 2001, pp. 365-379.

[4] N. Greene, M. Kass, G. Miller, Hierarchical Z-buffer visibility, SIGGRAPH'93, pp.231-236.

[5] H. Zhang, D. Manocha, T. Hudson, K.E. Hoff III. Visibility Culling Using Hierarchical Occlusion Maps. Computer Graphics (Proceedings of SIGGRAPH'97) pp.77-88, 1997.

[6] N. Scott, D. Olsen, E. Gannet, An Overview of the visualize fx graphics accelerator hardware. The Hewlett-Packard Journal, 28-34, May 1998.

[7] T. Hüttner, M. Meissner, D. Bartz. OpenGLassisted Visibility Queries of Large Polygonal Models. Technical Report WSI-98-6, ISSN 0946-3852, Dept. of Computer Science (WSI), University of Tuübingen, 1998.

[8] D. Cohen-Or, Y. Chrysanthou, C.T. Silva. A survey of visibility for walkthrough applications. Proc. of EUROGRAPHICS'00, course notes, 2000.

[9] Silicon Graphics Inc. OpenGL Optimizer Programmer's Guide. Technical Report, 1998.

[10] D.S. Staneker, A first step towards occlusion culling in OpenSG PLUS, in Proc. of the 1st OpenSG Symposium, 2002.

[11] D. Bartz et al, Jupiter: A Toolkit for Interactive Large Model Visualization, Proc. of Symposium on Parallel and Large Data Visualization and Graphics, pp.129134, 2001.

[12] P. Wonka, M. Wimmer, and F. Sillion. Instant Visibility. in Proc. Eurographics 2001.

[13] R. Kent Dybwig. The Scheme programming language: ANSI Scheme. P T R Prentice-Hall, Englewood Cliffs, NJ 07632, USA, Edition 2, 1996.

[14] G. Welch, G. Bishop. An introduction to the Kalman filter, ACM SIGGRAPH'2001, Course 8.

[15] M. Evers et al, Analysis of Correlation and Predictability: What Makes Two-Level Branch Predictors Work, Proceedings of the 25th International Symposium on Computer Architecture, Barcelona, June 1998, pp.52-61.

[16] S.V. Klimenko, I.N. Nikitin, W.F. Urazmetov. Methods of numerical analysis of 1-dimensional 2-body problem in Wheeler-Feynman electrodynamics, Computer Physics Communications, Vol.126 (2000) pp. 82-87.

[17] G. Hirota, S. Fisher, M. Lin, Simulation of Non-penetrating Elastic Bodies Using Distance Fields. UNC Technical Report TR00-018, 2000.

[18] домашняя страничка проекта Xanten: http://viswiz.imk.fraunhofer.de/~lia/xanten