计算机图形学CHP9可见面判别算法ppt课件

Computer Graphics第九章第九章 可见面判别算法可见面判别算法可见面判别算法的实现空间可见面判别算法的实现空间可见面判别算法的分类可见面判别算法的分类9.1 可见面判别算法的实现空间：可见面判别算法的实现空间：消隐的思索：消隐的思索：用计算机生成三维形体的真实图形，是计算机图形学研讨的重用计算机生成三维形体的真实图形，是计算机图形学研讨的重要内容之一。在运用显示设备描画三维图形时，必需把三维信要内容之一。在运用显示设备描画三维图形时，必需把三维信息作某种投影变换，在二维显示平面上绘制出来。息作某种投影变换，在二维显示平面上绘制出来。由于投影变换失去了深度信息，往往导致图形的二义性：由于投影变换失去了深度信息，往往导致图形的二义性：要消除二义性，必需在绘制时隐藏实践不可见的线和面，即消隐。经过消隐的投影图形称为物体的真实图形。三维形体三维形体察看空间的定义及转换察看空间的定义及转换三维裁剪三维裁剪投投 影影消消 隐隐消消 隐隐投投 影影投投 影影光照效果生成光照效果生成线框图线框图消隐图消隐图真实感图真实感图三维形体的二维显示：三维形体的二维显示：选择不同的消隐算法：选择不同的消隐算法：消隐问题有不同的算法，有些算法要求速度快，有些要求图消隐问题有不同的算法，有些算法要求速度快，有些要求图形的真实度高。例如，快速消隐算法可用于实时模拟如飞行模形的真实度高。例如，快速消隐算法可用于实时模拟如飞行模拟等；具有高度真实感图形的消隐算法可用于计算机动画等领拟等；具有高度真实感图形的消隐算法可用于计算机动画等领域，所生成的图形普通具有延续颜色，并能产生阴影、透明、域，所生成的图形普通具有延续颜色，并能产生阴影、透明、外表纹理及反射、折射等视觉效果。不过这类算法比较慢。产外表纹理及反射、折射等视觉效果。不过这类算法比较慢。产生一幅图能够需求几分钟甚至几小时。所以，在进展消隐算法生一幅图能够需求几分钟甚至几小时。所以，在进展消隐算法的设计时，应在计算速度和图形细节之间进展权衡，任何一种的设计时，应在计算速度和图形细节之间进展权衡，任何一种算法都不能兼顾两者。算法都不能兼顾两者。消除物体上不可见的线段，叫线消隐；对象：线框模型消除物体上不可见的线段，叫线消隐；对象：线框模型消除物体上不可见的面，叫面消隐。对象：填色图消除物体上不可见的面，叫面消隐。对象：填色图消隐的分类：消隐的分类：消隐算法的实现空间：消隐算法的实现空间：形体空间法形体空间法(object-space method)直接对形体定义进展处置把形体和形体的某些部分彼此比较，直接对形体定义进展处置把形体和形体的某些部分彼此比较，以确定哪些外表和线作为一个整体是不可见的以确定哪些外表和线作为一个整体是不可见的for(场景中的每一个物体 将其与场景中的其它物体比较，确定其外表的可见部分；显示该物体外表的可见部分；图像空间法图像空间法(image-space method)对形体投影图像进展处置对投影平面上的每一个象素位置逐点对形体投影图像进展处置对投影平面上的每一个象素位置逐点检测其可见性检测其可见性 常用常用for(窗口内的每一个像素)确定距视点最近的物体，以该物体外表的颜色来显示像素二者区别：二者区别：形体空间法是在定义对象的坐标系中实现的，而图像空间法是在对象显示的屏幕坐标系中实现的。形体空间法以尽能够高的精度完成几何计算，所以可以把图像放大许多倍而不致损害其准确性，但是图像空间法只能以与显示屏的分辨率相顺应的精度来完成计算，所以其图像的放大效果较差。这两类算法的性能特性也是不同的。形体空间法所需的计算时间随场量中物体的个数而添加，而图像空间法的计算时间那么随图像中可见部分的复杂程度而添加。算法复杂度：算法复杂度：假设场景中有k个物体，平均每个物体外表由h个多边形构成，显示区域中有m n个像素，那么：图像空间法的算法复杂度为：O(mnkh)形体空间法的算法复杂度为：O(kh)*(kh)分类：分类：图像空间法：深度缓冲器算法、图像空间法：深度缓冲器算法、A A缓冲器算法、区间扫描线算缓冲器算法、区间扫描线算法等。法等。形体空间法：形体空间法：BSP(binary space-partitioning)BSP(binary space-partitioning)树算法、多边树算法、多边形区域排序算法。形区域排序算法。介于二者之间：深度排序算法、区域细分算法、光线投射算法介于二者之间：深度排序算法、区域细分算法、光线投射算法等。等。外表定向法后向面消除法back-faces method层深缓冲法depth-buffer methodA缓冲器算法A-buffer method区间扫描线算法scan-line method深度排序算法depth-sorting method光线投射算法9.2 可见面判别算法类型：可见面判别算法类型：nwuv p1p2p2p3p4一外表定向法：一外表定向法：外表法矢量：指向外表外部法线方向视野矢量：物体外表任一点指向视点的方向视角：法矢量和视野矢量的夹角。判别原那么：invisiblevisible)180,90()90,0(000计算方法：计算signcos13121),(cos|ppvppupwzwywxpwvunnwnw计算公式：计算公式：nwuv p1p2p2p3p4facesbackinvisiblethendczbyaxifzyxpoviewdczbyax_0_),(:int0后向面的判别：后向面的判别：二后向面二后向面back face消除法：消除法：XZYZvN(A,B,C)所谓的所谓的back face取取决于察看的方向和察决于察看的方向和察看系统的坐标系看系统的坐标系(右右手和左手手和左手)例：左手系，察看方向为z轴正向容易得知：容易得知：If C0back faces invisibleElse visibleXZYview direction(x,y)s1s2s3三层深缓冲法三层深缓冲法ZBuffer算法：算法：根本思想：对投影平面上的每个像素点逐点检测其可见性，以近物取代远物。如图，如图，s1s1平面间隔投影平面间隔投影平面最近，所以投影点平面最近，所以投影点x x，y y将保管将保管s1s1平面平面上相应点的属性信息。上相应点的属性信息。当要改动某个像素的颜色值时，首先检查当前多边形的深度值能否小于该像素原来的深度值保管在该像素所对应的Z缓冲器的单元中，假设小于，阐明当前多边形更接近察看点，用它的颜色交换像素原来的颜色；否那么阐明在当前像素处，当前多边形被前面所绘制的多边形遮挡了，是不可见的，像素的颜色值不改动。两个缓冲器：两个缓冲器：帧缓冲器用来存储图像空间中每一个象素的属性；帧缓冲器用来存储图像空间中每一个象素的属性；Z缓冲器用来存储图像空间中每一个可见象素相应缓冲器用来存储图像空间中每一个可见象素相应的深度的深度(或或Z坐标坐标)，是一个独立的深度缓冲器。，是一个独立的深度缓冲器。算法主要是计算将要写入帧缓冲器象素的深度(或Z值)，并与已存储在Z缓冲器中该象素的原来深度进展比较：假设新象素点位于帧缓冲器中原象素点的前面，那么将新象素点的属性写入帧缓冲器，并将相应的深度(Z值)也写入Z缓冲器；否那么，帧缓冲器和Z缓冲器中的内容不变。本算法的本质是对给定的本算法的本质是对给定的x,y，寻觅最小的，寻觅最小的z(x,y)值。值。算法描画：算法描画：设置帧缓冲器为背景颜色设置帧缓冲器为背景颜色;设置设置Z Z缓冲器为最大缓冲器为最大z z值值;while while 对每一个多边形对每一个多边形 do dobeginbegin while while 对多边形中的每一个元素对多边形中的每一个元素 do do begin begin 计算该象素的深度计算该象素的深度z1(x,y)z1(x,y)/*比较比较z1(x,y)z1(x,y)与存储在与存储在Z Z缓冲器中该位置处的深度缓冲器中该位置处的深度z(x,y)z(x,y)*/if z1(x,y)if z1(x,y)z(x,y)z(x,y)then then 将此多边形的颜色将此多边形的颜色 写入帧缓冲器且写入帧缓冲器且z(x,y)z(x,y)z1(x,y)z1(x,y)end endendendend of algorithmend of algorithm最终，Z缓冲器中保管的是可见面的深度值，而帧缓冲器中保管的是这些外表的对应属性值。采样点(x,y)的深度z1(x,y)的计算：根据平面方程计算设平面方程为：设平面方程为：由于同一条扫描线上的由于同一条扫描线上的y分量为常量，所以沿扫描线上的象素分量为常量，所以沿扫描线上的象素 x1=x+x，y1=y处的深度为：处的深度为：所以，根据扫描线上各点前后相关性，运用增量方法计算Z值是极为方便的。0axbyczd()(0)axbydzcc 那么那么111()axbydzc()axbydaxcc azxc假设假设x=1，那么，那么1azzc层深缓冲法的优缺陷：层深缓冲法的优缺陷：优点：简单，易于处置隐藏面以及显示曲面之间的交贯线。被显示的画面可以恣意复杂，由于图像空间的大小是固定的，最坏情况下，计算量随画面复杂程度线性增长。由于被显示的元素可按恣意顺序写入帧缓冲器和Z缓冲器，所以不需求进展深度排序，节省了排序时间。缺陷：Z缓冲器需求占用大量存储空间。假设被显示的画面经变换和剪取后，Z值在一定范围内变化，那么可采用固定精度的Z缓冲器。本算法结合光照，透明等相关算法后，可产生较佳效果。层深缓冲法每个象素点只能对应一个可见面，不能处置多层深缓冲法每个象素点只能对应一个可见面，不能处置多个面的累计强度值。个面的累计强度值。A A缓冲器法对层深缓冲法进展扩展，使每个单元位置对应缓冲器法对层深缓冲法进展扩展，使每个单元位置对应一个外表链表，可以思索各像素点处多个外表的强度值。一个外表链表，可以思索各像素点处多个外表的强度值。四四A缓冲器法：缓冲器法：根本思想：根本思想：A的含义：的含义：antialiased：反走样；：反走样；accumulation-buffer：累计缓冲器；：累计缓冲器；area-averaged：区域平均。：区域平均。P1P2Id0d0surf1surf2surf3每个单元的深度域和强度域：深度域：存储一个正或负的实数。为正，表示该象素具有独一的外表深度；为负，表示多个面共同对该象素点产生影响。强度域：存储外表的强度信息深度域为正或指针深度域为负。Surf(i)中含有的数据项：中含有的数据项：RGB强度分量强度分量外表的标识名外表的标识名透明性参数透明性参数其他外表绘制参数其他外表绘制参数深度深度覆盖度覆盖度指向下一外表的指针指向下一外表的指针像空间算法多边形区域填充扫描线算法的延伸，扩展到多个外表。在多个外表的重叠区域，采用深度测试确定可见部分。分类：分类：扫描线扫描线z-buffer算法算法区间扫描线算法区间扫描线算法五扫描线算法：五扫描线算法：fzfor(每条扫描线)将扫描线帧缓存fbuffer中的值置为背风光；将扫描线zbuffer的值置为最小值；for(每个多边形)求出该多边形与当前扫描线相交区间；for(区间中的各个像素)if(多边形在该点处的Z值大于zbuffer的值)zbuffer在该处的值=多边形在该处的Z值；fbuffer在该处的值=多边形在该处的亮度值；用fbuffer的内容显示当前扫描线；S1S2多边形表扫描线z-buffer算法：根本思想：判别与各条扫描线相交的一切外表的可见性，记算各重叠外表的深度以找出间隔察看平面最近的外表，将其相应属性写入刷新缓冲器。A1扫描线算法原理图扫描线算法原理图0 0 x xy y扫描线扫描线2 2A A2 2A A3 3B B1 1B B2 2B B3 3B B4 4扫描线扫描线1 1扫描线扫描线3 3C C1 1C C2 2C C3 3C C4 4A AB BC C区间扫描线算法：n 扫描线与多个多边形相交于扫描线与多个多边形相交于a1 an；n ai,ai+1(i=1,2,n)称为一个小区间；称为一个小区间；n 判别可见性准那么：判别可见性准那么：n 假设小区间上没有任何多边形，那么假设小区间上没有任何多边形，那么该小区间为背风光；该小区间为背风光；n 小区间上只需一个多边形，用该多边小区间上只需一个多边形，用该多边形的颜色显示；形的颜色显示；n 小区间上存在两个或两个以上的多边小区间上存在两个或两个以上的多边形时，经过深度测试判别可见性。形时，经过深度测试判别可见性。xya1a2a3a4a5a6算法设计：a1a2a3a4a5a6xz无贯穿情形无贯穿情形a1a2a3a4a5a6xz有贯穿情形有贯穿情形小区间上的深度测试：贯穿情况的处置贯穿情况的处置:扫描线上的分割点不仅应包含扫描线上的分割点不仅应包含各多边形的边与扫描线的交点，而且应包含这各多边形的边与扫描线的交点，而且应包含这些贯穿边境与扫描线的交点。些贯穿边境与扫描线的交点。(b)(b)循环遮挡循环遮挡循环遮挡情况的处置循环遮挡情况的处置:将多边形进展划分以消除循环遮挡。图中绿色为划分边境。区间扫描线算法与层深缓冲法Z-Buffer算法的比较：1对于扫描线对于扫描线Z-Buffer算法而言，比层深缓冲法改良的地算法而言，比层深缓冲法改良的地方将整个绘图窗口内的消隐问题分解到一条条扫描线上处理，方将整个绘图窗口内的消隐问题分解到一条条扫描线上处理，使所需的使所需的Z缓冲器大大减少；缓冲器大大减少；2对于区间扫描线算法而言，层深缓冲法在每个象素处都对于区间扫描线算法而言，层深缓冲法在每个象素处都要计算深度值，进展深度比较，因此在被多个多边形覆盖的象要计算深度值，进展深度比较，因此在被多个多边形覆盖的象素处要进展多次计算。而区间扫描线算法抑制了这一缺陷，使素处要进展多次计算。而区间扫描线算法抑制了这一缺陷，使得在一条扫描线上每个区间只计算一次深度值，并且不需求得在一条扫描线上每个区间只计算一次深度值，并且不需求Z缓冲器。它是把当前扫描线与各多边形在投影平面的投影的交缓冲器。它是把当前扫描线与各多边形在投影平面的投影的交点进展排序后，使扫描线分为假设干子区间。因此，只需在区点进展排序后，使扫描线分为假设干子区间。因此，只需在区间任一点处找出在该处间任一点处找出在该处Z值最大的一个面，这个区间上的每一值最大的一个面，这个区间上的每一个象素就用这个面的颜色来显示。个象素就用这个面的颜色来显示。六深度排序算法画家算法：六深度排序算法画家算法：算法来源：算法来源：画家的作画顺序暗示出所画物体之间的相互遮挡关系。画家的作画顺序暗示出所画物体之间的相互遮挡关系。假设场景中任何多边形在深度上均不贯穿或循环遮挡，假设场景中任何多边形在深度上均不贯穿或循环遮挡，那么各多边形的优先级顺序可完全确定。那么各多边形的优先级顺序可完全确定。根本思想：先将场景中的物体按其距察看点的远近进展根本思想：先将场景中的物体按其距察看点的远近进展排序，然后按照从表头到表尾的顺序逐个绘制物体。排序，然后按照从表头到表尾的顺序逐个绘制物体。算法设计：算法设计：将多边形按深度进展排序：距视点近的优将多边形按深度进展排序：距视点近的优先级高，距视点远的优先级低。先级高，距视点远的优先级低。由优先级低的多边形开场逐个对多边形进由优先级低的多边形开场逐个对多边形进展扫描转换。展扫描转换。其中的关键是将多边形按深度进展排序。其中的关键是将多边形按深度进展排序。S1S2Z1minZ1maxZ2minZ2maxs1s1和和s2s2无深度重叠无深度重叠问题：深度的重叠问题。1无重叠情况：按深度优先级顺序处置各个外表。2有重叠情况时，对与A平面重叠的外表B分别作如下测试：1两外表在两外表在xoy平面上投影的包围矩形无重叠；平面上投影的包围矩形无重叠；2相对于察看位置，面相对于察看位置，面A完全位于重叠外表完全位于重叠外表B之后；之后；3相对于察看位置，重叠外表相对于察看位置，重叠外表B完全位于面完全位于面A之前；之前；4两外表在察看平面上的投影无重叠；两外表在察看平面上的投影无重叠；*结论：只需有一个条件为真，那么A和B无须重新排序。1 2 yxABA和B在xoy平面上投影的包围盒无重叠xzABA完全位于重叠外表B之后3 xAB重叠外表B完全位于A之前zxABA、B、C之间的遮挡关系zC4两外表在察看平面上的投影无重叠假设不属于上面四类，那么必需重新排序。假设不属于上面四类，那么必需重新排序。关键问题：如何对场景中的物体按深度远近排序，建立深度优先级表？一种针对多边形的排序算法：假定在左手察看坐标系XYZ中，投影方向是Z轴的负向，因此Z坐标大距察看者近。记Zmin(P)Zmax(P)分别为多边形P的各个顶点Z坐标的最小值和最大值，算法步骤如下：Step 1:将场景中一切多边形存入一个线性表链表或数组，将场景中一切多边形存入一个线性表链表或数组，记为记为L;Step 2:假设假设L中仅有一个多边形，算法终了；否那么根据每个中仅有一个多边形，算法终了；否那么根据每个多边形的多边形的Zmin对它们预排序。无妨假定多边形对它们预排序。无妨假定多边形P落在表首，即落在表首，即Zmin(P)为最小。再记为最小。再记Q为为L P(表中其他多边形中恣意一表中其他多边形中恣意一个；个；Step 3:判别判别P,Q之间的关系，有如下二种：之间的关系，有如下二种：step 3.1:对一切的对一切的Q，有，有Zmax(P)Zmin(Q)，需进，需进一步判别：一步判别：step 3.2.1 假设假设P,Q投影投影P,Q的包围盒不相交，那么的包围盒不相交，那么P,Q在表中的次序不重要，令在表中的次序不重要，令L=L P，前往前往step 2；否那么进；否那么进展下一步。展下一步。step 3.2.2 假设假设P的一切顶点位于的一切顶点位于Q所在平面的不可见的一所在平面的不可见的一侧，那么侧，那么P,Q关系正确，令关系正确，令L=L P，前往，前往step 2；否那么进；否那么进展下一步。展下一步。step 3.2.3 假设假设Q 的一切顶点位于的一切顶点位于P所在平面的可见的一所在平面的可见的一侧，那么侧，那么P,Q关系正确，令关系正确，令L=L P，前往前往step 2；否那么进；否那么进展下一步。展下一步。step 3.2.4 对对P,Q投影投影P,Q求交，假设求交，假设P,Q不相交，那么不相交，那么P,Q在表中的次序不重要，令在表中的次序不重要，令L=L P，前往，前往step 2；否那么；否那么在它们所相交的区域中任取一点，计算在它们所相交的区域中任取一点，计算 P,Q在该点的深度值，在该点的深度值，假设假设P的深度小，那么的深度小，那么P,Q关系正确，令关系正确，令L=L P，前往，前往step 2；否那么交换；否那么交换P,Q，前往，前往step 3.画家算法的优点是简单、容易实现。缺陷是不能处置相互交叉的面，由于此时深度优先级表中面的顺序能够出错。处理问题的方法是把相关的面进一步分割。七区域细分算法：七区域细分算法：根本思想：利用区域延续性，将整个察看范围细分为根本思想：利用区域延续性，将整个察看范围细分为越来越小的矩形单元，直至每个单元仅包含单个可见越来越小的矩形单元，直至每个单元仅包含单个可见外表的投影或不含任何外表。外表的投影或不含任何外表。多边形外表的投影与察看区域之间的关系察看区域察看区域察看区域察看区域(1)包围外表(2)重叠外表(3)内含外表(4)分别外表一个外表与细分后的察看区域的关系有四种：一个外表与细分后的察看区域的关系有四种：假设满足以下三个条件中的恣意一个，那么不用再假设满足以下三个条件中的恣意一个，那么不用再对区域进展细分：对区域进展细分：条件一：该区域没有内含、重叠或包围外表一切外表均条件一：该区域没有内含、重叠或包围外表一切外表均为区域的分别外表；为区域的分别外表；条件二：该区域只需一个内含外表、重叠外表或包围外表；条件二：该区域只需一个内含外表、重叠外表或包围外表；条件三：该区域有一个在其边境内遮挡了其他一切外表的条件三：该区域有一个在其边境内遮挡了其他一切外表的包围外表；包围外表；(a)(b)xz围绕多边形相交多边形被包含多边形xz围绕多边形相交多边形被包含多边形条件三的可见性测试：条件三的可见性测试：1将外表根据它们离察看平面的间隔进展排序，假设某包围平将外表根据它们离察看平面的间隔进展排序，假设某包围平面间隔察看平面的最大深度小于该区域内其他一切外表的最小深面间隔察看平面的最大深度小于该区域内其他一切外表的最小深度，那么满足条件三。度，那么满足条件三。2利用平面方程计算一切包围、重叠、内含外表上区域四个顶利用平面方程计算一切包围、重叠、内含外表上区域四个顶点的深度值，假设某包围外表的深度值小于其他一切外表，那么点的深度值，假设某包围外表的深度值小于其他一切外表，那么满足条件三。满足条件三。xyz投影线投影平面八光线投射算法：八光线投射算法：算法原理：调查由视点出发穿过察看屏幕的一象素而算法原理：调查由视点出发穿过察看屏幕的一象素而射入场景的一条射线，那么可确定出场景中与该射线射入场景的一条射线，那么可确定出场景中与该射线相交的物体。在计算出光线与物体外表的交点之后，相交的物体。在计算出光线与物体外表的交点之后，离象素最近的交点的所在面的颜色即为该象素的颜色；离象素最近的交点的所在面的颜色即为该象素的颜色；假设没有交点，阐明没有多边形的投影覆盖此象素，假设没有交点，阐明没有多边形的投影覆盖此象素，用背风光显示它即可。用背风光显示它即可。算法步骤：1.经过视点和投影平面显示屏幕上的一切象素点作一入射线，构成投影线。2.将任一投影线与场景中的一切多边形求交。3.假设有交点，那么将一切交点按z值的大小进展排序，取出最近交点所属多边形的颜色；假设没有交点，那么取出背景的颜色。4.将该射线穿过的象素点置为取出的颜色。算法描画：For 屏幕上的每一象素屏幕上的每一象素 构成经过该屏幕象素构成经过该屏幕象素(x,y)的射线；的射线；for场景中的每个物体场景中的每个物体 将射线与该物体求交；将射线与该物体求交；if 存在交点存在交点 以最近的交点所属的颜色显示象素以最近的交点所属的颜色显示象素(x,y)else 以背风光显示象素以背风光显示象素(x,y)光线投射算法与光线投射算法与Z Z缓冲器算法的比较：仅仅是内外循环缓冲器算法的比较：仅仅是内外循环颠倒了一下顺序，所以它们的算法复杂度类似。区别在颠倒了一下顺序，所以它们的算法复杂度类似。区别在于光线投射算法不需求于光线投射算法不需求Z Z缓冲器。缓冲器。The End!