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

СПИСОК СОКРАЩЕНИЙ

ВВЕДЕНИЕ

1.ВИЗУАЛИЗАЦИЯ ТРЕХМЕРНЫХ ОБЪЕКТОВ С МНОЖЕСТВЕННЫМ РАЗРЕШЕНИЕМ

1.1.Визуализация рельефов

1.2.Цифровое представление рельефа местности

1.3.Количественная оценка аппроксимирующей триангуляции 20 1.3.1.Оценка погрешности аппроксимации 21 1.3.2.Оценка компактности триангуляции

1.4. Методы аппроксимации поверхностей и МР

1.4.1. Итерационные методы автоматической аппроксимации по принципу укрупнения

1.4.2. Итерационные методы автоматической аппроксимации по принципу уточнения

1 .б.Модели представления поверхности ТО с МР

1.5.1. Многослойные модели

1.5.2.Модели с МР поддерживающие переменное разрешение

1.6.Постановка задачи исследования

2.РАЗРАБОТКА АЛГОРИТМОВ ТРИАНГУЛЯЦИИ И МЕТОДА

РАНЖИРОВАНИЯ ОПОРНЫХ ТОЧЕК РЕЛЬЕФОВ

2.1.Систематизация методов аппроксимации поверхности трехмерных объектов рельефов

2.2.Построение триангуляционных нерегулярных сеток рельефов 60 2.2.1 .Триангуляция Делоне

2.2.2.Алгоритм добавления вершины в триангуляцию Делоне

2.2.3.Алгоритм обработки флипов 67 2.2.4Алгоритм удаления вершины из триангуляции Делоне

2.3.Метод итерационного ранжирования опорных точек рельефа 71 2.3.1 .Селекция кандидатов для удаления 73 2.3.2.Оценка стоимости удаления элементов аппроксимации 73 2.3.3.Алгоритм итерационного ранжирования опорных точек рельефа с использованием средних плоскостей

2.4. Алгоритмы автоматической генерализации ранжированных вершин рельефов

2.5.Выводы

3.АНАЛИЗ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ ТРИАНГУЛЯЦИИ И

АЛГОРИТМА РАНЖИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ СРЕДНИХ ПЛОСКОСТЕЙ

3.1.Теоретический анализ

3.1.1 .Оценка сложности

3.1.2.Оценка затрат памяти

3.2.Экспериментальное исследование

3.2.1.Оценка времени выполнения

3.2.2.Оценка качества результирующих аппроксимаций полученных на основе ранжирования

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

3.4.Выводы

4.РАЗРАБОТКА И ИССЛЕДОВАНИЕ АДАПТИВНОЙ СИСТЕМЫ

ВИЗУАЛИЗАЦИИ ПОВЕРХНОСТИ РЕЛЬЕФОВ С МР

4.1.Критический анализ иерархических моделей с МР

4.2.Вложенная модель рельефа с МР на основе адаптивной тесселяции

4.2.1.Компактная структура данных для хранения межуровневых иерархических связей

4.2.2.Построение макрорельефа

4.2.3.Уточнение макрорельефа путем адаптивной тесселяции

4.3.Адаптивная выборка элементов аппроксимации на основе иерархии смежных треугольников

4.3.1 .Адаптивная выборка ЭА с постоянной СД

4.3.2.Адаптивная выборка ЭА с переменной СД

4.4.Разработка системы адаптивной визуализации модели рельефов с МР

4.5.Анализ эффективности разработанной модели представления поверхности рельефов с МР при адаптивной визуализации

4.6.Выводы 147 5.ЗАКЛЮЧЕНИЕ

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

Решение задачи визуализации осуществляется методами компьютерной графики. После появления компьютерной графики еще в б 0-х годах были разработаны первые графические приложения: картографические системы, САПР и научно-исследовательские системы. Сегодня компьютерная графика широко применяется при реализации систем моделирования виртуальной реальности. Например, с помощью тренажеров специалисты проходят обучение, аттестацию и тренировку в лабораторных условиях, где моделируются стандартные и нестандартные ситуации. Основным требованием к таким системам является интерактивность1.

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

1 Система является интерактивной, если обеспечивает взаимодействие с пользователем и дискретность вывода изображений не заметна человеческому глазу. процессора обработки графических приложений. В настоящее время производительность ПК, оснащенных графическим процессором (ГП - его называют еще акселератором или ускорителем трехмерной графики), работающих по принципу аппаратной параллельно-конвейерной обработки, достигла достаточно высокого уровня. Например, ГП GeForce 2 GTS

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

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

