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

ИНСТИТУТ ФИЗИКИ ВЫСОКИХ ЭНЕРГИЙ

95-21

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

Семновенков Михаил Николаевич

УДК 681.3.06

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

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем п сетей

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

Протвино 1995

Работа выполнена в Институте математических проблем биологии РАН (г. Пущино).

Научный руководитель:

кандидат технических наук В.Н. Кочин.

Официальные оппоненты:

доктор физико-математическ! наук, профессор C.B. Клименко,

кандидат технических наук О. С. Кислюк.

Ведущая организация:

Институт системного. программирования РАН (г. Москва).

Защита состоится "_

1995г. в_ча<

на заседании Специализированного совета К.034.02.01 в ИФ! по адресу: 142284 г. Протвино Московской обл.

С диссертацией можно ознакомиться в библиотеке ИФ

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

1995г.

Ученый секретарь Специализированного совета кандидат физико-математических наук

В.Н. Ла

© Институт физики высоких энергш

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

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

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

Целью диссертационной работы является:

1. Анализ требований, предъявляемых к базовой растровой графике со стороны систем более высокого уровня.

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

3. Разработка алгоритмов, проектирование и реализация базовой графики на различных аппаратных платформах.

4. Разработка и реализация алгоритмов базовой графики для трехмерного растра.

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

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

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

3. Предложены два способа интерполяции яркости пикселов многоугольника.

4. Предложен ряд базовых алгоритмов для развертки изображения в трехмерном растре: алгоритм развертки многоугольника в трехмерном растре, алгоритм вывода множества многоугольников в трехмерном растре, алгоритм вывода Z-сечения изображения в трехмерном растре, алгоритм оптимизации маршрута "пера" трехмерного графического устройства при выводе Z-сечения в трехмерном растре.

Практическая ценность работы.

1. Создан комплекс графических подпрограмм ГРАН, поддерживающий оконную систему для широкого круга графических дисплеев и ряда языковых и системных сред. Комплекс использован (в основном в составе систем программирования QUASIC-2 и QUASIC-3) во многих научных, производственных, военных, учебных заведениях для решения широкого круга задач.

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

Апробация работы. Содержание работ, составивших основу диссертации, докладывалось и получило одобрение на семинара) и конференциях ИМПБ РАН (бывший НИВЦ АН СССР, г Пущино), на республиканской школе-семинаре "Информатика i интерактивная компьютерная графика" (г. Дилижан

1986г.), на II международной школе по автоматизации научны; исследований (г. Пущино, 1987г.), на Международно!* коллоквиуме "Новые информационные технологии" (г. Москва 1991г.).

Публикации. Основные результаты и положени диссертации изложены в 8 печатных работах.

Структура н объем диссертации. Диссертация состоит и введения, четырех глав, заключения, списка литературы (9 наименование) и лрнложений.Общий объем работы 9

страницы, в том числе 60 страниц основного текста, 3

рисунков и 1 таблица.

)

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

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

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

возможности упомянутых в главе графических систем и стандартов.

Главные понятия системы базовой графики и их взаимосвязь: Графическое устройство выполняет запросы о аппаратных возможностях, текущем состоянии, изменении текущего состояния. Обладает Видеопамятью (Растром). Видеопамять может быть реализована в видеопамяти физического графического дисплея, в ОЗУ, в файле, а также на принтере, где "память" работает только на запись.

Окно - прямоугольник виртуального Растра, в который выводятся графические примитивы.

Основные графические примитивы - Линия и Область.

Линия состоит из звеньев, заданных концевыми пикселами; координаты промежуточных пикселов вычисляются Генераторами координат пикселов, набор которых открыт для пополнения.

Область ограничена замкнутой Линией.

Над множеством Областей заданы операции (объединение, пересечение, вычитание).

Специфически растровые примитивы - прежде всего прямоугольник пикселов (частные случаи операций - сдвиг изображения на экране, обмен видеопамяти с ОЗУ, "твердая сопия").

Графический контекст - совокупность атрибутов Линий и Областей. Атрибуты можно приписывать любому звену Линии I, соответственно, любому звену границы Области. Множество

значений атрибутов не фиксировано: Базовая система открыта для включения процедур интерпретации атрибутов.

Область отсечения. В качестве области отсечения можно использовать любую Область.

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

Глава 2 содержит описание разработанного автором комплекса графических подпрограмм ГРАН.

