汪老师课件3二维图元的光栅化处理

1、二维图元的光栅化处理,2019/6/21,概要,二维图元的裁剪 二维图元的填充 二维图元的反走样,2019/6/21,1 二维裁剪,基本目的：判断图形元素是否落在窗口区域之内。 显示部分画面，指定图形内容，窗口系统。地图显示。 图形编辑 图形裁剪算法，直接影响图形系统的效率。,2019/6/21,二维裁剪,两个步骤：图元在窗口区域内外的判别；图形元素与窗口的求交； 裁剪扫描转换: 点阵图形在设备坐标系中进行，算法效率不高，适合求交难度大的图形。 裁剪扫描转换: 点、线、多边形等简单图形，在世界坐标系中进行。分析裁剪。,2019/6/21,1.1直线段裁剪,是基础。 裁剪线段与窗口的关系：(1)线段完全可见；(2)显然不可见；(3)其它 提高裁剪效率： 快速判断情形(1)(2)， 对于情形(3)，设法减 少求交次数和每次求 交时所需的计算量。 点裁剪。,2019/6/21,1.1.2 直接求交算法,直线与窗口边都 写成参数形式， 求参数值。,2019/6/21,1.1.3 Cohen-SutherLand算法(编码算法),裁剪过程是递归的。 由窗口四条边所在直线把二维平面分成9个区域，每

2、个区域赋予一个四位编码 CtCbCrCl，上下右左； 各位编码含义： 上面：if yymax, Ct=1, else, 0; 下面：if yxmax, Cr=1, else, 0; 左面：if xxmix, Cl=1, else, 0;,2019/6/21,线段端点编码，区域的编码值，端点在窗口内部，只要编码值为0。 两个端点的编码的逻辑“与”非0时，落在窗口某边外侧。线段显然不可见。 窗口与线段求交，验证两端点各位编码值，相异则求交。,2019/6/21,最坏情形，线段求交四次。 求次测试顺序固定， 由交点编码可判断线段的可见性。,2019/6/21,特点：用编码方法可快速判断线段的完全可见和显然不可见。 特别适用二种情形：大窗口场合；窗口特别小场合(光标拾取图形)，光标看作小的裁剪窗口。,2019/6/21,1.1.4 Nicholl-Lee-Nicholl算法,消除C-S算法中多次求交的情况。 基本想法：对2D平面的更细的划分。,2019/6/21,假定P0点落在区域0，4，5,2019/6/21,步骤： 1.区域细分(9个区域)，只考察P0在0，4，5情形，其它类似。 2.P0

3、点向窗口的四角点引射线，把平面区域分成4个有意义的区域。判断P1所在区域位置，可判定P0、P1与窗口那条边求交。 3.用斜率判P1所在区域 4.求交点，确定线段可见部分。 特点：效率较高，但仅适合二维矩形窗口。,2019/6/21,2019/6/21,1.1.5中点分割法,想法：从P0点出发找出距P0最近的可见点，从P1点出发找出距P1最近的可见点。 取中点Pm=(P1+P2)/2。（算法见框图）,2019/6/21,2019/6/21,对分辩率为2N*2N的显示器，上述二分过程最多进行N次。 主要过程只用到加法和除法运算，适合硬件实现。适合平行计算。,2019/6/21,1.1.6 Liang-Barsky算法,看作点集之间的交集，即为裁剪结果。 Q0Q1为诱导窗口，一维窗口，二维裁剪简化成一维裁剪。,2019/6/21,一维裁剪问题 P0P1与Q0Q1之间的关系如图。 建立坐标系，P0为原点P1为一个单位， Q0为t0 ，Q1 为t1 。 P0P1至少部分可见的充要条件是 Max(0,t0)=min(1,t1) 且可见部分的参数区间为 Max(0,t0),min(1,t1),201

