Линейный алгоритм Брезенхема против сложного наивного вектора
Дано xlen дельта-х, ylen дельта-у, len это длина строки, почему этот код:
//Bresenham implementation
float x = x0, y = y0;
if (slope < 1) {
while (x < xlen) {
paintpt(x, y));
x += step;
if (left.y > right.y)
y += slope * step;
else
y -= slope * step;
}
}
более эффективный, чем этот код?
//Naive vector addition
int x = x0, y = y0;
float xinc = xlen / len, yinc = ylen / len;
for (float i = 0; i < len; i++) {
paintpt(x, y);
x += i * xinc;
y += i * yinc;
}
(Я имею в виду, кроме инициализации, очевидно. Предположим, что вам даны только длина линии и направление, и вы должны отступить от наклона и еще много чего.)
Решение
1) x += i * xinc; это умножение с плавающей точкой, округленное до целого числа. Это не гарантирует, что вы пройдете все целые числа с самого начала x в ваш финал x, Это означает, что в вашей линии могут быть дыры …
2) Ваша реализация в Брезенхэме неверна. Вы не добавляете шаги в x, Вы увеличиваете xна каждой итерации и добавить delta_y к счетчику ошибок. Когда счетчик ошибок больше delta_x Вы увеличиваете y и вычесть delta_x из счетчика ошибок.
Это объяснение линии, чья delta_y больше 0 и уступает delta_x, Делайте ротацию для всех остальных случаев.
3) Для эффективности: это немного сложно. Старые компьютеры не могли легко выполнять вычисления с плавающей запятой. Вплоть до Pentium не было никакого сопроцессора x87, и все вычисления с плавающей запятой выполнялись программно. Это было в 1000 раз медленнее, чем простая целочисленная арифметика. В настоящее время все компьютеры могут выполнять операции SIMD (т.е. они используют векторные расширения с плавающей точкой); это может быть не так больше.
Другие решения
Алгоритм Брезенхема основан на 60-х годах, когда компьютеры помещались в большие шкафы. Его отличительными чертами были / являются:
- нет математики с плавающей точкой,
- нет умножения / деления.
Поскольку в те дни даже целочисленные деления и умножения были «дорогими». «Настоящая» реализация Брезенхэма не будет делить / умножаться и не будет использовать математические вычисления с плавающей запятой. Ваша реализация «ложная». Проверьте Вот для «истинного».