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

ВВЕДЕНИЕ.

ГЛАВА I. ГЕОМЕТРИЧЕСКИЕ ЗАДАЧИ МАШИННОГО СИНТЕЗА ПОЛУТОНОВЫХ ИЗОБРАЖЕНИЙ И ОРГАНИЗАЦИЯ ИХ РЕШЕНИЯ

1.1. Формальное описание процесса синтеза полутоновых изображений.

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

1.3. Декомпозиция граней и объектов на выпуклые части.

1.4. Иерархическое описание моделируемой сцены.

1*5. Цреобразование координат и отсечение.

1.6. Удаление невидимых поверхностей

1.7. Тонирование изображений

1.8. Организация вычислительного процесса синтеза полутоновых изображений.

Е&воды по первой главе

ШВА 2. АЛГОРИТМИЗАЦИЯ ОПЕРАЦИЙ НАД ВЫПУКЛЫМИ МНОГОУГОЛЬНИКАМИ

2.1. Операционная среда подсистемы синтеза полутоновых изображений

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

2.3. Ориентированная нумерация вершин многоугольника

2.4. Определение взаимного расположения ¡двух многоугольников .*.

2.5. Отсечение выпуклых многоугольников

2.6. Растровое преобразование выпуклых многоугольников

Выводы по второй главе

ПЛАВА 3. УДАЛЕНИЕ НЕВОДИМЫХ ПОВЕРХНОСТЕЙ И ПОСТРОЕНИЕ

ТЕНЕЙ

3.1. Использование связности при анализе видимости и затенения.

3.2. Линейное подразделение плоскости и пространства

3.3. Алгебрологический метод формирования приоритетного списка.

3.4. Цроведение разделяющих плоскостей.

3.5. Замкнутые приоритетные циклы и разрезание объектов

3.6. Формирование приоритетного списка.

За последние два десятилетия получила интенсивное развитие новая ветвь прикладной математики - машинная графика. Её применение в научно-исследовательской и проектно-конструкторской практике не только позволяет эффективно решать поставленные задачи, но и саму их постановку выводит на качественно новый уровень. Машинная графика является важной составной частью систем автоматизированного проектирования и автоматизации научных исследований, о которых в "Основных направлениях экономического и социального развития СССР на 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] разработаны вопросы объединения методов и алгоритмов в графические пакеты, обладающие развитым интерфейсом и способностью вести диалог с пользователем.

В результате целенаправленных усилий разработаны такие системы для моделирования и отображения графической информации, как ГРАФОР, ГРМСМ, МП-НЗ>, ИНТЭАР, АЛ ГРАФ, АТОМ, ГРАС и другие. Машинная графика успешно применяется при архитектурном проектировании, в различных отраслях машиностроения, в радиоэлектронике, в молекулярной химии, при обработке экспериментальных данных. Многообразие графических систем, появление похожих разработок в различных организациях стимулировали работы по их сталдартизации и унификации [17,40,73,118].

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

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

Потребность в полутоновой машинной графике ощущается во всех областях, где необходимо работать с наглядными изображениями реальных трехмерных сцен. Традиционными областями применения таких изображений давно стали архитектурное проектирование, создание новых образцов автомобильной и авиационной техники, эргономическом проектировании транспортных средств и операторско-диспетчер-ских пунктов. Новые задачи перед системами полутоновой графини поставило интенсивное развитие робототехники. Разработка систем машинного зрения, моделирование траекторий перемещения манипуляторов и другие проблемы значительно удобнее решать с помощью машинной графики. Не случайно первый алгоритм удаления невидимых линий и первое применение однородных координат в машинной графике были осуществлены Робертсом [67] при разработке роботов-манипуляторов. Наглядность полутоновых машинных изображений позволяет использовать их на тех стадиях проектирования, где необходимо производить отбор вариантов с учетом эстетических критериев оценки.

Графические системы, создающие полутоновые изображения, оперируют обычно с трехмерными объектами, составляющими некоторую сцену. Для большинства приложений характерна статичность сцен и моделирование перемещения условного наблюдателя, осматривающего их. Гилой отмечает [18], что "получение изображений /относительно хорошо отображающих реальность/ трехмерных тел является самостоятельной целью; как правило, не делается попыток производить манипуляции с такими объектами в интерактивном режиме". Именно в такой постановке и будут рассматриваться задачи синтеза изображений в данной работе.

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

