计算机图形学

计算机图形学课程内容绪论介绍计算机图形学的含义、研究内容、应用及发展情况基本图形生成算法介绍有关在图形终端上显示图形的算法图形变换介绍二维、三维的几何变换及三维投影变换课程内容--续二维图形的运算二维图形裁减、添充及求交高级话题曲线、曲面消隐几何造型附加内容及应用实践AUTOCAD入门、上机操作主要参考书、期刊孙家广、杨长贵，计算机图形学（新版），清华大学出版社，1995谢步瀛，计算机绘图教程，上海同济大学出版社，1995计算机辅助设计与图形学学报第一章绪论一、计算机图形学的含义

ISO的定义：

计算机图形学是研究通过计算机将数据转换为图形，并在专门的显示设备上显示的原理、方法和技术的学科

数据图形显示模型

二、计算机图形学的发展及应用1.发展情况50年代：诞生MIT旋风I号、CALCOMP滚筒绘图仪、GERBER的平板绘图仪60年代：确立并蓬勃发展MIT的IvanE.Sutherland--”Sketchpad--一个人机通信的图形系统“博士论文拉开图形学研究的序幕；大公司开展大规模研究（通用、AT&T、BELL）70、80年代：进入实用化更完备的硬件系统，个人计算机、工作站系统大量图形应用软件出现90年代：广泛深入的应用标准化、集成化、智能化多媒体技术、人工智能、科学计算可视化、虚拟现实三维造型技术2.应用用户接口：人机界面CAD/CAM：机械、电子、汽车、飞机等办公自动化、电子印刷、管理绘图绘制勘探、测量图形：地理、地形模拟现实：艺术、工业、农业科学计算可视化：天气预报，过程模拟，CAI：计算机辅助教学、幼儿教育其它：医疗、刑侦三、计算机图形学的研究内容基本图素的生成点、线、圆、字符的生成图形的基本操作和处理并、交、差、裁减、填充、变换图形的输入输出交互输入、扫描输入、图形终端显示、图纸输出三维几何造型实体造型、曲面造型、特征造型真实感图形生成消隐、浓淡图、光照模型科学计算可视化分析数据的图形描述四、计算机图形系统的组成

计算机图形系统是计算机硬件（包括中央处理机、图形输入输出设备），以及软件（包括系统软件和图形软件）的集合。（一）基本功能要求计算功能：点、线、面的表示，求交，变换等存储功能：在计算机中存储图形数据对话功能：实时显示出用户操作结果输入功能：输入用户的设计、绘制要求输出功能：显示、保存（二）组成硬件及软件硬件1.输入设备鼠标器：光电式、光机式、机械式光笔触摸屏：电阻式、电容式、红外线式坐标数字化仪图形扫描仪

2.显示设备阴极射线管式随机扫描(60年代中期）存储管式（60年代后期）光栅扫描式（70年代中期）液晶显示器（LCD）等离子显示器3.绘图设备图形打印机针式打印机喷墨打印机激光打印机绘图机静电绘图仪笔式绘图仪：平板式、滚筒式软件系统软件：操作系统（UNIX，WINDOWS）、语言系统（C，C++）图形系统软件：图形支撑软件（OpenGL,PHIGS,etc.)、系统软件(AutoCAD,Pro/Engineer,UGII,I-DEAS,Alias/Wavefront,AVS,etc.)(三）常用计算机图形系统个人计算机图形系统：是由个人计算机（PC）加上图形输入输出设备和有关图形支撑软件集成起来的系统。价格便宜、功能及性能不强工作站图形系统：UNIX、OPENGL，图形系统软件著名工作站：HP、SGI、SUN价格较昂贵、功能强大、性能良好两种系统的比较光栅扫描图形显示器原理帧缓冲器显示控制器D/A转换器CRT返回连续存储器,每个象素需一个存储位PC计算机鼠标键盘彩色图形显示器(TVGA)打印机绘图机个人计算机图形系统硬件组成返回特征PC机工作站处理器总线虚拟存储网络操作系统整数处理速度(MIPS)尺寸图形价格CISC,C/RRISCAT,EISASBUS,MBUS

无有选择有OS/2,WINDOWSUNIX1-1005-20012-17

16-27二维三维300-50005000-10万

性质CRTLCD等离子显示器功耗大小中屏幕大小中平面度一般好中分辩率中一般好视角大一般中色彩丰富中中亮度好中好价格低低中第二章基本图形生成算法本章将主要研究在光栅显示器上的直线、圆的生成算法。

几何图形Ｇ＝｛Ｐi|

Pi最接近图形的象素

｝基本图形的生成算法任务之一就是找出所有的Ｐi.第二章基本图形生成算法本章将主要研究在光栅显示器上的直线、圆的生成算法。

几何图形Ｇ＝｛Ｐi|

Pi最接近图形的象素

｝基本图形的生成算法任务之一就是找出所有的Ｐi.一、直线的生成算法

即是找出逼近直线的一组象素，按扫描线顺序，对这些象素进行写操作。1.数值微分法（ＤＤＡ）

假定直线的起点、终点分别为：（X0,Y0),(X1,Y1)，且都为整数。

