光栅转化与消隐.pptx

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