КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Алгоритмы вывода прямой линии
РАСТРОВЫЕ АЛГОРИТМЫ
Пусть заданы координаты (x1,y1) и (x 2, y 2) концов отрезка прямой линии. Для вывода линии необходимо закрасить в определенный цвет все пикселы вдоль линии. Для того чтобы закрасить каждый пиксел, необходимо знать его координаты. Алгоритм ЦДА. Простейший алгоритм растрового преобразования линейного отрезка известен как алгоритм ЦДА [24]. Этот алгоритм "позаимствован" у специализированных вычислителей - цифровых дифференциальных анализаторов, которые использовались для численного решения систем дифференциальных уравнений. Поскольку прямая описывается дифференциальным уравнением вида dy/dx = m, где m — коэффициент наклона, формирование прямолинейного отрезка есть не что иное, как решение этого простейшего уравнения численным методом. Пусть отрезок задан крайними точками (х1,у1) и (х2,у2) (рис. 9.1).
Рис. 9.1. Прямолинейный отрезок в системе координат
Будем считать, что значения координат округлены до ближайшего целого, т.е. отрезок начинается и заканчивается в центре соответствующего пиксела. Коэффициент наклона отрезка определяется соотношением: . Будем считать, что 0 < т < 1. При других вариантах значения т можно использовать симметричную модификацию алгоритма. В основе алгоритма лежит запись кода цвета в ячейку буфера, представляющую определенный пиксел, по мере того как х изменяется от х1 до х2. Между элементарными приращениями δx и δy координат точки, которая перемещается от начала отрезка к его концу, существует связь: δy = m * δx. Если на каждом шаге увеличивать значение х на 1, т.е. принять δx =1, то координату у отображающей точки нужно увеличить на величину δy=т. Хотя каждое очередное значение х представляет целое число, очередное значение у таковым не является, поскольку m в общем случае — дробь. Поэтому значение у нужно округлить и найти подходящий пиксел, представляющий текущее положение отображающей точки (рис. 9.2).
Рис.9.2. Формирование пикселей при использовании алгоритма ЦДА
Алгоритм Брезенхема рисования линии. Описанный алгоритм ЦЦА при всей его простоте и наглядности обладает одним недостатком – при формировании координат каждой отображающей точки необходимо выполнять сложение действительных чисел. Более простой целочисленный алгоритм предложил Брезенхэм в 1965 году [21, 24]. Как и в алгоритме ЦДА, будем считать, что конечные точки отрезка представлены целочисленными координатами (x1, y1) и (х2, у2), а коэффициент наклона удовлетворяет условию 0 < m < 1. Это условие достаточно критично для работоспособности алгоритма. Суть алгоритма в том, что при построении растрового образа отрезка выбирается пиксел, ближайший по вертикали к соответствующей прямой. Рассмотрим промежуточный шаг растрового преобразования отрезка после того, как будет сформирован пиксел (i + 1/2, j + 1/2) (рис.9.3). Рис.9.3. Алгоритм Брезенхема
Известно, что прямая описывается уравнением: y=тх + h. При х = i + 1/2 прямая проходит от центра пиксела, точки с координатами (i, j+ 1/2), не далее, чем на 1/2 шага между пикселами. В противном случае образ прямой вследствие округления не прошел бы через этот пиксел. При переходе к следующей точке, для которой х = i + 3/2, учитывая ограничения, наложенные на значение коэффициента наклонa, образ отрезка должен пройти либо через пиксел с центром в (i+ 3/2, j+ 1/2), либо через пиксел с центром в (i +3/2, j+ 3/2). Проблема выбора решается с помощью характеристической переменной d = b - a, где а и b расстояния между прямой в точке х=i +3/2 и верхним и нижним пикселами кандидатами (рис. 9.4). Рис. 9.4. Характеристическая переменная алгоритма Брезенхема
Если d отрицательно, прямая проходит ближе к центру нижнего пиксела в качестве следующего пиксела образа отрезка выбирается (i+ 3/2, j+ 1/2). В противном случае выбирается пиксел с центром в (i + 3/2, j + 3/2 ). Можно было бы определить значение d, вычислив у = тх + b, но тогда теряется одно из заявленных достоинств алгоритма – использование только целочисленных операций, поскольку т является действительной дробью. Поэтому, во-первых, операции над числами с плавающей точкой заменяются операциями над числами с фиксированной точкой, а во-вторых, все вычисления выполняются в приращениях. Изменим определение характеристической переменной. Будем использовать . Это изменение не влияет на выбор пикселов-кандидатов, поскольку для принятия решений используется только знак характеристической переменной, а он в новой формулировке будет таким же, как и в прежней. Подставляя в выражение d значения а и b, полученные из уравнения прямой, и принимая во внимание, что , , приходим к выводу, что d принимает только целочисленные значения. Итак, удалось избавиться от операций над действительными числами, но непосредственное вычисление d все же требует большого количества вычислений, хотя и целочисленных. Поэтому несколько изменим подход. Пусть dk — значение d при х = k+ 1/2. Попробуем вычислить dk+i в приращениях относительно dk. Значение приращения будет зависеть от того, выполнялось ли на предыдущем шаге приращение координаты у пиксела. Возможные варианты представлены на рис 9.5.
Рис.9.5. Приращение значений параметров a и b
Для параметров а и b — расстояний между прямой и пикселами-кандидатами — справедливы следующие соотношения: если на предыдущем шаге произошло приращение у, то . В противном случае . Умножив полученные выражения на Δ х, получим, что при переходе к следующему значению х значение d изменяется либо на 2Δ у, либо на 2( Δ у- Δ х). Этот результат можно записать в таком виде:
В результате вычисление каждого очередного пиксела растрового образа отрезка потребует только одной операции сложения целых чисел и анализа знака. Алгоритм настолько эффективен, что в аппаратно он реализован в виде одной инструкции.
Дата добавления: 2015-04-25; Просмотров: 1024; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |