Алгоритм брезенхема построения окружности


Алгоритм Брезенхема для генерации окружности

Что-то не получается, кто может помочь?
(Данный алгоритм также является целочисленным. В соответствии с ним полагается, что генерируется окружность с целочисленным радиусом R и центром в точке (x = 0, y = 0) (что всегда можно сделать, связав координаты x и y с координатной сеткой растра простым преобразованием координат). Изначально пошагово строится четверть окружности в первом квадранте. Причем ее построение начинается в точке (x = 0, y = R) и осуществляется в направлении по часовой стрелке. )

08.12.2014, 20:35

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

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

Алгоритм Брезенхема
Сегодня дали задание реализовать процедуру рисования линии используя SetPixel. Дали алгоритм.

Графика (алгоритм Брезенхема)
Необходимо написать программу в которой реализовать алгоритм Брезенхема для построения отрезка.

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

Алгоритм Брезенхема для генерации окружности

Дата добавления: 2013-12-23 ; просмотров: 3536 ; Нарушение авторских прав

В растр нужно разлагать не только линейные, но и другие, более сложные функции.

Для того чтобы нарисовать окружность необходимо сгенерировать только 1/8 часть. Остальные ее части могут быть получены последовательными отражениями. Если сгенерирован первый октант (от 0 до 45° против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой y=x, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой x=0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой y=0 для завершения построения полной окружности (рис.4).

Рис.4. Генерация окружности

Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат (рис.5). Заметим, что если работа алгоритма начинается в точке x=0, y=R, то при генерации окружности по часовой стрелке в первом квадранте y является монотонно убывающей функцией аргумента x. Аналогично, если исходной точкой является точка x=R, y=0, то при генерации окружности против часовой стрелки x будет монотонно убывающей функцией аргумента y.

Предположим, что центр окружности и начальная точка находятся точно в точках растра, выберем для нашего случая генерацию по часовой стрелке с началом в точке x=0, y=R.

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

Разность между квадратами расстояний от центра окружности до диагонального пикселя ( ) и от центра до точки на окружности R 2 равна

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

При d 0, расстояние до горизонтального пикселя ( ) больше. Таким образом:

— при d£0 выбираем в точке ( ),

— при d>0 выбираем в точке ( ),

— при d=0, когда расстояние от окружности до обоих пикселов одинаково, выбираем горизонтальный шаг.

Если >0, то диагональная точка ( ) находится вне окружности. В данной ситуации ясно, что должен быть выбран либо пиксель ( ), т.е. , либо ( ), т.е. . Далее проверяется разность между квадратом расстояний от окружности до диагонального пикселя и вертикального пикселов, т.е.

При 0 расстояние от окружности до диагонального пикселя больше и следует выбрать вертикальное движение к пикселю ( ). Таким образом:

— при £0 выбираем в ( ),

— здесь в случае =0, т.е. когда расстояния равны, выбран диагональный шаг.

Подведем итог полученных результатов:

0 выбираем пиксель ( ) à ,

£0 выбираем пиксель ( ) à ,

>0 выбираем пиксель ( ) à ,

=0 выбираем пиксель ( ) à ,

Легко разработать простые рекуррентные соотношения для реализации пошагового алгоритма. Сначала рассмотрим горизонтальный шаг к пикселю ( ). Обозначим это новое положение пикселов (i+1). Тогда координаты нового пикселя и значение равны:

Аналогично координаты нового пикселя и значение для шага к пикселю ( ) таковы:

То же самое для шага к пикселю ( ) :

Выполняя частные алгебраические преобразования и используя метод Брезенхема, получим следующий алгоритм:

Procedure Mich_Circle (radius; color: integer);

Процедура CirclePoint имеет вид:

Procedure CirclePoint (x,y,color: integer);

PutPixel (y,-x, color);

PutPixel (-x,-y, color);

PutPixel (x,-y, color);

PutPixel (-y,-x, color);

PutPixel (-y,x, color);

PutPixel (-x,y, color)

| следующая лекция ==>
Общий алгоритм Брезенхема | Групповое кодирование

Не нашли то, что искали? Google вам в помощь!

Алгоритм Брезенхема для генерации круга

В растр нужно разлагать не только линейные, но и другие, более сложные функции. Разложению конических сечений, т.е. окружностей, эллипсов, парабол, гипербол, было посвящено значительное число работ. Наибольшее внимание, разумеется, уделено кругу. Один из наиболее эффективных и простых для понимания алгоритмов генерации окружности принадлежит Брезенхему. Для начала заметим, что необходимо сгенерировать только одну восьмую часть окружности. Другие его части могут быть получены последовательными отражениями, как это показано на рис. 5.1. Если сгенерированный первый октант (от 0 до 45 ° против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой y = х, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой х = 0 для получения соответствующей части окружности во втором квадранте. Верхнее полуокружность отражается относительно прямой y = 0 для завершения построения. На рис. 7 приведены двумерные матрицы соответствующих преобразований.

Рис. 7. Генерация полного круга с дуги в первом октанте

Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат. Заметим, что если работа алгоритма начинается в точке х = 0, у = R, то при генерации окружности по часовой стрелке в первом квадранте в является монотонно убывающей функцией аргумента х. Аналогично, если исходной точкой является у = 0, х = R, то при генерации окружности против часовой стрелки х будет монотонно убывающей функцией аргумента у. В нашем случае выбирается генерация по часовой стрелке с началом в точке х = 0, у = R. Предполагается, что центр круга и начальная точка находятся точно в точках растра.

Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим приближает круг горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. Эти направления обозначены соответственно MH, MD, MV. Алгоритм выбирает пиксел, для которого минимальный квадрат расстояния между одним из этих положений и кругом, то есть минимум с

Разница между квадратами расстояний от центра окружности до диагонального пиксела (Xи +1, вi -1) и от центра до точки на окружности R 2 равна

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

При d 0, расстояние до горизонтального пиксела больше. Таким образом,

При d = 0, когда расстояние от круга до обоих пикселов одинакова, выбираем горизонтальный шаг.

Количество вычислений, необходимых для оценки величины d, можно сократить, если заметить, что в случае 1

Дополнение до полного квадрата члена (Yи) 2 с помощью сложения и вычитания — 2Yи + 1 дает


В квадратных скобках стоит по определению Dи и его подстановка

значительно упрощает выражение.

Рассмотрим случай 2, заметим, что здесь должен быть избранным горизонтальный пиксел (Xи +1, вi), так как в является монотонно убывающей функцией. Проверка компонентов d показывает, что

    I +1) 2 + (уI) 2 -R 2 2 + (уя -1) 2 -R 2 0, то диагональная точка (Xи +1, вi -1) находится вне круга, то есть это случаи 3 и 4. В данной ситуации ясно, что нужно выбрать пиксел (Xи +1, вi -1), или (Xи, вi -1). Аналогично рассмотрения предыдущего случая критерий выбора можно получить, рассматривая сначала случай 3 и проверяя разность между квадратами расстояний от окружности до диагонального M D и вертикального M V пикселей, то есть

При d’ 0 расстояние от окружности до диагонального пиксела больше и следует выбрать вертикальное движение к пиксела (Xи, вi -1). Таким образом, при d’ 0 выбираем MV (Xи, вi -1).

Здесь для случая d ‘ = 0, т.е. когда расстояния равны, выбран диагональный шаг.

Проверка компонентов d ‘ показывает, что

Дополнение до полного квадрата члена (Xи) 2 с помощью добавления и вычитания 2xи +1 дает

Использование определения D и приводит выражение к виду

Теперь, рассматривая случай 4, снова заметим, что следует выбрать вертикальный пиксел (Xи, вi-1), так как y является монотонно убывающей функцией от х.

Проверка компонентов d’ для случая 4 показывает, что

Поскольку оба пиксела находятся вне круга. Итак, d’ > 0 и при использовании критерия, разработанного для случая 3, происходит верный выбор MV.

Осталось проверить только случай 5, который встречается, когда диагональный пиксел (Xи +1, вi -1) лежит на окружности, то есть Dи = 0. Проверка компонентов d показывает, что

Итак, d> 0 и выбирается диагональный пиксел (Xи +1, вi -1). Аналогичным образом оцениваем компоненты d’:

  • я 1) 2 + (уя -1) 2 -R 2 = 0
  • я +1) 2 + (уя -1) 2 -R 2 0. Подведем итог полученных результатов:

Легко разработать простые рекуррентные соотношения для реализации пошагового алгоритма. Сначала рассмотрим горизонтальный шаг M H к пиксела (X и +1, в i). Обозначим это новое положение пиксела как (i +1). Тогда координаты нового пиксела и значение D и уровне

Аналогично координаты нового пиксела и значение Dи для шага MD к пиксела (Xи +1, вi -1) таковы:

Реализация алгоритма Брезенхема на псевдокоде для круга приводится ниже.

Пошаговый алгоритм Брезенхема для генерации окружности в первом квадранте все переменные — целые инициализация переменных

если Dя = 0, то 20

определение случая 1 или 2

определение случая 4 или 5

Переменная границы устанавливается в ноль для окончания работы алгоритма на горизонтальной оси, в результате генерируется круг в первом квадранте. Если необходим только один из октантов, то второй октант можно получить с помощью установки Предел = Integer (R / sqrt (2)), а первый — за счет отражения второго октанта относительно прямой у = х (рис. 6). Блок-схема алгоритма показана на рис. 8.

Рис. 8. Блок-схема пошагового алгоритма Брезенхема для генерации окружности в первом квадранте

Рассмотрим окружность радиусом 8 с центром в начале координат. Генерируется только первый квадрант.

Алгоритм Брезенхема

Алгоритм Брезенхема выбирает оптимальные растровые координаты для представления отрезка. В процессе работы одна из координат — либо x, либо у (в зависимости от углового коэффициента) — изменяется на единицу. Изменение другой координаты (либо на нуль, либо на единицу) зависит от расстояния между действительным положением отрезка и ближайшими координатами сетки. Такое расстояние называется ошибкой.

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

else

инициализация с поправкой на половину пиксела

for i = 1 to x

Plot (x ,y)

While ( 0)

If Обмен = 1 then

if Обмен = 1 then

next i

Этот алгоритм удовлетворяет самым строгим требованиям. Он имеет приемлемую скорость и может быть легко реализован на аппаратном или микропрограммном уровне.

2.4 Алгоритм Брезенхема для генерации окружностей

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

