6第三章直线、圆、椭圆生成算法 图形的扫描转换(光栅化):确定一个像素集合,用 于显示一个图形的过程。步骤如下: 确定有关像素 2、用图形的颜色或其它属性,对像素进行写操作, 对一维图形,不考虑线宽,则用一个像素宽的直线来 显示图形。二维图形的光栅化,即区域的填充:确定 像素集,填色或图案。 任何图形的光栅化,必须显示在一个窗口内,否则不 予显示。即确定一个图形的哪些部分在窗口内,哪些 在窗口外,即裁剪。 2021/1/21 浙江大学计算机图形学
2021/1/21 浙江大学计算机图形学 1 第三章 直线、圆、椭圆生成算法 图形的扫描转换（光栅化）：确定一个像素集合，用 于显示一个图形的过程。步骤如下： 1、确定有关像素 2、用图形的颜色或其它属性，对像素进行写操作。 对一维图形，不考虑线宽，则用一个像素宽的直线来 显示图形。二维图形的光栅化，即区域的填充：确定 像素集，填色或图案。 任何图形的光栅化，必须显示在一个窗口内，否则不 予显示。即确定一个图形的哪些部分在窗口内，哪些 在窗口外，即裁剪
图形显示前需要:扫描转换+裁剪 ●裁剪--〉扫描转换:最常用,节约计算时间。 ●扫描转换-)裁剪:算法简单; 图元二维 扫描 裁剪 转换 2021/1/21 浙江大学计算机图形学
2021/1/21 浙江大学计算机图形学 2 图形显示前需要：扫描转换+裁剪 ●裁剪---〉扫描转换：最常用，节约计算时间。 ●扫描转换---〉裁剪：算法简单；
邮本章内容 扫描转换直线段 DDA算法 中点画线法 Bresenham画线算法 圆弧、椭圆弧扫描转换 中点算法 内接正多边形迫近法 等面积正多边形逼近法 生成圆弧的正负法 2021/1/21 浙江大学计算机图形学
2021/1/21 浙江大学计算机图形学 3 本章内容 扫描转换直线段 DDA算法 中点画线法 Bresenham画线算法 圆弧、椭圆弧扫描转换 中点算法 内接正多边形迫近法 等面积正多边形逼近法 生成圆弧的正负法
直线段的扫描转换算法 ■直线的扫描转换:确定最佳逼近于该直线 的一组象素,并且按扫描线顺序,对这 些象素进行写操作。 三个常用算法: 数值微分法(DDA) 中点画线法 Bresenham算法 2021/1/21 浙江大学计算机图形学
2021/1/21 浙江大学计算机图形学 4 直线段的扫描转换算法 ◼ 直线的扫描转换: 确定最佳逼近于该直线 的一组象素，并且按扫描线顺序，对这 些象素进行写操作。 ◼ 三个常用算法： 数值微分法（DDA） 中点画线法 Bresenham算法
数值微分法(DDA) 假定直线的起点、终点分别为:(×0,y0) (×1y1),且都为整数。 X计+1.Y1 栅格交点表示象素点位置 (X1,ImY+05) 2021/1/21 浙江大学计算机图形学
2021/1/21 浙江大学计算机图形学 5 数值微分法（ＤＤＡ） 假定直线的起点、终点分别为：（x0,y0), (x1,y1)，且都为整数。 (X i+1 ,Yi + k) (X i , Int(Yi +0.5)) (X i , Yi) 栅格交点表示象素点位置 。 。 。
数值微分(DDA)法 ■基本思想 已知过端点P0(xO,y0),P1(X1,y1)的直线段L y=kx+b 直线斜率为 令x=x0→>x;x=x+ stepx v=kx+b (x, round()) 这种方法直观,但效率太低,因为每一步需要一次浮点乘法 和一次舍入运算。 2021/1/21 浙江大学计算机图形学
2021/1/21 浙江大学计算机图形学 6 数值微分(DDA)法 ◼基本思想 已知过端点P0 (x0, y0), P1(x1, y1)的直线段L y=kx+b 直线斜率为 这种方法直观，但效率太低，因为每一步需要一次浮点乘法 和一次舍入运算。 1 0 1 0 x x y y k − − = ( , ( )) ; 0 1 x round y y k x b x x x x x stepx = + 令 = → = +
数值微分(DDA法 计算y1=kx1+b =kx+b+k△X =yi+kAX 当AX=1;y1=y+k 即:当x每递增1,y递增k(即直线斜率) ■注意上述分析的算法仅适用于k≤1的情形。 在这种情况下,ⅹ每增加1,y最多增加1。 n当k>1时,必须把X,y地位互换 2021/1/21 浙江大学计算机图形学 7
2021/1/21 浙江大学计算机图形学 7 数值微分(DDA)法 计算yi+1= kxi+1+b = kxi+b+kx = yi+kx 当x =1; yi+1 = yi+k ◼ 即：当x每递增1，y递增k(即直线斜率)； ◼ 注意上述分析的算法仅适用于k ≤1的情形。 在这种情况下，x每增加1,y最多增加1。 ◼ 当 k 1时，必须把x，y地位互换
数值微分(DDA)法 ■增量算法:在一个迭代算法中,如果每 一步的ⅹ、y值是用前一步的值加上一个 增量来获得,则称为增量算法。 ■DDA算法就是一个增量算法。 2021/1/21 浙江大学计算机图形学
2021/1/21 浙江大学计算机图形学 8 数值微分(DDA)法 ◼ 增量算法：在一个迭代算法中，如果每 一步的x、y值是用前一步的值加上一个 增量来获得，则称为增量算法。 ◼ DDA算法就是一个增量算法
数值微分(DDA)法 void ddaline (int xo int yo, int x,, int yu,int color) fint X: float dx, dy, y, k dx,=X-Xo, dy=y1-yoi k=dy/dx, y=yo for(X=X6;X≤X1,X++) i drawpixel ( x, int(y+0.5),color y=y+k; 2021/1/21 浙江大学计算机图形学
2021/1/21 浙江大学计算机图形学 9 数值微分(DDA)法 void DDALine(int x0 ,int y0 ,int x1 ,int y1 ,int color) int x； float dx, dy, y, k; dx, = x1 -x0 , dy=y1 -y0 ; k=dy/dx, y=y0 ; for (x=x0 ; xx1 , x++) drawpixel (x, int(y+0.5), color); y=y+k;
数值微分(DDA)法 例:画直线段PO,0)-P(5,2) nt(y+05)y+0.51ine:P0(0,0)-p1(,2) 0 0+0.5 0 0.4+0.5 0.8+0.5 12+0.5 1.6+0.5 012345 52 2.0+0.5 2021/1/21 浙江大学计算机图形学
2021/1/21 浙江大学计算机图形学 10 数值微分(DDA)法 ◼ 例：画直线段P0(0,0)--P1(5,2) x int(y+0.5) y+0.5 0 0 0+0.5 1 0 0.4+0.5 2 1 0.8+0.5 3 1 1.2+0.5 4 2 1.6+0.5 5 2 2.0+0.5 0 1 2 3 4 5 3 2 1 Line: P0(0, 0)-- P1(5, 2)