第五章 2.图形处理算法.ppt

第5章　图形处理算法 5.1　视见变换 5.1.2　计算机图形学中常用的坐标系 目的: 5.1.4　变换过程 5.2　二维图形的裁剪（Clipping） 5.2.2　裁剪的基本思想 5.3　光栅图形的扫描转换与区域填充 5.3.2　边填充算法 5.3.3　种子填充算法（边界填充） 区域连通方式对填充结果的影响 填充算法 A可见否? AB显然不可见 P= (A+B)/2 |P - B|ε？ AP显然不可见? A = P B= P N N N Y A= P exit 原线完全不可见 exit A = P exit 中点分割算法框图 N Y Y Y （四） 梁友栋-Barsky算法 y x yT yB xL xB A B C D P1 P0 P0C可见部分 设要裁减的线段是P0P1。 P0P1和窗口边界交于A,B,C,D四点 算法的基本思想是从A,B和P0三点中找出最靠近的P1点 图中要找的点是P0。 从C,D和P1中找出最靠近P0的点 要找的点是C点 那么P0C就是P0P1线段上的可见部分 具体计算时，把P0P1写成参数方程 x = x0 + Δx · t y = y0 + Δy · t 其中Δx=x1 - x0， Δy=y1 - y0 把窗口边界的四条边分成两类，一类称为始边，另一类称为终边。 当Δx≥0（Δy≥0）时，称x=xL(y=yB)为始边， x=xR(y=yT)为终边。 当Δx0（Δy0）时，称x=xL(y=yB)为终边， x=xR(y=yT)为始边。 求出P0P1和两条始边的交点的参数t0’和t0’’ 令：t0 = max(t0’，t0’’，0) 则t0就是图中A、B和P0三点中最靠近P1的点的参数。 当t1t0时，直线方程中参数t∈[t0, t1]的线段就是P0P1的可见部分。当t0t1时，整个直线段为不可见。 求出P0P1和两条终边的交点的参数t1’，t1’’ ， 令：t1 = min(t1’，t1’’，1) 则t1就是图中C、D和P1三点中最靠近P0的点的参数。 它使QL=0，DL0和QR=0，DR0。这时由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交点，而让EF和y=yT及y=yB的交点决定直线段上的可见部分。 xL xB y x E F C D A B Qi=0的情况 为了确定始边和终边，和求P0P1与它们的交点 令： QL = -Δx DL = x0 - xL QR = Δx DR = xR - x0 QB = - Δy DB = y0 - yB QT = Δx DT = yT - y0 易知交点的参数: ti = Di/Qi, i= L,R,B,T 当Qi0时，求得的ti必是P0P1和始边的交点的参数 当Qi0时，ti必是P0P1和终边的交点的参数。 当Qi=0时，若Di0，则P0P1是完全不可见的（如图4中AB，有QR=0，DR0）。 当Qi=0而相应的Di ≥0时则是另一种情况，图的EF就是这种情况， 1 2 4 6 5 3 7 8 　　上机调试例5-1及区域编码算法程序例5-2 　　给下图8条直线进行区域编码，并简述2、3两条线段的剪取过程。 作业： 5.3.1　多边形的扫描转换 1. 什么是多边形的扫描转换 如图1 多边形可表示成图2的底色为灰色的象素的集合。 图2 多边形的点阵表示 在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示 顶点表示：用多边形顶点的序列来刻划多边形。 多边形可表示成P0P1P2P3P4P0的点序列形式。 这种表示方法的特点是:直观、几何意义强、占内存少。 点阵表示：用位于多边形内的象素的集合来刻划多边形。 这种方法虽然失去了许多重要的几何信息，但便于运用帧缓冲存储器表示图形，是面着色所需要的图形表示形式。 图1 多边形的顶点表示 P0 P1 P2 P3 P4 光栅图形技术的迅速发展,应用领域地不断扩大,它已成为CG的一个重要分支 使光栅图形的画面明暗自然,色彩丰富,形象逼真,具有真实感 光栅图形的一个基本问题就是把多边形的顶点表示转换为点阵表示. 　　就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。 首要问题：判断一个象素是在多边形内还是在多边形外。 数学上提供的方法：扫描交点的奇偶数判别法。 　　区域填充即给出一个区域的边界，要求对边界范围内的所有象素单元赋予指定的颜色代码。 　　多边形区域填充给出一个多边形的边界，要求对多边形边界范围