С появлением ГП задача повышения эффективности интерактивных систем визуализации пространственных сцен не потеряла своей актуальности. При всех преимуществах применения ГП, для воспроизведения на экранах ПК фотореалистичных изображений в реальном времени необходимы поиски новых методов визуализации. При работе с множеством детализированных трехмерных объектов (ТО) приходится искать компромисс между производительностью обработки и точностью представления. Чтобы сохранить высокое разрешение представления ТО и повысить производительность визуализации, представляется целесообразным адаптировать степень детализации к конкретным условиям наблюдения. Представлением поверхности ТО с разной степенью детализации (level-of-detail), для учета изменений условий наблюдения, называется представление с множественным разрешением (МР). Представление с МР основано на аппроксимации исходной поверхности ТО и является адаптивным подходом при визуализации. Благодаря' представлению с МР может достигаться улучшение отношения визуального качества информации к ее объему.

Известно несколько моделей представления ТО с МР. При этом можно выделить прогрессивную сетку, зависящую от пирамиды видимости, предложенную Хоуппом (Hoppe)[40], мультитриангуляцию, предложенную Де Флориани (De Floriani) [35] и иерархию равнобедренных треугольников, предложенную Душено (Duchaineau)[3 6]. Однако оптимальное решение этой проблемы с точки зрения эффективной визуализации пока не найдено.

Интерактивная визуализация рельефов выполняется во многих системах моделирования виртуальной реальности: геоинформационные системы (ГИС), тренажеры, компьютерные игры и т.д. Рельефом называется поверхность, заданная множеством опорных точек, которая может быть представлена как однозначная функция двух переменных. Под интерактивной визуализацией рельефа далее понимается синтез его изображения при заданных и оперативно изменяемых параметрах наблюдения. Параметрами наблюдения являются: точка наблюдения, направление взгляда, сектор обзора, ограничения по дальности.

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

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

1. Систематизировать методы аппроксимации и методы представления моделей трехмерных объектов с множественным разрешением для поиска новых решений в рассматриваемой области;

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

3. разработать новые методы для представления рельефов с множественным разрешением;

4. разработать интерактивную систему визуализации рельефов с множественным разрешением и исследовать разработанные методы.

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

1. Систематизированы методы аппроксимации и модели представления трехмерных объектов с множественным разрешением, и, на основе приведенной классификации, выявлены и разработаны новые методы для построения адаптивной системы визуализации рельефов с множественным разрешением повышенной производительности.

2. Разработаны три новых метода:

1. Итерационное ранжирование с использованием средних плоскостей на основе удаления опорных точек из триангуляции Делоне;

2. адаптивная тесселяция элементов аппроксимации для представления рельефа с множественным разрешением;

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

Практическая ценность диссертации:

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

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

3. Создана универсальная адаптивная система визуализации рельефов с множественным разрешением на платформе ПК для экспериментальной оценки эффективности разработанных методов и реализованных алгоритмов визуализации в интерактивных условиях наблюдения при конкретных аппаратных конфигурациях.

Апробация работы. Основные положения работы представлялись и обсуждались на Санкт-Петербургской Международной конференции по мягким вычислениям и измерениям (С. -Петербург 2000), а также на семинарах кафедры Вычислительной Техники СПбГЭТУ (С. -Петербург, 1999 и 2000).

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

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

Структура и объем работы

Диссертация состоит из введения, четырех разделов, заключения и списка литературы. Общий объем диссертации - 163 страниц. Основная часть работы изложена на 14 9 странице и включает 41 рисунок, 7 таблиц и список литературы из 110 наименований.

4.6. Выводы

1. Разработанная вложенная модель рельефа на основе адаптивной тесселяции поддерживает основные требования к моделям представления с МР.

2.Наибольшая эффективность адаптивной выборки достигается при извлечении ЭА с минимальной СД, т. е. когда количество ЭА минимальное. Точность аппроксимации при этом минимальная.

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

-148

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

5. Заключение

Результаты диссертационной работы следующие:

1.Систематизированы методы аппроксимации и модели представления поверхностей трехмерных объектов и на основе приведенной классификации выявлены и разработаны новые методы повышенной производительности для построения системы визуализации рельефов.

2.Для построения адаптивных систем визуализации рельефов разработаны три новых метода:

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

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

