计算机图形学实验指导书(14)

B．圆、椭圆生成算法 一、实验目的

编写圆和椭圆的扫描转换算法程序，验证算法的正确性。

二、实验任务（2学时）

1． 编写中点画圆法的扫描转换程序，考虑原点在（x0,y0）处程序的改动； 2． 添加鼠标程序，实现交互式画圆； 3． 编写中点画椭圆法的扫描转换程序； 4． 添加鼠标程序，实现交互式画椭圆；

三、实验内容

圆的Bresenham算法

设圆的半径为r。先考虑圆心在(0, 0)，并从x=0、y=r，开始的顺时针方向的1/8圆周的生成过程。在这种情况下，x每步增加1，从x=0开始，到x=y结束。即有 xi+1 = xi + 1

相应的yi+1则在两种可能中选择： yi+1 = yi或者yi+1 = yi-1 选择的原则是考察精确值y是靠近yi还是 靠近yi-1(如右图)， 计算式为 y2 = r2-(xi+1)2

d1 = yi2-y2 = yi2-r2+(xi+1)2

d2 = y2-(yi-1)2 = r2-(xi+1)2-(yi-1)2 令pi=d1-d2，并代入d1、d2，则有 pi = 2(xi+1)2 + yi2 + (yi-1)2-2r2

pi称为误差。如果pi<0则yi+1=yi，否则yi+1=yi-1。 pi的递归式为

pi+1 = pi + 4xi +6+2(yi+12- yi2) -2(yi+1-yi) pi的初值由上式代入xi=0，yi=r而得 p1 = 3-2r

根据上面的推导，圆周生成算法思想如下： ⒈ 求误差初值，p1=3-2r，i=1，画点(0, r)；

⒉ 求下一个光栅位置，其中xi+1=xi+1，如果pi<0则yi+1=yi，否则yi+1=yi-1； ⒊ 画点(xi+1, yi+1)；

⒋ 计算下一个误差，如果pi<0则pi+1=pi+4xi+6，否则pi+1=pi+4(xi-yi)+10； ⒌ i=i+1，如果x=y则结束，否则返回步骤2。

-- 37

任务一：中点画圆法的扫描转换算法

编写中点画圆法的扫描转换程序，考虑原点在（x0,y0）处程序的改动；

分析：考虑圆心不在原点，设圆心坐标为（x0,y0）。通过平移坐标原点到圆心，则第二个8分圆上一点p(x,y)，其原始坐标为 x’=x+x0 y’=y+y0

即p’1（x0 +x, y+y0）

其它7个对称点分别是：p’2（x0+y,y0+x）, p’3 (x0+y,y0-x)，p’4 (x0+x,y0-y)，p’5 (x0-x,y0-y)，p’6 (x0-y,y0-x)，p’7 (x0-y,y0+x)，p’8 (x0-x,y0+y)

p’1（x0 +x, y0+y） Y’ Y 算法程序如下：

p(x,y)

MidpointCircle(int x0,int y0,int r, int color) p’8 (x0-x,y0+y) R {

p’2（x0+y,y0+x） int x,y; p’7 (x0-y,y0+x) float d;

(x0,y0) X’ x=0; y=r ; d=1.25-r ;

p’6 (x0-y,y0-x) CirPot(x0,y0,x,y,color); p’3 (x0+y,y0-x) while (x<=y)

p’4 (x0+x,y0-y)） { p’5 (x0-x,y0-y) if(d