Алгоритмы вычерчивания отрезков прямых

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

Методические рекомендации к лабораторным работам

Для студентов специальности 1-53 01 02 «Автоматизированные системы обработки информации» и направлениям подготовки

Информатика и вычислительная техника»,

Программная инженерия»

Дневной и заочной форм обучения

Могилев 2018

УДК 621.01

ББК  36.4

К 87

 

Рекомендовано к изданию

учебно-методическим отделом

Белорусско-Российского университета

 

 

Одобрено кафедрой «Автоматизированные системы управления»
«06» февраля 2018 г., протокол № 10

 

Составитель канд. техн. наук, доц. А. В. Шилов

Рецензент канд. техн. наук, доц. И. В. Лесковец

Методические рекомендации к курсовому проектированию предназначены для студентов специальности 1-53 01 02 «Автоматизированные системы обработки информации» и направлениям подготовки 09 03 01 «Информатика и вычислительная техника», 09 03 04 «Программная инженерия».

 

 

Учебно-методическое издание

 

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

 

 

Ответственный за выпуск                                                      А. И. Якимов

Технический редактор                                                          С. Н. Красовская

Компьютерная верстка                                                          Н. П. Полевничая

 

Подписано в печать.                                    Формат 60х84/16. Бумага офсетная. Гарнитура Таймс.

Печать трафаретная. Усл. печ. л.    . Уч.-изд. л.             . Тираж 16 экз. Заказ №

 

Издатель и полиграфическое исполнение:

Государственное учреждение высшего профессионального образования

«Белорусско-Российский университет».

Свидетельство о государственной регистрации издателя,

изготовителя, распространителя печатных изданий

№ 1/156 от 24.01.2014

Пр. Мира, 43, 212000, Могилев.

 

© ГУ ВПО «Белорусско-Российский

университет», 2018

Содержание

 

Введение. 4

1 Формирование цветов. Изучение цветовых характеристик. Аддитивная цветовая модель RGB.. 5

2 Алгоритмы вычерчивания отрезков прямых. 7

3 Формирование цветов с помощью дизеринга. 10

4 Алгоритмы вычерчивания окружностей. 13

5 Алгоритмы заполнение многоугольников методом САР. 15

6 Алгоритмы заполнение многоугольников методом заливки. 17

7 Аффинные преобразования. 18

8 Метод Робертса. 20

9 Метод Z буфера. 25

10 Модели отражения света. 27

11 Модель отражения света Гуро. 30

12 Модель отражения света Фонга. 32

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

Приложение А.. 34

 

Введение

 

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

Целью данных методических рекомендаций является приобретение обучающимися знаний в областях геометрического моделирования, свойств геометрических моделей, параметризации моделей, геометрических операций над моделями, алгоритмов визуализации: отсечения, развертки, удаления невидимых линий и поверхностей, закраски; способов создания фотореалистических изображений, основных функциональные возможности современных графических систем, организация диалога в графических системах; классификация и обзор современных графических систем. При этом на практике должны быть получены навыки работы с программными средствами, обеспечивающими: аппаратную реализацию графических функций, ввод и вывод графической информации; преобразование: систем координат, форматов хранения графической информации; разработка «открытых» графических систем; 2-D и 3-D моделирование.

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

Формирование цветов

 

Цель работы: изучение цветовых характеристик и аддитивной цветовой модели RGB.

Эта модель используется для описания цветов, которые получаются с помощью устройств, основанных на принципе излучения. В качестве основных цветов выбран красный (Red), зеленый (Green) и синий (Blue). Иные цвета и оттенки получаются смешиванием определенного количества указанных основных цветов (рисунок 1.1).

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

G зеленый

B синий

R красный

голубой

желтый

пурпурный

белый

 

Рисунок 1.1 – Основные цвета RGB и их смешение

 

Некоторое время спустя, Джемс Максвелл (1831–1879) изготовил первый колориметр, с помощью которого человек мог зрительно сравнивать монохроматический цвет и цвет смешивания в заданной пропорции компонент RGB. Регулируя яркость каждой из смешиваемых компонент, можно добиться уравнивания цветов смеси и монохроматического излучения. Это описывается следующим образом:

 

C = r · R + g · G + b · B,

 

