Разработка и исследование алгоритмов сжатия 3-х мерных графических объектов для коллективного проектирования в компьютерных сетях тема диссертации и автореферата по ВАК РФ 05.13.13, кандидат технических наук Федотов, Роман Владимирович

• Федотов, Роман Владимирович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Федотов, Роман Владимирович

Введение

1 Краткий обзор состояния вопроса и постановка задач исследования

1.1 Алгоритмы снижения числа элементов описывающих ЗЭ-модель.

1.2 Оптимизация модели с учетом передачи по сети.

1.3 Задачи исследования.

2 Сжатие инженерных моделей с учетом специфики сжимаемых данных

2.1 Специфика инженерных ЗБ-моделей.

2.2 Распознавание и кодирование повторяющихся объектов

2.3 Метод сжатия полигональных инженерных ЗБ-моделей с помощью автоматического поиска плоских элементов

2.4 Выводы по главе 2.

3 Реализация алгоритмов автоматического поиска плоских элементов

3.1 Общая схема алгоритмов поиска плоских элементов

3.2 Алгоритм перебора сочетаний.

3.3 Алгоритм плоских сечений.

3.3.1 Исследование сечений множества Vo в направлении iVj.

3.3.2 Генерация множеств N с заданным отклонением соседних элементов.

3.3.3 Оценка быстродействия и ресурсоемкое™ алгоритма

3.4 Эффективное кодирование найденных групп.

3.4.1 Оценка эффективности введения группы.

3.4.2 Подбор оптимального сочетания множеств V2 для максимизации коэффициента сжатия.

3.5 Сетевая передача

3.5.1 Оптимизированная передача с постоянным уровнем детализации.

3.5.2 Прогрессивная передача модели.

3.6 Выводы по главе 3.

4 Экспериментальные исследования

4.1 Задачи экспериментальных исследований.

4.2 Разработанное программное обеспечение.

4.3 Экспериментальные подтверждения эффективности метода сжатия с помощью поиска плоских элементов

4.4 Экспериментальные данные о производительности алгоритмов поиска плоских элементов

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

4.5.1 Анализ зависимости коэффициента сжатия от числа итераций.

4.5.2 Анализ Зависимости числа найденных плоских элементов от числа итераций.

4.5.3 Анализ зависимости коэффициента сжатия от числа найденных плоских элементов.

4.6 Выводы по главе 4.

Введение диссертации (часть автореферата) на тему «Разработка и исследование алгоритмов сжатия 3-х мерных графических объектов для коллективного проектирования в компьютерных сетях»

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

Наиболее распространенный способ описания объемной модели — представление ее в виде множества смежных треугольных граней. Этот способ описания поддерживается большинством Интернет-ориентированных форматов.

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

Алгоритмы такого кодирования, рассчитанные на сжатие данных любого типа [1—3], широко используются, но имеют вполне определенный предел сжатия. Наиболее реальным развитием методов сжатия представляется способ, основанный на анализе геометрии модели [4—10]. При этом возможен комбинированный способ, последовательно решающий первую и вторую задачи в рамках требуемой точности. В связи с вышеизложенным актуальность предлагаемых к рассмотрению задач заключается в разработке и реализации методов сжатия, основанных на анализе геометрии трехмерных моделей без потери точности.

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

Цель работы: заключается в разработке и исследовании алгоритмов сжатия трехмерных моделей (ЗО-моделей), основанных на анализе геометрических свойств и допускающих восстановление без потери точности представленных объектов.

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

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

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

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

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

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

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

Предложены способы сетевой передачи сжатой модели.

Практическая ценность и реализация: заключается в:

• разработке эффективной технологии сжатия и сетевой передачи сжатых инженерных ЗБ-моделей.

• разработке способа внедрения предлагаемой технологии сжатия в существующие форматы.

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

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

Апробация результатов работы и публикации. Основные результаты по теме диссертационного исследования докладывались на X и XI Всероссийских научных конференциях ПГАТИ (Самара, 2003, 2004 г., соответственно), 6-й Всероссийской научно-технической конференции «Новые информационные технологии в научных исследованиях и образовании» РГРТА (Рязань, 2001), IV Международной школе-семинаре БИКАМП'ОЗ (ГУАП, Санкт-Петербург, 2003 г.)

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

Объем и структура работы: Диссертация состоит из введения, 4 глав, списка литературы, включающего 83 наименований и приложений.

Заключение диссертации по теме «Телекоммуникационные системы и компьютерные сети», Федотов, Роман Владимирович

Основные результаты исследования:

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

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

3. Разработан алгоритм поиска плоских элементов с помощью перебора сочетаний вершин сжимаемой модели.

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

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

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