В результате многочисленных исследований в области зрительного восприятия [22,23,33,38] установлено, что зрительный анализатор человека нельзя рассматривать обособленно как некоторый, хотя и сложный, оптический прибор. 3|рительное восцриятие осуществляется системой глаз-мозг. Мозг производит корректировку восцринимаемых от глаза изображений, опираясь на накопленный опыт, который выражается в црисутствующих в памяти ассоциативных связях. Входной информацией системы являются геометрические искажения, изменения яркости и цвета, перемещения объектов. Эта корректировка позволяет обычно правильно восцринимать формы рассматриваемых объектов и их удаленность от наблюдателя. Иногда в результате осмысления видимой картины у наблюдателя формируются неправильные выводы о реальной конфигурации сцены. В таких случаях говорят о зрительных иллюзиях. Иллюзии возникают при наличии совокупности признаков, допускающей двусмысленное толкование.

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

Одно из важнейших таких свойств - перспективное преобразование, уже несколько веков используемое художниками и архитекторами. "Перспектива является изображением наиболее близким к видимым формам предмета и, поэтому, наиболее наглядным. По перспективе можно правильно судить о внешнем облике, о пропорциях и соотношении объемов и отдельных элементов, об ожидаемом зрительном -восприятии проектируемого здания" [70]. Перспективное преобразование вводится в изображение путем простой формализации и представления в аналитическом виде процедуры центрального проецирования. Аппарат центрального проецирования при построении машинных изображений обычно задается положением точки зрения и направлением главного луча; картинная плоскость предполагается перпендикулярной главному лучу и находящейся от точки зрения на определенном расстоянии. Формальный характер построения перспективных изображений с помощью ЭВМ позволяет получить объективную картину, избегая ситуаций, о которых пишет Н.Л.рус-скевич [70]: "Некоторые авторы при построении перспектив отступают от геометрических методов построения и, пытаясь достичь желаемого результата, вносят случайные поправки. В итоге получается перспектива не запроектированного в действительности объекта, а такого, каким его хотелось бы видеть архитектору".

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

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

Перспективой, тенями и удалением невидимых поверхностей не исчерпывается список возможных способов повышения наглядности машинных изображений; можно также воспользоваться средствами архитектурной композиции, управляющими зрительным восприятием: объемно-пространственной структурой, членением изображения, указателями масштаба [49]. Однако за исключением архитектурных приложений использование этих средств затруднительно, т.к. требует внесения' в сцену дополнительных элементов.

Получение наглядных изображений не является единственной проблемой при создании систем синтеза полутоновых изображений. Другая важная проблема состоит в быстродействии этих систем. Быстродействие - это серьезный фактор, обуславливающий эффективность и сферу применения графической системы. При необходимости интерактивной работы проектировщика с графической системой время синтеза одного кадра изображения должно исчисляться секундами. Еще более высокие требования предъявляются к быстродействию, если скорость смены кадров должна обеспечить иллюзию непрерывного перемещения наблюдателя. Это так называемый синтез изображений в реальном времени. Как известно [52], чтобы изображение воспринималось без мельканий, частота его регенерации должна составлять 25-30 Гц; для создания впечатления непрерывности перемещения последовательные кадры должны появляться через 0,11-0,13 сек. Системы синтеза изображений в реальном времени стали использоваться в последние годы в имитаторах визуальной обстановки авиационных тренажеров [5]. Большая часть вычислений в них выполняется специальными аппаратурными блоками. Предсказывая, что современные синтезирующие системы визуализации будут удовлетворять потребностям практики вплоть до рубежа 2000 года, специалисты, тем не менее, отмечают необходимость разработки новых более эффективных графических алгоритмов [124]. Это объясняется чрезвычайно высокой стоимостью аппаратурной реализации систем синтеза изображений в реальном времени. Снижение стоимости может быть достигнуто созданием высокоэффективных алгоритмов и минимизацией специального оборудования.

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

