裁剪算法 直线段裁剪1.直线段和窗口的关系我们所说的窗口是各边平行于坐标轴的矩形。

窗口把一个直线段分成窗口内部分和窗口外部分。

通常落在窗口内部分是可见的，而落在窗口外部分是不可见的。

裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。

这个选择过程称为裁剪。

裁减的依据是一对简单的不等式：通常，我们只要验证点的坐标是否满足上述条件即可。

然而，如果逐点验证上述不等式，运算效率是非常低的。

直线段和窗口的关系有 (1)直线段在窗口外； (2)直线段完全在窗口内；(3)直线段与窗口的一条边相交； (4)直线段与窗口的两条边相交；结论：对于任意一条直线，它要么被完全排斥在窗口之外；要么在窗口内留下一个可见段，并且只能有一个可见段。

⎩⎨⎧≤≤≤≤t b l l xy y x x x3.实现方法端点在窗口内。

段只有一个只有一个成立，则直线或如果满足.22211⎩⎨⎧<<<<⎩⎨⎧<<<<t b rl t b r l y y y x x x y y y x x x窗口外。

端点在窗口外或直线段两个都不成立，则直线段的和如果满足.32211⎩⎨⎧<<<<⎩⎨⎧<<<<t b rl t b r l y y y x x x y y y x x x()()⎩⎨⎧≤≤≤≤⎪⎩⎪⎨⎧=+-=+-=10来判断是否满足11交点计算.42121t y y y xx tyy t y tx x t x tb l代码裁剪法基本思想：对于每条线段P 1P 2分为三种情况处理: （1）若P 1P 2完全在窗口内，则显示该线段P 1P 2简称“取”之。

（2）若P 1P 2明显在窗口外，则丢弃该线段，简称“弃”之。

（3）若线段不满足“取”或“弃”的条件，则在交点处把线段分为两段。

其中一段完全在窗口外，可弃之。

然后对另一段重复上述处理。

为快速判断，采用如下编码方法：()()直线段在窗口内。

和如果满足，右上角为，假设窗口左下角坐标为⎩⎨⎧<<<<⎩⎨⎧<<<<t b rl t b r l t r b l y y y x x x y y y x x x y x y x 2211.1,,每个区域赋予4位编码l r b t C C C C⎩⎨⎧<=⎩⎨⎧>=other y y C othery y C b t 0101minmax⎩⎨⎧>=⎩⎨⎧>=other x x C otherx x C l r 0101minmax若P 1P 2完全在窗口内code1=0,且code2=0,则“取” 若P 1P 2明显在窗口外code1&code2≠0，则“弃”在交点处把线段分为两段。

其中一段完全在窗口外，可弃之。

然后对另一段重复上述处理。

中点分割裁剪算法基本思想：与前一种Cohen-Sutherland 算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况:全在、完全不在和线段和窗口有交。

对前两种情况，进行一样的处理。

对于第三种情况，用中点分割的方法求出线段与窗口的交点。

求线段与窗口的交点P0A 、B 分别为距P 0、P 1最近的可见点，P m 为P 0P 1中点从出发找最近可见点的方法先求出的中点若不是显然不可见的，并且在窗口中有可见部分，则距最近的可见点一定落在上，所以用代替；否则取代替再对新的求中点。

重复上述过程，直到长度小于给定的控制常数为止，此时收敛于交点Ａ。

从出发找最近可见点采用上面类似方法。

多边形裁剪基本思想是一次用窗口的一条边裁剪多边形。

考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分:可见一侧；不可见一侧基本思想是一次用窗口的一条边裁剪多边形。

考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分:可见一侧；不可见一侧可见一可见一侧p SS Sp p(1)(2)(3)(4)对于情况（1）仅输出顶点P；情况（2）输出0个顶点；情况（3）输出线段PS与裁剪线的交点I；情况（4）输出线段PS与裁剪线的交点I和终点P上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。

对于每一条裁剪边，只是判断点在窗口哪一侧以及求线段PS与裁剪边的交点算法应随之改变。

多边形运算1.多边形的覆盖1)多边形覆盖情况分析当两个多边形互相重叠时，就会产生覆盖的效果。

覆盖是指一个多边形部分或全部地盖掉了下面的另一个多边形对于多边形的覆盖，特别是凹多边形，由于情况比较复杂，画图的步骤一般是：①利用“重叠性检验”，排除不会发生覆盖的多边形。

②逐条求出被覆盖多边形的边和覆盖多边形轮廓边的交点。

③对交点进行排序。

④利用“包含性检验”，区分出被覆盖段和未覆盖段。

⑤绘图输出未覆盖线段。

2.多边形的布尔运算1)布尔运算的概念多边形的布尔运算指的是：在两个多边形之间进行并、交、差的运算。

2)多边形的描述任何一个多边形均是由顶点和边组成的。

所以可以把多边形的数据结构组成两张数据表：顶点表和边表。

通常，在实际的布尔运算处理中，为了方便把多边形的边表改为环表。

环表是由组成多边形的顶点按照一定的顺序连接而成。

在环表中，每相邻两个顶点组成一条有向线段，它的方向与环的方向相同。

