Aka the way to digitally draw a line between two points
- uses only integer addition, subtraction, and bit shifting
- derived from y = mx + b, in a way
![[600px-Bresenham.svg.png]]
http://members.chello.at/~easyfilter/bresenham.html / http://members.chello.at/~easyfilter/Bresenham.pdf
https://www.javatpoint.com/computer-graphics-bresenhams-line-algorithm
FPGA implementation: https://projectf.io/posts/lines-and-triangles/
```verilog
always_ff @(posedge clk) begin
case (state)
DRAW: begin
if (x == x1 && y == y1) begin
done <= 1;
state <= IDLE;
end else begin
if (movx) x <= right ? x + 1 : x - 1;
if (movy) y <= down ? y + 1 : y - 1;
err <= err + derr;
end
end
default: begin // IDLE
done <= 0;
if (start) begin
err <= dx + dy;
x <= x0;
y <= y0;
state <= DRAW;
end
end
endcase
```
## In Amaranth
```python
class LineDrawer(Elaboratable):
def __init__(self):
self.x0 = Signal(8)
self.y0 = Signal(8)
self.x1 = Signal(8)
self.y1 = Signal(8)
self.x = Signal(8)
self.y = Signal(8)
self.dx = Signal(range(-255,255))
self.dy = Signal(range(-255,255))
self.err = Signal(range(-255,255))
self.movx = Signal()
self.movy = Signal()
self.right = Signal()
self.down = Signal()
def elaborate(self, platform):
m = Module()
m.d.comb += self.movx.eq(2*self.err >= self.dy)
m.d.comb += self.movy.eq(2*self.err <= self.dx)
m.d.comb += self.right.eq(self.x0 < self.x1)
m.d.comb += self.down.eq(self.y0 < self.y1)
m.d.comb += self.dx.eq(abs(self.x1 - self.x0))
m.d.comb += self.dy.eq(-abs(self.y1 - self.y0))
with m.FSM() as fsm:
with m.State("Start"):
m.d.sync += self.x.eq(self.x0)
m.d.sync += self.y.eq(self.y0)
m.next = "Draw"
with m.State("Draw"):
with m.If((self.movx) & (self.movy)):
m.d.sync += self.err.eq(self.err + self.dx + self.dy)
with m.If(self.right):
m.d.sync += self.x.eq(self.x + 1)
with m.Else():
m.d.sync += self.x.eq(self.x - 1)
with m.If(self.down):
m.d.sync += self.y.eq(self.y + 1)
with m.Else():
m.d.sync += self.y.eq(self.y - 1)
with m.If((self.movx) & ~(self.movy)):
m.d.sync += self.err.eq(self.err + self.dy)
with m.If(self.right):
m.d.sync += self.x.eq(self.x0 + 1)
with m.Else():
m.d.sync += self.x.eq(self.x0 - 1)
with m.If(~(self.movx) & (self.movy)):
m.d.sync += self.err.eq(self.err + self.dx)
with m.If(self.down):
m.d.sync += self.y.eq(self.y + 1)
with m.Else():
m.d.sync += self.y.eq(self.y - 1)
return m
```