2D Viewing Lectured by Hua Yan

Contents 2D Viewing Pipeline 2D Clipping Clipping Window Viewport Point clipping Line clipping Area clipping Text clipping

6.1 2D Viewing Pipeline Def. 常规图形系统中，世界坐标系中指定的用于显示的坐标区域-> 裁剪窗口(clipping window)或窗口(window) Def. 显示设备上用于窗口映射的坐标区域-> 视区、视口(viewport)。 Def. 通常，世界坐标系中部分场景映射到设备坐标系的过程->观察(视图、视像)变换。 通常图形软件都允许指定已定义图形中要显示的部分以及在显示器显示的位置; 任何用做世界坐标参考系的笛卡儿坐标系都可以用来定义图形 二维图形的视图通过指定整个图形区域中的一个子区域来获得 可以仅显示一个区域，也可以同时显示几个区域，或者显示一个场景中的动态扫描序列

x y w1 w2 w3 w4 窗口 世界坐标系 设备坐标系 x y v1 v2 v3 v4 视口 通过改变视口的位置，我们可在输出设备上的不同显示区域观察物体。也可通过改变视口的大小来改变显示物体的尺寸和位置。如果将不同尺寸的窗口连续映射到尺寸不变的视口中，则可以得到缩放的效果。当窗口变小时，就可放大物体的显示，从而观察到当窗口较大时未能观察到的细节。通过将一个固定大小的窗口移动过一个场景中不同的对象或同一对象的不同位置，产生扫视的效果

yw xw xv yv x y ??任意方向的矩形窗口 y0 x0 某些图形软件包仅仅提供了使用标准的矩形窗口和视口的操作。更加通用的方法是允许矩形窗口有任意方向。

坐标系 世界坐标系(World Coordinates) 图形定义时所采用的坐标系，坐标的大小和尺寸由用户确定。 设备坐标系(Device Coordinates) 与一个图形设备相关的坐标系叫设备坐标系。如显示器或打印机有它们自己的坐标系。 规范化坐标系(Normalized Coordinates) 它是独立于具体物理设备的一种坐标系，其显示空间在X和Y方向上都是从0到1

1 绘图仪 其他输出设备 建模坐标 世界坐标 规范化坐标 设备坐标

2D viewing-transformation pipeline 2D 观察流水线（P.247） 建模坐标-世界坐标变换 世界坐标-观察坐标变换 观察坐标-规范化坐标观察变换 规范化坐标到设备坐标变换 MC WC VC NC DC W-V Some graphics packages that provide window and viewport operations allows only standard rectangles, but a more general approach is to allow the rectangular window to have any orientation. In this case we carry out the viewing transformation in several steps. 2D Viewing Pipeline 2D viewing-transformation pipeline Modeling coordinates --> World coordinates --> Viewing coordinates --> Normalized viewing coordinates --> Display coordinates

窗口->视口变换 x y w1 w2 w3 w4 窗口 (xw,yw) x y v1 v2 v3 v4 视口 (xv,yv) Some graphics packages that provide window and viewport operations allows only standard rectangles, but a more general approach is to allow the rectangular window to have any orientation. In this case we carry out the viewing transformation in several steps. 2D Viewing Pipeline 2D viewing-transformation pipeline Modeling coordinates --> World coordinates --> Viewing coordinates --> Normalized viewing coordinates --> Display coordinates

窗口->视口变换 保持视口与窗口中的对象具有同样的相对位置，必须满足 (Xw-W1) / (W2-W1) = (Xv-V1) / (V2-V1) (Yw-W3) / (W4-W3) = (Yv-V3) / (V4-V3)

Xv = SxXw+tx Yv = SyYw+ty 缩放系数 Sx = (V2-V1) / (W2-W1) Sy = (V4-V3) / (W4-W3) 平移参数 tx = (W2*V1-W1*V2) / (W2-W1) ty = (W4*V3-W3*V4) / (W4-W3)

