 drawLine and clipLine bugs

#1

I’m currently trying to handle the bug reported by @HomineLudens in Issue # 31.

I’ve currently got it working as this:

void Display::drawLine(int16_t x0, int16_t y0, int16_t x1, int16_t y1) {
if (x0 == x1)
drawColumn(x0, y0, y1);
else if (y0 == y1)
drawRow(x0, x1, y0);
else {

signed int dx = 0;
signed char s1 = 0;

//take absolute value
if (x1 < x0) {
dx = x0 - x1;
s1 = -1;
}
else if (x1 == x0) {
dx = 0;
s1 = 0;
}
else {
dx = x1 - x0;
s1 = 1;
}

signed int dy = 0;
int_fast8_t s2 = 0;

if (y1 < y0) {
dy = y0 - y1;
s2 = -1;
}
else if (y1 == y0) {
dy = 0;
s2 = 0;
}
else {
dy = y1 - y0;
s2 = 1;
}

bool xchange = false;

if (dy > dx) {
int temp = dx;
dx = dy;
dy = temp;
xchange = true;

}

int e = ((int)dy << 1) - dx;

signed int x = x0;
signed int y = y0;

for (int j = 0; j <= dx; ++j) {
if((x < 0 || x >= width) || (y < 0 || y >= height))
break;

drawPixel(x, y);

if (e >= 0) {
if (xchange)
x += s1;
else
y += s2;

e -= ((int)dx << 1);
}

if (xchange)
y += s2;
else
x += s1;

e += ((int)dy << 1);
}
}
}

That’s probably going to be too slow to be the final version.
(I don’t know how fast it is, I don’t know what the best way to speed test is.)

I’m currently trying to think of some alternatives.
I know the obvious one is to limit dx and dy,
but the problem lies in getting the slope to match up
(i.e. if you subtract from dx you have to subtract a proportionate amount from dy.)

Anyone got any ideas?

#2

@HomineLudens and @Pharap you do not explain what is the nature of the bug

Why I am saying this is because way my brain works I can put the “kettle on” as soon as I hear the problem. Many times I have a solution/strong idea even before I start looking at the code. Now I need to wait until I have time to try and discover the bug myself.

Minor detail but still.

#3

It’s kind of hard to explain.

Essentially the slope isn’t calculated correctly for lines beyond a certain length.

#4

Aha, I got it working.

I changed the UQ8.8 fixed point arithmetic to UQ16.16.

uint8_t Display::clipLine(int16_t *x0, int16_t *y0, int16_t *x1, int16_t *y1){
// Check X bounds
if (*x1<*x0) {
//std::swap (*x1,*x0); // swap so that we dont have to check x1 also
swapWT(int16_t*,x1,x0);
//std::swap (*y1,*y0); // y needs to be swaaped also
swapWT(int16_t*,y1,y0);
}

if (*x0>=width) return 0; // whole line is out of bounds

// Clip against X0 = 0
if (*x0 < 0) {
if ( *x1 < 0) return 0; // nothing visible
int32_t dx = (*x1 - *x0);
int32_t dy = ((*y1 - *y0) << 16); // 8.8 fixed point calculation trick
int32_t m = dy/dx;
*y0 = *y0 + ((m*-*x0)>>16); // get y0 at boundary
*x0 = 0;
}

// Clip against x1 = 83
if (*x1 >= width) {
int32_t dx = (*x1 - *x0);
int32_t dy = ((*y1 - *y0) << 16); // 8.8 fixed point calculation trick
int32_t m = dy/dx;
//*y1 = *y1 + ((m*(*x1-XMAX))>>8); // get y0 at boundary
*y1 = *y1 + ((m*(width-1-*x1))>>16); // get y0 at boundary
*x1 = width-1;
}

// Check Y bounds
if (*y1<*y0) {
//std::swap (*x1,*x0); // swap so that we dont have to check x1 also
swapWT(int16_t*,x1,x0);
//std::swap (*y1,*y0); // y needs to be swaaped also
swapWT(int16_t*,y1,y0);
}

if (*y0>=height) return 0; // whole line is out of bounds

if (*y0 < 0) {
if ( *y1 < 0) return 0; // nothing visible
int32_t dx = (*x1 - *x0) << 16;
int32_t dy = (*y1 - *y0); // 8.8 fixed point calculation trick
int32_t m = dx/dy;
*x0 = *x0 + ((m*-*y0)>>16); // get x0 at boundary
*y0 = 0;
}

// Clip against y1 = 47
if (*y1 >= height) {
int32_t dx = (*x1 - *x0) << 16;
int32_t dy = (*y1 - *y0); // 8.8 fixed point calculation trick
int32_t m = dx/dy;
*x1 = *x1 + ((m*(height-1-*y1))>>16); // get y0 at boundary
//*x1 = *x1 + ((m*(*y1-YMAX))>>8); // get y0 at boundary
*y1 = height-1;
}
return 1; // clipped succesfully
}

I’ll get a branch ready.

#5

I had thought of changing the 8.8 for 16.16 earlier, but I decided to try to understand how Bresenham’s algorithm worked and tried to implement an alternative to clipLine.

So I ended up wasting a load of time trying to be clever when I should have just followed my gut instinct.

Long story short:
I found a fix, but I still don’t understand how Bresenham’s algorithm works.

#6

Its very simple. A line is an infinite set of points. However, a display is not. Bresenham works by determining the distance from the current point to the closest edge of next pixel (is it a step in x-direction or y-direction), then steps and makes the same determination again. Think of two “weights” snapping the line to next pixel in x or y direction. If the line is steep (for example 3 y-pixels in comparison to 1 x-pixel) it takes 3 steps before the x-weight passes the y-weight. The line then makes a x-step, the x-weight falls to zero and the process begins again.

#7

Thanks @pherap this was stopping on one of my WIP.

#8

I get the abstract idea, but it’s the specifics I fall down at, mainly around the ‘weights’.

I think I’d have to sit down and play around with the numbers and do it manually a few times before I truly comprehended it.

There’s a lot going on in the algorithm because of the number of different cases it has to cover.
I’m sure I’ll understand it one day, it’s just a matter of sitting down and working through the maths.

(Also I just realised I’ve had this typed out for ~2 hours and I forgot to hit send. Oops. :P)

No problem @humoneloduns :P