(Xi+1,Yi+k)(Xi,Int(Yi+0.5))(Xi,Yi)栅格交点表示象素点位置。。。。直线的斜率：

k=(Y1-Y0)/(X1-X0)

为讨论方便，假定|k|<=1

直线方程：Ｙ=k*X+B设Ｘ的增量为Ｄx=１，可得如下Ｙ的增量方程：

Yi+1=kXi+1+B=k(Xi+Dx)+B=kXi+B+kDx=Yi+kDx=Yi+k程序实现：DDALine(X0,Y0,X0,Y0,Color)intX0,Y0,X1,Y1,Color;{intXfloatdx,dy,k,ydx=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;}}缺点：浮点运算、取整－－》废时，且不利于硬件实现。问题：为什么｜k｜《１？，若｜k｜>１，上述算法会出现什么情况？应如何处理？2.中点画线法原理：假定直线斜率K<1，且已确定点亮象素点P（Xp,Yp

）M为中点，Q为交点现需确定下一个点亮的象素。P（Xp,Yp)MQP2P1显然可得出如下结论：若M在Q的下方，选P2，否则选P1算法实现：假设直线的起点、终点分别为：（X0,Y0),(X1,Y1)

该直线方程可表示为：

F(x,y)=a*x+b*y+c（1）

其中：

a=Y0-Y1,b=X1-X0,c=X0*Y1-X1*Y0

当：

F(Xt,Yt)=0++>(Xt,Yt)在直线上

F(Xt,Yt)<0++>(Xt,Yt)在直线下方

F(Xt,Yt)>0++>(Xt,Yt)在直线上方因此：将中点M坐标代入（1）式，并判断其符号即可确定象素点的选取。构造如下判别式：

d=F(M)=F(Xp+1,Yp+0.5)=a(Xp+1)+b(Yp+0.5)+c

由上式可看出，d是x,y线性函数，可推导d的增量公式。当d>=0时，取象素P1，此时再下一个象素的判别式为：

