计算机图形学义(裁减)

《计算机图形学义(裁减)》由会员分享，可在线阅读，更多相关《计算机图形学义(裁减)（15页珍藏版）》请在金锄头文库上搜索。

1、中点分割裁剪算法1、基本思想： 从 P0 点出发找出离 P0 最近的可见点，和从 P1 点出发找出离 P1 最近的可见点。这两 个可见点的连线就是原线段的可见部分。 （见上图） 与 Cohen-Sutherland 算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三 种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段 与窗口的交点。A、B 分别为距 P0 、 P1 最近的可见点，Pm 为 P0P1 中点。2、中点分割算法-求线段与窗口的交点 1） 、从 P0 出发找距离 P0 最近可见点采用中点分割方法 先求出 P0P1 的中点 Pm, 若 P0Pm 不是显

2、然不可见的，并且 P0P1 在窗口中有可见部分，则距 P0 最近的可见点 一定落在 P0Pm 上，所以用 P0Pm 代替 P0P1； 否则取 PmP1 代替 P0P1。 再对新的 P0P1 求中点 Pm。重复上述过程，直到 PmP1 长度小于给定的控制常数为止， 此时 Pm 收敛于交点。 2） 、从 P1 出发找距离 P1 最近可见点采用上面类似方法。3、 s 对分辩率为 2N*2N 的显示器，上述二分过程至多进行 N 次。 主要过程只用到加法和除法运算，适合硬件实现，它可以用左右移位来代替乘除法， 这样就大大加快了速度。P0P1PmAB对分辩率为 2N*2N 的显示器，上述二分过程至多进行

3、N 次。主要过程只用到加法和除法运算，适合硬件实现，它可以用左右移位来代替乘除法， 这样就大大加快了速度。梁友栋-Barsky 算法 设要裁剪的线段是 P0P1。 P0P1 和窗口边界交于 A,B,C,D 四点，见图。算法的基本思想是 从 A,B 和 P0 三点中找出最靠近的 P1 点，图中要找的点是 P0。从 C,D 和 P1 中找出最靠近 P0 的点。图中要找的点是 C 点。那么 P0C 就是 P0P1 线段上的可见部分。线段的参数表示x=x0+tx y=y0+ty 0 tl,则可见线段区间tl , tut0t1t2t301始边和终边的确定及交点计算： 令 QL= - x DL= x0-x

4、L QR= x DR= xR-x0QB= - y DB= y0-yB QT= y DT= yT-y0 交点为 ti= Di / Qi i=L,R,B,T Qi 0 ti 为与终边交点参数 Qi =0 Di 0 时, 分析另一 D, 当 Qi =0 时 若 Di 0 时, 分析另一 D, （如图中的 EF 就是这种情况，它使 QL=0，DL0 和 QR=0，DR0。这时由于 EF 和 x=xL 及 x=xR 平行，故不必去求出 EF 和 x=xL 及 x=xR 的交点，而让 EF 和 y=yT 及 y=yB 的交点决定直线段上的可见部分。 ） 为始边。为终边，若为终边。为始边，若为始边。为终边，

5、若为终边。为始边，若TBTBRLRLyyyyyyyyyyxxxxxxxxxx0000EFAB参数化算法(Cyrus-Beck)ARNP1考虑凸多边形区域 R 和直线段 P1P2 P(t)=(P2-P1)*t+P1 设 A 是区域 R 的边界上 一点，N 是区域边界在 A 点的内法线向量 则对于线段 P1P2 上任一点 P(t) N (P(t)-A)外侧 N (P(t)-A)0-内侧 N (P(t)-A)=0-边界 或其延长线上 凸多边形的性质：点 P(t)在凸多边形内的充要条件是，对于凸多边形边界上任意一点 A 和该点处内法向 N，都有 N(P(t)-A)0 k 条边的多边形，可见线段参数区间

6、的解: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) Ni (P2-P1) =0- 平行于对应边。 此时判断 Ni (P1-Ai) 若 Ni (P1-Ai) P1 P2 在多边形外侧-不可见， 若 Ni (P1-Ai) 0-P1 P2 在多边形内侧-继续其它边的判断 对于 t 值的选择：首先，要符合 0t1；其次，对于凸窗口来说，每一个线段与 其至多有两个交点，即有两个相应的 t 值。所以我们可以把计算出的 t 值分成两组： 一组为下限组，是分布在线段起点

7、一侧的；一组为上限组，是分布在线段终点一侧 的。这样，只要找出下限组中的最大值及上限组中的最小值，就可确定线段了。 分组的依据是： 如果 Ni (P2-P1) 0，则计算出的值属于上限组 如果 Ni (P2-P1) 0，则计算出的值属于下限组 因此，线段可见的交点参数： tl=max0,maxti: Ni (P2-P1) 0 tu=min1,minti: Ni (P2-P1)0 若 tl = tu, tl ， tu是可见线段的交点参数区间，否则，线段不可见。 当凸多边形是矩形窗口且矩形的边与坐标轴平行时，该算法退化为 Liang-Barsky 算法。 Cyrus-Beck 扩充到凸多边形 思考

8、： 凹多边形窗口的线段裁剪 圆和曲线窗口的线段裁剪多边形裁剪 错觉错觉：直线段裁剪的组合？ 新的问题：新的问题：1）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其 边界？ 1212121 12121 12000PPNPPNPPNAPNtPPNPPNAPNtPPNiiiii iiii iSutherland-Hodgman 算法分割处理策略分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线 的裁剪。 流水线过程流水线过程(左上右下左上右下)：前边的结果是后边的输入。亦称逐边裁剪算法亦称逐边裁剪算法基本思想是一次用窗口的一条边裁剪多边形。 考虑窗口的一条边以及延长

