Понимание части алгоритма накопления ошибок Брезенхэма?

У меня проблемы с пониманием того, как работает часть накопления ошибок в алгоритме рисования линий Брезенхэма.

Скажем у нас x1 а также x2, Давайте предположим, что x1 < x2, y1 < y2, а также (x2 - x1) >= (y2 - y1) для простоты:

Давайте начнем с наивного способа рисования линии. Это будет выглядеть примерно так:

void DrawLine(int x1, int y1, int x2, int y2)
{
    float y = y1 + 0.5f;
    float slope = (float)(y2 - y1) / (x2 - x1);
    for (int x = x1; x <= x2; ++x)
    {
        PlotPixel(x, (int)y);
        y += slope;
    }
}

Давайте сделаем его более Bresenham'ish и разделим целую и плавающую части y:

void DrawLine(int x1, int y1, int x2, int y2)
{
    int yi = y1;
    float yf = 0.5f;
    float slope = (float)(y2 - y1) / (x2 - x1);
    for (int x = x1; x <= x2; ++x)
    {
        PlotPixel(x, yi);
        yf += slope;
        if (yf >= 1.0f)
        {
            yf -= 1.0f;
            ++yi;
        }
    }
}

На данный момент мы могли бы умножить yf а также slope от 2 * (x2 - x1) чтобы сделать их целыми числами, больше не плавает. Я это понимаю.

Часть, которую я не полностью понимаю, это:

    if (yf >= 1.0f)
    {
        yf -= 1.0f;
        ++yi;
    }

Как это на самом деле работает? почему мы сравниваем с 1.0, а затем уменьшаем его?

Я знаю, что основной вопрос Брезенхэма: если мы в настоящее время в пикселе x, y и мы хотим нарисовать следующий, мы должны выбрать x + 1, y или же x + 1, y + 1? - Я просто не понимаю, как эта проверка помогает нам ответить на этот вопрос.

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

Любые объяснения приветствуются, спасибо.

Источник

3 ответа

Решение

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

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

Во-вторых, все нарисованные линии являются отражением линий с наклоном от 0 до 0,5. Существует особый случай для вертикальных линий. Если ваш алгоритм корректен для этого ввода, то вам нужно инициализировать начальное состояние растеризатора, чтобы правильно растеризовать линию: начальный пиксель (x, y), ∆x, ∆y и D переменная решения.

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

Вы можете принять это решение, отслеживая, насколько ваша растеризованная линия отклоняется от истинной линии. Для этого уравнение линии переписывается в неявную функцию, F(x, y) = ∆yx - ∆xy + ∆xb = 0, и вы неоднократно оцениваете его F(x + 1 y + 0.5). Поскольку для этого требуется математика с плавающей запятой, вы сосредотачиваетесь на том, чтобы определить, находитесь ли вы над, над или под истинной линией. Следовательно, F(x + 1 y + 0,5) = ∆y - 0,5∆x и умножается на два 2 * F(x + 1 y + 0,5) = 2∆y - ∆x. Это первое решение, если результат меньше нуля, добавьте единицу к x, но ноль к y.

Второе решение и последующие решения следуют аналогично, и ошибка накапливается. Решающая переменная D инициализируется в 2∆y - ∆x. Если D < 0, то D = D + 2∆y; иначе y = y + 1 и D = D + 2(∆y - ∆x). Переменная x всегда увеличивается.

Джим Арво прекрасно объяснил алгоритм Брезенхэма.

Источник

В вашей реализации yf это расстояние 0,5 + между реальной координатой Y с плавающей точкой и нарисованной (целой) координатой Y. Это расстояние является текущей ошибкой вашего рисунка. Вы хотите, чтобы ошибка не превышала половины пикселя между реальной линией и нарисованной линией (-0,5..+0,5), поэтому yf который 0.5+error должно быть между 0 и 1. Когда оно превышает единицу, вы просто увеличиваете свою нарисованную координату Y (yi) на единицу, и вам нужно уменьшить ошибку на единицу. Давайте возьмем пример:

slope = 0.3;
x = 0; yf = 0.5; y = 0; // start drawing: no error
x = 1; yf = 0.8; y = 0; // draw second point at (1, 0); error is +0.3
x = 2; yf = 1.1; y = 0; // error is too big (+0.6): increase y
       yf = 0.1; y = 1; // now error is -0.4; draw point at (2, 1)
x = 3; yf = 0.4; y = 1; // draw at (3, 1); error is -0.1
x = 4; yf = 0.7; y = 1; // draw at (4, 1); error is +0.2
x = 5; yf = 1.0; y = 1; // error is too big (+0.5); increase y
       yf = 0.0; y = 2; // now error is -0.5; draw point at (5, 2)

И так далее.

Источник

У меня недостаточно репутации, чтобы отвечать на досаду »

Спасибо за ответ. Хорошая статья! Одна вещь, которую он не охватывает, - это то, как адаптировать алгоритм для работы с другими октантами и случаями, когда m> 1. Есть идеи?

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

Источник
Другие вопросы по тегам