Example 已知w1=10,w2=20,w3=40,w4=80, v1=80,v2=110,v3=10,v4=130, 窗口中一点P(15，60)，求视区中的映射点P‘? 解：(15-10)/(20-10) = (xv-80)/(110-80) (60-40)/(80-40) = (yv-10)/(130-10) xv = 95, yv=70

OpenGL 2D Viewing Functions (P.253-257) Demo (P.258-259)

6.2 2D Clipping 识别图形在指定区域内或区域外的过程->裁剪 裁剪定义Clipping 应用包括： 从定义的场景中取出用于观察的部分； 在三维图形中标识出可见面； 防止线段或对象的边界混淆； 用实体造型来创建对象； 显示多窗口的环境； 允许进行拷贝、移动或删除等绘图操作 6.2 2D Clipping Operations Definition of Clipping any procedure that identifies those portions of a picture that are either inside or outside of a specified region of space is referred to as a clipping. Clipping time window clipping viewport clipping

6.2 2D Clipping 裁剪窗口：用来裁剪对象的区域。 裁剪时机 针对窗口裁剪：只有窗口内的部分映射到设备坐标系中，不用将多余图元变换到设备空间中 针对视口裁剪：映射后，用视口边界裁剪，可通过合并观察和几何变换矩阵来减少计算量 6.2 2D Clipping Operations Definition of Clipping any procedure that identifies those portions of a picture that are either inside or outside of a specified region of space is referred to as a clipping. Clipping time window clipping viewport clipping

6.2 2D Clipping 裁剪类型 点裁剪 直线裁剪 多边形区域裁剪 曲线裁剪（P.279） 文字裁剪

6.2.1 点裁剪 点(x,y)如果满足下列不等式则保留： w4 w1 <= x <= w2 w3 <= y <= w4 w4 w3 w1 w2 A point(x,y) is saved, if the following inequalities are satisfied: w1 <= x <= w2 w3 <= y <= w4 (x,y)

6.2.2 直线裁剪 线段与窗口的位置关系： 整个线段全在窗口内 整个线段全在窗口外 线段部分在窗口外，部分在窗口内

6.2.2 直线裁剪 Cohen-Sutherland直线裁剪算法 Liang梁友栋-Barsky直线裁剪算法 Nicholl-Lee-Nicholl直线裁剪算法 非矩形裁剪窗口(P.270自学) Cohen-Sutherland Line Clipping Liang-Barsky Line Clipping Nicholl-Lee-Nicholl Line Clipping Nonrectangular Clip Windows

6.2.2.1 CS直线裁剪算法 IDEA 直线由端点标识； 测试直线端点和窗口边界的关系以确定是否需要计算交点 This is one of the oldest and most popular line-clipping procedures. Generally, the method speeds up the processing of line segments by performing initial tests that reduced the number of intersections that must be calculated. Lines are defined by their endpoints, so it should be possible just to examine these, and not every pixel on the line Most applications of clipping use a window that is either very large, I.e. nearly the whole scene fits inside, or very small, I.e. most of the scene lies inside the window Hence, most lines may be either trivially accepted or rejected

CS 编码方案 扩展窗口的边界将整个2D平面划分为9个区域 w4 每个区域赋予一个4位编码, 称为区域码 w3 w1 w2 0000 0110 0100 0101 0010 0001 1001 1000 1010 上 下 右 左 w1 w2 w3 w4 CS 编码方案 扩展窗口的边界将整个2D平面划分为9个区域 每个区域赋予一个4位编码, 称为区域码 CS coding The window edges are assumed to be extended so that the whole picture is divided into 9 regions Each region is assigned a four-bit code, called region code

编码规则 b0 = 1 iff x < w1 w4 b1 = 1 iff x > w2 b2 = 1 iff y < w3 0000 0110 0100 0101 0010 0001 1001 1000 1010 上 下 右 左 w1 w2 w3 w4 编码规则 b0 = 1 iff x < w1 b1 = 1 iff x > w2 b2 = 1 iff y < w3 b3 = 1 iff y > w4