d’=F(Xp+2,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c=a(Xp+1)+b(Yp+0.5)+c+a=d+a;当d<0时，取象素P2，此时再下一个象素的判别式为：

d’=F(Xp+2,Yp+1.5)=a(Xp+2)+b(Yp+1.5)+c=a(Xp+1)+b(Yp+0.5)+c+a+b=d+a+b;d的初始值可按下式计算：

d0=F(X0+1,Y0+0.5)=a(X0+1)+b(Y0+0.5)+c=F(X0,Y0)+a+0.5b=a+0.5b

由于只用d的符号作判断，为了只包含整数运算,可取2d

代替d，这样可得如下中点算法程序：

MidpointLine(X0,Y0,X1,Y1,Color)intX0,Y0,X1,Y1,Color;{inta,b,d1,d2,d,x,y;a=Y0-Y1;b=X1-X0;d=a+a+b;d1=a+a;d2=a+b+a+b;x=X0;y=Y0; drawpixle(x,y,Color);while(x<X1){if(d<0){x++;y++;d+=d2;}

else{x++;d+=d1;}drawpixle(x,y,Color);}/*while*/}/*MidPointLine*/

习题：按照中点划线算法，确定直线（0，0）（5，3）的点亮象素。列出计算过程，并列出所选象素坐标。

3.Bresenham画线算法原理：dddd假定直线斜率,0<k<1,起点坐标为(x,y);下一个点亮象素可能是：(x+1,y)或(x+1,y+1)。这可通过d值的大小来确定:d=d+k,当d>1时d=d-1;当d<0.5取(x+1,y)，否则取(x+1,y+1)。令e=d-0.5,显然e的初值为-0.5。这样可用e的符号来进行判断。程序如下：

BresenhamLine(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;{intx,y,dx,dy;floatk,e;inte;dx=x1-x0;dy=y1-y0;k=dy/dx;e=-0.5;x=x0;y=y0;e=-dx;for(i=0;i<=dx;i++){drawpixel(x,y,color);x++;e=e+k;e1=e-0.5;e=e+2*dy;e1=e-dx;if(e1>0)e=e-1;e=e-2*dx;if(e>=0)y++;}}

思考题：如何去除上述程序中的浮点运算、乘除法？就是要使得e值为整数

e’=2*dx*ee>0==>e’>0;e<0==>e’<0

二、圆的生成算法

即是找出逼近圆的一组象素，按扫描线顺序，对这些象素进行写操作。

下面仅以圆心在原点的圆为例，讨论圆的生成算法。1.圆弧扫描算法

X2+Y2=R2Y=Sqrt(R2-X2)在一定范围内，每给定一X值，可得一Y值。当X取整数时，Y须圆整。缺点：浮点运算，开方，圆整，不均匀。2.角度DDA法

x=x0+Rcosy=y0+Rsindx=-Rsinddy=Rcosdxn+1=xn+dxyn+1=yn+dyxn+1=xn-(yn-y0)dyn+1=yn+(xn-x0)d

显然，确定x,y的初值及d值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算。3.中点法利用圆的对称性，只须讨论1/8圆。MP1P2P（Xp，Yp）P为当前点亮象素，那么，下一个点亮的象素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp+1)。

构造一函数：

F（X，Y）=X2+Y2-R2F（X，Y）=0（X，Y）在圆上；

F（X，Y）<0（X，Y）在圆内；

F（X，Y）>0（X，Y）在圆外。M为P1、P2间的中点，M=(Xp+1,Yp-0.5)有如下结论：

F（M）<0取P1F（M）>=0取P2为此，可采用如下判别式：

d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2

若d<0,则P1为下一个象素，那么再下一个象素的判别式为：

d=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2

=d+2xp+3

即d的增量为2xp+3.

若d>=0,则P2为下一个象素，那么再下一个象素的判别式为：

d=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2

=d+2(xp-yp)+5

即d的增量为2(xp-yp)+5.d的初值:d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-RMidpointCircle(r,color)intr,color;{intx,y;floatd;x=0;y=r;d=1.25-r;drawpixel(x,y,color);while(x<y){if(d<0){d+=2*x+3;x++}else{d+=2*(x-y)+5;x++;y--;}}}习题：在上述程序基础之上，写出一新程序，使其仅为整数运算，且不含乘除法。光栅扫描图形显示器原理帧缓冲器显示控制器D/A转换器CRT返回连续存储器,每个象素需一个存储位第三章图形变换图形变换是计算机图形学基础内容之一。几何变换，投影变换，视窗变换线性变换，属性不变，拓扑关系不变。作用：把用户坐标系与设备坐标系联系起来；可由简单图形生成复杂图形；可用二维图形表示三维形体；动态显示。内容：以下几方面的内容：数学基础：矢量、矩阵及运算二维几何变换三维几何变换投影变换视窗变换裁剪一、矢量、矩阵及运算1.矢量的含义矢量：是由n个实数组成的集合。如：二维矢量(x,y)，三维矢量(x,y,z)(x,y)XYXYZ(x,y,z)2.矢量运算假定：V1(x1,y1,z1),V2(x2,y2,z2)为两个矢量，则有：矢量和

V1+V2=(x1+x2,y1+y2,z1+z2)矢量点积

V1·V2=x1*x2+y1*y2+z1*z2矢量叉积

V1×V2=(y1z2-y2z1,z1x2-z2x1,x1y2-x2y1)矢量长度

|V1|=(V1·V1)1/2=(x1*x1+y1*y1+z1*z1)1/2

3.矩阵的含义矩阵：由m×n个数按一定位置排列的一个整体，简称m×n矩阵。A=其中，aij称为矩阵A的第i行第j列元素4.矩阵运算加法设A，B为两个具有相同行和列元素的矩阵A+B=数乘kA=[k*aij]|i=1..m,j=1,n乘法设A为3×2矩阵，B为避免2×3矩阵

C=A·B=C=Cm×p=Am×n·Bn×pcij=∑aik*bkj单位矩阵在一矩阵中，其主对角线各元素aii=1,其余皆为0的矩阵称为单位矩阵。n阶单位矩阵通常记作InAm×n=Am×n·Ink=1,n逆矩阵若矩阵A存在A·A-1=A-1·A=I，则称A-1为A的逆矩阵矩阵的转置把矩阵A=(aij)m×n的行和列互换而得到的n×m矩阵称为A的转置矩阵,记作AT

。

(AT)T=A(A+B)T=AT+BT(aA)T=aAT(A·B)T=BT·AT

当A为n阶矩阵，且A=AT，则

A是对称矩阵。5.矩阵运算的基本性质交换律与结合律师

A+B=B+A;A+(B+C)=(A+B)+C数乘的分配律及结合律

a(A+B)=aA+aB;a(A·B)=(aA)·B=A·(aB)(a+b)A=aA+bAa(bA)=(ab)A矩阵乘法的结合律及分配律

A(B·C)=(A·B)C(A+B)·C=A·C+B·CC·(A+B)=C·A+C·B矩阵的乘法不适合交换律二、变换的一般流程二维变换的一般流程：三维变换的一般流程：基本元素几何图形屏幕窗口区几何变换开窗与裁剪视窗变换基本体素几何图形屏幕窗口区几何变换变换、裁剪视窗变换观察空间投影变换三、二维图形变换1.平移变换从点P[x,y]平移到点P’[x’,y’]x’=x+my’=y+nP(x,y)P’(x’y’)mnXY2旋转变换αθρ(x,y)(x’,y’)一个点绕原点的旋转，逆时针方向为正。3比例变换P(x,y)P’(x’,y’)x’=x*sxy’=y*sySx=Sy：均匀缩放。Sx=Sy>1，放大Sx=Sy<1，缩小Sx不等于Sy时，沿坐标轴方向伸展和压缩YX4.对称变换关于X轴的对称变换

P(x,y)对称点为P’(x,-y)关于Y轴的对称变换

P(x,y)对称点为P’(-x,y)关于坐标原点的对称变换

P(x,y)关于原点的对称点为P’(-x,-y)5错切变换(SHEAR)(1)沿x方向产生错切

x’=x+y*tag(θ) y’=y(2)沿y方向产生错切

x’=x y’=y+x*tag(θ)θ(x,y)(x’,y’)θ(x,y)(x’,y’)YXYX1.齐次坐标

齐次坐标就是一个n维矢量的(n+1)维矢量表示。例如：二维坐标点P(x,y)的齐次坐标为：(H*x,H*y,H)。

二维坐标与齐次坐标是一对多的关系。通常都采用规格化的齐次坐标，即取H=1。(x,y)的规格化齐次坐标为(x,y,1)。

齐次坐标的几何意义：可理解为在三维空间上第三维为常数的一平面上的二维向量。四、二维图形变换的矩阵表示齐次坐标的作用：

1.将各种变换用阶数统一的矩阵来表示。提供了用矩阵运算把二维、三维甚至高维空间上的一个点从一个坐标系变换到另一坐标系的有效方法。2.便于表示无穷远点。例如：（x*H,y*H,H)，令H等于0，1.恒等变换2.比例变换3.对称变换关于X轴的对称变换

