ББК 32.973 Ш57 УДК 681.327.1 Е. В. Шикин, А. В. Боресков, А. А. Зайцев Ш57 Начала компьютерной графики. — М.: "ДИАЛОГ- МИФИ", 1993. — 138 с. ISBN 5-86404-035-5 Книга знакомит с такими понятиями компьютерной графики, как растровые алгоритмы, геометрические сплайны, преобразования на плоскости и в пространстве и проектирование. Она дает рабочее представление об основных направлениях и методах компьютерной графики, включая способы построения реалистических изображений и удаления невидимых линий, позволит освоить базовые приемы реализации ее алгоритмов на персональных компьютерах. Книгу можно рассматривать как практическое руководство. Она рассчитана на читателей, знакомых с элементами аналитической геометрии, линейной алгебры и языком программирования Pascal. Ш 2404000000-008 Г70(03)-93 Без объявл. ВБК 32.973 Учебно-справочное издание Евгений Викторович Шикин Алексей Викторович Боресков Андрей Александрович Зайцев Начала компьютерной графики. Редактор О. А. Голу^Ьв Макет и обложка О. А. Кузьминовой Корректор В. С. Кустов Лицензия ЛР N 070109 от 29.08.91. Подписано в печать 23.12.93. Формат 60х84/16. Бум. офс. Печать офс. Гарнитура Тайме. Усл. печ. л. 8.37. Уч.-изд. л. 6.45. Тираж 15 000 экз. Заказ 12)^ Акционерное общество "ДИАЛОГ-МИФИ" 115409, Москва, ул. Москворечье, 31, корп. 2 Подольская типография 142100, г. Подольск, Московская обл., ул. Кирова, 25 ISBN 5-86404-035-5 © Е. В. Шикин, А. В. Боресков, А. А. Зайцев 1993 ©Оригинал-макет, оформление обложки. АО "ДИАЛОГ-МИФИ", 1993 ПРЕДИСЛОВИЕ В настоящее время в связи с широким внедрением персональных компьютеров во все сферы жизни, резкой интенсификацией процесса научных исследований, революционным совершенствованием его технологии, значительным повышением возможностей аппаратуры все больший интерес вызывают идеи, алгоритмы и средства компьютерной графики. Спектр использования компьютерной графики чрезвычайно широк: от создания рекламных роликов, компьютерных мультфиль- мов и игр, кроя одежды, малых и монументальных форм дизайна, компьютерной живописи до визуализации результатов научных изысканий и конструирования фактически нового инструментария в процессе получения знаний. В Европе, США и Японии ежегодно проводятся представительные междуна- родные конференции по компьютерной графике, издаются десятки журналов и выпускается множество книг, посвященных различным аспектам компьютерной графики и ее применениям. Наши успехи в этом направлении выглядят значительно скромнее. Правда, в самое последнее время наметились определенные тенденции к изменению ситуации: проведены две международные конференции "Графикон-91" и "Графикон-92" и начал выходить журнал "Компьютерная графика". Что же касается литературы, то отечественных пособий и руководств по компьютерной графике практически нет. Вместе с тем, как показало оживленное обсуждение проблем преподавания компьютерной графики на конференции "Графикон-92", проходившей в октябре 1992 года в Москве, интерес к машинной графике в нашей стране и разнообразен, и очень велик. Поэтому во многих российских учебных центрах появилось наме- рение организовать на базе университетов и крупных инженерных вузов чтение курсов по компьютерной графике. Одним из серьезных препятствий на этом пути является практическая невозможность обеспечить слушателей подобных курсов доступной учебной литературой. Отчасти это можно объяснить быстрым разви- тием новых методов компьютерной графики, многие из которых описаны только в журнальных публикациях. Изучение книжного рынка показало наличие значительной потребности в книгах по компьютерной графике. Подобный интерес обусловлен в первую очередь красотой и эффективностью самой компьютерной графики, знакомство с которой необходимо разработчику аппаратуры и инженеру-конструктору, дизай- неру и кинооператору, художнику-модельеру и специалисту по рекламе. Существующая литература (фактически только переводная) издана довольно д,"гно, далеко не всегда удовлетворяет отечественным (традиционно высоким) требованиям, предъявляемым к учебной литературе и, наконец, практически недоступна. •ДИАЛОГ-МИФИ" "* Последние несколько лет на факультете вычислительной математики и ки- бернетики Московского государственного университета им. М. В. Ломоносова читается курс "Начала компьютерной графики", вызывающий чрезвычайно боль- шой интерес у студентов разных курсов и факультетов, а также у слушателей инженерного потока. Опыт чтения этого курса показывает, что даже сравнительно небольшого, просто и доступно изложенного набора сведений по компьютерной графике оказывается достаточно для самостоятельного выполнения весьма содер- жательных геометрических и графических задач без привлечения дополнительной литературы. Название предлагаемой книги - "Начала компьютерной графики" - довольно верно отражает и ее содержание, и цели, которые ставили перед собой авторы при ее написании. Предпринимая попытку познакомить читателя с одним из бур- но развивающихся направлений использования персональных компьютеров, мы сознательно ограничились изложением только самых основных понятий, приемов и фактов, связывая это не столько с допустимым объемом издания (он срав- нительно невелик), сколько с тем обстоятельством, что практически каждый новый выпуск любого из журналов, посвященных работе на персональных ком- пьютерах, приносит многие интересные результаты, раскрывающие направления развития возможностей и вглубь, и вширь. Частью этих материалов авторы поль- зовались при подготовке книги. На отбор материала повлияло также желание дать в руки читателю инструмент пусть и не слишком изощренный, но достаточно совершенный для того, чтобы решать содержательные задачи. Среди многообразия возможностей, предоставляемых современными вычислительными средствами, те, что основаны на пространственно-образном мышлении человека, занимают особое место. Современные программно-опера- тивные средства компьютерной графики представляют собой весьма эффективный инструмент поддержки такого мышления при выполнении работ самых разных ви- дов, и проектно-конструкторских, и научно-исследовательских, и производственно- оформительских. С другой стороны, именно пространственно-образное мышление является неформальной творческой основой для расширения изобразительных возможностей компьютеров. Это важное обстоятельство предполагает взаимно обогащающее, органическое сотрудничество все более совершенной техники и человека со всем богатством знания, накопленного предшествующими поколения- ми. Глаз и раньше был эффективным средством познания человеком мира и себя. Поэтому столь привлекательной оказывается компьютерная визуализация, особен- но визуализация динамическая, которую следует рассматривать как важнейший инструмент для обучения наукам. По мнению авторов, во вводном курсе основное внимание следует уделить алгоритмам и методам компьютерной графики, не оставляя в стороне, разумеется, ее программного и технического обеспечения. Алгоритмы и методы, используемые при первом знакомстве, должны быть достаточно простыми. Читатель познакомится с ключевыми понятиями компьютерной графики, по- лучит рабочее представление об основных ее направлениях, включая методы построения реалистических изображений, освоит основные программистские 4 приемы реализации алгоритмов компьютерной графики на персональном компью- тере, включая принципы организации работы с современными графическими интерфейсами. Книга содержит материал, отобранный на основе опыта чтения указанного выше курса и "визуализированного" приема экзаменов, заключавшегося в демон- страции выполненного задания (динамической картинки) на экране персонального компьютера. Книгу можно рассматривать как практическое руководство: в ней приводятся примеры графических задач, которые способен самостоятельно выполнить на персональном компьютере пользователь, прочитавший книгу. По желанию можно приобрести дискету содержащую тексты всех программ, приведенных в книге, а также обучающую программу "Геометрические пре- образования", иллюстрирующую в динамике один из разделов книги. За дискетой нужно обращаться в издательский отдел АО "ДИАЛОГ-МИФИ". На пути от замысла этой книги до ее выхода произошло значительное число событий, прямо или косвенно повлиявших на ее судьбу. Среди случившихся обстоятельств наряду с объективными было много трудностей, носивших вполне субъективный характер. В наше непростое время неожиданной и весьма приятной оказалась поддер- жка издательского отдела "ДИАЛОГ-МИФИ" и его сотрудников. Без нее, а также нетривиального участия в самый критический момент Александра Ивановича Плиса и Андрея Фазыловича Мубаракшина книга вряд ли дошла бы до читателя. Выражением благодарности к ним я и хочу завершить предисловие. 19 июля 1993 года Е. В. Шикин 'ДИАЛОГ-МИФИ' СОДЕРЖАНИЕ ПРЕДИСЛОВИЕ....................................................................................................3 ГРАФИЧЕСКИЕ ПРИМИТИВЫ В ЯЗЫКАХ ПРОГРАММИРОВАНИЯ.................. 6 Инициализация и завершение работы с библиотекой ...........................••••••••••• 7 Работа с отдельными точками ................................................•••••••••••••••••••••••••••^ Рисование линейных объектов .................................•••••••••••••••'••••••••••••••••••••••••• 9 Рисование сплошных объектов...............———.—————————-—————— *® Закрашивание объектов ....................————————•—•••—••••••—••—•—— ^ Работа с изображениями. ................................-•••••••••••••••••••••••••••••••••••••••• ^ Работа со шрифтами ...............................................————————•—————•12 Понятие режима (способа) вывода..........................••••••---•••••••••••••••••••••••••13 Понятие окна (порта вывода) ..........................................-••••••••--•••••••••••••••14 Понятие палитры .....................................—...............-——————•——•• 14 Понятие видеостраниц и работа с ними. ..............................-••-••••••••••••••••••••15 Подключение нестандартных драйверов устройств .........................•.....•••••••••^ ПРЕОБРАЗОВАНИЯ НА ПЛОСКОСТИ И В ПРОСТРАНСТВЕ.......................... .17 Аффинные преобразования на плоскости ...............................................•••••••••*7 Аффинные преобразования в пространстве ....................................................23 Виды проектирования ... ..,..............................................••••••••••••••••••••••••••••••••• 27 Особенности проекций гладких отображений.................................................33 ГЕОМЕТРИЧЕСКИЕ СПЛАЙНЫ..............................................----------36 РАСТРОВЫЕ АЛГОРИТМЫ...............———.—————.———....—————.49 Простейшие свойства множеств на целочисленной решетке .........................49 Растровое представление геометрических объектов.......................................50 Понятие растрового представления геометрического объекта...............50 Растровая развертка отрезка. Алгоритм Брезенхема ..................................... 51 Общий алгоритм Брезенхема для восьмисвязной развертки отрезка ............55 Заполнение сплошных областей. .....................---...———•••———•-•••- ел Тест принадлежности точки многоугольнику ..........................•••••••••••••••57 Заполнение многоугольников .......................................—.--..-——-58 Алгоритмы заполнения области с затравкой ............................••••••••••••••59 УДАЛЕНИЕ НЕВИДИМЫХ ЛИНИЙ И ПОВЕРХНОСТЕЙ...............-——..——.63 Постановка проблемы и терминология. ...................-.---.-•————••••• 63 Некоторые подходы к решению задач загораживания ..................................67 Методы переборного типа .....................--.-.-—- .............................67 Метод Z-буфера... ..........................................................•.••••••••••••••••••••••68 Удаление нелицевых граней многогранника .................--——. ..................70 Методы количественной невидимости ................................-••••••••••••••••••••71 136 Разбиение картинной плоскости. Алгоритм Варнака .............................74 Кеширование по равномерной сетке...................——............................ 74 Методы приоритетов. ........—••—•- •——••.•••••-•-•-••—•——•——••••—• 75 Простейший вариант метода художника. Полутоновое изображение поверхности .................................................75 Метод плавающего горя30"" ..——•••••••••-————————•• —•76 Метод плавающего гори30""- Растровая версия................................... 77 Метод двоичного разбиения пространства......................................................80 Алгоритмы построчного сканирования............................................................ 81 ТРИАНГУЛЯЦИЯ. ПОСТРОЕНИЕ ЛИНИЙ УРОВНЯ ........———..—————— .83 Приближение функции на нерегулярной сетке. Триангуляция с вершинами в произвольном множестве точек......................83 Алгоритм построения триангуляции................................................................84 Структура данных для представления планарного графа ...............................86 Построение линий уровня функции двух переменных ................................... 87 РАБОТА С ОСНОВНЫМИ ГРАФИЧЕСКИМИ УСТРОЙСТВАМИ——...——.—.92 Мышь............................................................................................................... 92 Инициализация и проверка наличия мыши............................................93 Высветить на экране курсор мыши.........................................................93 Убрать (сделать невидимым) курсор мыши ............................................93 Прочесть состояние мыши (ее координаты и состояние кнопок) ..........93 Передвинуть курсор мыши в точку с заданными координатами............94 Принтер............................................................................................................94 Видеокарты EGA и VGA..................................................................................99 16-цветные режимы адаптеров EGA и VGA..................................................100 Graphics Controller (порты $ЗСЕ- $3CF).............................——.——.. 103 Sequencer (порты $ЗС4-$ЗС5).............................................................. 104 Режимы чтения.............................................................................................. 105 Режим чтения О.....................................................................................105 Режим чтения 1 .....................................................................................105 Режимы записи ..............................................................................................106 Режим записи 0.....................................................................................106 Режим записи 1..................................................................................... 107 Режим записи 2..................................................................................... 107 256-цветный режим адаптера VGA................................................................109 ГРАФИЧЕСКИЙ ПОЛЬЗОВАТЕЛЬСКИЙ ИНТЕРФЕЙС......................................110 Основные типы окон....................................................................................... 113 Нормальное ("классическое") окно ........................................................113 Кнопка (нажимаемая кнопка - Pushbutton)...........................................114 Check Box (переключатель)............ .....................................................114 Radio Button............................................................................................114 Редактор..................................................................................................114 "ДИАЛОГ-МИФИ" 137 Статический текст........................................................................... .. 114 Скроллер (Scroll Bar)......................................................................114 Список (List Box)............................................................................ ..114 СОЗДАНИЕ РЕАЛИСТИЧЕСКИХ ИЗОБРАЖЕНИЙ ............................................118 Трассировка лучей.......................................................................................... 118 Излучательность..............................................................................................121 ГРАФИЧЕСКИЙ ПРАКТИКУМ............................................................................. 124 Контрольные вопросы и задания ................................................................... 124 Задания первого уровня................................................................................. 126 Задания второго уровня................................................................................. 126 Задания третьего уровня ............................................................................... 126 Задания четвертого уровня........................................................................ ,...127 Задания пятого уровня .............................................................................. ....127 ГЛОССАРИЙ.........................................................................................................128 138 АО "ДИАЛОГ-МИФИ" продолжает серию книг ШГ иблиотека (JB истемного Ш рограммиста следующими изданиями: Том Ю. КОМПЬЮТЕР IBM PC/AT, MS-DOS и Windows ВОПРОСЫ И ОТВЕТЫ А. В. Фролов, Г. В. Фролов Книга охватывает ряд вопросов, наиболее часто возникающих при работе с компьютером. Мы рассмотрели проблемы, постоянно преследующие пользователей компьютерной техники, в том числе установку операционных систем MS-DOS 6.0 и Windows 3.1, русификацию компьютера и программ, восстановление данных. Приведены рекомендации по увеличению объема доступной оперативной и внешней памяти. Описаны средства защиты компьютерных данных от несанкционированного доступа. Том 11. ОПЕРАЦИОННАЯ СИСТЕМА Microsoft Windows ВВЕДЕНИЕ ДЛЯ ПРОГРАММИСТА. Часть 1 А. В. Фролов, Г. В. Фролов Первый из нескольких томов, посвященный программированию для операцион- ной системы Microsoft Windows. В книге рассмотрены основные принципы работы Microsoft Windows версии 3.1. Приведены все сведения, необходимые для того чтобы приступить к программированию в среде этой операционной системы. Книга содержит большое количество примеров программ на языке C++. Все примеры подготовлены для транслятора Borland C++ for Windows версии 3.1. В последующих томах будут подробно рассмотрены различные аспекты программирования для Microsoft Windows, в частности, графический интерфейс GDI, протоколы DDE и OLE, системы мультимедиа, интерфейс Win32s.