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

• Фрязинов, Олег Вячеславович
• кандидат физико-математических наук
• 2004

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

Введение.

1. Анализ существующих подходов к моделированию и дискретизации сложных пространственных объектов.

1.1. Анализ известных способов представления геометрических тел.

1.2.Анализ методов описания неоднородных геометрических объектов.

1.3. Анализ методов построения сеток.

1.3.1. Общий обзор методов генерации сеток.

1.3.2. Анализ методов дискретизации неявно заданных геометрических объектов.

1.4. Постановка задачи.

2. Формализация задачи построения конечно-элементных сеток в неявно заданных неоднородных объектах.

2.1 Функциональное представление геометрических объектов.

2.2 Дискретные геометрические модели.

2.3 Гибридная неоднородная геометрическая модель.

2.4 Формальное описание постановки задачи дискретизации неоднородного объекта, представленного гибридной геометрической моделью.

3. Методы поверхностной и объемной дискретизации неявно заданных неоднородных геометрических объектов.

3.1 Дискретизация граничной поверхности.

3.1.1 Генерация полигонального приближения граничной поверхности.

3.1.2. Восстановление поверхностных особенностей.

3.1.3. Улучшение и упрощение сетки на поверхности.

3.1.4 Адаптация поверхностной сетки.

3.2 Построение объемной сетки.

3.2.1 Генерация тетраэдральной сетки.

3.2.2 Оптимизация объемной сетки.

3.2.3 Преобразование атрибутов.

3.3. Процедуры оптимизация поверхностной сетки.

3.3.1 Функция остроты.

3.3.2 Операции перестройки сетки.

3.4 Процедуры генерации объемной сетки.

3.4.1. Модифицированный алгоритм фронтальной тетраэдризации.

3.4.2. Процедуры оптимизации объемной сетки.

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

4.1 Структуры данных.

4.1.1 Реализация отношений, заданных на множествах элементов комплекса.

4.1.2 Реализация модели трехмерного полиэдрального комплекса.

4.1.3 Реализация функционального представления.

4.1.4 Реализация моделей атрибутов.

4.1.5 Реализация гибридной модели.

4.2 Алгоритмы оптимизации поверхностных сеток.

4.2.1 Алгоритмы выполнения базовых операций перестройки сеток.

4.2.2 Алгоритмы основных операций оптимизации.

4.3 Интерактивные средства оптимизации поверхностных сеток.

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

4.5 Инструментальные средства создания объемных сеток.

4.6 Примеры использования программного комплекса.

4.6.1 Тетраэдризация твердого тела, заданного с помощью функционального представления.

4.6.2 Дискретизация неоднородного объекта с различными атрибутами

4.6.3 Моделирование миксера, используемого в химическом реакторе.

4.6.4 Оптимизация поверхностных сеток, импортированных из CAD системы.

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

В настоящее время математическое моделирование: широко применяется в различных областях науки и техники [1,2]. Математические модели ? дают формализованное представление исследуемых процессов и явлений, что открывает возможность использования аналитических и численных методов для решения практических задач- [1]. Неотъемлемой частью математического моделирования является геометрическое моделирование. Геометрические модели активно используются в приложениях, которые непосредственно связаны с решением различных геометрических задач: автоматизированное проектирование, компьютерный дизайн, анимация. Однако;нередко они является составной частью решения более общей математической задачи. Так, при изучении физических, химических, биологических и других процессов и явлений возникает необходимость исследования уравнений в частных производных, определенных в сложных пространственных областях. Для решения указанных уравнений используются обычно численные методы [3], в которых требуетсяv пространственная дискретизация, то- есть расчетная область должна быть представлена в виде, как правило, конечной совокупности достаточно простых геометрических объектов. Такая совокупность объектов, задающая разбиение пространственного; объекта, называется сеткой.

