扫描转换直线段

说明与环境配置环境配置 扫描转换直线段方法一: 直线方程法代码描述: 算法比较简单, 暂无代码. 方法二: 数字差分分析DDA算法代码描述: 方法三: 中点算法代码描述: 所有代码下载与效果展示:

说明与环境配置

生成一个线段的方法主要有三种:

直线方程法数字差分分析DDA算法中点算法, (Bresenham 算法) 我所采用的实现方式: OPENGL1.1库 + VS2019

环境配置

https://blog.csdn.net/BoyInC0de/article/details/90079870

扫描转换直线段

方法一: 直线方程法

该方法根据直线的几何方程来群定线段路径上的像素位置

方程: $$y=mx+b$$ 通俗来讲, 只要确定$m$和$b$, 就可以通过不断将$x_i$代入方程计算像素$(x_i,y_i)$的值

那么对于区间$[x_0,x_1]$只要将其离散化到$k_0,k_1....k_n$, 其中 $k_{i+1}=k_i+1,k_0=x_0,k_n=x_1$ 我们就可以通过$y_i=m{x}_i+b$计算纵坐标 然后通过取整得到$y$坐标 取整: $${\left\{(k_i,y_i)\right\}}_{i=0}^n\to {\left\{(k_i,y_{i,r})\right\}}_{i=0}^n$$ $$y_{i,r}=round(y_i)=(int)(y_i+0.5)$$ 和后两种算法相比, 该算法具有很明显的弊端. 运算特点: 乘法+加法+取整 浮点运算

代码描述: 算法比较简单, 暂无代码.

方法二: 数字差分分析DDA算法

方法: $$\begin{array}{rl}{y}_{i+1}& =m{x}_{i+1}+b\\ & =m(x_i+1)+b\\ & =m{x}_i+b+m\\ & =y_i+m\end{array}$$

运算特点: 加法+取整 浮点运算

代码描述:

void CALLBACK draw(){ //都是全局变量 glColor3f(rc, gc, bc); m = (float)dy / dx; y = y_0; for (x = x0; x <= x1; x++) { glBegin(GL_POINTS); glVertex2i(x,(int)(y+0.5)); glEnd(); y += m; } glFinish(); }

方法三: 中点算法

方法: 直线的隐式方程: $$F(x,y)=Ax+By+C=0$$ 该式中: $$\begin{array}{rl}A& =y_0-y_1=-\Delta y\\ B& =x_1-x_0=\Delta x\\ C& =x_0\ast y_1-x_1\ast y_0\end{array}$$ 直线具有正负划分性, 直线上方的点: $F(x,y)>0$ 直线下方的点: $F(x,y)<0$ 直线上的点: $F(x,y)=0$

有了正负划分性, 我们可以想象像素点组成了一条蛇, 它沿着直线, 在直线两侧游走. 一会大于0, 一会小于0.

那么这条蛇的出发点就是$(x_0,y_0)$, 那么它的下一个点应该是什么呢? 也就是说根据$(x_i,y_{i,r})$ 如何确定他的下一个像素点$(x_{i+1},y_{i+1,r})$, (y_{i,r}是取整后的坐标)

这里我们根据所取点间的中点M与直线的位置构造一个函数判别式: $$d=F(M)=F(x_i+1,y_{i,r}+0.5)$$ 这个函数的意义是 M点位于直线的上方还是下方, 也就是说, 算完$(x_i,y_{i,r})$以后, $x_i$加上1也就是点$E$ 再点E再向上加0.5个点位, 就是点$M$, 而我们只要将$M$坐标代入直线方程, 就可以根据正负来判断它是在直线上面还是下面

如果$d\ge 0$, 中点M在线段上方, 取点E如果$d<0$, 中点M在线段下方, 取点NE

接下来取包括初始点在内的连续三个点, 做一个计算, 参考图: 初始点: $(x_0,y_0)$ , 中点: $M(x_0+1,y_0+0.5)$ 代入$F(x,y)$ $$\begin{array}{rl}设d=F(x_0+1,y_0+0.5)& =A(x_0+1)+B(y_0+0.5)+C\\ & =(y_0-y_1)(x_0+1)+(x_1-x_0)(y_0+0.5)+x_0{y}_1-x_1{y}_0\\ & =y_0-y_1+0.5(x_1-x_0)\\ & =A+0.5B\end{array}$$ 接下来判定再下一个像素, $(x_i+2,y_{i+1,r})$ 第一种情况上一点的:$d\ge 0$: 初始点: $(x_0,y_0)$ , 第一个点: $M(x_0+1,y_0)$, 那么第二个点$(x_0+2,y_0+0.5)$ 代入F(x,y) $$\begin{array}{rl}F(x_0+2,y_0+0.5)& =A(x_0+2)+B(y_0+0.5)+C\\ & =(y_0-y_1)(x_0+2)+(x_1-x_0)(y_0+0.5)+x_0{y}_1-x_1{y}_0\\ & =(y_0-y_1)+0.5(x_1-x_0)+(y_0-y_1)\\ & =A+0.5B+A\\ & =d+A\end{array}$$ 第二种情况上一点的:$d<0$: 初始点: $(x_0,y_0)$ , 第一个点: $M(x_0+1,y_0+0.5)$, 那么第二个点$(x_0+2,y_0+1.5)$ 代入F(x,y) $$\begin{array}{rl}F(x_0+2,y_0+1.5)& =A(x_0+2)+B(y_0+1.5)+C\\ & =(y_0-y_1)(x_0+2)+(x_1-x_0)(y_0+1.5)+x_0{y}_1-x_1{y}_0\\ & =y_0-y_1+0.5(x_1-x_0)+(y_0-y_1)+(x_1-x_0)\\ & =A+0.5B+A+B\\ & =d+A+B\end{array}$$ 观察第一种情况: $d$ 的增量是$A$ ( 即$-\Delta y$ ) 观察第二种情况: $d$ 的增量是$A+B$ ( 即 $-(\Delta y-\Delta x)$ ) 那么采用归纳法: $$\begin{array}{rl}{d}_0& =A+0.5B\\ d_{i+1}& =\{\begin{array}{ll}{d}_i+A,& \text{di>0}\\ d_i+A+B,& \text{di≤0}\end{array}\end{array}$$ 接下来做一个优化: 用2d来代替d 增量都是整数, 只有初始值包含小数, 可以用2d代替d, 2a改写成a + a 这样一来, 算法中只有整数变量, 不含乘除法, 可用硬件实现.

但是, 这只是斜率 $0\le m\le 1$的情况 按照上面的归纳法, 通过计算, 便可以得到以下方程:

$0\le m\le 1$: $$\begin{array}{rl}{d}_0& =2A+B\\ d_{i+1}& =\{\begin{array}{ll}{d}_i+2A,& \text{di>0}\\ d_i+2A+2B,& \text{di≤0}\end{array}\\ d_i& <0时,y增1\end{array}$$

$m>1$: $$\begin{array}{rl}{d}_0& =A+2B\\ d_{i+1}& =\{\begin{array}{ll}{d}_i+2A+2B,& \text{di>0}\\ d_i+2B,& \text{di≤0}\end{array}\\ d_i& >0时,x增1\end{array}$$

$-1\le m\le 0$: $$\begin{array}{rl}{d}_0& =2A-B\\ d_{i+1}& =\{\begin{array}{ll}{d}_i+2A-2B,& \text{di>0}\\ d_i+2A,& \text{di≤0}\end{array}\\ d_i& >0时,y减1\end{array}$$

$m<-1$: $$\begin{array}{rl}{d}_0& =A-2B\\ d_{i+1}& =\{\begin{array}{ll}{d}_i-2B,& \text{di>0}\\ d_i+2A-2B,& \text{di≤0}\end{array}\\ d_i& <0时,x增1\end{array}$$

代码描述:

#include <windows.h> #include <GL.H> #include <GLAUX.H> #include <GLU.H> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <time.h> //添加这3条语句 #pragma comment (lib, "opengl32.lib") #pragma comment (lib, "glu32.lib") #pragma comment (lib, "glaux.lib") //#pragma comment( linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"" ) //这句是不让控制台窗体出现，如果想要出现，去掉即可。 inline void init() //初始化 { glClearColor(0.0, 0.0, 0.0, 1.0);//黑色背景 } //绘制图形函数 float r = 1, g = 0, b = 0; float x = 30.0f, y = 30.0f; float R1, R2; float pi = 3.1415926f; int i; int x0; int y_0; int x1; int y_1; float rc; float gc; float bc; void CALLBACK draw() { float dx = x1 - x0, dy = y_1 - y_0; float m = 0; if (dx != 0) m = dy / dx; else return; if (x0 > x1) { int t = x1; x1 = x0; x0 = t; t = y_1; y_1 = y_0; y_0 = t; } int d = 0; int d1 = d, d2 = d; int a = y_0 - y_1, b = x1 - x0, c = x0 * y_1 - x1 * y_0; glColor3f(rc, gc, bc); d = a + a + b; d1 = a + a; d2 = (a + b) + (a + b); int x = x0; int y = y_0; for (int i = x0; i < x1; i++) { if (d < 0) { y++; d += d2; } else d += d1; x++; glBegin(GL_POINTS); glVertex2i(x, y); glEnd(); } glFinish(); } void set(int x0, int y_0, int x1, int y_1, float rc, float gc, float bc) { ::x0 = x0; ::x1 = x1; ::y_0 = y_0; ::y_1 = y_1; ::rc = rc; ::gc = gc; ::bc = bc; } void CALLBACK change(){ set(100, 500, 350, 550, 0.0f, 1.0f, 0.0f); draw(); } void main() { auxInitDisplayMode(AUX_SINGLE | AUX_RGBA); auxInitPosition(100, 0, 1000, 1000); auxInitWindow("CGOpenGL"); init(); auxIdleFunc(change); auxMainLoop( draw ); }

所有代码下载与效果展示:

该代码采用包含直线段绘制的两种算法: **中点算法, 和 DDA算法. ** 分别采用两种算法描绘出4种不同斜率的直线, 外加一条单独处理的垂直x轴的直线. 有明确的注释. 虽然OpenGL1.1库文件较老, 但不论是对于教学还是实践, 对理解直线段算法都具有重要意义.

下载地址: https://download.csdn.net/download/boyinc0de/11206604

效果展示:

其中左侧图形为: 中点算法绘制 中间竖线为: 特殊处理 右侧图形为: DDA算法绘制