Алгоритм брезенхема – предпосылки-1

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

Прежде всего, он предложил строить отрезок всегда в первом октанте, где последовательность пикселов получается сплошная всегда. Расположение отрезков во всех других октантах можно легко получить отражениями.

Предпосылки-2

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

То есть в цикле построения пикселов отрезка выбор происходит (см рисунок выше) всегда ТОЛЬКО МЕЖДУ точкой T и точкой S. По сути достаточно отслеживать знак отклонения точки пересечения идеальной прямой от точки 0,5 на следующей вертикали. Изложенное позволило Брезенхему предложить такой целочисленный алгоритм растеризации, который называется его именем:

В современных видеоконтроллерах этот алгоритм реализован аппаратно.

Проблемы яркости отрезка

Приведенная картинка показывает, что наклон отрезка приводит к его различной визуальной яркости.

Ясно, что нужны какие-то средства компенсации вредного влияния «ступенчатости» отрезка , т.н. алиасинга.

Компенсация алиасинга яркостью

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

Растеризация окружности – подходы

Свой подход к построению инкрементных алгоритмов растеризации Брезенхем распространил и на дуги окружностей.

Растеризуется дуга, расположенная только и исключительно во втором октанте, где касательная к любой точке дуги окружности ориентирована под углом от 0 до -45 градусов, что важно для построения алгоритма.

Остальные дуги строятся отражениями.

Алгоритм Брезенхема для ОКРУЖНОСТИ (идея)

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

Выбор по-прежнему сводится к выбору между точками T и S.

Если анализировать Δ=(0,5 – e), то построении цепочки пикселов сводится к последовательности выборов, зависящих ТОЛЬКО ОТ ЗНАКА Δ! Целочисленный алгоритм Брезенхема для дуг также «зашит» в аппаратуру видеоконтроллеров.

Заливка областей постоянным цветом

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

Классификация областей

1 - ПО СВЯЗНОСТИ

Связность – характеристика области, основанная на том, какие из соседних пикселов для каждого данного пиксела считаются СОСЕДНИМИ. Возможны два варианта:

2 – По тому, как определена ВНУТРЕННОСТЬ ОБЛАСТИ

У внутренне-определенных областей задается цвет пикселов области, он одинаков. При переходе по области встреча пиксела с любым другим цветом означает, что достигнута граница области. Естественно, границу области могут составлять пикселы разного цвета, лишь бы он не совпадал с цветом области.

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