分享
 
 
 

正确的BresenHam算法。请各位讲解一下优化算法!

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

正确的画直线算法:

不过,第二个使用整数的变形算法搞不大明白

/*Bresenham算法

Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。仍然假定直线斜率在0~1之间,该方法类似于中点法,由一个误差项符号决定下一个象素点。

算法原理如下:过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点,然后确定该列象素中与此交点最近的象素。该算法的巧妙之处在于采用增量计算,使得对于每一列,只要检查一个误差项的符号,就可以确定该列的所求象素。

如图2.1.4所示,设直线方程为yi+1=yi+k(xi+1-xi)+k。假设列坐标象素已经确定为xi,其行坐标为yi。那么下一个象素的列坐标为xi+1,而行坐标要么为yi,要么递增1为yi+1。是否增1取决于误差项d的值。误差项d的初值d0=0,x坐标每增加1,d的值相应递增直线的斜率值k,即d=d+k。一旦 d≥1,就把它减去1,这样保证d在0、1之间。当d≥0.5时,直线与垂线x=xi+1交点最接近于当前象素(xi,yi)的右上方象素(xi+1,yi+1);而当d<0.5时,更接近于右方象素(xi+1,yi)。为方便计算,令e=d-0.5,e的初值为-0.5,增量为k。当e≥0时,取当前象素(xi,yi)的右上方象素(xi+1,yi+1);而当e<0时,取(xi,yi)右方象素(xi+1,yi)。

图2.1.4 Bresenham算法所用误差项的几何含义

*/

//Bresenham画线算法程序:

void Bresenhamline (int x0,int y0,int x1, int y1,int color)

{ int x, y, dx, dy;

float k, e;

dx = x1-x0;dy = y1- y0;k=dy/dx;//dx,dy是直线总的增量。k是实数的斜率

e=-0.5; x=x0;y=y0;//x,y为起点。e是调整数,以使问题成为〉=0,还是<0的问题。

/*

为方便计算,令e0=-0.5,e i+1=di+1-0.5,增量为k。当ei+1≥0时,取当前像素(xi,yi)

的右上方像素(xi+1, yi+1);而当e i+1<0时,更接近于右方像素(xi+1,yi)。

*/

//这里,我们利用了k=dy/dx这个斜率,而不是利用上面的逐个比较的方法。

//实数yi的值>=0.5,则用y(整数)+1的像素,<0.5则y轴仍用上一个像素的y坐标。

//一旦,用y+1,则我们的yi这个y轴的实数增量就会多出1这个增量。所以,一旦y++,就要yi--。

//这里,为了使我们不是判断是否>=0.5,而是改为判断是否>=0,我们需要对所有的yi-0.5。

//这实际上只需yi-0.5一次即可。因为yi是连续的增量----+k。

//这里我们用float e表示yi,并且赋e=-0.5,以后e=e+k,这样实际上就实现了给e-0.5的目的。

for (i=0;i<dx;i++)//循环dx次,即绘制dx个像素。

{ drawpixel (x, y, color);

x=x+1;e=e+k;

if (e>=0)

{ y++; e=e-1;}

}

}

/*举例:用Bresenham方法扫描转换连接两点P0(0,0)和P1(5,2)的直线段。

i x y e

0

-- 0 0 -0.5

1 -0.1

1 0 -0.1

2 1 -0.7

3 1 -0.3

4 2 -0.9 图2.1.5 Bresenham算法

5 2 -0.5

上述Bresenham算法在计算直线斜率与误差项时用到小数与除法。可以改用整数以避免除法。

由于算法中只用到误差项的符号,因此可作如下替换:2*e*dx。

改进的Bresenham画线算法程序:

*/

void InterBresenhamline (int x0,int y0,int x1, int y1,int color)

{

int x, y, dx, dy;

int k, e;

dx = x1-x0;dy = y1- y0;e=-dx;

x=x0;

y=y0;

for (i=0; i<dx; i++)

{drawpixel (x, y, color);

x++; e=e+2*dy;//大概是用2倍的y的绝对增量减去x的绝对增量这样的方法来计算的。

//具体怎样也搞不清楚!!!!!

if (e>=0) { y++; e=e-2*dx;}

}

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有