Заключение

Список литературы диссертационного исследования кандидат технических наук Федотов, Роман Владимирович, 2004 год

1. Huffman D. A. A method for the construction of minimum redundancy codes. // 1.stitute of Electrical and Radio Engineers 40,9(Sept.). — 1952. — Pp. 1098-1101.

2. Langdon G.f Rissanen J. Compression of black-white images with arithmetic coding. // IEEE Trans.Commun.COM. — № 29. — 1981. — Jun. — C. 858-867.

3. Ziv J., Lempel A. Compression of individual sequences via variable-rate coding. // IEEE Trans.Inf.Theory IT-24(5. — No. 24. — 1978. — Sept. — Pp. 530-536.

4. Bajaj C., Pascucci V., Zhuang G. Compression and coding of large CAD models: Ticam: The University of Texas at Austin, 1998.

5. Isenburg M., Snoeyink J. Coding polygon meshes as compressable ASCII // 3DPVT '2002 / University of North Carolina at Chapel Hill and INRIA Sophia-Antipolis. — 2002.

6. Kapoor N. S. Geometry based connectivity compression of triangular meshes. — 2000.

7. Isenburg M., Snoeyink J. Coding with ASCII: compact, yet text-based 3D content // International Symposium on 3D Data Processing Visualization and Transmission. — 2002. — Pp. 609 — 616.

8. Khodakovsky A., Alliez P., Desbrun M„ Schroeder P. Near-optimal connectivity encoding of 2-manifold polygon meshes. — 2001.

9. King D., Rossignac J., Szymczak A. Connectivity compression for irregular quadrilateral meshes: GVU TR-99-36: Georgia Tech, 1999.

10. Taubin G., Horn W. et al. Geometry coding and VRML // IEEE. — Vol. 86. — 1998. — June. — Pp. 1228-1243.

11. Andbjar C. Geometry simplification.— 1999. — February.

12. Bajaj C. L., Pascucci V., Zhuang G. Single resolution compression of arr bitrary triangular meshes with properties // Data Compression Conference. — 1999. — Pp. 247-256.

13. Hoppe H., DeRose T. et al. Mesh optimization // Computer Graphics. — 1993. — Vol. 27, no. Annual Conference Series. — Pp. 19-26.

14. Hinker P., Hansen C. Geometric optimization // Proc. Visualization '93. — San Jose, С A: 1993. — October. — Pp. 189-195.

15. Шикин E. В., Боресков А. В. Компьютерная графика. Полигональные модели. — М. Диалог-МИФИ, 2000.

16. Isenburg М., Alliez P. Compressing hexahedral volume meshes // Pacific Graphics '2002 / University of North Carolina at Chapel Hill and INRLA Sophia-Antipolis. — 2002.

17. And'ujar C. Octree-based Simplification of Polyhedral Solids: Cs dept / Universitat Polit'ecnica de Catalunya. — Barcelona, Spain, 1999.

18. Isenburg M. Compressing polygon mesh connectivity with degree duality prediction // Graphics Interface '2002 / University of North Carolina at Chapel Hill. — 2002.

19. Saupe D., KuskaJ. Compression of isosurfaces for structured volumes: Tech. rep. — 04109 Leipzig, Germany: University of Leipzig, Computer Science Institute Augustusplatz, 2001. — November.

20. Searching triangle strips guided by simplification criterion // WSCG 2001 Conference Proceedings / Ed. by V. Skala. — 2001.

21. Xiang, Held, Mitchell. Fast and effective stripification of polygonal surface models (short) // SODA: ACM-SLAM Symposium on Discrete Algorithms (A Conference on Theoretical and Experimental Analysis of Discrete Algorithms). — 1999.

22. Carey R., Bell G., Marrin C. — The Virtual Reality Modeling Language. — ISO/IEC DIS 14772-1, 1997. — April.

23. Jackie Neider T. D., Woo M. — OpenGL Programming Guide — The Official Guide to Learning OpenGL, Version 1.1.— Addison-Wesley, Reading, MA, USA, 1997.

24. Kronrod В., Gotsman C. Optimized triangle mesh compression using prediction trees // Pacific Graphics '2000. — 2000.

25. NganA. Simplification of 3D meshes. — 2000.

26. Gumhold S., Strauer W. Real time compression of triangle mesh connectivity // Computer Graphics. — 1998. — Vol. 32, no. Annual Conference Series. — Pp. 133— 140.

27. Schroeder W. J., Zarge J. A., Lorensen W. E. Decimation of triangle meshes // Computer Graphics. — 1992. — Vol. 26, no. 2. — Pp. 65 — 70.

28. Szymczak A., Rossignac J. Grow & fold: Compression of tetrahedral meshes: Tech. Rep. SM99-021. — Atlanta USA: School of Mathematics Georgia Institute of Technology and Graphics, Visualization & Usability Center College of Computing, 1999. —January.

29. Taubin G., Rossignac J. Geometric compression through topological surgery // ACM Transactions on Graphics. — 1998. — Vol. 17, no. 2. — Pp. 84-115.

30. Федотов P. В., Кораблин M. А. Разработка методов и средств опти-мизацииформата vrml для использования в сети интернет // Тезисы докладов 6-й всероссийской НТК / РГРТА.— Рязань: 2001.— С. 154.

31. Rossignac J. Geometric simplification and compression // SIG-GRAPH'97. — 1997.

32. Rossignac J., Borrel P. Multi-resolution 3d approximations for rendering complex scenes // Geometric Modeling in Computer Graphics. — Springer Verlag, 1993. June-July. — Pp. 455-465.

33. LowK. L., Tan T. S. Model simplification using vertex-clustering.

34. Hoppe H. Progressive meshes // Computer Graphics.— 1996.— Vol. 30, no. Annual Conference Series. — Pp. 99— 108.

35. Федотов P. В., Федотов Г. В. Разработка программы визуализации компьютерных моделей // Повышение эффективности работы железнодорожного транспорта.— 2000.— Т. 2, № 20.— С. 169 — 170.

36. Evans F, Skiena S. S., Varshney A. Optimizing triangle strips for fast rendering // IEEE Visualization '96 / Ed. by R. Yagel, G. M. Nielson. — 1996. —Pp. 319-326.

37. Bajaj C. L., Ihm /., Park S. Compression-based 3D texture mapping for real-time rendering // Graphical Models. — 2000. — Vol. 62, no. 6. — Pp. 391-410.

38. Turk G. Re-tiling polygonal surfaces // Computer Graphics. — 1992. — Vol. 26, no. 2. — Pp. 55 64.

39. SzymczakA., RossignacJ., King D. Piecewise regular meshes: Construction and compression: GVU GA 30332. — Atlanta USA: Georgia Tech, 2002. — February.

40. Yuen P., Khalili N., Mokhtarian F. Curvature estimation on smoothed 3d meshes: Tech. rep.: Centre for Vision, Speech and Signal Processing School of Electronic Engineering, Information Technology and Mathematics University of Surrey,, 1999.

41. Boehm W.t Prautzsch H. Geometric fundamentals.

42. JoeW., Tony D. Barycentric coordinates for convex polytopes.— 1993.

43. Golub G., Van Loan C. Matrix Computations. — 2nd edition. — University Press, 1989.

44. Du W. A Study of Several Specific Secure Two-party Computation Problems: Ph.D. thesis / Purdue University. — West Lafayette, Indiana, 2001.

45. L. Bajaj С., Pascucci V., Zhuang G. Progressive compression and transmission of arbitrary triangular meshes // IEEE Visualization '99 / Ed. by D. Ebert, M. Gross, B. Hamann. — San Francisco: 1999. — Pp. 307 — 316.

46. Taubin G. 3D geometry compression and progressive transmission // EUROGRAPHICS 99. — 1999.

47. Hoppe H. Efficient implementation of progressive meshes // Computers and Graphics. — 1998. — Vol. 22, no. 1. — Pp. 27 36.

48. Khodakovsky A., Schroder P., Sweldens W. Progressive geometry compression // Siggraph 2000, Computer Graphics Proceedings / Ed. by K. Akeley. — ACM Press / ACM SIGGRAPH / Addison Wesley Longman, 2000. — Pp. 271-278.

49. Li J., Li J., Кио С. C. J. Progressive compression of 3D graphic models // International Conference on Multimedia Computing and Systems. — 1997. —Pp. 135-142.

50. Pajarola R.f Rossignac J. Compressed progressive meshes // IEEE Transactions on Visualization and Computer Graphics. — 2000. — /. — Vol. 6, no. 1. —Pp. 79-93.

51. Pajarola R. В., Rossignac J., Szymczak A. Implant sprays: Compression of progressive tetrahedral mesh connectivity// IEEE Visualization '99 / Ed. by D. Ebert, M. Gross, B. Hamann. — San Francisco: 1999. — Pp. 299-306.

52. Popovic J., Hoppe H. Progressive simplicial complexes // SIGGRAPH.— 1997. —Pp. 217-224.

53. Cohen-Or D., Levin D., Remez O. Progressive compression of arbitrary triangular meshes // IEEE Visualization '99 / Ed. by D. Ebert, M. Gross, B. Hamann. — San Francisco: 1999. — Pp. 67 — 72.