关于Y轴的对称变换

关于坐标原点的对称变换

习题：请写出二维错切变换的变换矩阵。5.旋转变换其矩阵表示为：αθρ(x,y)(x’,y’)6.平移变换P(x,y)P’(x’y’)mnXY7.绕任一点的旋转变换假定该任一点为P(m,n),旋转角为θ变换过程如下：(m,n)(x,y)θ(x’,y’)(x1,y1)θ(x2,y2)mn123(x’,y’)T1T2T3T=T1T2T3

称为矩阵级联，也称复合变换。问题：如何将平面上一正方形绕原点进行旋转变换？对圆又如何变换？习题：

1请写出二维错切变换的变换矩阵。

2试推导将二维平面上任一条直线P(x1,y1),Q(x2,y2)变换成与坐标轴X重合的变换矩阵。

第四章二维图形的运算

在本章将主要介绍一些二维图形的常用运算方法。包括交点计算、几何图形的关系判别及线段裁剪等。一、交点计算1.两直线段的交点设有两线段S1，S2。S1的端点分别为P1(x1,y1),P2(x2,y2),S2的端点分别为P3(x3,y3),P4(x4,y4).则两直线段的参数方程为：讨论：无解，此时意味两线段平行或重合；有唯一解，但不一定是有效解，有效解应该是交点必须位于两直线段上。此时应满足如下条件：