• адаптивная выборка элементов аппроксимации с МР на основе иерархии смежных треугольников.

3.Получены следующие практические результаты:

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

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

• Создана универсальная адаптивная система визуализации рельефов с МР, для экспериментальной оценки эффективности разработанных методов и реализованных алгоритмов визуализации в интерактивных условиях наблюдения при конкретных аппаратных конфигурациях.

1.Шикин Е.В., Боресков А.Б., Зайцев А.А. Начало компьютерной Графики //М.: ДИАЛОГ-МИФИ.-1993.

2. Шикин Е.В., Боресков А. Б. Компьютерная Графика //М.: ДИАЛОГ-МИФИ.-2000.

3. Майкл Ласло Вычислительная геометрия и компьютерная графика на С++: Пер. с англ.-М.: «Издательство БИНОМ». -1997.

4. Cignoni Р., Puppo Е., Scopigno R. Representation and Visualization of Terrain Surfaces at Variable Resolution //The Visual Computer.-1997.-13.-PP.89-134 .

5. M., Garland, P.S. Heckbert Surface simplification using quadric error metrics //Computer Graphics (SIGGRAPH '97 Proceedings).-1997.PP.209-21 б.

6. W.J. Schroeder, J.A. Zarge, W.E. Lorensen Decimation of triangle meshes //In Edwin E. Catmull, editor, ACM Computer Graphics (SIGGRAPH '92 Proceedings).-1992.-2 6.PP.65-7 0.

7. Баяковский Ю.М., Галактионов В.А., Ходулев А. Б. Архитектура высокопроизводительных графических систем //Зарубежная радиоэлектроника.-1989.-2.-С.18-44.

8. Bruce Buchanan 3D Technologies //Rexcellence, Computer Aided Engineering news.-1997.-7(8).-PP.57-61.

9. Палташев Т.Т., Климина С.И., Ю В. К. Технология визуализации в компьютерном синтезе реалистичных изображений //Зарубежная радиоэлектроника.-1989.-2.-С. 71, 96-108 .

10. Тимофеев А.В. Разработка и повышение производительности параллельной системы визуализации трехмерных сцен //Автореферат диссертации на соискание ученой степени кандидата технических наук.-С.-Петербург .-1997.

11. Перков А.Н. Разработка и исследование методов адаптивного синтеза изображений рельефов местности //Автореферат диссертации на соискание ученой степени кандидата технических наук.-С.-Петербург.-1998.

12. De Floriani L., Puppo E., Magillo P. Geometric structures and algorithms for geographic information systems //Technical Report DISI-TR-97-08.-Department of Computer and Information Sciences, University of Geneva.-1997.

13. Magillo P., Puppo E. Algorithms for Parallel Terrain Modelling and Visualisation //Chapter 16 in Parallel Processing Algorithms for GIS.-R.G. Healey, S. Dowers B.M. Gittings, M.J. Mineter (Editors).-Taylor and Francis.-1998.-PP.351-386.

14. Leila De Floriani Surface■ representation based on triangular greeds //The Visual Computer-1987.-1.-PP.27-50.

15. Shubert L., Wang C.A. An optimal algorithm for constructing the Delanay triangulation of set of line segments //Proceedings 3rd ACM Symposium on Computational Geometry.-Waterloo.-June 1987.-PP.223-232 .

16. De Floriani L., Magillo P., Puppo E. Building and traversing a surface at variable resolution //Proceedings IEEE Visualization 97.-Phoenix, AZ (USA).-October 1997.-PP.236-253.

17. Fowler R., Little J. Automatic extraction of irregular network digital terrain models //ACM Computer Graphics„-13(3) .-1979.-PP.199-207 .

18. Franklin W.R. Triangulated irregular network to approximate digital terrain //Technical report.-ECSE Dept.-RPI, Troy (NY).-1994.

19. Kirpatrick D.G. Optimal search in planar subdivisions //SIAM Journal of Computing.-12 (1).-1983.-PP.28-35.

20. Lee J. A drop heuristic conversion method for extracting irregular networks for digital elevation models //Proceedings GIS/LIS ' 89.-Orlando, FL, USA.-1989.-PP, 30-39.,

21. Rippa S. Adaptive approximations by piecewise linear polynomials on triangulations of subsets of scattered data //SIAM Journal on Scientific and Statistic Computing.-13(1).-1992.-PP.1123-1141.

