Исследование и разработка методов визуализации деформируемых поверхностей в стерео-проекционных системах тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Сенин, Михаил Андреевич

• Сенин, Михаил Андреевич
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Сенин, Михаил Андреевич

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Сенин, Михаил Андреевич, 2005 год

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.