裁剪实心圆

1高级计算机图形学高级计算机图形学讲授:董兰芳研究方向:科学计算可视化图形、图像处理模式识别Telephone:0551-3603484Email:lfdong@ustc.
edu.
cnHomepage:http://staff.
ustc.
edu.
cn/~lfdong/research.
html视觉计算与可视化实验室27.
1图形绘制流水线的基本策略7.
2图形系统的四个主要任务7.
3裁剪7.
4线段的裁剪7.
5多边形的裁剪7.
6其他图元的裁剪7.
7三维裁剪第七章第七章从顶点到片元从顶点到片元37.
17.
1图形绘制流水线的基本策略图形绘制流水线的基本策略如何实现绘制框架裁剪线段裁剪多边形裁剪光栅化直线是如何绘制的多边形的填充方法隐藏面消除47.
17.
1图形绘制流水线的基本策略图形绘制流水线的基本策略计算机图形系统可看作一个黑盒子.
输入:程序中定义的顶点和状态量--几何对象、属性和照相机设置输出:帧缓冲区里的彩色像素阵列内部处理:变换、裁剪、明暗处理、隐藏面消除和光栅化,对每个几何对象进行处理给颜色缓冲区的每个像素赋颜色值57.
17.
1图形绘制流水线的基本策略图形绘制流水线的基本策略考虑绘制由不透明对象构成的场景的两种方法:对于每个像素,确定投影到这个像素的离观察者最近的那个对象,从而基于该对象计算像素的明暗值光线跟踪框架.
面向像素的方法for(each_pixel)assign_a_color(pixel)对于每个对象,确定它所覆盖的像素,并用对象的状态确定像素的明暗值流水线方法,必须跟踪深度值.
面向对象的方法for(each_object)render(object)67.
17.
1图形绘制流水线的基本策略图形绘制流水线的基本策略面向对象方法:优点处理速度快,运行成本低缺点过去需要占用大量内存,每个对象单独处理的代价较大.
由于低价大容量内存,以及专用硬件芯片的出现,已不再是问题.
不能得到大多数全局效果,例如涉及多个对象的复杂光照隐藏面消除例外.
77.
17.
1图形绘制流水线的基本策略图形绘制流水线的基本策略优点:任何时刻只需有限的显示内存,且可以按显示器的刷新速度和次序生成像素,利用相邻像素间的连贯性可设计增量式算法,适合处理全局效果.
缺点:需要复杂的几何对象的数据结构必须确定哪些图元影响哪些像素,绘制过程中需要随时访问所有的几何数据.
面向图像的方法8第七章第七章从顶点到片元从顶点到片元7.
1图形绘制流水线的基本策略7.
2图形系统的四个主要任务7.
3裁剪7.
4线段的裁剪7.
5多边形的裁剪7.
6其他图元的裁剪7.
7三维裁剪97.
27.
2图形系统的四个主要任务图形系统的四个主要任务建模几何处理光栅化片元处理107.
27.
2图形系统的四个主要任务图形系统的四个主要任务建模器输出几何对象的顶点数据集,它工作在对象坐标系.
117.
27.
2图形系统的四个主要任务图形系统的四个主要任务几何处理的对象是顶点,目标是确定显示在屏幕上的几何对象,并确定这些对象顶点的明暗值或颜色值投影.
它包括步骤如下:投影图元装配裁剪明暗处理127.
27.
2图形系统的四个主要任务图形系统的四个主要任务投影利用模型-视图变换把几何对象从对象坐标系变换到照相机坐标系或视点坐标系.
利用投影变换把顶点变换到规范化视景体内,顶点表示为裁剪坐标.
图元装配变换是对顶点进行的,在进行后续操作需要组装成几何对象,称为图元装配.
裁剪是针对图元进行的.
光栅器不能对顶点单独进行处理.
137.
27.
2图形系统的四个主要任务图形系统的四个主要任务裁剪器确定哪些图元或图元的哪些部分会被传送到光栅器,最终可能会显示在屏幕上只有在视景体内的对象.
部分在视景体内的图元,裁剪后生成新的图元.
没被裁剪掉的顶点仍表示为四维齐次坐标,通过透视除法转换为三维的规范化设备坐标.
明暗处理为每个顶点赋颜色值,由当前绘制颜色决定.
开启光照时,根据改进的Phong模型计算得到.
147.
27.
2图形系统的四个主要任务图形系统的四个主要任务光栅化或扫描转换从裁剪后的对象生成片段(准像素).
对于线段,确定哪些像素可用来近似表示顶点间的线段.
对于多边形,确定哪些像素位于多边形顶点定义的二维域的内.
片段的颜色取决于系统颜色状态值或由光照模型计算顶点明暗值插值得到.
157.
27.
2图形系统的四个主要任务图形系统的四个主要任务片元处理最简单的情形下,片段的颜色由光栅器赋值,并且该值就是片元所对应的帧缓冲区中像素的颜色值.
纹理贴图、融合、半透明效果,反走样.
隐藏面消除:确定可见对象的片元值可见对象指位于视景体内,且没有被其他更靠近照相机的不透明对象所遮挡的对象.
16第七章第七章从顶点到片元从顶点到片元7.
1图形绘制流水线的基本策略7.
2图形系统的四个主要任务7.
3裁剪7.
4线段的裁剪7.
5多边形的裁剪7.
6其他图元的裁剪7.
7三维裁剪177.
37.
3裁剪裁剪三种情形:接受、拒绝或裁剪.
二维相对于裁剪窗口,三维相对于裁剪体.
对线段和多边形很容易进行裁剪.
曲线和文本需要首先转化为线段和多边形.
18第七章第七章从顶点到片元从顶点到片元7.
1图形绘制流水线的基本策略7.
2图形系统的四个主要任务7.
3裁剪7.
4线段的裁剪7.
5多边形的裁剪7.
6其他图元的裁剪7.
7三维裁剪点的裁剪P=(x,y)满足下列不等式:xwminyT;否则为0;CB为1当且仅当区域在窗口下边界之下,即yxR;否则为0;CL为1当且仅当区域在窗口左边界之左,即x>xL;否则为0;交点求法:知道线段的两端点,斜率-截距式的直线方程为Y=y1+m(x-x1)其中m=(y2-y1)/(x2-x1)x=x1+(y-y1)/m缺点:Cohen_Sutherland算法需要求线段与窗口边界的交点237.
47.
4线段的裁剪线段的裁剪线段裁剪的流水线体系:对窗口一边进行裁剪时,与其它边无关在流水线中要用到四个独立的裁剪器.
247.
47.
4线段的裁剪线段的裁剪Cyrus-Beck算法(简称CB算法)将线段表示成参数方程的形式,求线段与窗口边界的交点的参数,确定了线段的可见部分之后再用交点的参数计算交点的坐标,因此,Cyrus-Beck算法也称作参数化裁剪算法.
Cyrus-Beck算法不仅适用于矩形裁剪窗口,而且适用于凸多边形裁剪窗口,更加具有一般性.
本节中的裁剪窗口指的是凸多边形裁剪窗口.
Cyrus-Beck算法257.
47.
4线段的裁剪线段的裁剪向量的点积:对于两个向量V1和V2,假设它们之间的夹角为θ(0°≤θ≤180°),那么它们的点积V1·V2=|V1||V2|cosθV1·V2>0当且仅当0°≤θ1时所表示的点在线段的延长线上.
277.
47.
4线段的裁剪线段的裁剪P0P0P0P1P1P1内部外部Ni入点出点Ei入边、出边和平行边287.
47.
4线段的裁剪线段的裁剪对于窗口的任意一条边界Ei,假设它的外法向量(outwardnormal)为Ni,那么可以根据Ni·P0P1判断边界Ei属于哪一类:如果Ni·P0P10,那么Ni与P0P1方向大致相同,即P0P1指向窗口外部,边界Ei相对于P0P1为出边,Ei与P0P1的交点称为出点(leavingpoint);如果Ni·P0P1=0,那么Ni与P0P1垂直,边界Ei相对于P0P1为平行边,Ei与P0P1没有交点.
于是,裁剪窗口的所有边界相对于待裁剪的向量P0P1可以分为三类,即入边、出边和平行边,与此相对应,交点也分为两组,即入点组和出点组.
297.
47.
4线段的裁剪线段的裁剪线段P0P1与窗口边界Ei的交点.
假设交点为P(t),在Ei上任取一点Ai(Ai≠P(t)),向量AiP(t)与窗口边界Ei重合,与Ei的外法向量Ni垂直,即Ni·AiP(t)=0Ni·(P0+tP0P1-Ai)=0tNi·P0P1+Ni·AiP0=0t=-(Ni·AiP0)/(Ni·P0P1)307.
47.
4线段的裁剪线段的裁剪如果线段P0P1有可见部分(即完全可见或部分可见),假设可见部分的起点和终点的参数分别为tE和tL,[tE,tL]为线段可见部分的参数区间,显然应该有0≤tE≤tL≤1.
tE=0表示可见部分的起点为P0,否则表示可见部分的起点参数(入点组中参数值最大者);tL=0表示可见部分的终点为P1,否则表示可见部分的终点参数(出点组中参数值最小者).
如果线段P0P1没有可见部分(即不可见),那么入点组中参数值最大者一定大于出点组中参数值最小者.
317.
47.
4线段的裁剪线段的裁剪梁友栋-Barsky算法(简称LB算法)可以看作是Cyrus-Beck算法的特殊情况,此时裁剪窗口不是一般的凸多边形,而是矩形窗口.
(xL,yB)(xR,yT)OXY(0,-1)(0,1)(-1,0)(1,0)矩形窗口的外法向量327.
47.
4线段的裁剪线段的裁剪边Ei外法向量Ni边上一点AiAiP0Ni·AiP0Ni·P0P1上(y=yT)(0,1)(x,yT)(x0-x,y0-yT)(y0-yT)(y1-y0)下(y=yB)(0,-1)(x,yB)(x0-x,y0-yB)-(y0-yB)-(y1-y0)右(x=xR)(1,0)(xR,y)(x0-xR,y0-y)(x0-xR)(x1-x0)左(x=xL)(-1,0)(xL,y)(x0-xL,y0-y)-(x0-xL)-(x1-x0)梁友栋-Barsky算法中所用的量由于Cyrus-Beck算法适用于凸多边形裁剪窗口,更加具有一般性,因此当裁剪窗口为矩形时,其效率不高.
梁友栋-Barsky算法是针对矩形窗口的Cyrus-Beck算法,效率比一般的Cyrus-Beck算法更高.
33第七章第七章从顶点到片元从顶点到片元7.
1图形绘制流水线的基本策略7.
2图形系统的四个主要任务7.
3裁剪7.
4线段的裁剪7.
5多边形的裁剪7.
6其他图元的裁剪7.
7三维裁剪347.
57.
5多边形的裁剪多边形的裁剪多边形的裁剪:并不像线段裁剪那样简单裁剪一条线段最多得到一条线段,裁剪一个多边形可以得到多个多边形.
然而,裁剪凸多边形最多得到一个多边形.
357.
57.
5多边形的裁剪多边形的裁剪划分与凸性一种方法就是把非凸(凹)多边形用一组三角形代替,这个过程称为划分(tessellation).
这同样也使得填充变得简单.
在GLU库中有划分代码,但最好的方法就是由用户自己进行.
367.
57.
5多边形的裁剪多边形的裁剪多边形裁剪的流水线体系377.
57.
5多边形的裁剪多边形的裁剪包围盒(boundingbox)不是直接对复杂多边形进行裁剪,而是先用一个方向与坐标轴平行的长方体或其它形状包围多边形包围盒,应尽可能得小,容易计算出坐标的最大值与最小值.
应用包围盒,通过直接基于包围盒确定多边形的接受与拒绝.
387.
57.
5多边形的裁剪多边形的裁剪(a)(b)(c)(d)(e)多边形依次相对于窗口的每一条边界进行裁剪.
Sutherland-Hodgeman算法397.
57.
5多边形的裁剪多边形的裁剪SP外部内部SP外部内部ISP外部内部SP外部内部I情况1:输出P情况2:输出I情况3:无输出情况4:输出I、P缺点是需要生成并存储多边形相对于窗口的一条边界进行裁剪之后得到的中间多边形.
407.
57.
5多边形的裁剪多边形的裁剪Weiler-Atherton算法Weiler-Atherton算法沿着待裁剪多边形的边按照逆时针方向跟踪,直到遇到与窗口边界的交点为止;如果该交点为入点,那么继续沿着待裁剪多边形的边按照逆时针方向跟踪;如果该交点为出点,那么保存该交点供以后恢复跟踪时使用,并且在出点处沿着裁剪窗口的边界按照逆时针方向跟踪;重复上述过程,直到形成封闭的多边形,这样我们就得到了裁剪后的一个多边形;如果待裁剪多边形尚未完全遍历,那么就从前面保存的出点处恢复跟踪,继续沿着待裁剪多边形的边按照逆时针方向跟踪,直到待裁剪多边形完全遍历为止.
417.
57.
5多边形的裁剪多边形的裁剪Weiler-Atherton算法P1P2P3P4P5P6P7P8I1I2I3I442第七章第七章从顶点到片元从顶点到片元7.
1图形绘制流水线的基本策略7.
2图形系统的四个主要任务7.
3裁剪7.
4线段的裁剪7.
5多边形的裁剪7.
6其他图元的裁剪7.
7三维裁剪437.
77.
7其他图元的裁剪其他图元的裁剪圆的裁剪方法一1、先作包围盒测试,排除完全可见或显然完全不可见的情况.
2、如果圆的包围盒与窗口相交,将圆分为四个象限,对每个象限再作包围盒测试.
3、如果包围盒仍然与窗口相交,那么我们用解方程组的方法计算圆与窗口边界的交点,再对得到的圆弧进行扫描转换.
方法二"边扫描转换边裁剪".
对于空心圆,可以在扫描转换时逐点进行判断,只画那些位于窗口内部的像素;对于实心圆,可以在扫描转换时逐区段进行判断,只画区段位于窗口内部的部分.
447.
77.
7其他图元的裁剪其他图元的裁剪1.
字符串精度2.
字符精度3.
点精度457.
77.
7其他图元的裁剪其他图元的裁剪背景窗口窗口1窗口2多窗口系统裁剪467.
77.
7其他图元的裁剪其他图元的裁剪V1V2V3V4V5P1P2P3P4P5凹多边形窗口裁剪47第七章第七章从顶点到片元从顶点到片元7.
1图形绘制流水线的基本策略7.
2图形系统的四个主要任务7.
3裁剪7.
4线段的裁剪7.
5多边形的裁剪7.
6其他图元的裁剪7.
7三维裁剪487.
77.
7三维裁剪三维裁剪三维空间中的Cohen-Sutherland算法利用6位进行编码,必要时,相对于平面裁剪线段.
497.
77.
7三维裁剪三维裁剪在三维空间中一般的裁剪需要计算线段与任意平面的交点.
例:斜投影视图平面与直线的交点求交需要6次乘法运算和1次除法运算507.
77.
7三维裁剪三维裁剪规范化过程是视图生成的一部分(在裁剪前进行).
但在规范化后,相对于正平行六面体(长方体)进行裁剪.
这时典型的求交计算只需要一次浮点减法,例如:是否x>xmax51第七章第七章从顶点到片元从顶点到片元7.
1图形绘制流水线的基本策略7.
2图形系统的四个主要任务7.
3裁剪7.
4线段的裁剪7.
5多边形的裁剪7.
6其他图元的裁剪7.
7三维裁剪