也欢迎⼤家转载本篇⽂章。分享知识，造福⼈民，实现我们中华民族伟⼤复兴！
【摘 要 】本⽂就 ⽬前现有⾯消隐算法进⾏ 了分类，对每类算法特 点进⾏ 了总结。从每种 算法本 ⾝的特点 、消隐空间、排序效率和对场景的限制这⼏⽅⾯ ．重点分析⽐较 了⼏种常⽤的⾯消隐算法。 1 引⾔
消隐(Hidden Surface Removal)是在⼀定观察⽅向下消除不可见的线和⾯。有时也称为可见性测试。虽然各种消隐算法在可见性测试和不可见⾯消除⽅法上区别不⼤．但这些消隐⽅法有时还可以⼀起被统称为不可见⾯的消除．简称消隐。在三维造型技术、真实感图形的显⽰、虑拟场景的显⽰、以及在地形．地图的绘制中．消隐都起到⾄关重要的作⽤。所以研究和实现消隐算法，并根据场景的复杂度和各个不同应⽤领域的场景来提⾼消隐算法的速度是很有必要的，它对整个三维图形显⽰．真实感图形的显⽰以及各种地形地貌图形的显⽰是很有意义的。
就⽬前研究出的⾯消隐算法，按照它们对消隐算法加速的⽅法不同可分为两类：
⼀类是致⼒于消隐⽅法的研究。
(1)现有的消隐算法研究。现有的常⽤的⼏种⾯消隐算法主要有：Z—buffer算法、扫描线算法、画家算法、BSP树算法等，其主要区别在于它们消隐空间不同、可见⾯测试⽅法和不可见消除⽅法不同，故它们所适⽤的范围也不同。本⽂将在第三部分从每种算法本⾝的特点、消隐空间、排序效率和对场景的限制上对这⼏种消隐算法来分析和⽐较。
(2)由于消隐算法不同，它们适⽤的场景类型和复杂度也不同，所以有⼀些专门⽤于针对地形、地图的绘制 、凸多边体消隐、复杂形体消隐、对某⼀种形体表⽰的场景的消隐 、对曲⾯消隐等的算法研究。
(3)研究新的消隐⽅法或⽤不同⽅法对已有算法改进来提⾼消隐速度．如树结构的消隐算法、改进的扫描线算法、BSP树法在辐射度显⽰中的应⽤、BSP树法加⼊到层次遮挡图(HOM)算法、BSP树法结合Image cache(Sprite)算法等．可以在不同程度的提⾼图形绘制效率。对于BSP树加⼊到其它算法中可提⾼其它算法效率，本⽂也将在第三部分进⾏⽐较。
另⼀类是致⼒于减少视域中的待处理的景物⾯⽚数，来达到加速消隐过程的⽬的。硬件Z—buffer算法是⽬前最为常⽤的实时图形绘制算法，尽管其线性复杂度为O(N)(N为⾯⽚数)，但该算法由于不考虑景物的空间连贯性，需逐⼀绘制景物⾯⽚⽽不管它是否隐藏。 因⽽，对⾼度复杂的场景，硬件Z—buffer算法仍难以达到实时。解决这⼀个问题的关键是减少复杂场景中需实时绘制的景物⾯⽚数N。
⽽减少视域中的待处理⾯⽚数⽬前有两种途径：
(1)基于空间连贯性的快速消隐算法。这种算法并不简化场景⼏何，⽽是充分利⽤景物空间、图象空间和时间域上的可见性和不可见性连贯性来剔除被遮挡的景物⾯⽚。层次遮挡图算法和层次Z—buffer算法是这类算法的典型代表。这两个算法均将景物空间组织成层次结构，并把⾯⽚的可见性计算分解为深度排序和在屏幕⼘的重叠测试两个过程。算法引⼊深度z锥来实现快速的保守排序，⽽图象锥则⽤来加速⾯⽚的重叠测试，这两个层次结构的引⼊使得快速剔除不可见⾯成为可能．从⽽极⼤地降低了后续硬件z—buffer算法的绘制复杂度。更进⼀步，时问域上可见性连贯性的使⽤保证了Z锥和图象锥具有⼀个极好的初始条件，为快速绘制提供了重要保障。由于着眼于开发不可见景物的空间连贯性，这类算法对⾼遮挡率的场景⾮常有效．但对遮挡复杂性不⾼的复杂场景却毫⽆优势，仍⽆法达到实时。
(2)基于层次细节的图形绘制技术 。这种算法根据视觉特性．对离视点较远的景物进⾏⼏何简化，从⽽达到降低场景复杂性的⽬的．或利⽤其它⼏何⽅法对整个场景⾯⽚进⾏简化，来减少场景⾯⽚数。这种⽅法⼤⼤的减少了场景的复杂度．提⾼了绘制场景的速度，但对⾼度复杂的场景．经过⼏何简化后的场景可能仍⽆法实时绘制．直到九⼗年代中期发展起来的纹理简化技术较好地解决了这类问题。其典型代表是Shade的图象缓存(Image Cache)技术 ，该算法结合⼏何简化和基于图象的绘制技术的优点。算法⾸先将场景组织成⼀棵BSP树。漫游时，算法⾃动地决定BSP树中各个结点中的景物是否满⾜纹理简化的误差要求，若满⾜．则取图象缓存中对应图象作为纹理．将其映射到⼀空间四边形表⾯ ：
来取代结点中的⼏何来绘制域⾯：否则，直接采⽤⼏何来绘制。显然，这种动态图象简化技术⼤⼤减低了场景的复杂性．从⽽提⾼了图形的绘制效率。但由于该算法采⽤从后向前的绘制⽅式，不能利⽤前述的空问不可见性连贯性来加速消隐过程。为此，郑⽂庭，鲍虎军等结合了层次遮挡图和图象缓存算法．提出了基于时空连贯性和⼏何简化技术的复杂场景快速消隐绘制算法⼝ ，可以适合对各种复杂场景的实时绘制．提⾼了图形绘制效率，加速了消隐过程。
美国标准普尔公司
2．研究消隐算法的⽅法
2．1从消隐空间来分析：对消隐算法消隐空间的分析是对消隐算法的效率的分析的⼀个重要⽅⾯。因为这样可以对消隐算法进⾏归类，并为提⾼消隐算法的效率打好基础。根据消隐所在的空间分为消隐算法可以分为三⼤类：
(a)物体空间法(光线投射Roberts)：物体空问是⽤户来定义三维形体的三维空间．即所说的世界坐标系空间。它是三维形体还没有被投影到⼆维空间内所在的空间。物体空间法就是利⽤三维环境信息或三维视图(主要使⽤三维观察坐标，有时也使⽤三维世界坐标)来消除隐藏⾯．即根据空间中各物体三维模型的⼏何关系，来判断哪些表⾯可见，哪些表⾯不可见。
政治权利是什么
(b)图象空间法(Z—buffer、扫描线、warnock)：图象空间是把三维图形投影到的⼆维空间，即我们所说的屏幕空间。图象空间法是基于物体三维模型的⼆维显⽰图形(使⽤⼆维显⽰坐标)来确定物体或表
⾯与观察点的远近关系，从⽽判断哪些表⾯遮挡了其它表⾯。
(c)物体空间和图像空间的消隐算法(画家算法)：在物体空间中预先汁算⾯的可见性优先级，再在图像空间中⽣成消隐图。从理论上讲，对象空间⽅法即为⼀个对象必须和空间中其他对象进⾏⽐较，以确定其是否可见。若画⾯中有n个对象，那么，⽐较操作的计算量为n 次。图像空间⽅法则是将每个对象的投影分解为像素，像素之间进⾏⽐较。若每个对象投影后含有N个像素．则⽐较计算量为N~n次，N虽然很⼤，但像素之间⽐较简单。实⽤的消隐算法通常将对象空间⽅法和图像空间⽅法结合起来使⽤。⾸先．使⽤空间对象⽅法删除对象中⼀部分不可见的⾯；其次，对剩余的⾯⽤图像空问⽅法进⾏⽐较计算。这样才能提⾼消隐算法的效率。
2．2要研究⼀种消隐算法．就要知道每种算法的基本组成元素．这样才能更透彻的理解这种算法，去研究这种算法。对于每种消隐算法，可以从它们共同拥有的五个⽅⾯着⼿来研究。因为每⼀个消隐算法可以看成是以下⼀个五元组的集合．即：
HA=(I，O，D，P，S)，其中：
HA为⼀个消隐算法
I为要进⾏消隐处理的三维对象的集合：
O为经过消隐处理的⼆维对象的集合：
D为进⾏消隐处理时所采⽤的数据结构；西乡县卫生局
P为进⾏消隐处理所需基本操作过程的集合，主要包括：分类、排序，三维坐标变换，透视投影变换，基本图形元素间的求交计算，两个区域重叠判断，点与区域的包含测试，⾯的朝向测试
S为消隐策略，即规定P中各基本操作过程被采⽤的先后次序。
消隐算法不同，主要在于D，P，S，对于D(消隐处理时所采⽤的数据结构)，如扫描线算法中的AET、APT可以加速扫描速度，BSP树算法就是利⽤了⼆叉树来分割和显⽰场景，都是为了加速消隐速度；对于P(分类、排序、包含性测试、可见性测试)，算法不同．⽅法也不同；S(P中各基本操作过程被采⽤的先后次序)，根据不同的应⽤需要，场
景类型来设计。因此，设计消隐算法时应考虑上述五个要素及它们之间的相互关系，在改进这五个基本要素⽅⾯着⼿去提⾼算法的速度．并在应⽤领域也要考虑这五个基本要素去着⼿。
3．⼏种常⽤⾯消隐算法的⽐较
消隐的对象是三维形体，⽽消隐的结果不只与三维形体的形状有关，还有观察⽅向有关。消隐的效率
有很多因素决定．除了算法本⾝外，还有：场景的复杂度、要显⽰物体的类型、可⽤设备、以及要显⽰画⾯是动态的还是静态的等等。这些因素决定了要选⽤的消隐的算法类型，也决定了这种消隐算法的效率。在设备相同，要显⽰画⾯是静态的情况下，下⾯就⽬前⼏种常⽤的消隐算法：Z—buffer算法，扫描线算法，画家算法，BSP树算法，从不同的场景复杂度、消隐空间、排序效率、对物体类型的限制引 阁这⼏
⽅⾯来进⾏⽐较：
3．1从算法特点来⽐较:
Z—buffer算法像素级上以距离观察者近的物体替代远的物体，物体在屏幕上的出现顺序⽆关紧要，算法简单．以利于硬件实现。单初始值的多样性，有限的复杂度O(N)，N为场景中所含⾯的数⽬．⽆需对场景中的多边形排序，⽽扫描线和画家算法运⽤了稍复杂的排序算法，排序算法⽐起Z-Buffer算法难实现。因此．Z—buffer算法硬件易实现，得到了⼴泛的应⽤。但Z—buffer算法需要⼤量的存贮空间，当画深度复杂度为：s=d，fl=a的物体时浪费时间，z精度的误差性⾼(这时必须要采样点)。它的最⼤缺点是两个缓存数组占⽤的存储单元太多。故改进Z—Buffer算法，只设置⼀个深度缓存变量ZB，帧缓存(CB数组)存放每个像素的颜⾊值，这样可以⼤⼤减少存储单元。也可以⽤⽤扫描线相关性和点相关性来改进。另外，Z—buffer算法速度依赖于场景中多边形⾯⽚数⽬。⽽不是场景中对于观察者可见多边形⾯⽚数⽬。与Z—bufer算法相⽐较。扫描线Z_buffer算法做了两点改进： (1)整个绘图窗⼝内的消隐问题分解到⼀条扫描线上解决，使所需的Z缓冲器⼤⼤减少。
(2)计算深度值时，利⽤了⾯连贯性，只⽤了⼀个加法。但它在每个象素处都计算深度值，进⾏深度⽐较。扫描线算法中．被多个多边形覆盖的象素区处还要进⾏多次计算，计算量仍然很⼤。区间扫描线算法克服了这⼀缺陷，使得在条扫描线上每个区间只计算⼀次深度值，并且不需要z缓冲器。它是把当前扫描线与各多边形在投影平⾯的投影的交点进⾏排序后．使扫描线分为若⼲⼦区间。因此，只要在区间任⼀点处出在该处Z值最⼤的⼀个⾯，这个区间上的每⼀个象素就⽤这个⾯的颜⾊来显⽰。画家算法它的缺点是只能处理互不相交的⾯．⽽且深度优先级表中⾯的顺序可能出错。在两个⾯相交，三个以上的⾯重叠的情形，⽤任何排序⽅法都不能排出正确的序。这时只能把有关的⾯进⾏分割后再排序。⽽且，在画家算法中，深度排序计算量⼤，⽽且排序后，还需再检查相邻的⾯，以确保在深度优先级表中前者在前，后者在后。若遇到多边形相交，或多边形循环重叠的情形，还必须分割多边形，然后进⾏排序，最后再进⾏显⽰。⽽Z—Buffer算法和扫描线算法可避免这个问题。但扫描线算法和Z—buffer算法的缺点是，对于不可见的多边形⾯⽚了同样画出，这样造成了绘制过程中不必要的费时。
因为硬件加速Z—buffer算法太慢，故提出了BSP树算法。BSP树⼀个数据结构，它把空间分成更⼩的部分。只存储多边形⾯⽚在空间的相对位置，这样使得多边形在场景中排序后，你会⼀直从后向前的绘制，这就意味着最⼩z值的多边开最后画。⽤其它⽅式排序多边形时，离视点最近的多边形最后绘出，
⽐如画家算法就是这样．但很少会象BSP树⼀样节省，便利。因为BSP树法中多边形排序是预先处理的，不需花费运⾏时间。BSP树法是画家算法的拓展。但由于画家算法的缺点是对于交叉多边形的情况，这时多边形不会被正确绘出。⽽且多边形排序计算很费时间，算法也⽐较复杂。所以BSP树算法利⽤它的存储结构可以优化多边形的排序过程，故它的排序速度⽐画家算法要快，尤其是复杂度⾼的场景。
另外在BSP树的各层次结点⾥我们可以放置景物的包围盒数据．因⽽可以形成场景的层次包围盒结构，这对加速求交(如光线跟踪算法)和视域裁剪算法很有利。同时．BSP树算法在辐射度的计算中也起着重要的作⽤，把BSP树应⽤到辐射度算法或其它算法中可以达到加速这种算法本⾝，⼀般的辐射度算法中，最坏的情况是与每条光线与场景中相关多边形会被测O(n )．n是树中的⾯⽚数．⽽⽤BSP—tree算法进⾏优化处理后，会减少⼤量运⾏时间．⾄于要减少多少要看树的结构了。
BSP—tree算法的这种效果，也可以引⼊到HOM 算法．Sprite算法中，这样可以对复杂度⾼的场景的绘制减少运⾏时间．加速了消隐过程。⽂中 试验了，对于复杂度为157542个三⾓⾯⽚的场景．在⼀台SGI Octane图形⼯作站，CPU是MIPS R10000处理器． 内存为128M．MIXI图形板，4M纹理内存，经过BSP分割后，有276708个⾯⽚．测试
结果：光纤起偏器
BSP+H0M 0．657秒
BSP+Sprite 0．642秒
BSP+H0M+Sprite 0．581秒
可见，BSP—tree由于它独特的结构，可以在其它算法中起到很好的加速效果。
3．2从消隐空间来⽐较：个人述职报告格式
物体空间算法复杂度依赖于多边形⾯⽚的数⽬，每⼀个多边形都有和其它多边形⽐较，复杂度是n^2(n为多边形⾯⽚数⽬)。
图象空间法：检查图象的每个象素点去检测哪个⾯在这⼀点绘出，复杂度依赖于多边形⾯⽚的数⽬和象素点的个数，因此复杂度是nN，(n 是多边形⾯⽚的个数，N是象素点的个数。)
扫描线算法和Z—buffer算法⼀样，也是图象空间算法，它能⽤z—buffer同样的运⾏时间去产⽣⼀个图像，但扫描线算法在缓冲区中仅⽤了⼀条扫描线的存储量，这也是被容易接受的原因之⼀。扫描线算法是利⽤扫描线相关性和点相关性，根据参考⽂献，扫描线算法实际操作更优，⽽且Z—buffer算法速度更快，它的排序是以线性速度增长的。
画家算法(列表优先算法)，是介于图象空间与物体空间的算法。在⾯集优先的计算与相对于分割平⾯的视点位置有关，⽽⾯⽚优先计算则与视点⽆关，使得⾯集和⾯⽚的优先集的计算是相互独⽴的，这样减少了计算量。
它的排序也可利⽤扫描线相关性和点相关性，但是它在遇到相互交叉多边形时要分割，这样⽐较费时，这与扫描线算法⽐较，这是它的不利之处。画家算法⽅法和扫描线⽅法在复杂场景中效果⽐Z—buffer算法好，z—buffer算法对于复杂度⾼的场景却效果不好。
BSP树建⽴⼀个预先处理过程．只适于特殊场景。它的运⾏时间⽤在对于给定视点⽅向下按优先顺序对多边形遍历的过程．遍历⽐较费时，⽆需重新计算，因为它的预处理是⼀个可视独⽴结构．存储多边形的相对位置，⽐如⼀个多边形．只记录它在其它的多边形的前或后，因此，BSP树和它的预处理都不能进⾏消隐处理，只有遍历可进⾏消
隐处理。场景的特性是⼀系列多边形进⾏⽐较，⽐如多边形P，从多边形集中，观察者位于P的前(后)，那么位于多边形P后(前)的其它多边形不会遮挡它，同样P不会遮挡其它位于它的前(后)的多边形。
BSP的运⾏时间上，它很好的储存了多边形的相对位置，然后运⾏，这样可以节省时间，⽐如，给定多边形P，在树的⼀个结点中，也许遮挡了树中的多边形Q，此时，P是否遮挡多边形集 中其它多边形
Q，则在它的孩⼦结点中。
3．3从排序算法的效率上来⽐较：
z—buffer算法易实现，⽆需对场景中的多边形排序，⽽扫描线和画家算法运⽤了稍复杂的排序算法．排序算法⽐起Z—buffer算法难实现。因此由于Z—buffer算法硬件易实现，得到了⼴泛的应⽤。
根据参考⽂献扫描线对中⾼复杂度场景的排序耗时约为N．画家算法在低复杂度场景排序耗时也为N，树结构排序对于复杂度⾼的场景耗时为N，N为要处理的⾯⽚⽬。
对多边形排序时，按每个多边形顶点的最⼩的图象坐标系中的z值 或对边排序，即⽤两点间的最⼩的Y坐标值来排序。排序是根据所选的对象不同来对⼀系列所要处理的多边形或边进⾏排序，排序效率依赖于所需处理对象的数⽬。对于排序的各种结构，可以减少查、插⼊．归类等的时间，从⽽减少整个消隐算法的运⾏时间。对于⽂献可知 ⼀个排序树，对于复杂度⼩的场景排序时间为logN，对于复杂度⾼的场景，排序列表的的排序耗时也为logN，因此，画家算法对于复杂度⾼的场景，它的排序时间和BSP树对于复杂度⼩的场景的耗时是⼀样的．即，BSP树的速度⽐画家算法快。
但画家算法的深度排序计算量⼤，⽽且排序后，还需再检查相邻的⾯．以确保在深度优先级表中前者在前，后者在后。若遇到多边形相交或多边形循环重叠的情形．还必须分割多边形。⽽Z—Buffer算法和BSP树算法都可以避免这个问题。
edta
3．4从对场景的限制来⽐较：
在画家算法中要求场景中多边形要求是凸多边形：BSP虽然没有场景中的多边形都是是凸多边形，但在分割过程中选择分割⾯时，所选多边形必须是凸多边形；描线算法中除了R0MEY算法中要求所有多边形都是凸多边形、三⾓⾯⽚、不允许有洞，其它扫描线算法都没对场景有限制。
4、总结与展望
本⽂对⽬前现有的⾯消隐算法进⾏了分类，并重点⽐较了⼏种常⽤的⾯消隐算法，这为以后更深⼊地⽐较其它更多消隐算法做好了准备。给我⽼师的⼈⼯智能教程打call！
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议