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

НИЖЕГОРОДСКАЯ ГОСУДАРСТВЕННАЯ АРХИТЕКТУРНО-СТРОИТЕЛЬНАЯ АКАДЕМИЯ

На правах рукописи

МАРТЕМЬЯНОВ Борис Викторович

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

Специальность 05.01.01 - Прикладная геометрия, инженерная

и компьютерная графика

Автореферат диссертации на соискание ученой степени кандидата технических наук

Самара - 1996г.

Работа выполнена в Самарском государственном техническом университете (СамГТУ).

Научный руководитель: доктор технических наук, профессор Орлов С.П. Официальные оппоненты:

-доктор технических наук, профессор Кетков Ю.Л. (Н.Новгород); - кандидат технических наук Митин С.В. (Н.Новгород).

Ведущая организация: Институт систем обработки изображений Российской АН (ИСОИ РАН) г.Самара.

Защита состоится 10 сентября 1996г.

в 15 час. 00 мин. на заседании диссертационного совета К064.09.02 в Нижегородской государственной Архитектурно-строительной Академии (НГАСА) по адресу : 603600, Н.Новгород, ул. Ильинская, 65, ауд 5-202.

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

Отзывы представлять в двух экземплярах с подписью, заверенной печатью. Справки по телефону: (8312) 34-10-34 кафедра "Начертательная геометрия

Автореферат разослан

июня 1996г.

и САПР" НГАСА.

Ученый секретарь диссертационного совета к.т.н., доцент

М.ЛЛапшин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

ЦЕЛЬ РАБОТЫ заключается в исследовании и разработке методов и алгоритмов растровой машинной графики, обеспечивающих формирование изображений сложных пространственных объектов с падающими тенями, отбрасываемыми объектами моделируемого мира.

Указанная цель достигается в результате :

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

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

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

- разработки методов уменьшения трудоемкости алгоритмов визуализации .

МЕТОДЫ ИССЛЕДОВАНИЯ. Методы исследования базируются на аппарате теории множеств, аналитической алгебры, общей алгебры, аналитической и проективной геометрии, матричном исчислении, методах машинной графики.

НАУЧНАЯ НОВИЗНА.

1. Обоснован принцип построения процедур визуализации геометрических образов трехмерных объектов, заданных алгебро-логической моделью, в системах растровой полутоновой графики, основанный на декомпозиции исходных объектов на объекты, описываемые с помощью теоретико-множественных функций ( ТМФ ) специального вида.

