bresenham算法的FPGA的实现1
0赞
发表于 2014/10/23 14:18:47
阅读(1544)
接着上一篇的 计算实现给出屏幕上任意两个点,求出这两个点之间直线上的所有的点。http://www.cnblogs.com/sepeng/p/4042464.html 这种直接算法的确是被鄙视了
强大的度娘告诉我们还有专用的算法叫bresenham算法。调用我大脑中所有的数学知识残留借用网上资料,费尽了吃奶的力气才把这个算法推导了一遍,高手们不要笑话
后来觉得这个时候讨论的是 0<k<1.那么把pi换一换就是 -1<k<0.仿真后发现自己又脑残了一次,对算法知之甚少,组合了好几次都没有组合成功,最后不得不把-1<k<0的算法拿出来讨论
这次才知道-1<k<0的时候 pi,xi 长啥样子,我的大脑还是猜不出来的,老老实实的推导算法吧。
算法推导出来了,这下好了就开始写FPGA的实现了
/* date:2014/10/22 version : QuartusII + de1-soc cyclone V designer : pengxiaoen funtion : 实现bresenham 算法在象限对直线的计算 |k| <1 任意方向都满足 */ module bresenham ( clock , reset , xs_in , //输入的X 点的起始坐标 ys_in , // 输入的Y 点的起始坐标 xe_in , //输入X点的终止坐标 ye_in , //输入Y 点的终止坐标 in_en , //当前输入信号有效标志 1:有效 0:无效 x_ou, //输出的X 点的坐标 y_ou, // 输出的Y 点的坐标 fini_flag //计算完成标志位 ); input clock ,reset ; input in_en ; input [9:0] xs_in ,xe_in ; input [8:0] ys_in ,ye_in ; output reg [9:0] x_ou ; output reg [8:0] y_ou ; output reg fini_flag ; wire [15:0] dx ; // X方向上的变化量 wire [15:0] dy ; //Y方向上的变化量 reg signed [15:0] pi ; wire x_dir ; wire y_dir ; wire [9:0] Xmin ; wire [9:0] Xmax ; wire [8:0] Ymin ; wire [8:0] Ymax ; // assign x_dir= (xs_in<xe_in)? 1'd0 : 1'd1 ; assign y_dir= (ys_in<ye_in)? 1'd0 : 1'd1 ; assign Xmin = (xs_in<xe_in)? xs_in : xe_in ; assign Xmax = (xs_in<xe_in)? xe_in : xs_in ; assign Ymin = (ys_in<ye_in)? ys_in : ye_in ; assign Ymax = (ys_in<ye_in)? ye_in : ys_in ; assign dx = Xmax-Xmin; //得出X方向上的差值 assign dy = Ymax-Ymin; //得出Y方向上的差值 reg signed [9:0] x_cnt ; // X 坐标计数 有符号运算 //********************************************************** always @ (posedge clock ) if(!reset) begin x_cnt <= 10'd0 ; fini_flag <= 1'd0 ; end else if(in_en) //数据装载 begin x_cnt <= xs_in ; fini_flag <= 1'd0 ; end else if (x_cnt==xe_in) // 运算完毕 begin //x_cnt <= 10'd0 ; fini_flag <= 1'd1 ; end else //运算进行中 begin x_cnt <= x_cnt + {{9{x_dir}},1'd1}; fini_flag <= 1'd0 ; end always @(posedge clock ) if(!reset) begin y_ou <= 9'd0 ; x_ou <= 10'd0 ; end else if ((!fini_flag) && (!in_en)) //运算标志正在运算,并且装载数据完成 begin if(pi[15]) begin pi <= pi+(dy<<1) ; x_ou <= x_cnt ; end else begin pi <= pi + (dy<<1) - (dx<<1) ; y_ou <= y_ou + {{8{y_dir}},1'd1}; x_ou <= x_cnt ; end end else begin pi <= (dy<<1)-dx ; y_ou <= ys_in ; x_ou <= xs_in ; end endmodule
附上测试代码
`timescale 1ns/1ps module bresenham_tb ; reg clock ,reset ; reg in_en ; reg [9:0] xs_in ,xe_in ; reg [8:0] ys_in ,ye_in ; wire [9:0] x_ou ; wire [8:0] y_ou ; wire fini_flag ; bresenham U1_bresenham( .clock (clock), .reset (reset), .xs_in (xs_in), .ys_in (ys_in), .xe_in (xe_in), .ye_in (ye_in), .in_en (in_en), .x_ou (x_ou), .y_ou (y_ou), .fini_flag (fini_flag) ); always #10 clock = ~clock ; initial begin clock = 1'd0 ; reset =1'd0 ; in_en = 1'd0 ; xs_in = 10'd0 ; xe_in = 10'd0 ; ys_in = 9'd0 ; ye_in = 9'd0 ; #40 reset = 1 ; in_en = 1 ; xs_in = 100 ; xe_in = 200 ; ys_in = 100 ; ye_in = 150 ; #80 in_en = 0 ; #3000 ; // k = 1/2 验证 正方向 in_en = 1 ; xs_in = 200 ; xe_in = 100; ys_in = 150 ; ye_in = 100; #80 in_en = 0 ; #3000 ; // k = 1/2 验证 反方向 in_en = 1 ; xs_in = 100 ; xe_in= 200 ; ys_in = 100 ; ye_in= 50 ; #80 in_en = 0 ; // k = -1/2 验证 正方向 #3000 in_en = 1 ; xs_in = 200 ; xe_in= 100; ys_in = 50 ; ye_in= 100 ; #80 in_en = 0 ; // k = -1/2 验证 反方向 #3000 $stop ; end endmodule