4、9/6/21,诱导窗口计算： 假设直线l与窗口左、右、上、下四边的交点为L，R，T，B P0P1的可见部分 VW=P0P1LRTB 这就是二维裁剪 问题的解。,2019/6/21,用参数域方法定可见部分： 始边，终边(对窗口边而言)由有向直线段方向定。 诱导窗口与P0P1的交点可用直线的参数区间来表示。 交点参数的简单确定：用X或Y坐标边的长度比。,2019/6/21,1.1.7参数化算法(Lyrus-Beck算法),考虑凸多边形区域R和直线段P1P2 P1P2=(P2-P1)*t+P1 凸多边形的性质：P(t)在凸多边形内的充要条件是，对于凸多边形边界上任意一点A和该点处内法向N，都有 N(P(t)-A)0,2019/6/21,A,P1,P2,R,2019/6/21,k条边的多边形，可见线段参数区间的解: Ni (p(t)-Ai)=0, i=0,k, 0t 1. 即： Ni (P1-Ai)+ Ni (P2-P1) t=0可得：ti= 线段可见的交点参数： t1=max0,maxti: Ni (P2-P1) 0 t2=min1,minti: Ni (P2-P1)0 若 t1=t2, t

5、1，t2是可见线段的交点参数区间，否则，线段不可见。,2019/6/21,算法的几何意义：,当凸多边形是矩形窗口且矩形的边与坐标轴平行时，算法退化为Liang-Barsky算法。,2019/6/21,1.2 多边形裁剪,直线段裁剪的组合？ 封闭的二维区域，裁剪后的封闭性？ 不封闭，如何封闭？ 凹多边形裁剪后可能出现多个小的多边形，如何确定其边界？,2019/6/21,2019/6/21,1.2.1 Sutherland-Hodgman算法,分割处理：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。 流水线处理：上边的结果是左边的开始。,2019/6/21,Sutlerland_Hodgman算法 逐边裁剪 ：两次分解，流水线处理 第一次分解：将多边形关于矩形窗口的裁剪分解为它关于窗口四边所在直线的裁剪 第二次分解：将多边形关于一条直线的裁剪分解为多边形各边关于该直线的裁剪 例子,2019/6/21,逐边裁剪,2019/6/21,多边形的边与半空间的关系 裁剪结果的顶点构成：裁剪边内侧的原顶点；多边形的边与裁剪边的交点。 顺序连接。,2019/6/21,几点说明： 裁剪

6、算法采用流水线方式，适合硬件实现。 可推广到任意凸多边形，三维凸多面体。 凸的？,2019/6/21,1.2.2 Weiler-Atherton算法,裁剪窗口，被裁剪多边形可以是任意多边形：凸、凹、带内环。地位对等。 被裁剪多边形为主多边形，裁剪窗口为裁剪多边形。,2019/6/21,主多边形和裁剪多边形把二维平面分成两部分。 内裁剪：AB 外裁剪：A-B,A,2019/6/21,进点：主多边形边界由此进入裁剪多边形区域内：I1 I3 I5 I7 I9 I11 出点：I0 I2 I4 I6 I8 I10,2019/6/21,（内裁剪）算法步骤：,建顶点表; 求交点； 裁剪； 奇异情形处理。,2019/6/21,2019/6/21,1.3 字符裁剪,三种典型方式： 基于字符串； 基于字符； 基于构成字符的最小元素：像素裁剪： 点阵字符，点裁剪；矢量字符，线段裁剪。,2019/6/21,2 二维图元的填充算法,扫描转换：矩形、多边形、扇形 确定图元内部像素； 内部颜色显示：均匀填色，图像填充；,2019/6/21,2.1扫描转换矩形,比一般多边形可简化计算。 应用非常多，窗口系统。 多边形