Понятие связности /когеренции/ было введено в машинную графику Сазерлендом и др. [126] и быстро распространилось среди специалистов. Оно характеризует существование локально постоянных свойств сцены или изображения, позволяющих прогнозировать с высокой степенью вероятности наличие определенных закономерностей в анализируемой ситуации. Различают пространственную, объектную, реберную, кадровую, растровую и другие виды связности. Например, растровая связность заключается в большом сходстве последовательных строк растра. Использование свойств связности состоит обычно в принятии некоторых решений, которые затем лишь незначительно уточняются и корректируются на основании анализа конкретной ситуации. Однако очень часто свойства связности учитываются только в каких-то локальных процедурах, например, для ускорения сортировки. Анализ существующих алгоритмов показал, что далеко не всегда авторы используют все свойства геометрии моделируемой сцены. Между тем, данные, обрабатываемые алгоритмами машинной графики, являются не абстрактными числами, а геометрическими параметрами, характеризующими форму объектов, топологию соединения их частей, компоновку сцены. Поэтому представляется целесообразным расширить понятие связности, распространив его также на глобальные геометрические свойства объектов. Такое расширение понятия связности не противоречит его исходному определению. Многие геометрические свойства при машинном решении задач не позволяют сразу получить требуемый результат, а только прогнозируют его, сокращают объем переборов, направляют решение по оптимальному пути. Сочетание локальных и глобальных характеристик является той основой, на которой возможно построение эффективных машинных методов решения геометрических задач.

Разработка машинных алгоритмов решения геометрических задач ведется по двум направлениям. Первое состоит в формализации операций, выполняемых при графических построениях [82]. Однако этот путь далеко не всегда может привести к требуемым результатам, ибо многие графические методы опираются на визуальное восприятие информации и трудноформализуемые эвристики. Построение машинных аналогов графических операций приводит к многочисленным переборам и проверкам, требующим больших затрат времени. Второе направление заключается в создании специальных методов, ориентированных на машинную обработку геометрической информации. В работах [1,21,47] рассмотрены особенности этих методов и требования, предъявляемые к ним.

Следует отметить, что алгоритмы синтеза полутоновых изображений нельзя рассматривать как простое расширение уже известных алгоритмов для векторной графики, фи синтезе полутоновых изображений трехмерных объектов приходится работать не с отдельными отрезками и дугами кривых, а с охватываемыми ими отсеками поверхностей и объемами. Необходима разработка новых, специально приспособленных для полутоновой машинной графики алгоритмов. В настоящее время этот вопрос исследован относительно мало [12,50]. В какой-то мере это объясняется отсутствием отечественных серийно выпускаемых дисплейных терминалов растрового типа. Хотя такие терминалы разработаны и используются в отдельных организациях [27,28,75,77], широкого распространения они еще не получили. С другой стороны, включение в состав вычислительных комплексов растровых терминалов тормозится отсутствием программно-алгоритмического обеспечения для этих устройств. Настоящая работа является попыткой создания такого программно-алгоритмического обеспечения.

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

- исследование основных геометрических задач, возникающих при машинном синтезе полутоновых изображений;

- разработка эффективной организации вычислительного цроцесса машинного синтеза полутоновых изображений;

- разработка базового набора алгоритмов для выполнения операций над выбранными геометрическими примитивами;

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

- разработка алгоритма построения теней;

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

- внедрение результатов исследований.

Научную новизну работы составляют:

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

- базовые геометрические алгоритмы для выполнения операций над выпуклыми многоугольниками;

- алгоритмы линейного подразделения моделируемой сцены, формирования и интерпретации приоритетного списка для удаления невидимых поверхностей;

- методика построения падающих теней по теневым многоугольникам объектов;

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

Практическая ценность. Разработанные алгоритмы реализованы в виде пакета программ, составляющих подсистему синтеза полутоновых изображений. Созданное программное обеспечение функционирует на ЭШ ЕС-1060 и способно для сцен средней сложности формировать за одну секунду несколько последовательных кадров, соответствующих различным положениям наблюдателя. Большая часть программных модулей адаптирована на ЭШ СМ-4. Использование разработанных программно-алгоритмических средств для решения различных задач подтверждает их практическую ценность и эффективность.

На защиту выносятся:

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

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

- алгоритм рекурсивного линейного подразделения моделируемой сцены и формирования приоритетного списка;

- алгоритм построения падающих теней;

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

Содержание диссертации излагается в четырех главах.

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

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

Третья глава посвящена алгоритмизации методов построения наглядных изображений - удалению невидимых поверхностей и построению падающих теней.

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

Выводы по четвертой главе.

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

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