c1 & c2 不为零，同在某一边界外，删除该直线 c1 & c2 为零，需要进一步求解交点 算法描述 计算直线端点编码, c1 和 c2; 判断 c1 和 c2 均为0000，保留直线 c1 & c2 不为零，同在某一边界外，删除该直线 c1 & c2 为零，需要进一步求解交点 以L,R,B,T 为序，找出端点区域码中第一位为1的位，将x=w1/w2或y=w3/w4带入直线方程，计算直线与窗口边界的交点，将交点和另一端点重复上述过程，直至线段保留或删除 The region code for each end of the line is computed, giving codes c1 and c2. One of the following cases will occur: Both c1 and c2 are 0000. This means that both endpoints lie inside the window, so the line may be trivially accepted If c1 and c2 have one or more bits in common, then the line must be wholly outside the window. Hence if (c1 AND c2) is not equal to zero, the line may be trivially rejected If (c1 AND c2) is equal to zero, further processing is necessary. Lines that cannot be identified as completely inside or outside a clip window are checked for intersection with the window boundary in the order left, right, bottom, top. The remaining part of the line is checked against the other boundaries until the line is totally discarded or a section is found inside the window

程序流程图

p1 p2 p3 p4 1 3 2 程序实现(P.264)

CS线段裁剪算法 举例 P3 P4 1 0000 0110 0100 0101 0010 0001 1001 1000 1010

CS线段裁剪算法 举例 1 3 2 P1 P2 0000 0110 0100 0101 0010 0001 1001 1000 1010

CS线段裁剪算法小结 优点：简单，易于实现。 算法中求交点的次数决定了算法的速度。

6.2.2.2 Liang-Barsky 线段裁剪算法 思想：基于直线段参数方程分析的快速直线裁剪算法 参数方程 直线两端点 P1(x1, y1), P2 (x2, y2) x = x1 + (x2 - x1)u y = y1 + (y2 - y1)u, 0≤u≤1 该算法与Cohen-Sutherland 一样，用于标准矩形窗口的裁剪(边界与坐标轴平行)，但它是更快的直线裁剪算法，它基于线段的参数化方程的分析，

已知直线端点 ： 起点P1(x1, y1)，终点P2(x2, y2) 参数方程： x = x1 + (x2 - x1)u y = y1 + (y2 - y1)u P1 P2 u<0 0≤u≤1 u>1

LB算法推导 如果直线在窗口内, 则 w1 ≤ x1 + dx * u ≤ w2 w3 ≤ y1 + dy * u ≤ w4 统一表示为：Pk * u ≤ Qk k = 1, 2, 3, 4 P1 = - dx, Q1 = x1-w1 P2 = dx, Q2 = w2-x1 P3 = - dy, Q3 = y1-w3 P4 = dy, Q4 = w4-y1

w1 w2 w3 w4 ub ul ut ur 1 dx dy

对 Pk<>0的情形, 用Qk/Pk计算交点所对应的u值 算法描述 计算 Pk, Qk, k=1~4 Pk = 0，表示直线平行于窗口某边界 Qk < 0，（任一小于零）直线完全在窗口外，被裁剪 Qk >= 0，直线在窗口内，平行边界内 对 Pk<>0的情形, 用Qk/Pk计算交点所对应的u值 Algorithm Description Computing Pk, Qk, k=1~4 Judge if there any Pk= 0, then the line is parallel to one of the clipping boundaries. If, for that value of k, we also find Qk < 0, then the line is completely outside the boudary, otherwise the line is inside the boudary for case Pk<>0, calculate the value of u that corresponds to the intersection point as Qk/Pk For each line, calculate two parameters u1&u2 that define the section inside the clipping window. u1=Max{0, Qk/Pk}, Pk < 0 u2=Min{1, Qk/Pk}, Pk > 0 if u1 > u2, then line is outside the clip window, otherwise calculate the intersection point