где r, g и b – количество соответствующих основных цветов.

Соотношение коэффициентов r, g и b Максвелл наглядно показал с помощью треугольника, впоследствии названного его именем. Треугольник Максвелла является равносторонним, в его вершинах располагаются основные цвета – R, G и В (рисунок 1.2). Из заданной точки проводятся линии, перпендикулярные сторонам треугольника. Длина каждой линии и показывает соответствующую величину коэффициента r, g или b. Одинаковые значения r = g = b имеют место в центре треугольника и соответствуют белому цвету. Следует также отметить, что некоторый цвет может изображаться как внутренней точкой такого треугольника, так и точкой, лежащей за его пределами. В последнем случае это соответствует отрицательному значению соответствующего цветового коэффициента. Сумма коэффициентов равна высоте треугольника h, а при высоте равной единице h = r + g + b = 1.

 

G

B

R

g

r

b

Рисунок 1.2 – Треугольник Максвелла

 

В качестве основных цветов Максвелл использовал излучения с длинами волн 630, 528 и 457 нм.

К настоящему времени система RGB является официальным стандартом. Решением Международной Комиссии по Освещению (МКО) в 1931 г. были стандартизованы основные цвета, которые было рекомендовано использовать в качестве R, G и В. Это монохроматические цвета светового излучения с длинами волн соответственно: R – 700 нм; G – 546,1 нм; В – 435,8 нм.

Цвет, создаваемый смешиванием трех основных компонент, можно представить вектором в трехмерной системе координат R, G и В, изображенной на рисунке 3 Черному цвету соответствует центр координат – точка О(0, 0, 0). Белый цвет выражается максимальным значением компонент. Пусть это максимальное значение вдоль каждой оси равно единице. Тогда белый цвет – это вектор (1, 1, 1). Точки, лежащие на диагонали куба от черного к белому, соответствуют равным значениям: R = G = В (см. рисунок 1.3). Это градации серого – их можно считать белым цветом различной яркости. Вообще говоря, если все компоненты вектора (r , g , b) умножить на одинаковый коэффициент (k = 0...1), то цвет (k_r , k_g , k_b) сохраняется, изменяется только яркость. Поэтому, для анализа цвета важно соотношение компонент.

 

G

B

R

Черный

Белый

О

 

Рисунок 1.3 – Трехмерные координаты RGB

 

Для того чтобы компьютер имел возможность работать с цветными изображениями, необходимо представлять цвета в виде чисел – кодировать цвет. Для модели RGB каждая из компонент может представляться числами, ограниченными некоторым диапазоном – например, дробными числами от 0 до 1 либо целыми числами от 0 до некоторого максимального значения. В настоящее время достаточно распространенным является формат True Color, в котором каждая компонента представлена в виде байта, что дает 256 градаций для каждой компоненты: R = 0...255, G = 0...255, В = 0...255. Количество цветов составляет 256 × 256 × 256 = 16,7 млн.

Такой способ кодирования цветов можно назвать компонентным. В компьютере коды изображений True Color представляются в виде троек байтов, либо упаковываются в длинное целое (четырехбайтное) – 32 бита (так, на пример, сделано в API Windows):

 

С = 00000000 bbbbbbbb gggggggg rrrrrrrr.

 

Практическое задание

Разработать программу, которая формирует треугольник Максвелла.

Содержание отчета: блок-схема разработанной программы; краткие ответы на вопросы, приведенные в таблице 1.1; распечатка листа Excel с результатами.

 

Таблица 1.1 – Вопросы для защиты

 

Вопрос	Рейтинг
Дать определение термину «Растр»	1
Геометрические характеристики растра	1
Оценка разрешающей способности растра	1
Аддитивная цветовая модель RGB	1
Формирование треугольника Максвелла	2
Трехмерные координаты RGB	1
Соотношение для перекодирования цвета из модели CMY в RGB	1
Компонентный способ кодирования цветов	1
Коды изображений True Color	1
Функция VBA RGB	1

 

Алгоритмы вычерчивания отрезков прямых

 

Цель работы: изучение алгоритма Брезенхема для вычерчивания отрезков.