3. Проведены измерения производительности разработанной подсистемы. Результаты измерений показывают линейный рост затрат времени на синтез цри увеличении сложности сцены. Подсистема способна синтезировать на ЭВМ типа ЕС-1060 несколько последовательных кадров изображения в секунду для сцен средней сложности.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

1. Автоматизированное проектирование. Изометрические и графические задачи/В.С.Полозов, О.А.Будеков, С.И.Ротков и др. -М.: Машиностроение, 1983.-280 с.

2. Альперович Л.З. К вопросу программного обеспечения процедуры удаления невидимых линий в задаче вывода центральной проекции объекта на графический терминал. -Программирование, 1977, №3, с.39-42.

3. Артемьева Г.П. Об исследовании перспективных искажений. -В кн.: Лэометрия и восприятие изображений/Труды МДЦИ, 1973, вып.64, с.33-38.

4. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. -М.: Мир, 1979.-536 с-.

5. Бабенко B.C. Имитаторы визуальной обстановки тренажеров летательных аппаратов. -М.: Машиностроение, 1978.-143 с.

6. Бадаев Ю.И» Аппроксимация выпуклых поверхностей отсеками: плоскостей. -В кн.: Прикл. геометрия и инж. графика. -Пиев: Буд1вельник, 1975, вып.19, с.133-135.

7. Бадаев Ю.И. Вопросы подготовки и анализа оптимальности геометрической информации элементов поверхностей для целей воспроизведения в системах с программным управлением: Автореферат дисс. . канд. техн. наук. -Киев, 1977.-16 с.

8. Банковский Ю.М. Анализ методов разработки графического обеспечения ЭВМ: Автореферат дисс. . канд. физ.-мат. наук. -М., 1974.-17 с.

9. Баяковский Ю.М., Галактионов В.А. Об одном алгоритме удаления невидимых линий. -В кн.: Применение систем автоматизированного проектирования в приборостроении и машиностроении: Меж-вуз. сб. научн. тр. -Челябинск, 1980, №256, с.107-112.

10. Банковский Ю.М., Галактионов В.А., Михайлова Т.Н. ГОАЗЮЕ: комплекс графических программ на ФОРТРАНЕ. 4.1. -М.: ИПМ АН СССР, 1983.-182 с.

11. Боднар И.Ф. Алгоритм автоматизированного построения теней. -В кн.: ЭВМ в исследованиях и проектировании объектов гражданского строительства: Сб. научн. тр. КиевЗНИИЭП. -Киев, 1975, вып.У, с.3-8.

12. Боднар И.Ф. Реализация тоновых изображений на графических терминалах. -В кн.: ЭВМ в исследованиях и проектировании объектов гражданского строительства: Сб. научн. тр. КиевЗНИИЭП. -Киев, 1977, с.11-17.

13. Вальков К.И. Лекции по основам геометрического моделирования. -Л.: Изд. Ленингр. ун-та, 1975.-180 с.

14. Васильев В.П. Методы автоматизации геометрического моделирования в САПР на основе параметрических В-сплайнов: Автореферат дисс. . канд. техн. наук. -Минск, 1982.-16 с.

15. Верлер К.Х. Обработка графической информации с помощью вычислительной техники. -М.: Машиностроение, 1979.-254 с.

16. Гаврилов В.А. Видимость в атмосфере. -Л.: Гкдрометеоиздат, 1966.-324 с.

17. Галактионов В.А. Исследование и разработка геометрических алгоритмов и методов машинной графики: Автореферат дис. . канд. физ.-мат. наук. -М., 1982.-16с.

18. Вшой В. Интерактивная машинная графика. -М.: М1ф, 1981.-384 с.19.- Елушков В.М. Диалог с вычислительной машиной: современныевозможности*и перспективы. -УСиМ, 1974, PI, с.3-7.

19. Гиупшов В.М., Тимофеев Б.Б. Некоторые проблемы автоматизации проектирования. -Механизация и автоматизация управления, 1975, №4, с.3-6.

20. Горелик А.Г. Автоматизация инженерно-графических работ с помощью ЭВМ. -Минск: Вышэйшая школа, 1980.-206 с.

21. Грегори Р.Л. Глаз и мозг. Психология зрительного восприятия. -М.: Црогресс, 1970.-271 с.

22. Грегори Р.Л. Разумный глаз. -М.: Мир, 1972.-209 с.

