可见面判别算法

1、Computer Graphics电子科技大学计算机学院电子科技大学计算机学院 Designed by Lgs .UESTCCHP9 visible surface detectionnvisible surface detectionnAlgorithm typen表面定向理论n后向面消除法（back-faces method）n深度缓冲法（depth-buffer method）nA缓冲器算法（A-buffer method）n扫描线算法（scan-line method）n深度排序算法（depth-sorting method） Designed by Lgs .UESTCn消隐的考虑：

2、n用计算机生成三维形体的真实图形，是计算机图形学研究的重要内容之一。在使用显示设备描绘三维图形时，必须把三维信息作某种投影变换，在二显示表面上绘制出来。n由于投影变换失去了深度信息，往往导致图形的二义性：n要消除二义性，必须在绘制时隐藏实际不可见的线和面，即消隐。经过消隐的投影图称为物体的真实图形。CHP9 visible surface detection Designed by Lgs .UESTCn不同消隐算法考虑的因素n速度问题实时模拟，如飞行模拟n真实度问题计算机动画，有连续色调，能产生阴影、透明、表面纹理及反射、折射等视觉效果n在进行消隐算法的设计时，应在计算速度和图形细节之间进行

3、权衡，同一种算法无法兼顾CHP9 visible surface detection Designed by Lgs .UESTCn消隐算法的实现空间（两种方法）n形体空间法(object-space method)n直接对形体定义进行处理（把形体和形体的某些部分彼此比较，以确定哪些表面和线作为一个整体是不可见的）n图像空间法(image-space method)n对形体投影图像进行处理（对投影平面上的每一个象素位置逐点检测其可见性） CHP9 visible surface detection Designed by Lgs .UESTCdifference Designed by Lgs

