直线扫描转换
在显示器上用最逼近直线的像素点来表示直线
1.DDA画线法
思想：
即数值微分法，Digitical Differential Analyzer
实现：
plot(x,int(y))
#include <gl/glut.h>
#include <stdio.h>
#include <math.h>
int xs,ys,xe,ye;
//x0和y0为起始坐标，x1和y1为终止坐标
void DDALine(int x0, int y0, int x1, int y1){
int dy=y1-y0;
int dx=x1-x0;
float k=dy[表情];
int y=y0;
if(k<1){
for (int x=x0;x<=x0;x++){
glVertex2i(x,int(y+0.5));
y+=k;
}
}
else{
int x=x0;
for (;y<=y1;y++){
glVertex2i(int(x+.5),y);
x+=1/k;
}
}
}
void lineSegment(){
glClear(GL_COLOR_BUFFER_BIT);
glColor3f(0.0,0.0,0.0);
glBegin(GL_POINTS);
DDALine(xs,ys,xe,ye);
glEnd();
glFlush();
}
void main(int argc, char *argv[]){
glutInit(&argc,argv);
glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);
printf("输出线段起始和终止坐标(范围为0-500， 0-500):");
scanf("%d,%d,%d,%d",&xs,&ys,&xe,&ye);
glutInitWindowPosition(50,100);
glutInitWindowSize(500,500);
glutCreateWindow("中点画线算法");
glClearColor(1.0,1.0,1.0,0.0);
glMatrixMode(GL_PROJECTION);
gluOrtho2D(0.0,500.0,0.0,500.0);
glutDisplayFunc(lineSegment);
glutMainLoop();
}
- 采用微分思想
- 计算y使用浮点数、除法
- 迭代算法
- |k|>1将导致隔行显示，故|k|>1时采用y=y+1，x=x+1/k
2.中点画线法
思想：
|K|<1时，
其中d又满足迭代(带入直线标准式推得)
实现：
- plot(x,y)
- 3.
- 重复2-3，直到绘制完成
#include <gl/glut.h>
#include <stdio.h>
#include <math.h>
int xs,ys,xe,ye;
//x0和y0为起始坐标，x1和y1为终止坐标
void MidPoint(int x0, int y0, int x1, int y1){
int a=y0-y1;
int b=x1-x0;
int c=x0*y1-x1*y0;
int d=2*a+b;
int d1=2*a;
int d2=2*(a+b);
//斜率小于1时
int y=y0;
for (int x=x0;x<=x1;x++){
if (d<0){
y+=1;
glVertex2i(x,y);
d+=d2;
}
else{
y=y;
glVertex2i(x,y);
d+=d1;
}
}
}
void lineSegment(){
glClear(GL_COLOR_BUFFER_BIT);
glColor3f(0.0,0.0,0.0);
glBegin(GL_POINTS);
MidPoint(xs,ys,xe,ye);
glEnd();
glFlush();
}
void main(int argc, char *argv[]){
glutInit(&argc,argv);
glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);
printf("输出线段起始和终止坐标(范围为0-500， 0-500):");
scanf("%d,%d,%d,%d",&xs,&ys,&xe,&ye);
glutInitWindowPosition(50,100);
glutInitWindowSize(500,500);
glutCreateWindow("中点画线算法");
glClearColor(1.0,1.0,1.0,0.0);
glMatrixMode(GL_PROJECTION);
gluOrtho2D(0.0,500.0,0.0,500.0);
glutDisplayFunc(lineSegment);
glutMainLoop();
}
特点：
- 不必算斜率 ，无除法
- 无浮点数，只有整数
- 只有加法和乘2运算
3.Breshnham画线法
image.png
d初始化为0，每次加K，但y每加1，d需要减1,d高于中点取上面的像素，否则取下面的像素
有浮点数、慢
改进1:
d与浮点数0.5比较太慢了，令e=d-0.5
只判断e的符号即可
终结版：
e的初值依然是浮点数，而且还要算k，不如令e=2e*dx（dx=x1-x0，dy=y1-y0，原先算斜率用的），就可以抵消分母，并把自带的0.5取整
算法：
- 输入（x0，y0），（x1,y1)
- dx=x1-x0, dy=y1-y0,e=-dx,x=x0,y=y0
- plot(x,y)
- e=e+2dy if e>0 (x,y)更新为（x+1，y+1）e=e-2dy ，else （x,y）更新为（x+1，y)
- 5.重复3-4直到画完
#include <gl/glut.h>
#include <stdio.h>
#include <math.h>
int xs, ys, xe, ye;
//x0和y0为起始坐标，x1和y1为终止坐标
void BreshnhamLine(int x0, int y0, int x1, int y1) {
int dy = y1 - y0;
int dx = x1 - x0;
if (dx == 0) {
printf("error");
}float k = dy / dx;
float d = 0;
int x = x0, y = y0;
int e = -dx;
for (x; x <= x1; x++) {
glVertex2i(x, y);
e += 2 * dy;
if (e) {
y += 1;
e -= 2 * dx;
}
}
}
void lineSegment() {
glClear(GL_COLOR_BUFFER_BIT);
glColor3f(0.0, 0.0, 0.0);
glBegin(GL_POINTS);
BreshnhamLine(xs, ys, xe, ye);
glEnd();
glFlush();
}
void main(int argc, char *argv[]) {
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
printf("输出线段起始和终止坐标(范围为0-500， 0-500):");
scanf("%d,%d,%d,%d", &xs, &ys, &xe, &ye);
glutInitWindowPosition(50, 100);
glutInitWindowSize(500, 500);
glutCreateWindow("中点画线算法");
glClearColor(1.0, 1.0, 1.0, 0.0);
glMatrixMode(GL_PROJECTION);
gluOrtho2D(0.0, 500.0, 0.0, 500.0);
glutDisplayFunc(lineSegment);
glutMainLoop();
}
特点：只有加法和乘法运算，全是整数运算，乘法也只是乘2，可以用移位位实现，便于硬件实现
小结
画线主要还是要简化步骤，尽量避免浮点数和除法，尽量多用加法，少用乘法
上述算法主要讨论了K<1的情况，k>1时将x，y互换即可
网友评论