В силу сложности формализации представления пространственных объектов; не существует универсальных геометрических моделей. На сегодняшний день известны разные способы описания геометрии, каждый из которых имеет свои преимущества и недостатки [4]. В целом можно выделить два основных типа геометрических моделей. Это явные и неявно заданные модели [5]. В явных моделях обычно используются параметрические представления кривых и поверхностей. Исторически явные модели получили более широкое применение в системах автоматизированного проектирования и компьютерной графике. Это связано с относительной* простотой: численной обработки и визуализации явных моделей. Однако: при задании; сложных форм; с помощью? явных параметрических описаний приходится использовать составные поверхности и кривые, состоящие * из большого числа; сегментов. Это усложняет процесс задания- и модификации геометрических моделей и приводит к возникновению большого количества ошибок. В" работах [6, 7] отмечаются основные недостатки полиномиальных и рациональных параметрических представлений; Они- связаны в первую очередь с неоднозначностью параметрического описания и; со» сложностями, которые возникают при; вычислении пересечений; Для обеспечения гладкого сопряжения кривых и поверхностей- в автоматизированном проектировании приходится использовать параметрические: функции высоких порядков: При этом, как известно [7], порядок алгебраической, поверхности; которая соответствует параметрическому описанию с координатными функциями порядка л, равен

7 7

2п или п . Порядок алгебраической поверхности определяет максимальное число возможных точек; пересечения прямой с этой поверхностью: Таким; образом, порядок поверхностей напрямую влияет на численную устойчивость, надежность ш точность процедур' вычисления пересечений. При использовании параметрических описаний порядок применяемых поверхностей искусственно завышается; что снижает точность ненадежность, вычислительных процедур. Кроме того; при: выполнении различных операций; над объектами, заданными явными моделями; возникает необходимость- дополнительного i дробления; составных поверхностей и; кривых, что в целом усложняет модель, ш может привести; к снижению» точности ее представления. Вычислительные погрешности могут приводить к несоответствию геометрического и топологического представления; объекта, что делает модель- объекта некорректной. Неоднозначность параметрического описания; кривых и поверхностей* и основанного на их использовании граничного представления объемных тел усложняет интерпретацию описаний моделей, импортируемых из других систем;. Поэтому, несмотря на разработку универсальных форматов [8], не удается обеспечить надежный обмен данными между различными системами; геометрического моделирования и. автоматизированного проектирования. В работах [9, 10] отмечается, что перечисленных недостатков лишен подход, основанный на неявном представлении поверхностей: Анализ возможностей применения неявных алгебраических поверхностей второго и? третьего порядка при проектировании объектов сложной формы приводится в работах [10, 11]. Основные проблемы практического применения! алгебраических поверхностей5 связаны, со сложностью выбора интуитивно: понятных механизмов управления их формой, аналогичных по простоте, аппарату контрольных точек, используемому в»В-сплайнах и; кривых Безье. С другой! стороны,, важным; преимуществом; неявных моделей является: возможность единого описания объемных тел и ограничивающих их поверхностей,, которое достигается, например,' при использовании функционального представления[ 12] . Такое представление замкнуто относительно теоретико-множественных операций; и обеспечивает корректность математического представления сложных объемных тел, получаемых в процессе автоматизированного конструирования. Неявные поверхности; которые описываются» неполиномиальными' функциями, как правило, не имеют аналогичных параметрических представлений, поэтому применение неявных моделей может открыть принципиально новые возможности; в проектировании и дизайне.

Широкое: распространение неявно заданных моделей долгое время, сдерживалось, высокой трудоемкостью' получения дискретного описания поверхностей неявно заданных тел: и, как следствие, сложностью их: визуализации и численного анализа; Однако быстрое развитие компьютерной техники, обеспечивает сегодня возможность манипулирования! неявно заданными моделями со скоростями, приемлемыми для интерактивного проектирования. Поэтому последнее время в компьютерном моделировании интерес к неявно заданным моделям» неуклонно» возрастает. Указанные модели; обеспечивают компактное- и интуитивно понятное представление сложных объектов, поддерживают теоретико-множественные операции, и позволяют также выполнять такие операции, как сглаживание, пространственная деформация, конволюция и другие.

