Содержание к диссертации
ВВЕДЕНИЕ 5
ІЇЇАВА I. ГЕОМЕТРИЧЕСКИЕ ЗДЦАЧИ МАШИННОГО СИНТЕЗА ПОЛУ ТОНОВЫХ ИЗШРАЖЕНИЙ И ОРГАНИЗАЦИЯ ИХ РЕШШИЯ 17
1.1. Формальное описание процесса синтеза полутоновых изображений 17
1.2. Изометрические примитивы для представления объектов 21
1.3. Декомпозиция граней и объектов на выпуклые части 27
1.4. Иерархическое описание моделируемой сцены 32
Ї.5. Преобразование координат и отсечение 36
1.6. Удаление невидимых поверкностей 39
1.7. Тонирование изображений 46
1.8. Организация.вычислительного процесса синтеза полутоновых изображений 49
Выводы по первой главе 59
ШАВА 2. АЛГОРИТМИЗАЦИЯ ОПЕРАЦИЙ НДД ВЫПУКЛЫМИ МНОГО УГОЛЬНИКАМИ 60
2.1. Операционная среда подсистемы синтеза полутоновых изображений 60
2.2. Построение выпуклой оболочки множества точек на плоскости 66
2.3. Ориентированная нумерация вершин многоугольника 72
2.4. Определение взаимного расположения ,двух многоугольников 75
2.5. Отсечение выпуклых многоугольников 83
2.6. Растровое преобразование выпуклых многоугольников 87
Выводы по второй главе . 95
ШВА 3. УДАЛЕНИЕ НЕВИДИМЫХ ПОВЕРХНОСТЕЙ й ГОСТРОЕНИЕ ШЕЙ 96
3.1. Использование связности при анализе видимости и затенения 96
3.2. Линейное подразделение плоскости и пространства 99
3.3. Алгебрологический метод формирования приоритетного списка ЮЗ
3.4. Проведение разделяющих плоскостей ПО
3.5. Замкнутые приоритетные Циклы и разрезание объектов 121
3.6. Формирование приоритетного списка 126
3.7. Приложение алгоритма удаления невидимых поверхностей к удалению невидимых линий 129
3.8. Построение теней 132
Выводы по третьей главе 141
ЇЇІАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ПОДСИСТЕМЫ СИНТЕЗА ПОЛУТОНОВЫХ ИЗОБРАЖЕНИЙ 143
4.1. Структуры графических данных 143
4.2. Вычислительные процедуры 146
4.3. Методика использования подсистемы синтеза полутоновых изображений 151
4.4. Оценки быстродействия подсистемы синтеза полутоновых изображений 156
4,5, Практическое внедрение результатов исследо ваний 162
Выводы по четвертой главе 164
ЗАКЛЮЧЕНИЕ , 165
ЛИТЕРАТУРА 167
ПРИЛОЖЕНИЕ 180
Введение к работе
За последние два десятилетия получила интенсивное развитие новая ветвь прикладной математики - машинная графика. Её применение в научно-исследовательской и проектно-конструкторской практике не только позволяет эффективно решать поставленные задачи, но и саму их постановку выводит на качественно новый уровень. Машинная графика является важной составной частью систем автоматизированного проектирования и автоматизации научных исследований, о которых в "Основных направлениях экономического и социального развития СССР на I98I-I985 годы и на период до 1990 года" сказано: "расширять автоматизацию проектно-конетрукторских и научно-исследовательских работ с применением электронно-вычислительной техники".
Машинная графика вобрала в себя достижения многих разделов прикладной математики: начертательной геометрии и черчения, аналитической и дифференциальной геометрии, теории графов и математической логики, теории множеств и методов оптимизации, численных методов и теории групп, программирования для ЭВМ и теории фокальных грамматик. Кроме того, при разработке графических систем привлекаются оптика, электроника, теория информации, цифровая обработка сигналов, психология и физиология зрительного восприятия. Разработке идей и методов, прямо или косвенно относящихся к машинной графике, посвящены многочисленные работы советских и зарубежных ученых и специалистов.
В работах И.Й.Котова, В.Е.Михайленко, В.С.Обуховой, В.А.Оси-пова, А.В.Павлова, А.Л.Подгорного, Н.Н.Рыжова и их учеников разработаны графические и аналитические методы конструирования поверхностей, их аппроксимации, построения обводов [45,56-60,63,
Большое внимание уделено в литературе методу центрального проецирования как важному средству повышения наглядности изображений. Вопросам построения перспективных проекций и изучения их свойств посвящены работы Г.ЇЇ.іІртемьевой, А.Я.Эиетного, Ю.И.Короева, Н.Л.Русскевича, К.А.Сазонова, М.В.Федорова [3,35, 44,70,80].
Важную роль в развитии машинной графики играют работы, посвященные машинной реализации графических методов и разработке алгоритмов. Этими вопросами занималось большое число советских и зарубежных исследователей: Ю.М.Баяковский, Н.Ф.Боднар, Б.А.Галактионов, А.Г.Горелик, Д.М.Зозулевич, С.В.Клименко, В.А.Львов, В.С.Полозов, В.Н.Семенов, П.Безье, Дж.Блинн» В.Гилой, У.Ньюмен, М.Ньюэлл, А.Сазерленд, Р.Сцрулл, Т.Уиттед, Р.ЩумеЙкер и многие другие [1,8-12,17,18,21,25,36,39,47,61,74,96,97,125,126,128].
В работах Ю.М.Баяновского, В.А.Галактионова, В.М.Глушкова, А.Г.Горелика, В.Й.Дворжеца, Л.Г.Дмитриева, Ю.В.Котова, В.В.Мана-ко, А.Й.Никитина, В.С.Полозова, К.А.Сазонова [1,8,10,17,19-21, 29,30,39,43,47,48,55,72,74] разработаны вопросы объединения методов и алгоритмов в графические панеты, обладающие развитым интерфейсом и способностью вести диалог с пользователем.
В результате целенаправленных усилий разработаны такие системы для моделирования и отображения графической информации, как ГРАШОР, ГРШЗМ, ФАП-КШ, ИНТЭАР, АЛГР4Ф, АТОМ, ГРАС и другие. Машинная графика успешно применяется при архитектурном проектировании, в различных отраслях машиностроения, в радиоэлектронике, в молекулярной химии, при обработке экспериментальных данных. Многообразие графических систем, появление похожих разработок в различных организациях стимулировали работы по их стан дартизации и унификации [17,40,73,118].
Однако все эти системы относятся к так называемой традиционной графике, в основе которой лежит использование векторных дисплеев и графопостроителей. Векторные изображения, получаемые на этих устройствах, являются вполне приемлемыми в различных системах проектирования и разработки конструкторской документации. Иногда они служат единственно возможной формой представления графической информации, как при автоматизированной трассировке печатных плат. Но в то же время воспроизведение на векторных графических терминалах наглядных изображений реальных объектов является труднорешаемой задачей. Кроме того, в векторных дисплеях сложность воспроизводимых изображений обычно ограничивается появлением мерцания. Имеются приложения, где векторные изображения вообще непригодны, как в синтезирующих системах визуализации тренажеров транспортных средств. Для решения таких задач необходимы полутоновые или цветные изображения, формируемые на экране растрового устройства отображения телевизионного типа.
Необходимо отметить, что в части решения геометрических задач синтез цветных изображений практически не отличается от синтеза полутоновых изображений. Различия возникают только при тонировании поверхностей. Поэтому, хотя в дальнейшем будет употребляться термин "полутоновые изображения", изложенные метода и алгоритмы целиком применимы и для синтеза цветных изображений.
Потребность в полутоновой машинной графике ощущается во всех областях, где необходимо работать с наглядными изображениями реальных трехмерных сцен. Традиционными областями применения таких изображений давно стали архитектурное проектирование, создание новых образцов автомобильной и авиационной техники, эргономичес ком проектировании транспортных средств и операторско-диспетчер-ских пунктов. Новые задачи перед системами полутоновой графики поставило интенсивное развитие робототехники. Разработка систем машинного зрения, моделирование траекторий перемещения манипуляторов и другие проблемы значительно удобнее решать с помощью машинной графики. Не случайно первый алгоритм удаления невидимых линий и первое применение однородных коорцинат в машинной графике были осуществлены Робертсом [67] при разработке роботов-манипуляторов. Наглядность полутоновых машинных изображений позволяет использовать их на тех стадиях проектирования, где необходимо производить отбор вариантов с учетом эстетических критериев оценки.
Графические системы, создающие полутоновые изображения, оперируют обычно с трехмерными объектами, составляющими некоторую сцену. Для большинства приложений характерна статичность сцен и моделирование перемещения условного наблюдателя, осматривающего их. Гилой отмечает [18], что "получение изображений /относительно хорошо отображающих реальность/ трехмерных тел является самостоятельной целью; как правило, не делается попыток производить манипуляции с такими объектами в интерактивном режиме", именно в такой постановке и будут рассматриваться задачи синтеза изображений в данной работе.
К синтезируемым изображениям трехмерных сцен предъявляют требования соблюдения информационного и психофизиологического подобия реальным объектам. Это означает, что синтезируемые изображения должны адекватно отображать моделируемую сцену, чтобы образ, формирующийся у наблюдателя при восприятии изображений, был близок к образу реальных объектов среды. В связи с этим, уместно кратко рассмотреть средства, повышающие наглядность изо бражений.
В результате многочисленных исследований в области зрительного восприятия [22,23,33,38] установлено, что зрительный анализатор человека нельзя рассматривать обособленно как некоторый, хотя и сложный, оптический прибор. Зрительное восприятие осуществляется системой глаз-мозг. Мозг производит корректировку воспринимаемых от глаза изображений, опираясь на накопленный опыт, который выражается в присутствующих в памяти ассоциативных связях. Входной информацией системы являются геометрические искажения, изменения яркости и цвета, перемещения объектов. Эта корректировка позволяет обычно правильно воспринимать формы рассматриваемых объектов и их удаленность от наблюдателя. Иногда в результате осмысления видимой картины у наблюдателя формируются неправильные выводы о реальной конфигурации сцены. В таких случаях говорят о зрительных иллюзиях. Иллюзии возникают при наличии совокупности признаков, допускающей двусмысленное толкование.
Синтезируемые на ЭВМ изображения всегда являются в большей или меньшей степени условными. При работе с такими изображениями на зрительную систему возлагается дополнительная нагрузка по их распознаванию и правильному восприятию. Машинные изображения вычисляются в виде проекций трехмерных сцен, поэтому их зрительное восприятие можно рассматривать как обратную задачу - восстановление трехмерной сцены по её проекциям. Правильное и быстрое выполнение этой операции достигается введением в изображение геометрических свойств, способствующих однозначному его толкованию.
Одно из важнейших таких свойств - перспективное преобразование, уже несколько веков используемое художниками и архитекторами. "Перспектива является изображением наиболее близким к видимым формам предмета и, поэтому, наиболее наглядным. По перс пентиве можно правильно судить о внешнем облике, о пропорциях и соотношении объемов и отдельных элементов, об ожидаемом зрительном гвосцриятии проектируемого здания" [70]. Перспективное преобразование вводится в изображение путем простой формализации и представления в аналитическом виде процедуры центрального проецирования. Аппарат центрального проецирования при построении машинных изображений обычно задается положением точки зрения и направлением главного луча; картинная плоскость предполагается перпендикулярной главному лучу и находящейся от точки зрения на определенном расстоянии. Формальный характер построения перспективных изображений с помощью ЭШ позволяет получить объективную картину, избегая ситуаций, о которых пишет H.JLFyc-скевич [70]: "Некоторые авторы при построении перспектив отступают от геометрических методов построения и, пытаясь достичь желаемого результата, вносят случайные поправки. В итоге получается перспектива не запроектированного в действительности объекта, а такого, каким его хотелось бы видеть архитектору".
Другим важным свойством, повышающим наглядность изображений, является наличие теней [37]. Тени дают хорошее представление о пространственных соотношениях между объектами и поверхностями, позволяют восстанавливать по проекции особенности формы. Разумеется, при синтезе изображений с тенями трудно воспроизвести реальные физические процессы: дифракцию света, неравномерность интенсивности тени и т.п. Однако и без учета этих явлений можно получить достаточно выразительные затененные изображения.
Ще одним способом повышения наглядности машинных изображений является удаление объектов и их частей, заслоненных другими объектами. Эту процедуру называют удалением невидимых линий или удалением невидимых поверхностей. Реальное физическое явление - непропускание света непрозрачными объектами - при моделировании на ЭВМ оказывается едва ли не самой сложной и трудоемкой задачей в машинной графике.
Перспективой, тенями и удалением невидимых поверхностей не исчерпывается список возможных способов повышения наглядности машинных изображений; можно также воспользоваться средствами архитектурной композиции, управляющими зрительным восприятием: объемно-пространственной структурой, членением изображения, указателями масштаба [49]. Однако за исключением архитектурных приложений использование этих средств затруднительно, т.к. требует внесения в сцену дополнительных элементов.
Получение наглядных изображений не является единственной проблемой при создании систем синтеза полутоновых изображений. Другая важная проблема состоит в быстродействии этих систем. Быстродействие - это серьезный фактор, обуславливакщий эффективность и сферу применения графической системы. При необходимости интерактивной работы проектировщика с графической системой время синтеза одного кадра изображения должно исчисляться секундами. Ще более высокие требования предъявляются к быстродействию, если скорость смены кадров должна обеспечить иллюзию непрерывного перемещения наблюдателя. Это так называемый синтез изображений в реальном времени. Как известно [52], чтобы изображение воспринималось без мельканий, частота его регенерации должна составлять 25-30 Та,; для создания впечатления непрерывности перемещения последовательные кадры должны появляться через 0,11-0,13 сек. Системы синтеза изображений в реальном времени стали использоваться в последние годы в имитаторах визуальной обстановки авиационных тренажеров [5]. Большая часть вычислений в них выполня ется специальными аппаратурными блоками. Предсказывая, что современные синтезирующие системы визуализации будут удовлетворять потребностям практики вплоть до рубежа 2000 года, специалисты, тем не менее, отмечают необходимость разработки новых более эффективных графических алгоритмов [124]. Это объясняется чрезвычайно высокой стоимостью аппаратурной реализации систем синтеза изображений в реальном времени. Снижение стоимости может быть достигнуто созданием высокоэффективных алгоритмов и минимизацией специального оборудования.
Интерактивные графические системы ориентируются на использование ЭВМ общего назначения, объем специальной аппаратуры в них незначителен. Тем более остро они нуждаются в высокой производительности алгоритмов. Поиск новых алгоритмов осуществляется в направлении исследования и применения геометрических свойств выбранного набора примитивов, структур графических данных, методов сортировки, способов представления трехмерных объектов. Перспективным направлением совершенствования алгоритмов синтеза изображений является использование связности.
Понятие связности /когеренции/ было введено в машинную графину Сазерлендом и др. [126] и быстро распространилось среди специалистов. Оно характеризует существование локально постоянных свойств сцены или изображения, позволяющих прогнозировать с высокой степенью вероятности наличие определенных закономерностей в анализируемой ситуации. Различают пространственную, объектную, реберную, кадровую, растровую и другие виды связности. Например, растровая связность заключается в большом сходстве последовательных строк растра. Использование свойств связности состоит обычно в принятии некоторых решений, которые затем лишь незначительно уточняются и корректируются на основании анализа конкретной ситуации. Однако очень часто свойства связности учитываются только в каких-то локальных процедурах, например, для ускорения сортировки. Лнализ существующих алгоритмов показал, что далеко не всегда авторы используют все свойства геометрии моделируемой сцены. Между тем, данные, обрабатываемые алгоритмами машинной графики, являются не абстрактными числами, а геометрическими параметрами, характеризующими форму объектов, топологию соединения их частей, компоновку сцены. Поэтому представляется целесообразным расширить понятие связности, расіфостранив его также на глобальные геометрические свойства объектов. Такое расширение понятия связности не противоречит его исходному определению. Многие геометрические свойства при машинном решении задач не позволяют сразу получить требуемый результат, а только прогнозируют его, сокращают объем переборов, направляют решение по оптимальному пути. Сочетание локальных и глобальных характеристик является той основой, на которой возможно построение эффективных машинных методов решения геометрических задач.
Разработка машинных алгоритмов решения геометрических задач ведется по двум направлениям. Первое состоит в формализации операций, выполняемых при графических построениях [82]. Однако этот путь далеко не всегда может привести к требуемым результатам, ибо многие графические методы опираются на визуальное восприятие информации и трудноформализуемые эвристики. Построение машинных аналогов графических операций приводит к многочисленным переборам и проверкам, требующим больших затрат времени. Второе направление заключается в создании специальных методов, ориентированных на машинную обработку геометрической информации. В работах [1,21,47] рассмотрены особенности этих методов и тре бования, предъявляемые к ним.
Следует отметить, что алгоритмы синтеза полутоновых изображений нельзя рассматривать как простое расширение уже известных алгоритмов для векторной графики. При синтезе полутоновых изображений трехмерных объектов приходится работать не с отдельными отрезками и дугами кривых, а с охватываемыми ими отсеками поверхностей и объемами. Необходима разработка новых, специально приспособленных для полутоновой машинной графики алгоритмов. В настоящее время этот вопрос исследован относительно мало [12,50], В какой-то мере это объясняется отсутствием отечественных серийно выпускаемых дисплейных терминалов растрового типа. Хотя такие терминалы разработаны и используются в отдельных организациях [27,28,75,77], широкого распространения они еще не получили. С другой стороны, включение в состав вычислительных комплексов растровых терминалов тормозится отсутствием программно-алгоритмического обеспечения для этих устройств. Настоящая работа является попыткой создания такого программно-алгоритмического обеспечения.
Цель работы заключается в разработке эффективных геометрических алгоритмов и создании на их основе пакета программ, составляющего высокопроизводительную подсистему синтеза полутоновых изображений. Для достижения указанной цели были поставлены и решены следующие задачи:
- исследование основных геометрических задач, возникающих при машинном синтезе полутоновых изображений;
- разработка эффективной организации вычислительного процесса машинного синтеза полутоновых изображений;
- разработка базового набора алгоритмов для выполнения операций над выбранными геометрическими примитивами;
- разработка быстродействующего алгоритма удаления невидимых поверхностей;
- разработка алгоритма построения теней;
- создание пакета программ, реализующих разработанные алгоритмы и составляющих подсистему синтеза полутоновых изображений;
- внедрение результатов исследований. Научную НОВИЗНУ работы составляют:
- методика машинного решения геометрических задач синтеза полутоновых изображений, основанная на широком использовании глобальных и локальных свойств связности;
- базовые геометрические алгоритмы для выполнения операций над выпуклыми многоугольниками;
- алгоритмы линейного подразделения моделируемой сцены, формирования и интерпретации приоритетного списка для удаления невидимых поверхностей;
- методика построения падающих теней по теневым многоугольникам объектов;
- организация вычислений в высокопроизводительной подсистеме синтеза полутоновых изображений.
Практическая ценность. Разработанные алгоритмы реализованы в виде пакета программ, составляющих подсистему синтеза полутоновых изображений. Созданное программное обеспечение функционирует на ЭВМ EC-I060 и способно для сцен средней сложности формировать за одну секунду несколько последовательных кадров, соответствующих различным положениям наблюдателя. Большая часть программных модулей адаптирована на ЭВМ СМ-4. Использование разработанных программно-алгоритмических средств для решения раз личных задач подтверждает юс практическую ценность и эффективность.
На защиту выносятся:
- структурная схема организации вычислений при решении геометрических задач синтеза полутоновых изображений;
- алгоритмы геометрических операций, выполняемых над выпуклыми многоугольниками в процессе синтеза полутоновых изображений;
- алгоритм рекурсивного линейного подразделения моделируемой сцены и формирования приоритетного списка;
- алгоритм построения падающих теней;
- методика построения подсистемы синтеза полутоновых изображений для решения практических задач.
Содержание диссертации излагается в четырех главах.
В первой главе приведен анализ способов представления объектов и основных геометрических задач машинного синтеза полутоновых изображений. Рассмотрены методы их решения. Предложена структурная схема организации вычислений в высокопроизводительной подсистеме синтеза полутоновых изображений.
Во второй главе описаны геометрические алгоритмы для выполнения операций над выпуклыми многоугольниками, составляющие основу функционирования подсистемы синтеза полутоновых изображений.
Третья глава посвящена алгоритмизации методов построения наглядных изображений - удалению невидимых поверхностей и построению падающих теней.
В четвертой главе рассмотрена программная реализация разработанных алгоритмов, приведены некоторые характеристики производительности подсистемы синтеза полутоновых изображений.