7、共享边处理： 边有宽度，光栅系统的特点； 避免填充扩大化。,2019/6/21,2.2 扫描转换多边形,顶点表示；点阵表示。 三种方法： 逐点判断法；扫描线算法；边缘填充法。,2019/6/21,逐点判断法,逐个判断绘图窗口内的像素： 如何判断点在多边形的内外关系？ 射线法： 累计角度法 编码法；,2019/6/21,(1)射线法 V点出发射线，与多边形边相交，若交点个数偶数，V点在外边，反之 交点通过多边形顶点? 通过等边的中点(不考虑边的端点),2019/6/21,(2) 累计角度法 步骤 从v点向多边形P顶点发出射线，形成有向角 计算有相交的和， 离散计算方法：编码方法,2019/6/21,(3)编码方法：累计角度方法的离散方法 Step: a.预处理，测试点在边上否。 b.V为中点作局部坐标系。 c.顶点编码， d.边编码。PiPi+1: PiPi+1=Ipi+1-Ipi e.计算编码和: 0, 在外； +/-4， 在内； 注意： 周期性为4， =2时？在边界上。 逐点判断法程序简单， 速度太慢，效率低。,2019/6/21,2.3 扫描线算法(有序边表算法),利用像素之间的连

8、贯性，逐点判断和反复求交。 一条扫描线与多边形的边间有偶数个交点。 交点之间的点或在内，或在外，称为扫描线的连贯性 处理对象：非自交多边形,2019/6/21,填充过程步骤(对于一条扫描线): (1)求交点 (2)交点排序 (3)交点配对，填充区段。,2019/6/21,先解决填充过程中的两个特殊问题： 第一是扫描线与多边形的顶点相交，交点的取舍，保证交点正确配对。 第二是边界上象素的取舍问题，避免填充扩大化。 方法： 1.检查两相邻边在扫描线的哪一侧。 只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。 2.边界象素：规定落在右上边界的象素不予填充。,2019/6/21,(a)1个交点 (b)1个交点 (c) 2个交点 (d) 0个交点,2019/6/21,交点的取整规则 要求：使生成的像素全部位于多边形之内 用于线画图元扫描转换的四舍五入原则导致部分像素位于多边形之外，从而不可用 假定非水平边与扫描线y=e 相交，交点的合作标为x, 规则如下,2019/6/21,X为小数 (a)交点位于左边之上，相右取整 (b)交点位于右

9、边之上，相左取整,2019/6/21,2. (x,e)落在像素之上 (a) (x,e)位于左边之上，属于多边形 (b) (x,e)位于右边之上，不属于多边形 边界象素：规定落在右上边界的象素不予填充。,2019/6/21,特殊情况处理 水平边:扔掉！ 尖角：反混淆,2019/6/21,几个概念：,活性边：与当前扫描线相交的边。 活性边表：按交点x的增量顺序存放在一个链表中；活性边表的每个结点存放对应边的有关信息。 边的连贯性：某条边与当前扫描线相交，也可能与下一条扫描线相交。 扫描线的连贯性：当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序可能相同或类似。,2019/6/21,设扫描线与边的交点x坐标，下一条扫描线与这条边的交点x坐标，只要用增量法计算，不必重新求交。 设边的直线方程为ax+by+c=0, xi+1=xi-b/a 记x=-b/a为常量 活性边表的结点信息 typedef struct int ymax; float x,deltax(X); Edge *nextEdge; Edge; X：当前扫描线与边的交点。 X：以当前扫描线到下一条扫描线之间的X的增量(边的斜率的倒数)。 Ymax: 边所交的最高扫描线号 由扫描线的连贯性，新交点序列与旧交点序列基本一致。,2019/6/21,(a) Y=6对应的活化边表,(b) Y=7对应的活化边表,2019/6/21,算法：(对每一条扫描线i) step1：把新边表NETi中的边结点，用插入排序法插入活性边表AET，使之按X坐标递增顺序排序； step2：遍历AET表，把配对交点之间的区间(左闭右开)上的各象素(X，Y)，用drawpixel(x,y,color)改写象素颜色值； step3：遍历AET表，把Ymax=i的结点从AET表中删除，并把Ymaxi的结果点的X值递增X；若允许多边形的边自相交，则用冒泡排序法对AET表重新排序； step4：重复各扫描线,2019/6/21,特点：算法效率比逐点填充法高很多。 缺点：对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。,2019/6/21,补充：光栅操作,显示模式 4种简单的显示模式

《汪老师课件3二维图元的光栅化处理》由会员E****分享，可在线阅读，更多相关《汪老师课件3二维图元的光栅化处理》请在金锄头文库上搜索。