Содержание к диссертации
Введение
Глава 1. Системы графического вывода 22
1.1. Система математического обеспечения графопостроителей 22
1.1.1. СМОГ, 1-ый уровень 22
1.1.2. СМОГ, 2-ой уровень 29
1.1.3. Заключение по первому периоду разработки СМОГ 31
1.2. Система управления графическим выводом 33
1.2.1. Виртуальное устройство графического вывода 36
1.2.2. Программные каналы графического вывода 41
1.2.2.1. Канал вывода на УМКФ КАРАТ 42
1.2.2.2. Каналы непосредственного вывода на ГП, ФП и СОМ-320 47
1.2.2.3. Универсальный канал накопления (УКН) 49
1.2.3. Технология вывода из графического архива 51
1.2.3.1. Графические архивы СУГВ 52
1.2.3.2. Диалоговый модуль СЕРВГП 57
1.2.3.3. Диалоговый модуль User 58
1.2.3.4. Дальнейшее развитие СУГВ 60
1.3. Заключение по главе 62
Глава 2. Многоцелевая система машинной графики смог- 85 67
2.1. Общее описание системы СМОГ-85 68
2.2. Пакет для управления внешней памятью и работы со структурой данных 69
2.2.1. Виртуальная внешняя память 71
2.2.2. Иерархическая структура данных 72
2.3. Графический пакет 73
2.4. Инструментальные средства программирования распределенных программ для двухмашинного комплекса 75
2.4.1. Опыт реализаций станций ГКС 75
2.4.2. Система программного обеспечения графического диалога 77
2.4.3. СПО ГД - программное обеспечение графического диалога 81
2.4.4. Программное обеспечение связи и протокол 86
2.5. Описание геометрических моделей плоских объектов и выпуск чертежей 91
2.6. Геометрическое моделирование трехмерных тел 92
2.7. Оформление документов на графических устройствах 94
2.7.1. Постановка задачи на разработку ПС ФОРТ 95
2.7.2. Текстовый документ 98
2.7.3. Автоматизация подготовки описания документа 98
2.7.4. Структура ПС ФОРТ 100
2.7.5. Краткая характеристика языка описания документа 103
2.7.5.1. Форматирование текста 103
2.7.5.2. Управление распечаткой 105
2.7.5.3. Язык процессора формул 105
2.7.5.4. Процессоры графики 107
2.7.6. Заключение по разработке ПС ФОРТ 108
2.8. Заключение по главе 109
Глава 3. Системы машинной графики для персональных ЭВМ 112
3.1. Инструментальная система для разработки графических диалоговых приложений 114
3.1.1. Операционная среда 114
3.1.2. Модели экрана 115
3.1.3. Виртуальная клавиатура 118
3.1.4. Базовые компоненты программного обеспечения 120
3.1.4.1. Вывод графической информации 120
3.1.4.2. Вывод, ввод и редактирование данных 122
3.1.4.3. Управление маркером 123
3.1.4.4. Протоколы 123
3.1.5. Меню текстовых кнопок 124
3.1.6. Графические панели 126
3.1.7. Редактор FM-MAKER 129
3.1.8. Заключение по разработке технологии VAD 130
3.2. Редактор графических меню UI EDIT 131
3.3. Система авторской подготовки текстов DP 132
3.3.1. Экранные редакторы математических формул 136
3.3.2. Описание редактора СЭРФ 137
3.4. Библиотека БЕЗЬЕ для конструирования плоских областей 139
3.4.1. Задание исходных данных 141
3.4.2. Разбиение плоскости 143
3.4.3. Регуляризованные теоретико-множественные операции 147
3.4.4. Операция пересечения объектов с прямой 147
3.4.5. Программный интерфейс 148
3.5. Заключение по главе 150
Глава 4. Системы визуализации трехмерных сцен 152
4.1. Мотивация разработок 152
4.2. Объектно-ориентированная система SmogDX/3D 154
4.2.1. Общие сведения о библиотеке Direct3D Retained Mode 154
4.2.2. Задача разработки системы SmogDX 159
4.2.3. Общее описание системы SmogDX 161
4.2.4. Программный интерфейс SmogDX/3D 167
4.2.5. Модуль FrameExplorer 167
4.2.6. Заключение по разработке SmogDX/3D 170
4.3. Синтез реалистических изображений трехмерных сцен методами декомпозиции 172
4.4. Метод световых сеток 178
4.4.1. Обратная рекурсивная лучевая трассировка 178
4.4.2. Метод световых сеток. Введение 181
4.4.3. Задача 183
4.4.4. Идея метода световых сеток 184
4.4.5. Скалярное световое поле прямой освещенности 187
4.4.6. Алгоритм метода световых сеток 190
4.4.7. Интерполяция 192
4.4.8. Мягкие тени 195
4.4.9. Эксперименты 197
4.4.10. Заключение по методу световых сеток 201
4.5. Заключение по главе 202
Заключение 207
Литература 210
Приложение 231
- Система управления графическим выводом
- Пакет для управления внешней памятью и работы со структурой данных
- Библиотека БЕЗЬЕ для конструирования плоских областей
- Объектно-ориентированная система SmogDX/3D
Введение к работе
Машинная (или как сейчас говорят - компьютерная) графика - это достаточно новое научное направление: почти все авторы связывают ее начало с работой И. Сазерденда 1963 года [1], где он представил первую программную разработку — редактор графических изображений Sketchpad, давший старт всему направлению. За какие-то 5 лет проблематика машинной графики заняла определенную нишу в тематике таких конференций как весенние и осенние конференции (SJCC и FJCC) AFIPS (American Federation of Information Processing Society). Уже в 60-х годах затрагивалась достаточно широкая проблематика. Большое место занимала тематика вывода на графические устройства - пассивная графика. С технологической точки зрения большое влияние оказала работа Брезенхэма 1965-го года [2], посвященная алгоритмам растеризации отрезков с использованием только операций сдвига и сложения. К 1973-му году накапливается значительное количество исследований и практических разработок, так авиастроительные компании США разрабатывают и применяют САПР на комплексах IBM/360 с графическими дисплеями IBM-2250 [3].
В конце 60-х годов в нашей стране ряд научных учреждений и КБ (ИПМ АН СССР, ВЦ АН СССР, ВЦ СО АН СССР, и др.) приобретают импортные графические устройства, в основном графопостроители, а также и дисплеи - ЛВТА ОИЯИ (г. Дубна). Организации страны эксплуатировали в основном отечественную вычислительную технику, для которой еще несовершенное западное программное обеспечение было совсем неприменимо. Стали проводиться работы по инженерному сопряжению графических устройств с ЭВМ и параллельно велись разработки графических устройств (например, дисплеи ИАЭ СО АН СССР) и графического программного обеспечения.
В 1973 году выходит книга Ньюмена и Спрулла "Principles of Interactive Computer Graphics", которая переводится на русский язык и издается в СССР в 1976 году [4]. Она оказывает неоценимое влияние на развитие машинной графики в
нашей стране. В это время графическая техника получает распространение в стране, особенно на машинах типа М-220 и БЭСМ-6, во многих городах ведутся разработки. На различных конференциях, связанных с АСНИ или САПР, докладываются работы по графике. В сентябре 1977 года ВЦ СО АН СССР и Новосибирский филиал ИТМиВТ АН СССР проводят в Новосибирске первую конференцию, посвященную машинной графике, которая имела региональный статус, но собрала специалистов из многих районов Союза.
В 1979 году ассоциация Сигграф (АСМ США) анонсирует проект Core System [5], который претендует на стандарт графической системы. Этот факт показывает, что назрела насущная проблема обмена алгоритмами в форме программ, переноса (продажи) графических программных продуктов в другие организации и/или на другие компьютерные платформы. Проект оказал значительное влияние на разработки графических систем во всем мире.
В 1981-м в Новосибирске состоялась Всесоюзная конференция по проблемам машинной графики, которая имела действительно всесоюзное представительство (Москва, Владивосток, Новосибирск, Дубна, Киев, Протвино, Ленинград, Ижевск, Горький, Харьков, Пенза, Свердловск, Жуковский, Кишинев, Челябинск, Минск, Кемерово, Николаев, Ульяновск). По докладам видно влияние Core System, хотя большинство из них посвящается разработке графических алгоритмов и прикладных систем.
В 1983, наконец, официально выходит стандарт ISO Graphical Kernel System (GKS или ГКС) [6], который во многом опирается на Core System, но задание самих графических примитивов отличается значительно. Многие разработчики начинают ориентироваться уже на ГКС. Забегая вперед, скажем, что с появлением IBM PC ГКС постепенно забывается, но то огромное влияние, особенно единая терминология и большой вклад в графическое образование нельзя не отметить. В 1988 году в СССР ГКС также становится стандартом [7].
Сильная команда из ИАиПУ ДВНЦ АН СССР, которая занималась всем спектром проблем машинной графики, проводит во Владивостоке в 1985 году очередную всесоюзную конференцию, которая даже в названии показывает расширение тематики до "распознавания изображений". В 1987 году 4-я всесоюзная конференция по машинной графике проводится в Протвино сильной командой по научной визуализации из ИФВЭ. А в 1989 году в Новосибирске проводится пятая и, пожалуй, последняя конференция, на которой еще серьезно рассматривались проблемы, связанные с реализацией графических систем для отечественных машин.
Очередная эра развития машинной графики в нашей стране начинается в 1991 году, когда при поддержке АСМ и Сигграф АСМ проводится первая из 13-ти ежегодных международных конференций Графикой (1991-2003). На ней отечественные специалисты знакомятся из первых рук с наиболее передовыми разработками, в том числе: фотореалистическая визуализация, анимация, станция Silicon Graphics.
С сожалением стоит отметить, что переход на импортные ЭВМ с западным программным обеспечением и недофинансирование привели к резкому сокращению числа отечественных исследований и разработок, да и разработчиков. Это видно по составу докладов на Графиконах, где почти половину докладов представляют специалисты их западных стран. Главная причина видится в отсутствии внутреннего заказчика. А выживают только те, которые смогли найти внешние гранты или заказы.
Актуальность темы. Результаты данной работы были получены за период около трех десятилетий, и на каждом этапе актуальность решаемых задач соответствовала требованиям времени.
1. В конце 1960-х - начале 1970-х годов в нашей стране появились графические устройства (в основном иностранного производства) без технических и программных средств сопряжения с отечественными ЭВМ. Автоматизация вы-
вода информации из ЭВМ в графическом виде многократно увеличивает производительность труда исследователей, но для ее обеспечения необходимо наличие на ЭВМ программных средств обработки и вывода в графическом виде результатов расчетов. Следовательно, на начало 70-х годов прошлого столетия актуальными были две проблемы: разработка технических и программных средств сопряжения графических устройств с отечественными ЭВМ (эта проблема в диссертации не рассматривается) и задача разработки систем для графического представления и вывода результатов научных расчетов (рассмотренная в диссертации) на отечественных ЭВМ (М-220, БЭСМ-6 и др.), оснащенных системами автоматизации программирования (языки: Алгол-60, Альфа, Фортран, и трансляторы с них).
Вывод графического представления результатов численных экспериментов (графической информации) непосредственно из ЭВМ (в режиме on-line) на графическое устройство резко уменьшал производительность ЭВМ (до скорости рисования графиков на графопостроителе) и для высокопроизводительных ЭВМ такой режим вывода графической информации нецелесообразен. Для решения этой проблемы, например, фирма Бенсон (Франция) разработала аппаратуру для считывания управляющих команд для графопостроителя с магнитной ленты (режим off-line). Вывод графической информации на магнитную ленту несколько, но не существенно, уменьшил зависимость производительности ЭВМ от наличия в программе графического вывода. Актуальной для высокопроизводительных ЭВМ и Вычислительных центров коллективного пользования (оснащенных мощными вычислителями в единой сети) стала проблема разработки технологии, обеспечивающей вывод графической информации без уменьшения производительности ЭВМ. Таким образом, решение задачи разработки системы программной поддержки технологии и организации вывода графической информации в крупном вычислительном центре или ВЦКП (Вычислительные центры коллективного пользования) становится определяющим условием эффективного (по крайней мере с точки зрения владельца ВЦКП) ис-
пользования графических устройств. Например, в 1977 году ВЦ СО АН СССР обслуживал не менее 1500 пользователей из институтов Новосибирского научного центра, получающих в среднем за месяц 3000 графиков общей длиной 30 км пути пера.
2. Естественно, что для развития экономики страны, проблема вывода инфор
мации научных расчетов играет меньшую роль, чем решение задач отраслей
народного хозяйства. Пожалуй, оснащение вычислительной техникой и графи
ческими устройствами в первую очередь производилось в конструкторских бю
ро и отраслевых институтах нашей страны. Проблемы их технического и про
граммного обеспечения во многом совпадали с аналогичными проблемами в
научных организациях, но имели особенности, связанные с производством, в
частности:
решение геометрических и графических задач в САПР,
выпуск технической документации.
Во второй половине 1970-х годов актуальной становится задача разработки многофункциональных систем машинной графики для систем автоматизированного проектирования и АСНИ (как части решения отраслевых задач), включающих в себя средства геометрического моделирования рассчитываемых объектов и вывода расчетных данных в графическом виде, как части документации по проектируемым изделиям. Актуальность исследований методов разработки систем машинной графики для САПР машиностроения в конце 1970-х и начале 1980-х годов для отечественных ЭВМ не вызывают сомнения, а сами исследования проводились в тот период большинством академических и отраслевых научных организаций нашей страны.
3. В конце 1980-х годов, к сожалению, в нашей стране произошла смена отече
ственной вычислительной техники на иностранную. Резкое ежегодное увеличе
ние производительности ПЭВМ и рабочих станций создало необходимые пред
посылки для рассмотрения проблем реализации и практического применения
алгоритмов трехмерной графики. Широкое распространение вычислительной техники и ее применение непрерывно растущим кругом пользователей (от школьников до домохозяек) поставило задачу создания, в частности, графических систем мощных по их возможностям и простым для освоения. Стандартные профессиональные графические библиотеки трехмерной графики OpenGL и Microsoft DirectX требуют значительного времени для практического освоения. Актуальной (с середины 1990-х) становится задача исследований и разработки простого, с точки зрения освоения, но достаточно мощного, с точки зрения практических приложений, программного средства задания и визуализации динамических пространственных сцен.
Проблема визуализации пространственных сцен остается и на сегодняшний день сложной задачей, прежде всего, с точки зрения объема и времени вычислений. Задача разработки новых эффективных методов визуализации пространственных сцен остается актуальной и по сегодняшний день. Один из методов решения этой задачи предлагается в заключительном параграфе диссертации.
Цель работы заключается в исследовании и разработке принципов, подходов и методов построения программного обеспечения графического ввода-вывода информации из ЭВМ: научно-исследовательские расчеты, системы автоматизации проектирования, визуализация пространственных сцен. В соответствии с этими задачами были выполнены следующие исследования и разработки:
исследование и разработка принципов построения системы математического обеспечения графического представления результатов вычислений унифицированной для различных ЭВМ и систем программирования;
исследование и разработка технологии хранения и вывода графической информации на графические устройства вычислительного центра коллективного пользования;
исследование и разработка подходов и принципов построения на двухмашинных комплексах (главная ЭВМ для массовых расчетов, сателлит для
формирования заданий и анализа результатов расчета (АРМ - автоматизированное рабочее место) многофункциональной интегрированной системы для САПР, обеспечивающей полный цикл проектирования и сопровождения изделий, включая построение геометрических моделей, выпуск чертежной документации и пояснительных документов, визуализацию исходных и расчетных данных;
исследование и разработка методики изучения и применения стандартных систем построения и визуализации динамических пространственных сцен в повседневной практике;
исследование и разработка алгоритмов фотореалистической визуализации пространственных сцен.
В основе методологии исследований лежит применение системного подхода, современных информационно-вычислительных технологий, методов объектно-ориентированного программирования. Одним из основных использовался эволюционный подход - от создания прототипа к конечному продукту, т.е. через эксперименты и/или обратную связь с пользователем, получаемую во время опытной эксплуатации. При разработке алгоритмов использовались методы вычислительной геометрии, численные методы решения уравнения переноса, элементы теории графов и др.
Научная новизна представленной работы заключается в следующем:
1. Разработаны (1974 [13], 1976 [12], 1979 [37]) принципы построения системы математического обеспечения графического представления данных, заключающиеся в выделении следующих компонент системы:
СУГВ - система управления графическим выводом,
1-й уровень - базовые графические средства (графический стандарт),
2-й уровень - прикладные графические алгоритмы (графики, поверхности, изолинии и т.д.).
*
'»
Отметим, что в дальнейшем эти принципы развивались как отечественными, так и зарубежными исследователями, а виртуальное графическое устройство, впервые разработанное в нашей стране в рамках СУГВ, является прототипом графических стандартов CGI/CGM [55].
2. Разработаны (1985 [58], 1986 [59, 60], 1988 [61]) принципы построения на двухмашинных комплексах многофункциональной системы машинной графики для САПР машиностроения, суть которых в следующем:
независимость функциональных возможностей системы от операционный среды, в которой система должна быть реализована и эксплуатироваться;
отделение геометрических и графических данных от алгоритмов и программ, которые их обрабатывают;
независимость функциональных средств от специфики прикладных областей;
общая база данных для хранения геометрических моделей и технической документации по проектируемым объектам;
описание двумерных геометрических моделей проектируемых объектов (геометрическая и чертежная документация);
описание трехмерных геометрических моделей проектируемых объектов (полиэдры и параметрические кривые и поверхности);
программно-техническая подсистема (СПО ГД), обеспечивающая программирование распределенных прикладных программ на комплексе "главная ЭВМ - сателлит"
программное средство подготовки документации, обеспечивающее форматирование текстов с математическими формулами, рисунками и таблицами, включающая один из первых в мире экранных редакторов математических формул (1987 [138]).
Предложенная структура и ее функциональное наполнение системы машинной графики для САПР машиностроения впервые были предложены в 1980 году автором диссертации совместно с A.M. Мацокиным для решения конкретных прикладных задач машиностроительной отрасли.
З.В развитие систем СМОГ и СМОГ-85 была исследована и решена (1997 [147], 1998 [148], 2000 [145]) прикладная задача задания областей с криволинейной границей, состоящей из параметрических кривых Безье. Построен новый метод разбиения плоскости набором четырехточечных кривых Безье на подобласти, что позволило верифицировать задание области и построить ее характеристическую функцию, как необходимое средство идентификации точек области. Эта методика и программы были применены при решении задач математической физики для описания геометрии двумерных областей и построения сеток.
4. Исследована и разработана технология (1990 [128]) для создания графическо
го интерфейса диалоговых прикладных программ в среде DOS IBM PC, заклю
чающаяся в представлении пользователю удобных и экономичных средств соз
дания меню для управления процессом управления прикладной программой, в
основу которой были положены принципы (подсистема СПО ГД системы
СМОГ-85):
отделение процесса проектирования диалогового графического интерфейса от расчетной части прикладной программы;
применение подхода WYSIWYG (что вижу, то и получаю): экранный редактор для планирования раскроя экрана и создания графических меню, прототип диалога;
библиотеки программ ввода и вывода данных и работы с меню.
5. На основе анализа материалов и пособий по использованию системы DirectX
для описания и визуализации динамических пространственных сцен разработа
на новая методика (в том числе программная реализация методики - система
SmogDX/3D, 1999 [160, 161], 2001 [159]) изучения основ динамической трехмерной машинной графики, достаточной для решения большинства практически важных задач (курс освоения SmogDX/3D - 12 академических часов).
6. Предложена и исследована (2001 [189,190], 2002 [191]) модификация метода обратной рекурсивной трассировки лучей визуализации пространственных сцен - метод световых сеток, позволяющий строить мягкие тени от точечных источников света и требующий меньшего объема вычислений по сравнению с объемом вычислений метода обратной рекурсивной трассировки лучей в случае большого количества источников света и/или большого размера изображения.
Практическая ценность
Система СМОГ была широко распространена в стране и установлена на отечественных вычислительных машинах, таких как ряд М-22х/БЭСМ-4, БЭСМ-6, ЕС и СМ ЭВМ, ДВК и др.
Система управления графическим выводом СУГВ для БЭСМ-6 разрабатывалась на оборудовании ВЦКП СО АН СССР и в течение двух десятилетий использовалась в качестве единственного модуля, отвечающего за технологический вывод графической информации, для СМОГа, ГРАФОРа и других графических систем. Ее терминальный модуль, работающий на периферийных центрах (мини-ЭВМ) ВЦКП в институтах СО АН СССР, обеспечивал просмотр графического вывода задач непосредственно на рабочем месте исследователя. СУГВ обеспечивала вывод на специфические графические устройства: а) СОМ-320 для получения более 200 графических кадров на одной микрофише, б) устройство микрофильмирования КАРАТ, обеспечивающего вывод машинных фильмов на 35 мм кинопленку.
После ввода в ВЦ СО АН СССР в эксплуатацию ЕС ЭВМ СУГВ была реализована на этих машинах и обеспечила для пользователей все возможности, которые до этого были у них на БЭСМ-6: вывод и/или просмотр графики, получение микрофиш и компьютерных фильмов.
Система СМОГ-85 была положена в основу отраслевой системы машинной графики "Магистраль" для САПР машиностроительных изделий Миноборон-прома СССР. Функционирование системы осуществлялось на комплексе, состоящем из нескольких БЭСМ-6, нескольких ЕС ЭВМ и нескольких автоматизированных рабочих мест (типа АРМ-М и АРМ-Р), объединенных универсальной магистралью системного обмена УМСО. Система проектирования работала по технологии "главная ЭВМ - сателлит" и была построена на основе СПО ГД. Калининское НПО Центрпрограммсистем выпустило документацию по системе СМОГ-85 в соответствие с ГОСТами, зарегистрировало ее во Всесоюзном фонде алгоритмов и программ и распространяло в организациях страны систему как целиком, так и отдельными подсистемами.
Технология разработки графического интерфейса VAD для интерактивных программ в DOS IBM PC использовалась в разработках ВЦ СО АН СССР, проводимым в рамках плановых работ и по хоздоговорам (например, [131-133]). 6. Система авторской подготовки текстов ФОРТ (а затем система DP для IBM PC в DOS) использовалась в ВЦ СО АН СССР с 1983 по 1992 годы при подготовке документации, статей, диссертаций, сборников научных трудов, пока не была заменена системами LaTeX и Word по очевидной причине - издательства и конференции стали брать тексты, подготовленные только в этих системах. Экранный редактор формул СЭРФ эксплуатировался дольше в связи с тем, что: а) ему не было альтернативы - формулы в текстовом процессоре Word появились позднее; б) в системе DP существовала утилита, обеспечивающая конвертирование описаний документов с языка системы ФОРТ/DP в язык LaTeX.
7. Система классов SmogDX опубликована в виде трех монографий, ее исходные тексты свободно доступны через интернет, либо высылаются читателям в ответ на их запросы по электронной почте. На ее освоение достаточно 5-6 лекций, она преподается в рамках курса по машинной графике на трех факультетах НГУ, а также используется в учебном процессе в Дрезденском техническом университете (Германия).
Библиотека БЕЗЬЕ для C/C++ (Windows, Mac), реализующая теоретико-множественные операции на плоскости над областями, ограниченными кривыми Безье 3-ей степени, применяется для описания областей в расчетных задачах.
Метод световых сеток может быть достаточно просто встроен в существующие алгоритмы и системы синтеза изображений (RenderMan, 3Dstudio, Maya, инструментальные средства разработки мультимедийных приложений и др.). По сравнению со стандартной лучевой трассировкой он позволяет: а) ускорить и упростить процесс расчета теней; б) повысить реализм изображений за счет генерации мягких теней; в) ускорить расчет сцен, содержащих большое количество источников света и объектов, и/или при изображениях большого разрешения; г) интерактивно управлять процессом синтеза изображения. Метод световых сеток позволяет последовательно повышать качество изображения путем добавления дополнительных точек световой сетки в расчеты освещенности объектов сцены.
Апробация. Все представленные в диссертации результаты докладывались на Всесоюзных и международных конференциях и семинарах: 6-я конференция по эксплуатации вычислительных машин БЭСМ-6 (Тбилиси, 1976), конференция по автоматизации научных исследований (Новосибирск, 1977), первая конференция по машинной графике (Новосибирск, 1977). II Всесоюзное совещание "Диалог-79" (Протвино, 1979), II школа-семинар "Интерактивные системы" (Боржоми, 1980), III школа-семинар "Интерактивные системы" (Боржоми, 1981), Всесоюзная конференция по проблемам машинной графики (Новосибирск, 1981), Всесоюзное совещание по интерактивным системам проектирования (Москва, ИПУ, 1981), Всесоюзная конференция по проблемам машинной графики и цифровой обработке изображений (Владивосток, 1985), Международная конференция по машинной графике (ЧССР, Смоленице, 1986), Всесоюзная школа-семинар "Информатика и интерактивная компьютерная графика" (Цахкадзор, 1987), 4-я Всесоюзная конференция по машинной графике (Серпу-
хов, 1987), 13-я школа "Программирование" (Болгария, Варна, 1988), Всесоюзная конференция по машинной графике (Новосибирск, 1989), Международная конференция по визуальному анализу и интерфейсу VAI-91 (Новосибирск, 1991), Международные конференции Графикон'94, Графикон'96, Графикон'97, Графикон'98, Графикон'99, Графикон'2000, Графикон'01, Графикон'02, АНИГРАФ-98 (Москва, 1998), Международные конгрессы по индустриальной математике INPRIM (Новосибирск, 1998, 2000), International Conference on Computer Science (Амстердам, 2002), международный семинар "Virtual environments on PC clusters" (Протвино, 2002).
Личный вклад автора
Система СМОГ 1 -ый уровень разработана коллективом под руководством А.Я. Куртукова, реализована в 1969 году для ЭВМ М-220 с графопостроителем Benson-121. Прототип системы для БЭСМ-6 был реализован автором диссертации на БЭСМ-Алгол в 1971 году. На основе результатов опытной эксплуатации автором совместно с СВ. Гориным, В.И. Дворжецом, А.Я. Куртуковым была разработана архитектура системы для БЭСМ-6, реализация завершена к 1975 году. Подсистему управления графическим выводом СУГВ автор разрабатывал самостоятельно. Перенос СМОГ и СУГВ на ЕС ЭВМ осуществляли С.А. Упольников и В.И. Дворжец. Перенос на СМ-ЭВМ - Р.Н. Вильданов. Л.Ф. Васильевой выполнены все подключения нестандартных графических устройств в ОС Д-68, ДИАПАК и ДИСПАК, обеспечена программная связь разнотипных ЭВМ в универсальной магистрали системного обмена УМСО.
Система СМОГ 2-ой уровень разработана автором совместно с СВ. Гориным, В.И. Дворжецом.
СПО ГД (программирование комплекса "главная ЭВМ - сателлит") разработана совместно с A.M. Мацокиным, А.И. Чубаревым. В реализации сателлитного обеспечения участвовали Р.Н. Вильданов и В.И. Торшин.
Автору принадлежит определяющий вклад в разработку концепции системы и протокола межмашинного обмена.
Перенос системы СМОГ на Burroughs-6700, Labtam-3215/FS, IBM-PC (DOS и Windows) осуществлялся автором с помощью С.А. Плеханова, Ю.А. Ткачева, А.В. Русскова, К.К. Дурнецова, П.В. Горана, СИ. Купря-хина.
Система СМОГ-85. Общая концепция системы разрабатывалась совместно с A.M. Мацокиным. В реализации автор руководил разработкой компонент СМОГ, СПО ГД (реализация с А.И. Чубаревым, В.И. Торшиным, Р.Н. Вильдановым), БАЗАД (с Н.С. Шуптой), ФОРТ (с С.А. Плехановым), а также выполнил ряд работ по программированию алгоритмов визуализации в компоненте СПЕЙС.
Библиотека БЕЗЬЕ. Автор разработал программный интерфейс и участвовал в разработке алгоритмов и реализации программ наравне с A.M. Мацокиным и С.А. Упольниковым.
SmogDX. Системная часть разработана совместно с Ю.А. Ткачевым, который также реализовал двумерную графику. Часть, относящаяся к трехмерной графике - SmogDX/3D - принадлежит автору.
Алгоритмы реалистической визуализации разрабатывались автором и коллективом его магистрантов и аспирантов: И.М. Севастьянов (метод световых сеток), Д.В. Мальдон, Е.В. Парилов, О.А. Ким, С.А. Саттаров.
В 1986 году автору была присуждена бронзовая медаль выставки ВДНХ СССР за разработку программного обеспечения (графическая система авторской подготовки документов ФОРТ). В 1988 году вместе с коллективом разработчиков системы СМОГ-85 автор получил диплом 3-ей степени на конкурсе прикладных работ Сибирского отделения АН СССР. В 1988 году в составе другого коллектива автор получил Государственную премию СССР в области науки и техники за разработку и реализацию алгоритмов научной визуализации. Разработ-
20 ка библиотеки БЕЗЬЕ (1998 год) и разработка системы SmogDX (1999 год) вошли в годовые отчеты ИВМ и МГ СО РАН в качестве важнейших результатов института. Разработка метода световых сеток для лучевой трассировки отмечена как важнейшее достижение в годовом отчете Сибирского отделения РАН (2001 год).
Основания для выполнения работ
Все работы, представленные к защите, выполнялись в соответствии с планами Института, Государственными программами, хоздоговорами по темам: "Пакет программ для вывода информации из ЭВМ на графические устройства" (Per. 76051923, 1974-1980гг.), "Разработка математического обеспечения устройств графического ввода-вывода" (Per. 76093229, 1976-78гг.), "Математические методы и программное обеспечение решения трехмерных графических задач на ЭВМ" (Per. 81032953, 1981-85гг.), Государственная научно-техническая программа 0.80.03 "Создать новые и развить действующие системы автоматизированного проектирования (САПР) и автоматизированные системы научных исследований (АСНИ) в народном хозяйстве", задание 09.14.А "Создать и ввести в эксплуатацию в ВНИИПАС программно-технический комплекс для проектирования объектов машиностроения на базе локальной сети ЭВМ высокой производительности, персональных ЭВМ и профессиональных рабочих станций интерактивной графики" (1986-90гг.), "Математические методы трехмерной машинной графики" (Per. 0186.0125723, 1986-95гг.; Per. 01.9.30001314, 1996-1999гг.), "Разработка методов декомпозиции решения краевых задач и аппроксимации функций" (Per. 01.20.0004754, 2000-2002гг.); Государственной научно-технической программе "Перспективные информационные технологии" (проекты № 242 - 1992г., № 1054 - 1995г., № 239 - 1997г.). Дополнительно разработка алгоритмов реалистической визуализации пространственных сцен поддерживалась грантами РФФИ 96-01-01758 "Синтез реалистических изображений пространственных сцен" и 99-01-00577 "Моделирование фотореалистических изображений методами декомпозиции", которые выполнялись под руково-
21 дством автора диссертации. Развитие библиотеки БЕЗЬЕ осуществлялось при частичной поддержке РФФИ по гранту 99-07-90422ск (руководитель академик А.С. Алексеев).
Диссертационная работа состоит из введения, четырех глав и заключения. В первой главе рассматривается разработка систем СМОГ и СУГВ. Вторая глава посвящена многофункциональной графической системе СМОГ-85. Обе главы охватывают исследования и разработки графических систем для отечественных ЭВМ. В третьей главе описаны системы для персональных ЭВМ: инструментальная система VAD для программирования графического диалогового интерфейса, система авторской подготовки текстов DP и библиотека БЕЗЬЕ. Основы этих трех компонент были заложены еще при разработке системы СМОГ-85. В связи с переходом на ЭВМ типа IBM PC эти компоненты были оформлены в виде самостоятельных продуктов. Четвертая глава работы посвящена графической объектно-ориентированной системе SmogDX/3D, построенной на основе библиотеки DirectX Direct3D Retained Mode, и методу световых сеток для реалистической визуализации пространственных сцен.
После основного текста диссертации и литературы даны два приложения:
приложение 1 с иллюстрациями, показывающими результаты работы алгоритмов отображения графиков функций двух переменных и проволочных моделей пространственных сцен, разработанных автором диссертации и реализованных в рамках систем СМОГ и СМОГ-85.
приложение 2 содержит краткое описание программного интерфейса системы SmogDX/3D.
Система управления графическим выводом
Данный параграф посвящен разработке системы управления графическим выводом СУГВ как составной части математического обеспечения вывода информации из ЭВМ в графическом виде, с одной стороны, а с другой стороны, СУГВ - это программный комплекс технологической поддержки процесса вывода графических результатов в крупном ВЦ. Рассмотрим состояние на 1975 год. Задача разработки СУГВ решалась на вычислительном комплексе ВЦ СО АН СССР, который обслуживал около 1500 пользователей из 140 организаций. В сутки осуществлялось около 1200 запусков задач (см. [31]). Из них значительная часть использовала графический вывод. На рис. 1.3 представлен вычислительный комплекс, который включает: Три ЭВМ БЭСМ-6 с общей памятью на магнитных дисках. Специальные магнитофоны (СМЛ), подключенные к двум БЭСМ-6, через которые осуществляется передача графики на УГВ. СМЛ - специальная магнитная лента, которая может содержать несколько отдельных графических страниц или кадров. Устройство микрофильмирования УМКФ КАРАТ [32], осуществляющее вывод на 35мм кинопленку, непосредственно подсоединено ко второй БЭСМ-6. Графопостроители фирмы БЕНСОН ГШ, ГП2, ГПЗ, оснащенные декодерами СМЛ. Фотопостроитель (ФП) фирмы БЕНСОН, оснащенный декодером СМЛ, осуществляет вывод слайдов на фотопленку. Устройство СОМ-320 фирмы БЕНСОН, оснащенный декодером СМЛ, осуществляет вывод на микрофиши. Все устройства фирмы БЕНСОН используются в режиме off-line через СМЛ. Часть УГВ имеет инкрементальный входной язык - по одной команде осуществляется передвижение пера на 1 шаг, другие УГВ умеют отрабатывать отрезки.
Пунктирные линии указывают на перенос СМЛ оператором. Подключение ГП1 в режиме on-line использовалось, как правило, в специальных случаях.
В начале 1970-х в нашей стране также были разработаны и эксплуатировались графические системы: ГРАФОР [24, 25], ГРАФАЛ [27], комплекс построения номограмм [26] и др. Эти системы с богатой для того времени функциональностью были разработаны для какого-то одного типа графических устройств. С одной стороны, такое решение позволяет наиболее полно учесть специфику конкретного устройства и эффективно реализовать графические алгоритмы. С другой стороны, это решение усложняет адаптацию графической системы к другим устройствам, в частности, к устройствам с более богатыми возможностями. В проектировании графических систем того времени был отмечен принцип "перевернутой пирамиды" [33], когда на самом нижнем уровне (драйвер системы) получается описание результата не в командах конкретного УГВ, а в виде набора графических примитивов - виртуальных команд. Задача преобразования этих виртуальных команд в команды реального УГВ решается на самом нижнем уровне системы - "острие пирамиды". Адаптация графической системы к УГВ заключалась в разработке модуля, транслирующего графические примитивы в команды управления УГВ.
Автор диссертации предложил дальнейшее развитие этого подхода, которое заключается в разработке СУГВ как самостоятельной системы, представляющей собой "общий знаменатель" всех используемых УГВ и имеет собственный входной язык [34, 35]. В этом случае каждая конкретная графическая система, эксплуатируемая на вычислительном комплексе, должна иметь модуль преобразования своего множества графических примитивов в команды входного языка СУГВ. Отметим, что в начале 1970-х в ВЦ СО АН СССР разнообразие УГВ как по системе команд, так и по качеству получаемого материала, было уникальным для нашей страны. 1) Графопостроители фирмы БЕНСОН. Шаг устройства - 0.05, 0.025 мм. Носитель результата - бумага, формат до АО. До 4-х перьев. Шаговые и интерполирующие графопостроители. Подключение - on-line и off-line. 2) Фотопостроитель фирмы БЕНСОН, шаговый. Результат - слайд. Носитель результата - 35мм фотопленка. "Растр" - 4096x3072; 8 градаций яркости луча. Имеет видеоконтрольное устройство (ВКУ) - дисплей на запоминающей трубке с полем изображения около 200x150 мм, который дублирует построение изображения на слайде. Подключение - off-line. 3) Устройство микрофильмирования (УМКФ) КАРАТ, интерполирующий. Результат - фильм. Носитель - 35мм фотопленка. Выдерживает расстояние между кадрами. "Растр" - 4096x3072; 16 градаций яркости луча; 16 степеней времени экспозиции; 16 градаций диаметра пятна (толщина линий). Текстовый знакогенератор позволяет выводить прямые печатные знаки в двух размерах: 64 строки по 128 знаков или 32 строки по 64 знака. ВКУ на запоминающей трубке с полем изображения около 200x150 мм с независимым управлением. Подключение - on-line. 4) Устройство вывода на микрофиши СОМ-320 фирмы БЕНСОН, интерполирующее. Носитель результата - микрофиша, на которой располагается: 14 строк по 16 страниц, 16 строк по 18 страниц или 8 строк по 9 страниц. 8 градаций яркости луча. Текстовый генератор обеспечивает печать на одной странице 64 строки по 132 знака одного размера (аналог стандартного печатающего устройства IBM/360). Подключение - off-line.
Пакет для управления внешней памятью и работы со структурой данных
Основная задача при создании 1111 БАЗАД [58, 61] - обеспечение фортран-программ средствами динамического образования внешних динамических массивов с прямым доступом к их элементам. Решение этой задачи повлекло за собой разработку всего комплекса вопросов, связанных с хранением информации во внешней памяти и доступом к ней.
ГШ БАЗАД разрабатывался, в первую очередь, с учетом стоящих перед нами задач из области машинной графики и вычислительной геометрии. По своей сути это не СУБД, а скорее, аналог файловой системы. Дело в том, что на момент разработки не было общепризнанной СУБД, более или менее удовлетворяющей различным требованиям разработчиков программных средств машинной графики. Это видно и на примере международного графического стандарта ГКС [6, 7], в котором имеются только понятия графического сегмента и метафайла, т.е. линейные структуры, но не специфицируются структуры хранения. Для САПР, конечно, важен более высокий уровень - это пакеты вычислительной геометрии, которые должны применяться в системах моделирования. Различные представления геометрических объектов (многогранники, параметрическое задание, поверхности Кунса [63] и т.д.) требуют в первую очередь разработки структур данных, которые зависят от представления геометрии в ЭВМ, и которые, в свою очередь, определяются характером работы с объектами (объединение, пересечение, разность, разрезы, отображение с удалением невидимых линий и т.п. ). Многие "геометрические" алгоритмы в случае достаточно слож ных объектов используют внешнюю память, при этом требуется динамически создавать и расширять рабочие файлы.
Отметим, что многие графические школы страны также обратились к решению прикладных проблем и разрабатывали аналогичные задачи: СУБД РПСАР РШМ АН СССР [64], иерархическая СУБД [65] и база графических данных ПРИС [66] РІАиПУ ДВНЦ АН СССР и др. Отличием указанных разработок было то, что они строили СУБД вполне конкретного типа - сетевая или иерархическая. База данных ПРИС, более того, была ориентирована на графические данные. Определялись понятия объекта и отношений между объектами, на уровне языка системы учитывались типы переменных: целые, вещественные и т.д. В случае ПН БАЗАД было принято решение построения системы в 2 уровня. Первый уровень пакета обеспечивал независимую от платформы систему файлов прямого доступа. Как известно, на БЭСМ-6 была возможность программировать только физический обмен между памятью и устройствами прямого доступа, а на ЕС ЭВМ предоставлялось большое разнообразие для работы с последовательными файлами, а в случае работы с динамическими файлами прямого доступа не было требуемого сервиса. С другой стороны, автор уже имел многолетний опыт работы с оперативным графическим архивом СУГВ (см. п. 1.2) на БЭСМ-6, ЕС ЭВМ и Burroughs-6700. Именно этот архив и был взят за основу файловой системы 1111 БАЗАД. Второй уровень пакета предоставлял средства организации иерархических структур данных и работы с ними. Интерфейс между обеими частями пакета четко выделен.
Следует отметить, что ни на момент разработки ни в настоящее время не существовало работ, которые бы говорили, что для разработки графических алгоритмов или программ для АСНИ и/или САПР лучше всего надо использовать какую-либо конкретную СУБД - некий стандарт. Как правило, выбор СУБД определялся исходными условиями разработки (например, заказчик настаивал на использовании конкретного математического обеспечения), начальным набором решаемых графических и геометрических задач и другими факторами.
Успех той или иной базы данных в конечном итоге определялся решаемыми на их основе прикладными задачами и реализованными алгоритмами.
Основным понятием 1111 БАЗ АД является виртуальная внешняя память (ВП) это набор данных прямого доступа на ЕС ЭВМ или БЭСМ-6. Для ее организа ции и работы с ней используются стандартные средства операционной системы. ВП строится как коллективная, что важно при создании баз данных в рамках интегрированных САПР. Единицей измерения информации выбран байт. На уровне ВП выделено понятие области - динамический байтовый массив. Идентификация областей производится по имени и шифру программиста. С каждой областью ассоциированы основные атрибуты: пароли доступа, даты последних записи и чтения, количество обращений, длина в байтах. Пакет БАЗАД предоставляет следующие средства при работе с ВП и областями: - создание ВП; - образование и уничтожение области в ВП; - работу с несколькими ВП в одной программе; - работу с несколькими областями в одной ВП; - работу с одной и той же ВП (и даже областью) в различных программах; - обмен информацией между программными переменными и областями: при записи за пределы области, она (область) автоматически расширяется; - уменьшение размера области; - сервисные функции, такие как смена паролей, значений атрибутов и т.д. В ПП БАЗАД введено понятие ВПОЗУ - виртуальная внешняя память, которая моделируется на оперативной памяти. Использование ВПОЗУ вместо ВП удобно в том случае, когда общий объем динамически возникающих массивов дос # таточно мал, меньше, чем объем доступной оперативной памяти, особенно, в тестовых расчетах. В пакете отсутствует понятие сборки мусора, каталоги ВП организованы таким образом, что после уничтожения области все занимаемое ею пространство сразу же может быть использовано. При разработке пакета БАЗАД усовершенствована структура каталогов, которая использовалась для технологического архива системы управления графическим выводом СУГВ (см. п. 1.2). На ВП может быть организована иерархическая структура данных. Основные понятия структуры данных - объект и куст. Объект структуры данных характеризуется: - именной частью, которая служит целям идентификации объекта и его поиска по структуре; - ссылочной частью, состоящей из ссылок "вверх" и ссылок "вниз", которые и поддерживают иерархию объектов. - информационной частью, имеющей переменную длину в зависимости от объема данных об объекте; Куст - это подструктура, определяемая выделенным объектом, называемым головой куста, и состоящая из всех объектов, до которых можно дойти от головы, используя только ссылки "вниз". Данные размещаются в оперативной (обязательно) и во внешней (не обязатель но) памяти ЭВМ. Основные операции: - инициализация структуры данных; - создание объекта; - образование и разрушение связей;
Библиотека БЕЗЬЕ для конструирования плоских областей
Конечно, чертежи машиностроительных деталей и их "трехмерные" изображения выводились во всех графических системах проектирования. Но проектная документация не ограничивается только ими - в принципе, готовятся документы, которые содержат обоснование конструкторского решения в САПР с формулами, графиками и таблицами расчетных данных. В АСНИ часто результатом является научная статья или отчет. Для того, чтобы обеспечить в рамках СМОГ-85 полный процесс документооборота, была поставлена задача разработать специализированное программное средство (ПС) ФОРТ для оформления документов, содержащих текст, математические формулы, таблицы, рисунки и распечатки файлов (например, текстов программ или результатов расчетов). В связи с отсутствием матричных принтеров было принято решение получать документы на графических устройствах, через СМОГ. В дальнейшем ПС ФОРТ было выделено в отдельный программный продукт DP (см. п. 3.3).
Во время создания СМОГ-85 разработка программных продуктов требовала подготовки документации по ГОСТу ЕСПД. Поэтому наряду с автоматизацией создания самого пакета программ необходимо было предусмотреть средства автоматизации подготовки и получения программной документации. В конце 1970-х и начале 1980-х отмечался большой интерес к системам оформления текстовых документов вообще: инструктивных материалов, статей и т.п. на основе применения ЭВМ. В СССР был разработан ряд программных средств (ПС), обеспечивающих получение текстовых документов на печатающих устройствах ЭВМ и фотонаборных автоматах, см. [99-107]. Описание документа выполняется на специальных языках и хранится на машинном носителе. В случае программной документации для хранения этого описания выбирается тот же носитель, что и для самих программ. Наличие доступного описания документа позволяет оперативно вносить в него изменения синхронно с изменениями в программах. В отличие от "ручной подготовки" при перепечатывании не возникает новых ошибок.
Программные средства оформления текстовых документов того времени можно дифференцировать по назначению, сложности подготавливаемых документов, мощности языка описания документов. Подавляющее число распространенных ПС было ориентировано на получение документов на печатающих устройствах ЭВМ (АЦПУ). Это в значительной степени было связано с доступностью на званных устройств, а, следовательно, и с потенциальной тиражируемостью разработанного ПС. АЦПУ - устройство очень бедное с точки зрения изобразительных средств, и поэтому ПС, разработанные для них, дают документ низкого качества. Основное назначение таких документов - использование конечным потребителем, т.к. это обычно сверхоперативные инструктивные материалы и рабочая программная документация. Сложность документов, получаемых на АЦПУ, также невысока — только текст, один шрифт, один размер знаков.
Языки описания документов по мощности тоже давали довольно широкий спектр. У одного конца спектра - язык широко распространенных программ листовой печати на АЦПУ. Здесь все функции форматирования возложены на пользователя, и даже небольшая корректировка текста могла привести к довольно трудоемкой правке исходного файла (например, от места исправления до конца абзаца). Ближе к другому краю спектра располагаются языки таких программных систем, как ДОКУМЕНТАТОР [104], ПАРИС [101].
ПС, описанные в работах [99-101, 103-107], были ориентированы на устройства типа пишущей машинки или фотонаборного автомата и предназначались для подготовки машинописных и ротапринтных изданий. В системах документирования этого класса из терминального устройства "выжимались" все возможности, на которое оно только рассчитано. Сложность подготавливаемых документов существенно возрастает: они могут включать формулы, таблицы, иллюстрации. Но в большинстве своем эти ПС оформление формул и рисунков возлагали либо на этап "ручной доработки" документа целиком, либо таким способом, как это делалось в системе СТРЕЛА [105, 108], т.е. получение иллюстраций на графопостроителе с последующей наклейкой их на документ в зарезервированном системой месте страницы.
Объектно-ориентированная система SmogDX/3D
В пакете СПЕЙС системы СМОГ-85 был создан мощный аппарат конструирования плоских объектов с границей, состоящих из отрезков прямых [96, 97]. Плоские области применяются в конструировании, при работе с изображениями, в научных расчетах. Даже при конструировании шрифтов часто используются плоские объекты с криволинейными границами, как правило, заданными отрезками параметрических кривых. Пакет СПЕИС криволинейные границы аппроксимировал отрезками прямых, но, как известно, в ряде случаев такая аппроксимация может приводить к неверным решениям. В связи с этим встала задача разработки библиотеки для конструирования плоских объектов, состоя щих из областей с границей, состоящей из отрезков параметрических кривых, заданных как четырехточечные отрезки Безье [63].
На основе опыта работы с приложениями, построенными на основе применения системы СМОГ-85 (например, программа решения уравнения Пуассона [72], работы по триангуляция области [129]) были сформулированы задачи, которые должны решаться с помощью этой библиотеки. Дополнительное требование к набору операций библиотеки, заключалось в том, чтобы на основе их применения программист мог достаточно просто разработать диалоговый графический интерфейс для конструирования плоских областей. В целом, необходимо было разработать и реализовать следующие алгоритмы: Разработка описания области, задания области, задания плоского объекта. Проверка правильности задания области/объекта. Другими словами, контроль входных параметров. Реализация характеристической функции области/объекта, которая по ее описанию определяет принадлежность к ней точки плоскости. Определение точек пересечения прямой с границей объекта. Реализация теоретико-множественных операций над областями и объектами. Теоретически эти задачи достаточно исследованы, см. например, [142 - 144], но в открытом пространстве нет доступных реализаций. Все, что можно найти в интернет, не работает вообще - не то что ненадежно. Это стало особенно заметно после публикации [145], когда к авторам стали обращаться по электронной почте. На практике часто встречаются программные продукты, использующие подобные плоские объекты и выполняющие подобные операции, например:
Как правило, для задания кривых применяются трех- и четырехточечные сегменты (дуги) кривых Безье [63].Конечно, ряд продуктов ориентируется на растровое представление. В этом случае алгоритмы более простые. По всей вероятности, выделение подобной библиотеки в отдельный продукт не делалось по следующим причинам: Данные операции не выделены в качестве отдельной библиотеки в самом программном продукте, обеспечивающим двумерное моделирование; Реализация библиотеки требует устойчивых численных алгоритмов пересечения кривых и прямых, что является в своем роде know-how и определяет одну из основных ценностей библиотеки. Как правило, продается более сложный и дорогой программный продукт.
Исходные данные могут быть представлены пользователем или являться результатом выполнения каких-либо операций. Область может строиться в диалоге на основе визуальной обратной связи или вводиться при помощи устройства типа сколки. В обоих случаях возможны ошибки задания, например, разрывы границы: экран дисплея имеет конечное разрешение, человек повторно неточно указывает координаты той же (логически) точки. В связи с этим одним из параметров настройки библиотеки является мера отождествления точек Є, которая говорит, что если во входной информации две точки отстоят менее, чем на Є, то эти точки отождествляются. Область - это открытое связное множество [146], но в практике геометрического моделирования, как правило, применяются более сложные объекты: совокупность областей, замкнутые связные точечные множества и др. Более того, пользователь видит на экране или бумаге область вместе с границей, тем не менее, в качестве простейшего объекта мы выбрали область на плоскости.