22. Scarlatos L.L. An automatic critical line detector for digital elevation matrices //Proceedings 1990 ACSM-ASPRS Annual Convention.-2, Denver, CO.-1990.-PP.43-52.

23. Southard D.A. Piecewise linear surface models from sampled data //Proceedings Computer Graphics International 91.-Boston, MA.-22-28 June.-1991.-PP.274-295.

24. V iaeo С ontrollers.-Rose Computing Services Website.- Texas Networking Inc. -http: //www, texas .net/~ res/res cat 37 . htm .-1998 .

25. Кручкнин С. Новое поколение графических подсистем для настольных рабочих станций HP, SGI и Sun //Computer Week.-199 6.-4 4.-С.3 6-39,4 4,45.

26. Gelberg Lawrence M., MacMann Jeffrey F., Mathias Craig J. Graphics, image processing, and the Stellar graphics supercomputer //Proc. Soc. Photo-Opt. Instrum. Eng.-1989.-PP.89-96.

27. Advances in Computer Graphics.-Ed. by G. Enderle^ M. Grave, F. Lillehagen.-Berlin: Springer-Verlag.-1986.

28. Фоли Дж. , вэн Дэм А. Основы интерактивной машинной графики.-М.: Мир.-1985.-в 2-х кн.

29. Finke U., Hinrichs K.H. The quad view data structure A representation for planar subdivisions //Advances in Spatiol Databases, Lecture notes in Computer Science.-Springer,-1995.-PP.29-46.

30. Flajolet p., Gonnet G.H., Puech C., Robson J.M. Analytic variations on quadtrees //Algorithmica.-1993,-10(6).-PP.473-500.

31. Inventor Mentor: Openlnventor Reference Manual.- Openlnventor Architecture group.-Addison Wesley.-1994.

32. Wernecke J. The Inventor mentor: programming ObjectOoriented 3D graphics with Openlnventor.-Addison Wesley.-1994.

33. The Virtual Reality Modeling Language Specification Version 2.0.-August 1996.-http://vag„vrml.org/.

34. Puppo E. Variable resolution terrain surfaces //Proceedings Canadian Conference on Computational Geometry,-Ottawe (Canada) 12015 August.-1996.-PP.34-57 .

35. L. De Floriani, P. Magillo, E. Puppo. Multiresolution representation and reconstruction of triangulated surfaces //In Third International Workshop on Visual Form.-Capri (Italy), May 1997.

36. M. Duchaineau, M. Wolinsky, D.E. Sigeti, M.C. Miller, C. Aldrich, M.B. Mineed-Weinstein ROAMing terrain: Real-time optimally adapting meshes //In Proceedings IEEE Visualization'97.-1997.-PP.81-88.

37. Samet H. Applications of spatial data structures.-Addison-Wesley.-1990.

38. Dutton G. Improving locational specificity of map data a multiresolutional, metedataOdriven approach and notation //International Journal of Geographic Information Systems.-1996.-10(3).-PP.253-268 .

39. Goodchild M.F., Shiren Y. A hierahical data structure for global geographic information systems //Computer Vision, Graphics and Image Processing.-1992.-54.-PP.31-44.

40. Klein R., Strasser W. Generation of muitireslution models from CAD data for real time rendering. Theory and Practice of Geometric Modelling.-Springer-Verlag.-1996.

41. Hoppe H. Progressive meshes //ACM Computer Graphics Proceedings.-Annual Conference Series (SIGGRAPH''96).-1996.-PP.99-108.

42. Hoppe H. View-dependent refinement of progressive meshes //ACM Computer Graphics Proceedings.-Annual Conference Series (SIGGRAPH '97).-1997.-PP.73-86.

43. Maheshwari A., Morin P., Sack J.R. Progressive TINs: algorithms and applications //Proceedindg 5th ACM Workshop on Advances in Geographic Information Systems.-Las Vegas (Nevada).-November 15-16, 1997.-PP.2 5 6-2 63.

44. Xia J.C., Varshney A. Dynamic view-depended simplification for polygonal models //Proceedings

45. EE Visualization '96.-S. Francisco, CA.-R. Yagel and Nielson (Eds.).-1996.-PP.327-334 .

46. Brown P.J.C. A fast algorithm for selective refinement of terrain meshes //Proceedings COMPUGRAPHICS 96.-GRASP.-December 1996.-PP.70-82 .

47. George Nasy Terrain visibility //Computers & Graphics,-1994.-6.-PP.38-52.

