[Описание] Алгоритм Брезенхэма.

Различные алгоритмы, связанные с выводом графики.
Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16478
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

[Описание] Алгоритм Брезенхэма.

Сообщение Хакер » 28.12.2007 (Пт) 18:32

Алгоритм Брезенхэма (назван в честь автора этого алгоритма, Джека Е. Брезенхэма) - алгоритм, имеющий очень широкое применение. Этот алгоритм позволяет определеить оптимальное равное распределение (отношение) элементов можнества M к элементам множеству Z.

Бытовым примером применения этого алгоритма может послужить ситуация, когда у вас имеется 4 вазы и 10 яблок, и вам нужно разложить яблоки таким образом, чтобы вазы содержали примерно равное число яблок.

Этот алгоритм применим всегда, когда требуется распределить m сущностей по n группам, причём m / n - нецелое число (т.е. задачу нельзя решить, просто посчитав, сколько сущностей должно оказаться в каждой группе и разделив их).

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

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

Стало быть, для того чтобы изобразить наклонную линию необходимо составить её из множества горизонтальных или вертикальных (в зависимости от угла наклона) линий.

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

Нам необходимо всего-лишь определить, когда должен произойти излом горизонтального отрезка, т.е. когда отрезок должен перейти на один пиксел вниз.

Для этого введём такое понятия как фактор ошибки (или фактор погрешности). Фактор ошибки - это число, показывающие, насколько точка горизонтального ряда пикселов (т.е. горизонтального отрезка) отстаёт от соответствующей ей точки настоящего (идеального отрезка).

Горизонтальные ряды пикселов расположены на одинаковом расстоянии друг от друга по вертикали - на расстоянии в 1 пиксел. Таким образом идеальная линия может быть либо ближе к какой верхнему ряду (фактор ошибки < 0.5), либо быть между рядами (фактор ошибки = 0.5), либо быть ближе к нижнему ряду (фактор ошибки > 0.5).

Так, отслеживая изменения фактора ошибки, мы можем точно определить момент, когда линия должна уйти на один пиксел вниз. Это должно произойти когда фактор ошибки дойдёт до 0.5 .

Изображение

На рисунке выше красным цветом показан идеальный отрезок. Синими линиями показаны ряды пикселов, которые должны быть закрашены, а залётным цветом показаны моменты, когда фактор ошибки достигает переломного числа (>0.5).

На VB реализация этого алгоритма будет выглядеть так:

Код: Выделить всё
Public Sub DrawLine(ByVal XFrom As Long, ByVal YFrom As Long, ByVal XTo As Long, ByVal YTo As Long)
    Dim x                       As Long
    Dim y                       As Long
    Dim ErrorFactor             As Double
    y = YFrom
    For x = XFrom To XTo
        DrawPoint x, y
        ErrorFactor = CDbl((YTo - YFrom)) / CDbl(XTo - XFrom) * (x - XFrom) - (y - YFrom)
        If ErrorFactor >= 0.5 Then
            y = y + 1
        End If
    Next x
End Sub


Однако, эта реализация неоптимальна. Инструкция, производящая расчёт фактора ошибки подлежит значительной оптимизации.

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

С учётом этого, код функции примет такой вид:
Код: Выделить всё
Public Sub DrawLine(ByVal XFrom As Long, ByVal YFrom As Long, ByVal XTo As Long, ByVal YTo As Long)
    Dim x                       As Long
    Dim y                       As Long
    Dim ErrorFactor             As Double
    Dim ErrorIncrement          As Double
    ErrorIncrement = CDbl(YTo - YFrom) / CDbl(XTo - XFrom)
    y = YFrom
    For x = XFrom To XTo
        DrawPoint
        ErrorFactor = ErrorFactor + ErrorIncrement
        If ErrorFactor > 0.5 Then
            y = y + 1
            ErrorFactor = ErrorFactor - 1
        End If
    Next x
End Sub


Здесь, когда фактор ошибки достигает критического значения, координата y увеличивается на 1, а фактор ошибки уменьшается на 1, т.к. ряд теперь стал ниже на 1 пиксел.

Но и этот код можно оптимизировать :) Дело в том, что вычисления с дробными числами (а именно такими у нас являются ErrorFactor и ErrorIncrement) протекают дольше, чем с целыми числами. Поэтому, попытаемся превратить наши ErrorFactor и ErrorIncrement в целые.

Как известно, если равные между собой X и Y умножит на некоторое Z, XZ и YZ будут также равны. Воспользуемся этим :)

Для начала умножим ErrorFactor и 0.5 на 2. Тогда 0.5 обратиться в единицу - от одного дробного числа мы уже избавились.

У нас остались ErrorIncrement и ErrorFactor. Итак, если ErrorFactor производится ErrorIncrement-ом, поэтому, если мы сделаем ErrorIncrement целым, ErrorFactor тоже станет целым.

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

Тогда код примет следующий вид:

Код: Выделить всё
Public Sub DrawLine(ByVal XFrom As Long, ByVal YFrom As Long, ByVal XTo As Long, ByVal YTo As Long)
    Dim x                       As Long
    Dim y                       As Long
    Dim ErrorFactor             As Long
    Dim ErrorIncrement          As Long
    Dim DeltaX                  As Long
    ErrorIncrement = YTo - YFrom
    DeltaX = XTo - XFrom
    y = YFrom
    For x = XFrom To XTo
        DrawPoint x, y
        ErrorFactor = ErrorFactor + ErrorIncrement
        If 2 * ErrorFactor > DeltaX Then
            y = y + 1
            ErrorFactor = ErrorFactor - DeltaX
        End If
    Next x
End Sub


Всё, все переменные лонговые. Код должен работать очень быстро.

Важно заметить, что наш код умеет рисовать только наклонные линии (для вертикальных или горизонтальных должен быть devision by zero или overflow). Чтобы создать функцию, которая рисовала бы любые линии, нужно написать переходник к этой - она должна менять либо менять один из знаков, либо менять x, y местами, либо менять начальные и конечные координаты, либо рисовать строго горизонтальные или вертикальные линии.

Недостатоком алгоритма Брезенхэма является то, что линии получаются грубыми, угловатыми (эффект алиасинга). Чтобы нарисовать сглаженную линию нужно использовать алгоритм Ву.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Вернуться в Графика

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

    TopList