23. Г£>ин В.М. Программное обеспечение для работы с трехмерными объектами на графических терминалах: Автореферат дис. . канд. техн.- наук. -М., 1974.-19 с.

24. Г£>ин В.М., Львов В. А. Машинное построение проекций трехмерных объектов с удалением невидимых линий. -В кн.: Вычислительные системы. -Новосибирск, 1972, вып.50, с.64-85.

25. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. -М.: Мир, 1975.-544 с.

26. Гуглин И.Н. Телевизионные устройства отображения информации. -М.: Радио и связь, I98I.-200 с.

27. Гуглин И.Н. Электронный синтез телевизионных изображений. -М.: Советское радио, 1979.-255 с.

28. Дворжец В.И. Исследование и разработка модульных систем математического обеспечения машинной графики: Автореферат дисс. . канд. физ-мат. наук. -Новосибирск, 1979.-16 с.

29. Дмитриев Л.Г., Касилов A.B., Втльман Г.Б., Ковбасюк В.П. Автоматизированное проектирование конструкций гражданских зданий. -Киев: Буд1вельник, 1977.-236 с.

30. Евдокимов В.Ф., Тимошенко Н.П., Владимирский А.Н., Крыжный

31. Б.К. Об организации вычислительного процесса в высокопроизводительной системе электронного синтеза изображений. -Электронное моделирование, 1983, №4, с.32-36.

32. Заболотный П.А., Тодорой Д.Н. Геометрические задачи машинной графики. -В кн.: Современные вопросы прикладной математики и программирования. Математические науки: Межвузовский сб. -Кишинев: Штиинца, 1979, с.44-50.

33. Завалишин Н.В», Мучник И.Б. Модели зрительного восприятия и алгоритмы анализа изображений. -М. : Наука, 1974.-344 с.

34. Зингер Б.Х., Талныкин Э.А. Предварительная пространственная сорт1фовка основа алгоритма удаления невидимых поверхностей для систем отображения приоритетного типа. -Автометрия, 1983, №6, с.83-87.

35. Зметный А.Я. Линейная перспектива на наклонной плоскости. -Л.: Стройиздат, 1968.-202 с.

36. Зозулевич Д.М. Машинная графика в автоматизированном проектировании. -М.: Машиностроение, 1976.-240 с.

37. Канадэ Т. Геометрические аспекты интерпретации изображений трехмерной сцены. -ТЙИЭР, 1983, т.71, №7, с.6-22.

38. Клике Ф. Проблемы психофизики восприятия пространства. -М.: Прогресс, 1965.-464 с.

39. Клименко C.B., Кочин В.Н. Об одном способе изображения поверхностей в машинной графике. -Программирование,î 1981, №2, с.56-62.

40. Климов В.Е., Клишин В.В. Аксиоматизация задачи синтеза геометрии трехмерных объектов. -Изв. АН СССР, сер. Техническая кибернетика, 1983, №4, с.57-62.

41. Кнут Д. Искусство программирования для ЭВМ. Т.З. Сортировкаи поиск. -М.: Мир, 1978.-844 с.

42. Кованцов M.I. Проективна геометр1я. -Ки1в: Вшца школа, 1969.-411 с.

43. Кольцов Ю.В., Манако В.В., Никитин А.И. Графический пакет ГРАС. Буферизованный вывод. -УСиМ, 1983, №3, с.96-101.

44. Короев Ю.И., Федоров М.В. Архитектура и особенности зрительного восприятия. -М.: ГИЛСЙА, 1954.-136 с.

45. Котов И.И. Линейная аксонометрия. -В кн.: Прикл. геометрия и инж. графика. -Киев: Буд1вельник, 1974, вып.18, с.3-8.

46. Котов И.И., Магауенов Р.Г. Алгоритмы параллельных и центральных проекций. -В кн.: Кибернетика графики и прикл. геометрия поверхностей, ч.ХП/Труды МАИ, 1975,вып.331, с. 12-17.

47. Котов Й.И., Полозов B.C., Широкова Л.В. Алгоритмы машинной графики. -М.: Машиностроение, 1977.-231 с.

48. Котов Ю.В., Симонин С.И. Автоматизация построения наглядных изображений с применением ЭВМ. -М.: Изд-во МДЦИ, ч.1 1976, 72 е.; ч.2 - 1978, 60 с.

