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

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

Сенин Михаил Андреевич

Исследование и разработка методов визуализации деформируемых поверхностей в стерео-проекционных системах

Специальность: 05.13.18 — математическое моделирование, численные методы и комплексы программ

Автореферат

диссертации на соискание учёной степени кандидата физико-математических наук

Москва - 2005

Работа выполнена на кафедре системной интеграции и менеджмента Московского физико-технического института (ГУ).

Научный руководитель: доктор физико-математических наук,

профессор Клименко Станислав Владимирович

Официальные оппоненты: доктор физико-математических наук,

профессор Столяров Лев Николаевич

кандидат физико-математических наук Иванов Денис Владимирович

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

Институт прикладной математики им.М.В.Келдыша РАН

Защита состоится

2005г. в

43.

часов на заседании диссертационного совета К 212.156.02 при Московском физико-техническом институте (ГУ) по адресу: 141700, г.Долгопрудный, Московской обл., Институтский пер., д. 9

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

Автореферат разослан «_ • »

005г.

Учёный секретарь диссертационного совета кандидат физико-математических наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Стерео 3D системы применяются при разработке приложений, в которых необходимо создание иллюзии реальности. Исследования в области психологии восприятия1 показывают, что бинокулярность зрения играет второстепенную роль при определении размеров объектов удалённых более чем на 5 м. Гораздо больший вклад даёт загораживание, эффект двигательного параллакса и перспективы (см. рис. 1). Однако при восприятии близких объектов бинокулярное расхождение становится одним из основных механизмов определения глубины пространства.

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

Перечисленные выше приложения имеют демонстрационный харак-

'P. Vishton J. Cutting. Perception of Space and Motion, chapter Perceiving Layout and Knowing Distance: The Integration, Relative Potency and Contextual use of Different Information about Depth., pages 69-118. New York: Academic Press, 1995.

1 10 100 1000 10000 расстояние от наблюдателя, н

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

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

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

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

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

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

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

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

- разработка математической модели деформируемых объектов демонстрируемых в стерео-проекционных системах;

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

- разработка алгоритма реконструкции поверхностей и изображе-

ний;

- разработка алгоритма сглаживания поверхностей;

- разработка алгоритма регистрации столкновений деформируемых поверхностей;

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

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

Практическая ценность: Разработанные алгоритмы могут быть использованы при построении стерео-проекционных систем, а также при подготовке моделей для 3D сцен, и потому имеют большую практическую ценность. Применение общедоступных стерео-проекционных систем в учебном процессе позволяет существенно обогатить лекционный материал. Установки такого типа и разработанные для них методы визуализации и программное обеспечение могут быть использованы в научно-исследовательских институтах, образовательных центрах для решения самых разнообразных задач: моделирование чрезвычайных ситуаций; визуализация моделей космических аппаратов, создание моделей лабораторий и их дистанционное управление; визуализация в авиационной, автомобильной, судостроительной промышленности (обтекание, окраска, интерьер и пр.); визуализация в системах конструирования, быстрого макетирования и анимации; визуализация в медицине и

2Н. Wendland. Piecewisepolynomial, positive defined and compactly supported radial functions of minimal degree. AICM, 4:389-396, 1995.

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

Автор защищает:

1. математическая модель деформируемых объектов демонстрируемых в стерео-проекционных системах;

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

3 алгоритм локальной реконструкции поверхностей и изображений;

4 алгоритм сглаживания поверхностей,

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

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

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

Апробация работы. Материал диссертации опубликован в работах [1-8], а также докладывался и обсуждался на международных научных конференциях Eurographics 2002 (Германия, Саарбрюккен, Сентябрь 2002), 5-th International Conference on Humans and Computers HС2002 (Япония, Аизу-Вакаматсу, Сентябрь 2002), International Workshop on Geometric Modeling, Computing, and Visualization (Япония, Аизу-Вака-матсу, Июль 2003), Eurographics 2003 (Испания, Гранада, Сентябрь 2003), XLVII научная конференция МФТИ (2004).

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

комплекса ПО включающего перечисленные алгоритмы, адаптированные для применения в стерео-проекционных системах.

Структура диссертации. Диссертационная работа изложена на 118 страницах, состоит из введения, трёх глав и заключения, содержит 37 иллюстраций, б таблиц и список цитируемой литературы, содержащий 127 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе представлены наиболее известные крупномасштабные стерео-проекционные системы. Такие системы позволяют обеспечить отдельных пользователей или группы учёных, инженеров, дизайнеров рабочим пространством, в котором они могут наблюдать, исследовать и создавать в режиме реального времени необходимые им данные. Большинство таких систем имеет сходную аппаратную конфигурацию. Центральное место занимают: графический обработчик — SGI суперкомпьютер или кластер на базе Linux PC, который обрабатывает данные, и проекционная система, которая отображает их на экран. В некоторые системы также включается устройство слежения, которое измеряет положение и ориентацию головы пользователя, позволяя вычислять правильное изображение соответствующее текущему положению пользователя.

(а) (б)

Рис. 2: Принципиальные схемы пассивных мобильных стерео-проекционных систем- (а) обратная проекция, (б) прямая проекция. Обозначения: (1) графический вычислитель; (2) вычислитель для синтеза звука; (3) экран; (4,5) проекторы; (6,7) аудио-система; (8) устройства управления.

Рис. 3: Система Teleport. Рис. 4: Система VEonPC.

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

