I don't know why I struggled months ago when I was first attempting Bresenham. Maybe I was trying to implement one of the unoptimized formula's. But it only took me an hour to get the example on the wiki to work, outputting the correct coordinates. I'll have to add a 'LOAD' input signal to this module, and an output 'DONE' signal, which will go to set one of the unused cpu flag bits. So far this is a separate module not part of the project yet, and I still have to add checks for the other slopes. This implementation uses 75 slice registers, 117 slice LUTs and 55 LUT FF pairs. Each pixel coordinate takes 2 cycles:
Code:
module LineGen ( input clk,
output reg [9:0] X = 0,
output reg [8:0] Y = 0
);
reg [9:0] x0;
reg [8:0] y0;
reg [9:0] x1;
reg [8:0] y1;
reg [9:0] dx;
reg [8:0] dy;
reg [16:0] D;
reg [2:0] state;
parameter LOAD = 0, CALC1 = 1, CALC2 = 2, PLOT = 3;
always @(posedge clk) begin
state <= LOAD;
case (state)
LOAD:
state <= CALC1;
CALC1:
state <= CALC2;
CALC2:
state <= PLOT;
PLOT:
if ( x0+1 <= x1 )
state <= CALC2;
else
state <= LOAD;
endcase
end
always @(posedge clk) begin
case (state)
LOAD:
begin
x0 <= 0;
y0 <= 1;
x1 <= 6;
y1 <= 4;
end
CALC1:
begin
X <= x0;
Y <= y0;
dx <= x1 - x0;
dy <= y1 - y0;
D <= y1*2 - y0*2 - x1 + x0;
end
CALC2:
if ( D[16] == 0 ) begin
x0 <= x0 + 1;
y0 <= y0 + 1;
D <= D + dy*2 - dx*2;
end
else begin
x0 <= x0 + 1;
D <= D + dy*2;
end
PLOT:
begin
X <= x0;
Y <= y0;
end
endcase
end
endmodule
EDIT: Fixed the detect when D goes negative. Seems to work only when DX>DY.