光栅图形学(1)-数值微分 DDA(Digital Differential Analyzer)画线算法

文章目录[x]
  1. 1:算法介绍
  2. 2:代码

 

FBI WARNING:本文含有数学公式,如显示异常请刷新页面

算法介绍


DDA算法,是计算机图形学中一种基于直线的微分方程来生成直线的方法,由于有浮点数运算与取整,该算法不利于硬件实现

--- 百度百科

如上图所示,需要在点A (3, 2)和点B(10, 6)之间绘制一条线段,在高中我们都学过直线方程式,直线的表达方式有很多种,斜截式便是之一,$ y = mx + b $。其中 $ m $ 为斜率,$ b $ 为截距。此时当然可以直接通过这个公式算出经过AB两点的直线方程,然后代入x求出y得出结果,但是这样做是低效的。因为该公式中含有一个乘法,即 $ mx $。对于计算机而言,加法的运算时最快的,那么能否将这个乘法去除呢?DDA便可以。

本算法有两种教学思想,扁扁在这里选取自己比较喜欢的一种

$$ \Delta x = 10 - 3  = 7  \qquad  \Delta y = 7 - 2  = 5 $$

$$  \therefore m = \frac{\Delta y}{\Delta x} =  \frac{5}{7} $$

$$ 当 m < 1 时, \quad steps = \Delta x = 7 (要选 \Delta y 和 \Delta x 中较大的一个) $$

$$ \therefore xInc = \frac{\Delta x}{steps} = 1 \qquad yInc = \frac{\Delta y}{steps} \approx 0.71  $$

点A step1 step2 step3 step4 step5 step6 step7
x 3 4 5 6 7 8 9 10
y 2 2.71 3.42 4.13 4.84 5.55 6.26 6.97
y 2 3 3 4 5 6 6 7

通过上面的一顿盲目分析,扁扁已经算出来了点A到点B之间需要绘制的点,但是现在只分析了当斜率小于1的情况,那么其它情况是什么样子的呢?说到这里,扁扁请到的两位老师登场,剩下的就看他们的表演吧。

需要说明的是,两位老师采用的是不同的思想教学,建议先看中文视频再看英文视频。本人是采用的第一位老师的思想。

 

代码


void DDA::DrawLineByDDA(Vector2 from, Vector2 to)
{
	float x, y;
	int steps;

	// step1: 计算两点差值
	float dx = to.x - from.x;
	float dy = to.y - from.y;

	// step2: 确定DrawPixel的次数
	if (abs(dx) > abs(dy))
		steps = abs(dx);
	else
		steps = abs(dy);

	// step3: 计算每步的增量
	dx = dx / steps;
	dy = dy / steps;

	// step4: 填充像素
	x = from.x;
	y = from.y;
	for (int i = 0; i <= steps; i++)
	{
		//qLog("x=%d,y=%d\n", int(x + 0.5), int(y + 0.5));
		m_RenderSystem->GetRasterizer()->DrawPixel(x + 0.5, y + 0.5, Color::red);
		x += dx;
		y += dy;
	}

	//system("pause");
}

 

可以看到,代码里面计算出来的结果也是丝毫不差呢。

 

:huaji: 顺手点个赞吧 :huaji2:

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像