利用Bresenham算法控制多部步进电机匀速转动
bresenham算法的另外一个应用。
计算机图形学中绘制直线的Bresenham算法原本是用在绘图仪上控制X轴方向和Y轴方向的两部电机的，最近遇到一个十分类似的步进电机控制问题，用Bresenham算法恰好能解决。
问题描述：有左右两个相同的步进电机，用8051单片机控制L297 + L298芯片驱动，需要它们同时转动（同时启动，同时停止），但转速不同。例如左侧电机正转180步，同时右侧电机反转97步。这就好比从原点出发画一条到点(180, -97)的直线。
与电机的接口已抽象为四个函数：
void MotorLeftShrink(); // 左侧电机收紧绳索
void MotorLeftLoose(); // 左侧电机放松绳索
void MotorRightShrink(); // 右侧电机收紧绳索
void MotorRightLoose(); // 右侧电机放松绳索
另外有两个辅助函数，分别控制左右电机：
void MotorLeftStep(int direct)
{
if (direct == 1)
MotorLeftLoose();
else if (direct == -1)
MotorLeftShrink();
}
void MotorRightStep(int direct)
{
if (direct == 1)
MotorRightLoose();
else if (direct == -1)
MotorRightShrink();
}
现在的任务是写一个函数MoveMotor()，有四个参数，分别为两个电机转的步数和方向，让它控制这两部电机同时运转。我用的是整数版本的直线Bresenham算法，取自《计算机图形学的算法基础》一书。
// 参数：absDL、absDR 分别是左右电机转动的步数
// sDL、sDR 分别是左右电机转动的方向
void MoveMotor3(int absDL, int absDR, int sDL, int sDR)
{
int [...]
用Bresenham算法在FPGA上实现小数分频器
呵呵，人真的很奇妙，什么样的想法都有。
最近朋友问了一个问题，输入时钟是33MHz，要分出一路2.048MHz的时钟来，要求相位抖动尽可能小。我想到可以用计算机图形学中绘制直线的Bresenham算法来解决，获得成功。
输入时钟是33000kHz，输出时钟是2048kHz，好比从原点画一条到(33000,2048)的直线，用输入时钟驱动画笔在 x 方向的运动，那么对应的 y 方向的运动就是输出时钟。
Verilog代码如下：
module divider(clk_in, clk_out, nrst);
input clk_in, nrst;
output clk_out;
reg clk_out;
parameter input_freq = 33000; // both in kHz
parameter output_freq = 2048;
reg[16:0] err; // change to 18 bits if necessary, look down
always @(posedge clk_in or negedge nrst)
begin
if (nrst == 1′b0) begin
clk_out <= 1′b0;
err <= [...]
直线的生成算法
在光栅显示器的荧光屏上生成一个对象，实质上是往帧缓存寄存器的相应单元中填入数据。画一条从（x1, y1）到（x2, y2）的直线，实质上是一个发现最佳逼近直线的象素序列，并填入色彩数据的过程。这个过程也称为直线光栅化。
直线的DDA算法
DDA是数字微分分析式（Digital Differential Analyzer）的缩写。设直线之起点为（x1，y1），终点为（x2，y2），则斜率m为：
m = (y2-y1)/(x2-x1)=dy/dx
直线中的每一点坐标都可以由前一点坐标变化一个增量（Dx, Dy）而得到，即表示为递归式：
xi+1=xi+Dx
yi+1=yi+Dy
并有关系：Dy = m · Dx
递归式的初值为直线的起点（x1, y1），这样，就可以用加法来生成一条直线。具体方法是：
图2.1.1 直线方向的8个象限
表2.1.1
象限
|dx|>|dy|?
D x
D y
1a
1b
2a
2b
3a
3b
4a
4b
Ö
´
Ö
´
Ö
´
Ö
´
1
1/m
-1
-1/m
-1
-1/m
1
1/m
m
1
m
1
-m
-1
-m
-1
按照直线从（x1，y1）到（x2，y2）的方向不同，分为8个象限（图2.1.1）。对于方向在第1a象限内的直线而言，D x=1，D y=m。对于方向在第1b象限内的直线而言，取值Dy=1，Dx=1/m。各象限中直线生成时Dx, Dy的取值列在表2.1.1之中。
研究表中的数据，可以发现两个规律：
1、当|dx|>|dy|时
|D x|=1, |D y|=m；
否则：
Dx=1/m，|Dy|=1
2、Dx, Dy的符号与dx, dy的符号相同。
这两条规律可以导致程序的简化。由上述方法写成的程序如程序2.1.1所示。其中steps变量的设置，以及D x=dx/steps; D y=dy/steps等语句，正是利用了上述两条规律，使得程序变得简练。
使用DDA算法，每生成一条直线做两次除法，每画线中一点做两次加法。因此，用DDA法生成直线的速度是相当快的。
#include <stdlib.h>
#include <math.h>
inline int round(const float a){return int(a+0.5);}
void lineDDA(int xa, int ya, int xb, int yb,int c)
{
float delta_x, delta_y, x, y;
int dx, dy, steps, k;
dx=xb-xa;
dy=yb-ya;
if (abs(dx)>abs(dy)) steps=abs(dx);
else steps=abs (dy);
delta_x=(float)dx / (float)steps;
delta_y=(float)dy / (float)steps;
x=xa;
y=ya;
set_pixel(x, y, c);
for (k=1; k<=steps; k++)
{
x+=delta_x;
y+=delta_y;
set_pixel(x, y, c);
}
}
程序2.1.1 DDA直线生成程序
直线的Bresenham算法
本算法由Bresenham在1965年提出。设直线从起点（x1, y1）到终点（x2, y2）。直线可表示为方程y=mx+b。其中
b = y1 – m * x1,
m = (y2-y1)/(x2-x1)=dy/dx
我们的讨论先将直线方向限于1a象限（图2.1.1）在这种情况下，当直线光栅化时，x每次都增加1个单元，即
xi+1=xi+1。而y的相应增加应当小于1。为了光栅化，yi+1只可能选择如下两种位置之一。
yi+1的位置选择yi+1=yi 或者 yi+1=yi+1。选择的原则是看精确值y与yi及yi+1的距离d1及d2的大小而定。计算式为：
y=m(xi+1)+b (2.1.1)
d1=y-yi (2.1.2)
d2=yi+1-y (2.1.3)
如果d1-d2>0，则yi+1=yi+1，否则yi+1=yi。因此算法的关键在于简便地求出d1-d2的符号。将式（2.1.1）、（2.1.2）、（2.1.3）代入d1-d2，得
d1-d2=2y-2yi-1=2（dy/dx） (xi+1)-2yi+2b-1
用dx乘等式两边，并以Pi=dx(d1-d2)代入上述等式，得
Pi=2xidy-2yidx+2dy+dx(2b-1) (2.1.4)
d1-d2是我们用以判断符号的误差。由于在1a象限，dx总大于0，所以Pi仍旧可以用作判断符号的误差。Pi-1为：
Pi+1=Pi+2dy-2dx(yi+1-yi) (2.1.5)
误差的初值P1，可将x1, y1，和b代入式（2.1.4）中的xi, yi而得到：
P1=2dy-dx
综述上面的推导，第1a象限内的直线Bresenham算法思想如下：
1、画点(x1, [...]