48. Вирт H. Алгоритмы + структуры данных = программы, -M.: Мир.-1985.

49. Кнут Д. Искусство программирования для ЭВМ.-М.: Мир.-1978„-в 3-х кн.

50. Холл П. Вычислительные структуры. Введение в нечисленное программирование.-М.: Мир.-1978.

51. Гилой В. Интерактивная машинная графика.-М.:1. Мир.-1981.

52. Rappoport A. An efficient algorithm for line and. polygon clipping //The Visual Computer.-1991.-1 (7) .-PP., 19-25.

53. De Floriani L., Puppo . E. Hierarchical triangulation for multiresolution surface description //ACM Transactions on Graphics.-1995.-14(4 ).-PP.363-411.

54. Dutton G. Polyhedral hierarchical tesselation: the shape of GIS to come //Geo Info Systems.-1991. -2 (1) .-PP.49-55.

55. De Floriani L., Marzano P., and Puppo E. Multiresolution models for topographic surface descript ion /./The Visual Computer.-1996.-12(7).1. PP,317-345.

56. De Floriani L. A pyramidal data structure for triangle-based surface description //IEEE Comp.Graph. & App1.-1995.-9(2)„-PP.67-78.

57. L. Scarlatos, T. Pavlidis Hierarchical triangulation using cartographies coherence //CVGIP: Graphical Models and Image Processing.-1992.-2.-PP. 147-161,

58. Dobkin D. and Laszlo M. Primitives for the manipulation of threedimensional subdivisions //Algorithmica.-198 9.-4.-PP,3-32.

59. Boissonnat J. and Teillaud M. On the randomized construction of the Deiaunay tree //Theoretical Computer Science.-112.-1993.-PP.339-354.

60. Agarwal P.K., Suri S. Surface approximation and geometric partitions //Proceedings 5th ACM-SIAM Symposium on Discrete Algorithms.-1994.-PP.24-33 .

61. Agarwal P.K., Desikan P.K. An efficient algorithm for terrain simplification //Proceedings 8th ACMSIAM Symposium on Discrete Algorithms.-1997.-PP.162-184.

62. Silva C.T., Mitchell J.S.B., Kaufman A. E. Automatic generation of triangular irregular networks using greedy cuts //Proceedings IEEE Visualization'95.-1995.-PP.201-208.

63. Джок Кармак. Direct3D или OpenCiL? //Компьютерная графика.-1996.-6.-С.68-70.

64. Эллис M.f Строуструп Б. Справочное руководство по языку программирования С++ с комментариями: Пер. с англ.-М.:Мир.-1992.12, Найджел Томпсон Секреты программирования трехмерной графики для Windows 95./ пер. с англ. -СПб.:Питер.-1997.

65. Мюррей V., Паппас К. Visual С++. Руководство для профессионалов: пер. с англ.-Спб.: BHV-Санкт-Петербург„-1996.

66. Агиштейн М.З., Мигдал A.A. «Эксперимент на дисплее» //Москва .-1989.-PP.141-174 .

67. М. Garland, P.S. Heckbert Fast polygonal approximation of terrains and height fields //Technical Report CMU-CS-95-181, School of Computer Sciences,, Carnegie Mellon University, Pittsburgh.1995.

68. M. Garland, P.S. Heckbert Simplifying surfaces with color and normals with quadric error metrics //In Proceedings IEEE Visualization'98.-1998.-PP.263-269.

69. J. Rossignac, P. Borrel Multiresolution 3D approximation for rendering complex scenes //In Geometric Modeling in Computer Graphics.-1993. -PP.4 55-4 65.

70. P. Hinker, C. Hansen Geometric optimization //In IEEE Visualization '93 Proceedings.-1993.-PP.18 9-195.

71. A, D. Kalvin, R.H. Taylor Superfaces: Poligonal mesh simplification with bounded error //IEEE C.G.&A.-1996.-3.-PP.64-7 7.

72. M„E. Algorri, F. Schmitt Surface reconstruction from unstructured 3D data //Computer Graphics Forum.1996.-1,-PP.47-60.

73. P. Lindstrom, G. Turk A fast and memory ecient polygonal simplification //In Proceedings IEEE Visualization'98.-1998.-PP.287-295.

74. H. Hoppe, Т. DeRose, Т. Duchamp, J. McDonald, W« Stuelzle Surface reconstruction from unorganizedpoints .//In ACM Computer Graphics Proceedings, Annual Conference Series, (SIGGRAPH '92) .-1992.-PP.71-78 .

