Linear interpolation along the Breschenham line

Question

I use linear interpolation to animate an object between two 2d coordinates on the screen. This is very close to what I want, but due to rounding I get a jagged movement. In ASCII text:

ooo ooo ooo oo 

Notice how he walks in the Manhattan grid, instead of taking turns of 45 degrees. What I would like is linear interpolation along the line that the Breshenem algorithm could create:

 oo oo oo oo 

For each x, there is only one corresponding y. (And change x / y to a cool line)

So why don't I just use the Breshenem algorithm? Of course, I could, but this algorithm is iterative, and I would like to know only one coordinate along the line.

I will try to solve this by linearly interpolating the x coordinate, rounding it to a pixel grid, and then finding the corresponding y. (Again, swap x / y for steep lines). Regardless of how this decision comes out, I would be interested in another proposal and, possibly, previous experience.

Answer 1

The Breshenem algorithm for lines was introduced in order to draw a complete line a little faster than conventional approaches. It has two main advantages:

• It works with integer variables.
• It works iteratively, which is fast when drawing a full line

The first advantage is not very much if you are only calculating some coordinates. The second advantage is as a disadvantage in calculating only certain coordinates. In the end, there is no need to use the Bresenem algorithm.

Instead, you can use a different algorithm that results in the same string. For example, DDA (Digital Differential Analyzer). This is basically the same approach you were talking about.

First step: calculate the slope.

 m = (y_end - y_start) / (x_end - x_start) 

Second step: calculate the iteration step, which is simple:

 i = x - x_start 

Third step: Calculate the corresponding y value:

 y = y_start + i * m = y_start + (x - x_start) * (y_end - y_start) / (x_end - x_start) 

Answer 2

In this solution, I ended up:

 public static Vector2 BresenhamLerp(Vector2 a, Vector2 b, float percent) { if (ax == bx || Math.Abs(ax - bx) < Math.Abs(ay - by)) { // Didn't do this part yet. Basically, we just need to recurse // with x/y swapped and swap result on return } Vector2 result; result.x = Math.Round((1-percent) * ax + percent * bx); float adjustedPercent = (result.x - ax + 0.5f) / (bx - ax); result.y = Math.Round((1-adjustedPercent) * ay + adjustedPercent * by); return result; } 

Answer 3

This is what I just realized will work. These are probably not the most beautiful interpolations, but these are just 1-2 float additions to iterate on the line with a one-time preliminary calculation. It works by calculating the number of steps on the Manhattan matrix.

Ah, and he has not yet caught the case where the line is vertical (dx = 0)

This is a naive brashenham, but iterations can theoretically only use integers. If you want to get rid of the color value of the float, things will get complicated, because the line may be longer than the color difference, so delta-color <1.

 void Brepolate( uint8_t* pColorBuffer, uint8_t cs, float xs, float ys, float zs, uint8_t ce, float xe, float ye, float ze ) { float nColSteps = (xe - xs) + (ye - ys); float fColInc = ((float)cs - (float)ce) / nColSteps; float fCol = cs; float dx = xe - xs; float dy = ye - ys; float fCol = cs; if (dx > 0.5) { float de = fabs( dy / dx ); float re = de - 0.5f; uint32_t iY = ys; uint32_t iX; for ( uint32_t iX = xs; iX <= xe; iX++ ) { uint32_t off = surf.Offset( iX, iY ); pColorBuffer[off] = fCol; re += de; if (re >= 0.5f) { iY++; re -= 1.0f; fCol += fColInc; } fCol += fColInc; } } }