Однако для практического/ применения неявно» заданных моделей в таких приложениях, как конечно-элементное и конечно-разностное моделирование (FEA/FDA) [13, 14] автоматизированное проектирование, инженерный* анализ и подготовка производства (CAD/CAM/CAE) [15] необходимо гарантировать выполнение для этих моделей различных вычислительных процедур, которые основаны на использовании дискретных моделей или сеток. Во- многих приложениях, связанных с численным моделированием; (CAD/CAE/CAM, вычислительная! физика, математическое моделирование, вычислительная геометрия и топология и т.д.) требуется учет внутренней- структуры рассматриваемых геометрических объектов. Однако до сих пор в связи с широким: распространением явных моделей алгоритмы генерации? сеток были ориентированы; в основном на граничные модели и модели; пространственного перечисления, основанные на явном описании. Методы дискретизации неявно? заданных, объектов в настоящее время; активно г развиваются? в визуализации и обработке изображений. Однако требования;, которые предъявляются к дискретным моделям в численном моделировании жестче,, чем в других приложениях; Это связано с тем, что в; численном моделировании сетки являются- основой для аппроксимации; систем уравнений математической физики, описывающих сложные процессы и явления. При этом размеры и форма элементов, а также сама структура сетки оказывают серьезное влияние на устойчивость процедур! численного моделирования и точность получаемых решений. Поэтому зачастую сетки, используемые для: визуализации > геометрических объектов, оказываются неприемлемыми* для конечно-элементного- и конечноразностного анализа. В связи с. этим представляется актуальной задача построения дискретных моделей неявно заданных объектов, которые отвечают требованиям конечно-элементного моделирования.

Еще одной; важной современной тенденцией: в компьютерной' геометрии, и графике является; возрастание интереса к неоднородным моделям; которые наряду- с геометрическими и топологическими данными содержат информацию о других свойствах объектов, например, материале, цвете, характеристиках среды и так далее. Задание негеометрических свойств играет важную роль в конечно-элементном моделировании (FEA/FDA) и; автоматизированном проектировании (CAD/GAM/GAE), поэтому в данной: работе; задача дискретизации решается* с учетомнеоднородности- свойств; моделируемых геометрических объектов.

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

Диссертация состоит из введения, четырех глав и заключения.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Фрязинов, Олег Вячеславович

Заключение

В данной работе были получены следующие основные результаты:;

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

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

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

4. Разработаны алгоритмы оптимизации и адаптации дискретных моделей; неявно заданных геометрических объектов с учетом особенностей их граничных поверхностей; а также с учетом значений? и характера распределения: их негеометрических атрибутов. Указанные алгоритмы обеспечивают построение адаптивных конечно-элементных сеток на; неявных поверхностях.

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

6. Разработана объектно-ориентированная модель. данных, обеспечивающая поддержку функциональных и дискретных представлений геометрических объектов и атрибутов. Указанная модель допускает расширение набора используемых функциональных описаний,, и позволяет эффективно работать с динамически: изменяющимися поверхностными и объемными сетками: Возможности применения предложенной» модели данных не- ограничиваются задачами; рассмотренными в данной диссертации.

7. Разработаны программные средства, реализации? предложенных, алгоритмов оптимизации дискретных моделей1 неявно* заданных неоднородных геометрических объектов.

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

9. На основе перечисленных средств создан программный^ комплекс для работы: с неоднородными? геометрическими моделями, позволяющий выполнять широкий набор - операций» над, гибридной функционально-сеточной моделью. В рамках данного комплекса разработана-интерактивная система оптимизации сеток на поверхностях неоднородных неявно заданных геометрических тел.

10.Разработанные программные средства* применяются для построения расчетных сеток при решении задач многофазовой газовой динамики и * магнитной^ гидродинамики в Институте Математического Моделирования РАН: Средства оптимизации поверхностных сеток используются для качественной? полигонизации неявно заданных объектов в международном проекте Hyperfun (www.hyperfun.org). Разработанные средства генерации объемных сеток были использованы в совместном российско-корейском; предприятии RUCORERC при подготовке данных для проведения инженерного анализа гидродинамики и тепло-массопереноса в химических реакторах с вынужденным перемешиванием.

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

Результаты были опубликованы в следующих печатных работах:

1. E.Kartasheva, V.Adzhiev, A. Pasko,- О. Fryazinov, V. Gasilov Surface and Volume Discretization of Functional based Heterogeneous Objects Journal of Computing and Information Science in Engineering; Transactions of the ASME, 2003vVoL 3, No. 4, pp. 285-294.

2. E.Kartasheva, V.Adzhiev , A. Pasko, O. Fryazinov, V. Gasilov Discretization of Functionally-based* Heterogeneous Objects. Proc. 8th ACM Symposium».on Solid Modeling and Applications,, G. Elber and V. Shapiro (Eds.), Seattle, USA, ACM Press, 2003, pp. 145-156.

31 Гасилов В1А.,Карагичев А.Б., Карташева Е.Л.,Кутанова А.В., Тарасов Д.С., Фрязинов О.В1 Интерактивная система генерации тетраэдральных сеток ITERA; В сборнике трудов «Четвертая международная конференция по математическому моделированию» М: МГТУ «Станкин» 2001. Т.2. 84-91с

4. В.А.Гасилов, А.С.Чуватин, А.Ю.Круковский, E.JI. Карташева, О.Г.Ольховская, А.С.Болдарев, Д.С.Тарасов, Н.В.Серова, С.В. Дьяченко, О.В.Фрязинов Комплекс программ РАЗРЯД: Моделирование ускорения плазмы в сильноточных импульсных системах. - Математическое Моделирование, 2003, Т. 15, No. 9, стр. 107-124

5. В.А. Гасилов, А.С. Чуватин, А.Ю. Круковский, E.JI. Карташева, О.Г. Ольховская, А.С. Болдарев, Д.С. Тарасов, Н.В. Серова, С.В. Дьяченко, О.В. Фрязинов. Исследование сжатия магнитного потока плазменным лайнером. - В сб. "Тезисы докладов XXX Звенигородской конференции по физике плазмы и УТС г.Звенигород, 24-28 февраля 2003". Москва, Науч. Совет РАН по физике плазмы, 2003, стр. 132

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

1. Самарский А.А., Михайлов А.П. Математическое моделирование. М.: Наука, Физматлит, 1997, 205с.

2. Математическое моделирование: Проблемы и результаты,-М. Наука, 2003

3. Федоренко Р.П. Введение в вычислительную физику. М.: МФТИ. 1994. 528с

4. Foley J, A.van Dam, S.Feiner, J.Hughes, R.Philips Introduction to Computer Graphics, Addison Wesley, 1994

5. А.Фокс, M. Пратт Вычислительная геометрия: Пер.с англ.-М.: Мир, 1982.

6. Pratt M.J., Geisow A.D. Surface/surface intersection problems. In The Mathematics of Surfaces ed. By Gregory J.A., Oxford University Press, 1986

7. Owen J. STEP: En introduction. Information Geometers, Winchester, UK, 1993

8. Bloomenthal J. et al.: Introduction to Implicit Surfaces. Morgan Kaufmann, 1997.

9. Pasko A., Adzhiev V., Sourin A., Savchenko V. Function representation in. geometric modeling: concepts, implementation and applications, The Visual Computer, vol.11, N 8, 1995, pp. 429-446.

10. Зенкевич О., Морган К. Конечные элементы и аппроксимация М.: Мир 1986,318с

11. Н.Сабоннадьер Ж.-К.,. Кулон Ж.-Л. Метод конечных элементов и САПР:Пер.с франц.-М; :Мир, 1989.

12. Гардан И:, Люка М. Машинная графика и автоматизация конструирования; Пер. с фр.-М.,Мир,1987

13. Ефимов Н; В., Высшая геометрия, 4 изд., М., 196117.3ейфертГ.,Трельфалль В; Топология, ГОНТИ, 193818;Mortenson М, Geometric Modeling, Wiley, New York, 198519;Ходж В., Пидо Д., Методы алгебраической геометрии, пер. с англ., т. 1-3,М., 1954- 55;

14. Понтрягин Л.С. Основы комбинаторной топологии, М., Наука, 1986

15. Requicha A.A.G. Representstion for Rigid Solid: Theory, Methods and5 Systems. // Computing Surveys, 1980, V2, № 14, p. 437-464.

16. Химушин Ф.Ф.Обзор методов геометрического моделирования для; САПР.- В сб. Программное обеспечение САПР, ВЦ АН СССР, М., 1987, с.78-101

17. Mantylia М. Introduction to- Solid Modeling, Computer Science Press, Rockville; MD, 1988;

18. Химушин Ф.Ф. Конструктивное геометрическоемоделирование.-В сб. Программное обеспечение САПР.ВЦАНСССР,М., 1987, с.102-121

