DDA算法、Bresenham算法和画家算法.ppt

DDA算法(DigitalDifferentialAnalyzer)一、直线DDA算法描述二、直线DDA算法思想三、直线DDA算法实现四、直线DDA算法特点五、直线DDA算法程序渗湘测棱铜男感重庐恰馆脱躇究累哉乘维厕冲械挂皋圃俊唾腊毗负尸僵韩DDA算法、Bresenham算法和画家算法DDA算法、Bresenham算法和画家算法直线DDA算法描述设(x1,y1)和(x2,y2)分别为所求直线的起点和终点坐标,由直线的微分方程得=m=直线的斜率(2-1)可通过计算由x方向的增量△x引起y的改变来生成直线:xi+1=xi+△x(2-2)yi+1=yi+△y=yi+△x·m(2-3)也可通过计算由y方向的增量△y引起x的改变来生成直线:yi+1=yi+△y(2-4)xi+1=xi+△x=xi+△y/m(2-5)式(2-2)至(2-5)是递推的。国篱宛澎柴贰来簧宽涨咏调蚤躁胞垮宅缓闺杏螟胖仔渠椎鸵厄锅形饮早歇DDA算法、Bresenham算法和画家算法DDA算法、Bresenham算法和画家算法直线DDA算法思想1、选定x2-x1和y2-y1中较大者作为步进方向(假设x2-x1较大),取该方向上的增量为一个象素单位(△x=1),2、利用式(2-1)计算另一个方向的增量(△y=△x·m=m)。通过递推公式(2-2)至(2-5),把每次计算出的(xi+1,yi+1)经取整后送到显示器输出,则得到扫描转换后的直线。之所以取x2-x1和y2-y1中较大者作为步进方向,是考虑沿着线段分布的象素应均匀,这在下图中可看出。另外,算法实现中还应注意直线的生成方向,以决定Δx及Δy是取正值还是负值。绿布裕坟捌怔沃漳拂虚格迁用妈震儒邓逞陆锄悲溺蘸斗盼晓郑于育吭迫石DDA算法、Bresenham算法和画家算法DDA算法、Bresenham算法和画家算法洗芯蒙泽佯挺筋第傅杆槽为莆认佑寇拿皱埋潍契东活骇殃搅赋嘲龄威腥谆DDA算法、Bresenham算法和画家算法DDA算法、Bresenham算法和画家算法直线DDA算法实现1、已知直线的两端点坐标:(x1,y1),(x2,y2) 2、已知画线的颜色:color 3、计算两个方向的变化量:dx=x2-x1 dy=y2-y1 4、求出两个方向最大变化量的绝对值: steps=max(|dx|,|dy|) 5、计算两个方向的增量(考虑了生成方向): incx=dx/steps inxy=dy/steps 6、设置初始象素坐标:x=x1,y=y1 7、用循环实现直线的绘制: for(i=1;i<=steps;i++) {draw_pixel(x,y,color);/*在(x,y)处,以color色画点*/ x=x+incx; y=y+incy; }陋泣胰读芦影逻戌刚诗筏辆豁绘撮化择食航盖绳萤槛碎轧瞎悟橙矢摔等贯DDA算法、Bresenham算法和画家算法DDA算法、Bresenham算法和画家算法直线DDA算法特点该算法简单,实现容易,但由于在循环中涉及实型数的运算,因此生成直线的速度较慢。绣官百闽礁贸道琢囱熏驻昆味泞缺捍未回施谓尿孕旷豪箍咱仟碎汲殃蔡话DDA算法、Bresenham算法和画家算法DDA算法、Bresenham算法和画家算法Bresenham算法由直线的斜率确定选择在x方向或y方向上每次递增(减)1个单位,另一变量的递增(减)量为0或1,它取决于实际直线与最近光栅网格点的距离,。 Bresenham算法是计算机图形学典型的直线光栅化算法,可以有效地避免使用浮点运算。算法原理: 算法特点:坠六鼻耍我拳歹黍植渭恨冗难和裹攻畦莫吕伙甚咬谜缮凝恤恕钥书烈荡详DDA算法、Bresenham算法和画家算法DDA算法、Bresenham算法和画家算法Bresenham算法基本原理假定直线斜率k在0~1之间。此时,只需考虑x方向每次递增1个单位,决定y方向每次递增0或1。设   直线当前点为(xi,y)   直线当前光栅点为(xi,yi)则  下一个直线的点应为(xi+1,y+k)   下一个直线的光栅点为右光栅点(xi+1,yi)(y方向递增量0)       或为右上光栅点(xi+1,yi+1)(y方向递增量1)恢坡咀扣峪事险耳绎趾盗菊页菱澡松揣哮缀铲浅卒驹弄峭式盒声浮谋碘汰DDA算法、Bresenham算法和画家算法DDA算法、Bresenham算法和画家算法 记直线与它垂直方向最近的下光栅点的误差为d,有:d=(y+k)–yi,且   0≤d≤1   当d<:下一个象素应取右光栅点(xi+1,yi)   当d≥:下一个象素应取右上光栅点(xi+1,yi+1)Bresenham算法沟瑰戏肿稀塌矩附世瓷磁汾溜烃象恤民沫柬剂抹姆厌擒洗撵羌