49. Вудин П.А., Ломов Б.Ф. Использование художественных средств архитектурной композиции для управления зрительным восприятием. -В кн.: Проблемы инженерной психологии. -Л., 1966, вып.4, с.93-108.

50. Кужутов A.B., Леус В.А., Полещук Н.С. Численный синтез тонового изображения освещенной поверхности и растровая визуализация. -Автометрия, 1978, №5, с.59-64.

51. Курилов М.А. Построение изображений трехмерных объектов с удалением невидимых линий в графическом пакете ГРАС. -В кн.: Прикладное программирование: Сб. научн. тр./ИК АН УССР. -Киев, 1982, с.73-79.

52. Луизов А.В. Глаз и свет. -Л.: Энергоатомиздат, 1983.-144 с.

53. Люстерник Л.А. Выпуклые фигуры и многогранники. -М.: ГЪс-техиздат, 1956.-212 с.

54. Маллер Д., Црепарата Ф. Нахождение пересечения двух выпуклых многогранников. -В кн.: Кибернетический сборник. Новая серия. Вып.20. -М.: Мир, 1983, с.5-29.

55. Манако В.В. Стандартный графический пакет ГРАС. Цроектиро-вание. Базис вывода. -УСиМ, 1981, №3, с.48-54.

56. Михайленко В.Е. О приближенном паркетировании оболочек различной гауссовой кривизны. -В кн.: Прикл. геометрия и инж. графика. -Киев: Буд1вельник, 1973, вып.16, с.14-19.

57. Михайленко В.Е., Г.рабко С.М. Аппроксимация регулярных поверхностей различной гауссовой кривизны многогранниками. -В кн.: Прикл. геометрия и инж. графика. -Киев: Буд1вель-ник, 1970, вып.II.

58. Михайленко В.Е., Ковалев С.Н. Конструирование форм современных архитектурных сооружений. -Киев: Буд1вельник, 1978. -112 с.

59. Михайленко В.Е., Обухова B.C., Подгорный А.Л. Формообразование оболочек в архитектуре. -Киев: Буд1вельник, 1972. -205 с.

60. Надолинный В.А., Павлов А.В. Способ конструирования поверхностей сложных технических форм. -В кн.: Прикл. геометрия и, инж. графика. -Киев: Буд1вельник, 1975, вып.20, с.11-13.

61. Ньюмен У., Спрулл Р. Основы интерактивной машинной графики. -М.: Мир, I98I.-384 с.

62. Орзиев М. Вопросы сплайн-аппроксимации в подсистемах геометрического моделирования САПР: Автореферат дисс. . канд.техн. наук. -Киев, I98I.-I6 с.

63. Осипов В.А. Машинное проектирование и воспроизведение поверхностей. -В кн.: Машинное проектирование, увязка и воспроизведение сложных деталей в авиастроении. -Иркутск, 1976, с.5-10.

64. Панченко A.A. Алгоритм удаления невидимых линий для линейчатых поверхностей. -В кн.: Прикл. геометрия и инж. графика. -Киев: Буд1вельник, 1983, вып.36, с.88-91.

65. Похвалинский А.Б. Способ описания и обработки трехмерных графических объектов. -В кн.: Машинная графика в системах автоматизированного проектирования. -Киев: ИК АН УССР, 1982, с.28-34. -/АН УССР, Ш-т кибернетики; Препринт 82-33/.

66. Принс М.Д. Машинная графика и автоматизация проектирования. -М.: Советское радио, 1975.-232 с.

67. Роберте Л. Автоматическое восприятие трехмерных объектов. -В кн.: Интегральные роботы/Под ред. Г.Е.Поздняка. -М.: Мир, 1973, с.162-208.

68. Роджерс Д., Адаме Дж. Математические основы машинной графики. -М.: Машиностроение, 1980.-204 с.

69. Ротков С.И. Разработка средств машинной графики для автоматизированного конструирования геометрических объектов: Автореферат дисс. . канд. техн. наук. -Свердловск, 1981. -18 с.

70. Русскевич H.JI. Перспектива на наклонной плоскости. -Киев: Буд1вельник, 1968.-68 с.

71. Рыжов H.H. Алгоритмизация вывода уравнений линейчатых поверхностей с учетом наперед заданных условий. -В кн.: Прикл. геометрия и инж. графика. -Киев: Буд1вельник, вып.14, с.3-8.

