4
$\begingroup$

Why does Bresenham's line algorithm eliminate dy/dx division and the multiplication of that (potentially floating point) number?

$\endgroup$
2
  • 2
    $\begingroup$ So it seems to me that we don't have to necessarily talk about Bresenham's algorithm, or any specific algorithm. Really, the question seems to be "why is integer arithmetic faster than floating-point arithmetic". Would you agree? If so, this will ultimately boil down to your specific hardware you care about. If you care about say modern desktop hardware, have a look at the Intel optimization guide. You can see the latency etc. for a specific instruction (this you can very well use as a reference too). $\endgroup$
    – Juho
    Oct 21 '15 at 12:06
  • $\begingroup$ This would be my first comment though, anyway i have a similar situation and i can tell you that division would {by time} take longer and longer to calculate the decimal points this would by somehow change the structure of a specific system. $\endgroup$
    – ABD
    Oct 21 '15 at 19:31
5
$\begingroup$

Multiplication can inherently be computed faster than division because it parallelizes better.

If you recall the multiplication and division methods of written calculation, they work by successive additions or subtractions, with shifts. Anyway, in a multiplication you can multiply the multiplicand by all digits of the multiplier simultaneously, and add the results. On the opposite, in division you have to wait until a subtraction has been performed to decide the next digit of the quotient, and the approach is much more serial.

ALU designers are working wonders to implement fast divisors, but they never reach the performance of multipliers.

In the old days, processors even had no hardware divisors at all and divisions were performed in software, orders of magnitude slower, which incited people to avoid divisions by all means.


If you look at Bresenham's algorithm, it actually computes points on a line using the standard line equation $$y=\frac{\Delta_y}{\Delta_x}x$$ for increasing integers $x$ (width a slope not exceeding $1$). More precisely, to cope with the discrete nature of the raster, the $y$ coordinate needs to be truncated or rounded,

$$y=\left\lfloor\frac{\Delta_y}{\Delta_x}x+\epsilon\right\rfloor=\left\lfloor\frac{\Delta_yx+\Delta_x\epsilon}{\Delta_x}\right\rfloor,$$ where $\epsilon$ can be $0$ or $\frac12$.

The trick of Bresenham is to avoid performing the division on every incrementation of $x$, but instead keep the value of the quotient and remainder updated, which costs only a comparison and one or two additions (either add $\Delta_y$ to the remainder, or increment the quotient and add $\Delta_y-\Delta_x$ to the remainder).

When the line is sufficiently long, it makes sense to compare this with the one-time computation of the slope in fixed-point arithmetic, followed by successive additions and rounding. What you lose by performing a division can be regained by avoiding the conditional branch.

$$y=\left\lfloor\frac{px+e}{2^n}\right\rfloor$$ where $p=[2^n\Delta_y/\Delta_x]$ and $e=[2^n\epsilon]$. The "division" is implemented with a fast shift.

$\endgroup$
5
  • $\begingroup$ Ok thanks. What about the efficiency of adding or multiplying floating points versus integers? $\endgroup$ Oct 22 '15 at 6:11
  • $\begingroup$ Is a rounding function slow as well due to it having to round the base 10 value while the computer works in base 2? $\endgroup$ Oct 22 '15 at 6:16
  • $\begingroup$ I would not think of floating-point at all here, fixed-point is preferable. $\endgroup$ Oct 22 '15 at 7:29
  • $\begingroup$ Rounding isn't done in base $10$, you add $1/2$ and truncate, which is done with a simple shift. $\endgroup$ Oct 22 '15 at 7:30
  • $\begingroup$ On a modern CPU, adding and multiplying floating points is often just as efficient as adding and multiplying integers, when you take instruction scheduling into account. However, this wasn't true of CPUs in 1962, and also isn't necessarily true of other hardware (e.g. microcontrollers which control plotters or 3D printers). $\endgroup$
    – Pseudonym
    Oct 23 '15 at 0:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.