Алгоритмические основы современной компьютерной графики

Алгоритмические основы современной
компьютерной графики

2-е издание, исправленное

Куликов А.И.
Овчинникова Т.Э.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Алгоритмические основы современной компьютерной графики/ А.И. Куликов, Т.Э. Овчинникова М.: Национальный Открытый Университет “ИНТУИТ”, 2016

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

(c) ООО “ИНТУИТ.РУ”, 2007-2016
(c) Куликов А.И., Овчинникова Т.Э., 2007-2016

3

Общее введение в компьютерную графику

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

Предмет и область применения компьютерной графики

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

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

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

Сфера применения компьютерной графики включает четыре основных области.

1. Отображение информации

4

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

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

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

2. Проектирование

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

3. Моделирование

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

5

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

4. Графический пользовательский интерфейс

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

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

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

построение модели объекта и формирование изображения;
преобразование модели и изображения;
идентификация объекта и получение требуемой информации.

Обработка и анализ изображений касаются в основном дискретного (цифрового)
представления фотографий и других изображений. Средства компьютерной графики
здесь используются для:

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

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

6

видеонаблюдения.

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

Одним из наиболее ранних примеров использования когнитивной компьютерной
графики является работа Ч.Страуса “Неожиданное применение ЭВМ в чистой
математике” (ТИИЭР, т. 62, № 4, 1974, с.96-99). В ней показано, как для анализа
сложных алгебраических кривых используется “n-мерная” доска на основе
графического терминала. Пользуясь устройствами ввода, математик может легко
получать геометрические изображения результатов направленного изменения
параметров исследуемой зависимости. Он может также легко управлять текущими
значениями параметров, “углубляя тем самым свое понимание роли вариаций этих
параметров”. В результате получено “несколько новых теорем и определены
направления дальнейших исследований”.

В настоящем курсе предполагается рассмотреть следующие вопросы:

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

Краткая история

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

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

Первой официально признанной попыткой использования дисплея для вывода
изображения из ЭВМ явилось создание в Массачусетском технологическом
университете машины Whirlwind-I в 1950 г. Таким образом, возникновение
компьютерной графики можно отнести к 1950-м годам. Сам же термин “компьютерная
графика” придумал в 1960 г. сотрудник компании Boeing У. Феттер.

Первое реальное применение компьютерной графики связывают с именем Дж. Уитни.
Он занимался кинопроизводством в 50-60-х годах и впервые использовал компьютер

7

для создания титров к кинофильму.

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

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

В том же 1961 г. студент Стив Рассел создал первую компьютерную видеоигру
Spacewar (“Звездная война”), а научный сотрудник Bell Labs Эдвард Зэджек создал
анимацию “Simulation of a two-giro gravity control system“.

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

Университет штата Юта становится центром исследований в области компьютерной
графики благодаря Д.Эвансу и А.Сазерленду, которые в это время были самыми
заметными фигурами в этой области. Позднее их круг стал быстро расширяться.
Учеником Сазерленда стал Э.Кэтмул, будущий создатель алгоритма удаления
невидимых поверхностей с использованием Z-буфера (1978). Здесь же работали
Дж.Варнок, автор алгоритма удаления невидимых граней на основе разбиения области
(1969) и основатель Adobe System (1982), Дж.Кларк, будущий основатель компании
Silicon Graphics (1982). Все эти исследователи очень сильно продвинули
алгоритмическую сторону компьютерной графики.

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

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

В 1977 г. появляется новый журнал “Computer Graphics World”.

В середине 1970-х годов графика продолжает развиваться в сторону все большей
реалистичности изображений. Э.Кэтмул в 1974 г. создает первые алгоритмы
текстурирования криволинейных поверхностей. В 1975 г. появляется упомянутый

8

ранее метод закрашивания Фонга. В 1977 г. Дж.Блин предлагает алгоритмы
реалистического изображения шероховатых поверхностей (микрорельефов); Ф.Кроу
разрабатывает методы устранения ступенчатого эффекта при изображении контуров
(антиэлайзинг). Дж.Брезенхем создает эффективные алгоритмы построения растровых
образов отрезков, окружностей и эллипсов. Уровень развития вычислительной техники
к этому времени уже позволил использовать “жадные” алгоритмы, требующие
больших объемов памяти, и в 1978 г. Кэтмул предлагает метод Z-буфера, в котором
используется область памяти для хранения информации о “глубине” каждого пикселя
экранного изображения. В этом же году Сайрус и Бэк развивают алгоритмы
клиппирования (отсечения) линий. А в 1979 г. Кэй и Гринберг впервые реализуют
изображение полупрозрачной поверхности.

В 1980 г. Т.Уиттед разрабатывает общие принципы трассировки лучей, включающие
отражение, преломление, затенение и методы антиэлайзинга. В 1984 г. группой
исследователей (Горэл, Торрэнс, Гринберг и др.) была предложена модель
излучательности, одновременно развиваются методы прямоугольного клиппирования
областей.

В 1980-е годы появляется целый ряд компаний, занимающихся прикладными
разработками в области компьютерной графики. В 1982 г. Дж.Кларк создает Silicon
Graphics, тогда же возникает Ray Tracing Corporation, Adobe System, в 1986 г. компания
Pixar отпочковывается от Lucasfilm.

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

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

1968, ВЦ АН СССР, машина БЭСМ-6, вероятно, первый отечественный растровый
дисплей с видеопамятью на магнитном барабане;

1972, Институт автоматики и электрометрии (ИАиЭ), векторный дисплей “Символ”;

1973, ИАиЭ, векторный дисплей “Дельта”;

1977, ИАиЭ, векторный дисплей ЭПГ-400;

1982, Киев, НИИ периферийного оборудования, векторный дисплей СМ-7316, 4096
символов, разрешение 2048?2048;

1979-1984, Институт прикладной физики, серия растровых цветных полутоновых

9

дисплеев “Гамма”. Последние дисплеи данной серии имели таблицу цветности,
поддерживали окна, плавное масштабирование.

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

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

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

В 1990-е годы методы компьютерной графики становятся основным средством
организации диалога “человек-компьютер” и остаются таковыми по настоящее время.

Технические средства поддержки компьютерной графики

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

Возникновение компьютерной графики, как уже говорилось ранее, можно отнести к
50-м годам. Дисплейная графика на первом этапе своего развития использовала
электронно-лучевые трубки (ЭЛТ) с произвольным сканированием луча для вывода в
виде изображения информации из ЭВМ. С эксперимента в Массачусетском
технологическом институте начался этап развития векторных дисплеев (дисплеев с
произвольным сканированием луча).

Самым простым из устройств на ЭЛТ является дисплей на запоминающей трубке с
прямым копированием изображения. Запоминающая трубка обладает свойством
длительного времени послесвечения: изображение остается видимым в течение
длительного времени (до одного часа). При выводе изображения интенсивность
электронного луча увеличивают до уровня, при котором происходит запоминание
следа луча на люминофоре. Сложность изображения практически не ограничена.
Стирание происходит путем подачи на всю трубку специального напряжения, при
котором свечение исчезает, и эта процедура занимает приблизительно 0,5 с. Поэтому
изображения, полученные на экране, нельзя стереть частично, а стало быть,
динамические изображения или анимация на таком дисплее невозможны. Дисплей на
запоминающей трубке является векторным, или дисплеем с произвольным
сканированием, т.е. он позволяет провести отрезок из одной адресуемой точки в
любую другую. Его достаточно легко программировать, но уровень интерактивности у

10