图形学 (一): 画线算法DDA和Bresenham

偏执的太偏执、 2022-03-27 09:46 301阅读 0赞

### 画线算法 ###

*  前言
 *   *  API介绍
 *  DDA
 *   *  代码
     *  效果图
 *  Bresenham
 *   *  代码
     *  效果图
 *  中点画线算法
 *   *  代码
     *  注意事项
     *  效果图
 *  总结
 *   *  Bresenham 循环体内指令
     *  DDA 循环体内指令

# 前言 #

我们老师竟然还在用MFC，一开始我是震惊的，后来参考了很多国内的教材发现都是MFC。。（QB对不起！  
**该图形学系列博客的环境是VC++6.0 & MFC & OpenGL**，Mac上装一个Windows XP虚拟机，适应一段时间后发现还是挺舒服的，也找到了童年的感觉。  
代码地址：[我的Github][Github]

## API介绍 ##

**类名::draw(CPoint from, CPoint to, CDC\* dc)**  
其中CDC\* dc是一个设备上下文对象，通过调用它的

void CDC::SetPixel(int x, int y, COLORREF color);
    void CDC::SetPixel(CPoint point, COLORREF color);

方法来画像素点

# DDA #

将直线按照长轴方向微分, 比如这条直线是 (0, 0) -> (5, 4), 那么一共画5个点, 分别是(0, 0), (1, 0.8), (2, 1,6), (3, 2.4), (4, 3.2), (5, 4). 因为像素空间的坐标值只能是整数, 所以在绘制时要四舍五入.

## 代码 ##

void DDALine::draw(CPoint from, CPoint to, CDC* dc) { 
    	float x = from.x + 0.5;
    	float y = from.y + 0.5;
    	float stepx, stepy;
    	int times = 1;
    	COLORREF color = RGB(255, 0, 0);
    
    	int dy = to.y - from.y;
    	int dx = to.x - from.x;
    	if (abs(dy) >= abs(dx)) { 
    		times += abs(dy);
    		stepx = dx * 1.f / dy;
    		stepy = 1.f;
    		if (from.y > to.y) { 
    			stepx *= -1;
    			stepy *= -1;
    		}
    	} else { 
    		times += abs(dx);
    		stepx = 1.f;
    		stepy = dy * 1.f / dx;
    		if (from.x > to.x) { 
    			stepx *= -1;
    			stepy *= -1;
    		}
    	}
    
    	while (times--) { 
    		dc->SetPixel((int) x, (int) y, color);
    		x += stepx;
    		y += stepy;
    	}
    }

## 效果图 ##

黑色为MFC提供的画线算法  
红色为DDA画线算法  
由此可见二者几乎完全重合  
![DDALine][]

# Bresenham #

该算法也是按照长轴方向计算, 但优势是**没有浮点运算**, 因此性能会好一点.

## 代码 ##

void Bresenham::draw(CPoint from, CPoint to, CDC* dc) { 
    	int dx = abs(to.x - from.x);
    	int dy = abs(to.y - from.y);
    	int x = from.x;
    	int y = from.y;
    	COLORREF color = RGB(0, 255, 255);
    	int stepx = (from.x < to.x) ? 1 : -1;
    	int stepy = (from.y < to.y) ? 1 : -1;
    	int e;
    	if (dx > dy) { 
    		e = dy * 2 - dx;
    		for (int i = 0; i <= dx; i++) { 
    			dc->SetPixel(x, y, color);
    			x += stepx;
    			e += 2 * dy;
    			if (e > 0) { 
    				e -= 2 * dx;
    				y += stepy;
    			}
    		}
    	} else { 
    		e = dx * 2 - dy;
    		for (int i = 0; i <= dy; i++) { 
    			dc->SetPixel(x, y, color);
    			y += stepy;
    			e += 2 * dx;
    			if (e > 0) { 
    				e -= 2 * dy;
    				x += stepx;
    			}
    		}
    	}
    }

