Сложно сегодня найти человека, который бы не сталкивался с машинной графикой в тех или иных проявлениях. Если человек начинает интересоваться алгоритмами, лежащими в её основе, то одними из первых будут алгоритмы Брезенхема. Беда лишь в том, что мне до сих пор не попадалось простого и вразумительного описания этих алгоритмов, а уж тем более — реализации. В этой статье я попытаюсь по возможности просто рассказать о семействе алгоритмов Брезенхема, а также приведу готовый к использованию код на 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 < 0 . Нам известны координаты начала отрезка, то есть точки, заведомо лежащей на искомой кривой. Ставим туда первый пиксель и принимаем Z = 0 . От текущего пикселя можно сделать два шага — либо по вертикали (по горизонтали), либо по диагонали на один пиксель. Конкретные направления шагов выбираются в зависимости от типа линии, которую надо нарисовать. Делая шаг, мы мы вычисляем, как изменятся значение Z:
ΔZ = Z" x Δx + Z" y Δy
При одном из возможных шагов Z растёт, при другом — уменьшается. Каждый шаг выбирается с тем расчётом, чтобы значение Z для нового пикселя было как можно ближе к 0. Таким образом, мы будем двигаться вдоль линии, создавая её изображение.
Рисование отрезка
Сразу договоримся, что алгоритм для прямой не рисует горизонтальные и вертикальные линии. Это связано с тем, что рисование таких линий можно реализовать гораздо более простым способом, часто на уровне BIOS или драйвера.
Оставшиеся отрезки делятся на две группы: горизонтальные и вертикальные. Если представить уравнение прямой в виде y = kx , то горизонтальными считаются отрезки, у которых |k| ≤ 1 , а вертикальными — у которых |k| > 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!
|
|||||||||||||||||||||||||||||||||||||
Алгоритм Брезенхе́ма- это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками.
Отрезок проводится между двумя точками - (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 error:= 0
real deltaerr:= deltay / deltax
int y:= y0
for x from x0 to x1
error:= error + deltaerr
if error >= 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 , то P i =T i =(r+1,q) и тогда
X i +1 =i+1;Y i +1 =Y i , если же (s-t)≥0,то P i =T i =(r+1,q+1) и тогда X i +1 =i+1 ; Y i +1 =Y i +1 ;
dx=(s-t)=2(rdy-qdx)+2dy –dx
Поскольку знак dx=(s-t) совпадает со знаком разности) , то будем проверять знак выражения d i =dx(s-t). . Так как r=X i -1 и q=Y i -1 ,то
d i +1 = d i +2dy -2dx(y i -y i -1) .
Пусть на предыдущем шаге d i <0 , тогда(y i -y i -1)=0 и d i +1 = d i +2dy . Если же на предыдущем шаге d i ≥0 , тогда(y i -y i -1)=1 и d i +1 = d i +2dx(y i -y i -1)
Осталось узнать как вычислить d i . Так как при i=1
Procedure Bresenham(x1,y1,x2,y2,Color: integer);
dx,dy,incr1,incr2,d,x,y,xend: integer;
dx:= ABS(x2-x1);
dy:= Abs(y2-y1);
d:=2*dy-dx; {начальное значение для d}
incr1:=2*dy; {приращение для d<0}
incr2:=2*(dy-dx); {приращение для d>=0}
if x1>x2 then {начинаем с точки с меньшим знач. x}
PutPixel(x,y,Color); {первая точка отрезка}
While x d:=d+incr1 {выбираем нижнюю точку} d:=d+incr2; {выбираем верхнюю точку, y-возрастает} PutPixel(x,y,Color); 26. Общий алгоритм Брезенхема.
Алгоритм выбирает оптимальные растровые координаты для представления отрезка. Большее из приращений, либо Δx, либо Δy, выбирается в качестве единицы растра. В процессе работы одна из координат - либо x, либо y (в зависимости от углового коэффициента) - изменяется на единицу. Изменение другой координаты (на 0 или 1) зависит от расстояния между действительным положением отрезка и ближайшими координатами сетки. Такое расстояние есть ошибкой. Алгоритм построен так, что требуется лишь знать знак этой ошибки. Следовательно, точка растра (1, 1) лучше аппроксимирует ход отрезка, чем точка (1, 0). Если угловой коэффициент меньше ½, то верно обратное. Для углового коэффициента, равного ½, нет какого-либо предпочтительного выбора. В данном случае алгоритм выбирает точку (1, 1). Так как желательно проверять только знак ошибки, то она первоначально устанавливается равной -½. Таким образом, если угловой коэффициент отрезка больше или равен ½, то величина ошибки в следующей точке растра может быть вычислена как е = -½ + Δy/Δx. Чтобы реализация алгоритма Брезенхема была полной, необходимо обрабатывать отрезки во всех октантах. Это легко сделать, учитывая в алгоритме номер квадранта, в котором лежит отрезок и его угловой коэффициент. Когда абсолютная величина углового коэффициента больше 1, y постоянно изменяется на единицу, а критерий ошибки Брезенхема используется для принятия решения об изменении величины x. Выбор постоянно изменяющейся (на +1 или -1) координаты зависит от квадранта
var x,y,sy,sx,dx,dy,e,z,i: Integer; 27. Алгоритм Брезенхема для генерації окружності
У растр потрібно розкладати як лінійні, а й інші, більш складні функції. Розкладаннюконічних перерізів, тобто кіл, еліпсів, парабол, гіпербол, було присвячено значнукількість робіт. Найбільшу увагу, зрозуміло, приділено кола. Один з найбільшефективних і простих для розуміння алгоритмів генерації окружності належитьБрезенхему. Для початку зауважимо, що необхідно згенерувати тільки одну восьмучастину кола. Решта її частини можуть бути отримані послідовними відбитками. Якщо згенерований перший октант (від 0 до 45 ° протигодинникової стрілки), то другий Октант можна отримати дзеркальним відображеннямвідносно прямої у = х, що дає в сукупності перший квадрант. Перший квадрант відбивається відносно прямої х = 0 для отримання відповідної частини кола у другому квадранті. Верхня півколо відбивається відносно прямої у = 0 для завершення побудови. Для виведення алгоритму розглянемо першу чверть кола з центром в початкукоординат. Зауважимо, що якщо робота алгоритму починається в точці х = 0, у = R, то при генерації окружності за годинниковою стрілкою в першому квадраті у ємонотонно спадною функцією аргументів. Аналогічно, якщо вихідною точкою є у = 0, х == R, то при генерації окружності проти годинникової стрілки х будемонотонно спадною функцією аргументу у. У нашому випадку вибирається генерація за годинниковою стрілкою з початком в точці х = 0, у = R. Передбачається, що центр кола та початкова точка перебувають точно в точках растру. Для будь-якої заданої точки на колі при генерації за годинниковою стрілкою існує тільки три можливості вибрати наступний піксел, найкращим чином наближує окружність: горизонтально вправо, по діагоналі вниз і вправо, вертикально вниз. Алгоритм вибирає піксель, для якого мінімальний квадрат відстані між одним з цих пікселів і окружністю. 28.Понятие фрактала. История фрактальной графики
В повседневной жизни часто можно наблюдать изображение (узоры), которые, казалось бы, нельзя описать математически. Пример: окна зимой замерзают, можно в итоге наблюдать картину. Подобные множества называют фрактальными. Фракталы не похожи на известные фигуры из геометрии, и строятся они по определенным алгоритмам, которые можно реализовать на компьютере. Упрощенно, фрактал - это изображение, полученное в результате некоторого преобразования, многократно примененного к исходной фигуре. Фрактал - это геометрическая фигура, состоящая из частей и которая может быть поделена на части, каждая из которых будет представлять уменьшенную копию целого. Основным свойством фракталов является самоподобие, т.е. любой фрагмент фрактала в том или ином отношении воспроизводит его глобальную структуру. Фракталы делятся на геометрические, алгебраические, стохастические, системы итерируемых функций. 29. Понятие размерности и её расчет
В своей повседневной жизни мы постоянно встречаемся с размерностями. Мы прикидываем длину дороги, узнаем площадь квартиры и т.д. Это понятие вполне интуитивно ясно и, казалось бы, не требует разъяснения. Линия имеет размерность 1. Это означает, что, выбрав точку отсчета, мы можем любую точку на этой линии определить с помощью 1 числа - положительного или отрицательного. Причем это касается всех линий - окружность, квадрат, парабола и т.д. Размерность 2 означает, что любую точку мы можем однозначно определить двумя числами. Не надо думать, что двумерный - значит плоский. Поверхность сферы тоже двумерна (ее можно определить с помощью двух значений - углов наподобие ширины и долготы). Если смотреть с математической точки зрения, то размерность определяется следующим образом: для одномерных объектов - увеличение в два раза их линейного размера приводит к увеличению размеров (в данном случае длинны) в два раза (2^1). Для двумерных объектов увеличение в два раза линейных размеров приводит к увеличению размера (например, площадь прямоугольника) в четыре раза (2^2). Для 3-х мерных объектов увеличение линейных размеров в два раза приводи к увеличению объема в восемь раз (2^3) и так далее. Геометрические фракталы
Именно с этим фракталов началась история развития фракталов в целом. Этот тип фракталов получается путем простых геометрических построений. Обычно при построении геометрических фракталов руководствуются следующим алгоритмом: Примеры геометрических фракталов: кривая Пеано, снежинка Коха, лист папоротника, треугольник Серпинского, Алгебраические фракталы
Фрактал
- сложная геометрическая фигура, обладающая свойством самоподобия, то есть составленная из нескольких частей, каждая из которых подобна всей фигуре целиком Алгебраические фракталы получили своё название за то, что их строят на основе алгебраических функцій.К алгебраическим фракталам относяться: множество Мандельброта, множество Жюлиа, басейны Ньютона, биоморфы.
-множество Мандельброта:
Впервые множество Мандельброта было описано в 1905 году Пьером Фату. Фату изучал рекурсивные процессы вида Начав с точки на комплексной плоскости, можно получить новые точки, последовательно применяя к ним эту формулу. Такая последовательность точек называется орбитой при преобразовании Фату нашел, что орбита при этом преобразовании показывает достаточно сложное и интересное поведение. Существует бесконечное множество таких преобразований - своё для каждого значения . (названо мандельброта так как он первым провел необходимое количество вычислений использовав компьютер). -множество Жюлиа
: мно́жество Жюлиа́ рационального отображения -бассейны Ньютона:
Области с фрактальными границами появляются при приближенном нахождении корней нелинейного уравнения алгоритмом Ньютона накомплексной плоскости (для функции действительной переменной метод Ньютона часто называют методом касательных
, который, в данном случае, обобщается для комплексной плоскости). Применим метод Ньютона для нахождения нуля функции комплексного переменного, используя процедуру: Выбор начального приближения представляет особый интерес. Т.к. функция может иметь несколько нулей, в различных случаях метод может сходиться к различным значениям. -биоморфы:
сокращенная форма множества Жюлиа, вычисляеться по формуле z=z 3 +c. Название получила из-за схожести с одноклеточными организмами. Стохастические фракталы
Типичным представителем данного вида фракталов является так называемая плазма. Для её построения берут прямоугольник и для каждого его угла определяют цвет. Далее находят центральную точку прямоугольника и раскрашивают её в цвет, равный среднеарифметическому цветов по углам прямоугольника + некоторое случайное число. Чем больше это случайно число - тем более рваным будет рисунок. Природные объекты часто имеют фрактальную форму. Для их моделирования могут применяться стохастические (случайные) фракталы. Примеры стохастических фракталов: траектория броуновского движения на плоскости и в пространстве; граница траектории броуновского движения на плоскости. В 2001 году Лоулер, Шрамм и Вернер доказали предположение Мандельброта о том, что её размерность равна 4/3. эволюции Шрамма-Лёвнера - конформно-инвариантные фрактальные кривые, возникающие в критических двумерных моделях статистической механики, например, в модели Изинга и перколяции. различные виды рандомизированных фракталов, то есть фракталов, полученных с помощью рекурсивной процедуры, в которую на каждом шаге введён случайный параметр. Плазма - пример использования такого фрактала в компьютерной графике. Фрактальная монотипия, или стохатипия - направления в изобразительном искусстве, заключающиеся в получении изображения случайного фрактала. Похожая информация. Алгоритм Брезенхема был предложен Джеком Е. Брезенхэмом (Jack E. Bresenham) в 1962 году и предназначен для рисования фигур точками на плоскости. Этот алгоритм находит широкое распространение в машинной графике для рисования линий на экране. Алгоритм определяет, какие точки двумерного растра необходимо закрасить. Графическая интерпретация алгоритма Брезенхема представлена на рисунке. Для рисования прямых отрезков на плоскости с использованием алгоритма Брезенхема запишем уравнение прямой в общем виде f(x,y)=Ax+By+C=0
где коэффициенты A
и B
выражаются через коэффициенты k
и b
уравнения прямой. Если прямая проходит через две точки с координатами (x1
;y1
)
и (x2
;y2
)
, то коэффициенты уравнения прямой определяются по формулам A=y2-y1
Для любой растровой точки с координатами (xi
;yi
)
значение функция Таким образом, одним из методов решения того, какая из точек P
или Q
(см. рисунок) будет отображена на следующем шаге, является сравнение середины отрезка |P-Q|
со значением функции f(x,y)
. Если значение f(x,y)
лежит ниже средней точки отрезка |P-Q|
, то следующей отображаемой точкой будет точка P
, иначе - точка Q
. ∆f=A∆x+B∆y
После отображения точки с координатами (xi,yi)
принимается решение о следующей отображаемой точке. Для этого сравниваются приращения Δx
и Δy
, характеризующие наличие или отсутствие перемещения по соответствующей координате. Эти приращения могут принимать значения 0 или 1. Следовательно, когда мы перемещаемся от точки вправо, когда мы перемещаемся от точки вправо и вниз, то ∆f=A+B
, когда мы перемещаемся от точки вниз, то Нам известны координаты начала отрезка, то есть точки, заведомо лежащей на искомой прямой. Ставим туда первую точку и принимаем f
= 0
. От текущей точки можно сделать два шага - либо по вертикали (по горизонтали), либо по диагонали на один пиксель. |A|<|B|
с каждым шагом осуществляется движение по горизонтали или диагонали. 1 #include
Алгоритм Брезенхема также может применяться в задачах управления, например, для регулирования мощности или скорости вращения. При этом горизонтальной осью является ось времени, а заданное значение устанавливает коэффициент угла наклона прямой. Алгоритм
вывода прямой линии
Поскольку
экран растрового дисплея с электронно-лучевой
трубкой (ЭЛТ) можно рассматривать как
матрицу дискретных элементов (пикселов),
каждый из которых может быть подсвечен,
нельзя непосредственно провести отрезок
из одной точки в другую. Процесс
определения пикселов, наилучшим образом
аппроксимирующих заданный отрезок,
называется разложением в растр. В
сочетании с процессом построчной
визуализации изображения он известен
как преобразование растровой развертки.
Для горизонтальных, вертикальных и
наклоненных под углом 45°. отрезков выбор
растровых элементов очевиден. При любой
другой ориентации выбрать нужные пикселы
труднее, что показано на рис.1. Рис.1.1.
Разложение в растр отрезков прямых. Общие
требования к алгоритмам вычерчивания
отрезков следующие: Отрезки должны
выглядеть прямыми, начинаться и
заканчиваться в заданных точках, яркость
вдоль отрезка должна быть постоянной
и не зависеть от длины и наклона, рисовать
нужно быстро. Постоянная
вдоль всего отрезка яркость достигается
лишь при проведении горизонтальных,
вертикальных и наклоненных под углом
45° прямых. Для всех других ориентаций
разложение в растр приведет к
неравномерности яркости, как это показано
на рис. 1. В
большинстве алгоритмов вычерчивания
отрезков для упрощения вычислений
используется пошаговый алгоритм.
Приведем пример подобного алгоритма: Простой
пошаговый алгоритм
позиция
= начало шаг
= приращение 1.
if
позиция
- конец < точность then
4 if
позици > конец then
2 if
позиция
< конец then
3 2.
позиция = позиция - шаг 3.
позиция = позиция + шаг 4.
finish
Алгоритм
Брезенхема.
Хотя
алгоритм Брезенхема был первоначально
разработан для цифровых графопостроителей,
однако он в равной степени подходит для
использования растровыми устройствами
с ЭЛТ. Алгоритм выбирает оптимальные
растровые координаты для представления
отрезка. В процессе работы одна из
координат - либо x, либо y (в зависиимости
от углового коэффициента) - изменяется
на единицу. Изменение другой координаты
(на 0 или 1) зависит от расстояния между
действительным положением отрезка и
ближайшими координатами сетки. Такое
расстояние мы назовем ошибкой. Алгоритм
построен так, что требуется проверить
лишь знак этой ошибки. На рис.3.1 это
иллюстрируется для отрезка в первом
октанте, т.е. для отрезка с угловым
коэффициентом, лежащим в диапазоне от
0 до 1. Из рисунка можно заметить, что
если угловой коэффициент отрезка из
точки (0,0) больше, чем 1/2, то пересечение
с прямой x = 1 будет расположено ближе к
прямой y = 1, чем к прямой y = 0. Следовательно,
точка растра (1,1) лучше аппроксимирует
ход отрезка, чем точка (1,0). Если угловой
коэффициент меньше 1/2, то верно обратное.
для углового кэффициента, равного 1/2,
нет какого либо предпочтительного
выбора. В данном случае алгоритм выбирает
точку (1,1). Рис.3.2.
График ошибки в алгоритме Брезенхема. Так
как желательно проверять только знак
ошибки, то она первоначально устанавливается
равной -1/2. Таким образом, если угловой
коэффициент отрезка больше или равен
1/2, то величина ошибки в следующей точке
растра с координатами (1,0) может быть
вычислена как e
=
e
+ m
где
m
- угловой коэффициент. В нашем случае
при начальном значении ошибки -1/2 e
= 1/2 + 3/8 = -1/8 Так
как е
отрицательно, отрезок пройдет ниже
середины пиксела. Следовательно, пиксел
на том же самом горизонтальном уровне
лучше аппроксимирует положение отрезка,
поэтому у
не увеличивается. Аналогично вычисляем
ошибку e
=
-1/8 + 3/8 = 1/4 в
следующей точке растра (2,0). Теперь е
положительно, значит отрезок пройдет
выше средней точки. Растровый элемент
(2,1) со следующей по величине координатой
у
лучше аппроксимирует положение отрезка.
Следовательно
у
увеличивается на 1. Прежде чем рассматривать
следующий пиксел, необходимо
откорректировать ошибку вычитанием из
нее 1. Имеем e
= 1/4 - 1 = -3/4 Заметим,
что пересечение вертикальной прямой x
= 2 с заданным отрезком лежит на 1/4 ниже
прямой у
=
1. Еслиже перенести отрезок 1/2 вниз, мы
получим как раз величину -3/4. Продолжение
вычислений для следующего пиксела дает e
= -3/4 + 3/8 = -3/8 Так
как е
отрицательно, то у не увеличивается. Из
всего сказанного следует, что ошибка -
это интервал, отсекаемый по оси у
рассматриваемым отрезком в каждом
растровом элементе (относительно -1/2). Приведем
алгоритм Брезенхема для первого октанта,
т.е. для случая 0 =< y =< x. Алгоритм
Брезенхема разложения в растр отрезка
для первого октанта
Integer
- функция преобразования в целое x,
y, x, y - целые е
- вещественное инициализация
переменных Инициализация
с поправкой на половину пиксела е
= y/x - 1/2 начало
основного цикла for
i = 1 to x while
(e => 0) e
= e + y/x Блок-схема
алгоритма приводится на рис.3.3. Пример
приведен ниже. Рис.
3.3. Блок-схема алгоритма Брезенхема. Пример
3.1. Алгоритм Брезенхема. Рассмотрим
отрезок проведенный из точки (0,0) в точку
(5,5). Разложение отрезка в растр по
алгоритму Брезенхема приводит к такому
результату: начальные
установки е
= 1 - 1/2 = 1/2 Результат
показан на рис.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 для
отрицательного, нулевого и положительного
аргумента соответственно инициализация
переменных x
= abs(x2 - x1) y
= abs(y2 - y1) s1
= Sign
(x2
- x1) s2
= Sign
(y2
- y1) обмен
значений x и y в зависимости от углового
коэффициента наклона отрезка if
y
< x
then
end
if
инициализация
с поправкой на половину пиксела =
2*y
- x основной
цикл for
i = 1 to
x Plot
(x,y) while
(
=>0) if
Обмен
= 1 then
=
- 2*x end
while
if
Обмен
= 1 then
=
+ 2*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 диагональная точка (x i ,
+ 1, у i
-
1) находится внутри реальной окружности,
т. е. это случаи 1 или 2 на рис. 5.4. Ясно,
что в этой ситуации следует выбрать
либо пиксел (x i ,
+ 1, у
i),
т.
е. m H ,
либо пиксел (x i ,
+ 1, у
i
-
1), т. е. m D .
Для этого сначала рассмотрим случай 1
и проверим разность квадратов расстояний
от окружности до пикселов в горизонтальном
и диагональном направлениях: =
|(x i
+ 1) 2
+ (y i) 2
-R 2 |
- |(x i
+ 1) 2
+ (y i
-1) 2
-R 2 | При
< 0 расстояние от окружности до
диагонального пиксела больше, чем до
горизонтального.
Напротив, если
> 0,
расстояние
до горизонтального пиксела больше.
Таким образом, при
<= 0 выбираем m H
в
(x i ,
+ 1, у i
- 1) при
> 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( i
+ y i
)
-
1 существенно
упрощает выражение. Рассмотрим
случай 2 на рис. 5.4 и заметим, что здесь
должен быть выбран горизонтальный
пиксел (x i ,
+ 1, у i),
так как.у является монотонно убывающей
функцией. Проверка компонент показывает,
что (x i
+ 1) 2
+ (y i) 2
-R 2
< 0 (x i
+ 1) 2
+ (y i
-1) 2
-R 2
< 0 поскольку
в случае 2 горизонтальный (x i ,
+ 1, у i)
и диагональный (x i ,
+ 1, у i
-1) пикселы лежат внутри окружности.
Следовательно, < 0, и при использовании
того же самого критерия, что и в случае
1, выбирается пиксел (x i ,
+ 1, у i). Если
i
> 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) больше и следует выбрать диагональный
шаг к пикселу (x i ,
+ 1, у i
-1). Напротив, в случае"
>
0 расстояние от окружности до диагонального
пиксела больше и следует выбрать
вертикальное движение к пикселу (x i , у i
-1). Таким образом, при
"
<=
0 выбираем m D
в (x i
+1, у 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 поскольку
для случая 3 диагональный пиксел (x i
+1,
у i
-1) находится вне окружности, тогда как
вертикальный пиксел (x i , у i
-1) лежит внутри ее. Это позволяет записать
"
в виде "
= (x i
+1) 2
+ (y i
-1) 2
-R 2
+ (x i) 2
+ (y i
-1) 2
-R 2 Дополнение
до полного квадрата члена (x i) 2
с помощью добавления и вычитания 2x i
+ 1 дает "
= 2[(x i
+1) 2
+ (y i
-1) 2
-R 2 ]
- 2x i
- 1 Использование
определения i
приводит выражение к виду "
=
2( i
-
x i
)-
1 Теперь,
рассматривая случай 4, снова заметим,
что следует выбрать вертикальный пиксел
(x i ,
у i
-1), так как у является монотонно убывающей
функцией при возрастании х.
Проверка
компонент "
для случая 4 показывает, что (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) . Таким образом, случай i
= 0 подчиняется тому же критерию, что и
случай i
< 0 или i
>
0. Подведем итог полученных результатов: <=
0выбираем
пиксел (x i
+1 , у i) - m H >
0 выбираем пиксел (x i
+1 , у i
-1)
-
m D "
<= 0 выбираем пиксел (x i
+1 , у i
-1) - m D Если пространство недискретно, то почему Ахиллес обгоняет черепаху? Если же пространство дискретно, то как частицы реализуют алгоритм Брезенхема? Я давно задумываюсь над тем, что собою представляет Вселенная в целом и законы её работы в частности. Порою описания некоторых физических явлений на той же Википедии достаточно запутаны, чтобы оставаться непонятными даже для человека, который не шибко далёк от данной области. Тем более не повезло мне подобным - тем, кто от этой области по крайней мере был весьма далёк. Однако, с несколько другой плоскостью - алгоритмами, я, будучи программистом, сталкиваюсь почти ежедневно. И однажды, в процессе реализации некоего подобия 2d-физики в консоли, я подумал: «А ведь Вселенная - это по сути такая же консоль неизвестной размерности. Есть ли причины думать, что для линейного движения на, так сказать, экране этой консоли, частицы не должны реализовывать алгоритм Брезенхема?». И кажется, причин нет. Всех, кому интересно, что вообще такое алгоритм Брезенхема, как он может быть связан с физикой и как это может повлиять на её интерпретацию - добро пожаловать под кат. Возможно, Вы найдёте там косвенное подтверждение существования параллельных Вселенных. Или даже вложенных друг в друга Вселенных. F(x) = 0
F(x) = x
F(x) = x * tan(55)
Сей аглоритм был разработан Джеком Брезенхемом в 1962 году, когда тот работал в IBM. Он до сих пор используется для реализации виртуальной графики во многих прикладных и системных комплексах, начиная с оборудования на производстве и заканчивая OpenGL. Используя этот алгоритм, можно рассчитать максимально подходящее приближение для заданной прямой при заданном уровне дискретности плоскости, на которой эта прямая располагается. Реализация на Javascript для общего случая
var draw = (x, y) => { ... }; // функция для рисования точки
var bresenham = (xs, ys) => {
// xs, ys - массивы и соответственно
let deltaX = xs - xs,
deltaY = ys - ys,
error = 0,
deltaError = deltaY,
y = ys;
for (let x = xs; x <= xs; x++) {
draw(x, y);
error += deltaError;
if ((2 * error) >= deltaX) {
y -= 1;
error -= deltaX;
};
};
};
Ещё одним косвенным подтверждением дискретности пространства может служить суждение, исходящее из вышеописанного: если при определённом уменьшении масштабов наблюдаемого, сие теряет способность быть описанным с помощью евклидовой геометрии, то очевидно, что при преодолении минимального порога расстояния метод геометрического описания субъекта всё равно должен быть. Пусть в такой геометрии одной параллельной прямой может соответствовать более одной другой прямой, проходящей через точку, не принадлежащую исходной прямой, или в такой геометрии вообще нет понятия параллельности прямых или даже вовсе понятия прямых, однако имеет место быть любой, гипотетически представляемый метод описания геометрии объекта меньше минимальной длины. И, как известно, есть одна теория, претендующая на способность описать такую геометрию в пределах известного минимального порога. Это теория струн. Она предполагает существование чего-то
, что учёные зовут струнами или бранами, сразу в 10/11/26 измерениях в зависимости от интерпретации и математической модели. Мне лично кажется, что примерно так всё и обстоит и для обоснования своих слов я проведу с Вами мысленный эксперимент: на двумерной плоскости при полной «евклидности» её геометрии работает уже упоминавшееся правило: через одну точку можно провести только одну прямую, параллельную данной. Теперь масштабируем это правило на трёхмерное пространство и получим два
из него вытекающих новых правила: Иначе говоря, или Ахиллес никогда не догонит черепаху, или мы в Матрице вся обозримая Вселенная и известная физика, скорей всего - лишь капля в огромном океане возможного разнообразия реальности.
change: boolean;
begin
x:=x1; y:=y1;
dx:=abs(x2-x1); dy:=abs(y2-y1) ;
sx:=sign(x2-x1); sy:=sign(y2-y1);
e:= 2*dy-dx;
if dy
else begin
z:=dx;
dx:=dy; dy:=z;
change:=true
end;
for i:=1 to dx+dy do begin
if dy< dx then begin
if change then y:=y+sy
else x:=x+sx;
e:=e+2*dy;
end else
if change then x:=x+sx
else y:=y+sy;
e:=e-2*dx
end;
Form1.Canvas.Pixels:=clblack; // вывод точки, для примера
end;
Первые идеи фрактальной геометрии возникли в 19 веке. Кантор с помощью простой рекурсивной процедуры превратил линию в набор несвязанных точек, которые в последствии получили название «Пыль Кантора». Он брал линию и удалял центральную треть и после этого повторял то же самое с оставшимися отрезками. Пеано нарисовал особый вид линии. Для ее рисования Пеано использовал следующий алгоритм:
Он брал прямую линию и заменял её отрезками в три раза меньшей длины, чем у исходной линии. Далее он повторял это же действие с каждым из отрезков. Её уникальность в том, что она заполняет всю плоскость, т.е. для каждой точки, находящейся на плоскости можно найти точку, принадлежащую линии Пеано.
Основателем фрактальной геометрии считается Бенуа Мандельброт
. Мандельброт ввел понятие «фрактал».
Рис. Снежинка Коха
Рис. Лист
Рис. Треугольник Серпинского
- множество точек, динамика в окрестности которых в определённом смысле неустойчива по отношению к малым возмущениям начального положения. В случае, если f
- полином, рассматривают также заполненное множество Жюлиа - множество точек, не стремящихся к бесконечности. Обычное множество Жюлиа при этом является его границей.
B=x1-x2
C=y1∙x2-y2∙x1
Запишем приращение функции
Направление движения по вертикали или горизонтали определяется коэффициентом угла наклона. В случае если угол наклона меньше 45º, и
Если угол наклона больше 45º, с каждым шагом движение осуществляется вертикали или диагонали.
Таким образом, алгоритм рисования наклонного отрезка следующий:
Реализация на C++
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
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) signa = -1;
else
signa = 1;
if
(B < 0) signb = -1;
else
signb = 1;
int
f = 0;
z = "*"
;
int
x = x0, y = y0;
if
(sign == -1)
{
do
{
f += A*signa;
if
(f > 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 < SIZE; i++)
{
z[i] = new
char
;
for
(int
j = 0; j < SIZE; j++)
z[i][j] = "-"
;
}
cout <<
"x1 = "
; cin >>
x1;
cout <<
"y1 = "
; cin >>
y1;
cout <<
"x2 = "
; cin >>
x2;
cout <<
"y2 = "
; cin >>
y2;
Brezenhem(z, x1, y1, x2, y2);
for
(int
i = 0; i < SIZE; i++)
{
for
(int
j = 0; j < SIZE; j++)
cout <<
z[i][j];
cout <<
endl;
}
cin.get(); cin.get();
return
0;
}
Результат выполнения
Алгоритм Брезенхема
Говоря простым языком, чтобы нарисовать на тетрадном листке в клеточку линию толщиной в одну клетку, Вам понадобится закрашивать последовательно идущие клетки, стоящие в ряд. Предположим, что плоскость тетрадного листка дискретна по клеткам, то есть Вы не можете закрасить две соседних половинки соседних клеток и сказать, что закрасили клетку со смещением в 0.5, ибо дискретность заключается в непозволении подобного действия. Таким образом, закрашивая последовательно клетки, стоящие в ряд, Вы получите отрезок желаемой длины. Теперь представим, что Вам необходимо повернуть его на 45 градусов в любом направлении - теперь уже Вы будете закрашивать клетки по диагонали. По сути это - прикладное применение нашим мозгом двух простейших функций:
и
А теперь представим, что отрезок необходимо повернуть ещё на 10 градусов, например. Тогда мы получим классическую однородную линейную функцию:
И нарисовать график этой функции обычной ручкой на обычном листке не составит труда для любого ученика 7 класса. Однако что делать в случае с нашим предполагаемым листком бумаги, который дискретен по клеткам? Ведь тогда возникает необходимость выбирать, какие именно клетки закрашивать при рисовании линии. Тут нам на помощь и приходит алгоритм Брезенхема.
А теперь представьте, что пространство, которое окружает нас, всё таки дискретно. Причём не важно, заполнено ли оно ничем, частицами, переносчиками, полем Хиггса или ещё чем - есть некое понятие минимального количества пространства, меньше которого ничто не может быть. И не важно, относительно ли оно и верна ли теория относительности касательно него - если пространство искривлено, то локально там, где оно искривлено, оно всё равно будет дискретно, даже если с другой позиции может показаться, будто имело место быть изменение того самого минимального порога в любую сторону. При таком предположении получается, что некое явление, или сущность, или правило, должно реализовывать алгоритм Брезенхема для любого рода движения как частиц материи, так и переносчиков взаимодействий. В какой-то мере это объясняет квантование движения частиц в микромире - они принципиально не могут двигаться линейно, не «телепортируясь» из кусочка пространства в другой кусочек, ибо тогда получится, что пространство вовсе не дискретно.
Говоря проще, если добавить измерение при построении прямых, но не добавлять измерение при расчёте подчинения прямых правилам евклидовой геометрии, то вместо двух возможных параллельных прямых, получим «цилиндр» возможных прямых вокруг центра - исходной прямой. А теперь представьте, будто мы живём в мире Супер Марио и пытаемся спроецировать такой цилиндр на собственное двумерное пространство - по рассчётам параллельных прямых быть не может, но по наблюдениям их целая бесконечность-X. Что мы предположим? Правильно, мы введём ещё одно измерение для построения прямых, но не станем добавлять его для расчёта подчинения прямых правилам евклидовой геометрии. По сути, увидев проекцию такого цилиндра на родное двумерное пространство мы придумаем теорию струн в своём двумерном мире.Параллельные и вложенные Вселенные?
Может оказаться так, что древние философы, которые видели в модели атома поведение небесных тел и наоборот, были, скажем, не шибко дальше от истины, чем те, кто утверждал, будто это полная чушь. Ведь если освободиться от всяких знаний
и рассудить логически - теоретически нижний предел есть не более чем фикция, придуманная нами для ограничения действия привычной нам евклидовой геометрии. Говоря другими словами - всё, что меньше планковской длины, а точней, так сказать настоящей планковской длины
, просто не поддаётся исчислению методами евклидовой геометрии, однако же это не значит, будто оное не существует! Вполне может оказаться так, что каждая брана - это набор мультивселенных и так сложилось, что в пределах от планковской длины до неизвестного X геометрия реальности евклидова, ниже планковской длины - например главенствует геометрия Лобачевского или сферическая геометрия, или ещё какая, никак не ограничивая наш полёт фантазии, а выше предела X - например одновременно недезаргова и сферическая геометрия. Мечтать не вредно - могли бы сказать Вы, коли б не тот факт, что даже для однозначно квантового движения, не говоря уже о линейном (которое всё равно квантуется на уровне микромира) частицы должны реализовывать алгоритм Брезенхема, если пространство дискретно.