# drawLine and clipLine bugs

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?

@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.

It’s kind of hard to explain.

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

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.

1 Like

PR ready:

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.

2 Likes

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.

3 Likes

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

1 Like

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`