Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Практикум по ИТ.doc
Скачиваний:
46
Добавлен:
17.03.2015
Размер:
3 Мб
Скачать
☆

Лабораторная работа № 3:

"Простейший алгоритм построения отрезка и окружности. Алгоритм Брезенхема для построения отрезка и окружности"

Математические основы

Экран дисплея - это экран растрового дисплея. Экран - это решетка с практически невидимыми глазу отдельными ячейками. Ячейки решётки называются пикселами. Очевидно, что чем меньше ячейка ( пиксел ), тем более чётким получается изображение. Принято говорить не о размере решётки или размере пиксела, а о разрешении экрана. Разрешение экрана - это количество пикселов на экране. Например, разрешение экрана может быть 640 х 480 пикселов, 1024 х 768 пикселов и т.д.

Для того, чтобы на экране появилось какое-либо изображение, надо определённым цветом высветить определённый набор пикселов. То есть ответить на вопросы:

Где на экране высветить пиксел ( то есть где на экране поставить точку ) ?

Каким цветом высветить этот пиксел?

Какие пикселы высветить, чтобы получить требуемое изображение?

Рис. 1 Построение растрового изображения на экране дисплея

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

Рис.2 Выбор пикселов при построении отрезка на экране .

Существуют алгоритмы ( и появляются новые ) рисования отрезков. Естественно, что все эти алгоритмы - разные, но есть несколько правил, общих для всех алгоритмов:

  1. Отрезки должны начинаться и заканчиваться в заданных точках.

  2. Отрезки должны выглядеть прямыми .

  3. Яркость вдоль отрезка должна быть постоянной, не зависеть от длины и наклона.

  4. Рисовать надо быстро, чтобы глаза воспринимали отрезок как единое целое, а не как цепочку бегущих пикселов.

Простейший алгоритм построения отрезка

Рассмотрим задачу построения отрезка на растровой плоскости, соединяющего точки P(x1, y1) и Q(x2, y2). Зеркальным отображением мы всегда сможем добиться, чтобы

Это несколько упростит нашу задачу.

Существует несколько подходов, зависящих от представления отрезка. Мы можем использовать математическое задание:

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

Алгоритм Брезенхема для построения отрезка.

Каждый пиксел имеет 8 соседей N, NE, NW, W, E, SE, SW, S. Предположим, что во время построения отрезка, мы поставили некоторую точку M (x,y). Тогда следующим мы поставим либо E либо NE пиксел. Как определить, какой из двух вариантов наиболее точно будет продолжать линию? Это можно определить с помощью срединной точки (рис.1) Если отрезок проходит выше срединной точки, то следующим ставится NE пиксел, иначе, если отрезок проходит ниже срединной точки, то ставится E пиксел. Сделать это математически поможет формула отрезка в неявно заданном виде:

F(x,y)=0 – значит точка (x,y) лежит на отрезке

F(x,y)<0 – выше отрезка

F(x,y)>0 – ниже отрезка

Предположим, мы поставили точку P. тогда координаты срединной точки будут

А значение функции F в этой точке

Если следующим поставленным пикселем будет E, тогда значение функции в новой срединной точке будет:

Вслучае NE:

Рассмотрим начальную точку (x1,y1):

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

Единственная неприятность – деление на 2 в первом d. Получившееся значение скорее всего будет вещественным и потребует использование вещественных операций. Однако от этого можно избавиться, использовав следующее преобразование:

Тогда все d становятся целыми

Для построения произвольного отрезка перед построением необходимо проверить угол наклона и провести соответствующую зеркальную симметрию:

Если 0<=x2-x1<=y2-y1 то меняем местами x и y координаты.

Если тангенс угла наклона меньше 0, то отражаем относительно оси ординат x=-x а затем, если это необходимо, меняем x и y координаты.

Некоторые дополнительные вопросы построения отрезка

Порядок конечных точек

Одна из сложностей, возникающих по ходу построения отрезка, заключается в том, что отрезок от Т1 до Т2 должен содержать те же самые пикселы, что и отрезок Т2 – Т1, для того, чтобы представление линии было независимо от порядка задания концов. Единственный случай, в котором выбор пиксела зависит от направления построения линии, это прохождение отрезка точно через срединную точку, т.е. когда индикатор d равен нулю. Строя линию слева направо мы выберем пиксел E, а в противном случае пиксел W, но он же расположен на единичку выше первого! А значит, при построении линии справа налево необходимо в случае d=0 выбирать SW – пиксел.

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

Построение отрезка в случае отсечения (клипирования)

Некоторая модификация алгоритма необходима для поддержки отсечения. На рисунке (a) показан отрезок, отсекаемый по левой границе клипирующего прямоугольника (x =min x). Точка пересечения с границей имеет целую x координату, но вещественную y. Пиксел - тот же самый, который был бы выведен в отсутствии отсечения. Однако, приняв этот пиксел в качестве начального, нам необходимо соответствующим образом инициализировать индикатор по следующей срединной точке. Это требуется для получения правильной растеризации. В противном случае она была бы отлична от ожидаемой, ведь наклон нового отрезка от до (x,y) не совпадает с наклоном исходного .

Еще более сложная ситуация представлена на рисунке (b) при пересечении отрезка с горизонтальной границей. Нам бы хотелось, чтобы были выведены все точки, соответствующие границе. Однако при простом вычислении точки пересечения отрезка и границы будет поставлена в качестве первой точка A, а не B. Из рисунка видно, что первая точка, которую необходимо поставить – это ближайшая справа к точке пересечения отрезка с горизонталью. Значит, для правильного отсечения по нижней границе достаточно найти точку пересечения с линиейи округлить значение x. Таким образом, первый пиксел B будет расположен в.