19. ЧельцовА.Ю., ДавыдченкоЭ.А. Представление данных ш алгоритмы для системы геометрического моделирования, основанной на заметании.- В сб. Программное обеспечение САПР, ВЦ АН СССР.,М:, 1987, с. 121-133.

20. Samet Н.,Webber R.E.Hierarchical; data structures and; algorithms for computer graphics. IEEE Comput.Graph & Appl., 1988,V 8,N 4,p.59-75.

21. Соллогуб А.И., Валыдин, А.Т. Система трехмерного геометрического моделирования пространственных тел с использованием характеристических и R-функций.,Программирование, 1991, N3,c.86-96'

22. Shapiro V., Tsukanov, I. Implicit functions with' guaranteed; differential properties, Proceedings; of the Fifth ACM Symposium on<■ Solid Modeling and Applications, ACM, 1999, 258-269.

23. Kobbelt, L., Botsch, M., Schwanecke, U., Seidel; H.-P. Feature sensitive surface extraction from volume data, Computer Graphics (Proceedings of SIGGRAPH 2001), 57-66.

24. Рвачев JI. Методы логической алгебры в математической физике. Наукова думка; Киев, 1974г.

25. Пасько А.А., Пилюгин В.В., Покровский В.Н. Геометрическое моделирование в задаче анализа функций трех переменных, Сообщение ОИЯИ Р10-86-310, Дубна, 1986. Publication in English: Computers and Graphics, vol.12, # # 3/4, 1988, pp. 457-465.

26. Whitehead J.H.C. Combinatorial homotopy, I, Bull. Amer. Math. Soc., 55(1949), 213-245.35;Александров П.С. Комбинаторная топология., ОГИЗ, Гостехиздат, 1947

27. Fritsch F, Piccinini RA. Cellular structures in topology. Cambridge University Press, Cambridge, 1990

28. Fomenko, A.T., Kunii, T.L. Topological modeling for visualization, Springer-Verlag, Tokyo and Heidelbrg, 1997

29. Rossignac J., O'Connor M. SGC: A dimension independent model5 for pointsets with internal structures and incomplete boundaries. In Geometricmodeling for product engineering, ed. by M: Wozny, J. Turner, K. Preiss, 1990.

30. Armstrong C., Bowyer A., Cameron S. et all: Djinn. A Geometric interface for solid modeling. Information Geometers, Winchester, UK, 2000.

31. Карташева ЕЛ. Инструментальные средства подготовки и анализа данных для решения трехмерных задач математической физики -Математическое моделирование. 1997. Т. 9. №6. G. 20.

32. Kumar V., Burns D., Dutta D., Hoffmann C.: A framework for object modeling. Computer-Aided Design 31, 9, (1999), 541-556.

33. Cutler В., Dorsey J., McMillan L., Mueller M., Jagnow R.: A procedural approach to authoring solid models. In Proc. SIGGRAPH'02, ACM TOG 21, 3(2002), 302-311.

34. Park S. M., Crawford R., Beaman J.: Volumetric multi-texturing for functionally gradient material- representation. In Proc. Sixth ACM Symposium on, Solid Modeling and! Applications, D. Anderson, K. Lee (Eds.), ACM Press, 2001, 216-224.

35. Siu Y.K., Tan S.T.: "Source-based" heterogeneous solid modeling. Computer-Aided Design 34, (2002), 41-55

36. Rossignac J;: Structured Topological; Complexes: A feature-based API for non-manifold topologies. In Proc. the ACM Symposium on Solid Modeling, 1997, 1-9.

37. Pasko A., Adzhiev V., Schmitt В., Schlick G.: Constructive hypervolume modeling. Graphical Models 63, 6 (2001), 413-442.

38. Biswas, A., Shapiro, V., Tsukanov, I. Heterogeneous material modeling with distance fields, Technical Report SAL 2002-4, University of Wisconsin-Madison, June, 2002

39. Frey, P.J;, George, P.-L. Mesh Generation: Application to Finite Elements -HERMES Science Europe, OXFORD & PARIS, 2000; 814p.

40. Ho-Le, К Finite element mesh generation methods: a review and; classification./CAD, 1988, V.20,N 1, p. 27-38.

