转载自:http://blog.csdn.net/cppyin/article/details/6172211
1. 数学分析
1) 画直线的问题
本来我以为画直线会很容易,随便拿个直线公式,遍历X求Y画出来不就完了么,但事实并非如此。以2D直线为例,因为3D直线也只是多引入了个Z坐标而已。关键的问题:我们在数学中所学的直线是基于实数域的,而在计算机屏幕上,所画的直线是基于正整数域的,可以想象这么一个情形,在直线的某一点X=1,Y=0.01时,在屏幕上如何画呢?下图对比了实数域的直线,与基于正整数域的直线:
为什么直线在正整数域是不连续的呢,还记得斜率的的定义么:斜率m = dy / dx = (y1 - y0) / (x1 - x0)
这意味着当X坐标增加1,则Y坐标就增加m。这就是会出现上述情况的根本原因。
2) Bresenham算法
该算法由Bresenham在1965年发明,它到底做了什么事呢?其实想法很简单,就是每X移动一个像素,则考虑Y应该是如何移动。为什么我们要关注Bresenham算法呢,我们发现,这种算法实际只做了加减法,是非常适合计算机运算的,这种算法的速度是相当快的。
该算法把直线分为两种:一种是斜率<1的线,即近X轴线。另一种是斜率>1的线,即近Y轴线。
我们以近X轴直线为例,如图:
Bresenham算法的核心就是,当X加1后,如何决定Y的移动。显然可见,近X轴直线的dy<dx。所以一个直观的想法是,保存一个误差累计变量,每当X加1,误差变量便累计增加一个dy。当累计误差小于等于dx时,Y不动,当累计的误差大于dx时,Y加1,同时把累计误差减掉一个dx。这样,算法将不停的将光栅线与实际线之间的误差减到最小。
2. 函数实现
这里给出一个例子,实现了上面的算法,但只限近X轴并且是从左上往右下画的,可以很清楚的看到实现的逻辑。通用的画线在源码中已实现,可以下载获取。
-
intdx=x1-x0;
-
intdy=y1-y0;
-
interror=0;
-
if(dx>dy)
-
{
-
for(intx=x0,y=y0;x<=x1;++x)
-
{
-
DrawPixel(x,y,color);
-
error+=dy;
-
-
if(error>dx)
-
{
-
error-=dx;
-
++y;
-
}
-
}
-
}
针对所有情况的完整代码如下,其中在误差的计算方面进行了一些优化,起始值更居中,而不是写死的0。
-
int_CPPYIN_3DLib::DrawLine(intx0,inty0,intx1,inty1,DWORDcolor)
-
{
-
intx,y,dx,dy,dx2,dy2,xstep,ystep,error,index;
-
x=x0;
-
y=y0;
-
dx=x1-x0;
-
dy=y1-y0;
-
-
if(dx>=0)
-
{
-
xstep=1;
-
}
-
else
-
{
-
xstep=-1;
-
dx=-dx;
-
}
-
-
if(dy>=0)
-
{
-
ystep=1;
-
}
-
else
-
{
-
ystep=-1;
-
dy=-dy;
-
}
-
-
dx2=dx<<1;
-
dy2=dy<<1;
-
-
if(dx>dy)
-
{
-
error=dy2-dx;
-
for(index=0;index<=dx;++index)
-
{
-
DrawPixel(x,y,color);
-
if(error>=0)
-
{
-
error-=dx2;
-
y+=ystep;
-
}
-
error+=dy2;
-
x+=xstep;
-
}
-
}
-
else
-
{
-
error=dx2-dy;
-
for(index=0;index<=dy;++index)
-
{
-
DrawPixel(x,y,color);
-
if(error>=0)
-
{
-
error-=dy2;
-
x+=xstep;
-
}
-
error+=dx2;
-
y+=ystep;
-
}
-
}
-
-
return1;
-
}
3. 源码下载
这个示例使用该函数,每帧在窗口中画500条随机颜色的直线,截图如下:
项目源代码下载:>>点击进入下载页<<
4. 补充更新
画直线还有一些算法,速度有的更快,如:
Run-Slicing
Symmetric Double Step
Quadruple Step
如果有时间我会一一实现,如果读者已经实现,请留言分享,谢谢。
分享到:
相关推荐
为了提高效率,一般的图形绘制系统,如Java2D、OpenGL之类都是默认不进行反走样的。 还有一个疑问,既然反走样比不反走样的图像质量高很多,不进行反走样的绘制还有什么作用呢?前面说的是一个方面,也就是,在...
这一课我们将创建一些基于2D图像的字体,它们可以缩放,但不能旋转,并且总是面向前方,但作为基本的显示来说,我想已经够了。 14.图像字体 在一课我们将教你绘制3D的图形字体,它们可像一般的3D模型一样被变换...
这一课我们将创建一些基于2D图像的字体,它们可以缩放,但不能旋转,并且总是面向前方,但作为基本的显示来说,我想已经够了。 14.图像字体 在一课我们将教你绘制3D的图形字体,它们可像一般的3D模型一样被变换。 ...
4.3.2 实现图像视图和文本字段 43 4.3.3 添加图像视图 44 4.3.4 添加文本字段 47 4.3.5 设置第二个文本字段的属性 50 4.3.6 连接输出口 50 4.4 构建和运行 51 4.4.1 完成输入后关闭键盘 51 4.4.2 通过触摸背景关闭...
5.2版控件新增了一个Chartlet的组件,使用非常方便,可以生成柱形图、饼图、折线图等多种图形,而且可以设置2D或3D效果,既可以在打印控件中打印出来,也可以在Graphics对象中显示。 4、分组汇总打印DataGridVeiw...
5.2版控件新增了一个Chartlet的组件,使用非常方便,可以生成柱形图、饼图、折线图等多种图形,而且可以设置2D或3D效果,既可以在打印控件中打印出来,也可以在Graphics对象中显示。 4、分组汇总打印DataGridVeiw...
该章介绍了OpenGL ES 3.0支持的所有纹理类型:2D纹理、立方图、2D纹理数组和3D纹理。 第10章——片段着色器 第9章的重点是如何在片段着色器中使用纹理,第10章介绍编写片段着色器所需知道的其他知识。该章概述了...
5.2版控件新增了一个Chartlet的组件,使用非常方便,可以生成柱形图、饼图、折线图等多种图形,而且可以设置2D或3D效果,既可以在打印控件中打印出来,也可以在Graphics对象中显示。 4、分组汇总打印DataGridVeiw...
5.2版控件新增了一个Chartlet的组件,使用非常方便,可以生成柱形图、饼图、折线图等多种图形,而且可以设置2D或3D效果,既可以在打印控件中打印出来,也可以在Graphics对象中显示。 4、文本打印输出功能,控件提供...
这是通过应用图像处理技术来识别所有墙壁来实现的,因此不需要结构的 CAD 模型。 它所需要的只是结构蓝图的图像(提供了此类图片的示例)。 蓝图需要简单,所有的墙壁都应该是直线,以便霍夫变换检测到(没有曲线)...
数组长度 line0.GetLength(1) 数组赋值 可以从一个已经赋值的数组 array2 向未赋值的同等数组 array1 赋值,用 array1=array2; 这时,array1 就变成和 array2 一样的数组了。 集合 集合的使用 集合可以看成是可以...