Комплекс базовой растровой графики ГРАН реализован как переносимый для семейства ЭВМ с системой команд РОР-11. Реально комплекс эксплуатировался на следующих ЭВМ:

"Элекгроника-60";

ДВК-2, 3, 4;

"Элекгроника-85";

СМ-4;

сеть СМ-4 - "Элекгроника-60";

МЕИА-бО;

СМ-3.

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

- контроллер КГД для ДВК-2;

- контроллер КЦГД для ДВК-3;

- графический контроллер для "Электроники-85";

- контроллер МТУ-60 для МЕИА-бО.

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

В комплексе ГРАН обеспечена переносимая реализацш операции "твердая копия". Автором выполнена поддержю "твердой копии" следующих принтеров:

- 0100;

- БЮОМ;

- ЕР50М-РХ-800 и аналогичных по системе

графических команд;

- УВВПЧ-30-004.

Комплекс ГРАН реализован для ряда языковых и операционных сред:

- для семейства систем программирования

(¿иАБЮ, С?иА81С-2, диАБГС-З;

- для языка ФОРТРАН-ГУ под ОС 11Т11,

ЯБХПМ;

- для языка С под ОС КЛТ1.

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

Реализация комплекса очень компакта и занимает от 5 до 8 Кбайтов оперативной памяти (в зависимости от типа поддерживаемого графического устройства). Компактность во многом была достигнута благодаря следованию ряду принципов, обсуждавшихся в главе 1, а также в главе 2 диссертации. Так, важным правилом, использованным при разработке комплекса было стремление избегать увеличения понятий (и, соответствешю, подпрограмм) для реализации запланированных возможностей, а также пытаться извлечь максимум из реализованных алгоритмов.

Комплекс ГРАН обеспечивает поддержку системы окон. В окнах наряду с традиционной пикселной системой координат поддерживаются символьная и декартова системы координат, что увеличивает удобства пользователя и возможности переносимости программ, использующих разные дисплеи. Все системы координат окна равноправны, т.е. в любой ситуации может' использоваться любая система координат. Например, открывая окно внутри уже существующего, пользователь указывает расположение окна-сына в системе координат окна-отца. Использование в этом случае символьной или математической систем координат окна (вместо традиционной пикселной) увеличивает возможности создания переносимых программ пользователя.

Комплекс ГРАН предоставляет следующий набор графических операций:

- вывод точки (пиксела);

- чтение цвета точки;

- вывод отрезка;

- вывод окружности, круга;

- вывод закрашенного прямоугольника;

- вывод границы прямоугольника;

- копирование фрагмента изображения внутри окна;

- запоминание фрагмента изображения в массиве;

- вывод фрагмента изображения из массива;

- перемещение рисунков, так называемых спрайтов;

- вывод строки символов, стандартных и

пользовательских;

- закрашивание замкнутых областей ("заливка");

- вывод осей математической системы координат.

Комплекс ГРАН распространялся - фондом алгоритмов и программ (ФАЛ) НИВЦ АН СССР (ныне ИМПБ РАН), г. Пущино. Официальный тираж комплекса составляет свыше 60 экземпляров. Копии документов о сдаче комплекса ГРАН в ФАЛ НИВЦ АН СССР и передачах комплекса (как составной части систем программирования риАБ1С-2 и (^иАБЮ-З) в сторонние организации приведены в приложениях диссертации.

Система программирования С>иА81С-2 (и, соответственно, комплекс ГРАН как ее составляющая) рекомендована Межотраслевым экспертным советом по содействию внедрению научно-технических достижений в качестве штатного программного обеспечения серийно выпускаемых микроЭВМ.

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

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

Прежде всего в главе проанализированы стратегии реализации примитива "многоугольник". На основе анализе известных алгоритмов растровой развертки многоугольнике указаны три основные стратегии реализации примитива Стратегии суть следующие: 1) алгоритм полной сортировю координат пикселов границы многоугольника, 2) алгоритмы использующие буфер кадра, 3) алгоритмы с построчно] генерацией границы многоугольника. Для стратега] проанализированы основные накладные расходы, связанные с и: реализацией. Указаны результаты соответствующи:

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

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

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

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

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

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

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

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

- вывод неодиосвязны;: многоугольников,

- вывод многоугольных карт заполнения,

- выполнение теоретико-множественных операций

над многоугольниками,

- интерполяция яркости пикселов многоугольника,

- вывод проекции трехмерной поверхности с

удалением невидимых линий,

- вывод примитива Ceil Array.

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

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

Автором программно реализован ряд описанных в главе задач. При подготовке соответствующих рисунков для диссертации использована программная реализация алгоритмов для IBM PC иод операционной системой DOS.

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

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

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

Первая задача, рассматриваемая в главе - задача развертки многоугольника в трехмерном растре. Задача сведена к следующей вспомогательной задаче: дан плоский многоугольник и яркость его вершин, найти яркости пикселов многоугольника. Таким образом трехмерная задача сведена к двумерной, где яркость играет роль третьей координаты. Вспомогательная задача решается с помощью одного из методов интерполяции яркости пикселов многоугольника, предложенных в главе 2. Суть метода состоит в добавлении к многоугольнику дополнительных ребер, которые разделяют многоугольник на области с разной яркостью. В терминах исходной задачи это соответствует различным г-сечениям трехмерного многоугольника. Решение вспомогательной задачи опирается на открытую реализацию примитива "многоугольник", предложенную в главе 3 диссертации.

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

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

Для решения проблемы вывода поверхности предлагается алгоритм, который является обобщением на трехмерный случай алгоритма вывода многоугольника с построчной генерацией границы многоугольника. Аналогами ребер плоского многоугольника выступают грани поверхности. Аналог скан-линии у=с - скан-плоскость г—с. В сечении грани скан-плоскостью получаются отрезок или многоугольник (аналогично тому, как в сечении ребра плоского многоугольника получаются точка или отрезок). Предлагаемый в главе алгоритм сводится к нахождению последовательных сечений поверхности скан-плоскостью и выводу получаемых г-сечений.

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

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

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

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

В_приложениях приведен ряд документов о

распространении комплекса ГРАН,

ЗАКЛЮЧЕНИЕ

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

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

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

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

4. Предложено обобщение примитива Cell Array на случай произвольного выпуклого четырехугольника и показан способ реализации обобщенного примитива.

5. Предложены два способа интерполяции яркости пикселов многоугольника.

6. Предложен ряд базовых алгоритмов для развертки изображения в трехмерном растре: алгоритм развертки многоугольника в трех,мерном растре, алгоритм вывода множества многоугольников в трехмерном растре, алгоритм вывода Z-сечения изображения в трехмерном растре, алгоритм оптимизации маршрута "пера" трехмерного графического устройства при выводе Z-сечения в трехмерном растре.

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

1. Барилко Ш.И., Семкопенков М.Н., Бурякова H.JI., Буряков Г.В. Программное обеспечение цветных бытовых телевизоров, используемых в качестве устройств графического вывода микроЭВМ // В кн.: Тезисы докладов республиканской школы-семинара "Информатика и интерактивная компьютерная графика". - Дилижан, 1986, стр. 33-34.

2. Подольский Л.И., Семноненков М.Н., Стаценко П.Б. Интегрированная система программирования QUASIC-3. -Пущино, ОНТИ ПНЦ РАН, 1992.

3. Ссмкопенков М.Н. Комплекс графических подпрограмм ГРАН // В сб.: Международный коллоквиум "Новые информационные технологии" Доклады. - М.: МЦНТИ, 1991, стр. 233-234.

4. Семноненков М.Н. Комплекс подпрограмм растровой графики ГРАН для ДВК и "Электроники-60". Версия 2.5. -Пущино, ОНТИ НЦБИ АН СССР, 1990.

5. Семноненков М.Н. Программное обеспечение бытовых цветных телевизоров, используемых в качестве устройств графического вывода мини- и микроЭВМ// В кн.: Материалы II международной школы по автоматизации научных исследований. - Пущино, ОНТИ НЦБИ АН СССР, 1987, стр. 287-289.

6. Семноненков М.Н. Развертка многоугольника в трехмерном растре. - Пущино, ОНТИ ПНЦ РАН, 1994.

7. Семноненков М.Н., Кочин В.Н. Базовый графический примитив "Cell Array для произвольного выпуклого четырехугольника растровой плоскости". Понятие обобщенного многоугольника для базовой графики. - Пущино, ОНТИ ПНЦ РАН, 1994.

8. Стаценко П.Б., Подольский Л.И., Сешкшенков М.Н. Интегрированная система программирования QUASIC-3 для ДВК-ЗМ, ДВК-4 и "Электроники-85" I/ Информатика и образование. 1993. N 2, стр. 42-52.

Рукопись поступила 14 февраля 1995г.