Одним из методов разложения отрезка в растр является алгоритм Брезенхема. Этот алгоритм определяет, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Большее из приращений, либо Δx, либо Δy, выбирается в качестве единицы растра. В процессе работы одна из координат (в зависимости от углового коэффициента) изменяется на единицу. Изменение другой координаты (на 0 или 1) зависит от расстояния между действительным положением отрезка и ближайшими координатами сетки. Такое расстояние мы назовем ошибкой.

Алгоритм построен так, что требуется проверять лишь знак этой ошибки. Из рисунка 2.1 можно заметить, что если угловой коэффициент отрезка из точки с координатами (0, 0) больше чем 1/2, то его пересечение с прямой х = 1 будет расположено ближе к прямой y = 1, чем к прямой y = 0. Следовательно, точка растра (1, 1) лучше аппроксимирует ход отрезка, чем точка (1, 0). Если угловой коэффициент меньше 1/2, то верно обратное. Для углового коэффициента, равного 1/2, нет какого-либо предпочтительного выбора. В данном случае алгоритм выбирает точку (1, 1).

 

 

Рисунок 2.1 – Основная идея алгоритма Брезенхема

 

Так как желательно проверять только знак ошибки, то она первоначально устанавливается равной –1/2. Таким образом, если угловой коэффициент отрезка больше или равен 1/2, то величина ошибки в следующей точке растра может быть вычислена как е = –1/2 + Δy/Δx. Недостаток такого вычисления ошибки в том, что она требует использования арифметики с плавающей точкой и деления для вычисления углового коэффициента. Быстродействие алгоритма можно увеличить, если использовать только целочисленную арифметику и исключить деление.

Не все отрезки проходят через точки растра, поэтому рассмотрим пример, где отрезок с тангенсом угла наклона 3/8 сначала проходит через точку растра (0, 0) и последовательно пересекает три пиксела (рисунок 2.2, а).

Результаты вычисления ошибки при представлении отрезка дискретными пикселами иллюстрируются рисунком 2.2, б. Так как желательно проверять только знак ошибки, то она первоначально устанавливается равной –1/2. Таким образом, если угловой коэффициент отрезка больше или равен 1/2, то величина ошибки в следующей точке растра с координатами (1,0) может быть вычислена как

 

е₁ = е₀ + m,

 

где m – угловой коэффициент.

а)

б)

Рисунок 2.2 – Изображение отрезка в растре при его построении методом Брезенхема (а) и график ошибки (б)

 

В нашем случае при начальном значении ошибки –1/2

 

е₁ = –1/2+ 3/8 = –1/8.

 

Так как е отрицательно, отрезок пройдет ниже середины пиксела. Следовательно, пиксел на том же самом горизонтальном уровне лучше аппроксимирует положение отрезка, поэтому у не увеличивается. Аналогично вычисляем ошибку в следующей точке растра (2, 0)

 

е₂ = –1/8 + 3/8 = –1/4.

 

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

е'₂ = 1/4 – 1 = –3/4.

 

Заметим, что пересечение вертикальной прямой х = 2 с заданным отрезком лежит на 1/4 ниже прямой y = 1. Если же перенести отрезок 1/2 вниз, мы получим как раз величину –3/4. Продолжение вычислений для следующего пиксела дает

 

e₃ = –3/4 + 3/8 = –3/8.

 

Так как e отрицательно, то у не увеличивается. Из всего сказанного следует, что ошибка – это интервал, отсекаемый по оси у рассматриваемым отрезком в каждом растровом элементе (относительно –1/2).

Практическое задание

 

Разработать программу для отображения объекта № 1.

Содержание отчета: блок-схема данной программы; краткие ответы на вопросы, приведенные в таблице 2.1; распечатка листа Excel с результатами.

 

Таблица 2.1 – Вопросы для защиты

 

Вопрос	Рейтинг
Записать рекуррентное соотношение для последовательных значений по методу ЦДА	1
Алгоритм формирования отрезка методом ЦДА	1
Представить график ошибки в алгоритме Брезенхема	1
Как изменяется величина ошибки при закрашивании пиксела по оси Х	1
Как изменяется величина ошибки при закрашивании пиксела по оси Y	1
Пояснить схему алгоритма построения отрезка методом Брезенхема	2