2.4 字符的生成 2.5 图形求交

上一篇 / 下一篇 2007-04-07 10:50:24 / 个人分类：还电脑一片纯洁

查看( 129 ) / 评论( 0 ) / 评分( 0 / 0 )

2.4 字符的生成

在计算机图形学中，字符可以用不同的方式表达和生成。常用的方法有点阵式、矢量式和编码式。电脑爱好者网x\a[9lXcT0U

2.4.1 点阵式字符

点阵式字符将字符表示为一个矩形点阵，由点阵中点的不同值表达字符的形状。常用的点阵大小有5? 7、7? 9、8? 8、16? 16等等。图2.4.1(a)所示的字母“P”的点阵式表示例子。在这种8? 8网格中的字形比较粗糙，但当点阵变大时，字型可以做得非常漂亮。电脑爱好者网!_^3wn/_

使用点阵式字符时，需将字库中的矩形点阵拷贝到buffer中指定的单元中去。在拷贝过程中，可以施加变换，以获得简单的变化。图2.4.1(b)~(d)列出了P字母原型的一些变化例子。相应的变换算法是：

(a) (b) (c) (d)电脑爱好者网+v4f Zp*MUm

2_4_1.gif (3270 bytes)

图2.4.1 点阵式字符及其变化电脑爱好者网%^%]d%n8e:]-q

图（b）变成粗体字。算法是：当字符原型中每个象素被写入帧缓存寄存器的指定位置x_i, y_i时，同时被写入x_i+1, y_i。电脑爱好者网])jb7G'}H1nK

图（c）旋转90? 。算法是：把字符原型中每个象素的x, y坐标彼此交换，并使y值改变符号后，再写入帧缓存寄存器的指定位置。