2. Разработан метод обработки алгебро-логической модели пространственного объекта с целыо его визуализации. Метод предполагает использование в модели ТМФ специального вида и основывается на применении введенных соискателем координатно зависимых теоретико-множественных операций (ТМО): модифицированного теоретико-множественного вычитания и двух модификаций теоретико-множественного пересечения.

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

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ РАБОТЫ. Практическую ценность представляет подсистема визуализации геометрических образов пространственных сцен, разработанная на основе научных результатов, полученных соискателем, и объединенная в единую систему с языком геометрического конструирования объектов сложной структуры. Система написана на языке Pascal для PC-AT/*86-(S)VGA.

Практические и теоретические результаты, излагаемые в диссертационной работе, использовались при выполнении хоздоговорных работ, выполнявшихся по постановлениям СМ СССР (1983-1989г.г.), по приказам отраслевого министерства (1990-1993г.г.) для Центрального специализированного конструкторского бюро (ЦСКБ) г. Самара, в НИР по программе ИР-86 "Информатизация России" с РОС НИИ ИТ и АП (1991 г.), в НИР в рамках региональной программы "Конверсия" (1992 г.)., в НИР "Разработка программно-математического обеспечения компьютерной системы моделирования регистрации изображений оптико-электронной аппаратурой на реальном фоне" для ЦСКБ (1994 г.), в НИР "Разработка компьютерной системы моделирования регистрации изображений оптико-электронной аппаратурой типовых объектов наблюдения на реальном фоне (версия 2.0)" для Ленинградского аэрокосмического центра экологии "ЭКОС-конверсия" (1995г.), в НИР "Разработка методического, алгоритмического, функционального программного и программно-аппаратного обеспечения системы поддержки оперативного принятия решений по

управлению на НКУ на основе анализа телеметрической информации системы управления движением изделия ,., " для Иркутского вычислительного центра СО РАН (1995, 1996г.г.).

В рамках последних из перечисленных НИР осуществлялось моделирование различных аспектов работы различных систем технического зрения.

Разработанная система геометрического конструирования и визуализации, внедренная в ЦСКБ (г. Самара), использовалась при выполнении ЦСКБ фундаментальной НИР "ЖУК" в части проведения работ по разработке диалоговой системы моделирования динамики функционирования сложных технических систем и НИР "Моноплан - 9 - Листва" (часть 2). В рамках этих НИР осуществлялась имитация наблюдения объектов сложной формы с учетом эффектов затенения (с отображением падающих теней), а так же была создана библиотека моделей геометрических объектов сложной формы специального класса.

НА ЗАЩИТУ ВЫНОСИТСЯ:

1. Обоснование принципа построения процедур визуализации геометрических образов трехмерных объектов, заданных алгебро-логичес-кими моделями, основанного на использовании в моделях на этапе визуализации ТМФ специального вида и настройке алгоритмов на обработку таких моделей без их преобразования к полигональному виду.

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

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

4. Метод уменьшения вычислительной сложности процесса обработки алгебро-логической модели, содержащей ТМФ специального вида, основанный на уменьшении площади картинной плоскости проекций, для пэлов которой достаточно выполнять вычисления, а также на применении введенных автором координатно зависимых модификаций ТМО вычитания и пересечения.

АПРОБАЦИЯ РАБОТЫ. Основные результаты докладывались и обсуждались на:

-International Symposium on Vizual Analysis and Interface, (Novosibirsk, USSR, August 1-4 1991 ); Всесоюзной научно-методической конференции "Научно-методические основы использования ЭВМ, САПР в учебном процессе", Ленинградский кораблестроительный институт, (Ленинград, 1985 г.); 2-й Всесоюзной конференции "Методы и средства обработки графической информации", Горьковский государственный университет, (Горький, 1985 г.); научно-техническом семинаре сектора графических систем Вычислительного центра НИИ механики Горьковского государственного университета, (Горький, ноябрь 1986 г.); 4-й Всесоюзной конференция по проблемам машинной графики, Институт физики высоких энергий, (Протвино, 1987 г.); научно-технической конференции "Вопросы геометрического моделирования в САПР", Уральский политехнический институт, (Свердловск, 1987 г.); 3-й Всесоюзной конференции "Методы и средства обработки графической информации", Горьковский государственный университет, ( Горький, сентябрь 1988 г.); научно-технических конференциях факультета математических знаний Куйбышевского политехнического института, (Куйбышев, 1982, 1984, 1987 г.г.); общемосковском семинаре по математическому обеспечению систем машинной графики, Институт проблем управления АН СССР, (Москва, 1984г.).

ПУБЛИКАЦИИ. По материалам диссертации опубликовано 18 печатных работ, в том числе 1 авторское свидетельство. Работы, в которых описываются методы формирования растровых изображений, основываются на методах, разработанных соискателем и излагаемых в данной диссертации. Работы, в которых описывается программное обеспечение, основываются на программных и аппаратных средствах компьютерной графики, разработанных соискателем совместно с сотрудниками научно-исследовательской лаборатории кафедры "Вычислительная техника" Куйбышевского политехнического института (в настоящее время - Самарского государственного технического университета). Соискатель принимал непосредственное участие в проектировании и отладке лабораторного образца системы растровой компьютерной графики, на основе которого был разработан пакет программных средств, эксплуатировавшийся на компьютерах серии ЕС ЭВМ. В программных средствах и для ЕС ЭВМ и для IBM PC совместимых компьютеров соискателем полностью разработана подсистема визуализации, предложены математические модели описания пространственных форм, которые определили особенности языка, ориентированного на их конструирование, и его компилятора.

СТРУКТУРА И ОБЪЕМ РАБОТЫ. Работа состоит из введения, четырех разделов, заключения и приложения. Текст содержит 152 страницы, из них 19 рисунков, 9 страниц - список литературы из 89 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

В ПЕРВОМ РАЗДЕЛЕ анализируются используемые в машинной графике методы описания геометрии трехмерных объектов, содержание и методы выполнения основных этапов визуализации пространственных форм по их математическим моделям, формулируется цель дальнейших исследований в рамках задачи визуализации пространственных объектов средствами растровой полутоновой графики непосредственно по их алгебро-логической модели, анализируются подходы к получению изображений, отображающих падающие тени, формулируются основные вопросы, которые необходимо решить в процессе детальной разработки предложенного метода.

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

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

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

- все объекты непрозрачны;

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

- источник света вынесен за пределы пространства, занимаемого моделируемой сценой.

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

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

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

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

ВО ВТОРОМ РАЗДЕЛЕ сформулирована математическая постановка задачи обработки модели сцены с целью получения кадра растрового изображения; разработан метод решения этой задачи для случая использования алгебро-логической модели; сформулированы задачи этапов обработки алгебраической и логической компонент модели применительно к модели отдельного объекта (детали) сцены; обоснована целесообразность настройки процедур визуализации на обработку объектов, названных деталями и описываемых ТМФ фиксированного вида в терминах "тело-заготовка", "тела-отверстия"; разработан итерационный алгоритм обработки модели отдельной детали; введены координатно зависимые теоретико-множественные операции ( ТМО ) вычитания и пересечения, представляющие собой модификации ТМО, рассматриваемых в классической теории множеств; разработаны вопросы применения введенных операций при обработке модели детали. Задача обработки модели сцены с целью визуализации сцены сформулирована как задача, состоящая в задании функционального соответствия:

И : Е { I }, (1)

такого, что

1(Х,¥) = Р((Х,У) | (Х,¥) е Е ), где Е - множество точек плоскости проекций, соответствующее множеству пэлов кадра изображения ;

(Х,У) - координаты пэла в кадре ;

1(ХЛ0 - имя поверхности, видимой в точке (Х,У) плоскости проекций ;

{ I } - множество всех имен (номеров ) поверхностей сцены.

Проблема удаления скрытых поверхностей решается на основе метода 7-буфера, что позволяет свести обработку модели сцены к последовательной обработке моделей отдельных объектов.

Объект О отождествляется с занимаемой им областью пространства.

Алгебро-логическая модель ( АЛМ ) области О состоит из двух компонент: алгебраической и логической.

Алгебраическая компонента (АК) задает множество алгебраических функций 1Л, описывающих ориентированные поверхности Р1, каждая из которых ограничивает в трехмерном пространстве ЯЗ элементарную область 01:

01 = {(х,у,2) | 1Л(х,у,2) >= 0} АК = { 1Л }

Логическая компонента ( ЛК ) задает ТМФ Т, применение которой к элементарным областям СИ выделяет в трехмерном пространстве ЯЗ область О, занимаемую отдельным объектом сцены:

о =т({дп)

Для визуализации сцены достаточно исследовать область Яп пространства ЯЗ, задаваемую проецирующими прямыми(ПП), проецирующими в точки множества Еп :

Яп = {(х,у,г) | (х,у) е Еп}

В основу метода визуализации положено моделирование в пространстве Яп процесса образования области Б из элементарных областей СП в соответствии с ТМФ Т.

Пусть Яху - ПП из Яп, содержащая точку (х,у,0).

СЦху = СМ Р> Яху ; Бху = Э О Яху = Т({ С>1ху }), где СНху, Оху - отрезки, вырезаемые из Яху областями СН и Э соответственно.

Пусть <3'1ху и Э'ху - множества пар значений координаты Ъ, задающих множества СНху и Эху соответственно.

Элементами пар множества <3'1ху являются координаты Ъ точек пересечения Яху с поверхностью Рь Ориентация поверхности в данной точке пересечения определяет место в паре соответствующей координаты Ъ, задающей либо ближний, либо дальний конец отрезка, принадлежащего Яху.

В процессе обработки АЛМ выделены два этапа:

- этап обработки АК модели;

- этап обработки Л К модели.

Задача этапа обработки АК модели объекта Б сформулирована следующим образом:

для всех 1*, входящих в модель данной области Б, и всех (х,у) из Еп выполнить преобразование

П : 1Л-»СГ1ху такое, что

СПху = Р10,х,у).

Задача этапа обработки ЛК модели объекта Б сформулирована следующим образом:

для всех (х,у) из Еп выполнить преобразование

¥2: { фху } Б ху, такое, что

Б'ху = Р2(х,у) = Т({ (^¡ху }), где Т' - представление ТМФ Т, в котором ТМО над { (^¡ху } реализованы операциями над { С^Чху}.

Этап обработки ЛК - это этап образования формы объекта Б, состоящий в получении представления пространственной формы В в виде {Б'ху} из представлений исходных элементарных форм в виде {СПху} для всех (х,у) из Еп.

Очевидно, что в точке (х,у) видимой поверхностью объекта О будет та Р1, которой принадлежит точка Яху, соответствующая наименьшей координате 2гшп из Б'ху. Пара (Р1, 2т'т ) обрабатывается алгоритмом Ъ-буфера. После выполнения преобразований П и Б2 для всех объектов и всех точек из Еп задача, сформулированная в виде (1), будет решена.

Такой подход позволяет уравнения всех поверхностей обрабатывать независимо одно от другого, так как не требует построения линий пересечения поверхностей и, следовательно, решения систем уравнений. Для сокращения объема вычислений при выполнении преобразования ¥2 предложен метод, ориентированный на использование на этапе визуализации ТМФ фиксированной стандартной формы.

Пространственные формы, задаваемые пересечением элементарных пространственных областей, названы простыми геометрическими телами (ПГТ) (как в работах Горелика А.Г.). Показано, что декомпозиция произвольных объектов до уровня ПГТ приводит к значительному объему лишних вычислений. Поэтому в качестве стандартной выбрана форма ТМФ, описывающая более широкий класс геометрических форм, чем ПГТ:

0 = Т2\иТ0к) (2)"

к

где О - объект, названный деталью;

Т7. - тело-заготовка данной детали ;

ТОк - тела-отверстия данной детали .

Деталь Б задается как объект, получаемый из своей исходной формы тела-заготовки ТЪ удалением тел-отверстий ТОк. В качестве ТЪ и ТОк используются ПГТ.

Как видно, процесс формообразования объекта Б имеет аналогии с процессом изготовления деталей в машиностроении. Это и послужило поводом для введения термина "деталь" для объекта, заданного в виде (2). Но следует отметить, что термин "деталь" в смысле (2) не всегда совпадает с соответствующим понятием, принятым в машиностроении.

Предложен итерационный алгоритм выполнения преобразования И2, учитывающий особенности ТМФ, задающей отдельную деталь в виде (2). Алгоритм состоит в построении в Яп исходной формы детали Б в виде Т7, и постепенном ее преобразовании в результирующую форму детали путем вычитания из множества точек пространства Ил, принадлежащих текущему состоянию формы детали, множества точек, принадлежащих очередному обрабатываемому телу-отверстию ТОк •

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

В процессе выполнения предложенного алгоритма необходимо отображать форму следующих пространственных тел: ТЪ, ТОк, Б (к), где Б (к) - текущее состояние формы детали Б после обработки тела-отверстия ТОк.

Б(0):=Тг; Б(к) := Б(к-1)\ТОк. (3)

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

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

- способ отображения формы перечисленных тел;

- метод обработки модели детали, учитывающий особенности отображения формы и использующий введенные автором специальные коор-динатно зависимые модификации ТМО, применяемые к отрезкам ПП: модифицированное теоретико-множественное вычитание (МТМВ); две модификации теоретико-множественного пересечения (МТМП). Результат введенных модификаций ТМО зависит от ориентации пространственных

областей, участвующих в них, относительно оси Ъ системы координат, в которой эти области обрабатываются. Это обстоятельство позволило определить введенные модификации ТМО как координатно зависимые.

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

Предложено: для отображения формы тел ТОк, Б(к) при всех к использовать только по одному отрезку каждой из ПП на каждое тело. Показано, что при последовательной обработке моделей ТОк трех множеств координат Ъ концов отрезков ПП достаточно для отображения формы всех тел, перечисленных выше.

При построении в Яп ПГТ применены специальные отображения их формы, названные "отображением с избытком" (ОИ) (для тела-заготовки и текущего состояния формы детали) и "неполным отображением" (НО) (для тел-отверстий). Эти отображения порождаются двумя модификациями операции МТМП.

При ОИ все данное множество отрезков ПП заменяется одним отрезком наименьшей длины, содержащим в себе все данные отрезки.

НО формы ПГТ состоит в том, что для каждой данной ПП из всех отрезков, принадлежащих данному ПГТ, выбирается единственный: тот, который содержит в себе видимую точку текущей формы Б( к ) из ( 3).

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

В ТРЕТЬЕМ РАЗДЕЛЕ разрабатывается метод получения изображения падающих теней в растровой графике, применимый к моделям объектов, содержащих криволинейные поверхности в неаппроксимиро-ванном виде. При этом: сформулированы задачи этапов предварительной обработки модели сцены и синтеза кадра изображения; предложено вычислять и использовать специальный набор данных, названный боковым кадром (БК), отображающий все освещенные и только освещенные точки сцены; предложены, разработаны и проанализированы способы неявного задания в БК освещенных точек сцены; предложен способ и разработан алгоритм уменьшения объема данных, составляющих БК; разработан алгоритм анализа содержимого БК на этапе синтеза кадра изображения.

При разработке метода были приняты следующие ограничения:

- в пространстве моделируемой сцены существует плоскость, отделяющая источник света от сцены;

- все объекты сцены непрозрачны;

- вторичные источники света игнорируются.

В основу разрабатываемого метода положен следующий подход:

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

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

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

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

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

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

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

В качестве способа неявного задания положения точки в пространстве Ы3 предложено использовать некоторое множество Н(Т) признаков, характеризующих в совокупности единственную точку Т пространства ЯЗ:

Н(Т)= {Ы(Т),Ь2(Т).....Ьп(Т)},

где Ы(Т) - отдельный признак точки Т, значение которого, возможно, совпадает для множества точек из ЯЗ.

Таким образом, при неявном задании положения в пространстве точек содержимое БК задает множество освещенных точек сцены посредством множества множеств признаков: БК = { Н(Т)}.

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

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

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

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

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

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

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

Предложены алгоритмы вычисления координат X концов отрезков строк и восстановления содержимого БПП по данным из БК для точки БПП, соответствующей видимой и потенциально освещенной точке сцены. При этом показано, что часто не требуется точного восстановления содержимого БПП для данной его точки, так как оказывается

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

В конце раздела делаются выводы.

В ЧЕТВЕРТОМ РАЗДЕЛЕ приводятся краткие сведения о двух поколениях систем машинной графики, разработанных на основе методов, изложенных в разделах 2 и 3.

Система первого поколения была написана на языке ПЛ-1 для компьютеров ЕС-ЭВМ. В качестве средств визуализации использовались:

- специализированное устройство, разработанное и изготовленное с участием соискателя на кафедре "Вычислительная техника" Куйбышевского политехнического института, (Самарского государственного технического университета);

- технические средства компьютера Robotron на предприятии ЦСКБ г.Куйбышева.

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

Система второго поколения написана на языке Turbo-Pascal 6.0 под MS-DOS для IBM-PC совместимых компьютеров с адаптерами VGA и SuperVGA.

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

В ЗАКЛЮЧЕНИИ отмечены основные результаты работы.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

1. Пугачев А.И., Мартемьянов Б.В. Метод построения очерковых линий для систем машинной графики,- //Вычислительная техника в автоматизированных системах контроля и управления: Межвуз.сб.научн. тр.-. Пенза: Пенз.политехн. ин-т,1980, вып.10 -с.97-101.

2. Пугачев А.И., Мартемьянов Б.В. Построение тоновых цветных изображений объектов в системах моделирования и управления,-//Вычислительная техника в автоматизированных системах контроля и

управления: Межвуз.сб.научн.тр.- Пенза: Пенз.политехн. ин-т,1983, вып. 13 -с. 141-146.

3. Пугачев А.И., Мартемьянов Б.В. Преобразование поверхностей второго порядка в алгоритмах машинной графики. -Куйбышев: Куйбышевский политехи, ин-т., 1984. -5с. ( Рукопись деп. в ВИНИТИ 21.08.84 N 5956 - 84 Деп.).

4. Мартемьянов Б.В., Воронцов И.В., Пугачев А.И. Методы геометрического моделирования трехмерных объектов в САПР.-//Научно-методи-ческие основы использования ЭВМ, САПР в учебном процессе:Тез.докл. Всесоюзной. науч.-метод.конф. -Л.:ЛКИ,1985, -с.62.

5. Мартемьянов Б.В., Воронцов И.В., Орлов С.П. Автоматизированная обучающая система с использованием цветной машинной графики.-//Научно-методические основы использования ЭВМ, САПР в учебном процессе: Тез. докл. Всесоюзной науч.-метод.конф. -Л.:ЛКИ,1985, -с.84.

6. Мартемьянов Б.В., Воронцов И.В., Пугачев А.И. Комплекс программ растровой машинной графики,- //Методы и средства обработки сложной графической информации: Тез.докл. 2 Всесоюзной конф.-Горь-кий: ГГУ, 1985, -с.24.

7. Мартемьянов Б.В. О методе построения растровых изображений трехмерных объектов с тенями.-//Методы и средства обработки сложной графической информации: Тез.докл. 2 Всесоюзной конф.-Горький: ГГУ,1985, -с.58.

8. Мартемьянов Б.В. О методе формирования растровых изображений трехмерных объектов по алгебро-логической модели,- //Методы и средства обработки сложной графической информации: Тез.докл. 2 Всесоюзной конф.-Горький:ГГУ, 1985, -с.58.

9. Мартемьянов Б.В. Метод формирования изображений трехмерных объектов и сцен без вычисления очерковых линий и линий пересечения поверхностей. -Куйбышев: Куйбышевский политехи, ин-т., 1985. -16с. ( Рукопись деп. в ВИНИТИ 9.12.85 N 8449-В ).

10. Мартемьянов Б.В. Метод формирования изображений падающих теней в растровой графике.-Куйбышев: Куйбышевский политехи, ин-т., 1985. -17с. (Рукопись деп. в ВИНИТИ 9.12.85 N 8450-В ).

11. Мартемьянов Б.В. О методе формирования растровых изображений трехмерных объектов по алгебро-логической модели.- //Автоматизация обработки сложной графической информации: Межвуз. сб.науч. тр.-Горький: ГГУ, 1986, -с. 143-156.

12. Мартемьянов Б.В., Воронцов И.В., Пугачев А.И., Ратушный В.Э. Система математического обеспечения растровой машинной графики. -//4 Всесоюзной конф. по проблемам машинной графики: Тез. докл. -Серпухов: ИФВЭ,1987,-с. 71.

13. Мартемьянов Б.В., Воронцов И.В., Пугачев А.И. Формирование математических моделей пространственных объектов в диалоговых системах автоматизированного проектирования,- //Вопросы геометрического моделирования в САПР: Тез. докл. науч.-тех.конф.- Свердловск: УПИ, 1987,-с.6-7.

14. Воронцов И.В., Ратушный В.Э., Мартемьянов Б.В. Моделирование геометрии технических объектов и их функционирования в растровой системе визуализации.- //Методы и средства обработки сложной графической информации: Тез.докл. Всесоюз.конф. в 2 ч. -Горький: ГГУ,1988,ч.1,с.112.

15. Воронцов И.В., Мартемьянов Б.В., Ратушный В.Э., Аликов A.B. Конструирование математических моделей геометрических объектов в системах машинной графики.-//Математическое обеспечение САПР: Межвуз.сб.науч. тр.-Куйбышев:Куйбыш.авиац.ин-т, 1989,-с. 107-112.

16. Alikov A.Y.,Yorontsov I.V.,Martemjanov B.V., Pugachov A.I., Ra-tushny V.E. Graphics System for Geometric Modelling and Visualization of Three-Dimentional Object.-//International Symposium on Visual Analysis and Interface. :Theses.-Novosibirsk, USSR, 1991.-p.45.

17. Воронцов И.В., Ратушный В.Э., Мартемьянов Б.В. Моделирование и визуализация кинематики трехмерных технических объектов.-//Математическое обеспечение САПР: Межвуз. сб. науч.тр.-Куйбы-шев:Куйбыш.авиац.ин-т, 1991 ,-с.64-71.

18. Воронцов И.В., Пугачев А.И., Мартемьянов Б.В. Устройство для формирования изображений линий второго порядка на экране телевизионного приемника,- A.C. 1596376. СССР, МКИ G09 0публ.30.09.90. Бюл.ЫЗО.

Изображение абстрактной формы с отображением падающих теней. Время вычисления изображения на компьютере 486-0X2/80 для пространственного разрешения кадра 800*600 пэл составило:

- компиляция + предварительная обработка для подготовки синтеза теней (формирование "бокового кадра") - 26 сек.;

- этап формирования кадра

ЧУ

У

Усложненный вариант "Ьр-теста".

Текст модели составляет 22 строки. Количество поверхностей в модели на этапе визуализации - 106. Количество простых геометрических тел (ПГТ) - 189 (одна и та же поверхность входит в модель различных ПГТ ). Количество поверхностей в составе отдельного ПГТ колеблется от 4 до 25. Количество объектов, названных в разделе 2 деталью, - 27. Каждая деталь задается ровно 7-ю ПГТ - так получилось в результате декомпозиции модели.

Время визуализации (с учетам этапа компиляции и сохранения синтезированного кадра в файле) на компьютере 486-0X2/80 для пространственного разрешения кадра

/ /