Optimising Bresenham by drawing many horizontal and vertical lines instead of pixels
https://stackoverflow.com/questions/5333320
-
26-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
I have a set of very efficient horizontal and vertical line drawing functions which can draw many pixels per cycle (for the horizontal one, ~4 pixels/cycle, and the vertical one ~0.25 pixels/cycle.) I'm using Bresenham's line drawing algorithm to draw arbitrary lines. However, this involves calling the single draw pixel routine, which is relatively slow (~0.03 pixels/cycle.)
I've noticed most of the lines drawn by Bresenham's algorithm show horizontal and vertical strips with a good distance between them. Does anyone know if it would be possible to replace these individual calls to DrawPixel with calls to the DrawHoriz and DrawVert drawing routines? Does anyone have a code example? I've tried already, but I've had limited success, mostly resulting in broken output - I suspect I'm approaching it the wrong way.
Many thanks
Solution
The Bresenham algorithm is normally implemented as a set of four special cases, depending on the sign and magnitude of the line's slope (steep positive, steep negative, shallow positive, shallow negative.) In the steep cases, you end up drawing a bunch of vertical line segments, each shifted by one horizontal pixel; for the shallow ones, it's horizontal lines.
As you compute the line coordinates, you step the faster moving one (y for the steep cases, x for the shallow ones) and you calculate the cumulative error in the other coordinate; you change it to the next value when the cumulative error gets to 1. So what if you ran a normal Bresenham algorithm, computing all the pixels, but then instead of drawing each pixel, you just drew the line for a given "fast" coordinate from the beginning to end of the "slow" coordinate -- if you know what I mean. Instead of drawing at each cycle, in other words, you just drew when the slow coordinate changed, right before you bump it to the next value.
Yes, I'm sure this would work. Whether it would be any faster, I have no idea, but it would definitely work.