Брезенхему. Для начала заметим, что необходимо сгенерировать только одну восьмую часть окружности. Остальные её части могут быть получены последовательными отражениями. Если сгенерирован первый октант (от 0 до 45 против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой у = x, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой x = 0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой у = 0 для завершения построения. На рис.2.3. приведены двумерные матрицы соответствующих преобразований.

Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат. Заметим, что если работа алгоритма начинается в точке x = 0, у = R, то при генерации окружности по часовой стрелке в первом квадранте у является монотонно убывающей функцией аргумента x. Аналогично, если исходной точкой является y = 0, x = R, то при генерации окружности против часовой стрелки x будет монотонно убывающей функцией аргумента у. В нашем случае выбирается генерация по часовой стрелке с началом в точке x = 0, у = R. Предполагается, что центр окружности и начальная точка находятся точно в точках растра. Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим образом приближающий окружность: горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. Эти направления обозначены соответственно mH, mD, mV. Алгоритм выбирает пиксел, для которого минимален квадрат расстояния между одним из этих пикселов и окружностью, т. е. минимум из

Вычисления можно упростить, если заметить, что в окрестности точки (xi, yi) возможны только пять типов пересечений окружности и сетки растра. Разность между квадратами расстояний от центра окружности до диагонального пиксела (xi + 1, yi 1) и от центра до точки на окружности R 2 равна

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

При 0, расстояние до горизонтального пиксела (mH) больше. Таким образом,

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

Количество вычислений, необходимых для оценки величины , можно сократить, если заметить, что в случае 1

так как диагональный пиксел (xi + 1, уi — 1) всегда лежит внутри окружности, а горизонтальный (xi + 1, уi) — вне ее. Таким образом, можно вычислить по формуле

Дополнение до полного квадрата члена (yi) 2 с помощью добавления и вычитания — 2уi + 1 дает

В квадратных скобках стоит по определению i, и его подстановка

существенно упрощает выражение.

Рассмотрим случай 2 на рис.2.6 и заметим, что здесь должен быть выбран горизонтальный пиксел (xi + 1, уi), так как у является монотонно убывающей функцией. Проверка компонент показывает, что

поскольку в случае 2 горизонтальный (xi + 1, уi) и диагональный (xi + 1, уi — 1) пикселы лежат внутри окружности. Следовательно, 0, то диагональная точка (xi + 1, уi — 1) находится вне окружности, т. е. это случаи З и 4 на рис.2.6. В данной ситуации ясно, что должен быть выбран либо пиксел (xi + 1, уi — 1), т. е. mD, либо (xi, уi — 1), т. е. mV. Аналогично разбору предыдущего случая критерий выбора можно получить, рассматривая сначала случай З и проверяя разность между квадратами расстояний от окружности до диагонального mD и вертикального mV пикселов, т. е.

При > 0 расстояние от окружности до диагонального пиксела больше и следует выбрать вертикальное движение к пикселу (xi, уi — 1). Таким образом,

при показывает, что

поскольку для случая З диагональный пиксел (xi + 1, уi — 1) находится вне окружности, тогда как вертикальный пиксел (xi, уi — 1) лежит внутри ее. Это позволяет записать в виде

Дополнение до полного квадрата члена (xi) 2 с помощью добавления и вычитания 2xi + 1 дает

Использование определения i приводит выражение к виду


Теперь, рассматривая случай 4, снова заметим, что следует выбрать вертикальный пиксел (xi, уi — 1), так как y является монотонно убывающей функцией при возрастании x. проверка компонент для случая 4 показывает, что

поскольку оба пиксела находятся вне окружности. Следовательно, > 0 и при использовании критерия, разработанного для случая 3, происходит верный выбор mV.

Осталось проверить только случай 5 на рис.2.7, который встречается, когда диагональный пиксел (xi + 1, уi — 1) лежит на окружности, т. е. i = 0. Проверка компонент показывает, что

Следовательно, > 0 и выбирается диагональный пиксел (xi + 1, уi — 1). Аналогичным образом оцениваем компоненты :

Подведем итог полученных результатов:

Легко разработать простые рекуррентные соотношения дня реализации пошагового алгоритма. Сначала рассмотрим горизонтальный шаг mH к пикселу (хi + 1, уi). Обозначим это новое положение пиксела как (i + 1). Тогда координаты нового пиксела и значение i равны

Аналогично координаты нового пиксела и значения i для шага mD к пикселу (хi + 1, уi — 1) таковы:

То же самое для шага mV к (хi, уi — 1)

Реализация алгоритма Брезенхема для окружности приводиться ниже.

Пошаговый алгоритм Брезенхема для генерации окружности в первом квадранте

все переменные целые

if yi Предел then 4

выделение случая 1 или 2, 4 или 5, или 3

if i 0 then 3

if i = 0 then 20

определение случая 1 или 2

if 0 then 10

if > 0 then 20

определение случая 4 или 5

if 0 then 20

if > 0 then 30

Алгоритм брезенхема построения окружности

Отрезок проводится между двумя точками — и , где в этих парах указаны колонка и строка, соответственно, номера которых растут вправо и вниз. Сначала мы будем предполагать, что наша линия идёт вниз и вправо, причём горизонтальное расстояние превосходит вертикальное , то есть наклон линии от горизонтали — менее 45°. Наша цель состоит в том, чтобы для каждой колонки x между и , определить, какая строка y ближе всего к линии, и нарисовать точку .

Общая формула линии между двумя точками:

Поскольку мы знаем колонку , то строка получается округлением к целому следующего значения:

Однако, вычислять точное значение этого выражения нет необходимости. Достаточно заметить, что уменьшается от и за каждый шаг мы добавляем к единицу и добавляем к значение наклона (в нашем случае значение наклона будет отрицательным числом)

которое можно вычислить заранее. Более того, на каждом шаге мы делаем одно из двух: либо сохраняем тот же y, либо уменьшаем его на 1.

Что из этих двух выбрать — можно решить, отслеживая значение ошибки, которое означает — вертикальное расстояние между текущим значением y и точным значением y для текущего x. Всякий раз, когда мы увеличиваем x, мы увеличиваем значение ошибки на величину наклона s, приведённую выше. Если ошибка превысила 0.5, линия стала ближе к следующему y, поэтому мы уменьшаем y на единицу, одновременно уменьшая значение ошибки на 1. В реализации алгоритма, приведённой ниже, plot(x,y) рисует точку, а abs возвращает абсолютную величину числа:

Проблема такого подхода — в том, что с вещественными величинами, такими как error и deltaerr , компьютеры работают относительно медленно. Кроме того, при вычислениях с плавающей точкой может накапливаться ошибка. По этим причинам, лучше работать только с целыми числами. Это можно сделать, если умножить все используемые вещественные величины на deltax . Единственная проблема — с константой 0.5 — но в данном случае достаточно умножить обе части неравенства на 2. Получаем следующий код:

Умножение на 2 для целых чисел можно реализовать битовым сдвигом влево. Однако, если число отрицательное, при сдвиге пропадёт бит знака.

Теперь мы можем быстро рисовать линии, направленные вправо-вниз с величиной наклона меньше 1. Осталось распространить алгоритм на рисование во всех направлениях. Это достигается за счёт зеркальных отражений, то есть заменой знака (шаг в 1 заменяется на −1), обменом переменных x и y, обменом координат начала отрезка с координатами конца.

6. Основные расчетные соотношения и алгоритм Брезенхема для генерации окружности.

  1. Ввод исходных данных R (радиус окружности) и при необходимости Xc,Yc (координаты центра окружности).
  2. Задание начальных значений текущих координат пиксела X=0, Y=R, параметра D=2(1-R), установка конечного значения ординаты пиксела Yk=0.
  3. Высвечивание текущего пиксела (X,Y).
  4. Проверка окончания работы: если Y 0, то переход к п.7.
  5. Вычисление параметра D1=2D+2Y-1 и анализ полученного значения:
    • если D1 0, то переход к п.9.
  6. Вычисление параметра D2=2D-2X-1 и анализ полученного значения:
    • если D2 0, то переход к п.10.
  7. Вычисление новых значений X и D (горизонтальный шаг): X=X+1; D=D+2X+1. Переход к п.3.
  8. Вычисление новых значений X,Y и D (диагональный шаг): X=X+1; Y=Y-1; D=D+2(X-Y+1). Переход к п.3.
  9. Вычисление новых значений Y и D (вертикальный шаг): Y=Y-1; D=D-2Y+1. Переход к п.3.
  10. Конец.

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

Сложно сегодня найти человека, который бы не сталкивался с машинной графикой в тех или иных проявлениях. Если человек начинает интересоваться алгоритмами, лежащими в её основе, то одними из первых будут алгоритмы Брезенхема. Беда лишь в том, что мне до сих пор не попадалось простого и вразумительного описания этих алгоритмов, а уж тем более — реализации. В этой статье я попытаюсь по возможности просто рассказать о семействе алгоритмов Брезенхема, а также приведу готовый к использованию код на JavaScript, который практически не отличается от кода на C/C++ . Код можно брать и использовать, предварительно написав автору благодарственное письмо.

Хотелось бы выразить свои глубокие и искренние чувства к разработчикам стандартов www и тем, кто их реализует. Вариант JavaScript-кода, работающий во всех доступных броузерах, т.е. IE 6.0, NN 7.0 и Opera 6.0x, не отличается красотой и изысканностью. Впрочем, «к науке, которую я в настоящий момент представляю, это отношения не имеет».

Итак, назначение алгоритмов Брезенхема — нарисовать линию на растровом устройстве, как правило, на мониторе. Как можно видеть на рисунке 1, не все пиксели, входящие в изображение линии, лежат на этой линии, то есть задача алгоритма — найти наиболее близкие пиксели. Главное достоинство алгоритма Брезенхема в том, что в нём не используется в цикле дорогостоящая операция умножения. Алгоритм подходит для прямых или кривых второго порядка*. Существуют модификации алгоритма для четырёхсвязной (т.е. соседними считаются точки, отличающиеся на 1 по одной координате) и восьмисвязной (т.е. соседними считаются точки, обе координаты которых отличаются не больше, чем на 1) линий. Здесь приведён второй вариант — более сложный, но и дающий лучший результат.

Основная идея алгоритма в том, что линия, которую надо нарисовать, делит плоскость на две части. Уравнение кривой записывается в виде Z = f (x,y) . Во всех точках кривой Z = 0 , в точках, лежащих над кривой Z > 0 , а в точках под кривой Z 1 . Отнеся отрезок к одной из групп, мы можем поменять местами координаты концов так, чтобы горизонтальные отрезки всегда рисовались слева направо, а вертикальные — сверху вниз.

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

Если координаты концов отрезка (x 1 ,y 1) и (x 2 ,y 2) соответственно, то при каждом шаге по оси x Z изменяется на 1, а по оси y — на (x 2 -x 1)/(y 2 -y 1) . Чтобы не связываться с делением и остаться в пределах целочисленной арифметики, переменную Z будем изменять соответственно на y2-y1 и x2-x1 . Вот, собственно, и вся математика, остальное можно понять из кода.

Рисование окружности

Алгоритм рисования дуги останется за рамками статьи, а вот алгоритм для рисования окружности получился значительно проще, чем для прямой. Связано это со многими причинами.

Во-первых, мы рисуем только одну восьмую часть окружности — от π/2 до π/4 , причём в обратном направлении, то есть по часовой стрелке. Вся остальная окружность получается путём отражения этой части относительно центра окружности, горизонтальной и вертикальной осей, а также прямых y = x + b и y = -x + b , проходящих через центр окружности.

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

Допустимые шаги — вправо и вправо-по диагонали, а изменение Z зависит от значений x и y , но зависимость линейная, поэтому операция умножения не требуется.

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

Если хотите увидеть демонстрацию работы алгоритмов в окне броузера, включите JavaScript!

Полезен материал? Поделись:
x1: y1:
x2: y2:
x0: y0:
R:

На что вы сейчас смотрите? Если вы не из параллельной вселенной, где все сидят за векторными мониторами, то перед вами растровое изображение. Поглядите на эту полоску: /. Если придвинуться поближе к монитору, то можно увидеть пиксельные ступеньки, которые пытаются притвориться векторной линией. Для этой цели существует целая куча всевозможных алгоритмов растеризации, но я бы хотел рассказать об алгоритме Брезенхема и алгоритме У, которые находят приближение векторного отрезка в растровых координатах.

С проблемой растеризации мне довелось столкнуться во время работы над процедурным генератором планов зданий. Мне нужно было представить стены помещения в виде ячеек двумерного массива. Похожие задачи могут встретиться в физических расчётах, алгоритмах поиска пути или расчёте освещения, если используется разбиение пространства. Кто бы мог подумать, что знакомство с алгоритмами растеризации однажды может пригодиться?

Принцип работы алгоритма Брезенхема очень простой. Берётся отрезок и его начальная координата x . К иксу в цикле прибавляем по единичке в сторону конца отрезка. На каждом шаге вычисляется ошибка — расстояние между реальной координатой y в этом месте и ближайшей ячейкой сетки. Если ошибка не превышает половину высоты ячейки, то она заполняется. Вот и весь алгоритм.

Это была суть алгоритма, на деле всё выглядит следующим образом. Сначала вычисляется угловой коэффициент (y1 — у0)/(x1 — x0) . Значение ошибки в начальной точке отрезка (0,0) принимается равным нулю и первая ячейка заполняется. На следующем шаге к ошибке прибавляется угловой коэффициент и анализируется её значение, если ошибка меньше 0.5 , то заполняется ячейка (x0+1, у0) , если больше, то заполняется ячейка (x0+1, у0+1) и из значения ошибки вычитается единица. На картинке ниже жёлтым цветом показана линия до растеризации, зелёным и красным — расстояние до ближайших ячеек. Угловой коэффициент равняется одной шестой, на первом шаге ошибка становится равной угловому коэффициенту, что меньше 0.5 , а значит ордината остаётся прежней. К середине линии ошибка пересекает рубеж, из неё вычитается единица, а новый пиксель поднимается выше. И так до конца отрезка.

Ещё один нюанс. Если проекция отрезка на ось x меньше проекции на ось y или начало и конец отрезка переставлены местами, то алгоритм не будет работать. Чтобы этого не случилось, нужно проверять направление вектора и его наклон, а потом по необходимости менять местами координаты отрезка, поворачивать оси, и, в конечном итоге, сводить всё к какому-то одному или хотя бы двум случаям. Главное не забывать во время рисования возвращать оси на место.

Для оптимизации расчётов, применяют трюк с умножением всех дробных переменных на dx = (x1 — x0) . Тогда на каждом шаге ошибка будет изменяться на dy = (y1 — y0) вместо углового коэффициента и на dx вместо единицы. Также можно немного поменять логику, «передвинуть» ошибку так, чтобы граница была в нуле, и можно было проверять знак ошибки, это может быть быстрее.

Примерно так может выглядеть код для рисования растровой линии по алгоритму Брезенхема. Псевдокод из Википедии переделанный под C#.

vo > Math.Abs(x1 — x0); // Проверяем рост отрезка по оси икс и по оси игрек // Отражаем линию по диагонали, если угол наклона слишком большой if (steep) < Swap(ref x0, ref y0); // Перетасовка координат вынесена в отдельную функцию для красоты Swap(ref x1, ref y1); >// Если линия растёт не слева направо, то меняем начало и конец отрезка местами if (x0 > x1) < Swap(ref x0, ref x1); Swap(ref y0, ref y1); >int dx = x1 — x0; int dy = Math.Abs(y1 — y0); int error = dx / 2; // Здесь используется оптимизация с умножением на dx, чтобы избавиться от лишних дробей int ystep = (y0 = y) < DrawPoint(x + x0, y + y0); DrawPoint(y + x0, x + y0); DrawPoint(-x + x0, y + y0); DrawPoint(-y + x0, x + y0); DrawPoint(-x + x0, -y + y0); DrawPoint(-y + x0, -x + y0); DrawPoint(x + x0, -y + y0); DrawPoint(y + x0, -x + y0); y++; if (radiusError Math.Abs(x1 - x0); if (steep) < Swap(ref x0, ref y0); Swap(ref x1, ref y1); >if (x0 > x1) < Swap(ref x0, ref x1); Swap(ref y0, ref y1); >DrawPoint(steep, x0, y0, 1); // Эта функция автоматом меняет координаты местами в зависимости от переменной steep DrawPoint(steep, x1, y1, 1); // Последний аргумент — интенсивность в долях единицы float dx = x1 — x0; float dy = y1 — y0; float gradient = dy / dx; float y = y0 + gradient; for (var x = x0 + 1; x = 0.5


error:= error — 1.0

Пусть начало отрезка имеет координаты (X 1 ,Y 1), а конец(X 1 ,X 2) . Обозначим

Dx=(X 2 -X 1),dy=(Y 2 -Y 1) . Не нарушая общности, будем считать, что начало отрезка совпадает с началом координат, и прямая имеет вид

Где. Считаем что начальная точка находится слева. Пусть на (i-1) -м шаге текущей точкой отрезка является P i -1 =(r,q) . Выбор следующей точки S i или T i зависит от знака разности (s-t). Если (s-t) =0>

While x Math.Abs(x1 — x0); // Проверяем рост отрезка по оси икс и по оси игрек // Отражаем линию по диагонали, если угол наклона слишком большой if (steep) < Swap(ref x0, ref y0); // Перетасовка координат вынесена в отдельную функцию для красоты Swap(ref x1, ref y1); >// Если линия растёт не слева направо, то меняем начало и конец отрезка местами if (x0 > x1) < Swap(ref x0, ref x1); Swap(ref y0, ref y1); >int dx = x1 — x0; int dy = Math.Abs(y1 — y0); int error = dx / 2; // Здесь используется оптимизация с умножением на dx, чтобы избавиться от лишних дробей int ystep = (y0 = y) < DrawPoint(x + x0, y + y0); DrawPoint(y + x0, x + y0); DrawPoint(-x + x0, y + y0); DrawPoint(-y + x0, x + y0); DrawPoint(-x + x0, -y + y0); DrawPoint(-y + x0, -x + y0); DrawPoint(x + x0, -y + y0); DrawPoint(y + x0, -x + y0); y++; if (radiusError Math.Abs(x1 - x0); if (steep) < Swap(ref x0, ref y0); Swap(ref x1, ref y1); >if (x0 > x1) < Swap(ref x0, ref x1); Swap(ref y0, ref y1); >DrawPoint(steep, x0, y0, 1); // Эта функция автоматом меняет координаты местами в зависимости от переменной steep DrawPoint(steep, x1, y1, 1); // Последний аргумент — интенсивность в долях единицы float dx = x1 — x0; float dy = y1 — y0; float gradient = dy / dx; float y = y0 + gradient; for (var x = x0 + 1; x конец then 2

Блок-схема алгоритма приводится на рис.3.3. Пример приведен ниже.

Рис. 3.3. Блок-схема алгоритма Брезенхема.

Пример 3.1. Алгоритм Брезенхема.

Рассмотрим отрезок проведенный из точки (0,0) в точку (5,5). Разложение отрезка в растр по алгоритму Брезенхема приводит к такому результату:

Результат показан на рис.3.4 и совпадает с ожидаемым. Заметим, что точка растра с координатами (5,5) не активирована. Эту точку можно активировать путем изменения цикла for-next на 0 to x. Активацию точки (0,0) можно устранить, если поставить оператор Plot непосредственно перед строкой next i.

Рис. 3.4. Результат работы алгоритма Брезенхема в первом октанте.

В следующем разделе описан общий алгоритм Брезенхема.

4. Общий алгоритм Брезенхема.

Чтобы реализация алгоритма Брезенхема была полной необходимо обрабатывать отрезки во всех октантах. Модификацию легко сделатть, учитывая в алгоритме номер квадранта, в котором лежит отрезок и его угловой коэффициепт. Когда абсолютная величина углового коэффициента больше 1, у постоянно изменяется на единицу, а критерий ошибки Брезенхема используется для принятия решения об изменении величины x . Выбор постоянно изменяющейся (на +1 или -1) кооординаты зависит от квадранта (рис.4.1.). Общий алгоритм может быть оформлен в следующем виде:

Обобщенный целочисленный алгоритм Брезенхема квадрантов

предполагается, что концы отрезка (x1,y1) и (x2,y2) не совпадают

все переменные считаются целыми

Sign — функция, возвращающая -1, 0, 1 для отрицательного, нулевого и положительного аргумента соответственно

s1 = Sign (x2 — x1)

s2 = Sign (y2 — y1)

обмен значений x и y в зависимости от углового коэффициента наклона отрезка

Рис.4.1. Разбор случаев для обобщенного алгоритма Брезенхема.

Пример 4.1. обобщенный алгоритм Брезенхема.

Для иллюсрации рассмотрим отрезок из точки (0,0) в точку (-8, -4).

результаты работы пошагового цикла

Рис.4.2. Результат работы обобщенного алгоритма Брезенхема в третьем квадранте.

На рис.4.2 продемонстрирован результат. Сравнение с рис. 2.2 показывает, что результаты работы двух алгоритмов отличаются.

В следующем разделе рассматривается алгоритм Брезенхема для генерации окружности.

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

В растр нужно разлагать не только линейные, но и другие, более сложные функции. Разложению конических сечений, т. е. окружностей, эллипсов, парабол, гипербол, было посвящено значительное число работ. Наибольшее внимание, разумеется, уделено окружности. Один из наиболее эффективных и простых для понимания алгоритмов генерации окружности принадлежит Брезенхему. Для начала заметим, что необходимо сгенерировать только одну восьмую часть окружности. Остальные ее части могут быть получены последовательными отражениями, как это показано на рис. 5.1. Если сгенерирован первый октант (от 0 до 45° против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой у = х, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой х = 0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой у = 0 для завершения построения. На рис. 5.1 приведены двумерные матрицы соответствующих преобразований.

Рис. 5.1. Генерация полной окружности из дуги в первом октанте.

Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат. Заметим, что если работа алгоритма начинается в точке х = 0, у = R, то при генерации окружности по часовой стрелке в первом квадранте у является монотонно убывающей функцией аргументам (рис. 5.2). Аналогично, если исходной точкой является у = 0, х == R, то при генерации окружности против часовой стрелки х будет монотонно убывающей функцией аргумента у. В нашем случае выбирается генерация по часовой стрелке с началом в точке х = 0, у = R. Предполагается, что центр окружности и начальная точка находятся точно в точках растра.

Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим образом приближающий окружность: горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. На рис. 5.3 эти направления обозначены соответственно m H , m D , m V . Алгоритм выбирает пиксел, для которого минимален квадрат расстояния между одним из этих пикселов и окружностью, т. е. минимум из

m H = |(x i + 1) 2 + (y i) 2 -R 2 |

m D = |(x i + 1) 2 + (y i -1) 2 -R 2 |

m V = |(x i) 2 + (y i -1) 2 -R 2 |

Вычисления можно упростить, если заметить, что в окрестности точки (xi,yi,) возможны только пять типов пересечений окружности и сетки растра, приведенных на рис. 5.4.

Рис. 5.4. Пересечение окружности и сетки растра.

Разность между квадратами расстояний от центра окружности до диагонального пиксела (x i , + 1, у i 1) и от центра до точки на окружности R 2 равна

 i = (x i + 1) 2 + (y i -1) 2 -R 2

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

При  i 0, расстояние до горизонтального пиксела больше. Таким образом,

при  0 выбираем m D в (x i , + 1, у i — 1)

При  = 0, когда расстояние от окружности до обоих пикселов одинаковы, выбираем горизонтальный шаг.

Количество вычислений, необходимых для оценки величины , можно сократить, если заметить, что в случае 1

(x i + 1) 2 + (y i) 2 -R 2 >= 0

так как диагональный пиксел (x i , + 1, у i 1) всегда лежит внутри окружности, а горизонтальный (x i , + 1, у i ) вне ее. Таким образом,  можно вычислить по формуле

= (x i + 1) 2 + (y i) 2 -R 2 + (x i + 1) 2 + (y i -1) 2 -R 2

Дополнение до полного квадрата члена (y i) 2 с помощью добавления и вычитания — 2y i + 1 дает

= 2[(x i + 1) 2 + (y i -1) 2 -R 2 ] + 2y i 1

В квадратных скобках стоит по определению  i и его подстановка

существенно упрощает выражение.

Рассмотрим случай 2 на рис. 5.4 и заметим, что здесь должен быть выбран горизонтальный пиксел (x i , + 1, у i), так как.у является монотонно убывающей функцией. Проверка компонент  показывает, что

(x i + 1) 2 + (y i) 2 -R 2 0, то диагональная точка (x i , + 1, у i -1) находится вне окружности, т. е. это случаи 3 и 4 на рис. 5.4. В данной ситуации ясно, что должен быть выбран либо пиксел (x i , + 1, у i -1), либо (x i , у i -1). Аналогично разбору предыдущего случая критерий выбора можно получить, рассматривая сначала случай 3 и проверяя разность между квадратами расстояний от окружности до диагонального m D и вертикального m V пикселов,

т. е. « = |(x i + 1) 2 + (y i -1) 2 -R 2 | — |(x i) 2 + (y i -1) 2 -R 2 |

При« 0 расстояние от окружности до диагонального пиксела больше и следует выбрать вертикальное движение к пикселу (x i , у i -1). Таким образом,

при « 0 выбираем m V в (x i , у i -1)


Здесь в случае « = 0, т. е. когда расстояния равны, выбран диагональный шаг.

Проверка компонент « показывает, что

(x i) 2 + (y i -1) 2 -R 2 >= 0

(x i + 1) 2 + (y i -1) 2 -R 2 0

(x i) 2 + (y i -1) 2 -R 2 > 0

поскольку оба пиксела находятся вне окружности. Следовательно, « > 0 и при использовании критерия, разработанного для случая 3, происходит верный выбор m V .

Осталось проверить только случай 5 на рис. 5.4, который встречается, когда диагональный пиксел (x i , у i -1) лежит на окружности, т. е.  i = 0. Проверка компонент  показывает, что

(x i +1) 2 + (y i) 2 -R 2 > 0

Следовательно,  > 0 и выбирается диагональный пиксел (x i +1 , у i -1) . Аналогичным образом оцениваем компоненты « :

(x i +1) 2 + (y i -1) 2 -R 2 = 0

(x i +1) 2 + (y i -1) 2 -R 2 0. Подведем итог полученных результатов:

 0 выбираем пиксел (x i +1 , у i -1) m D

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

Сложно сегодня найти человека, который бы не сталкивался с машинной графикой в тех или иных проявлениях. Если человек начинает интересоваться алгоритмами, лежащими в её основе, то одними из первых будут алгоритмы Брезенхема. Беда лишь в том, что мне до сих пор не попадалось простого и вразумительного описания этих алгоритмов, а уж тем более — реализации. В этой статье я попытаюсь по возможности просто рассказать о семействе алгоритмов Брезенхема, а также приведу готовый к использованию код на JavaScript, который практически не отличается от кода на C/C++ . Код можно брать и использовать, предварительно написав автору благодарственное письмо.

Хотелось бы выразить свои глубокие и искренние чувства к разработчикам стандартов www и тем, кто их реализует. Вариант JavaScript-кода, работающий во всех доступных броузерах, т.е. IE 6.0, NN 7.0 и Opera 6.0x, не отличается красотой и изысканностью. Впрочем, «к науке, которую я в настоящий момент представляю, это отношения не имеет».

Итак, назначение алгоритмов Брезенхема — нарисовать линию на растровом устройстве, как правило, на мониторе. Как можно видеть на рисунке 1, не все пиксели, входящие в изображение линии, лежат на этой линии, то есть задача алгоритма — найти наиболее близкие пиксели. Главное достоинство алгоритма Брезенхема в том, что в нём не используется в цикле дорогостоящая операция умножения. Алгоритм подходит для прямых или кривых второго порядка*. Существуют модификации алгоритма для четырёхсвязной (т.е. соседними считаются точки, отличающиеся на 1 по одной координате) и восьмисвязной (т.е. соседними считаются точки, обе координаты которых отличаются не больше, чем на 1) линий. Здесь приведён второй вариант — более сложный, но и дающий лучший результат.

Основная идея алгоритма в том, что линия, которую надо нарисовать, делит плоскость на две части. Уравнение кривой записывается в виде Z = f (x,y) . Во всех точках кривой Z = 0 , в точках, лежащих над кривой Z > 0 , а в точках под кривой Z 1 . Отнеся отрезок к одной из групп, мы можем поменять местами координаты концов так, чтобы горизонтальные отрезки всегда рисовались слева направо, а вертикальные — сверху вниз.

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

Если координаты концов отрезка (x 1 ,y 1) и (x 2 ,y 2) соответственно, то при каждом шаге по оси x Z изменяется на 1, а по оси y — на (x 2 -x 1)/(y 2 -y 1) . Чтобы не связываться с делением и остаться в пределах целочисленной арифметики, переменную Z будем изменять соответственно на y2-y1 и x2-x1 . Вот, собственно, и вся математика, остальное можно понять из кода.

Рисование окружности

Алгоритм рисования дуги останется за рамками статьи, а вот алгоритм для рисования окружности получился значительно проще, чем для прямой. Связано это со многими причинами.

Во-первых, мы рисуем только одну восьмую часть окружности — от π/2 до π/4 , причём в обратном направлении, то есть по часовой стрелке. Вся остальная окружность получается путём отражения этой части относительно центра окружности, горизонтальной и вертикальной осей, а также прямых y = x + b и y = -x + b , проходящих через центр окружности.

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

Допустимые шаги — вправо и вправо-по диагонали, а изменение Z зависит от значений x и y , но зависимость линейная, поэтому операция умножения не требуется.

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

Если хотите увидеть демонстрацию работы алгоритмов в окне броузера, включите JavaScript!

x1: y1:
x2: y2:
x0: y0:
R:

Если пространство недискретно, то почему Ахиллес обгоняет черепаху? Если же пространство дискретно, то как частицы реализуют алгоритм Брезенхема?

Я давно задумываюсь над тем, что собою представляет Вселенная в целом и законы её работы в частности. Порою описания некоторых физических явлений на той же Википедии достаточно запутаны, чтобы оставаться непонятными даже для человека, который не шибко далёк от данной области. Тем более не повезло мне подобным — тем, кто от этой области по крайней мере был весьма далёк. Однако, с несколько другой плоскостью — алгоритмами, я, будучи программистом, сталкиваюсь почти ежедневно. И однажды, в процессе реализации некоего подобия 2d-физики в консоли, я подумал: «А ведь Вселенная — это по сути такая же консоль неизвестной размерности. Есть ли причины думать, что для линейного движения на, так сказать, экране этой консоли, частицы не должны реализовывать алгоритм Брезенхема?». И кажется, причин нет.

Всех, кому интересно, что вообще такое алгоритм Брезенхема, как он может быть связан с физикой и как это может повлиять на её интерпретацию — добро пожаловать под кат. Возможно, Вы найдёте там косвенное подтверждение существования параллельных Вселенных. Или даже вложенных друг в друга Вселенных.

Алгоритм Брезенхема

F(x) = x
А теперь представим, что отрезок необходимо повернуть ещё на 10 градусов, например. Тогда мы получим классическую однородную линейную функцию:

F(x) = x * tan(55)
И нарисовать график этой функции обычной ручкой на обычном листке не составит труда для любого ученика 7 класса. Однако что делать в случае с нашим предполагаемым листком бумаги, который дискретен по клеткам? Ведь тогда возникает необходимость выбирать, какие именно клетки закрашивать при рисовании линии. Тут нам на помощь и приходит алгоритм Брезенхема.

Сей аглоритм был разработан Джеком Брезенхемом в 1962 году, когда тот работал в IBM. Он до сих пор используется для реализации виртуальной графики во многих прикладных и системных комплексах, начиная с оборудования на производстве и заканчивая OpenGL. Используя этот алгоритм, можно рассчитать максимально подходящее приближение для заданной прямой при заданном уровне дискретности плоскости, на которой эта прямая располагается.

Реализация на Javascript для общего случая

А теперь представьте, что пространство, которое окружает нас, всё таки дискретно. Причём не важно, заполнено ли оно ничем, частицами, переносчиками, полем Хиггса или ещё чем — есть некое понятие минимального количества пространства, меньше которого ничто не может быть. И не важно, относительно ли оно и верна ли теория относительности касательно него — если пространство искривлено, то локально там, где оно искривлено, оно всё равно будет дискретно, даже если с другой позиции может показаться, будто имело место быть изменение того самого минимального порога в любую сторону. При таком предположении получается, что некое явление, или сущность, или правило, должно реализовывать алгоритм Брезенхема для любого рода движения как частиц материи, так и переносчиков взаимодействий. В какой-то мере это объясняет квантование движения частиц в микромире — они принципиально не могут двигаться линейно, не «телепортируясь» из кусочка пространства в другой кусочек, ибо тогда получится, что пространство вовсе не дискретно.

Ещё одним косвенным подтверждением дискретности пространства может служить суждение, исходящее из вышеописанного: если при определённом уменьшении масштабов наблюдаемого, сие теряет способность быть описанным с помощью евклидовой геометрии, то очевидно, что при преодолении минимального порога расстояния метод геометрического описания субъекта всё равно должен быть. Пусть в такой геометрии одной параллельной прямой может соответствовать более одной другой прямой, проходящей через точку, не принадлежащую исходной прямой, или в такой геометрии вообще нет понятия параллельности прямых или даже вовсе понятия прямых, однако имеет место быть любой, гипотетически представляемый метод описания геометрии объекта меньше минимальной длины. И, как известно, есть одна теория, претендующая на способность описать такую геометрию в пределах известного минимального порога. Это теория струн. Она предполагает существование чего-то , что учёные зовут струнами или бранами, сразу в 10/11/26 измерениях в зависимости от интерпретации и математической модели. Мне лично кажется, что примерно так всё и обстоит и для обоснования своих слов я проведу с Вами мысленный эксперимент: на двумерной плоскости при полной «евклидности» её геометрии работает уже упоминавшееся правило: через одну точку можно провести только одну прямую, параллельную данной. Теперь масштабируем это правило на трёхмерное пространство и получим два из него вытекающих новых правила:

  1. Аналогичное — через одну точку можно провести только одну прямую, параллельную данной
  2. На указанном расстоянии от данной прямой может быть бесконечность-X прямых, и эта бесконечность-X в Y раз меньше бесконечности-Z всех прямых, параллельных данной, независимо от расстояния, где Y — это, грубо говоря, возможное количество толщин прямой в пределах пространства

Говоря проще, если добавить измерение при построении прямых, но не добавлять измерение при расчёте подчинения прямых правилам евклидовой геометрии, то вместо двух возможных параллельных прямых, получим «цилиндр» возможных прямых вокруг центра — исходной прямой. А теперь представьте, будто мы живём в мире Супер Марио и пытаемся спроецировать такой цилиндр на собственное двумерное пространство — по рассчётам параллельных прямых быть не может, но по наблюдениям их целая бесконечность-X. Что мы предположим? Правильно, мы введём ещё одно измерение для построения прямых, но не станем добавлять его для расчёта подчинения прямых правилам евклидовой геометрии. По сути, увидев проекцию такого цилиндра на родное двумерное пространство мы придумаем теорию струн в своём двумерном мире.

Параллельные и вложенные Вселенные?

Иначе говоря, или Ахиллес никогда не догонит черепаху, или мы в Матрице вся обозримая Вселенная и известная физика, скорей всего — лишь капля в огромном океане возможного разнообразия реальности.

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

Рис.1. Разложение в растр отрезков прямых.

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

Постоянная вдоль всего отрезка яркость достигается лишь при проведении горизонтальных, вертикальных и наклоненных под углом 45° прямых. Для всех других ориентаций разложение в растр приведет к неравномерности яркости, как это показано на рис. 1.

В большинстве алгоритмов вычерчивания отрезков для упрощения вычислений используется пошаговый алгоритм. Приведем пример подобного алгоритма:

Простой пошаговый алгоритм

1. if позиция — конец конец then 2

Блок-схема алгоритма приводится на рис.4.

Рис.4. Блок-схема алгоритма Брезенхема.

Пример алгоритма Брезенхема.

Рассмотрим отрезок проведенный из точки (0,0) в точку (5,5). Разложение отрезка в растр по алгоритму Брезенхема приводит к такому результату:

Результат показан на рис.5 и совпадает с ожидаемым. Заметим, что точка растра с координатами (5,5) не активирована. Эту точку можно активировать путем изменения цикла for-next на 0 to x. Активацию точки (0,0) можно устранить, если поставить оператор Plot непосредственно перед строкой next i.

Рис. 5. Результат работы алгоритма Брезенхема в первом октанте.

Общий алгоритм Брезенхема.

Чтобы реализация алгоритма Брезенхема была полной необходимо обрабатывать отрезки во всех октантах. Модификацию легко сделатть, учитывая в алгоритме номер квадранта, в котором лежит отрезок и его угловой коэффициепт. Когда абсолютная величина углового коэффициента больше 1, у постоянно изменяется на единицу, а критерий ошибки Брезенхема используется для принятия решения об изменении величины x . Выбор постоянно изменяющейся (на +1 или -1) кооординаты зависит от квадранта (рис.6.). Общий алгоритм может быть оформлен в следующем виде:

Обобщенный целочисленный алгоритм Брезенхема квадрантов

предполагается, что концы отрезка (x1,y1) и (x2,y2) не совпадают


все переменные считаются целыми

Sign — функция, возвращающая -1, 0, 1 для отрицательного, нулевого и положительного аргумента соответственно

s1 = Sign (x2 — x1)

s2 = Sign (y2 — y1)

обмен значений x и y в зависимости от углового коэффициента наклона отрезка

Рис.6. Разбор случаев для обобщенного алгоритма Брезенхема.

Пример. Обобщенный алгоритм Брезенхема.

Для иллюсрации рассмотрим отрезок из точки (0,0) в точку (-8, -4).

результаты работы пошагового цикла

Рис.7. Результат работы обобщенного алгоритма Брезенхема в третьем квадранте.

На рис. 7 продемонстрирован результат. Сравнение с рис. 5 показывает, что результаты работы двух алгоритмов отличаются.

В следующем разделе рассматривается алгоритм Брезенхема для генерации окружности.

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

В растр нужно разлагать не только линейные, но и другие, более сложные функции. Разложению конических сечений, т. е. окружностей, эллипсов, парабол, гипербол, было посвящено значительное число работ. Наибольшее внимание, разумеется, уделено окружности. Один из наиболее эффективных и простых для понимания алгоритмов генерации окружности принадлежит Брезенхему. Для начала заметим, что необходимо сгенерировать только одну восьмую часть окружности. Остальные ее части могут быть получены последовательными отражениями, как это показано на рис. 8. Если сгенерирован первый октант (от 0 до 45° против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой у = х, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой х = 0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой у = 0 для завершения построения. На рис. 8 приведены двумерные матрицы соответствующих преобразований.

Рис. 8. Генерация полной окружности из дуги в первом октанте.

Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат. Заметим, что если работа алгоритма начинается в точке х = 0, у = R, то при генерации окружности по часовой стрелке в первом квадранте у является монотонно убывающей функцией аргументам (рис. 9). Аналогично, если исходной точкой является у = 0, х = R, то при генерации окружности против часовой стрелки х будет монотонно убывающей функцией аргумента у. В нашем случае выбирается генерация по часовой стрелке с началом в точке х = 0, у = R. Предполагается, что центр окружности и начальная точка находятся точно в точках растра.

Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим образом приближающий окружность: горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. На рис. 10 эти направления обозначены соответственно m H , m D , m V . Алгоритм выбирает пиксел, для которого минимален квадрат расстояния между одним из этих пикселей и окружностью, т. е. минимум из

m H = |(x i + 1) 2 + (y i) 2 -R 2 |

m V = |(x i) 2 + (y i -1) 2 -R 2 |

Вычисления можно упростить, если заметить, что в окрестности точки (xi,yi,) возможны только пять типов пересечений окружности и сетки растра, приведенных на рис. 11.

Рис. 11. Пересечение окружности и сетки растра.

Разность между квадратами расстояний от центра окружности до диагонального пикселя (x i , + 1, у i 1) и от центра до точки на окружности R 2 равна

d i = (x i + 1) 2 + (y i -1) 2 -R 2

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

При d i 0, расстояние до горизонтального пикселя больше. Таким образом,

при d 0 выбираем m D в (x i , + 1, у i — 1)

При e = 0, когда расстояние от окружности до обоих пикселей одинаковы, выбираем горизонтальный шаг.

Количество вычислений, необходимых для оценки величины e, можно сократить, если заметить, что в случае 1

(x i + 1) 2 + (y i) 2 -R 2 >= 0

(x i + 1) 2 + (y i -1) 2 -R 2 0, то диагональная точка (x i , + 1, у i -1) находится вне окружности, т. е. это случаи 3 и 4 на рис. 11. В данной ситуации ясно, что должен быть выбран либо пиксел (x i , + 1, у i -1), либо (x i , у i -1). Аналогично разбору предыдущего случая критерий выбора можно получить, рассматривая сначала случай 3 и проверяя разность между квадратами расстояний от окружности до диагонального m D и вертикального m V пикселей,

т. е. d« = |(x i + 1) 2 + (y i -1) 2 -R 2 | — |(x i) 2 + (y i -1) 2 -R 2 |

При d« 0 расстояние от окружности до диагонального пикселя больше и следует выбрать вертикальное движение к пикселу (x i , у i -1). Таким образом,

при d« 0 выбираем m V в (x i , у i -1)

Здесь в случае d« = 0, т. е. когда расстояния равны, выбран диагональный шаг.

Проверка компонент e« показывает, что

(x i) 2 + (y i -1) 2 -R 2 >= 0

(x i + 1) 2 + (y i -1) 2 -R 2 0

(x i) 2 + (y i -1) 2 -R 2 > 0

поскольку оба пикселя находятся вне окружности. Следовательно, e« > 0 и при использовании критерия, разработанного для случая 3, происходит верный выбор m V .

Осталось проверить только случай 5 на рис. 11, который встречается, когда диагональный пиксел (x i , у i -1) лежит на окружности, т. е. d i = 0. Проверка компонент e показывает, что

(x i +1) 2 + (y i) 2 -R 2 > 0

Следовательно, d > 0 и выбирается диагональный пиксел (x i +1 , у i -1) . Аналогичным образом оцениваем компоненты d« :

(x i +1) 2 + (y i -1) 2 -R 2 = 0

(x i +1) 2 + (y i -1) 2 -R 2 0. Подведем итог полученных результатов:

d 0 выбираем пиксел (x i +1 , у i -1) m D

d« 0 выбираем пиксел (x i , у i -1)- m V

d i = 0 выбираем пиксел (x i +1 , у i -1) — m D

Легко разработать простые рекуррентные соотношения для реализации пошагового алгоритма. Сначала рассмотрим горизонтальный шаг m H к пикселу (x i + 1, у i). Обозначим это новое положение пикселя как (i + 1). Тогда координаты нового пикселя и значение e i равны

d i +1 = (x i +1 +1) 2 + (y i +1 -1) 2 -R 2 dd i + 2x i +1 + 1

Аналогично координаты нового пикселя и значение d i для шага m D к пикселу (x i + 1, у i -1) таковы:

d i+1 = d i + 2x i+1 — 2y i+1 +2

То же самое для шага m V к (x i , у i -1)

d i+1 = d i — 2y i+1 +1

Реализация алгоритма Брезенхема на псевдокоде для окружности приводится ниже.

Пошаговый алгоритм Брезенхема для генерации окружности в первом квадранте

все переменные — целые

1 Plot (x i , y i )


if D i = 0 then 20

определение случая 1 или 2

2 d = 2d i + 2у i — 1

определение случая 4 или 5

3 d = 2D i + 2х i 1

D i = D i + 2х i + 1

D i = D i + 2х i — 2у i + 2

Переменная предела устанавливается в нуль для окончания работы алгоритма на горизонтальной оси, в результате генерируется окружность в первом квадранте. Если необходим лишь один из октантов, то второй октант можно получить с помощью установки Предел = Integer (R/sqrt(2)), а первый — с помощью отражения второго октанта относительно прямой у = х (рис. 8). Блок-схема алгоритма приводится на рис. 12.

Рис. 12. Блок-схема пошагового алгоритма Брезенхема для генерации окружности в первом квадранте.

Кривая Безье и ее геометрический алгоритм.

Кривые Безье были разработаны в 60 – х годах XX века независимо друг от друга Пьером Безье (Bezier) из автомобилестроительной компании «Рено» и Полем де Кастелье (de Casteljau) из компании «Ситроен», где применялись для проектирования кузовов автомобилей.

Несмотря на то, что открытие де Кастелье было сделано несколько ранее Безье (1959), его исследования не публиковались и скрывались компанией как производственная тайна до конца 1960 – х.

Впервые кривые были представлены широкой публике в 1962 году французским инженером Пьером Безье, который, разработав их независимо от де Кастелье, использовал их для компьютерного проектирования автомобильных кузовов. Кривые были названы именем Безье, а именем де Кастелье назван разработанный им рекурсивный способ определения кривых (алгоритм де Кастелье).

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

Кривая Безье – параметрическая кривая, задаваемая выражением

for (i = 0; i конец then 2

Блок-схема алгоритма приводится на рис.3.3. Пример приведен ниже.

Рис. 3.3. Блок-схема алгоритма Брезенхема.

Пример 3.1. Алгоритм Брезенхема.

Рассмотрим отрезок проведенный из точки (0,0) в точку (5,5). Разложение отрезка в растр по алгоритму Брезенхема приводит к такому результату:

Результат показан на рис.3.4 и совпадает с ожидаемым. Заметим, что точка растра с координатами (5,5) не активирована. Эту точку можно активировать путем изменения цикла for-next на 0 to x. Активацию точки (0,0) можно устранить, если поставить оператор Plot непосредственно перед строкой next i.

Рис. 3.4. Результат работы алгоритма Брезенхема в первом октанте.

В следующем разделе описан общий алгоритм Брезенхема.

4. Общий алгоритм Брезенхема.

Чтобы реализация алгоритма Брезенхема была полной необходимо обрабатывать отрезки во всех октантах. Модификацию легко сделатть, учитывая в алгоритме номер квадранта, в котором лежит отрезок и его угловой коэффициепт. Когда абсолютная величина углового коэффициента больше 1, у постоянно изменяется на единицу, а критерий ошибки Брезенхема используется для принятия решения об изменении величины x . Выбор постоянно изменяющейся (на +1 или -1) кооординаты зависит от квадранта (рис.4.1.). Общий алгоритм может быть оформлен в следующем виде:

Обобщенный целочисленный алгоритм Брезенхема квадрантов

предполагается, что концы отрезка (x1,y1) и (x2,y2) не совпадают

все переменные считаются целыми

Sign — функция, возвращающая -1, 0, 1 для отрицательного, нулевого и положительного аргумента соответственно

s1 = Sign (x2 — x1)

s2 = Sign (y2 — y1)

обмен значений x и y в зависимости от углового коэффициента наклона отрезка

Рис.4.1. Разбор случаев для обобщенного алгоритма Брезенхема.

Пример 4.1. обобщенный алгоритм Брезенхема.

Для иллюсрации рассмотрим отрезок из точки (0,0) в точку (-8, -4).

результаты работы пошагового цикла

Рис.4.2. Результат работы обобщенного алгоритма Брезенхема в третьем квадранте.

На рис.4.2 продемонстрирован результат. Сравнение с рис. 2.2 показывает, что результаты работы двух алгоритмов отличаются.

В следующем разделе рассматривается алгоритм Брезенхема для генерации окружности.

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

В растр нужно разлагать не только линейные, но и другие, более сложные функции. Разложению конических сечений, т. е. окружностей, эллипсов, парабол, гипербол, было посвящено значительное число работ. Наибольшее внимание, разумеется, уделено окружности. Один из наиболее эффективных и простых для понимания алгоритмов генерации окружности принадлежит Брезенхему. Для начала заметим, что необходимо сгенерировать только одну восьмую часть окружности. Остальные ее части могут быть получены последовательными отражениями, как это показано на рис. 5.1. Если сгенерирован первый октант (от 0 до 45° против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой у = х, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой х = 0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой у = 0 для завершения построения. На рис. 5.1 приведены двумерные матрицы соответствующих преобразований.

Рис. 5.1. Генерация полной окружности из дуги в первом октанте.

Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат. Заметим, что если работа алгоритма начинается в точке х = 0, у = R, то при генерации окружности по часовой стрелке в первом квадранте у является монотонно убывающей функцией аргументам (рис. 5.2). Аналогично, если исходной точкой является у = 0, х == R, то при генерации окружности против часовой стрелки х будет монотонно убывающей функцией аргумента у. В нашем случае выбирается генерация по часовой стрелке с началом в точке х = 0, у = R. Предполагается, что центр окружности и начальная точка находятся точно в точках растра.

Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим образом приближающий окружность: горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. На рис. 5.3 эти направления обозначены соответственно m H , m D , m V . Алгоритм выбирает пиксел, для которого минимален квадрат расстояния между одним из этих пикселов и окружностью, т. е. минимум из

m H = |(x i + 1) 2 + (y i) 2 -R 2 |

m D = |(x i + 1) 2 + (y i -1) 2 -R 2 |

m V = |(x i) 2 + (y i -1) 2 -R 2 |

Вычисления можно упростить, если заметить, что в окрестности точки (xi,yi,) возможны только пять типов пересечений окружности и сетки растра, приведенных на рис. 5.4.

Рис. 5.4. Пересечение окружности и сетки растра.

Разность между квадратами расстояний от центра окружности до диагонального пиксела (x i , + 1, у i 1) и от центра до точки на окружности R 2 равна

 i = (x i + 1) 2 + (y i -1) 2 -R 2

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

При  i 0, расстояние до горизонтального пиксела больше. Таким образом,

при  0 выбираем m D в (x i , + 1, у i — 1)

При  = 0, когда расстояние от окружности до обоих пикселов одинаковы, выбираем горизонтальный шаг.

Количество вычислений, необходимых для оценки величины , можно сократить, если заметить, что в случае 1

(x i + 1) 2 + (y i) 2 -R 2 >= 0


так как диагональный пиксел (x i , + 1, у i 1) всегда лежит внутри окружности, а горизонтальный (x i , + 1, у i ) вне ее. Таким образом,  можно вычислить по формуле

= (x i + 1) 2 + (y i) 2 -R 2 + (x i + 1) 2 + (y i -1) 2 -R 2

Дополнение до полного квадрата члена (y i) 2 с помощью добавления и вычитания — 2y i + 1 дает

= 2[(x i + 1) 2 + (y i -1) 2 -R 2 ] + 2y i 1

В квадратных скобках стоит по определению  i и его подстановка

существенно упрощает выражение.

Рассмотрим случай 2 на рис. 5.4 и заметим, что здесь должен быть выбран горизонтальный пиксел (x i , + 1, у i), так как.у является монотонно убывающей функцией. Проверка компонент  показывает, что

(x i + 1) 2 + (y i) 2 -R 2 0, то диагональная точка (x i , + 1, у i -1) находится вне окружности, т. е. это случаи 3 и 4 на рис. 5.4. В данной ситуации ясно, что должен быть выбран либо пиксел (x i , + 1, у i -1), либо (x i , у i -1). Аналогично разбору предыдущего случая критерий выбора можно получить, рассматривая сначала случай 3 и проверяя разность между квадратами расстояний от окружности до диагонального m D и вертикального m V пикселов,

т. е. « = |(x i + 1) 2 + (y i -1) 2 -R 2 | — |(x i) 2 + (y i -1) 2 -R 2 |

При« 0 расстояние от окружности до диагонального пиксела больше и следует выбрать вертикальное движение к пикселу (x i , у i -1). Таким образом,

при « 0 выбираем m V в (x i , у i -1)

Здесь в случае « = 0, т. е. когда расстояния равны, выбран диагональный шаг.

Проверка компонент « показывает, что

(x i) 2 + (y i -1) 2 -R 2 >= 0

(x i + 1) 2 + (y i -1) 2 -R 2 0

(x i) 2 + (y i -1) 2 -R 2 > 0

поскольку оба пиксела находятся вне окружности. Следовательно, « > 0 и при использовании критерия, разработанного для случая 3, происходит верный выбор m V .

Осталось проверить только случай 5 на рис. 5.4, который встречается, когда диагональный пиксел (x i , у i -1) лежит на окружности, т. е.  i = 0. Проверка компонент  показывает, что

(x i +1) 2 + (y i) 2 -R 2 > 0

Следовательно,  > 0 и выбирается диагональный пиксел (x i +1 , у i -1) . Аналогичным образом оцениваем компоненты « :

(x i +1) 2 + (y i -1) 2 -R 2 = 0

(x i +1) 2 + (y i -1) 2 -R 2 0. Подведем итог полученных результатов:

 0 выбираем пиксел (x i +1 , у i -1) m D

error:= error — 1.0

Пусть начало отрезка имеет координаты (X 1 ,Y 1), а конец(X 1 ,X 2) . Обозначим

Dx=(X 2 -X 1),dy=(Y 2 -Y 1) . Не нарушая общности, будем считать, что начало отрезка совпадает с началом координат, и прямая имеет вид

Где. Считаем что начальная точка находится слева. Пусть на (i-1) -м шаге текущей точкой отрезка является P i -1 =(r,q) . Выбор следующей точки S i или T i зависит от знака разности (s-t). Если (s-t) =0>

Алгоритм брезенхема построения окружности

Прим. В зависимости от перевода, иногда его называют алгоритм Брезенхема.

Рассмотрим произвольный отрезок p 1 ( x 1 , y 1 ) – p 2 ( x 2 , y 2 ) :

Чтобы растеризовать его можно поступить следующим образом (небольшая модификация алгоритма DDA-линии):

  • посчитаем длины отрезка по осям координат lengthX = | x 2 – x 1 | и lengthY = | y 2 – y 1 | ;
  • выберем большую из них length = max ( lengthX , lengthY ) ;
  • случай length == 0 особый: закрашиваем пиксел ( x 1 , y 1 ) = ( x 2 , y 2 ) и завершаем работу алгоритма;
  • допустим большая длина оказалась lengthX . Установим начальную точку x = x1, y = y1 ;
  • сделаем length + 1 итераций:
    1. закрашиваем пиксел с координатами ( x , roundf ( y )) ;
    2. координата x увеличивается на единицу, координата y увеличивается на lengthY / length X .

Прим. roundf – округление до ближайшего целого.

Прим. Обратите внимание, что | x 2 – x 1 | и | y 2 – y 1 | это расстояния между центрами первого и последнего пикселей.

#define roundf(x) floor(x + 0.5f )

void line(HDC hdc, int x1, int y1, int x2, int y2)
<
int lengthX = abs(x2 — x1);
int lengthY = abs(y2 — y1);

int length = max(lengthX, lengthY);

if (length == 0)
<
SetPixel(hdc, x1, y1, 0);
>

if (lengthY
<
// Начальные значения
int x = x1;
float y = y1;

// Основной цикл
length++;
while (length—)
<
SetPixel(hdc, x, roundf(y), 0);
x++;
y += float (lengthY) / lengthX;
>
>
else
<
// Начальные значения
float x = x 1;
int y = y 1;

// Основной цикл
length ++;
while (length—)
<
SetPixel(hdc, roundf(x), y, 0);
x += float (lengthX) / lengthY;
y++;
>
>
>

При таком подходе x является целочисленной переменной, в то время как y – вещественная. Также заметим, что координата x всегда увеличивается на единицу, хотя x2 может быть меньше x1 . То же замечание относится к координате y .

Итак, приведенный выше алгоритм обладает двумя существенными недостатками:

  1. Он работает только в первой четверти.
  2. Используются вычисления с плавающей точкой.

Распространение алгоритма на всю плоскость

Делений становится меньше

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

Рассмотрим основной цикл. Сначала оптимизируем цикл для случая lengthY lengthX , для другого случая все делается аналогично. Заметим, что изначально y является целой величиной. В цикле y изменяется на дробь со знаменателем lengthX . Т.о. х также является дробью со знаменателем lengthX . Избавимся от знаменателя, домножив на него: // Начальные значения int x = x 1; int y = y 1 * lengthX ; // Основной цикл length++; while (length—) < SetPixel(hdc, x, roundf( float (y) / lengthX), 0); x += dx; y += dy * lengthY; >Увы, но при отрисовке пикселя мы снова должны прибегать к делению. Идея состоит в том, что величина y / lengthX за шаг меняется не более чем на единицу. Разобьем y на целую часть и приращение следующим образом:

y = z + c , где z это y , округленная до ближайшего целого, а с принадлежит отрезку [-0.5; 0.5] . То, что с принадлежит отрезку [-0.5; 0.5] гарантирует нам, что z — это действительно y, округленное до ближайшего целого. Нашей задачей будет поддержание величины c в этих границах. Рассмотрим исходный вариант реализации основного цикла: // Начальные значения int x = x 1; float y = y 1; // Основной цикл length ++; while (length—) < SetPixel(hdc, x, roundf(y), 0); x += dx; y += dy * float (lengthY) / lengthX; >Внесем необходимые изменения: // Начальные значения int x = x 1; int y = y1; float c = 0; // Основной цикл length++; while (length—) < SetPixel(hdc, x, y, 0); x += dx; c += dy * float (lengthY) / lengthX; if (c >0.5) < c--; y++; >if (c c++; y—; > > Чтобы не делать несколько сравнений можно величину с всегда увеличивать в положительную сторону. Тем самым сравнивать придется только с 0.5, но при этом у будет менятся на dy : // Начальные значения int x = x 1; int y = y1; float c = 0; // Основной цикл length++; while (length—) < SetPixel(hdc, x, y, 0); x += dx; c += float (lengthY) / lengthX; if (c >0.5) < c --; y += dy ; >> Начнем избавляться от дробей. Сперва заметим, что можно сделать замену d = 2 * c — 1 , при этом d сравнивается с нулем: // Начальные значения int x = x 1; int y = y1; float d = -1; // Основной цикл length++; while (length—) < SetPixel(hdc, x, y, 0); x += dx; d += 2 * float (lengthY) / lengthX; if (d >0) < d -= 2; y += dy; >>Прим. При линейных заменах ( u = a * v + b ) правила следующие:

  1. Считаем, что замена имеет смысл, т.е. не рассматривются варианты a = 0. Тогда замена обратима:

v = (1 / a) – b / a

  1. Присвоение переменной преобразуется по линейному закону:

v = 2 > u = a * 2 + b

  1. При сравнении переменной, величина, с которой производится сравнение, преобразуется по линейному закону:

v >0.5 > u > a * 0.5 + b

  1. Если v увеличивается на некоторую величину, то u увеличивается на ту же величину, помноженную на a :

v -= 4 > u -= 4 * a;

  1. В остальных ситуациях нужно внимательно следить, чтобы преобразования обоих величин сохраняли линейный закон их соответствия.

Вернемся к алгоритму. Последним штрихом будет применение оптимизации, рассмотренной в начале: // Начальные значения int x = x 1; int y = y1; int d = -lengthX; // Основной цикл length++; while (length—) < SetPixel(hdc, x, y, 0); x += dx; d += 2 * lengthY; if (d >0) < d -= 2 * lengthX; y += dy ; >>

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

Если пространство недискретно, то почему Ахиллес обгоняет черепаху? Если же пространство дискретно, то как частицы реализуют алгоритм Брезенхема?

Я давно задумываюсь над тем, что собою представляет Вселенная в целом и законы её работы в частности. Порою описания некоторых физических явлений на той же Википедии достаточно запутаны, чтобы оставаться непонятными даже для человека, который не шибко далёк от данной области. Тем более не повезло мне подобным — тем, кто от этой области по крайней мере был весьма далёк. Однако, с несколько другой плоскостью — алгоритмами, я, будучи программистом, сталкиваюсь почти ежедневно. И однажды, в процессе реализации некоего подобия 2d-физики в консоли, я подумал: «А ведь Вселенная — это по сути такая же консоль неизвестной размерности. Есть ли причины думать, что для линейного движения на, так сказать, экране этой консоли, частицы не должны реализовывать алгоритм Брезенхема?». И кажется, причин нет.

Всех, кому интересно, что вообще такое алгоритм Брезенхема, как он может быть связан с физикой и как это может повлиять на её интерпретацию — добро пожаловать под кат. Возможно, Вы найдёте там косвенное подтверждение существования параллельных Вселенных. Или даже вложенных друг в друга Вселенных.

Алгоритм Брезенхема

F(x) = x
А теперь представим, что отрезок необходимо повернуть ещё на 10 градусов, например. Тогда мы получим классическую однородную линейную функцию:

F(x) = x * tan(55)
И нарисовать график этой функции обычной ручкой на обычном листке не составит труда для любого ученика 7 класса. Однако что делать в случае с нашим предполагаемым листком бумаги, который дискретен по клеткам? Ведь тогда возникает необходимость выбирать, какие именно клетки закрашивать при рисовании линии. Тут нам на помощь и приходит алгоритм Брезенхема.

Сей аглоритм был разработан Джеком Брезенхемом в 1962 году, когда тот работал в IBM. Он до сих пор используется для реализации виртуальной графики во многих прикладных и системных комплексах, начиная с оборудования на производстве и заканчивая OpenGL. Используя этот алгоритм, можно рассчитать максимально подходящее приближение для заданной прямой при заданном уровне дискретности плоскости, на которой эта прямая располагается.

Реализация на Javascript для общего случая

А теперь представьте, что пространство, которое окружает нас, всё таки дискретно. Причём не важно, заполнено ли оно ничем, частицами, переносчиками, полем Хиггса или ещё чем — есть некое понятие минимального количества пространства, меньше которого ничто не может быть. И не важно, относительно ли оно и верна ли теория относительности касательно него — если пространство искривлено, то локально там, где оно искривлено, оно всё равно будет дискретно, даже если с другой позиции может показаться, будто имело место быть изменение того самого минимального порога в любую сторону. При таком предположении получается, что некое явление, или сущность, или правило, должно реализовывать алгоритм Брезенхема для любого рода движения как частиц материи, так и переносчиков взаимодействий. В какой-то мере это объясняет квантование движения частиц в микромире — они принципиально не могут двигаться линейно, не «телепортируясь» из кусочка пространства в другой кусочек, ибо тогда получится, что пространство вовсе не дискретно.


Ещё одним косвенным подтверждением дискретности пространства может служить суждение, исходящее из вышеописанного: если при определённом уменьшении масштабов наблюдаемого, сие теряет способность быть описанным с помощью евклидовой геометрии, то очевидно, что при преодолении минимального порога расстояния метод геометрического описания субъекта всё равно должен быть. Пусть в такой геометрии одной параллельной прямой может соответствовать более одной другой прямой, проходящей через точку, не принадлежащую исходной прямой, или в такой геометрии вообще нет понятия параллельности прямых или даже вовсе понятия прямых, однако имеет место быть любой, гипотетически представляемый метод описания геометрии объекта меньше минимальной длины. И, как известно, есть одна теория, претендующая на способность описать такую геометрию в пределах известного минимального порога. Это теория струн. Она предполагает существование чего-то , что учёные зовут струнами или бранами, сразу в 10/11/26 измерениях в зависимости от интерпретации и математической модели. Мне лично кажется, что примерно так всё и обстоит и для обоснования своих слов я проведу с Вами мысленный эксперимент: на двумерной плоскости при полной «евклидности» её геометрии работает уже упоминавшееся правило: через одну точку можно провести только одну прямую, параллельную данной. Теперь масштабируем это правило на трёхмерное пространство и получим два из него вытекающих новых правила:

  1. Аналогичное — через одну точку можно провести только одну прямую, параллельную данной
  2. На указанном расстоянии от данной прямой может быть бесконечность-X прямых, и эта бесконечность-X в Y раз меньше бесконечности-Z всех прямых, параллельных данной, независимо от расстояния, где Y — это, грубо говоря, возможное количество толщин прямой в пределах пространства

Говоря проще, если добавить измерение при построении прямых, но не добавлять измерение при расчёте подчинения прямых правилам евклидовой геометрии, то вместо двух возможных параллельных прямых, получим «цилиндр» возможных прямых вокруг центра — исходной прямой. А теперь представьте, будто мы живём в мире Супер Марио и пытаемся спроецировать такой цилиндр на собственное двумерное пространство — по рассчётам параллельных прямых быть не может, но по наблюдениям их целая бесконечность-X. Что мы предположим? Правильно, мы введём ещё одно измерение для построения прямых, но не станем добавлять его для расчёта подчинения прямых правилам евклидовой геометрии. По сути, увидев проекцию такого цилиндра на родное двумерное пространство мы придумаем теорию струн в своём двумерном мире.

Параллельные и вложенные Вселенные?

Иначе говоря, или Ахиллес никогда не догонит черепаху, или мы в Матрице вся обозримая Вселенная и известная физика, скорей всего — лишь капля в огромном океане возможного разнообразия реальности.

Сложно сегодня найти человека, который бы не сталкивался с машинной графикой в тех или иных проявлениях. Если человек начинает интересоваться алгоритмами, лежащими в её основе, то одними из первых будут алгоритмы Брезенхема. Беда лишь в том, что мне до сих пор не попадалось простого и вразумительного описания этих алгоритмов, а уж тем более — реализации. В этой статье я попытаюсь по возможности просто рассказать о семействе алгоритмов Брезенхема, а также приведу готовый к использованию код на JavaScript, который практически не отличается от кода на C/C++ . Код можно брать и использовать, предварительно написав автору благодарственное письмо.

Хотелось бы выразить свои глубокие и искренние чувства к разработчикам стандартов www и тем, кто их реализует. Вариант JavaScript-кода, работающий во всех доступных броузерах, т.е. IE 6.0, NN 7.0 и Opera 6.0x, не отличается красотой и изысканностью. Впрочем, «к науке, которую я в настоящий момент представляю, это отношения не имеет».

Итак, назначение алгоритмов Брезенхема — нарисовать линию на растровом устройстве, как правило, на мониторе. Как можно видеть на рисунке 1, не все пиксели, входящие в изображение линии, лежат на этой линии, то есть задача алгоритма — найти наиболее близкие пиксели. Главное достоинство алгоритма Брезенхема в том, что в нём не используется в цикле дорогостоящая операция умножения. Алгоритм подходит для прямых или кривых второго порядка*. Существуют модификации алгоритма для четырёхсвязной (т.е. соседними считаются точки, отличающиеся на 1 по одной координате) и восьмисвязной (т.е. соседними считаются точки, обе координаты которых отличаются не больше, чем на 1) линий. Здесь приведён второй вариант — более сложный, но и дающий лучший результат.

Основная идея алгоритма в том, что линия, которую надо нарисовать, делит плоскость на две части. Уравнение кривой записывается в виде Z = f (x,y) . Во всех точках кривой Z = 0 , в точках, лежащих над кривой Z > 0 , а в точках под кривой Z 1 . Отнеся отрезок к одной из групп, мы можем поменять местами координаты концов так, чтобы горизонтальные отрезки всегда рисовались слева направо, а вертикальные — сверху вниз.

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

Если координаты концов отрезка (x 1 ,y 1) и (x 2 ,y 2) соответственно, то при каждом шаге по оси x Z изменяется на 1, а по оси y — на (x 2 -x 1)/(y 2 -y 1) . Чтобы не связываться с делением и остаться в пределах целочисленной арифметики, переменную Z будем изменять соответственно на y2-y1 и x2-x1 . Вот, собственно, и вся математика, остальное можно понять из кода.

Рисование окружности

Алгоритм рисования дуги останется за рамками статьи, а вот алгоритм для рисования окружности получился значительно проще, чем для прямой. Связано это со многими причинами.

Во-первых, мы рисуем только одну восьмую часть окружности — от π/2 до π/4 , причём в обратном направлении, то есть по часовой стрелке. Вся остальная окружность получается путём отражения этой части относительно центра окружности, горизонтальной и вертикальной осей, а также прямых y = x + b и y = -x + b , проходящих через центр окружности.

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

Допустимые шаги — вправо и вправо-по диагонали, а изменение Z зависит от значений x и y , но зависимость линейная, поэтому операция умножения не требуется.

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

Если хотите увидеть демонстрацию работы алгоритмов в окне броузера, включите JavaScript!

x1: y1:
x2: y2:
x0: y0:
R:

Значительная часть школьного курса геометрии посвящена задачам на построение. Вопросы, связанные с алгоритмами построения геометрических фигур, интересовали еще математиков древности. Более поздние исследования показали их тесную связь с фундаментальными вопросами математики (достаточно вспомнить классические задачи о трисекции угла и квадратуре круга). Появление ЭВМ поставило перед математиками принципиально новые вопросы, которые не могли возникнуть в докомпьютерную эпоху. К их числу относятся задачи построения элементарных графических объектов — линий и окружностей.

Любая геометрическая фигура может быть определена как некоторое множество точек плоскости. В геометрии это множество, как правило, бесконечно; даже отрезок содержит бесконечно много точек.

В компьютерной графике дело обстоит иначе. Элементарная составляющая всех фигур — точка — обретает реальные физические размеры, а вопросы вида «сколько точек содержит данная фигура?» никого не удивляют. Мы попадаем в конечный мир, где все можно сравнить, измерить, подсчитать. Даже само слово «точка» употребляется редко. Его заменяет термин пиксель (pixel — от picture element — элемент картинки). Если взглянуть на экран дисплея сквозь увеличительное стекло, то можно увидеть, что фрагмент изображения, который невооруженному глазу кажется сплошным, на самом деле состоит из дискретного множества пикселей. Впрочем, на дисплеях с невысокой разрешающей способностью это можно наблюдать и без увеличительного стекла.

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

Имеется и другой аспект проблемы. Допустим, вы хотите съесть яблоко. Имеет ли для вас значение, съедите вы все яблоко целиком или разделите его на 2 половинки и съедите каждую из них отдельно? Скорее всего, если яблоко достаточно вкусное, вы охотно согласитесь на оба варианта. А вот с точки зрения программиста, поделив прекрасное целое яблоко пополам, вы совершаете огромную ошибку. Ведь вместо замечательного целого числа вам приходится иметь дело с двумя дробными, а это значительно хуже. По той же самой причине из двух равенств 1+1=2 и 1,5+0,5=2 программист всегда выберет первое — ведь в нем нет этих непрятных дробных чисел. Такой выбор связан с соображениями повышения эффективности работы программ. В нашем случае, когда речь идет об алгоритмах построения элементарных графических объектов, которые предполагают многократное применение, эффективность является обязательным требованием. Большинство микропроцессоров имеет лишь средства целочисленной арифметики и не располагает встроенными возможностями для операций над вещественными числами. Безусловно, такие операции реализуются, но при этом бывает, что одна операция требует выполнения компьютером до десятка и более команд, что существенным образом влияет на время выполнения алгоритмов.

Статья посвящена рассмотрению одного из шедевров искусства программирования — алгоритму построения окружности, предложенному Брезенхемом (Brezenham). Требуется разработать метод построения окружности на целочисленной координатной сетке по координатам центра и радиусу. Мы должны также максимально сократить время выполнения алгоритма, что заставляет оперировать по возможности целыми числами. Каким графическим инструментарием мы располагаем? Практически никаким. Безусловно, мы должны уметь ставить точку (pixel) в нужном месте экрана. К примеру, языки программирования фирмы Borland содержат процедуру putpixel, с помощью которой можно оставить на экране точку, имеющую нужные координаты и цвет. Цвет для нас значения не имеет, для определенности пусть он будет белым.

1. От чего придется отказаться.

Представим себе, что мы не ограничены в средствах. Что мы не только можем оперировать с дробными числами, но и использовать трансцендентные тригонометрические функции (такое, кстати, вполне возможно на машинах, оснащенных математическим сопроцессором, который берет на себя подобные вычисления). Задача все та же — построить окружность. Что мы станем делать? Вероятно, мы вспомним формулы, параметрически определяющие окружность. Эти формулы достаточно просты и могут быть получены непосредственно из определения тригонометрических функций. Согласно им окружность радиуса R с центром в точке (x 0 , y 0) может быть определена как множество точек M (x , y ), координаты которых удовлетворяют системе уравнений

м x = x 0 + R cos a

Теперь, когда получено рекуррентное выражение для D i +1 через D i , остается получить D 1 (контрольную величину в начальной точке.) Она не может быть получена рекуррентно, ибо не определено предшествующее значение, зато легко может быть найдена непосредственно

D 1 2 = (0+1) 2 +R 2 —R 2 = 1

D 1 = D 1 1 +D 1 2 = 3-2R .

Таким образом, алгоритм построения окружности, реализованный в bres_circle, основан на последовательном выборе точек; в зависимости от знака контрольной величины D i выбирается следующая точка и нужным образом изменяется сама контрольная величина. Процесс начинается в точке (0, r ), а первая точка, которую ставит процедура sim, имеет координаты (xc , yc +r ). При x = y процесс заканчивается.

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

Отрезок проводится между двумя точками — (x0,y0) и (x1,y1), где в этих парах указаны колонка и строка, соответственно, номера которых растут вправо и вниз. Сначала мы будем предполагать, что наша линия идёт вниз и вправо, причём горизонтальное расстояние x1 − x0 превосходит вертикальное y1 − y0, т.е. наклон линии от горизонтали — менее 45°. Наша цель состоит в том, чтобы для каждой колонки x между x0 и x1, определить, какая строка y ближе всего к линии, и нарисовать точку (x,y).

Общая формула линии между двумя точками:

Поскольку мы знаем колонку x, то строка y получается округлением к целому следующего значения:

Однако, вычислять точное значение этого выражения нет необходимости. Достаточно заметить, что y растёт от y0 и за каждый шаг мы добавляем к x единицу и добавляем к y значение наклона

которое можно вычислить заранее. Более того, на каждом шаге мы делаем одно из двух: либо сохраняем тот же y, либо увеличиваем его на 1.

Что из этих двух выбрать — можно решить, отслеживая значение ошибки, которое означает — вертикальное расстояние между текущим значением y и точным значением y для текущего x. Всякий раз, когда мы увеличиваем x, мы увеличиваем значение ошибки на величину наклона s, приведённую выше. Если ошибка превысила 0.5, линия стала ближе к следующему y, поэтому мы увеличиваем y на единицу, одновременно уменьшая значение ошибки на 1. В реализации алгоритма, приведённой ниже, plot(x,y) рисует точку, а abs возвращает абсолютную величину числа:

function line(x0, x1, y0, y1)

int deltax:= abs(x1 — x0)

int deltay:= abs(y1 — y0)

real deltaerr:= deltay / deltax

error:= error + deltaerr

error:= error — 1.0

Пусть начало отрезка имеет координаты (X 1 ,Y 1), а конец(X 1 ,X 2) . Обозначим

Dx=(X 2 -X 1),dy=(Y 2 -Y 1) . Не нарушая общности, будем считать, что начало отрезка совпадает с началом координат, и прямая имеет вид

Где. Считаем что начальная точка находится слева. Пусть на (i-1) -м шаге текущей точкой отрезка является P i -1 =(r,q) . Выбор следующей точки S i или T i зависит от знака разности (s-t). Если (s-t) =0>

While x 0 если точка лежит ниже прямой

  • f(xi,yi) где i – номер отображаемой точки.
  • Таким образом, одним из методов решения того, какая из точек P или Q (см. рисунок) будет отображена на следующем шаге, является сравнение середины отрезка |P-Q| со значением функции f(x,y) . Если значение f(x,y) лежит ниже средней точки отрезка |P-Q| , то следующей отображаемой точкой будет точка P , иначе — точка Q .
    Запишем приращение функции

    После отображения точки с координатами (xi,yi) принимается решение о следующей отображаемой точке. Для этого сравниваются приращения Δx и Δy , характеризующие наличие или отсутствие перемещения по соответствующей координате. Эти приращения могут принимать значения 0 или 1. Следовательно, когда мы перемещаемся от точки вправо,

    когда мы перемещаемся от точки вправо и вниз, то

    когда мы перемещаемся от точки вниз, то

    Нам известны координаты начала отрезка, то есть точки, заведомо лежащей на искомой прямой. Ставим туда первую точку и принимаем f = 0 . От текущей точки можно сделать два шага — либо по вертикали (по горизонтали), либо по диагонали на один пиксель.
    Направление движения по вертикали или горизонтали определяется коэффициентом угла наклона. В случае если угол наклона меньше 45º, и

    |A|
    using namespace std;
    void Brezenhem(char **z, int x0, int y0, int x1, int y1)
    <
    int A, B, sign;
    A = y1 — y0;
    B = x0 — x1;
    if (abs(A) > abs(B)) sign = 1;
    else sign = -1;
    int signa, signb;
    if (A 0)
    <
    f -= B*signb;
    y += signa;
    >
    x -= signb;
    z[y][x] = «*» ;
    >
    else
    <
    do <
    f += B*signb;
    if (f > 0) <
    f -= A*signa;
    x -= signb;
    >
    y += signa;
    z[y][x] = «*» ;
    > while (x != x1 || y != y1);
    >
    >
    int main()
    <
    const int SIZE = 25; // размер поля
    int x1, x2, y1, y2;
    char **z;
    z = new char *;
    for (int i = 0; i > x1;
    cout > y1;
    cout > x2;
    cout > y2;
    Brezenhem(z, x1, y1, x2, y2);
    for (int i = 0; i Рекомендуем почитать

    Илон Маск рекомендует:  Что такое код lstrcat
    Понравилась статья? Поделиться с друзьями:
    Кодинг, CSS и SQL