пожалуйста, объясните мне этот код для рисования линии Брезенхэма
Я искал по всему Интернету и нашел сотни реализации алгоритма рисования линий Брезенхэма. Но мне показалось странным то, что только два или три из них могут охватывать все восемь октетов. тем не менее, они используются во многих приложениях.
Например, эта леди реализованы эта версия (строка 415) алгоритма Брезенхэма. Но это не охватывает все 360 градусов. Этот парень здесь похоже развивает библиотеку. Но все равно это не работает должным образом.
Ты можешь сказать мне, почему?
Реализация этого парня работает отлично. Но, я полагаю, это не алгоритм Брезенхэма. Это имеет очень мало сходства с теория.
Наконец я нашел следующая версия алгоритма рисования линий Брезенхэма, который работает правильно.
#include "utils.h"
void Bresenham(int x1, int y1, int const x2, int const y2, int color)
{
int dx = x2 - x1;
// if x1 == x2, then it does not matter what we set here
int ix((dx > 0) - (dx < 0));
dx = abs(dx) << 1;
int dy = y2 - y1;
// if y1 == y2, then it does not matter what we set here
int iy((dy > 0) - (dy < 0));
dy = abs(dy) << 1;
PlotPixel(x1, y1, color);
if (dx >= dy)
{
// error may go below zero
int error(dy - (dx >> 1));
while (x1 != x2)
{
if ((error >= 0) && (error || (ix > 0)))
{
error -= dx;
y1 += iy;
}
// else do nothing
error += dy;
x1 += ix;
PlotPixel(x1, y1, color);
}
}
else
{
// error may go below zero
int error(dx - (dy >> 1));
while (y1 != y2)
{
if ((error >= 0) && (error || (iy > 0)))
{
error -= dy;
x1 += ix;
}
// else do nothing
error += dx;
y1 += iy;
PlotPixel(x1, y1, color);
}
}
}
int main()
{
int gm = DETECT;
int gd = DETECT;
initgraph(&gm, &gd, "");
double x1 = 0;
double y1 = 0;
double r = 50;
double x2 = 0;
double y2 = 0;
double signx = 0;
double signy = 0;
for(int theta=0 ; theta<=360 ; theta++)
{
x2 = r * cos(DegreeToRad((double) theta));
y2 = r * sin(DegreeToRad((double) theta));
x1 = 5 * cos(DegreeToRad((double) theta));
y1 = 5 * sin(DegreeToRad((double) theta));
Bresenham(x1, y1, x2, y2, YELLOW);
//delay(10);
}
getch();
closegraph();
return 0;
}
Оригинальный код довольно странный. Итак, мне нужна ваша помощь, чтобы понять это.
-
Почему он смещает влево dx и dy, а затем, перед расчетом, снова смещает их вправо?
-
Где дт и дс что теория Переговоры о?
-
Согласно теории, dt и ds должны были проверяться на каждом этапе цикла while. Но этот код не делает этого. Зачем?
-
Теория, кажется, не имеет никаких указаний на какую-либо ошибку обработки. Какая польза от
errorчто код рассчитывается? Как он рассчитываетerror? Как он используетerrorзначение? -
Какая логика стоит за тестом?
if(dx >= dy)?
Решение
Вот объяснение моей собственной версии Брезенхэма.
Начнем с параметрического уравнения линии, (X + t.Dx, Y + t.Dy), где t параметр в диапазоне [0, 1], Конечные точки, очевидно, (X, Y) а также (X + Dx, Y + Dy),
Чтобы превратить его в цифровую линию, нам нужен ровно один пиксель на строку или столбец, в зависимости от того, что обеспечит непрерывную линию. Так определяя D = Max(|Dx|, |Dy|)будем рисовать D+1 точки, соответствующие дробным t: (X + I.Dx/D, Y + I.Dy/D), с I в [0, D],
Давайте на минутку предположим 0 <= Dy < Dx = Dи уравнение упрощается до (X + I, Y + I.Dy/Dx), Поскольку последний член не может быть целым числом, мы округлим его round(I.Dy/Dx) = floor(I.Dy/Dx + 1/2) = floor((I.Dy + Dx/2) / Dx),
Последнее выражение представляет собой частное от числа после арифметической прогрессии по знаменателю, превышающему общую разницу. Следовательно, когда вы увеличиваете Iсоотношение либо остается фиксированным, либо увеличивается на 1, Для реализации без деления мы используем хитрость: оставим частное и остаток от деления, пусть Q а также Rи каждый раз, когда вы увеличиваете IОбновите это.
Позволять N = I.Dy + Dx/2, а также Q = N / Dx, R = N % Dx, Затем увеличение I, I' = I + 1, N' = N + Dy, Q' = (N + Dy) / Dx, R' = (N + Dy) % Dx, Как вы можете проверить, действует следующее правило:
if R + Dy >= Dx
Q' = Q + 1; R' = R + Dy - Dx
else
Q' = Q; R' = R + Dy
Теперь мы соединили все элементы, отрегулировали знаки и различали более горизонтальные и более вертикальные случаи (как вы заметите, нет необходимости представлять Q явно):
# Increments
Sx= Sign(Dx); Sy= Sign(Dy)
# Segment length
Dx= |Dx|; Dy= |Dy|; D= Max(Dx, Dy)
# Initial remainder
R= D / 2
if Dx > Dy:
# Main loop
for I= 0..D:
Set(X, Y)
# Update (X, Y) and R
X+= Sx; R+= Dy # Lateral move
if R >= Dx
Y+= Sy; R-= Dx # Diagonal move
else:
# Main loop
for I= 0..D:
Set(X, Y)
# Update (X, Y) and R
Y+= Sy; R+= Dx # Lateral move
if R >= Dy
X+= Sx; R-= Dy # Diagonal move
Реализация на C / C ++ (автор @anonymous)
void Set(int x, int y, int color)
{
PlotPixel(x, y, color);
}
int Sign(int dxy)
{
if(dxy<0) return -1;
else if(dxy>0) return 1;
else return 0;
}
void Bresenham(int x1, int y1, int x2, int y2, int color)
{
int Dx = x2 - x1;
int Dy = y2 - y1;
//# Increments
int Sx = Sign(Dx);
int Sy = Sign(Dy);
//# Segment length
Dx = abs(Dx);
Dy = abs(Dy);
int D = max(Dx, Dy);
//# Initial remainder
double R = D / 2;
int X = x1;
int Y = y1;
if(Dx > Dy)
{
//# Main loop
for(int I=0; I<D; I++)
{
Set(X, Y, color);
//# Update (X, Y) and R
X+= Sx; R+= Dy; //# Lateral move
if (R >= Dx)
{
Y+= Sy;
R-= Dx; //# Diagonal move
}
}
}
else
{
//# Main loop
for(int I=0; I<D; I++)
{
Set(X, Y, color);
//# Update (X, Y) and R
Y+= Sy;
R+= Dx; //# Lateral move
if(R >= Dy)
{
X+= Sx;
R-= Dy; //# Diagonal move
}
}
}
}
Другие решения
Почему он сдвинулся dx и dy, а затем, перед расчетом, снова
сдвигая их вправо?
Он использует половину int таким образом, чтобы он был точным. Но половина int будет усечена. Таким образом, используя представление, которое по своей сути удвоено, он может использовать сдвиг вправо в виде не усеченного деления на два. Это не то, как я узнал Брезенхэма давным-давно. Но намерение кажется ясным.
Где дт и дс, о которых говорит теория?
Я не внимательно прочитал вашу ссылку на теорию, но способ, которым я узнал Брезенхэма, проще, чем этот. Первоначальный пункт был для очень примитивных процессоров, в которых вы хотите минимизировать вычисления.
Теория, кажется, не имеет никаких указаний на какую-либо ошибку обработки.
Какая польза от ошибки, которую вычисляет код? Как он
вычислить ошибку? Как он использует значение ошибки?
Я ожидаю, что только разница в терминологии сбивает вас с толку. Ключевым моментом алгоритма (в любой форме) является накопитель, представляющий совокупную «ошибку» по сравнению с нецифрованной строкой. Эта «ошибка» обычно может иметь другое имя, но под любым именем она является сердцем кода. Вы должны увидеть, что он используется на каждом шаге, чтобы решить, в каком направлении этот шаг оцифровывается.
Какова логика теста, если (dx> = dy)?
Идея состоит в том, что более быстрое изменение направления изменяется на 1 на каждом шаге, а более медленное изменение направления изменяется на 0 или 1 за шаг в зависимости от этой кумулятивной «ошибки». Когда размер кода был основным фактором, реальная хитрость этого алгоритма заключалась в том, чтобы кодировать его так, чтобы код распределялся между основными различиями X быстрее по сравнению с Y быстрее. Но ясно, что все это легко понять, если вы посмотрите на случай изменения X быстрее, отдельно от случая изменения Y быстрее.
- Почему он сдвинулся dx и dy, а затем, перед расчетом, снова
сдвигая их вправо?
Я объясню ниже.
- Где дт и дс, о которых говорит теория?
Они исчезли, реализация реализует алгоритм рисования линий в средней точке. Вы можете получить один алгоритм из другого, хотя. Это упражнение для читателя 🙂
- Согласно теории, DT и DS должны были быть проверены в каждом
шаг в то время как цикл. Но этот код не делает этого. Зачем?
То же, что и выше. Это проверка на ошибку, что одно и то же.
- Теория, кажется, не имеет никаких указаний на какую-либо ошибку обработки.
Какая польза от ошибки, которую вычисляет код? Как он
вычислить ошибку? Как он использует значение ошибки?
Уравнение прямой a*x + b*y + c = 0, где a = x2 - x1 а также b = -(y2 - y1)может дать указание на ошибку, так как a*x + b*y + c пропорционально расстоянию между точками (x, y) от линии, с действительными коэффициентами a, b а также c, Мы можем умножить уравнение на произвольную вещественную постоянную k, не равный 0, и он будет по-прежнему сохраняться для каждой точки на линии.
Предположим, мы рисуем только в первом квадранте. На каждом этапе мы хотим оценить a*x + b*y + c за (x + 1, y + 1/2) чтобы увидеть, как далеко от линии находится эта (средняя) точка и на основании чего решить, будем ли мы увеличивать y или нет, но расстояние не имеет значения, только его знак. Для первого квадранта расстояние будет положительным, если линия находится выше средней точки (x + 1, y + 1/2) и отрицательный, если ниже. Если линия выше средней точки, мы должны идти «вверх».
Итак, мы знаем для начального (x, y), a*x + b*y + c = 0но как насчет (x + 1, y + 1/2)? Термин ошибки равен a + b/2, Нам не нравятся половинки, поэтому мы умножаем (сдвиг влево) a а также b на 1 и, таким образом, получить начальную ошибку 2*a + bЭто и есть причина правильного сдвига. Если ошибка положительная, то линия находится выше средней точки (x + 1, y + 1/2) и мы должны идти вверх. Если отрицательно, то линия находится ниже средней точки, и мы уходим y быть. Мы обновляем ошибку постепенно на каждом шаге, в зависимости от того, увеличивали ли мы y или нет.
С некоторыми мыслями вы можете распространить алгоритм на все секторы.
- Какова логика теста, если (dx> = dy)?
Тестируем на крутизну трассы. Это делает свопы ненужными.