diagram.png
[Hide] (5.6KB, 178x229) I don't know where to post this, so here goes.
A division-free DDA algorithm (WIP)
(This is the TL;DR version, so if Anons want me to go into more detail, then just let me know.)
Before developing this algorithm, I was working on designing a simple GPU for an FPGA board of mine. However, one of the challenges was implementing DDA. Since division (and to a lesser extent multiplication) are both expensive in hardware, I thought of coming up with another solution.
Reviewing the principles behind the Bresenham Line Algorithm, you can easily take a line (or any other linear values needing interpolation hint hint) and plot values using only addition and subtraction.
The BLA works by approximating the distance from pixels to a line and choosing the closest pixel to a line. By decomposing the line equation, it is possible to obtain a distance value from the line for each pixel that can be stepped and calculated by adding or subtracting dx or dy. Let me explain in detail:
Line equation:
y = (dy/dx)*x
y = (dy*x)/dx
dx*y = dy*x
0 = dy*x - dx*y
f(x,y) = dy*x - dx*y
f(x+1,y) - f(x,y) = dy
f(x,y+1) - f(x,y) = -dx
So, you can calculate a distance from a point to a line by simply adding or subtracting the deltas for the x and y points.
While this may seem obvious, the approximate points to draw the line are the values that produce a distance closest to 0. This means that by using a simple absolute value comparison, it can be possible to approximate points on a line without using any division at all. (see the diagram for more information)
Here's some code demonstrating how the interpolation algorithm implementation works:
int dx = x1 - x0, dy = y1 - y0;
int dist = 0;
for(int y = y0, x = x0; x <= x1; x++)
{
while(abs(dist - dx) < abs(dist))
{ y++; dist -= dx; }
dist += dy;
plot(x, y);
}
And here's some code I wrote for Processing (>inb4 babby language) that demonstrates the interpolation being used in a line drawing algorithm:
void sw_line(int x0, int y0, int x1, int y1)
{
int dx = abs(x1-x0), dy = abs(y1-y0);
int sx = x1 > x0 ? 1 : -1;
int sy = y1 > y0 ? 1 : -1;
int dm = dx > dy ? dx : dy;
int distX = 0, distY = 0;
for(int x = x0, y = y0;;)
{
while(abs(distY-dm)<abs(distY))
{ y += sy; distY -= dm; }
distY += dy;
while(abs(distX-dm)<abs(distX))
{ x += sx; distX -= dm; }
distX += dx;
point(x,y);
if(x == x1 && y == y1) { break; }
}
}
void setup()
{
size(200,200);
noSmooth();
}
void draw()
{
background(0);
stroke(255,0,0);
line(100,100,mouseX,mouseY);
stroke(0,255,0);
sw_line(100,100,mouseX,mouseY);
}
Sadly, as you may see, the algorithm is not entirely perfect. If you look at some parts of the line closely, you'll see some red pixels showing errors between Processing's line drawing implementation and mine. I'm not entirely sure what causes this. Nonetheless, I still think it's accurate enough for a simple hobby GPU, so I hope this writeup has been useful to Anons out there.