54. Progressive forest split compression / G. Taubin, A. Gueziec, W. Horn, F. Lazarus // Computer Graphics. — 1998. — Vol. 32, no. Annual Conference Series. — Pp. 123— 132.

55. VarshneyA. A hierarchy of techniques for simplifying polygonal models // SIGGRAPH '97 Course Notes CD-ROM, Course 25: Multiresolu-tion Surface Modeling. ACM SIGGRAPH. — 1997. — August.

56. Захаров А. А., Брагин П. А. Разработка методов изменения геометрической сложности графических объектов для систем генерации визуальной обстановки // Методы и устройства передачи и обработки информации. — 2002. — Т. 2. — С. 88-92.

57. Multiresolution analysis of arbitrary meshes / M. Eck, T. DeRose, T. Duchamp et al. // Computer Graphics. — 1995. — Vol. 29, no. Annual Conference Series. — Pp. 173—182.

58. Shamir A., Bajaj C. L., Pascucci V. Multi-resolution dynamic meshes with arbitrary deformations // IEEE Visualization.— 2000.— Pp. 423-430.

59. Федотов Р. В. Алгоритмы оптимизации фасетчатых моделей и методы их сетевой передачи // Вычислительные методы и программирование — Издательство Московского университета, Научно-исследовательсуий вычислительный центр МГУ.— 2003.— Т. 4, №2, —С. 47-57.

60. Федотов Р. В. Методы сетевой передачи, оптимизированных фасетчатых моделей. // Инфокоммуникационные технологии. — 2003.

61. Захаров А. А., Масанов А. Н. Синтез изображений протяженных участов местности // Методы и устройства передачи и обработки информации. — 2002. — Т. 2. — С. 98-102.

62. Barequet, Sharir. Partial surface and volume matching in three dimensions // IEEETPAMI: IEEE Transactions on Pattern Analysis and Machine Intelligence.— 1997. —Vol. 19.

63. Dorai C., Jain A. K. COSMOS a representation scheme for 3d free-form objects // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 1997. — Vol. 19, no. 10. — Pp. 1115 - 1130.

64. Osada R., Funkhouser T. et al. Matching 3d models with shape distributions // International Conference on Shape Modelling and Applications (SMI2001). — 2001. — May. — Pp. 154- 166.

65. Novotni M., Klein R. A geometric approach to 3d object comparison // International Conference on Shape Modelling and Applications (SMI2001). — 2001. —May. — Pp. 167-175.

66. Реппес X., Ayache N. A geometric algorithm to find small but highly similar 3D substructures in proteins // Bioinformatics.— 1998.— No. 14.—Pp. 516-522.

67. Automated discovery of active motifs in three dimensional molecules // Knowledge Discovery and Data Mining.— 1997.— Pp. 89-95.

68. Федотов P. В. Упаковка трёхмерных моделей методом разбиения множестве точек, на подмножества с ограничивающим условием // Тезисы докладов X Российская НК / ПГАТИ. — Самара: 2003. —март. — С. 137.

69. Федотов Р. В. Сжатие инженерных ЗО-моделей при помощи автоматического поиска плоских элементов, для минимизации сетевого трафика // Тезисы докладов XI Российская НК / ПГАТИ. — Самара: 2004.

70. Степанов Н. Н. Сферическая тригонометрия.— 2 изд.— Л.-М., 1948.

71. Lamme С. Lecons sur Les Coordonnees curvilignes et leurs diverses applications. — P., 1859.

72. Лаптев Г. Ф. Элементы векторного исчисления. — М., 1975.

73. Шикин Е. В., Боресков А. В. Компьютерная графика, динамика реалистические изображения. — М. Диалог-МИФИ, 1995.

74. Alliez P., Desbrun М. Valence-driven connectivity encoding for 3D meshes // EG 2001 Proceedings / Ed. by A. Chalmers, T.-M. Rhyne. — Blackwell Publishing, 2001. — Vol. 20(3). — Pp. 480-489.

75. Howard P. G. The design and analysis of efficient lossless data compression systems: Tech. Rep. CS-93-28: 1993.

76. Zhuang G. Compression and Progressive Transmission of Three-Dimensional Models: Ph.D. thesis / Purdue University. — 1998.

77. Jiankun L., JayKuo C. Embedded coding of mesh geometry: Tech. rep.: ISO/IEC JTC1/SC29/WG11 MPEG98/M3325, 1998. —March.

78. Andersson O., Armstrong P., othes. — Scalable Vector Graphics (SVG) 1.1 Specification. — W3C, 2003. — January.

79. P. D. — GZIP file format specification version 4.3. — Aladdin Enterprises, 1996. —May.