Во втором разделе первой главы описана системы разработки распределённых стерео 3D приложений Avango3. Система обеспечивает разработчиков концепцией общего графа сцены, доступного всем процессам образующим распределённое приложение. Каждый процесс обладает локальной копией графа сцены и содержащейся в нём информации о состоянии, которая поддерживается синхронизированной.

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

В первом разделе второй главы описан разработанный автором алгоритм быстрого вычисления гладких, локальных и интуитивно ожидаемых деформаций, заданных небольшим количеством контрольных векторов, который основан на использовании базиса радиальных функций с компактным носителем (compactly supported radial basis function — CSRBF), и позволяет производить вычисления деформации поверхности в реальном времени.

В подразделе 1 даётся обзор основных методов деформации поверхности, а именно: (1) отображение пространства на себя, (2) метаморфоза и (3) модификация определяющих функций. Проводится анализ досто-

3Н Tramberend. Avocado: A distributed virtual reality framework. In Proc. IEEE VR, 1999.

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

В подразделе 2 изложена общая схема алгоритма деформации поверхности методом пространственного отображения, основанного на использовании базиса радиальных функций с компактным носителем. Для набора контрольных векторов, заданного множеством /V различных контрольных точек X — {£1,..., х/у} С Мп, и векторами смещения БХ — в этих точках, отображение конструирует-

ся из п отображений К" —> Ш. Отображение Тк для к-ой координаты (1 ^ к ^ п) строится как интерполяция с использованием функций радиального базиса и имеет вид Т^хО?) = аь¥>(1|£ - х,||), где

|| ■ || — стандартная Евклидова норма в К", а у — базисная радиальная функция. Коэффициенты п^ определяются из условия интерполяции - <ЙЪ> < п путём решения системы линейных

алгебраических уравнений (СЛАУ).

Матрица полученной системы будет симметричной, а при использовании if имеющих ограниченный радиус поддержки ещё и разреженной. Существуют быстрые алгоритмы решения систем уравнений заданных такими матрицами. Это позволяет значительно уменьшить время вычислений и делает возможными выполнять их в режиме реального времени. Кроме того, уменьшается количество памяти, необходимое для хранения матрицы.

й = 1 </>1,0 = (1 - г) + с0

92,1 = (1-г)+(Зг+1) с'2

П,2 = (1-ГЦ18г2 + 5Г + 1) С4

<¿ = 3 ¥>2,0 = (1 - г)I Си

УЗ,1 = (1-г)4+(4Г+1) С"

</>4,2 = (1-ГШ35г2 + 18г + 3) с4

¥>5.з = (1 - г)1 (32га + 25г2 + 8г + 1) св

