计算机图形学2425的知识

2.4字符的生成2.4.1点阵式字符

点阵式字符将字符形状表示为一个矩形点阵，由点阵中点的不同值表达字符的形状。

使用点阵式字符时，需将字库中的矩形点阵复制到缓冲器中指定的单元中去。在复制过程中，可以施加变换，以获得简单的变化。图2.11(b)~(d)列出了以字母P为原型的一些变化例子。图2.11点阵式字符及其变化

1矩阵中的每个元素都是一位二进制位。（1：字符颜色；0：背景颜色）算法如下：Writechar(x0,y0,value)Intx0,y0,value;{for(j=0;j<=ymax;j++)for(i=0;i<=xmax;i++)if(mask(i,j)<>0)set_pixel(x0+i;y0+j;value);elseset_pixel(x0+i;y0+j;background);}22.4字符的生成2.4.2矢量式字符

矢量式字符将字符表达为点坐标的序列，相邻两点表示一条矢量，字符的形状便由矢量序列刻画。图2.12示出用矢量式表示的字符“B”。“B”是由顶点序列{a,b,c,d,e,f,e,g,h,i,j,k,j,

a,l}的坐标表达。图2.12矢量式表示字符“B”32.4字符的生成2.4.3

方向编码式字符

方向编码式字符用有限的若干种方向编码来表达一个字符。图2.14(a)示出字母“B”的方向矢量构成。这样，“B”就表示为8方向编码{666}。方向编码式字符很容易被填入帧暂存寄存器中予以显示(图2.14(b))，方向编码所占的空间比较小，它也能接受一些特定的变换操作。图2.13字符的8方向编码

图2.14方向编码式字符的实例42.4字符的生成2.4.4轮廓字形技术

直接使用点阵式字符方法将耗费巨大的存储空间。压缩方法有多种，最简单的有黑白段压缩法。另一种方法是部件压缩法。三是轮廓字形法，这种方法压缩比大，且能保证字符质量，是当今国际上最流行的一种方法。

轮廓字形法采用直线、或者二次Bezier曲线、三次Bezier曲线的集合来描述一个字符的轮廓线。轮廓线构成一个或若干个封闭的平面区域。轮廓线定义和一些指示横宽、竖宽、基点、基线等的控制信息，就构成了字符的压缩数据。52.5图形求交

在计算机图形学中常常会遇到求交计算。求交运算是比较复杂的，为了减少计算量，在进行真正的求交计算之前，往往先用凸包等辅助结构进行粗略地比较，排除那些显然不相交的情形。容差求交问题可以分为两类：

求交点求交线

62.5图形求交

2.5.1求交点算法

求交点可以分两种情况，即求线与线的交点以及求线与面的交点。⒈直线段与直线段的交点假设两条直线的端点分别为P1、P2和Q1、Q2，则直线可以用向量形式表示为P(t)=A+Bt，0≤t≤1Q(s)=C+Ds，0≤s≤1其中，A=P1，B=P2P1，C=Q1，D=Q2Q1。构造方程

A+Bt=C+Ds(2.9)

对三维空间中的直线段来说，上述方程组实际上是一个二元一次方程组，由3个方程式组成。可以从其中两个解出s、t，再用第三个验证解的有效性。当所得的解(ti,si)是有效解时，可用两个方程之一计算交点坐标，例如P(ti)=A+Bti。

72.5图形求交2.5.1求交点算法（续）

根据向量的基本性质，可直接计算s与t。对方程(2.9)两边构造点积得(CD)·(A+Bt)=(CD)·(C+Ds)

由于CD同时垂直于C和D，等式右边为0。故有类似地有82.5图形求交2.5.1求交点算法（续）

2.直线段与平面的交点图2.15线段与平面求交

平面上的点表示为P(u,w)=A+uB+wC，直线段上的点表示为Q(t)=D+tE，二者的交点记为R。假设线段不平行于平面，则它们交于

R=P(u,w)=Q(t)，即A+uB+wC=D+tE等式两边点乘(BC)，得

(BC)·(A+uB+wC)=(BC)·(D+tE)由于BC既垂直于B，又垂直于C，故有(BC)·A=(BC)·(D+tE)92.5图形求交2.5.1求交点算法（续）

可解出类似求得102.5图形求交

2.5.2求交线算法

⒈平面与平面的交线

当两个一般的多边形相交时，可能有多段交线。可以把两个多边形分别记为A和B，用如下的算法求出他们的交线：把A的所有边与B相交，求出所有有效交点；把B的所有边与A相交，求出所有有效交点；把所有交点先按y，再按x的大小进行排序；把每对交点所形成线段的中点与A和B进行包含性检测，若该中点既在A中又在B中，则这对交点定义了一条交线段。

112.5图形求交2.5.3包含判定算法

判断点与线段的包含关系，也就是判断点与线的最短距离是否位于容差范围内。⒈点与直线段的包含判定假设点坐标为P(x,y,z)，直线段端点为P1(x1,y1,z1)、P2(x2,y2,z2)，则点P到线段P1P2的距离的平方为

d2=(xx1)2+(yy1)2+(zz1)2[(x2x1)(xx1)+(y2y1)(yy1)+(z2z1)(zz1)]2/[(x2x1)2+(y2y1)2+(z2z1)2]

当d2<2时，认为点在线段(或其延长线)上，这时还需进一步判断点是否落在直线段的有效区间内。对坐标分量进行比较，假设线段两端点的x分量不等(否则所有分量均相等，那么线段两端点重合，线段退化为一点)，那么当xx1与xx2异号时，点P在线段的有效区间内。122.5图形求交2.5.3包含判定算法（续）2.点与平面区域的包含判定设点坐标为P(x,y,z)，平面方程为ax+by+cz+d=0。则点到平面的距离为若d<，则认为点在平面上；否则，认为点不在平面上。对落在平面上的点还应进一步判别它是否落在有效区域内。下面以平面区域多边形为例，介绍有关算法。判断平面上的一个点是否包含在该平面的一个多边形内，有多种算法，这里仅介绍常用的3种，即叉积判断法、夹角之和检验法以及交点计数检验法。

132.5图形求交2.5.3包含判定算法（续）⑴叉积判断法假设判断点为P0，多边形顶点按顺序排列为P1，P2，…，Pn，如图2.16所示。令Vi=PiP0，其中，i=1,2,…,n，Vn+1=V1。那么，P0在多边形内的充要条件是叉积ViVi+1(i=1,2,…,n)的符号相同。叉积判断法仅适用于凸多边形。当多边形为凹多边形时，可采用后面介绍的两种方法。图2.16叉积判断法142.5图形求交2.5.3包含判定算法（续）⑵夹角之和检验法假设某平面上有点P0和多边形P1P2P3P4P5，如图2.17所示。将点P0分别与Pi相连，构成向量Vi=PiP0，假设PiP0Pi+1=i。如果，则点P0在多边形之外，如图2.17(a)所示。如果，则点P0在多边形之内，如图2.17(b)所示。图2.17夹角之和检验法

152.5图形求交⑶交点计数检验法当多边形是凹多边形，甚至还带