对每条线计算参数u1&u2 u1=Max({Qk/Pk|Pk < 0} U {0}) u2=Min({Qk/Pk|Pk > 0} U {1}) 如果u1 > u2, 则直线在窗口外，否则计算交点坐标 x(u) = x1+dx*u y(u) = y1+dy*u

LB线段裁剪算法 例1 已知线段的两个端点P1(3, 4)，P2(8, 2) 窗口边界x=1, x=4, y=1, y=3

线段的参数方程 x = 3 + 5u y = 4 - 2u P1 = -5, Q1 = 2, R1 = -2/5 u1 = max(0, -2/5, 1/2) = 1/2 u2 = min(1, 1/5, 3/2) = 1/5 u1 > u2 所以线段全部被裁剪

LB线段裁剪算法 例2 线段的两个端点（-2，-1）和（1，1.5） 窗口边界x1 = -1, x2 = 1, y1 = -1, y2 = 1

△x = 3, △y = 2.5 p1 = -3 q1 = -1 r1 = 1/3 p2 = 3 q2 = 3 r2 = 1 p3 = -2.5 q3 = 0 r3 = 0 p4 = 2.5 q4 = 2 r1 = 4/5 对于p < 0，u1 = max{0，1/3，0} = 1/3 对于p > 0，u2 = min{1，1， 4/5} = 4/5 则u1<u2，则可见线段的端点坐标： x = x1 + u1 △x = -1, y = y1 + u1 △y = -1/6 即(-1, -1/6) x=x1+u2 △x=2/5, y=y1+u2 △y =1 即(2/5, 1)

Liang-Barsky和Cohen-Sutherland算法很容易扩展为三维裁剪算法 程序实现(P.267~268) LB vs. CS LB 效率高于 CS, 因为减少了交点计算次数。 参数u1 和 u2 的更新需要四次除法, 交点坐标计算至多4次乘法。 Liang-Barsky和Cohen-Sutherland算法很容易扩展为三维裁剪算法 LB is more efficient than the CS, since intersection calculations are reduced. Updates of parameters u1 and u2 require four divisions, intersection calculation require four multiplies at most.

6.2.2.3 NLN直线裁剪算法 IDEA 通过在裁剪窗口周围创立多个区域，并在求交运算之前进行更多的区域测试，从而避免对直线段进行多次剪裁。 适用范围 仅仅适用于2D剪裁 IDEA By creating more regions around the clip window, the NLN avoids multiple clipping of an individual line segment; Only be applied to 2D clipping

算法步骤 从P1点向窗口的四个角点发出射线，这四条射线和窗口的四条边界直线一起将二维平面划分为更多的小区域 。

线段端点P1的三种位置 Using symmetry, a given endpoint p1=(x1,y1) falls in one of three distinct regions.

Case 1 情况 1：P1位于窗口内部，则设定四个裁剪区域 P2位于窗口内部，P1P2保留；

Case 2 Part of line maybe visible if the ray from P1 through P2 enters region LB,LR or LT 情况2： P1位于窗口左侧： P2 位于L区域，计算和左边界交点P并保留P1P； P2位于区域LT，计算直线与窗口左边界、上边界的交点并保留该线段部分。 同理处理P2位于区域LR、LB。 P2不在四个裁剪区域，舍弃整个线段。

Case 3A The ray from P1 through (XL,YT) intersects bottom edge before the right edge P2 位于窗口内部 L(T)区域，计算和左边(上)界交点P并保留PP2 P2位于LB，计算左、下边界交点并保留 同理处理TR、LR P2不在四个裁剪区域，整个舍弃

Case 3B The ray from P1 through (XL,YT) intersects bottom edge after the right edge P2 位于窗口内部L(T)区域，计算和左边(上)界交点P并保留PP2 P2位于LB，计算左、下边界交点并保留 同理处理TB、TR P2不在四个裁剪区域，整个舍弃