¿ = 5 ¥>з,о = (1 - 0+ с°

¥>4,1 = (1-г) + (5г + 1) с*

¥>5,2 = (1 — г)+(16г2 + 7г + 1) с4

Таблица 1: Базовые функции для К*2. «=» — равенство с точностью до положительной константы, — используются лишь значения

В работе использовались функции, предложенные Вендландом (см. сноску 2 на стр. 4). Эти кусочные полиномиальные базисные функции

обеспечивают заданную гладкость для пространства заданной размерности, функции сконструированы таким образом, что матрица полученной системы будет положительно определённой. В таблице 1 представлены некоторые функции для I1, К3 и I5.

В подразделе 3 дано подробное описание алгоритма, состоящего из следующих частей: (1) сортировка входных данных, (2) конструирование СЛАУ, (3) решение СЛАУ, (4) выполнение преобразования. Подраздел 4 содержит описание программной реализации предложенного алгоритма, а подраздел 5 — результаты его применения.

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

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

В подразделе 2 дано детальное описание алгоритма. В случае восстановления отсутствующих участков поверхности алгоритм включает следующие шаги: (1) определение граничных рёбер, связывание их в граничные контуры, выделение простых контуров, (2) применение алгоритма грубого восстановления, (3) линейное разбиение (subdivision) граней грубо восстановленной поверхности, (4) применение алгоритма корректировки для каждой вершины восстановленной поверхности: (4а) нахождение опорных вершин и вычисление нормали к касательной плоскости, (4б) определение CSRBF-отображения, (4в) применение CSRBF-отображения.

Подраздел 3 содержит результаты использования алгоритма.

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

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

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

Подраздел 3 содержит результаты использования алгоритма. Алгоритм выполняет интерактивное сглаживание сложных моделей (более 50 тыс. треугольников) без предобработки. Алгоритм демонстрирует на практике свойства сохранения характерных особенностей и объема модели.

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

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

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

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

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

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

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

CSRBF-Core — программный комплекс для построения приложений, использующих CSRBF-деформации. ПО представляет собой библиотеку, написанную на языке C + + и включает следующую функциональность:

• построение СЛАУ по набору контрольных векторов;

• решение СЛАУ, одним из включённых в библиотеку методов, либо путём использования внешнего ПО;

• импорт/экспорт полученной деформации;

• выполнение CSRBF-деформации для набора вершин, или для произвольной точки.

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

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

Редактор 3D деформаций — приложение, разработанное в системе Avango с использованием библиотеки CSRBF-Core. Редактор позволяет создавать, просматривать и сохранять деформации, для которых могут быть заданы такие параметры воспроизведения, как длительность, цикличность, начальная и конечная фазы.

Corrector — приложение, производящее коррекцию и/или восстановление участков трёхмерных полигональных поверхностей. Приложение

Рис. 6: (а) — редактор 3D CSRBF-деформаций, (b) — использование модели.

также позволяет выполнять интерактивное сглаживание моделей. Приложение использует библиотеку CSRBF-Core.

Image Transformer — редактор 2D деформаций. Приложение было разработано на языке Java и использует (через JNI) библиотеку CSRBF-Core. Приложение аналогично редактору 3D деформаций, но предназначено для обработки 2D-изображений. Приложение позволяет создавать, просматривать и сохранять CSRBF-деформации.

ПО для восстановления фотографий. Приложение представляет собой встраиваемое расширение (plug-in) для коммерческого растрового редактора Adobe Photoshop и позволяет устранять различные дефекты изображений, а также убирать с изображений текст (рис. 9).

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

(a) (b)

Рис. 7: Приложение Corrector, (a) — выбор опорной зоны при корректировке, (b) — пример сглаженной модели.

(а) (Ь)

Рис. 8: Приложение Image Transformer, (а) до деформации, (b) после деформации.

Автором разработаны:

1. математическая модель деформируемых объектов, демонстрируемых в стерео-проекционных системах;

2. алгоритм гладкой локальной деформации поверхности;

3. алгоритм реконструкции поверхностей и изображений;

4. алгоритм сглаживания поверхностей;

5. алгоритм регистрации столкновений деформируемых моделей;

6. комплекс программ, включающий перечисленные алгоритмы, адаптированные для применения в стерео-проекционных системах.

(a) (b)

Рис. 9: Работа с расширением в Adobe Photoshop, (a) — исходное изображение, (b) — восстановленное изображение.

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

По теме диссертации опубликованы следующие работы:

1. М.А. Сенин, Н.Е. Кожекин, В.В. Савченко. Деформация поверхностей на основе функций радиального базиса с компактным носителем. // Исследовано в России, С. 1982-1991, 2004. http://zhurnal.ape.relarn.ru/articles/2004/186.pdf.

2. М.А. Сенин. Алгоритмы обработки 3d моделей на основе csrbf. // Труды XLVII научной конференции МФТИ, С. 109-123. Изд. МФТИ, Москва, 2004.

3. N. Kojekine, V. Savchenko, M. Senin, I. Hagiwara. An approach to surface retouching and mesh smoothing. // The Visual Computer Journal, 19(7-8):549-564, 2003.

4. M. Senin, N. Kojekine, V Savchenko, I. Hagiwara. Particle-based collision detection. // Short papers proceedings of Eurographics 2003, pages 1-6, 2003. Spain, Granada, September 1-6.

5. N. Kojekine, V. Savchenko, M. Senin, I. Hagiwara. An algorithm for polygonal surface stitching. // Proceedings of Computational Engineering Conference, volume 8, pages 63-74, 2003.

6. TV Kojekine, V. Savchenko, M. Senin, I. Hagiwara. A prototype system for character animation based on real-time csrbf deformations. // Proceedings of The 5-th International Conference on Humans and Computers, pages 82-86, 2002.

7. N. Kojekine, V. Savchenko, M. Senin, I. Hagiwara. A prototype system for character animation based on real-time deformations. // The Journal of Three Dimensional Images, 16(4):91-95, 2002.

8. N. Kojekine, V. Savchenko, M. Senin, I. Hagiwara. Real-time 3d deformations by means of compactly supported radial basis functions. // Proceedings of Eurographics EG2002, short papers, pages 35-43, 2002.

М.А. Сенин.

Исследование и разработка методов визуализации деформируемых поверхностей в стерео-проекционных системах.

Подписано к печати 21.02.05. Печать офсетная. Формат 60x84/16. Печ. л. 1,0. Тираж 100 экз. Заказ 11.

ОНТИ ГНЦ РФ «Институт физики высоких энергий» 142281, Протвино Московской обл.

05~,l¿ -(?5',¡3

* f S r / '

2 7 CAP

2305

1 Крупномасштабные стерео-проекционные системы

1 Аппаратные конфигурации.

1.1 CyberStage.

1.2 i-CONE.

1.3 Responsive Workbench.

1.4 Teleport.

1.5 VeonPC.

2 Программная среда Avango.

2.1 Основные принципы.

2 Методы визуализации в стерео-проекционных системах, разработанные автором

1 Деформация поверхностей.

1.1 Обзор.

1.2 Деформация поверхности с использованием CSRBF

1.3 Описание алгоритма.

1.4 Программное обеспечение

1.5 Результаты.

2.2 Обзор.•.52

2.3 Алгоритм корректировки поверхности.56

2.4 Алгоритм восстановления поверхности.58

2.5 Результаты.60

3 Сглаживание поверхностей.65

3.1 Сглаживание поверхности .65

3.2 Обзор.66

3.3 Алгоритм.67

3.4 Результаты.68

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

4.1 Введение.72

4.2 Предыдущие работы.74

4.3 Алгоритм.77

4.4 Программная реализация.83

4.5 Отклик.84

4.6 Результаты.85

3 Примеры использования разработанных методов 88

1 ПО для выполнения CSRBF-деформаций .88

2 ПО для регистрации столкновений.90

3 Редактор 3D деформаций .91

4 Комплекс ПО для подготовки 3D моделей.92

5 Редактор 2D деформаций .94

6 ПО для восстановления фотографий.95

Введение

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

Стерео 3D системы применяются при разработке приложений, в которых необходимо создание иллюзии реальности. Исследования в области психологии восприятия [1] показывают, что бинокуляр-ность зрения играет второстепенную роль при определении размеров объектов удалённых более чем на 5 м. Гораздо больший вклад даёт загораживание, эффект двигательного параллакса и перспективы (см. рис. 1). Однако при восприятии близких объектов бинокулярное расхождение становится одним из основных механизмов определения глубины пространства. расстояние опт наблюдателя, м

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

Автор представляет существующие крупномасштабные стерео-проекционные системы, описывает программную среду, необходимую для создания 3D сцен для таких систем, а также ряд разработанных при участии автора алгоритмов и программных комплексов [2-10], использующихся при создании программного обеспечения (ПО) для стерео-проекционных систем.

Стерео-проекционные системы обеспечивают отдельных пользователей. или группы ученых, инженеров, дизайнеров виртуальным рабочим пространством, в котором они могут наблюдать, исследовать и создавать в реальном времени необходимые им сложные данные. Большинство таких систем имеют сходную аппаратную конфигурацию (см. работы [11-13]). Центральное место занимают: графический обработчик — SGI суперкомпьютер или Linux кластер, который обрабатывает данные, и проекционная система, которая отображает данные на экран. Кроме того, обычно используется специальное устройство слежения, которое измеряет положение и ориентацию головы пользователя. Данные, произведенные устройством слежения, читаются графическим обработчиком, и используются для определения перспективно правильного изображения для текущего положения пользователя. Описание наиболее известных крупномасштабных стерео-проекционных систем дано в главе 1, разделе 1.

Системы ПО для стерео-проекционных систем (см. работы [1420]) обеспечивают разработчика высокоуровневым интерфейсом, позволяющим представлять сложные геометрические модели в виде графа сцены. Разработчик отгорожен от деталей взаимодействия с низкоуровневой графикой и может сконцентрироваться на разработке собственно приложения. Одной из таких высокоэффективных сред является Avango [14]. Эта система обеспечивает разработчиков концепцией обобществлённого графа сцены, доступного всем процессам, образующим распределенное приложение. Каждый процесс обладает локальной копией графа сцены и содержащейся в нем информации о состоянии, которая поддерживается синхронизированной. Разработка таких распределенных приложений особенно необходима для реализации виртуальных окружений на кластерах Linux PC. Структура системы Avango описана в главе 1, разделе 2 настоящей работы.

Основная цель нашей работы — разработка комплекса ПО, который может быть использован при создании недорогой стерео-проекционной системы для лекторского зала на базе Linux кластера. Применение таких систем в учебном процессе позволяет существенно обогатить лекционный материал. Установки такого типа, разработанные для них методы визуализации и программное обеспечение могут быть использованы в научно-исследовательских институтах, образовательных центрах для решения самых разнообразных задач: моделирование чрезвычайных ситуаций; визуализация моделей космических аппаратов, создание моделей лабораторий и их дистанционное управление; визуализация в авиационной, автомобильной, судостроительной промышленности (обтекание, окраска, интерьер и пр.); визуализация в системах конструирования, быстрого макетирования и анимации; визуализация в медицине и создание медицинских тренажёров; создание моделей музеев, планетариев, лекционных залов; реконструкция в археологии и туризме (моделирование древних и современных городов); синтетическое искусство, телевидение и кино, компьютерные игры; и др.

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

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

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

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

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

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

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

Все методы, разработанные автором, за исключением метода регистрации столкновений, связаны с применением функций радиального базиса с компактным носителем (compactly supported radial basis functions — CSRBF) [21] к задачам деформации, восстановления, сглаживания и пересечения полигональных поверхностей, возникающих в процессе подготовки и использования полигональных моделей в системах виртуального окружения. Общий подход к решению различных задач позволяет существенно сократить программную реализацию. Фактически реализация представленных ниже методов имеет общее ядро, которое многократно переиспользуется в различных алгоритмах.

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

Результаты работы алгоритма в двумерном случае представлены на рисунке 2.10 на стр. 60. На рисунке 2.10 (а) представлено поврежденное изображение стрекозы. На рисунке 2.10 (Ь) представлен результат глобальной реконструкции. Размер изображения 550 х 388. Размер опорной зоны составляет 580 пикселей, размер восстанавливаемой зоны — 380 пикселей. Распределение времени работы алгоритма представлено на таблице 2.3.

I [Ж

• Г Л f •М

Рис. 2.10: Пример восстановления изображения («Стрекоза»),

Рисунок 2.11 демонстрирует работу алгоритма при исправлении искусственно поврежденного текстурного изображения. При вос

Стадия алгоритма Время (сек.)

Сортировка входных данных 0.02

Решение СЛАУ 0,02

Применение CSRBF отображения 0,02

Суммарное время 0,06

Заключение

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

Автором разработаны:

• математическая модель деформируемых объектов, демонстрируемых в стерео-проекционных системах;

• алгоритм гладкой локальной деформации поверхности, основанный на использовании базиса радиальных функций с компактным носителем;

• алгоритм реконструкции поверхностей и изображений;

• алгоритм сглаживания поверхностей;

• алгоритм регистрации столкновений деформируемых поверхностей;

• обобщённый программный модуль для вычисления гладких локальных деформаций;

• программный модуль для регистрации столкновений деформируемых моделей;

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

Благодарности

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

1. P. Vishton J. Cutting. Perception of Space and Motion, chapter Perceiving Layout and Knowing Distance: The 1.tegration, Relative Potency and Contextual use of Different Information about Depth., pages 69-118. New York: Academic Press, 1995.

2. M.A. Сепии, H.E. Кожекин, В.В. Савченко. Деформация поверхностей на основе функций радиального базиса с компактным носителем. // Исследовно в России, pages 1982-1991, 2004. http://zhurnal.ape.relarn.ru/articles/2004/186.pdf.

3. M.A. Сенин. Алгоритмы обработки 3d моделей на основе csrbf. // Труды XLVII научной конференции МФТИ, pages 109-123. Изд. МФТИ, Москва, 2004.

4. N. Kojekine, V. Savchenko, М. Senin, I. Hagiwara. An approach to surface retouching and mesh smoothing. // The Visual Computer Journal, 19(7-8):549-564, 2003.

5. M. Senin, N. Kojekine, V. Savchenko, I. Hagiwara. Particle-based collision detection. // Short papers proceedings of Eurographics 2003, 2003. Spain, Granada, September 1-6.

6. N. Kojekine, V. Savchenko, M. Senin, I. Hagiwara. Smooth local deformations and particle based collision detection. // International Workshop on Geometric Modeling, Computing,and Visualization, 2003. Aizu-Wakamatsu, Japan, 12-15 July 2003.

7. N. Kojekine, V. Savchenko, M. Senin, I. Hagiwara. An algorithm for polygonal surface stitching. // Proceedings of Computational Engineering Conference, volume 8, 2003.

8. N. Kojekine, V. Savchenko, M. Senin, I. Hagiwara. A prototype system for character animation based on real-time csrbf deformations. // Proceedings of The 5-th International Conference on Humans and Computers, pages 82-86, 2002.

9. N. Kojekine, V. Savchenko, M. Senin, I. Hagiwara. A prototype system for character animation based on real-time deformations. // The Journal of Three Dimensional Images, 16(4):91-95, 2002.

10. N. Kojekine, V. Savchenko, M. Senin, I. Hagiwara. Real-time 3d deformations by means of compactly supported radial basis functions. // Proceedings of Eurographics EG2002, short papers, pages 35-43, 2002.

11. G. Eckel, M. Gobel, F. Hasenbrink, W. Heiden, U. Lechner, H. Tramberend, G. Wesche, J. Wind. Benches and caves. // H.J. Bullinger O. Riedel, editors, Proceedings 1st Int. Immersive Projection Technology Workshop, 1997.

12. Домашняя страничка Фраунгоферовского Института Медиа-коммуникаций. http://www.imk.fraunhofer.de.

13. Портвино, Институт Физико-Технической Информатики. Труды 1-ой Международной Конференции По Системам Виртуального Окружения На Кластерах Персональных Компьютеров. VE on PC 2001, 2001.

14. H. Tramberend. Avocado: A distributed virtual reality framework. // Proceedings of the IEEE Virtual Reality, 1999.

15. J. Rohlf J. Helman. Iris performer: A high performance multiprocessing toolkit for real time 3d graphics. //A. Glassner, editor, Proceedings of SIGGRAPH'94, pages 381-395, 1994.

16. J. Wernecke Open Inventor Architecture Group. The Inventor Mentor: Programming Object-Oriented 3D Graphics with Open Inventor, volume Release 2. Addison-Wesley, Reading, Massachusetts, 1994.

17. R. Carey G. Bell The VRML 2.0 Annotated Reference Manual. Addison-Wesley, Reading, MA, USA, 1997.

18. Silicon Graphics Inc. OpenGL Optimizer Programmer's Guide, 1998.

19. D.S. Staneker. A first step towards occlusion culling in opensg plus. // Proceedings of the 1st OpenSG Symposium, 2002.

20. D. Bartz et al. Jupiter: A toolkit for interactive large model visualization. // Proceedings of Symposium on Parallel and Large Data Visualization and Graphics, pages 129-134, 2001.

21. H. Wendland. Piecewise polynomial, positive defined and compactly supported radial functions of minimal degree. // AICM, 4:389-396, 1995.

22. Barco projection systems web page, http://www.barco.com/pro-j ection systems.

23. E.J. Wegman et al. The minicave — a voice-controlled ipt enviroment. // H.-J. Bullinger O. Riedel, editors, Proceedings of 3d Int. Immersive Projection Technology Workshop, pages 179-190. Springer-Verlag, Berlin, 1999.

24. I. McDowall M. Bolas. Revieweing single and multiple viewer stereo with dpi projectors. // Proceedings of 7th Annual Symposium on Immersion Projection Technologies, IPT 2002, 2002.

25. Tan infitec tm stereo viewing, домашняя страничка компании tan. http://www.tan.de/english/prod/infitec.html.

26. J.S. Lipscomb W.L. Wooten. Reducing crosstalk between stereoscopic views. // Proceedings of SPIE (Stereoscopic Displays and Virtual Reality SystemsII), volume 2409, pages 31-40, 1995.

27. J. Konrad et al. Cancellation of image crosstalk in time-sequential displays of stereoscopic video. // IEEE Transactions On Image Processing, 9(5):897-908, 2000.

28. R.K. Dybvig. The Scheme programming language: ANSI Scheme. PTR Prentice-Hall, Engewood Cliffs, NJ 07632, USA, second edition, 1996.

29. V. Savchenko A. Pasko. Transformation of functionally defined shapes by extended space mappings. // The Visual Computer, 14:257-270, 1998.

30. T.W. Sederberg S.R. Parry. Free-form deformation of solid geometric models. // Computer Graphics, 20(4):151-160, 1986.

31. S. Coquillart. Extended free-form deformation: a sculpting tool for 3d geometric modeling. // Computer Graphics, 24(4):187-196, 1990.

32. S. Coquillart P. Jancen. Animated free-form deformation: an interactive animation technique. // Computer Graphics, 25(4):23-26, 1991.

33. W.M. Hsu, G.F. Hughes, H. Kaufman. Direct manipulation of free-form deformations. // Computer Graphics, 26(2):177-184, 1992.

34. P. Borrel D. Bechmann. Deformation of n-dimensional objects. // International Journal of Computational Geometry and Applications, l(4):427-453, 1991.

35. P. Borrel A. Rappoport. Simple constrained deformations for geometric modeling and interactive design. // ACM Transactions on Graphics, 13(2): 137-155, 1994.

36. D. Bechmann. Space deformation models survey. // Computers & Graphics, 18(4):571-586, 1994.

37. J.H. Ahlberg, E.N. Nilson, J.L. Walsh. The theory of splines and their applications. // Academic Press, New York, 1967.

38. J. Dushon. Constructive Theory of Functions of Several Variables, chapter Splines Minimizing Rotation Invariants Semi-Norms in Sobolev Spaces, pages 85-100. Springer-Verlag, 1976.

39. B.A. Василенко. Сплайн-функции: Теория, Алгоритмы, Программы. Новосибирск, Наука, 1983.

40. R.M. Bolle B.C. Vemuri. On three-dimensional surface reconstruction methods. // IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(1):1—13, 1991.

41. G. Greiner. Wavelets, Images and Surface Fitting, chapter Surface Construction Based on Variational Principles, pages 277-286. AL Peters Ltd., 1994.

42. F.L. Bookstein. Principal warps: Thin plate splines and the decomposition of deformations. // IEEE Transactions on Pattern Analysis and Mashine Intelligence, ll(6):567-585, 1989.

43. F.L. Bookstein. Morphometric Tools for Landmark Data. Cambridge University Press, 1991.

44. F.L. Bookstein. Two shape metrics for biomedical outline data: Bending energy, procrustes distance, and the biometrical modeling of shape phenomena. // Proc. Shape Modeling Conference (SMIA'97), pages 110-120, 1997.

45. J. Moody. Fast learning in networks of locally-tuned processing units. // Neural Computation, 1:281-294, 1989.

46. S. Haykin. Neural Networks: A comprehensive Foundation. Upper Saddle River, NJ: Prentice Hall, 1994.

47. A.G. Bors. Minimal topology for a radial basis function neural network for pattern classification. // Digital Signal Processing, 4, 1989.

48. S. Chen, C.F.N. Cowan, P.M. Grant. Orthogonal least squares learning algorithm for radial basis function networks. // Transactions on Neural Networks, 2(2):302-309, 1989.

49. M. Niranjan F. Fallside. Neural networks and radial basis functions in classifying static speech patterns. // Computer Speech and Language, 4:275-289, 1990.

50. P. Litwinovicz L. Williams. Animating images with drawing. // Computer Graphics (Proceedings of SIGGRAPH'94), pages 409-412, 1994.

51. J.C. Carr, W.R. Fright, R.K. Beatson. Surface interpolation with radial basis functions for medical imaging. // IEEE Transaction on Medical Imaging, 16(1):96-107, 1997.

52. R.K. Beatson W.A. Light. Fast evaluation of radial basis functions: Methods for 2-d polyharmonic splines. Technical

53. Report 119, Mathematics Department Univ. of Canterbury, New Zealand, 1994.

54. W. Light. Wavelets, Images and Surface Fitting, chapter Using Radial Functions on Compact Domains, pages 351-370. AL Peters Ltd., 1994.

55. J.C. Carr, T.J. Mitchell, R.K. Beatson, J.B. Cherrie, W.R. Fright, B.C. McCallumm, T.R. Evans. Reconstruction and representation of 3d objects with radial basis functions. // Computer Graphics, Proceedings SIGGRAPH'2001, pages 67-76, 2001.

56. L. Greengard V. Rokhlin. A fast algorithm for particle simulation. // Journal of Computational Physics, 73:325-348, 1997.

57. V. Savchenko L.Schmitt. Reconstructing occlusal surfaces of teeth using a genetic algorithm with simulated annealing type selection. // Proceeding of 6th ACM Symposium on Solid Modeling and Application, pages 39-46, 2001.

58. V. V. Savchenko, A.A. Pasko, T.L. Kunii, A.V. Savchenko. Multimedia Modeling, chapter Feature based sculpting of functionally defined 3D geometric objects, pages 341-348. Towards Information Superhighway, 1995.

59. S. Lee, G. Wolberg, S. Y. Shin. Scattered data interpolation with multilevel b-splines. // IEEE Transactions on Visualization and Computer Graphics, 3(3):228-244, 1997.

60. D. Thalmann, J. Shen, E. Chauvineau. Fast realistic human body deformations for animation and vr applications. // Computer Graphics International, pages 166-174, 1999.

61. P. Fua, R. Plankers, D. Thalmann. From synthesis to analysis: Fitting human animation models to image data. // Computer Graphics International, pages 4-11, 1999.

62. Y. Lee, D. Terzopoulos, K. Waters. Realistic modeling for facial animation. 11 SIGGRAPH'95 Proceedings, pages 191-198, 1995.

63. J. Bloomenthal C. Lim. Skeletal methods of shape manipulation. // Proceedings of International Conference on Shape Modeling and Applications, pages 44-47, 1997.

64. A. Verroust F. Lazarus. Extracting skeletal curves from 3d scattered data. // Proceedings of International Conference on Shape Modeling and Applications, pages 194-202, 1999.

65. H. Wendland. On the smoothness of positive definite and radial functions. // Journal of Computational and Applied Mathematics, 101:177-188, 1999.

66. H. Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1986.

67. N. Kojekine, V. Savchenko, D. Berzin, I. Hagiwara. Software tools for compactly supported radial basis functions. // Computer Graphics and Imaging, Proc. IASTED CGIM'2000, pages 234-239, 2001.

68. A. Jennings. A compact storage scheme for the solution of symmetric linear simultaneous equations. // Computational Journal, 9:281-285, 1966.

69. W.H. Press, S.A. Teukolsky, T. Vetterling, B.P. Flannery. Numerical Recipes in C. Cambridge University Press, 1997.

70. The visualization toolkit textbook and open source С++ library, with tcl, python, and java bindings. http://www.kitware.com/vtk.html, 2001.

71. K. Shoernake. Animating rotation with quaternion calculus. // ACM SIGGRAPH 1987, 1987.

72. M. Bertalmio, G. Sapiro, V. Caselles, C. Ballester. Image inpainting. // Computer Graphics (Proceedings of SIGGRAPH'OO), pages 417-424, 2000.

73. M.M. Oliveira, B. Bowen, R. McKenna, Y.S. Chang. Fast digital image inpainting. // Proceedings of the Visualization, Imaging, and Image Processing IASTED Conference, pages 261-266, 2001.

74. S. Esedoglu J. Shen. Image inpainting by the mumford-shah-euler model. IMA Preprint 1812, accepted for publication in European Journal for Applied Mathematics.

75. A. Sarti, R. Malladi, J.A. Sethian. Computing missing boundaries in images. // Proceedings of the Visualization, Imaging, and Image Processing IASTED Conference, pages 495-500. Marbella, Spain, 2001.

76. M.K. Gousie W.R. Franklin. Converting elevation contours to a grid. // Proceeding of the Eighth International Symposium on Spatial Data Handling (SDH), 1998. http://www.ecse.rpi.edu/Homepages/wrf.

77. B. Schneider. Geomorphologically sound reconstruction of digital terrain surface from contours. // Proceedings of 8th Symposium on Spatial Data Handling, Vancouver, Canada, pages 139-150, 1998. http://www.geo.unizh.ch/ benni.

78. V. Savchenko, A. Pasko, 0. Okunev, T. Kunii. Function representation of solids reconstructed from scattered surface points and contours. // Computer Graphics Forum, 14(4):181—188, 1995.

79. G. Turk J.F. O'Brien. Shape transformation using variational implicit functions. // Computer Graphics (Proceedings of SIGGRAPH'99), pages 335-342, 1999.

80. Y. Ohtake, A. Belyaev, H-P.Seidel. A multi-scale approach to 3d scattered data interpolation with compactly supported basis functions. // Proceedings of SMI'2003, 2003.

81. N. Kojekine V. Savchenko. Software tools using csrbfs for processing scattered data. // Computer & Graphics, 27:311-319, 2003.

82. G. Barequet M. Sharir. Filling gaps in the boundary of a polyhedron. Technical Report 277/93, Tel-Aviv University, Department of Computer Science, Israel, 1993.

83. T. Hermann, Z. Kovacs, T. Varady. Geometric Modeling: Theory and Practice, chapter Special applications in surface fitting, pages 14-31. Springer, 1997.

84. M.I.J. Bloor M.J. Wilson. Spectral approximation to pde surfaces. // Computer Aided Design, 28(3):145-152, 1996.

85. J. A. Setian. Geometry, Fluid Mechanics, Computer Vision, and Material Sciences, chapter Level Set Methods: Evolving Interfaces. Cambridge University Press, 1996.

86. R.T. Whitaker D.E. Breen. Level-set models for the deformation of solid objects. // Proceedings of Implicit Surface Conferece, pages 19-35, 1998.

87. N. Kojekine V. Savchenko. Using csrbfs for surface retouching. // Proceedings of The 2nd IASTED International Conference Visualization, Imaging and Image Processing VIIP2002, pages 613-618, 2002.

88. J. Davis, S.R. Marschner, M. Garr, M. Levoy. Filling holes in complex surfaces using volumetric diffusion. // Proceeding of the First International Symposium on 3D Data Processing, Visualization, Transmission, 2002.

89. H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, W. Stuetzle. Surface reconstruction from unorganized points. // Proceeding of SIGGRAPH'92, volume 26, pages 79-88, 1992.

90. G. Farin. Curves and Surfaces for CAGD. Academic Press, 1998.

91. P. Graven G. Washba. Smoothing noisy data with spline functions. // Numerical Mathematics, 31:377-403, 1979.

92. G. Taubin. A signal pcocessing approach to fair surface design. // Computer Graphics (Proceedings of SIGGRAPH'95), volume 29, pages 351-358, 1995.

93. M. Desbrun, M. Meyer, P. Schroder, A.H. Barr. Implicit fairing of irregular meshes using diffusion and curvature flow. 11 Computer Graphics (Proceedings of SIGGRAPH'99), 33:317-324, 1999.

94. J. Warren H. Weimer. Subdivision Metods for Geometric Design. Academic Press, 2002.

95. L. Kobbelt, S. Campagna, J. Vorsatz, H-P. Seidel. Interactive multi-resolution modeling on arbitrary meshes. // Computer Grafics (Proceeding of SIGGRAPH'98), volume 32, pages 105-114, 1998.

96. H. Zhang E. Fiume. Mesh smoothing with shape or feature presevation. //J. Vince R. Earnshaw, editors, Advances in Modeling, Animation and Rendering (Proceedings of CGI'02), pages 167-181. Springer, 2002.

97. H. Yagou, Y. Ohtake, A. Belyev. Mesh denosing via iterative alpha-trimming and nonlinear diffusion of normals with automatic thresholding. // CGI'2003, 2003.

98. M.C. Lin S. Gottschalk. Collision detection between geometric models: a survey. // Proceedings of IMA Conference, Mathematics of Surfaces VIII, 1998.

99. P. Hubbard. Approximating polyhedra with spheres for time-critical collision detection. // ACM Transactions on Graphics (TOG), 15(3):179—210, 1996.

100. S.A. Ehmann M. C. Lin. Accurate and fast proximity queries between polyhedra using convex surface decomposition. // Computer Graphics Forum, 20:500-510, 2001.

101. M.C. Lin D. Manocha. Efficient contact determination in dynamic environments. // International Journal of Computational Geometry and Applications (IJCGA), 7:123-151, 1997.

102. G. Zachmann. Rapid collision detection by dynamically aligned dop-trees. // Proceedings of IEEE Virtual Reality Annual International Symposium, pages 90-97, 1998.

103. S. Redon, A. Kheddar, S. Coquillart. Fast continuous collision detection between rigid bodies. // Computer Graphics Forum (Proc. of Eurographics '02), 21(3), 2002.

104. T. Larsson T. Akinine-Moller. Collision detection for continuously deforming bodies. // Proceedings of Eurographics, short presentations, pages 325-333, 2001.

105. G. van den Bergen. Efficient collision detection of complex deformable models using aabb trees. // Journal of Graphics Tools, 2(4):1—14, 1997.

106. I. Palmer R. Grimsdale. Collision detection for animation using sphere-trees. // Computer Graphics Forum, 14(2): 105-116, 1995.

107. S. Quinlan. Efficient distance computation between non-convex objects. // Proceedings of IEEE International Conference on Robotics and Automation, pages 3324-3329, 1994.

108. S. Krishnan, A. Pattekar, M. Lin, D. Manocha. Spherical shell: A higher order bounding volume for fast proximity queries. // In Proceedings of WAFR'98, pages 287-296, 1998.

109. J.D. Cohen, M.C. Lin, D. Manocha, M. Ponamgi. I-collide: an interactive and exact collision detection system for large-scale environments. // Proceedings of the Symposium on Interactive 3D Graphics, pages 189-196, 1995.

110. M. Held, J.T. Klosowski, , J.S.B. Mitchell Evaluation of collision detection methods for virtual reality fly-troughs. //

111. Proceedings Seventh Canadian Conference on Computational Geometry, pages 205-210, 1995.

112. J.T. Klosowski, M. Held, J. S. Mitchell, H. Sowrizal, K. Zikan. Efficient collision detection using bounding volume hierarchies of k-dops. // IEEE Transactions on Visualization and Computer Graphics, 4(l):21-36, 1998.

113. Taosong He. Fast collision detection using quospo trees. // Proceedings of the Symposium on Interactive 3D Graphics, pages 55-62, 1999.

114. S. Gottschalk, M.C. Lin, D. Manocha. Oobtree: A hierarchical structure for rapid interference detection. // ACM Computer Graphics (Proc. of SIGGRAPH'96), pages 171-180, 1996.

115. S. Bandi D. Thalmann. An adaptive spatial subdivision of the object space for fast collision of animated rigid bodies. // Proceedings of Eurographics '95, pages 259-270, 1995.

116. D.H. Eberly. 3D game engine design. Morgan Kaufmann Publisher, 2001.

117. M.-P. Cani C. Puech. Dynamic animation of deformable bodies. //P- Stucki S. Coquillart, W. Straber, editor, From Object Modelling to Advanced Visual Communication, Focus on Computer Graphics, pages 118-139. Springer-Verlag, 1994.

118. G. Zachmann. Minimal hierarchical collision detection. // Proceedings of the ACM Smposium on Virtual Reality Software and Technology, pages 121-128, 2002.

119. M. Moore J. Wilhelms. Collision detection and response for computer animation. // ACM Computer Graphics (Proc. of SIGGRAPH '88), 22(4):289-298, 1988.

120. A. Joukhadar, A. Scheuer, Ch. Laugier. Fast contact detection between moving deformable polyhedra. // Proceedings of the IEEE International Conference on Intelligent Robots and Systems, pages 1810-1815, 1999.

121. M. Hughes, M. Lin, D. Manocha, C. Dimattia. Efficient and accurate interference detection for polynomial deformation. // Proceedings of Computer Animation, pages 155-166, 1996.

122. B. Mirtich. V-clip: Fast and robust polyhedral collision detection. // ACM Transaction on Graphics, 17(3):177-208, 1998.

123. S. Cameron. Enhancing gjk: Computing minimum penetration distances between convex polyhedra. // Proceedings of International Conference on Robotics and Automation, pages 3112-3117, 1997.

124. Openrm scene graph library, http://openrm.sourceforge.net.

125. J.K. Hahn. Realistic animation of rigid bodies. // ACM Computer Graphics (Proc. of SIGGRAPH '88), 22(4):299-308, 1988.

126. Scalapack web page, http://www.netlib.org/scalapack/scala-packhome.html.