3)布尔运算的规则在两个多边形有相互重叠的部分时，两个多边形可以进行布尔运算。

当两个多边形相互重叠时，表示两个多边形的两个环相交，其交点将有向直线段分为两部分：环内部分和环外部分，分别表示处于另一个环的内部或外部。

交点分为出点和入点两种：当一个环的有向线段经过交点进入另一环，则该交点称为入点；反之，如果是走出另一环，则该交点称为出点。

在进行布尔运算时，搜索新环的路径应该从交点处开始。

其运算规则如下：(1)并运算顺着环的方向搜索，当遇到的交点为入点时，则从该点在另一环上的对应点转入另一环，然后沿另一环的方向搜索；当遇到的交点为出点时，则继续顺着本环进行。

(2)交运算顺着环的方向搜索，当遇到的交点为出点时，则从该点在另一环上的对应点转入另一环，然后沿另一环的方向搜索；当遇到的交点为入点时，则继续顺着本环进行。

(3)差运算进行差运算时，首先要将差环的原方向倒转过来，然后按照与并运算相同的规则进行处理。

曲线曲线、曲面主要分为两种：1.可以用一个称为标准方程解析式表示的，如圆、椭圆、双曲线、圆柱、圆球等。

2.大部分曲线是由实验数据来给出的，只有一些数据点，称为“型值点”。

常见二次曲线的绘制1.绘制方法(1)曲线的方程取参数方程。

(2)将曲线分割成很多短线段，用这些短线段来逼近曲线。

/*正弦曲线*/#include <graphics.h>#include <math.h>#define PI 3.1415926main(){intdlt,x;float n0,s0,n,s,ds,dn;intgdriver=DETECT,gmode;initgraph(&gdriver,&gmode,"");setbkcolor(15);setcolor(4);dlt=3;ds = sin(2 * dlt * PI/640);dn= cos(2 * dlt * PI/640);s0 = 0;n0 = 1;line (0,240,640,240);moveto(0,240);x=0;while(x<640){s = s0 * dn + n0 * ds;n= n0 * dn- s0 * ds;x = x + dlt;lineto(x, 240 – 160* s);s0 = s;n0 = n;}getch();closegraph();}曲线参数表示参数表示:曲线上任一点的坐标均表示成给定参数的函数。

假定用t 表示参数，平面曲线上任一点P 可表示为：[])(),()(t y t x t P =空间曲线上任一三维点P 可表示为：[])(),(),()(t z t y t x t P =参数表示例子：直线]1,0[,)()(121∈-+=t t P P P t P圆]1,0[12,11)(222∈⎥⎦⎤⎢⎣⎡++-=t t t t t t P参数表示的优点：1）有更大的自由度来控制曲线、曲面的形状2）对曲线、曲面进行变换，可对其参数方程直接进行几何变换。

3）便于处理斜率为无穷大的情形，不会因此而中断计算。

4）便于用户把低维空间中曲线、曲面扩展到高维空间去。

5）规格化的参数变量t ∈[0, 1]，使其相应的几何分量是有界的，而不必用另外的参数去定义边界。

6）易于用矢量和矩阵表示几何分量，简化了计算。

位置矢量、切矢量● 曲线上任一点的位置矢量可表示为： P(t)=[x(t), y(t), z(t)]；● ● ● ● ●● 切向量(切矢量)• 选择弧长s 作为参数，则s Pds dP T s ∆∆==→∆0lim• 于是有)()(''t P t P ds dt dt dP ds dP =⋅=，即为单位矢量插值、拟合、逼近给定一组有序的数据点P i ，i=0, 1, …, n ，构造一条曲线顺序通过这些数据点，称为对这些数据点进行插值，所构造的曲线称为插值曲线。

线性插值：假设给定函数f(x)在两个不同点x1和x2的值，用一个直线：y=ax+b近似代替，称为线性插值。

抛物线插值:已知在三个互异点321,,x x x 的函数值为321,,y y y ，要求构造一个函数c bx ax x ++=2)(ϕ 使抛物线)(x ϕ在结点)3,2,1(=i x i 处与)(x f 在i x处的值相等拟合：构造一条曲线使之在某种意义下最接近给定的数据点(但未必通过这些点)，所构造的曲线为拟合曲线。

在计算数学中，逼近通常指用一些性质较好的函数近似表示一些性质不好的函数。

在计算机图形学中，逼近继承了这方面的含义，因此插值和拟合都可以视为逼近。

抛物样条曲线1、抛物线样条的由来最主要的由来是由于二次曲线是曲线中最简单的，用它来拟合一般型值点比较方便。

2、过三点定义一段抛物线设不在同一条直线上的三点：P1，P2，P3，过P1，P2，P3三点抛物线方程为： 每相邻的四个点可以决定中间一段抛物线样条曲线。

2、曲线的讨论 （1）端点条件)(x 12)(x ϕ=123(a)(b)图3.1.4 线性插值和抛物插值前面我们讲到，在全部点列P*i+(I=1,2,…,n)中，我们只能得到n-3段曲线。

但n 个点之间应当有n-1个曲线段，因为点列的首、尾两段P[1]P[2]和P[n-1]P[n]由于缺乏连续相邻的四点这样的条件而无法产生。