图（d）斜体字。算法是：从底到顶逐行拷贝字符，每隔n行，左移一单元。电脑爱好者网4iM!g(xb {

此外，还可以对点阵式字符作比例缩放等其他一些简单的变换。但是对点阵式字符作任意角度的旋转等变换，是比较困难的操作。电脑爱好者网$c1E:]z8?O1^(L

由于光栅扫描显示器的普遍使用，点阵式字符表示已经成为一种字符表示的主要形式。从字库中读出原字型，经过变换拷贝到buffer中去的操作，经常制成专门的硬件来完成。这就大大加快了字符生成的速度。

2.4.2 矢量式字符
矢量式字符将字符表达为一个点坐标的序列，相邻两点表示一条矢量，字符的形状便由矢量序列刻划。图2.4.2示出用矢量式表示的字符“B”。“B”是由顶点序列{a, b, c, d, e, f, e, g, h, I, j, k ,a, l}的坐标表达。
4Gr+vwO@'{0B0
调用矢量式字符的过程相当于输出一个polyline。由于矢量式字符具有和图形相一致的数据结构，因而可以接受任何对于图形的操作，如放大、旋转，甚至透视。而且，矢量式字符不仅可用于显示，也可用于绘图机输出。电脑爱好者网%m;L$xFK$y?S4ap
(vIdq-w,C+|/qrz0
图2.4.2 矢量式表示字符“B”
9x}z`;t,B\0
2.4.3 方向编码式字符
'i5F1?YR X:A1ykz0
方向编码式字符用有限的若干种方向编码来表达一个字符，常用的如8方向编码。图2.4.3示出8个方向的编码为0~7，其中编码为偶数和0的固定长度为1，编码为奇数的固定长度为。一个字符就可以表示为一连串方向码。图2.4.4(a)示出字母“B”的方向矢量构成。这样，“B”就表示为8方向编码：{000012344400012344440666666}。方向编码式字符很容易被填入帧缓存寄存器中予以显示（图2.4.4(b)），方向编码所占的空间比较小，它也能接受一些特定的变换操作，如按比例在x和y两个方向放大或缩小以及以45? 角为单位的旋转，但难以进行任意角度的旋转。
m0ji]s0
电脑爱好者网1p l*C.z+JsL:U7K6j
图2.4.3 图2.4.4
!Ndev"kx Q0
方向编码既可用于字符的显示，也可用于字符的绘图机输出
m}9th5kgj0
2.4.4 轮廓字型技术
#ZX B:@;h8f3N0
　　当对输出字符的要求较高时（如排版印刷），需要使用高质量的点阵字符。对于GB2312-80所规定的6763个基本汉字，假设每个汉字是72X72点阵，那么一个字库就需要72X72X6763/8=4.4兆字节存储空间；不但如此，在实际使用时，还需要多种字体（如基本体、宋体、仿宋体、黑体、楷体等），每种字体又需要多种字号。可见，直接使用点阵字符方法将耗费巨大的存储空间。因此把每种字体、字号的字符都存储一个对应的点阵，在一般情况是不可行的。
3u9?,F.l2O5Y O@/_0
　　解决这个问题一般采用压缩技术。对字型数据压缩后再存储，使用时，将压缩的数据还原为字符位图点阵。压缩方法有多种，最简单的有黑白段压缩法，这种方法简单，还原快，不失真，但压缩较差，使用起来也不方便，一般用于低级的文字处理系统中。另一种方法是部件压缩法。这种方法压缩比大，缺点是字型质量不能保证。三是轮廓字型法，这种方法压缩比大，且能保证字符质量，是当今国际上最流行的一种方法，基本上也被认为是符合工业标准化的方法。
yOn]XWiJ0
　　轮廓字型法采用直线、或者二/三次Bezier曲线的集合来描述一个字符的轮廓线。轮廓线构成一个或若干个封闭的平面区域。轮廓线定义加上一些指示横宽、竖宽、基点、基线等的控制信息，就构成了字符的压缩数据。这种控制信息用于保证字符变倍时引起的字符笔划原来的横宽/竖宽变大变小时，其宽度在任何点阵情况下永远一致。采用适当的区域填充算法，可以从字符的轮廓线定义产生的字符位图点阵，区域填充算法可以用硬件实现，也可以用软件实现。电脑爱好者网,q~6?(y_7h$g4p8@'~
由美国Apple和Microsoft公司联合开发的TrueType字型技术就是一种轮廓字型技术，已被用于为Windows中文版生成汉字字库。当前占领主要的电子印刷市场的我国北大方正和华光电子印刷系统，用的字型技术是汉字字型轮廓矢量法。这种方法能够准确地把字符的信息描述下来，保证了还原的字符质量，又对字型数据进行了大量的压缩。调用字符时，可以任意地放大、缩小或进行花样变化，基本上能满足电子印刷中字型质量的要求。轮廓字型技术有着广泛的应用。到目前为止在印刷行业中使用最多，随着Ms-Windows的大量使用，在CAD、图形学等领域也将变得越来越重要。电脑爱好者网n3n}5Ub`9T'H
2.5 图形求交
^{在计算机图形学中常常会遇到求交计算。例如，在进行扫描线区域填充时要求线段的交点，许多消隐算法需要进行直线和平面多边形的求交，等等。求交运算往往是比较复杂的，为了减小计算量，在进行真正的求交计算之前，往往先用凸包等辅助结构进行粗略的比较，排除那些显然不相交的情形。求交计算是}^{CAD系统的重要部分。它的准确性与效率直接影响CAD}^{系统的可靠性与实用性。}电脑爱好者网P Q^${L
^{在数学上两个浮点数可以严格相等，但计算机表示的浮点数有误差，所以当两个浮点数的差的绝对值充分小时（例如，小于某个正数}^{? ），就认为它们相等。相应地，求交运算中也要引进容差。当两个点的坐标值充分接近时，即其距离充分近时，就被认为是重合的点，直观地说，点可看作半径为? 的球，线可看作半径为? 的圆管，面可看作厚度为2? 的薄板。一般取? =10-6}^{或更小的数。}电脑爱好者网rV2M5@6ZdFw$Nd
^{求交问题可以分为求交点和求交线两类。本节的讨论不涉及自由曲线曲面，有关自由曲线曲面的求交问题将在}^{2.7和2.8节讨论。}电脑爱好者网'C(V'b&~5Gvh
2.5.1求交点算法
^{求交点可以分两种情况：求线与线的交点以及求线与面的交点。下面首先讨论线与线的交点的求法。。}电脑爱好者网\T&C B-`&Lh9k,w
^{1、直线段与直线段的交点}
zm0K2P G])dWL0
^{假设二条直线的端点分别为P1，P2，Q1，Q2，则它们可以用向量形式表示为：}电脑爱好者网5W)di(P2P(M
^{P(t)=A+Bt (0? t? 1)}电脑爱好者网/S*^!\^$h9n~DE"g
^{Q(s)=C+Ds (0? s? 1)}电脑爱好者网qz;`LA5v
^{其中，A=P1，B=P2-P1，C=Q1，D=Q2-Q1。}
4[K})Wexf/BaM0
^构造方程
0[ WK&|4lC,zV0
^{A+Bt=C+Ds (2-5-1)}电脑爱好者网r ~v6aXq sA@_
^{对三维空间中的直线段来说，上述方程实际上是一个二元一次方程组，由三个方程式组成。可以从其中两个解出s, t，再用第三个验证解的有效性：若第三个方程成立则说明找到了解，否则说明两条直线不相交。当所得的解（ti, si）是有效解时，可用二个线段方程之一计算交点坐标，例如P(ti)=A+Bti。}
:DmKmEo#O@ |W0
^{我们还可以根据向量的基本性质，直接计算s与t：对（2-5-2）两边构造点积得}电脑爱好者网UVV3q(V+b;euyf
^{(C? D)·（A+Bt）=（C? D）·（C+Ds）}
*Eh+U \8{0
^{由于C? D同时垂直于C和D，等式右边为零。故有}
(B,\*dn ].YK[$p0
6q@;E2wK2j+w/L/kd0
^类似地有
)yL,h*F1]0
T9Q x]2mI;D0
^{完整的算法还应判断无解与无穷多解（共线）的情形，以及考虑数值计算误差造成的影响。}电脑爱好者网 YC"`pDI_M
^{2、直线段与二次曲线的交点}电脑爱好者网;W8F.V%|m'siF|
^{不失一般性，考虑平面上一条直线与同平面的一条二次曲线的交。}电脑爱好者网rumS"REB
^{假设曲线方程为　　f(x, y)=0,}
P)pQ:K6uh z5~{0
^{直线段方程为　　(x, y)=(x1+tdx, y1+tdy),}电脑爱好者网b7}XA/dg
^{则在交点处有　f(x1+tdx, y1+tdy)=0}
)N-P6fs:c~+uNQ*U0f0
^{当曲线为二次曲线时，上述方程可写为}
Gy2uo&X/R5zp;u0
^at2+bt+c=0电脑爱好者网:AYm3yx
^{用二次方程求根公式即可解出t值。}
??e-eG0
^{3、圆锥曲线与圆锥曲线的交点}电脑爱好者网3k6Paj$Z|
^{圆锥曲线有代数法表示、几何法表示与参数法表示。在进行一对圆锥曲线的求交时，把其中一条圆锥曲线用代数/几何法表示为隐函数形式，另一条表示为参数形式（如二次NURBS曲线）。将参数形式代入隐函数形式可得关于参数的四次方程，可以使用四次方程的求根公式解出交点参数。得到交点后可再验证交点是否在有效的圆锥曲线段上。}电脑爱好者网P y4Pyi(L
^{下面讨论线与面的交点的求法。}
"A6[8I,d T3Vl'I0
^{1、直线段与平面的交点}电脑爱好者网&S7X ?5Eo8m GD'eDn
q8t%[{0i\Oghyw0
图2.5.1 线段与平面求交
^{考虑直线段与无界平面的求交问题，如图8.3.6所示。把平面上的点表示为P(u, w)=A+uB+wC，直线段上的点表示为Q(t)=D+tE，二者的交点记为R。假设线段不平行于平面，则它们交于R=P(u, w)=Q(t)，即}
^A+uB+wC=D+tE
f5c`&wm?5l0
^{等式两边点乘（B? C），得}电脑爱好者网kG'vXJ3F
^{（B? C）·（A+uB+wC）=（B? C）·（D+tE）}电脑爱好者网|xY;{Y
^{由于B? C既垂直于B，又垂直于C，故有}
Z*@5h3ELzb0
^{（B? C）·A=（B? C）·（D+tE）}电脑爱好者网4hxh/R?X
^可解出电脑爱好者网"CgT9p(F:o%?(L
电脑爱好者网 @)u{q2?U ?Z#D$s
电脑爱好者网}|2c+T-F R
类似求得电脑爱好者网#o-G._p(e$[
电脑爱好者网%XC y ^{;w)j.A+Q^
电脑爱好者网DzB'B3M$\-u
sz#PZY5I4?T} `(s0
5\+B:O"x!BL0
^{如果是直线与平面区域求交点，则要进一步判断点是否在平面上的有效区域中，其算法可参见2.5.3节。}
1nBA}SIr%Q\Py*\0
^{2、圆锥曲线与平面的交点}
u+i#Vh4Rz)NTV`"vL0
^{圆锥曲线与平面求交时，可以把圆锥曲线表示为参数形式，并把圆锥曲线的参数形式代入平面方程，即可得到参数的二次方程进行求解。}
^{圆锥曲线与二次曲面的交点}
^{圆锥曲线与二次曲面求交时，可把圆锥曲线的参数形式代入二次曲面的隐式方程，得到参数的四次方程，用求根公式求解。}
.H3Xjpj;D+|,t0

/x+Y"h,U-Y*ei{0

电脑爱好者网

关于作者

网络推荐

2.4 字符的生成 2.5 图形求交

2.4 字符的生成

2.4.1 点阵式字符

2.4.2 矢量式字符

2.5 图形求交

2.5.1求交点算法

相关阅读: