光栅转化与消隐.ppt
消隐算法图像空间算法,2,内容,消隐的基本概念图像空间消隐：z缓冲器(z-buffer)算法物体空间消隐背面剔除算法表优先级算法三维物体的深度排序算法二叉空间剖分树算法,3,内容,消隐的基本概念图像空间消隐：z缓冲器(z-buffer)算法物体空间消隐背面剔除算法表优先级算法三维物体的深度排序算法二叉空间剖分树算法,4,消隐的基本概念,消隐的基本概念(隐藏线或面消除)：相对于观察者，确定场景中哪些物体是可见或部分可见的，哪些物体是不可见的消隐可以增加图形的真实感投影：三维空间二维平面二维平面：通过确定物体的前后关系，可以获得更多信息消隐是图形学中非常重要的一个基本问题,5,消隐的基本概念,没有消隐的图形具有二义性：(a)立方体的线框图；(b)顶点B离视点最近时的消隐；(c)顶点C离视点最近时的消隐,B,C,6,消隐的基本概念,消隐问题的复杂性导致许多精巧的算法，不同算法适合于不同的应用环境在实时模拟过程中，要求消隐算法速度快，通常生成的图形质量一般 在真实感图形生成过程中，要生成高质量的图形，通常消隐算法速度较慢 消隐算法的权衡：消隐效率、图形质量,7,消隐与排序、连贯性,消隐与物体排序、连贯性密切相关排序：判断场景中的物体全部或者部分与视点之间的远近连贯性：场景中物体或其投影所表现出来的相似程度消隐算法的效率很大程度上取决于排序的效率、各种连贯性的利用,8,面消隐：输出着色图,消隐的分类对象与输出,根据消隐对象和输出结果,线消隐：输出线框图,9,消隐的分类：实现的坐标空间,算法实现时所在的坐标系(空间)进行分类：图像空间消隐景物空间消隐,10,图像空间消隐,描述for(图像中每一个像素)确定由投影点与像素连线穿过的距离观察点最近的物体；用适当的颜色绘制该像素；特点：在屏幕坐标系中进行的，生成的图像一般受限于显示器的分辨率 算法复杂度为O(nN)：场景中每一个物体要和屏幕中每一个像素进行排序比较，n为物体个数，N为像素个数代表方法：z缓冲器算法，扫描线算法等,11,景物空间消隐,描述for(世界坐标系中的每一个物体)确定未被遮挡的物体或者部分物体；用恰当的颜色绘制出可见部分；特点：算法精度高，与显示器的分辨率无关，适合于精密的CAD工程领域 算法复杂度为O(n2)：场景中每一个物体都要和场景中其他的物体进行排序比较，n为物体个数代表方法：背面剔除、表优先级算法等,12,景物和图形空间消隐方法的比较,理论上如果 n(物体数)N(像素数)，则景物空间算法的计算量O(n2)小于图像空间算法O(nN)实际应用中通常会考虑画面的连贯性，所以图像空间算法的效率有可能更高 景物空间和图像空间的混合消隐算法,13,消隐算法的几个假设,若图形对象为线框模型表示，需有面的信息投影平面是oxy平面投影方向为负z轴方向的平行投影z值越大，离视点越近透视变换转化为平行投影不能处理相互贯穿或循环遮挡的物体，此时应做特殊处理,14,消隐算法的几个假设,投影变换示意图,15,消隐算法的几个假设,相互贯穿,循环遮挡,16,内容,消隐的基本概念图像空间消隐：z缓冲器(z-buffer)算法物体空间消隐背面剔除算法表优先级算法三维物体的深度排序算法二叉空间剖分树算法,17,z缓冲器算法,z(深度)缓冲器算法属于图像空间算法 z缓冲器是帧缓冲器的推广帧缓冲器：存储的是像素的颜色属性z缓冲器：存储的是对应像素的z值假设在视点坐标系(oxyz)中，投影平面为z=0，视线方向沿(-z)轴方向，投影为平行投影深度值就是物体沿着视线(-z)方向、与视点的距离 离视点近的物体遮挡离视点远的物体：z值越大，离视点越近,18,z缓冲器算法,投影变换示意图,19,颜色与深度缓冲举例,颜色缓冲,深度缓冲,20,z缓冲器算法描述,(1)帧缓冲器中的颜色置为背景颜色(2)z缓冲器中的z值置成最小值(离视点最远)(3)以任意顺序扫描各多边形 a)对于多边形中的每一像素，计算其深度值z(x,y)b)比较z(x,y)与z缓冲器中已有的值zbuffer(x,y)如果z(x,y)zbuffer(x,y)，那么 计算该像素(x,y)的光亮值属性并写入帧缓冲器 更新z缓冲器 zbuffer(x,y)z(x,y),21,z缓冲器的其它应用,阴影算法：以光源为视点的z缓冲器,22,z缓冲器的其它应用,rgb和z缓冲器相结合，实现图像的合成,23,z缓冲器算法分析,优点算法复杂度(O(nN)：对于给定的图像空间，N是固定的，所以算法复杂度只会随着场景的复杂度线性地增加无须排序：场景中的物体是按任意顺序写入帧缓冲器和z缓冲器的，无须对物体进行排序，从而节省了排序的时间适合于任何几何物体：能够计算与直线交点适合于并行实现(硬件加速),24,z缓冲器算法分析,不足z缓冲器需要占用大量的存储单元一个大规模复杂场景中：深度范围可能为106，一个像素需要24bit来存储其深度信息。如果显示分辨率为12801024，那么深度缓冲器需要4MB存储空间深度的采样与量化带来走样现象难以处理透明物体解决存储问题：逐区域进行z缓冲器消隐,25,内容,消隐的基本概念图像空间消隐：z缓冲器(z-buffer)算法物体空间消隐背面剔除算法表优先级算法三维物体的深度排序算法二叉空间剖分树算法,26,背面剔除算法,利用视线方向V和物体表面法向N之间的关系NV0：不可见NV0：可见,27,背面剔除算法,作为消隐算法，背面剔除适用于凸多面体，不适用于凹多面体或其它复杂物体,对于蓝色与绿色的面，简单的背面剔除不能不能实现完全消隐,28,背面剔除算法,适用于场景消隐的预处理：消除一些显然不可见表面，从而提高其它消隐算法的效率,29,内容,消隐的基本概念图像空间消隐：z缓冲器(z-buffer)算法物体空间消隐背面剔除算法表优先级算法三维物体的深度排序算法二叉空间剖分树算法,30,景物空间中的表优先级算法,原理：离视点近的物体可能遮挡离视点远的物体在景物空间确定物体之间的可见性顺序(物体离视点远近)，由远及近地绘制出正确的图像结果油画家算法条件：场景中物体在z方向上没有相互重叠,31,二维半物体的深度排序,二维半物体的深度值是常数：卡通动画、窗口管理、VLSI设计、图像合成二维半物体的深度排序算法只要简单地比较其z值即可,32,三维物体的深度排序算法,将场景中的多边形序列按其z坐标的最小值zmin(物体上离视点最远的点)进行排序 当物体间 的z值范围不重叠时：假设多边形P的zmin在上述排序中最小，如果多边形P的z值范围与Q的z值范围不重叠，即Pzmax Qzmin，此时可以断定多边形P的优先级最低(见下图),33,三维物体的深度排序算法,物体间的z值范围不重叠,34,三维物体的深度排序算法,当物体间的z值范围重叠时：判断多边形P是否遮挡场景中多边形Q，需作如下5个判别步骤多边形P和Q的x坐标范围是否不重叠多边形P和Q的y坐标范围是否不重叠从视点看去，多边形P是否完全位于Q的背面从视点看去，多边形Q是否完全位于P的同一侧多边形P和Q在xy平面上的投影是否不重叠,35,三维物体的深度排序算法,1.多边形P和多边形Q的x坐标范围不重叠,36,三维物体的深度排序算法,2.多边形P和多边形Q的y坐标范围不重叠,37,三维物体的深度排序算法,3.从视点看去，多边形P完全位于Q的背面,38,三维物体的深度排序算法,4.从视点看去，多边形Q完全位于P的同一侧,39,三维物体的深度排序算法,5.多边形P和Q在xy平面上的投影不重叠,40,三维物体的深度排序算法,如果上述五种情况中只要有一种成立，就表明多边形P和Q是互不遮挡的，即多边形P的绘制优先级低于Q如果上述判断都不成立，说明多边形P有可能遮挡Q，此时把多边形P和Q进行互换重新进行判断，而重新判断只要对上述条件(3)和(4)进行即可,41,三维物体的深度排序算法,P和Q交换顺序后，仍不能判断其优先级顺序，可以按如下方法处理：将其中一个多边形沿另一个物体剖分避免循环判断：P做标记多边形剖分：将P沿Q剖分,42,三维物体的深度排序算法,相互遮挡时，将其中一个多边形沿另一个多边形进行剖分,43,三维物体的深度排序算法,深度排序算法有时可能将具有正确深度顺序的多边形进行剖分,44,三维物体的深度排序算法,深度排序算法有时可能将具有正确深度顺序的多边形进行剖分根据上述规则，P的优先级低于Q把多边形Q沿z轴算转如图的角度后，P的优先级仍然低于Q当用上述五个判别条件对它们进行判断时都不成立，P需要相对于Q进行剖分多余的剖分会增加计算量！,45,三维物体的深度排序算法,具有正确深度顺序而被剖分的多边形：多边形顶点只标记了其深度值。左图可以直接采用油画家算法进行绘制；右图虽然具有正确的深度顺序，但是它们在进行深度比较的时，五个条件均不满足。根据上述排序算法，需要进行对P多边形剖分,46,深度排序算法,三维物体的深度排序算法适合于固定视点的消隐通过多边形的剖分，总是可以实现多边形物体在三维空间中的深度排序深度排序算法可以有效地实现透明效果在视点变化的场合中(如飞行模拟)，深度排序算法难以满足实时性的要求算法复杂度O(nlogn),47,内容,消隐的基本概念图像空间消隐：z缓冲器(z-buffer)算法物体空间消隐背面剔除算法表优先级算法三维物体的深度排序算法二叉空间剖分树算法,48,二叉空间剖分树,二叉空间剖分树(BSP树-Binary Space Partitioning)的基本原理：如果场景中的多边形可以被一个平面分割成两部分(如果有多边形跨越分割平面，则剖分该多边形)，那么当视点位于分割平面的正侧时，位于分割平面正侧的多边形会遮挡位于分割平面另一侧的多边形 对位于分割平面两侧的多边形继续进行递归分割，直至每一个分割平面两侧或一侧只有一个多边形分割过程可以用一个二叉树的数据结构来表示 在BSP树算法中，分割平面取作场景中的多边形,49,二叉空间剖分树,z,x,50,二叉空间剖分树实例,箭头表示多边形的正侧。在图(a)中，首先选取1作为分割平面，2位于1的正侧，3和5位于1的负侧。4被1分割为4a和4b。其中，4a位于1的正侧，4b位于1的负侧。,51,二叉空间剖分树实例,对上述二叉树的左右两个分支进行进一步的分割。对于左侧分支，再取2所在平面为分割平面，4a位于2的正侧；对于右侧分支，取3所在的平面为分割平面，4b位于3的正侧，5位于3的负侧。至此建立了对所给场景的BSP树，树的每个叶节点是一个多边形,52,二叉空间剖分树,给定场景的BSP树不是唯一的“最佳”的BSP树的两个标准使BSP树尽可能平衡尽可能减少多边形的剖分,53,二叉空间剖分树另一种实现,54,二叉空间剖分树描述性算法,if PolygonList=NULL then BSPTree=NULL;else PartitionPolygon=SelectAndRemove(PolygonList);PositiveBranch=NegativeBranch=NULL;for(each polygon P in PolygonList)if(P in the positive side of PartitionPolygon)AddPolygonToBSP(P,PositiveBranch);else if(P in the negative side of PartitionPolygon)AddPolygonToBSP(P,NegativeBranch);else SubdividePolygon(P,PartitionPolygon,PosiP,NegaP);AddPolygonToBSP(PosiP,PositveBranch);AddPolygonToBSP(NegaP,NegativeBranch);CombineBSPTree(PositiveBranch,PartitionPolygon,NegativeBranch);,55,二叉空间剖分树的遍历,BSP树的遍历过程就是建立多边形的优先级的过程，这是一个递归过程 如果视点位于分割平面的正侧，那么该BSP树的遍历过程应当是：负侧分支根结点多边形正侧分支如果视点位于分割平面的负侧，那么该BSP树的遍历过程应当是：正侧分支根结点多边形负侧分支 这个判定标准递归地应用于每个子分支,56,二叉空间剖分树的遍历算法,void showBSP(v:Viewer,T:BSPtree)if(T is empty)return;P=root of T;if(viewer is in front of P)showBSP(back subtree of T);draw P;showBSP(front subtree of T);else showBSP(front subtree of T);draw P;showBSP(back subtree of T);,57,小结,消隐的基本概念图像空间消隐：z缓冲器(z-buffer)算法物体空间消隐背面剔除算法表优先级算法三维物体的深度排序算法二叉空间剖分树算法,