0≤u≤1.00≤v≤1.0根据u,v的值，即可获得交点的坐标。2.直线段与圆弧的交点讨论：无解，第一种情况；一解，第三种情况；两解，第二种情况。当有解时，还须进一步判断：0≤t≤1.0,αs≤α≤αe12312343.两圆弧的交点设有两段圆弧A，B。A圆弧的圆心坐标(xa,ya),半径为ra,B圆弧的圆心坐标(xb,yb),半径为rb。

则有如下方程：如果两圆相交，则应有：讨论：两圆之间的关系存在以上三种。而对圆弧来说，有效解应在圆弧的定义域内：即：二、关系判别1.点的包含性检验点的包含性检验是指：判断一个点是否被包含在某一个区域内。为讨论方便，我们定义该区域为一多边形。但所采用的方法可推广到曲线边界。夹角和法设有一个点P和多边形ABCDE，如下图所示：ABCDE

若依次将P点与多边形各顶点相连，且令αi为多边形各相邻顶点与点P相连所形成的夹角。则有如下结论：若∑αi=0,则点P在多边形之外；

若∑αi=±2π,则点P在多边形之内；夹角αi的计算可采用余弦定理获得。而其方向则可按右手法则确定，用公式表示如下：连线为两矢量Vi,Vi+1,,则Vi×Vi+1=因此，可用如下判别式判断夹角的方向：当T>0时，为逆时针方向；当T<0时，为顺时针方向。交点数判别法

ABCDEABCDE交点数法所利用的原理：由P点向任一方向作一条射线，然后求出该射线与多边形边的交点数。则有：

1）当交点数为偶数（0）时，则说明点P在多边形外；

2）当交点数为奇数时，则说明点P在多边形内。

为处理简单，通常射线的与坐标轴平行。奇异情况处理：即当射线穿过多边形顶点时的特殊处理。

当射线穿过的顶点两边在射线两侧，此时认为相交一次。而在同侧时，则认为相交两次。ABCDE122.多边形重叠性检验通常采用“最小最大试验法”，也称为“排斥试验法”。这种方法可迅速排除掉不可能相互重叠的情况，从而减少计算工作量，加快图形处理速度。1）多边形的最小包含矩形是指平面上能包含多边形的最小的矩形。如下图所示。

最小包含矩形2）重叠性检验利用最小包含矩形，可排除两个多边形不重叠情况。

如果两个多边形的最小包含矩形，不发生重叠，则这两个多边形必不重叠。123

假定两个多变形的最小矩形为a和b,左下角和右上角的坐标分别为：

则当a,b两矩形满足下列条件之一时，a和b不重叠

Xamax<=XbminYamax<=YbminXamin>=XbmaxYamin>=Ybmaxab(Xamin,Yamin)(Xamax,Yamax)(Xbmin,Ybmin)(Xbmax,Ybmax)XY

当a、b两矩形不满足上述条件，即意味两多边形可能重叠。此时需通过两多边形的边边求交来判断是否重叠。当存在交点时，既表明两多边形重叠，否则不重叠。四、几何图形的裁剪

就是在一个图形的整体中，把窗口的内部分和窗口外部分正确地分离开来。这种技术称为裁剪。1.线段裁剪线段和窗口的关系

要确定一条直线段上位于窗口内的可见段，只须求出它的两个位于窗口内的可见端点即可。 算法的基本思想 把所有的直线按照它和窗口的关系分类，不同的直线使用不同的处理方法确定其可见部分。矢量裁剪算法用窗口的四条边界的直线将窗口分为9个区。012345678(x1,y1)(x2,y2)ybytxlxr排斥性测试若线段满足下述四个条件之一时：max(x1,x2)≤xlmin(x1,x2)≥xrmax(y1,y2)≤ybmin(y1,y2)≥yt则线段必定位于窗口之外，无输出线段。包含性测试若线段满足：xl≤x1≤xr,yb≤y1≤yt,则线段的始点在0区，也即线段可见段的起点为：

