浙江大学：《计算机图形学》 第三章 直线、圆、椭圆生成算法

第三章直线、圆、椭圆生成算法 图形的扫描转换(光栅化):确定一个像素集合,用 于显示一个图形的过程。步骤如下: 1、确定有关像素 2、用图形的颜色或其它属性,对像素进行写操作。 对一维图形,不考虑线宽,则用一个像素宽的直线来 显示图形。二维图形的光栅化,即区域的填充:确定 像素集,填色或图案。 任何图形的光栅化,必须显示在一个窗口内,否则不 予显示。即确定一个图形的哪些部分在窗口内,哪些 在窗口外,即裁剪。 浙江大学信息学院 计算机图形学

浙江大学信息学院 计算机图形学 第三章 直线、圆、椭圆生成算法 图形的扫描转换（光栅化）：确定一个像素集合，用 于显示一个图形的过程。步骤如下： 1、确定有关像素 2、用图形的颜色或其它属性，对像素进行写操作。 对一维图形，不考虑线宽，则用一个像素宽的直线来 显示图形。二维图形的光栅化，即区域的填充：确定 像素集，填色或图案。 任何图形的光栅化，必须显示在一个窗口内，否则不 予显示。即确定一个图形的哪些部分在窗口内，哪些 在窗口外，即裁剪

图形显示前需要:扫描转换+裁剪 ●裁剪—)扫描转换:最常用,节约计算时间 ●扫描转换--〉裁剪:算法简单: 图元二维 扫描 裁剪 转换 浙江大学信息学院 计算机图形学

浙江大学信息学院 计算机图形学 图形显示前需要：扫描转换+裁剪 ●裁剪---〉扫描转换：最常用，节约计算时间。 ●扫描转换---〉裁剪：算法简单；

本章内容 ?扫描转换直线段 DDA算法 中点画线法 Bresenham画线算法 ?圆弧、椭圆弧扫描转换 中点算法 内接正多边形迫近法 等面积正多边形逼近法 生成圆弧的正负法 浙江大学信息学院 计算机图形学

浙江大学信息学院 计算机图形学 本章内容 ？扫描转换直线段 DDA算法 中点画线法 Bresenham画线算法 ？圆弧、椭圆弧扫描转换 中点算法 内接正多边形迫近法 等面积正多边形逼近法 生成圆弧的正负法

直线段的扫描转换算法 直线的扫描转换:确定最佳逼近于该直线 的一组象素,并且按扫描线顺序,对这 些象素进行写操作。 个常用算法: 数值微分法(DDA) 中点画线法 Bresenham算法 浙江大学信息学院 计算机图形学

浙江大学信息学院 计算机图形学 直线段的扫描转换算法 • 直线的扫描转换: 确定最佳逼近于该直线 的一组象素，并且按扫描线顺序，对这 些象素进行写操作。 • 三个常用算法： 数值微分法（DDA） 中点画线法 Bresenham算法

数值微分法(DDA) 假定直线的起点、终点分别为:(x0,y0) (x1y1),且都为整数 x+1,Y1+k) 栅格交点表示象素点位置 Xi, Int(Yi +0.5)) 浙江大学信息学院 计算机图形学

浙江大学信息学院 计算机图形学 数值微分法（ＤＤＡ） 假定直线的起点、终点分别为：（x0,y0), (x1,y1)，且都为整数。 (X i+1 ,Yi + k) (X i , Int(Yi +0.5)) (X i , Yi) 栅格交点表示象素点位置 。 。 。

数值微分DDA法 基本思想 已知过端点PO(xO,y0,P1(x1,y1)的直线段L y=kx+b 直线斜率为 x=x→x1;x=x+ stepx y=kx+b (x,rond(少) 这种方法直观,但效率太低,因为每一步需要一次浮点乘法 和一次舍入运算。 浙江大学信息学院 计算机图形学

浙江大学信息学院 计算机图形学 数值微分(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+1=kx1+1+b =kx:+b+k△x y+k△x 当△x=1;y1+1=y;+k 即:当x每递增1,y递增k(即直线斜率); 注意上述分析的算法仅适用于k≤1的情形。 在这种情况下,x每增加12y最多增加1。 当k>1时,必须把x,y地位互换 浙江大学信息学院 计算机图形学

浙江大学信息学院 计算机图形学 数值微分(DDA)法 计算yi+1= kxi+1+b = kxi+b+kx = yi+kx 当x =1; yi+1 = yi+k • 即：当x每递增1，y递增k(即直线斜率)； • 注意上述分析的算法仅适用于k ≤1的情形。 在这种情况下，x每增加1,y最多增加1。 • 当 k 1时，必须把x，y地位互换

数值微分①DDA法 增量算法:在一个迭代算法中,如果每 步的x、y值是用前一步的值加上一个 增量来获得,则称为增量算法 DDA算法就是一个增量算法 浙江大学信息学院 计算机图形学

浙江大学信息学院 计算机图形学 数值微分(DDA)法 • 增量算法：在一个迭代算法中，如果每 一步的x、y值是用前一步的值加上一个 增量来获得，则称为增量算法。 • DDA算法就是一个增量算法

数值微分ODDA法 void ddaline(int xo, int yo, int xI, int y1, int color) i int x; float dx, dy, y, k dx y-y1-y k=dy/dx; y=yo for(x=X0;X≤x1,X+) i drawpixel(x, int(y+0. 5), color) /y+k 浙江大学信息学院 计算机图形学

浙江大学信息学院 计算机图形学 数值微分(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 ; xx1 , x++)  drawpixel (x, int(y+0.5), color); y=y+k;  

数值微分DDA法 例:画直线段P(0,0)-P(5,2) x int(y+0. 5) 0.5 Line:PO(0,0)-P1(5,2) 00 0+0.5 0.4+0.5 0.8+0.5 2345 1.2+0.5 1.6+0.5 012345 2.0+0.5 浙江大学信息学院 计算机图形学

浙江大学信息学院 计算机图形学 数值微分(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)