比较直线段P1P2的斜率和剪裁区域边界的斜率. yt-y1 y2-y1 yt-y1 xr-x1 x2-x1 xl-x1 交点计算 Where is P2 located? compare the slope of the line(P1P2) to the slopes of the boundaries of the clip regions. Intersection Calculating

6.2.3 多边形区域裁剪 直接采用直线段裁剪算法的问题 裁剪前 裁剪后

裁剪算法 Sutherland-Hodgman 算法 Weiler-Atherton 算法

6.2.3.1 Sutherland-Hodgman 算法 IDEA 以多边形顶点为初始集合, 首先用窗口左边界剪裁多边形，产生新的顶点序列。新的顶点集依次传给右边界、下边界和上边界进行处理。 SH算法最终输出定义剪裁后的多边形边界的顶点序列。 P.272 图6.23 IDEA The output of SH method is a sequence of vertices that defines the clipped polygon boudaries. Beginning with the initial set of polygon vertices, we could first clip the polygon against the left boundary to produce a new sequence of vertices. The new set of vertices could then be sucessively passed to a right, bottom and top boundary.

A D G H 1 用上边界裁剪 3 4 5 6 7 8 输入：A134D5678GH 输出：K34D56789IHJ 9 I J K 输入：ABCDEFGH A B C D E F G H 输出：A12DEFGH 1 2 用左边界裁剪

S 沿多边形依次处理顶点有四种情况 剪裁情况一 P: second output S out, P in;由外至内 输出 i和p i: first output 沿多边形依次处理顶点有四种情况 剪裁情况一 S out, P in;由外至内 输出 i和p

S 剪裁情况二 S & P both in； 由内至内 输出 P P: output Clip boundary Polygon being clipped P: output Clip boundary S IN OUT 剪裁情况二 S & P both in； 由内至内 输出 P

IN OUT S i output P 剪裁情况三 S in, P out 由内至外 输出 i

(no output) P S IN OUT 剪裁情况四 S & P both out 由外至外 无顶点输出

1 2 3 4 5 6 窗口左边界 Example

1 2 3 4 5 6 1' 2' 3' 5' 4' 窗口左边界

1 2 3 4 5 6 1' 2' 3' 4' 5' 窗口左边界

算法改进 程序实现(P.275) 只有当窗口的四个边界都确定一个点在窗口内时才加入到输出顶点表中 Example(P.274图6.27) V1 V2 V3 V1’ V2’ V2’’ V3’

问题 SH算法适用于凸多边形 多余线段 Weiler-Atherton 算法 Convex polygons are correctly clipped by the SH algorithm, but concave polygons may be displayed with extraneous lines. 多余线段

6.2.3.2 Weiler-Atherton 算法 IDEA P.278 图6.29 Weiler算法适用于任意多边形裁剪区域 通过修改多边形顶点处理顺序(考虑顶点处理方向)，从而正确显示凹多边形。若顺时针处理多边形顶点，采用下列规则： 对由外到内的顶点对，沿着多边形边界的方向； 对由内到外的顶点对，按顺时针沿窗口边界的方向。 P.278 图6.29 Weiler算法适用于任意多边形裁剪区域

图 Weiler-Atherton算法裁剪凹多边形 B C D E V 1 2 3 4 图 Weiler-Atherton算法裁剪凹多边形 裁剪前 Weiler-Atherton算法的裁剪结果 返回

6.2.4 文本裁剪 全有或全无字符串裁剪 全有或全无字符裁剪 单字符裁剪 all-or-none string-clipping

全有或全无字符串裁剪 裁剪以字符串为单位，速度最快 裁剪前 STRING 1 STRING 2 裁剪后 STRING 2 all-or-none string-clipping

全有或全无字符裁剪 裁剪以字符为单位 裁剪前 STRING 1 STRING 2 ING 1 裁剪后 STRING 2 all-or-none character-clipping

单字符裁剪 裁剪以点（点阵字符）或线段（矢量字符）为单位，速度最慢 裁剪前 STRING 1 STRING 2 RING 1 裁剪后 character-clipping