72. Сазонов К.А. Автоматизация проектирования трехмерных объектов на перспективных изображениях: Автореферат дисс. . канд. техн. наук. -Киев, 1979.-18 с.

73. Семенков О.И., Винокуров Д.И. Некоторые проблемы унификации в машинной графике. -УСиМ, 1984, №1, с.50-55.

74. Семенов В.И. Автоматизация построения наглядных изображений в архитектурном проектировании: Автореферат дисс. . канд. техн. наук. -М., 1970.-16 с.

75. Современные методы и устройства отображения информации/ Под ред. М.И.Кривошеева и А.Я.Брейтбарта. -М.: Радио и связь, 1981.-216 с.

76. Стоян Ю.Г., Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объектов. -Киев: Наукова думка, 1976. -248 с.

77. Телевизионные методы и устройства отображения информации/ Под ред.М.И.Кривошеева. -М.: Советское радио, 1975.-239 с.

78. Трамбле Ж., Соренсон П. Введение в структуры данных. -М.: Машиностроение, 1982.-784 с.

79. Файн В.С. Алгоритмическое моделирование формообразования. -М.: Наука, 1975.-141 с.

80. Федоров М.В. Рисунок и перспектива. -М.: Искусство, 1960. -130 с.

81. Фокс А., Цратт М. Вычислительная геометрия. Приложение в проектировании и на производстве. -М.: Мир, 1982.-304 с.

82. Фролов С.А. Кибернетика и инженерная графика. -М.: Машиностроение, 1974.-224 с.

83. Ходорковский А.Н. Вопросы подготовки математической модели окружающей обстановки. -В кн.: Прикл. геометрия и инж. . графика. -Киев: Буд1вельник, 1983, вып.35, с.67-69.

84. Ходорковский А.Н. Информационная модель окружающей обстановки. -В кн.: Прикл. геометрия и инж. графика. -Киев: Буд1вельник, вып.34, 1982, с.112-114.

85. Ходорковский А.Н. Некоторые алгоритмические вопросы полутоновой машинной графики. -В кн.: Машинная графика и обработка документации в управлении, планировании и проектировании: Тез. докл. Первой Всесоюзной школы-семинара. -Цахкадзор, 1983, с.110-114.

86. Ходорковский А.Н. Приоритетные вычисления для алгоритма удаления скрытых поверхностей. -В кн.: Прикл. геометрия и инж. графика. -Киев:. БудГвельник, 1983, вып.36, с.84-86.

87. Четверухин Н.Ф. Проективная геометрия. -М.: Учпедгиз, 1969.-304 с.

88. Чукин Ю.В. Структура данных для представления изображений. -Зарубежная радиоэлектроника, 1983, №8, с.85-107.

89. Чумакова Л.А. Задача построения падающих теней от трехмерных объектов. -Изв. АН СССР, сер.Техническая кибернетика, 1976, №2, с.208-214.

90. Чумакова Л.А. Метод сокращения перебора при решении некоторых задач автоматизации обработки графической информации. -Изв. АН СССР, сер. Техническая кибернетика, 1975, №2, с.62-73.

91. Чумакова Л.А., Семенов В.Н. Применение линейного программирования к решению некоторых задач архитектурно-строительного проектирования. -Изв. АН СССР, сер. Техническая кибернетика, 1977, №1, с.13-23.

92. Atherton Р., Weiler К., Greenberg D. Polygon shadow generation. -Computer Graphics, 1978, v.12, N3, p.275-281.

93. Bezier P.F. Example of an existing system in the motor industry: the UNISURF system. -Proceedings of Royal Society of London, 1971, v.A.321, N1545, p.207-218.

94. Blinn J.3?., Newell M.E. Clipping using homogeneous coordinates. -Computer Graphics, 1978, v.12, N3, p.245-251.

95. Clark J.H. Hierarchical geometric models for visible surface algoritms. -Communications of the ACM, 1976, v.19,N10, P.547-554.

96. Cohen E., Lyche Т., Riesenfeld R. Discrete B-splines and subdivision techniques in computer aided geometric designand computer graphics. Computer Graphics and Image Processing, 1980, v.14, N2, p.87-111.