## 效果图 ##

青色为Bresenham算法  
由此可见二者虽然重合度不高, 但是平均差异一般不超过一个像素.  
![Bresenham][]

# 中点画线算法 #

思路很简单: 画出一条线的中点,然后将直线二分, 递归调用.

## 代码 ##

void MidLine::draw(CPoint from, CPoint to, CDC* dc) { 
    	if ((abs(from.x - to.x) <= 1) && (abs(from.y - to.y) <= 1)) return;
    	CPoint mid((from.x + to.x) / 2, (from.y + to.y) / 2);
    	dc->SetPixel(mid, RGB(0, 255, 0));
    	draw(from, mid, dc);
    	draw(mid, to, dc);
    }

## 注意事项 ##

我这个版本有一个问题: 中点mid的计算由于取整会产生误差, **且这个误差会随着递归不断扩散**, 因此这个版本不好, 修复方法是像DDA那样用 float 来存储坐标, 这样就不会出现取整问题, **但是会有另一个问题, 那就是递归何时结束**.

## 效果图 ##

明显可以看出, 绿线不但比黑线偏差了一个以上的像素, 且不直.  
![中点画线][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlZWVfXw_size_16_color_FFFFFF_t_70]

# 总结 #

Bresenham复杂度和DDA一样都是 O(*Lmax*). 虽然它不涉及浮点运算, 但是循环体内的指令数量比DDA多

## Bresenham 循环体内指令 ##

(单独抽出来的, 所以会有 main 函数符号)

movl	-36(%rbp), %eax
    cmpl	-32(%rbp), %eax
    jg	73 <_main+0x67>
    movl	-16(%rbp), %eax
    addl	-12(%rbp), %eax
    movl	%eax, -12(%rbp)
    movl	-24(%rbp), %eax
    shll	$1, %eax
    addl	-20(%rbp), %eax
    movl	%eax, -20(%rbp)
    cmpl	$0, -20(%rbp)
    jle	23 <_main+0x54>
    movl	-32(%rbp), %eax
    shll	$1, %eax
    movl	-20(%rbp), %ecx
    subl	%eax, %ecx
    movl	%ecx, -20(%rbp)
    movl	-28(%rbp), %eax
    addl	-8(%rbp), %eax
    movl	%eax, -8(%rbp)
    jmp	0 <_main+0x59>
    movl	-36(%rbp), %eax
    addl	$1, %eax
    movl	%eax, -36(%rbp)
    jmp	-85 <_main+0x12>
    movl	-4(%rbp), %eax

## DDA 循环体内指令 ##

movl	-32(%rbp), %eax
    cmpl	-28(%rbp), %eax
    jg	60 <_main+0x5a>
    movss	-16(%rbp), %xmm0
    addss	-8(%rbp), %xmm0
    movss	%xmm0, -8(%rbp)
    movss	-20(%rbp), %xmm0
    addss	-12(%rbp), %xmm0
    movss	%xmm0, -12(%rbp)
    cvttss2si	-8(%rbp), %eax
    movl	%eax, -24(%rbp)
    cvttss2si	-12(%rbp), %eax
    movl	%eax, -28(%rbp)
    movl	-32(%rbp), %eax
    addl	$1, %eax
    movl	%eax, -32(%rbp)
    jmp	-72 <_main+0x12>
    movl	-4(%rbp), %eax

如果浮点运算的时间是整数运算的两倍, 那么二者的运算时间几乎是一样的.

明天就考试了, 这个算是一个复习吧.

[Github]: https://github.com/TeeEye/Line
[DDALine]: /images/20220327/6d9b7b6f7aae4d3393a02dd4e3bb25b7.png
[Bresenham]: /images/20220327/03f079f07d714c629dc6e00a73c908c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlZWVfXw_size_16_color_FFFFFF_t_70]: /images/20220327/422baa5bcf94483a9e88a3bfcc4182f4.png