xs=x1,

ys=y1求交点，并判断I.若x1＜xl,则：线段的起点坐标可能位于3区、4区、5区。而新起点的坐标可能在直线y=yb和线段的交点上直线y=yt和线段的交点上直线x=xl和线段的交点上012345678(x1,y1)(x2,y2)ybytxlxr第一种情况：此时，若xl≤xs≤xr则(xsys)为有效新起点。第二种情况：此时，若xl≤xs≤xr则(xsys)为有效新起点。第三种情况：此时，若yb≤ys≤yt则(xsys)为有效新起点。三种情况都不满足，则此线段不在窗口区内。II.若x1>xr

线段的起点坐标可能位于6区、7区、8区。而新起点的坐标可能在直线y=yb和线段的交点上直线y=yt和线段的交点上直线x=xr和线段的交点上012345678(x1,y1)ybytxlxr第一种情况：此时，若xl≤xs≤xr则(xsys)为有效新起点。第二种情况：此时，若xl≤xs≤xr则(xsys)为有效新起点。第三种情况：

此时，若yb≤ys≤yt则(xsys)为有效新起点。若此三种情况都不满足，则此线段不在窗口区内。若Xl<=X<=Xr线段的起点坐标可能位于1区和2区。而新起点的坐标可能在直线y=yb和线段的交点上直线y=yt和线段的交点上012345678(x1,y1)ybytxlxr第一种情况：此时，若xl≤xs≤xr则(xsys)为有效新起点。第二种情况：

此时，若xl≤xs≤xr则(xsys)为有效新起点。若此二种情况都不满足，则此线段不在窗口区内。

使用同样的方法，可得到直线在窗口的另一个可见端点。编码法该法的基本思想是：1)首先判断线段是否完全位于窗口内，如果是，则输出原线段，如果不是，那么再进而判断是否完全位于窗口外，若是，则排除该线段，无输出。2)如果以上测试都不满足的话，那么就将该线段用窗口边线分割为二段，然后再回到1)进行上述测试。实现方法：将窗口边线两边沿长，得到九个区域，每一个区域都用一四位二进制数标识，直线的端点都按其所处区域赋予相应的标识码。100100010101100000000100101000100110ABCD第一位1：点处于左边框线的左边；第二位1：点处于右边框线的右边；第三位1：点处于下边框线的下边；第四位1：点处于上边框线的上边；显然： 如果某线段的两端点的两个四位代码全为零时那么该线段完全位于窗口内；如果两端点的标识码的逻辑乘不为零，那么该线段必位于窗口外。如果线段被分割，端点有了新的代码，然后再进行上述测试，测试结果是必有一段在窗口之外，可被排除，另一段再重复上述处理过程。如何判定该与窗口的哪条边求交呢？ 编码中对应位为1的边。中点分割算法定义：线段端点的最远可见点是指任一线段被窗口裁剪后所得两个新端点中离该端点较远的一个点。如下图所示。

A的最远可见点为a,B的最远可见点为b.ABab中点分割法的基本思想即是：不断地用对分方法，舍去线段的不可见部分，用中点去逼近线段与窗口边界的交点。

实现算法：（以A点为例说明）

1)排斥性测试，测试线段是否完全被排斥在窗口之外，若是，则无线段输出，算法结束。否则执行下一步；

2)包含性测试，测试B点是否包含在窗口内，如果是，则B点即为A的最远可件点，算法结束，否则，执行下一步；

3)将直线段AB于中点M处分割，则分如下几种情况处理：线段MB完全在窗口之外，那么便以线段AM为新的线段AB，然后返回算法的第一步重新开始测试；如果线段MB没有被完全排斥在窗口之外，那么便以线段MB作为新线段AB，然后返回算法的第一步1）。ABMABMABMABM

#defineTRUE1#defineFALSE0intmid_trim(p1,p2,xmin,ymin,xmax,ymax,a)floatp1[3],p2[3],xmin,ymin,xmax,ymax,a[3];{floatA[3],B[3],M[3];set_point(p1,A);set_point(p2,B);while(TRUE){