75. H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, W. Stuetzle Mesh optimization //In ACM Computer Graphics Proceedings, Annual Conference Series, (SIGGRAPH '93).-1993.-PP.19-26.

76. H. Hoppe, T. DeRose, T. Duchamp, M. Halstead, H. Jin, J. McDonald, J. Schweitzer, W. Stuetzle Piecewise smooth surface reconstruction //In ACM Computer Graphics Proceedings, Annual Conference Series, (SIGGRAPH '94).-1994.-PP.295-302.

77. W, J, Schroeder A topology modifyinfg progressive decimation algorithm //In Proceedings IEEE Visualization'97.-1997.-PP. 205-212.

78. J. Cohen, A. Varshney, D. Manocha, G. Turk, H. Weber, P. Agarwal, F. Brooks, W. Wright Simplification envelopes //In Computer Graphics Proc., Annual Conf. Series (SIGGRAPH '96).-1996.-PP.119-128.

79. R. Ronfard, J. Rossignac Full-range approximation of triangulated polyhedra //Computer Graphics Forum. (Eurographics'96 Proceedings).-1996.-3.-PP.67-7 6.

80. A. Gueziec Surface simplification inside a tolerance volume //Technical Report RC 20440, I.B.M.

81. T,J, Watson Research Center.-1996.

82. A. Gueziec, G. Taubin, F. Lazarus, W. Horn Simplicial maps for progressive transmission ofpolygonal surfaces //In Proceeding ACM VRML98.-1998.-PP.25-31.

83. B. Hamann A data reduction scheme for triangulated surfaces //Computer Aided Geometric Design.-1994.-2.-PP.197-214.

84. T.S. Gieng, B. Hamann, K.I. Joy, G.L. Schussman, I.J. Trotts Constructing hierarchies of triangle meshes //IEEE Transactions on Visualization and. Computer Graphics .-1997 .-2 .-PP . 145-160 .

85. J. Popovic, H. Hoppe Progressive simplicial complexes //In ACM Computer Graphics Proceedings, Annual Conference Series, (SIGGRAPH '97).-1997.-PP.217-224.

86. H. Samet Applications of Spatial Data Structures //Addison Wesley.-1990.

87. B. Von Herzen, A.H. Barr Accurate triangulations of deformed, intersecting surfaces //Computer Graphics (SIGGRAPH 87 Proceedings).-1987 .-4.-PP.103-110.

88. H. Hoppe Smooth view-dependent level-of-detail control and its application to terrain rendering //In Proceedings IEEE Visualization 198 .-1998.-PP.35-42 .

89. L. De Floriani A pyramidal data structure for triangle-based surface description //IEEE Computer Graphics and Applications.-1989.-2.-PP.67-78.

90. M. Bertolotto, L. De Floriani, P. Marzano Pyramidal simplicial complexes //In Proceedings 4th International Symposium on Solid Modeling.-1995.-PP. 153-162,

91. P. .Cignoni Scientiamc Visualization Based on Simplicial Complexes //PhD thesis, Computer Science Department, University of Pisa„-1997.

92. Marc Soucy, Guy Godin, Marc Rioux A texture-mapping approach for the compression of colored 3D triangulations //The Visual Computer.-1996.-10.-PP , 503-.5'. 4 .

93. Leif Kobbelt, Swen Campagna, Hans Peter Seidel A general framework for mesh decimation //In Proc. Graphics Interf ace '98.-1998.-PP.43-50 .

94. David Luebke, Carl Erikson View-dependent simplification of arbitrary polygonal environments //In SIGGRAPH 97 Proc.-1997.-PP.199-208.

95. Фукс A. JI. Предварительная обработка набора точек при построении триангуляции Делоне Геоинформатика,. Теория и практика. Вып. 1 Томск: Изд-во Томск, ун-та, 1998, с.48-60.

96. Скворцов А. В., Костюк Ю. Л. Сравнительный анализ алгоритмов построения триангуляции Делоне Международная Сибирская конференция по исследованию операций. Материалы конференциию Новосибирск, Изд-во Институт математики СО РАН, 1998.- с. 138.

97. Скворцов А. В., Костюк Ю. Л. Эффективные алгоритмы построения триангуляции Делоне Геоинформатика. Теория и практика. Вьш.1 Томск: Изд-во Томск, унта, 1998, с.22-47.