41. Lohner, R. Automatic unstructured grid generators, Finite Elements in Analysis and Design, 25, 1997, 114-134

42. Owen,. S. J., A survey of unstructured mesh generation: technology,. Proceedings 7th International Meshing Roundtable,, Dearborn, MI, October 1998

43. Построение расчетных сеток: Теория и приложения — В сб. под ред. Иваненко С.А., Гаранжа В.А., ВЦ РАН, М. 2002

44. Brawn P.R. A non-interactive method for the automatic generation of finite element meshes using Schwarz-Christoffel transformation. Сотр. Methods in Appl. Mech. Eng., 1981, V. 25, p. 101-126.

45. Baldwin K.H., Schreyer H.L. Automatic generation of quadrilateral elements by a conformal mapping. Eng. Comput., 1985, V.2, p. 187-194.

46. Cook W.A. Body oriented* (natural) coordinates for generating three dimensional meshes. Int. J. Num. Meth. Eng., 1974, V.8, p. 27-43.

47. Blum H A transformation for extracting new descriptors of shape. In. Models for the perception of speech and visual form, ed. By W.Wathen-Dunn, Cambridge, MA, the MIT Press, 1967, p.326-380

48. Arantes, E.R., Oliveira, E., Babuska, I:, Zienkiewicz, O.C., Gado J.P., eds. Proceedings International Conference on Accuracy Estimates and Adaptive Refinement in Finite Element Computation, Lisbon, 1984.

49. Thompson J.F. A survey of dynamically adaptive grids in the numerical solution of partial differential equations. / AIAA Paper 84-1606, 1984.

50. Rivara, M., Levin, С. A 3D refinement algorithm suitable for adaptive and5-multi-grid techniques, J. Сотр. and Appl. Math., 8, 1992, 281-290.

51. D. A. Field; The legacy of automatic mesh generation from solid modeling, Computer-Aided Geometric Des,V12, 1995,651-674

52. Bloomenthal, J. An Implicit Surface Polygonizer, Graphics Gems IV, Academic Press, 1994 •

53. Hartmann, E. A marching: method for the triangulation < of surfaces, The Visual Computer, 14(3), 1998; 95-108;

54. Karkanis, Т., Stewart, A. J. Curvature-dependent triangulation; of implicit surfaces, IEEE Computer Graphics and Applications, 21(2), 2001, 60-69.

55. Lorensen, W., Cline, H. Marching Cubes: a high resolution 3D surface construction algorithm, Computer Graphics, 21(4), 1987, 163-169.

56. Frey, P.J., Borouchaki, H., Geometric surface mesh optimizasion, Computing and Visualization in Science, 1(3), 1998, 113-121

57. Kobbelt, L. V3-Subdivision, Computer Graphics (Proceedings of SIGGRAPH'2000), 103-112.

58. Garland M., Heckbert, P.S. Surface simplification using error metrics, Computer Graphics (Proceedings of SIGGRAPIT97), 209-216.

59. Sheffer, A., Model simplification for meshing using face clustering, CAD, 33(13), 2001,925-934

60. Pasko A.A., Savchenko V.V. Algebraic sums for deformation of constructive solids, Third ACM Symposium on Solid Modeling and Applications, C.Hoffmann and J.Rossignac (Eds.), Salt Lake City, Utah, USA (May 17-19, 1995), ACM Press, 1995, pp. 403-408.

61. Александров П.С. Комбинаторная топология., ОГИЗ, Гостехиздат, 1947

62. Massey W.S. Algebraic topology: An introduction. Harcourt, Brace&World, Inc., New York-Chicago-San Francisco-Atlanta, 1967

63. Handbook of Discrete and Computational Geometry, ed. by Goodman J., O'Rourke J., CRC Press, 1997

64. Freitag, L., Ollivier-Gooch, C. Tetrahedral mesh improvement using swapping and smoothing, Int. J. Numer. Meth. Eng., 40, 1997, 3937-4002.

65. P.-A. FayoIIe, A. Pasko, E. Kartasheva, N. Mirenkov, "Shape recovery using functionally represented constructive models", Proc. International Conference on Shape Modeling and Applications 2004 (SMI'04),IEEE Computer Society, 2004, pp. 375-378