1、裁剪算法裁剪算法 反走样方法反走样方法 直线段裁剪直线段裁剪 直接求交算法直接求交算法 Cohen-Sutherland算法算法 中点分割算法中点分割算法 梁友栋梁友栋-Barskey算法算法 参数化裁剪算法参数化裁剪算法 多边形裁剪多边形裁剪 Sutherland_Hodgman算法算法 Weiler-Athenton算法算法 裁剪：裁剪：确定图形中哪些部分落在显示区之内，确定图形中哪些部分落在显示区之内，哪些落在显示区之外哪些落在显示区之外,以便只显示落在显示区以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。内的那部分图形。这个选择过程称为裁剪。图形裁剪算法，直接影响图形系统的效
2、率。图形裁剪算法，直接影响图形系统的效率。图形裁剪中最基本的问题。图形裁剪中最基本的问题。假设窗口的左下角坐标为假设窗口的左下角坐标为(x(xL L,y,yB B),),右上角坐标为右上角坐标为(x(xR R,y,yT T)，对于给定点，对于给定点P(x,y),P(x,y),则则P P点在窗口内的条件是要满点在窗口内的条件是要满足下列不等式：足下列不等式：否则，否则，P P点就在窗口外。点就在窗口外。问题：对于任何多边形窗口，问题：对于任何多边形窗口，如何判别？如何判别？(x(xL L,y,yB B)(x(xR R,y,yT T)xL=x=xR 并且并且yB=y=yT 直线段裁剪算法是复杂图形
3、裁剪的基础。复杂直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。也可以化为直线段的裁剪问题。直接求交算法直接求交算法Cohen-Sutherland算法算法中点分割算法中点分割算法梁友栋梁友栋barskey算法算法参数化裁剪算法参数化裁剪算法 裁剪线段与窗口的关系：裁剪线段与窗口的关系：(1)线段完全可见；线段完全可见；(2)显然不可见；显然不可见；(3)其它其它 提高裁剪效率：提高裁剪效率：快速判断情形快速判断情形(1)(2)，对于情形对于情形(3)，设法减，设法减少求交次数和每次求少求交次数
4、和每次求交时所需的计算量。交时所需的计算量。直线与窗口边都直线与窗口边都写成参数形式，写成参数形式，求参数值。求参数值。基本思想：基本思想：对于每条线段对于每条线段P P1 1P P2 2分为三种情况处理分为三种情况处理:（1 1）若）若P P1 1P P2 2完全在窗口内，则显示该线段完全在窗口内，则显示该线段P P1 1P P2 2。（2 2）若）若P P1 1P P2 2明显在窗口外，则丢弃该线段。明显在窗口外，则丢弃该线段。（3 3）若线段不满足（）若线段不满足（1 1）或（）或（2 2）的条件，则在交点）的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃处把线段分为两段。其
5、中一段完全在窗口外，可弃之。然后对另一段重复上述处理。之。然后对另一段重复上述处理。为快速判断，采用如下编码方法：为快速判断，采用如下编码方法：实现方法：实现方法：将窗口边线两边沿长，得到九个区域，每一个区将窗口边线两边沿长，得到九个区域，每一个区域都用一个四位二进制数标识，域都用一个四位二进制数标识，直线的端点都按其所处区域赋予相应的区域码，直线的端点都按其所处区域赋予相应的区域码，用来标识出端点相对于裁剪矩形边界的位置。用来标识出端点相对于裁剪矩形边界的位置。100100010101100000000100101000100110ABCD 将区域码的各位从左到右编号，则坐标区将区域码的各位
6、从左到右编号，则坐标区域与各位的关系为：域与各位的关系为：上上 下下 右右 左左 X X X XX X X X 任何位赋值为任何位赋值为1 1，代表端点落在相应的位，代表端点落在相应的位置上，否则该位为置上，否则该位为0 0。若端点在剪取矩形内，区域码为若端点在剪取矩形内，区域码为00000000。如果端点落在矩形的左下角，则区域码为如果端点落在矩形的左下角，则区域码为01010101。l 一旦给定所有的线段端点的区一旦给定所有的线段端点的区域码，就可以快速判断哪条直线域码，就可以快速判断哪条直线完全在剪取窗口内，哪条直线完完全在剪取窗口内，哪条直线完全在窗口外。所以得到一个规律：全在窗口外。
7、所以得到一个规律：若若P P1 1P P2 2完全在窗口内完全在窗口内code1=0,code1=0,且且code2=0,code2=0,则则“取取”若若P P1 1P P2 2明显在窗口外明显在窗口外code1&code20code1&code20，则，则“弃弃”在交点处把线段分为两段。其中一段完全在窗口在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。外，可弃之。然后对另一段重复上述处理。100100010101100000000100101000100110BCDA 如何判定应该与窗口的哪条边求交呢？如何判定应该与窗口的哪条边求交呢？编码中对应位为编码中对应
8、位为1的边。的边。计算线段计算线段P1(x1,y1)-P2(x2,y2)与窗口边界的交点与窗口边界的交点if if(LEFT&code!=0)(LEFT&code!=0)x=XL;x=XL;y=y1+(y2-y1)y=y1+(y2-y1)*(XL-x1)/(x2-x1);(XL-x1)/(x2-x1);else if else if(RIGHT&code!=0)(RIGHT&code!=0)x=XR;x=XR;y=y1+(y2-y1)y=y1+(y2-y1)*(XR-x1)/(x2-x1);(XR-x1)/(x2-x1);else if else if(BOTTOM&code!=0)(BOTT
9、OM&code!=0)y=YB;y=YB;x=x1+(x2-x1)x=x1+(x2-x1)*(YB-y1)/(y2-y1);(YB-y1)/(y2-y1);else if else if(TOP&code!=0)(TOP&code!=0)y=YT;y=YT;x=x1+(x2-x1)x=x1+(x2-x1)*(YT-y1)/(y2-y1);(YT-y1)/(y2-y1);优点：简单，易于实现。可以简单的描述为优点：简单，易于实现。可以简单的描述为将直线在窗口左边的部分删去，按左，右，将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部下，上的顺序依次进行，处理之后，剩余部
10、分就是可见的了。分就是可见的了。算法中求交点是很重要的，他决定了算法的算法中求交点是很重要的，他决定了算法的速度。另外，本算法对于其他形状的窗口未速度。另外，本算法对于其他形状的窗口未必同样有效。必同样有效。特点：用编码方法可快速判断线段的完全可特点：用编码方法可快速判断线段的完全可见和显然不可见。见和显然不可见。基本思想：基本思想：从从P P0 0点出发找离点出发找离P P0 0最近的可见点，从最近的可见点，从P P1 1点出发找离点出发找离P P1 1最近的可见点。这两个可见点的连线最近的可见点。这两个可见点的连线就是原线段的可见部分。就是原线段的可见部分。首先对线段端点进行编码，并把线段
11、与窗口的关系首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行与分为三种情况，对前两种情况，进行与Cohen-Cohen-SutherlandSutherland算法一样的处理；对于第三种情况，用算法一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。中点分割的方法求出线段与窗口的交点。A A、B B分别分别为距为距P P0 0 、P P1 1最近的可见点，最近的可见点，PmPm为为P P0 0P P1 1中点。中点。从从P0P0出发找距离出发找距离P0P0最近可见点采用中点分割方法最近可见点采用中点分割方法先求出先求出P P0 0P P1 1的中点的中
12、点P Pm m,若若P P0 0P Pm m不是显然不可见的，并且不是显然不可见的，并且P P0 0P P1 1在窗口中有可见部分，在窗口中有可见部分，则距则距P P0 0最近的可见点一定落在最近的可见点一定落在P P0 0P Pm m上，用上，用P P0 0P Pm m代替代替P P0 0P P1 1；否则取否则取P Pm mP P1 1代替代替P P0 0P P1 1。再对新的再对新的P P0 0P P1 1求中点求中点P Pm m。重复上述过程，直到。重复上述过程，直到P Pm mP P1 1长度小于长度小于给定的控制常数为止，此时给定的控制常数为止，此时P Pm m收敛于交点。收敛于交
13、点。从从P1P1出发找距离出发找距离P1P1最近可见点采用上面类似方法。最近可见点采用上面类似方法。对分辩率为对分辩率为2N*2N的显示器，上述二分过程的显示器，上述二分过程至多进行至多进行N次。次。主要过程只用到加法和除法运算，适合硬主要过程只用到加法和除法运算，适合硬件实现，件实现，它可以用左右移位来代替乘除法，它可以用左右移位来代替乘除法，这样就大大加快了速度这样就大大加快了速度。设要裁剪的线段是设要裁剪的线段是P P0 0P P1 1。P P0 0P P1 1和和窗口边界交于窗口边界交于A,B,C,DA,B,C,D四点。四点。算法的基本思想是从算法的基本思想是从A,BA,B和和P P0
14、 0三点三点中找出最靠近中找出最靠近P P1 1的点，图中要找的点的点，图中要找的点是是P P0 0。从。从C,DC,D和和P P1 1中找出最靠近中找出最靠近P P0 0的点，的点，图中要找的点是图中要找的点是C C点。点。P P0 0C C就是就是P P0 0P P1 1线段上的可见部分。线段上的可见部分。线段的线段的参数表示参数表示x=x0+txy=y0+ty 0=t tl,则可见线段区间则可见线段区间 tl,tu始边和终边的确定及交点计算：始边和终边的确定及交点计算：令令 Q QL L=-=-x Dx DL L=x=x0 0-x-xL L Q QR R=x Dx DR R=x=xR R
15、-x-x0 0 Q QB B=-=-y Dy DB B=y=y0 0-y-yB B Q QT T=y Dy DT T=y=yT T-y-y0 0交点为交点为 t ti i=D=Di i/Q Qi i i=L,R,B,Ti=L,R,B,TQ Qi i 0 t0 t0 ti i为与终边交点参数为与终边交点参数Q Qi i =0 D=0 Di i 0 0 0 时时,分析另一分析另一D,D,EFAB当当Q Qi i =0=0时时 若若D Di i 0 0 时时,线段不可见线段不可见（如图中如图中ABAB，有，有Q QR R=0=0，D DR R00 0 时时,分析另一分析另一D,D,（如图中的（如图中
16、的EFEF就是这种情况，它使就是这种情况，它使Q QL L=0=0，D DL L00和和Q QR R=0=0，D DR R00。这时求这时求EFEF和和y=yy=yT T及及y=yy=yB B的交点决定直的交点决定直线段上的可见部分。）线段上的可见部分。）EFAB 考虑凸多边形区域考虑凸多边形区域R和直线段和直线段P1P2P(t)=(P2-P1)*t+P1 设设A是区域是区域R的边界上的边界上一点，一点，N是区域边界在是区域边界在A点的内法线向量点的内法线向量ARNP1P2 则对于线段则对于线段P1P2上任一点上任一点P(t)N(P(t)-A)外侧外侧 N(P(t)-A)0-内侧内侧 N(P(
17、t)-A)=0-边界边界或其延长线上或其延长线上ARNP1P2 凸多边形的性质：点凸多边形的性质：点P(t)在凸多边形内的充在凸多边形内的充要条件是，对于凸多边形边界上任意一点要条件是，对于凸多边形边界上任意一点A和该点处内法向和该点处内法向N，都有，都有N(P(t)-A)0 K+1条边的多边形，可见线段参数区间的解条边的多边形，可见线段参数区间的解:Ni(p(t)-Ai)=0,i=0,k,0t 1.即：即：Ni(P1-Ai)+Ni(P2-P1)t=0 (1)式式 可得：可得：令令ti=Ni(P1-Ai)/Ni(P2-P1)12121211212112000PPNPPNPPNAPNtPPNPP
18、NAPNtPPNiiiiiiiiii Ni(P2-P1)=0-平行于对应边。平行于对应边。此时判断此时判断Ni(P1-Ai)若若Ni(P1-Ai)P1 P2在多边形外侧在多边形外侧-不可见，不可见，若若Ni(P1-Ai)0-P1 P2在多边形内侧在多边形内侧-继续其它继续其它边的判断边的判断 对于对于t t值的选择：首先值的选择：首先,要符合要符合0t10t1；其次；其次,对于凸对于凸窗口来说，每一个线段与其至多有两个交点，即有两窗口来说，每一个线段与其至多有两个交点，即有两个相应的个相应的t t值。所以把计算出的值。所以把计算出的t t值分成两组：一组为值分成两组：一组为下限组，分布在线段起
19、点一侧；一组为上限组，分布下限组，分布在线段起点一侧；一组为上限组，分布在线段终点一侧。找出下限组中的最大值及上限组中在线段终点一侧。找出下限组中的最大值及上限组中的最小值，就可确定线段了。的最小值，就可确定线段了。分组的依据是：分组的依据是：如果如果N Ni i(P(P2 2-P-P1 1)0,0,则计算出的值属于上限组则计算出的值属于上限组如果如果N Ni i(P(P2 2-P-P1 1)0,0,则计算出的值属于下限组则计算出的值属于下限组 因此，线段可见的交点参数：因此，线段可见的交点参数：tl=max0,maxti:Ni(P2-P1)0 tu=min1,minti:Ni(P2-P1)0
20、 若若 tl 0为特征，表示在该处沿为特征，表示在该处沿P1P2方向前进将接近或进入多边形内侧。方向前进将接近或进入多边形内侧。上限组以上限组以N Ni i(P(P2 2-P-P1 1)0)0为特为特征，表示在该处沿征，表示在该处沿P P1 1P P2 2方向前进将越方向前进将越来越远地离开多边来越远地离开多边形区域。形区域。l当凸多边形是矩形窗口且矩形的边与坐当凸多边形是矩形窗口且矩形的边与坐标轴平行时，该算法退化为标轴平行时，该算法退化为Liang-Barsky算法。算法。错觉：直线段裁剪的组合？错觉：直线段裁剪的组合？新的问题：新的问题：1）边界不再封闭，需要用窗口边）边界不再封闭，需要
21、用窗口边界的恰当部分来封闭它，如何确定其边界？界的恰当部分来封闭它，如何确定其边界？2）一个凹多边形可能被裁剪成几个小的多边形，）一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？如何确定这些小多边形的边界？分割处理策略：将多边形关于矩形窗口的裁剪分解分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。为多边形关于窗口四边所在直线的裁剪。流水线过程流水线过程(左上右下左上右下)：前边的结果是后边的输入前边的结果是后边的输入。亦称逐边亦称逐边裁剪算法裁剪算法 基本思想是一次用窗口的一条边裁剪多边形。基本思想是一次用窗口的一条边裁剪多边形。考虑窗口的一
22、条边以及延长线构成的裁剪线考虑窗口的一条边以及延长线构成的裁剪线,把把平面分成两个部分平面分成两个部分:可见一侧；不可见一侧可见一侧；不可见一侧 多边形的各条边的两端点多边形的各条边的两端点S S、P P。它们与裁剪线。它们与裁剪线的位置关系只有四种的位置关系只有四种 情况（情况（1 1）仅输出顶点）仅输出顶点P P；情况（情况（2 2）输出）输出0 0个顶点；个顶点；情况（情况（3 3）输出线段）输出线段SPSP与裁剪线的交点与裁剪线的交点I I；情况（情况（4 4）输出线段）输出线段SPSP与裁剪线的交点与裁剪线的交点I I和终点和终点P P 处理线段处理线段SP过程子框图过程子框图一条裁
23、剪线的处理流程一条裁剪线的处理流程上述算法仅用一条裁剪边对多边形进行裁上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。处理过程的输入。对于每一条裁剪边，算法框图同上，只是对于每一条裁剪边，算法框图同上，只是判断点在窗口哪一侧以及求线段判断点在窗口哪一侧以及求线段SPSP与裁剪边与裁剪边的交点算法应随之改变。的交点算法应随之改变。对凸多边形应用本算法可以得到正确的结果，对凸多边形应用本算法可以得到正确的结果，但是对凹多边形的裁剪将如图所示显示出一条但是对凹多边形的裁剪将如图所示显示出一条多余的直线。这种情况在裁剪后的
24、多边形有两多余的直线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个或者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。着第一个顶点。解决这个问题有多种方法，一是把凹多边形分解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多割成若干个凸多边形，然后分别处理各个凸多边形。二是修改本算法，沿着任何一个裁剪窗边形。二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。再有就口边检查顶点表，正确的连接顶点对。再有就是是WeilerWeiler-Athert
25、on-Atherton算法。算法。裁剪窗口为任意多边形（凸、凹、带内环）裁剪窗口为任意多边形（凸、凹、带内环）的情况：的情况：主多边形：被裁剪多边形，记为主多边形：被裁剪多边形，记为A 裁剪多边形：裁剪窗口，记为裁剪多边形：裁剪窗口，记为B 多边形顶点的排列顺序（使多边形区域位于有向多边形顶点的排列顺序（使多边形区域位于有向边的左侧边的左侧）外环：逆时针）外环：逆时针；内环：顺时针；内环：顺时针 主多边形和裁剪多边形把二维平面分成两部分。主多边形和裁剪多边形把二维平面分成两部分。内裁剪：内裁剪：AB 外裁剪：外裁剪：A-B裁剪结果区域的边界由裁剪结果区域的边界由A的部的部分边界和分边界和B的部
26、分边界两部分的部分边界两部分构成，并且在交点处边界发生构成，并且在交点处边界发生交替，即由交替，即由A的边界转至的边界转至B的的边界，或由边界，或由B的边界转至的边界转至A的的边界边界 如果主多边形与裁剪多边形有交点，则如果主多边形与裁剪多边形有交点，则交点成交点成对出现对出现，它们被分为如下两类：它们被分为如下两类：进点进点：主多边形边界由此进入裁剪多边形内：主多边形边界由此进入裁剪多边形内 如，如，I1,I3,I5,I7,I9,I11 出点出点：主多边形边界由：主多边形边界由此离开裁剪多边形区域此离开裁剪多边形区域.如，如，I0,I2,I4,I6,I8,I10 1）建顶点表；）建顶点表；2
27、）求交点；）求交点；3）裁剪）裁剪 1、建立主多边形和裁剪多边的顶点表、建立主多边形和裁剪多边的顶点表2、求主多边形和裁剪多边形的交点，并将这些交点按顺、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。在两多边表形顶点表中的相序插入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立双向指针同交点间建立双向指针。3、裁剪、裁剪:如果存在没有被跟踪过的交点，执行以下步骤：如果存在没有被跟踪过的交点，执行以下步骤：(1)建立空的裁剪结果多边形的顶建立空的裁剪结果多边形的顶点表点表 (2)选取任一没有被跟踪过的交点选取任一没有被跟踪过的交点为始点，将其输出到结果多边形为始
28、点，将其输出到结果多边形顶点表中顶点表中 (3)如果该交点为进点，跟踪主多如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪多边边形边边界；否则跟踪裁剪多边形边界形边界 (4)跟踪多边形边界，每遇到多边跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形形顶点，将其输出到结果多边形顶点表中，直至遇到新的交点顶点表中，直至遇到新的交点 (5)将该交点输出到结果多边形顶将该交点输出到结果多边形顶点表中，并通过连接该交点的双点表中，并通过连接该交点的双向指针改变跟踪方向（如果上一向指针改变跟踪方向（如果上一步跟踪的是主多边形边界，现在步跟踪的是主多边形边界，现在改为跟踪裁剪多边形边界；如果改为跟踪
29、裁剪多边形边界；如果上一步跟踪裁剪多边形边界，现上一步跟踪裁剪多边形边界，现在改为跟踪主多边形边界）在改为跟踪主多边形边界）(6)重复重复(4)、(5)直至回到起点直至回到起点取取I7为起点，所得裁剪结果多边形为起点，所得裁剪结果多边形I7I0q0I3I4I5I6I7。取。取I8为起点，所得为起点，所得裁剪结果多边形为裁剪结果多边形为I8I9I10I11I2q2I1I8。交点的奇异情况处理交点的奇异情况处理 1、与裁剪多边形的边重合的主多边形的边不参与求交点；、与裁剪多边形的边重合的主多边形的边不参与求交点；2、对于顶点落在裁剪多边形的边上的主多边形的边，如果、对于顶点落在裁剪多边形的边上的主
30、多边形的边，如果落在该裁剪边的内侧，将该顶点算作交点；而如果这落在该裁剪边的内侧，将该顶点算作交点；而如果这条边落在该裁剪边的外侧，将该顶点不看作交点条边落在该裁剪边的外侧，将该顶点不看作交点 用离散量表示连续量引起的失真现象用离散量表示连续量引起的失真现象称之称之为走样为走样(aliasing)。光栅图形的走样现象光栅图形的走样现象 阶梯状边界；阶梯状边界；图形细节失真；图形细节失真；狭小图形遗失：动画序列中时隐时现，产生狭小图形遗失：动画序列中时隐时现，产生闪烁。闪烁。不光滑不光滑(阶梯状）的图形边界阶梯状）的图形边界例子：例子：PaintBrush 图形细节失真图形细节失真 狭小图形的遗
31、失与动态图形的闪烁狭小图形的遗失与动态图形的闪烁 用于减少或消除走样现象的技术称为反用于减少或消除走样现象的技术称为反走样走样(antialiasing)反走样方法反走样方法 提高分辨率提高分辨率 简单区域取样简单区域取样 加权区域取样加权区域取样 半色调技术半色调技术 把显示器分辨率提高一倍，把显示器分辨率提高一倍，直线经过两倍的象素，锯齿也增加一倍，直线经过两倍的象素，锯齿也增加一倍，但同时每个阶梯的宽度也减小了一倍，但同时每个阶梯的宽度也减小了一倍，所以显示出的直线段看起来就平直光滑了所以显示出的直线段看起来就平直光滑了一些。一些。方法简单，但代价非常大。显示器的水平、竖方法简单，但代价
32、非常大。显示器的水平、竖直分辩率各提高一倍，则显示器的点距减少一直分辩率各提高一倍，则显示器的点距减少一倍，帧缓存容量则增加到原来的倍，帧缓存容量则增加到原来的4倍，而扫描倍，而扫描转换同样大小的图元却要花转换同样大小的图元却要花4倍时间。倍时间。而且它也只能减轻而不能消除锯齿问题而且它也只能减轻而不能消除锯齿问题另一种方法（软件方法）：另一种方法（软件方法）：用较高的分辨率的显示模式下计算，（对用较高的分辨率的显示模式下计算，（对各自像属下计算，再求（非）加权平均的颜色各自像属下计算，再求（非）加权平均的颜色值），在较低的分辨率模式下显示。值），在较低的分辨率模式下显示。只能减轻只能减轻而不
33、能消除锯齿问题。而不能消除锯齿问题。把每个像素分为四个子像素，扫描转换把每个像素分为四个子像素，扫描转换算法求得各子像素的灰度值，然后对四算法求得各子像素的灰度值，然后对四像素的灰度值简单平均，作为该像素的像素的灰度值简单平均，作为该像素的灰度值。灰度值。设 分 辨 率 为设 分 辨 率 为 m n,把 显 示 窗 口 分 为把 显 示 窗 口 分 为(2m+1)(2n+1)个子像素，对每个子像素个子像素，对每个子像素进行灰度值计算，然后根据权值表所规定进行灰度值计算，然后根据权值表所规定的权值，对位于像素中心及四周的九个子的权值，对位于像素中心及四周的九个子像素加权平均，作为显示像素的颜色。
34、像素加权平均，作为显示像素的颜色。设设m=3,n=4 方法由来方法由来两点假设两点假设1、象素是数学上抽象的点，它的面积为、象素是数学上抽象的点，它的面积为0，它的，它的亮度由覆盖该点的图形的亮度所决定；亮度由覆盖该点的图形的亮度所决定；2、直线段是数学上抽象直线段，它的宽度为、直线段是数学上抽象直线段，它的宽度为0。现实现实 像素的面积不为像素的面积不为0；直线段的宽度至少为直线段的宽度至少为1个像素；个像素；假设与现实的矛盾是导致混淆出现的原因之假设与现实的矛盾是导致混淆出现的原因之一一解决方法：改变直线段模型，由此产解决方法：改变直线段模型，由此产生算法生算法方法步骤：方法步骤：1、将直
35、线段看作具有一定宽度的狭长矩形；、将直线段看作具有一定宽度的狭长矩形；2、当直线段与某象素有交时、当直线段与某象素有交时,求出两者相交区域的面积；求出两者相交区域的面积；3、根据相交区域的面积，确定该象素的亮度值、根据相交区域的面积，确定该象素的亮度值 基本思想：基本思想：每个象素是一个具有一定面积的小区域，将直线段看作每个象素是一个具有一定面积的小区域，将直线段看作具有一定宽度的狭长矩形。当直线段与象素有交时，求具有一定宽度的狭长矩形。当直线段与象素有交时，求出两者相交区域的面积，然后根据相交区域面积的大小出两者相交区域的面积，然后根据相交区域面积的大小确定该象素的亮度值。确定该象素的亮度值
36、。有宽度的线条轮廓有宽度的线条轮廓 象素相交的五种情况及用于计算面积的量象素相交的五种情况及用于计算面积的量DD/mDm(1)(2)(3)(4)(5)面积计算面积计算情况情况（5)5)阴影面积为：阴影面积为：D D2 2/2m/2m；情况情况（4)4)阴影面积为：阴影面积为：D-m/2D-m/2；情况情况阴影面积为：阴影面积为：1-D1-D2 2/m/m 为了简化计算可以采用离散的方法为了简化计算可以采用离散的方法 求相交区域的近似面积的离散计算方法求相交区域的近似面积的离散计算方法 1、将屏幕象素分割成、将屏幕象素分割成n个更小的子象素；个更小的子象素；2、计算中心点落在直线段内的子象素的个
37、数，记为、计算中心点落在直线段内的子象素的个数，记为k，3、k/n为线段与象素相交区域面积的近似值为线段与象素相交区域面积的近似值 目的：简化计算目的：简化计算n=16,k=3近似面积近似面积=3/16 简单区域取样采用的是一个盒式滤波器，简单区域取样采用的是一个盒式滤波器，它是一个二维加权函数，以它是一个二维加权函数，以w表示。表示。w=1 若在当前像素所代表的正方形上若在当前像素所代表的正方形上 w=0 其它区域上其它区域上 直线条经过该像素时，该像素的灰度值直线条经过该像素时，该像素的灰度值可以通过在像素与直线条的相交区域上可以通过在像素与直线条的相交区域上对对w求积分获得。求积分获得。
38、此时，面积值此时，面积值=体积值体积值 采用圆锥形滤波器，圆锥的底圆中心在采用圆锥形滤波器，圆锥的底圆中心在当前像素，底圆半径为一个像素，锥高当前像素，底圆半径为一个像素，锥高为为1。当直线条经过该像素时，该像素的。当直线条经过该像素时，该像素的灰度值是在二者相交区域上对滤波器进灰度值是在二者相交区域上对滤波器进行积分的积分值。行积分的积分值。见见p213的图的图4.7.9 特点：特点：接近理想直线的像素将被分配更多的灰接近理想直线的像素将被分配更多的灰度值。度值。相邻的两个像素的滤波器相交，有利于相邻的两个像素的滤波器相交，有利于缩小直线条上相邻像素的灰度差。缩小直线条上相邻像素的灰度差。具
39、体算法见具体算法见p213 简单区域取样和加权区域取样技术的前简单区域取样和加权区域取样技术的前提是多级灰度，利用多级灰度来提高视提是多级灰度，利用多级灰度来提高视觉分辨率。但是，若只有两级灰度呢？觉分辨率。但是，若只有两级灰度呢？能否使用上述技术呢？能否使用上述技术呢？对于给定的分辨率，通过将几个像素组对于给定的分辨率，通过将几个像素组合成一个单元来获得多级灰度。合成一个单元来获得多级灰度。例：在一个显示器中将四个像素组成一例：在一个显示器中将四个像素组成一个单元，可产生个单元，可产生5种光强。种光强。可用如下矩阵来表示：可用如下矩阵来表示：它表示黑色像素填入它表示黑色像素填入2 2 2 2
40、个位置中的次序，每个位置中的次序，每一级灰度再添上一个黑色像素就得到下一级灰一级灰度再添上一个黑色像素就得到下一级灰度。度。注意：注意：1 1要尽量避免连成一条直线的花样。要尽量避免连成一条直线的花样。2 2花样是可以选择的。花样是可以选择的。单元也可以是长方形，如单元也可以是长方形，如4213236514 一般来说，对于两级灰度显示器可能构一般来说，对于两级灰度显示器可能构成的灰度数等于单元中像素个数加成的灰度数等于单元中像素个数加1 单元越大，灰度级别越高单元越大，灰度级别越高 它是以牺牲空间分辨率为代价的。它是以牺牲空间分辨率为代价的。例：灰度级别例：灰度级别=4,每个单元每个单元=2*2 若有若有m级灰度，级灰度，n n个像素组成一个单元，个像素组成一个单元，则灰度级别数为则灰度级别数为n n(m-1)+1