9、线构成的裁剪线该线把平面分成两个部分:可见一侧； 不可见一侧 多边形的各条边的两端点 S、P。它们与裁剪线的位置关系只有四种情况（1）仅输出顶点 P； 情况（2）输出 0 个顶点； 情况（3）输出线段 SP 与裁剪线的交点 I； 情况（4）输出线段 SP 与裁剪线的交点 I 和终点 P上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下 一条裁剪边处理过程的输入。 对于每一条裁剪边，算法框图同上，只是判断点在窗口哪一侧以及求线段 SP 与裁 剪边的交点算法应随之改变。可 见 一 侧可 见 一 侧可 见 一 侧可 见 一 侧SpSSSppp(1)(2)(3)(4)对凸多边形应用本算法

10、可以得到正确的结果，但是对凹多边形的裁剪将如图所示显 示出一条多余的直线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候 出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。 解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分别处理 各个凸多边形。二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连 接顶点对。再有就是 Weiler-Atherton 算法。反走样 用离散量表示连续量引起的失真现象称之为走样走样(aliasing) 。光栅图形的走样现象光栅图形的走样现象阶梯状边界； 图形细节失真； 狭小图形遗失：动画序列中时隐时现，产生闪烁。 走样

11、现象举例 不光滑不光滑(阶梯状）的图形边界阶梯状）的图形边界例子：PaintBrush 图形细节失真图形细节失真狭小图形的遗失与动态图形的闪烁狭小图形的遗失与动态图形的闪烁用于减少或消除走样现象的技术称为反走样反走样(antialiasing) 提高分辨率 简单区域取样 加权区域取样 把显示器分辨率提高一倍， 直线经过两倍的象素，锯齿也增加一倍， 但同时每个阶梯的宽度也减小了一倍， 所以显示出的直线段看起来就平直光滑了一些。方法简单，但代价非常大。显示器的水平、竖直分辩率各提高一倍，则显示器的点 距减少一倍，帧缓存容量则增加到原来的 4 倍，而扫描转换同样大小的图元却要花 4 倍时间。 而且它

12、也只能减轻而不能消除锯齿问题 另一种方法（软件方法）： 用较高的分辨率的显示模式下计算， （对各自像属下计算，再求（非）加权平均的颜色值） ， 在较低的分辨率模式下显示。只能减轻而不能消除锯齿问题。 把每个像素分为四个子像素，扫描转换算法求得各子像素的灰度值，然后对四像素的灰度 值简单平均，作为该像素的灰度值。设分辨率为 mn,把显示窗口分为(2m+1)(2n+1)个子像素，对每个子像素进行灰度 值计算，然后根据权值表所规定的权值，对位于像素中心及四周的九个子像素加权 平均，作为显示像素的颜色。 设 m=4,n=3简单区域取样 方法由来方法由来 两点假设两点假设 1、象素是数学上抽象的点，它的

13、面积为、象素是数学上抽象的点，它的面积为 0，它的亮度由覆盖该点的图形的亮度所决定；，它的亮度由覆盖该点的图形的亮度所决定； 2、直线段是数学上抽象直线段，它的宽度为、直线段是数学上抽象直线段，它的宽度为 0。 现实现实 像素的面积不为像素的面积不为 0； 直线段的宽度至少为直线段的宽度至少为 1 个像素；个像素； 假设与现实的矛盾是导致混淆出现的原因之一假设与现实的矛盾是导致混淆出现的原因之一解决方法：改变直线段模型，由此产生算法解决方法：改变直线段模型，由此产生算法 方法步骤：方法步骤： 1、将直线段看作具有一定宽度的狭长矩形；、将直线段看作具有一定宽度的狭长矩形； 2、当直线段与某象素有

14、交时，求出两者相交区域的面积；、当直线段与某象素有交时，求出两者相交区域的面积； 3、根据相交区域的面积，确定该象素的亮度值、根据相交区域的面积，确定该象素的亮度值 基本思想： 每个象素是一个具有一定面积的小区域，将直线段看作具有一定宽度的狭 长矩形。当直线段与象素有交时，求出两者相交区域的面积，然后根据相 交区域面积的大小确定该象素的亮度值。0112233445567891011DD/mD m(1)(2)(3)(4)(5)有宽度的线条轮廓 象素相交的五种情况及用于计算面积的量 面积计算 情况（5)阴影面积为：D2/2m； 情况（4)阴影面积为：D - m/2； 情况阴影面积为：1 - D2/

15、m 为了简化计算可以采用离散的方法 求相交区域的近似面积的离散计算方法求相交区域的近似面积的离散计算方法 1、将屏幕象素分割成、将屏幕象素分割成 n 个更小的子象素；个更小的子象素； 2、计算中心点落在直线段内的子象素的个数，记为、计算中心点落在直线段内的子象素的个数，记为 k， 3、k/n 为线段与象素相交区域面积的近似值为线段与象素相交区域面积的近似值 简单区域取样采用的是一个盒式滤波器，它是一个二维加权函数，以 w 表示。 w =1 若在当前像素所代表的正方形上 w =0 其它区域上 直线条经过该像素时，该像素的灰度值可以通过在像素与直线条的相交区域上对 w 求积分获得。 此时，面积值=体积值 缺点： 象素的亮度与相交区域的面积成正比，而与相交区域落在象素内的位置无 关，这仍然会导致锯齿效应。 直线条上沿理想直线方向的相邻两个象素有时会有较大的灰度差。 采用圆锥形滤波器，圆锥的底圆中心在当前像素，底圆半径为一个像素，锥高为 1。当直线条经过该像素时，该像素的灰度值是在二者相交区域上对滤波器进行积 分的积分值。 见 p213 的图 4.7.9 特点： 接近理想直线的像素将被分配更多的灰度值。 相邻的两个像