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

Д. В. МОРОХИН 

 
 
 
 
 

ОСНОВНЫЕ АЛГОРИТМЫ  

КОМПЬЮТЕРНОЙ ГРАФИКИ 

 
 
 

Лабораторный практикум 

 

 

 

 

 
 

 
 

Йошкар-Ола 

2017 

УДК 004.9 (07) 
ББК  32.972.13я7 
         М 80 
           
 
 

Рецензенты: 

генеральный директор ООО Компания «Цитрус»,  

кандидат технических наук А. В. Егошин; 

 

доцент кафедры ПиП ЭВС ПГТУ, 

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

 
 

Печатается по решению 

редакционно-издательского совета ПГТУ 

 
 
 
 
 
 

Морохин, Д. В. 

Основные алгоритмы компьютерной графики: лабораторный 

практикум / Д. В. Морохин. – Йошкар-Ола: Поволжский государственный технологический университет, 2017. – 60 с. 
ISBN 978-5-8158-1819-4 

 
Рассмотрены принципы организации и методика разработки программ 

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

Для магистрантов направления 09.04.01 «Информатика и вычислитель
ная техника». 

 

УДК 004.9 (07) 

ББК  32.972.13я7 

 

ISBN 978-5-8158-1819-4
© Морохин Д. В., 2017
© Поволжский государственный 
технологический университет, 2017

М 80

ОГЛАВЛЕНИЕ 

 

Предисловие ................................................................................................ 4 

Введение ...................................................................................................... 5 

Правила техники безопасности  
при выполнении лабораторных работ ....................................................... 6 

Лабораторная работа № 1.  
АФФИННЫЕ ПРЕОБРАЗОВАНИЯ НА ПЛОСКОСТИ ......................... 8 

Контрольные вопросы ............................................................................. 18 

Лабораторная работа № 2.  
ГЕНЕРАЦИЯ ВЕКТОРОВ И ОКРУЖНОСТЕЙ ................................... 19 

Контрольные вопросы ............................................................................. 28 

Лабораторная работа № 3.  
МЕТОДЫ ЗАКРАСКИ ОБЪЕКТОВ ...................................................... 29 

Контрольные вопросы ............................................................................. 37 

Лабораторная работа № 4.  
МЕТОДЫ ОТСЕЧЕНИЯ ОБЪЕКТОВ ................................................... 39 

Контрольные вопросы ............................................................................. 56 

Заключение ............................................................................................... 57 

Список литературы .................................................................................. 58 

 

ПРЕДИСЛОВИЕ 

 

Цель лабораторных занятий по дисциплине «Компьютерная гра
фика» – закрепление студентами знаний, полученных на лекциях. 

При подготовке практикума были использованы некоторые кон
цептуальные моменты, изложенные в работах [2] и [4]. 

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

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

Лабораторный практикум предназначен для самостоятельной и 

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

ВВЕДЕНИЕ 

 

Известно, что информация, представленная в визуальной форме, 

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

Описание, конструирование, манипулирование и представление 

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

Современная машинная графика – это тщательно разработанная 

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

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

ПРАВИЛА ТЕХНИКИ БЕЗОПАСНОСТИ 

ПРИ ВЫПОЛНЕНИИ ЛАБОРАТОРНЫХ РАБОТ 
 

1. Общие требования безопасности. 
Опасные производственные факторы: воздействие на человека 

электрического тока, электрического поля, рентгеновского излучения, ультрафиолетового излучения. 

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

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

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

3. Требования безопасности во время работы. 
3.1. Необходимо соблюдать оптимальное расстояние от глаз до 

экрана монитора (60-70 см). При меньшем расстоянии глаза 
быстро утомляются. 

3.2. При работе на ПК следует сидеть прямо, с небольшим 

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

3.3. При внезапном отключении электроэнергии в сети выклю
чить ПК. 

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

3.5. Оптимальное время непрерывной работы на компьютере 

40-50 минут. По истечении этого времени необходимо сделать перерыв на 10 минут. 

3.6. Суммарное время работы за дисплеем ПК в течение рабо
чего дня не должно превышать 4 часов. 

4. Требования безопасности при аварийной обстановке. 
4.1. Необходимо выключить ПК. 
4.2. Нельзя пользоваться ПК до полного устранения неисправ
ности. 

4.3. При получении травмы и внезапном заболевании следует 

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

5. Требования безопасности по окончании работы. 
5.1. Необходимо выключить ПК. 
5.2. Обо всех замечаниях и недостатках в работе ПК следует 

сообщить преподавателю или дежурному лаборанту. 

 
 

Лабораторная работа № 1 

 

АФФИННЫЕ ПРЕОБРАЗОВАНИЯ НА ПЛОСКОСТИ 

 
 

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

 

Т Е О Р Е Т И Ч Е С К И Е  С В Е Д Е Н И Я  

 

Основные преобразования 

К операциям геометрических преобразований двухмерных (плос
ких) графических объектов относят: 

 перенос начала координат,  
 изменение масштаба изображения, 
 поворот осей координат. 
1. Рассмотрим преобразование переноса на плоскости. На рис. 1.1 

точка А перенесена в точку В. 

 

Рис. 1.1. Операция переноса точки A в точку B 

Математически этот перенос можно описать с помощью вектора 

переноса. Пусть R  – радиус-вектор, соответствующий вектору пере
носа AB . Тогда переход из точки А в точку В будет соответствовать 

векторной записи 
R
A
B


. Отсюда получаем, что для переноса 

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

 



z
z
y
y
x
х
R
A
R
A
R
A
R
A
B






,
,
. 

 

2. Масштабированием объектов называется растяжение объектов 

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

 

Рис. 1.2. Операция масштабирования 

После применения операции однородного масштабирования с ко
эффициентом 2 треугольник ABC переходит в треугольник A′B′C′. 

Обозначим матрицу масштабирования 











y

x

S

S

S
0

0

. Для точек A и 

A′ операция масштабирования в матричном виде будет выглядеть следующим образом: 


 













y

x

S

S

y
x
y
x
0

0

,
'
,'
 . 

 
3. Рассмотрим далее операцию вращения (поворота) точки на не
который угол относительно начала координат. На рис. 1.3 точка 



y
x
A
,

 переходит в точку 


y
x
B



,
 поворотом на угол α.  

Найдем преобразование координат точки А в точку В. Обозначим 

ß угол, который составляет радиус-вектор A  с осью Оx. Пусть r – 

длина радиус-вектора A , тогда 



















sin
sin
cos
cos
cos
'
r
r
x
; 



















sin
cos
cos
sin
sin
'
r
r
y
. 

 

Рис. 1.3. Операция поворота точки A на угол α 

Так как 
r
x/
cos 

 и 
r
y /
sin


, то подставляя эти выражения в 

уравнения для x′ и y′, получаем  

;
sin
cos
'






y
x
x
 

.
cos
sin
'






y
x
y
 

В матричном виде вращение точки А на угол α выглядит следую
щим образом:  
 
 


 

.
cos
sin

sin
cos
,
'
,'
















y
x
y
x
 

 

Однородные координаты и матричное  

представление двумерных преобразований 

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

Двумерный вектор (x,y) в однородных координатах записывается 

в виде (wx,wy,w), где w не равно 0. Число w называется масштабным 
множителем. Для того чтобы из вектора, записанного в однородных