97. Crow F.C. An approach to real-time scan conversion. -Proc. AFIPS 1979 National Conputer Conference, 1979, v.48,p.157-165.

98. Crow F.C. Toward more complicated computer imagery. -Computers and Graphics, 1980, v. 5, N2-4, p.61-69.

99. Dewdney A.K. A grey-level character set for the production of a pictures at a printing terminal. -Computer Graphics, 1976, v.10, NJ, p.14-25.

100. Peng D.Y., Riesenfeld R.F. Some new surface forms for com-* puter aided geometric design. -Computer Journal, 1980,v.23, N4, p.324-331.

101. Feng H., Pavlidis T. Decomposition of polygons into simpler components: feature generation for syntactic pattern recognition. -IEEE Transactions on Computers, 1975, v.C-14, N6, p.636-650.

102. Fuchs H., Abram G.D., Grant E.D. Near real-time shaded display of rigid objects. -Computer Graphics, 1983» v.17, N3, p.65-72.

103. Fuchs H., Kedem Z.M. Predetermining visibility priority in 3-D scenes. -Computer Graphics, 1979, v.13, N2, p.175-181.

104. Gouraud H. Continuous shading of curved surfaces. -IEEE Transactions on Computers, 1971, v.C-20, N6, p.623-629.

105. Green P.J., Silverman B.W. Constructing the convex hull ofa set of points in the plane. -Computer Journal, 1979» v.22, N3, p.262-266.

106. Grossman D.D. Procedural representation of three-dimensional objects. -IBM Journal of Research and Development, 1976, v.20. N6, p.582-589.

107. Lane J.M., Carpenter L.O., Whitted T., Blinn J. Scan line methods for displaying parametrically defined surfaces. -Communications of the ACM, 1980, v.23, N1, p.23-34.

108. Lerner E.J. The computer graphics revolution. -IEEE Spectrum, 1981, v.18, N12, p.35-40.

109. MacLeod I.D.G. Pictorial output with a line printer. -IEEE Transactions on Computers, 1970, v.C-19, N2, p.160-162.

110. Mahl R. Visible surface algorithms for quadric patches. -IEEE Transactions on Computers, 1972, v.C-21, N1, p.1-4.

111. Max N.L. ATOMLL: atoms with shading and highlights. -Computer Graphics, 1979» v.13» N2, p.165-173*

112. Meagher D.J. Efficient synthetic image generation of arbitrary 3-D objects. -PRIPf82: Pattern Recogn. and Image Process. Proc. Conf., Las Vegas, Nev., 14-17 June 1982. Silver Spring, Md., 1982, p.473-478.

113. Newman W.M., van Dam A. Recent efforts towards graphics standartization. -Computing Surveys, 1978, v.10, N4,p.365-380.

114. Phong B.T. Illumination for computer generated pictures. -Communications of the ACM, 1975, v.18, N6, p.311-317.

115. Preparata F.P., Hong S.J. Convex hulls of finite sets of points in two and three dimensions. -Communications of the ACM, 1977, v.20, N2, p.87-93.

116. Reeves W.T. Particle systems a technique for modelinga class of fuzzy objects. -Computer Graphics, 1983, v.17, N3, P.359-376.

117. Requicha A.A.G. Representations for rigid solids: theory, methods, and systems. -Computing Surveys, 1980, v.12, N4, p.'437-464.

118. Schachter B. Decompisition of polygons into convex sets. -IEEE Transactions on Computers, 1978, v.C-27, N11,p.1078-1082.

119. Sutherland I.E., Sproull R.i*., Schumacker R.A. A characterization of ten hidden-surface algorithms. -Computing Surveys, 1974, v.6, N1, p.1-55.

120. Tomlinson D.J. An aid to hidden surface removal in real time CGI systems. -Computer Journal, 1982, v.25, N4,p.429-441.

121. Whitted T. An improved illumination model for shaded display. -Communications of the ACM, 1980, v.23, N6, p.343-349.

122. Williams R. A survey of data structures for computer graphics systems. —Computing Surveys, 1971» v. 3, N1, p.1-21.

123. Willis P.J. Proximity techniques for hidden-surface removal. -IEE Journal of Computers and Digital Techniques, 1978, v. 1, IM4, p.171-178.

124. Willis P.J. A real time hidden surface technique. -Computer Journal, 1977, v.20, N4, p.335-339.