4、 .UESTCnIdea（物空间算法物空间算法）n表面法矢量表面法矢量指向表面外部法线方向指向表面外部法线方向n视线矢量视线矢量物体表面任一点指向物体表面任一点指向视点的方向视点的方向n视角视角法矢量和视线矢量的夹角。法矢量和视线矢量的夹角。nwuv p1p2p2p3p4表面定向理论与定向法表面定向理论与定向法 Designed by Lgs .UESTCn判断原则：判断原则：n计算方法计算方法n计算计算sign（cos ）invisiblevisible)180,90()90, 0(000表面定向理论与定向法表面定向理论与定向法nwuv p1p2p2p3p4 Designed by Lgs

5、.UESTC13121),(cos|ppvppupwzwywxpwvunnwnw计算公式：计算公式：表面定向理论与定向法表面定向理论与定向法 Designed by Lgs .UESTCfacesbackinvisiblethendczbyaxifzyxpoviewdczbyax_0_) , , ( :int0后向面后向面(back faces)消除法（消除法（物空间算法物空间算法） Designed by Lgs .UESTCnEg: 左手系，左手系，view directionZ_axisXZYZvN(A,B,C)容易得知：容易得知：If C0back faces invisibleEls

6、e visible所谓的所谓的back face取决于取决于观察的方向和观察系统观察的方向和观察系统的坐标系的坐标系(右手和左手右手和左手)后向面后向面(back faces)消除法消除法 Designed by Lgs .UESTCnIDEA: Depth-buffer method 像空间算法像空间算法深度缓冲器算法（深度缓冲器算法（Z-Buffer）XvZvYvview direction(x,y)s1s2s3n如图，如图，s1平面平面距离投影平面距离投影平面最近，所以投最近，所以投影点（影点（x，y）将保存将保存s1平面平面上相应点的属上相应点的属性信息。性信息。 Designed b

7、y Lgs .UESTCnIDEA: Depth-buffer methodn刷新缓冲器用来存储图像空间中每一个象素的属性，刷新缓冲器用来存储图像空间中每一个象素的属性，Z缓冲缓冲器是用来存储图像空间中每一个可见象素相应的深度器是用来存储图像空间中每一个可见象素相应的深度(或或Z坐标坐标)，是一个独立的深度缓冲器。，是一个独立的深度缓冲器。n计算将要写入刷新缓冲器象素的深度计算将要写入刷新缓冲器象素的深度(或或Z值值)，并与已存储，并与已存储在在Z缓冲器中该象素的原来深度进行比较缓冲器中该象素的原来深度进行比较 ：若新象素点位于：若新象素点位于刷新缓冲器中原象素点的前面，则将新象素点的属性写入

8、刷新缓冲器中原象素点的前面，则将新象素点的属性写入刷新缓冲器，并将相应的深度刷新缓冲器，并将相应的深度(Z值值)也写入也写入Z缓冲器；否则，缓冲器；否则，刷新缓冲器和刷新缓冲器和Z缓冲器中的内容不变。缓冲器中的内容不变。n本算法的本算法的。深度缓冲器算法（深度缓冲器算法（Z-Buffer） Designed by Lgs .UESTClAlgorithm description：设置刷新缓冲器为背景颜色设置刷新缓冲器为背景颜色(或光强度或光强度)设置设置Z缓冲器为最大缓冲器为最大Z值（深度最深，规范化后为值（深度最深，规范化后为1）while 对每一个多边形对每一个多边形 dobegin wh

9、ile 对多边形中的每一个元素对多边形中的每一个元素 do begin 计算该象素的深度计算该象素的深度z(x,y)深度缓冲器算法（深度缓冲器算法（Z-Buffer） Designed by Lgs .UESTC/*比较比较z(x,y)与存储在与存储在Z缓冲其中该位置处的深度缓冲其中该位置处的深度Z(x,y)*/ if z(x,y)Z(x,y) then 将此多边形的颜色将此多边形的颜色(或光强度或光强度) 写入帧缓冲器且写入帧缓冲器且Z(x,y)z(x,y) endendend of algorithm*最终，最终，Z-buffer 中保存的是可见面的深度值，而中保存的是可见面的深度值，而R

10、efresh-Buffer中保存的是这些表面的对应属性值。中保存的是这些表面的对应属性值。深度缓冲器算法（深度缓冲器算法（Z-Buffer） Designed by Lgs .UESTCnProblem:计算采样点计算采样点(x,y)的深度的深度z(x,y) n设平面方程为：设平面方程为：ax+by+cz+d=0 则则 z=-(ax+by+d)/c c0由于同一条扫描线上的由于同一条扫描线上的y分量为常量，所以沿扫描线上的象素分量为常量，所以沿扫描线上的象素 x1=x+x，y1=y处的深度为：处的深度为：z1 =-(ax1+by+d)/c =-(ax+by+d)/c-(a/c)x =z-(a/

11、c)x若若x=1，则，则 z=z-a/c深度缓冲器算法（深度缓冲器算法（Z-Buffer） Designed by Lgs .UESTCn优点：优点：简单，易于处理隐藏面以及显示曲面之间的交简单，易于处理隐藏面以及显示曲面之间的交贯线。被显示的画面可以任意复杂，因为图像空间的大贯线。被显示的画面可以任意复杂，因为图像空间的大小是固定的，最坏情况下，计算量随画面复杂程度线性小是固定的，最坏情况下，计算量随画面复杂程度线性增长。由于被显示的元素可按任意顺序写入帧缓冲器和增长。由于被显示的元素可按任意顺序写入帧缓冲器和Z缓冲器，所以不需要进行深度排序，节省了排序时间。缓冲器，所以不需要进行深度排序，

12、节省了排序时间。n缺点：缺点：Z缓冲器需要占用大量存储空间。若被显示的画缓冲器需要占用大量存储空间。若被显示的画面经变换和剪取后，面经变换和剪取后，Z值在一定范围内变化，则可采用固值在一定范围内变化，则可采用固定精度的定精度的Z缓冲器。缓冲器。深度缓冲器算法（深度缓冲器算法（Z-Buffer） Designed by Lgs .UESTCnIdea（像空间算法像空间算法）nz-buffer每个象素点只能对应一个可见面，只能处理每个象素点只能对应一个可见面，只能处理不透明表面。不能处理多个面的累计强度值。不透明表面。不能处理多个面的累计强度值。n对对z-buffer进行扩展，使每个单元位置对应一

13、个表面进行扩展，使每个单元位置对应一个表面链表。链表。nA的含义：的含义：nantialiased：反走样；（主要应用于物体边界）：反走样；（主要应用于物体边界）naccumulation-buffer：累计缓冲器；：累计缓冲器；narea-averaged：区域平均；：区域平均；A缓冲器法缓冲器法 Designed by Lgs .UESTCn单元的深度域和强度域：单元的深度域和强度域：n深度域：存储一个正或负的实数。为正，表示该象素具有唯一的深度域：存储一个正或负的实数。为正，表示该象素具有唯一的表面深度；为负，表示多个面共同对该象素点产生影响。表面深度；为负，表示多个面共同对该象素点产生

14、影响。n强度域：存储表面的强度信息（深度域为正）或指针（深度域为强度域：存储表面的强度信息（深度域为正）或指针（深度域为负）。负）。A缓冲器法缓冲器法Id0d0surf1surf2surf3 Designed by Lgs .UESTCnSurf(i)中含有的数据项：中含有的数据项：nRGB强度分量强度分量n表面的标识名表面的标识名n透明性参数透明性参数n其他表面绘制参数其他表面绘制参数n深度深度n覆盖度覆盖度n指向下一表面的指针指向下一表面的指针A缓冲器法缓冲器法 Designed by Lgs .UESTC扫描线算法（扫描线算法（像空间算法像空间算法）nidea：判别与各条扫：判别与各条扫

15、描线相交的所有表面描线相交的所有表面的可见性，记算各重的可见性，记算各重叠表面的深度以找出叠表面的深度以找出距离观察平面最近的距离观察平面最近的表面，将其相应属性表面，将其相应属性写入刷新缓冲器。写入刷新缓冲器。n避免对被遮挡区域的避免对被遮挡区域的采样是进一步提高扫采样是进一步提高扫描线算法计算效率的描线算法计算效率的关键。关键。扫描线算法原理图扫描线算法原理图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 Designed b

16、y Lgs .UESTC扫描线算法扫描线算法nAlgorithm:n数据结构：三张表数据结构：三张表n边表边表:保存线段端点坐标、线段斜率的倒数、和指向多边形表中对应保存线段端点坐标、线段斜率的倒数、和指向多边形表中对应多边形的指针；多边形的指针；n多边形表：包含各多边形面的平面方程系数、表面属性信息以及指多边形表：包含各多边形面的平面方程系数、表面属性信息以及指向边表的指针；向边表的指针；n有效边表：也称活化边表，包含与当前扫描线相交的边，并将这些有效边表：也称活化边表，包含与当前扫描线相交的边，并将这些边按边按x升序排列；升序排列；n面标志面标志Flag：on（开始，左边界）或者（开始，左

17、边界）或者off（结束，右边界）；（结束，右边界）；n算法关键：分割子区间，确定子区间上的唯一可见面。算法关键：分割子区间，确定子区间上的唯一可见面。n特殊情形：贯穿情形、循环遮挡情形。特殊情形：贯穿情形、循环遮挡情形。 Designed by Lgs .UESTC扫描线算法扫描线算法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 Designed by Lgs .UESTC扫描线算法扫描线算法

18、n贯穿情况的处理贯穿情况的处理: :n为了使算法能处理为了使算法能处理互相贯互相贯穿的多边形穿的多边形，扫描线上的，扫描线上的分割点不仅应包含各多边分割点不仅应包含各多边形的边与扫描线的交点，形的边与扫描线的交点，而且应包含这些贯穿边界而且应包含这些贯穿边界与扫描线的交点与扫描线的交点( (图中红色图中红色为贯穿边界为贯穿边界) )(a)(a)贯穿贯穿 Designed by Lgs .UESTC扫描线算法扫描线算法n循环遮挡情况的处理循环遮挡情况的处理:n将多边形进行划分以消除将多边形进行划分以消除循环遮挡循环遮挡 n图中红色为划分边界图中红色为划分边界(b)(b)循环遮挡循环遮挡 Desi

19、gned by Lgs .UESTC深度排序算法（画家算法）深度排序算法（画家算法）nDepth-sorting method, 同时运用物空间和象空间操作。同时运用物空间和象空间操作。nIdea：若场景中任何多边形在深度上均不贯穿或循环遮挡，则各多：若场景中任何多边形在深度上均不贯穿或循环遮挡，则各多边形的优先级顺序可完全确定。边形的优先级顺序可完全确定。 n深度排序算法深度排序算法：n将多边形按深度进行排序：距视点近的优先级高，距视点远的优先级低。将多边形按深度进行排序：距视点近的优先级高，距视点远的优先级低。n由优先级低的多边形开始逐个对多边形进行扫描转换。由优先级低的多边形开始逐个对多边形进行扫描转换。n其中的关键是将多边形按深度进行排序！其中的关键是将多边形按深度进行排序！ Designed by Lgs .UESTC深度排序算法（画家算法）深度排序算法（画家算法）n深度的重叠问题深度的重叠问题n无重叠情况：按深度无重叠情况：按深度优先级顺序处理各个优先级顺序处理各个表面表面S1S2Z1minZ1maxZ2minZ2maxs1s1和和s2s2无深度重叠无深度重叠 Designed by Lgs .UESTC深度排序算法（画家算法）深度排序算法（画家算法） Design