Beyond textbook Bresenham
Introduction
Every now and then (don't ask) I have to yet again write a subpixel-accurate but NOT antialiased line drawer. In many ways AA lines are much simpler - because every pixel is a different shade, you can't really do anything much cleverer than simple Bresenham and use the distance as an AA coverage/shade index (which is then called Wu's Algorithm: https://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm). But today let's talk about non-AA lines - ones where the pixel is either set to the colour, or not.
The other thing I need to do is subpixel-correct lines, because they're so much more nicer in motion than non-subpixel-correct lines. Don't confuse this with AA lines - you can have chunky non-AA single-colour pixel lines that are ALSO subpixel-correct.
Why this is important is hard to convery in a static picture, but in motion the quality difference is very obvious. And it turns out the speed difference is not actually significant, so why not go for the extra quality?
Basic Bresenham
The thing everybody says when asked about drawing lines is "Bresenham's algorithm". It's one of those things people trot out to show how smart they are because they know a guy's name. And I don't have a problem with him - he was very smart, and there's a perfectly good Wikipedia article on the algorithm and it works great. But it has two problems. First, it doesn't handle subpixel ends - or at least none of the versions I have ever seen did. Second, it does its logic one pixel at a time. Plot, test, plot, test, etc. But in practice you can do significantly better, especially for lines that are nearly horziontal or nearly vertical, and especially if you have some sort of hardware assistance for drawing horizontal or vertical lines (e.g. a blitter or a fast memset or whatever).
Now, Bresenham absolutely did think of this, and he later published the "run slice" version that does exactly what I'm going to describe, but so few people document it, so I thought I would. It is aso documented in Chapter 36 of Michael Abrash's Black Book: http://www.phatcode.net/res/224/files/html/ch36/36-01.html but he doesn't at the same time discuss subpixel lines, and I need both.
But I'm getting ahead of myself. If you don't know what Bresenham is (or even if you do! I see quite a few people mis-stating the algorithm and missing some of its genius), the Wikipedia article is decent, but here's a quick intro. It is just copy-pasted from comments in my C code, so apologies for strange phrasing.
For ease of thinking, assume the following:
- A coordinate system where X is right, Y is down (typical computer 2D "raster pattern" screen space)
- The line goes mostly right and a little down, so we always step right a pixel, and may or may not step down.
- We will have a preamble that flips signs and X/Y to ensure the above, and in the code I renamed them Big and Small instead of X and Y.
The distance from a point (xp,yp) to a line (x1,y1)...(x2,y2) is ((xp-x1)*(y2-y1)-(yp-y1)*(x2-x1))/((x2-x1)^2+(y2-y1)^2) Because of the above assumptions, the distance is positive above and to the right of the line, negative down and to the left. The second half is just dividing by the length of the line, and we don't care about actual magnitude of the this distance, we just want to minimise it. So we can just discard the divide-by-length bit and focus on making (xp-x1)*(y2-y1)-(yp-y1)*(x2-x1) as small as possible. For brevity, DeltaX=(x2-x1) and DeltaY=(y2-y1), so the distance formula is:
distance = (xp-x1)*DeltaY-(yp-y1)*DeltaX
Because of the assumptions above, DeltaX and DeltaY are both positive, and DeltaX>=DeltaY
So we start with the first pixel, which has a distance from the line. Since the line ends have subpixel precision, this will be small, but usually not zero. We step one pixel right. So xp goes up by 1. The distance formula is (xp-x1)*DeltaY-(yp-y1)*DeltaX, so because xp increments by one, the distance will increase by DeltaY The question is - do we also want to move down a pixel or not? We're trying to minimise the absolute distance. If we move down by one pixel, yp will increment, so the distance will decrease by DeltaX. Is this new value smaller or larger in absolute value? Logically if the current distance is more than than 0.5*DeltaX, then subtracting DeltaX will make its magnitude smaller (and maybe positive, maybe negative). If the current distance is less than 0.5*DeltaX, then subtracting DeltaX will make the magnitude larger (and certainly negative) (note the actual canonical Bresenham multiples everything by 2 to avoid testing against 0.5*DeltaBf, because it was designed for integer-only machines)
So the algorithm is:
distance = (DeltaY-DeltaX)*0.5f
For each horizontal pixel:
if ( distance > DeltaX*0.5 )
Step down a pixel
distance -= DeltaX
Draw the pixel
Step right a pixel
distance += DeltaY
This is the simple one-pixel-at-a-time Bresenham "run length" algorithm as seen in all the textbooks, though usually they bias by DeltaX*0.5 and multiply everything by 2 to avoid dealing with factors of 0.5, meaning the whole thing can be done with integers. I haven't done that here for clarity. Don't worry, we'll get to the optimal+integer part soon!
But I slipped something past you - where did that magical (DeltaY-DeltaX)*0.5f in the initial distance calculation come from? That's a good question, and you can either look up where I got that in Wikipedia, or you can hold on and I'll get to it soon, after explaining this next bit.
Why this is clever
I just want to pause and reflect on the particular points of genius of this algorithm:
-
It avoids division. On the CPUs of the time (1960s and 70s), division was agonisingly slow, so this is a big deal, especially for short lines.
-
It can be done entirely with integer arithmetic. Again, very important in the CPUs of the time, most of which didn't support floating-point, or did it very slowly. Even today there is a latency and power cost for using floating-point.
-
Even though it does the above two, it is exact. The only wiggle factor is whether you test with a >= or a >. Aside from that philosophical tie-break question, there's no interpretaion or precision tolerances needed - THIS IS THE RIGHT ANSWER. Always.
We regard graphics as rather "squishy" these days - everything is somewhat approximate, it's all "well, you know, floating point numbers, ULPs, approximations, etc". It's pleasingly cromulent to have a version of something graphical that has none of that fuzziness AND it's blazing fast.
Subpixel precision
I mentioned the subpixel end points problem - I want smoother-moving lines. That's going to be trickier, right? Well, it turns out not really - the core routine doesn't change, you just have to change the setup when you introduce fractional pixel coordinates. Note that I'm going to continue talking about everything using floating-point numbers for ease of explanation for the time being.
The first thing that changes is that of course DeltaX and DeltaY are now not integers, because the end points of the line are no longer at integer pixel values. You calculate them the same way, they're just not integers any more. Again, note the core loop doesn't change. What does change is the initial distance calculation. Instead of that magic thing I used before, you use the original definition of "distance to a line":
distance = (xp-x1)*DeltaY-(yp-y1)*DeltaX
For reasons that will become clear, I will flip orders and signs and rewrite this as:
distance = (y1-yp)*DeltaX-(x1-xp)*DeltaY
(x1,y1) is the start end of the line. (xp,yp) is the coordinate of the first pixel of the line. These are not the same thing because pixels are only on integer coordinates. A subtlety here is where you view the origin (the 0.0,0.0) point of a pixel to be - is it in the middle of the pixel, or is it at the top-left corner? This is a long and complicated philosophical question that many people have debated for a very long time, and the conclusion that everybody agrees on is that half of the people are wrong. My answer is that you treat the big square pixel (quiet there Alvy Ray Smith) that is nominally at (12,67) as going from (12.0000,67.0000) to (12.9999,67.9999), so the distance you really care about is to the center of that pixel, at 12.5, 67.5. If you choose the other option, I am totally comfortable with you being wrong, but you should adjust accordingly. This means the setup for the first pixel (xp,yp) on the line is this:
xp = floor(x1)
yp = floor(y1)
FracX = x1-xp; // this is always in the range [0.0...1.0)
FracY = y1-yp; // this is always in the range [0.0...1.0)
distance = (FracY-0.5)*DeltaX-(FracX-0.5)*DeltaY
...and then you do the exact same algorithm body as above.
So now you've seen the subpixel-accurate version, it should be obvious where the magic (DeltaY-DeltaX)*0.5f part above came from. When the endpoints don't have subpixel precision, FracX and FracY are both zero, simplify it all out and there you go.
Again, the actual canonical Bresenham algorithm offsets the distance by DeltaX*0.5 and multiplies everything by 2, and then it can work entirely in integer space. As I said - we'll get there, for now I'm still focusing on legibility, so we'll stay in floats.
Now we have subpixel lines, and they look buttery-smooth when moving and when approximating curves. Again, this is hard to show in a static image, but the picture at the top of this post shows the same Lissajous-like pattern with 2 bits, 1 bit, and zero bits of subpixel precision - if you look carefully you may be able to see the lines are less "lumpy" with even 2 bits of subpixel precision. In motion you can easily see the difference between 0, 2 and 4 bits, and anything above 6 bits is basically as butter-smooth as a non-AA line can be. For reference, DirectX and OpenGL specify 8 bits of subpixel precision from hardware renderers, so it doesn't take many bits to be "enough".
The Run-Slice algorithm
This is great, but we can improve performance in some cases, and sometimes be much better. The problem with this naive algorithm is that it works one pixel at a time, and does one or two increments and a test each time. But if the line is quite a bit wider than it is long, you will notice something - the "step down" test will fail in a specific pattern - it will fail for either N or N+1 pixels, then succeed once, then fail for either N or N+1 pixels, and so on. The pathological case is of course if DeltaY is very small, in which case the step-down never succeeeds - you just draw a horizontal line. So that means we're doing too much math & testing, and also if we have hardware that can quickly draw completely horizontal or vertical lines (i.e. blitters, fast memset routines, clever VGA registers, etc), we're not taking abvantage of it.
The trick is to refactor the above to figure out what N is, and then draw N pixels, THEN do an increment and test. This time, the test doesn't ask "do you step down a pixel" - you will always do that. Instead it asks "before you step down, do you need to draw an extra pixel across". So it's the extra X-step that is conditional, not the Y-step. If we calculate BigStep = (int)floor(DeltaX/DeltaY), we know that we always need to step AT LEAST that many pixels right, and the only decision is whether we step one more pixel, or not, before going down.
Bresenham absolutely did think of this, and he later published the "run slice" version, but few people document it. It is documented in Chapter 36 of Michael Abrash's Black Book: http://www.phatcode.net/res/224/files/html/ch36/36-01.html but he doesn't at the same time discuss subpixel lines.
So if you factor it all out, the new algorithm is:
distance = (FracY-0.5)*DeltaX-(FracX-0.5)*DeltaY
BigStep = (int)floor(DeltaX/DeltaY)
While more than BigStep pixels left to do
distance += BigStep*DeltaY; // Certainly stepping BigStep pixels right.
if ( distance > DeltaX*0.5 ) // but do we want to step another one?
Draw BigStep pixels
else
Draw BigStep+1 pixels
distance += DeltaY;
Step down a pixel
distance -= DeltaX
Note in this case we're still testing against DeltaX*0.5, but then conditionally ADD DeltaY instead of SUBTRACTING DeltaX. This is counter-intuitive, but it's the way the maths works out, so be careful not to confuse yourself!
Note that we often need to draw a short first and last horizontal segment, shorter than BigStep - I didn't show this code. We could calculate these lengths analytically, but it's almost always quicker to just step it out with regular Bresenham until we need to step down - so it's just the first version, but as soon as it steps down it exits.
Also because testing against DeltaX*0.5 is a pain, we pre-subtract that so we're always just testing against zero. And there's a bunch of other obvious optimisations like this as well. And then you realise that if you multiply everything by the amount of subpixel precision you want (e.g. 64 is usually more than enough for high quality, and 256 is super easy because it's a whole byte) then you don't need floating point at all, and everthing can be done in fixed-point integers.
The one downside of this run-slice algorithm is that you have added a divide, which on some CPUs is a significant speed problem. Depending on how fast your integer divide is, and how long your average line is, it may be quicker to do this "divide" using a for loop, or by testing each bit of the result yourself (i.e. the shift-test-conditional-add method). This decision must be guided by profiling, and there's no hard and fast rules here, so I've left this as an exercise for the reader on their specific choice of machine.
First and last pixels, and the diamond-exit rule
When rendering multiple lines, e.g. when drawing curves with a sequences of lines, it is common that we don't want to plot the first and last pixels for every line. This is similar to the fill rules for triangles, where you don't draw the bottom and right pixels, because you assume an adjacent triangle will hit them instead.
For lines there is a fairly complex rule for this called the "diamond-exit rule". I won't go into it here - look it up if you're interested. It is a very robust algorithm, but it's also a pain to do right, and for some lines it produces counter-intuitive results which can really annoy people. I have chosen to use a much simpler rule, which is just "first pxiel gets rendered, last pixel does not". This 99% matches the diamond-exit rule, but there are a few corner cases where it does not. Maybe one day I'll find a case where this matters visually and go chase it down, but for now I have left it as an exercise for the reader.
Some people don't like the "last pixel not rendered" rule - it's easy and obvious to change if you want.
Diagonal run-slice
Finally I should note an extra step that I have considered, and will get around to One Day For Sure.
The observation is that for nearly-diagonal lines - or rather for any line that is less than twice as wide as it is tall - BigStep is just 1. Which means that the inner loop always steps across 1, and sometimes two, then it steps down. Or to rephrase - it always steps down and across, but then sometimes also just steps across. And as the line gets steeper, it will have runs of lots of down-and-across, then one across, then lots of down-and-across, then one across, etc. So it's the same run-slice algorithm, except instead of stepping across by N or N+1, then down - it steps across and down by N or N+1, then it steps across.
Fascinating for sure. But why is this better? Well, for one thing, as with the original run-slice algo, it's fewer decisions, and that's always better. And another thing - if you have helper HW that can draw diagonal lines fast (not just horizontal and vertical lines) then this is great as well. Hardware like this is not as common, but it does exist, and as it happens I am looking at one at the moment, which prompted this thought.
So for lines whose slope is between 2:1 and 1:1 (which is roughly half of them), we could use this algorithm instead, and for lines with slopes between 2:1 and horizontal, use the original run-slice. The interesting thing here is the progression of how many tests you have to do per pixel plotted:
- Original Bresenham: 1 test per pixel.
- Run slice Bresenham: 1 test per 1-N pixels.
- Run slice diagonal Bresenham: 1 test per 2-N pixels.
So diagonal run-slice basically halves the number of tests per pixel of standard run-slice. I'll take it! I have not yet implemented this, and there's probably some annoying corner cases to deal with, so I wanted to post this before diving into the implementation, but I'll get to it eventually.
Source code
Here is some example source code of the three versions, including the preamble to turn everything into mostly-right-slightly-down lines. I made them write to a hypothetical byte-per-pixel raster display with a pitch of FramebufferStride, since that's a common type of display (e.g. VGA Mode 13h) for these algorithms, but it's fairly obvious where to splice in your own, and/or whatever graphics hardware you're looking at. Enjoy!
// 6 bits works great for a 320x240 screen and 16-bit integers.
// Larger screens may need to drop the number of bits or use wider integers.
int const BitsOfPrecision = 6;
enum DrawLineDebugMethodEnum
{
DLDME_BresenhamFloat,
DLDME_BresSliceFloat,
DLDME_BresSliceFixed,
} DrawLineDebugMethod = DLDME_BresSliceFixed;
void DrawLine ( int X1, int Y1, int X2, int Y2, unsigned char Colour )
{
int const PrecisionMask = (1<<BitsOfPrecision)-1;
int const FramebufferStride = <fill this in>;
int DeltaX = X2-X1;
int DeltaY = Y2-Y1;
// This is the first pixel's starting subpixel fraction.
// Note we ALWAYS start at X1,Y1 - to do correct line sequences we must draw the first pixel but NOT the last.
int FracX = X1 & PrecisionMask;
int FracY = Y1 & PrecisionMask;
// NOTE! you must do the subtract AFTER the shift or it'll all go wrong.
int X1W = X1 >> BitsOfPrecision;
int Y1W = Y1 >> BitsOfPrecision;
int PixelsToGoX = ( X2 >> BitsOfPrecision ) - ( X1W );
int PixelsToGoY = ( Y2 >> BitsOfPrecision ) - ( Y1W );
// We will now sort the line into 8 octants,
// and figure out the values into B(ig) and S(mall) distances,
// and also figure out the actual pixel deltas for a Big step and a Small step.
// The idea is that Big delta >= Small delta, and both are positive,
// and the pixel deltas actually tell you which direction (X or Y) and in which direction.
int DeltaB;
int DeltaS;
int FracB;
int FracS;
int PixelStepB; // = 1;
int PixelStepS; // = FramebufferStride;
int PixelsToGoB;
int PixelsToGoS;
if ( DeltaX >= 0 )
{
// Line goes right
if ( DeltaY >= 0 )
{
// Line goes right and down
DeltaB = DeltaX;
DeltaS = DeltaY;
FracB = FracX;
FracS = FracY;
PixelsToGoB = PixelsToGoX;
PixelsToGoS = PixelsToGoY;
PixelStepB = 1;
PixelStepS = FramebufferStride;
}
else
{
// Line goes right and up
DeltaB = DeltaX;
DeltaS = -DeltaY;
FracB = FracX;
FracS = PrecisionMask-FracY;
PixelsToGoB = PixelsToGoX;
PixelsToGoS = -PixelsToGoY;
PixelStepB = 1;
PixelStepS = -FramebufferStride;
}
}
else
{
// Line goes left
if ( DeltaY >= 0 )
{
// Line goes left and down
DeltaB = -DeltaX;
DeltaS = DeltaY;
FracB = PrecisionMask-FracX;
FracS = FracY;
PixelsToGoB = -PixelsToGoX;
PixelsToGoS = PixelsToGoY;
PixelStepB = -1;
PixelStepS = FramebufferStride;
}
else
{
// Line goes left and up
DeltaB = -DeltaX;
DeltaS = -DeltaY;
FracB = PrecisionMask-FracX;
FracS = PrecisionMask-FracY;
PixelsToGoB = -PixelsToGoX;
PixelsToGoS = -PixelsToGoY;
PixelStepB = -1;
PixelStepS = -FramebufferStride;
}
}
ASSERT ( DeltaB >= 0 );
ASSERT ( DeltaS >= 0 );
ASSERT ( FracB >= 0 );
ASSERT ( FracS >= 0 );
ASSERT ( PixelsToGoB >= 0 );
ASSERT ( PixelsToGoS >= 0 );
if ( DeltaB < DeltaS )
{
// Line is more up/down than right/left, so swap everything around.
// A big subtlety here is that due to subpixel snapping, even though we make sure DeltaB >= DeltaS,
// you can get cases where PixelsToGoS is LESS THAN PixelsToGoB. Pretty freaky eh?
// However in those cases the first pixel "stripe" is zero-length, so the very first thing it does is step down,
// and that deals witht he extra pixel in the S direction without "using" pixels in the B direction.
int Temp;
Temp = DeltaB; DeltaB = DeltaS; DeltaS = Temp;
Temp = FracB; FracB = FracS; FracS = Temp;
Temp = PixelsToGoB; PixelsToGoB = PixelsToGoS; PixelsToGoS = Temp;
Temp = PixelStepB; PixelStepB = PixelStepS; PixelStepS = Temp;
}
if ( PixelsToGoB > 0 )
{
// For ease of thinking, assume the following:
// A coordinate system where X is right, Y is *down* (typical computer 2D "raster pattern" screen space)
// The line goes mostly right and a little down, so we always step right a pixel, and may or may not step down.
// We will have a preamble that flips signs and X/Y to ensure the above, and in the code I renamed them Big and Small instead of X and Y.
//
// The distance from a point (xp,yp) to a line (x1,y1)...(x2,y2) is ((xp-x1)*(y2-y1)-(yp-y1)*(x2-x1))/((x2-x1)^2+(y2-y1)^2)
// Because of the above assumptions, the distance is positive above and to the right of the line, negative down and to the left.
// The second half is just dividing by the length of the line, and we don't care about actual magnitude of the this distance, we just want to minimise it.
// So we can just discard the divide-by-length bit and focus on making (xp-x1)*(y2-y1)-(yp-y1)*(x2-x1) as small as possible.
// For brevity, DeltaX=(x2-x1) and DeltaY=(y2-y1), so the distance formula is (xp-x1)*DeltaY-(yp-y1)*DeltaX
// Because of the assumptions above, this means DeltaX and DeltaY are both positive, and DeltaX>=DeltaY
//
// So we start with the first pixel, which has a distance from the line. Since the line ends have subpixel precision, this will be small, but usually not zero.
// We step one pixel right. So xp goes up by 1. The distance formula is (xp-x1)*DeltaY-(yp-y1)*DeltaX, so because xp increments by one, the distance will increase by DeltaY
// The question is - do we also want to move down a pixel or not? We're trying to minimise the absolute distance.
// If we move down by one pixel, yp will increment, so the distance will decrease by DeltaX. Is this new value smaller or larger in *absolute* value?
// Logically if the current distance is more than than 0.5*DeltaX, then subtracting DeltaX will make its magnitude smaller (and maybe positive, maybe negative).
// If the current distance is less than 0.5*DeltaX, then subtracting DeltaX will make the magnitude larger (and certainly negative)
//
// So the algorithm is:
//
// Figure out the distance of the first pixel from the line using the full equation.
// For each horizontal pixel:
// if ( distance > DeltaX*0.5 )
// Step down a pixel
// distance -= DeltaX
// Draw the pixel
// Step right a pixel
// distance += DeltaY
//
// This is simple one-pixel-at-a-time Bresenham.
//
// But we can do better. Because the line goes mostly-right-and-sometimes-down, DeltaX is larger than DeltaY, and often quite a bit larger.
// So if we calculate BigStep = (int)floor(DeltaX/DeltaY), we know that we always need to step AT LEAST that many pixels right,
// and the only decision is whether we step one more, or not, before going down.
//
// Bresenham absolutely did think of this, and he later published the "run slice" version that does exactly this, but few people document it.
// It is well-documented in Chapter 36 of Michael Abrash's Black Book: http://www.phatcode.net/res/224/files/html/ch36/36-01.html
// but he doesn't at the same time discuss subpixel lines
//
// So if you factor it all out, the new algorithm is:
//
// Figure out the distance of the first pixel from the line using the full equation.
// BigStep = (int)floor(DeltaX/DeltaY)
// While more than BigStep pixels left to do:
// distance += BigStep*DeltaY; // Certainly stepping BigStep pixels right.
// if ( distance > DeltaX*0.5 ) // but do we want to step another one?
// Draw BigStep pixels
// else
// Draw BigStep+1 pixels
// distance += DeltaY;
// Step down a pixel
// distance -= DeltaX
//
// Note that we might need to draw a short first horizontal segment, shorter than BigStep. We could calculate this length analytically,
// but it's almost always quicker to just step it out with regular Bresenham until we need to step down.
//
// Also because testing against DeltaX*0.5 is a pain, we pre-subtract that so we're alwasy just testing against zero.
// And there's a bunch of other obvious optimisations like this as well.
// And then you realise you don't need floating point at all, and everthing can be done in integers!
if ( DrawLineDebugMethod == DLDME_BresenhamFloat )
{
// Simple pixel-by-pixel vanilla Bresenham.
// Do it all in floating point for ease of checking.
int PixelsToGo = PixelsToGoB;
float const PrecisionF = (float)( 1 << BitsOfPrecision );
float DeltaBf = (float)DeltaB / PrecisionF;
float DeltaSf = (float)DeltaS / PrecisionF;
float FracBf = (float)FracB / PrecisionF;
float FracSf = (float)FracS / PrecisionF;
ASSERT ( DeltaBf >= 0.0f );
ASSERT ( DeltaSf >= 0.0f );
ASSERT ( FracBf >= 0.0f );
ASSERT ( FracSf >= 0.0f );
// Start in the right subpixel place.
// However because we treat the big square pixel (12,67) as going from (12.0000,67.0000) to (12.9999,67.9999),
// the actual distance we want is to the MIDDLE of that square blob.
// Also note the equation above is: (xp-x1)*DeltaY-(yp-y1)*DeltaX
// ...but it's easier if you rewrite as: (y1-yp)*DeltaX-(x1-xp)*DeltaY
// ...and then notice that (y1-yp)=FracY and (x1-xp)=FracX.
float Distf = ( ( FracSf - 0.5f ) * DeltaBf ) - ( ( FracBf - 0.5f ) * DeltaSf );
// (note actual canonical Bresenham subtracts 0.5*DeltaBf and then multiples everything by 2 so it can test against 0)
unsigned char *CurPixAddr = GetFB ( X1W, Y1W );
bool FirstPixel = true;
while ( PixelsToGo > 0 )
{
if ( Distf > ( DeltaBf * 0.5f ) )
{
CurPixAddr += PixelStepS;
Distf -= DeltaBf;
}
// Little note here - the "first pixel" exception is a very rare case when the slope is pretty steep
// and the subpixel start is all the way in the top-right of the first pixel.
// In this case the very first pixel will be "too far" from the line.
// If we were STRICTLY following the "diamond-exit" rule we shouldn't draw this pixel,
// and it should have been drawn by the previous line. However, this aspect of the rule really annoys
// people and they moan about bugs, so I'm not going to follow it to the letter.
ASSERT ( ( Distf >= ( -DeltaBf * 0.5f ) ) && ( Distf <= ( DeltaBf * 0.5f ) ) || FirstPixel );
*CurPixAddr = Colour;
CurPixAddr += PixelStepB;
Distf += DeltaSf;
PixelsToGo--;
FirstPixel = false;
}
}
else if ( DrawLineDebugMethod == DLDME_BresSliceFloat )
{
float const PrecisionF = (float)( 1 << BitsOfPrecision );
// Do it all in floating point for ease of checking.
// Note - there are a number of optimisations NOT done here, to preserve the readability.
// I have noted most of them. They ARE applied to the fixed-point version.
int PixelsToGo = PixelsToGoB;
float DeltaBf = (float)DeltaB / PrecisionF;
float DeltaSf = (float)DeltaS / PrecisionF;
float FracBf = (float)FracB / PrecisionF;
float FracSf = (float)FracS / PrecisionF;
ASSERT ( DeltaBf >= 0.0f );
ASSERT ( DeltaSf >= 0.0f );
int BigStep = (int)floor(DeltaBf);
if ( DeltaSf > 0.0f )
{
BigStep = (int)floor(DeltaBf/DeltaSf);
}
ASSERT ( FracBf >= 0.0f );
ASSERT ( FracSf >= 0.0f );
// Start in the right subpixel place.
// However because we treat the big square pixel (12,67) as going from (12.0000,67.0000) to (12.9999,67.9999),
// the actual distance we want is to the MIDDLE of that square blob.
float Distf = ( DeltaBf * ( FracSf - 0.5f ) ) - ( DeltaSf * ( FracBf - 0.5f ) );
// Now offset by 0.5*DeltaX as described above, so we can just test against zero.
Distf -= DeltaBf * 0.5f; // you can fold this into the line above of course - here for illustration.
unsigned char *CurPixAddr = GetFB ( X1W, Y1W );
// First short segment - note that there are cases where we don't draw the first pixel before stepping down!
int FirstStep = 0;
while ( ( Distf <= 0.0f ) && ( PixelsToGo > 0 ) )
{
FirstStep++;
Distf += DeltaSf;
PixelsToGo--;
}
for ( int i = 0; i < FirstStep; i++ )
{
*CurPixAddr = Colour;
CurPixAddr += PixelStepB;
}
Distf -= DeltaBf;
CurPixAddr += PixelStepS;
if( PixelsToGo > 0 )
{
float StepDistf = DeltaSf * (float)BigStep;
ASSERT ( ( ( StepDistf <= DeltaBf ) && ( StepDistf + DeltaSf >= DeltaBf ) ) || ( DeltaSf == 0 ) );
// Optimisation - you can combine the two adds in the loop into a single add of (StepDistf - DeltaBf) and here pre-add DeltaBf
while ( true )
{
ASSERT ( ( Distf <= 0.0f ) && ( Distf >= -DeltaBf ) );
int StepSize = BigStep;
Distf += StepDistf;
if ( Distf > 0.0f )
{
StepSize = BigStep;
}
else
{
StepSize = BigStep + 1;
Distf += DeltaSf;
}
Distf -= DeltaBf;
ASSERT ( ( Distf >= -DeltaBf ) && ( Distf <= 0.0f ) );
// Actually draw the pixels.
if ( PixelsToGo <= StepSize )
{
// Oops! Hit the end of the line
break;
}
PixelsToGo -= StepSize;
for ( int i = 0; i < StepSize; i++ )
{
*CurPixAddr = Colour;
CurPixAddr += PixelStepB;
}
CurPixAddr += PixelStepS;
}
// Finish off the last segment.
for ( int i = 0; i < PixelsToGo; i++ )
{
*CurPixAddr = Colour;
CurPixAddr += PixelStepB;
}
}
}
else if ( DrawLineDebugMethod == DLDME_BresSliceFixed )
{
// Old-school fixed point!
int PixelsToGo = PixelsToGoB;
unsigned char *CurPixAddr = GetFB ( X1W, Y1W );
if ( PixelsToGoS == 0 )
{
// The best thinking is no thinking - this is a pure horizontal/vertical line.
// As well as being common just because people like to draw them,
// they're also surprisingly common cases for short "general" lines.
for ( int i = 0; i < PixelsToGo; i++ )
{
*CurPixAddr = Colour;
CurPixAddr += PixelStepB;
}
}
else
{
// If there are no bits of precision, we need to effectively add one, because otherwise "PrecisionHalf" has nowhere to go!
// In the original Bresenham algorithm, this corresponds to multiplying everything by two,
// but here we only need to do that if there is actually ZERO bits of subpixel precision.
int const LocalBitsOfPrecision = ( BitsOfPrecision == 0 ) ? 1 : BitsOfPrecision;
int const PrecisionOne = (1<<LocalBitsOfPrecision);
int const PrecisionHalf = (PrecisionOne >> 1);
ASSERT ( DeltaB >= 0 );
ASSERT ( DeltaS >= 0 );
int BigStep = DeltaB >> LocalBitsOfPrecision;
int StepDist = DeltaB;
if ( DeltaS > 0 )
{
// NOTE - depending on your CPU and your average line length,
// it may be quicker to just step this out in a for loop, or do it bit-by-bit, than actually do the integer divide.
BigStep = DeltaB / DeltaS;
StepDist = BigStep * DeltaS;
}
ASSERT ( FracB >= 0 );
ASSERT ( FracS >= 0 );
// (fun subtlety - if we jimmied LocalBitsOfPrecision to be 1 instead of 0, we should have to
// shift FracB and FracS left by one. But if BitsOfPrecision is zero, then by definition they are both 0 :-)
// Start in the right subpixel place.
// However because we treat the big square pixel (12,67) as going from (12.0000,67.0000) to (12.9999,67.9999),
// the actual distance we want is to the MIDDLE of that square blob.
#if 0
// Also remember that "Dist" is the size of TWO chunks of "Precision" bits
int Dist = ( DeltaB * ( FracS - PrecisionHalf ) ) - ( DeltaS * ( FracB - PrecisionHalf ) );
// Now offset by 0.5*DeltaX as described above, so we can just test against zero.
Dist -= ( DeltaB << ( LocalBitsOfPrecision - 1 ) );
#else
// Minor optimisation of above...
int Dist = ( DeltaB * ( FracS - PrecisionOne ) ) - ( DeltaS * ( FracB - PrecisionHalf ) );
#endif
// We need versions of these, shifted up by the subpixel precision amount.
int DeltaBPrec = DeltaB << LocalBitsOfPrecision;
int DeltaSPrec = DeltaS << LocalBitsOfPrecision;
int StepDistPrec = StepDist << LocalBitsOfPrecision;
// First short segment
int FirstStep = 0;
while ( ( Dist <= 0 ) && ( PixelsToGo > 0 ) )
{
FirstStep++;
Dist += DeltaSPrec;
PixelsToGo--;
}
for ( int i = 0; i < FirstStep; i++ )
{
*CurPixAddr = Colour;
CurPixAddr += PixelStepB;
}
CurPixAddr += PixelStepS;
if ( PixelsToGo > 0 )
{
Dist -= DeltaBPrec;
ASSERT ( ( ( StepDistPrec <= DeltaBPrec ) && ( StepDistPrec + DeltaSPrec >= DeltaBPrec ) ) || ( DeltaS == 0 ) );
int StepDistMinusDeltaBPrec = StepDistPrec - DeltaBPrec;
Dist += DeltaBPrec;
while ( true )
{
int StepSize = BigStep;
Dist += StepDistMinusDeltaBPrec;
if ( Dist <= 0 )
{
StepSize = BigStep + 1;
Dist += DeltaSPrec;
}
// Actually draw the pixels.
int PixelsToGoBNew = PixelsToGo - StepSize;
if ( PixelsToGoBNew <= 0 )
{
// Oops! Hit the end of the line
break;
}
PixelsToGo = PixelsToGoBNew;
for ( int i = 0; i < StepSize; i++ )
{
*CurPixAddr = Colour;
CurPixAddr += PixelStepB;
}
CurPixAddr += PixelStepS;
}
// Finish off the last segment.
for ( int i = 0; i < PixelsToGo; i++ )
{
*CurPixAddr = Colour;
CurPixAddr += PixelStepB;
}
}
}
}
}
}
[edits - typos and also maybe spell Bresenham right - sorry about that!]
from Hacker News https://ift.tt/Pi3ef6H
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.