计算机图形学消隐算法.ppt

《计算机图形学消隐算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、消隐算法主要内容:一、概述二、消隐的基本技术三、凸多面体消除隐藏线四、消除隐藏面用计算机生成三维形体的真实图形，是计算机图形学研究的重要内容之一。在使用显示设备描绘三维图形时，必须把三维信息作某种投影变换，在二维显示表面上绘制出来。由于投影变换失去了深度信息，往往导致图形的二义性：要消除二义性，必须在绘制时消隐实际不可见得线和面，即消隐。经过消隐的投影图称为物体的真实图形。一、概述消隐不仅与消隐对象有关，还与观察者的位置有关。如图所示，由于视点的位置不同，物体的可见部分也不同：消隐与观察者的位置关

2、系按消隐的对象分类线消隐（Hidden-line）面消隐（Hidden-surface）按消隐空间分类物体空间消隐算法图像空间消隐算法线消隐（Hidden-line）消隐对象是物体上不可见的线，一般用于线框图。当用笔式绘图仪或其它画线设备绘制图形时，主要使用这种算法。面消隐（Hidden-surface）消隐对象是物体上不可见的面，一般用于填色图。当用光栅扫描显示器绘制图形时，主要使用这种算法。早期图形显示器是用线条表示图形，消隐主要是消隐线问题。使用光栅显示器后，物体可用连续变化的色调来描述，消

3、隐算法的研究渐渐转向消隐面的问题。第一种是物空间算法。它以三维场景中的物体对像作为处理单元的，在所有的对像之间进行比较，除去完全不可见的的物体和物体上不可见的部分。常用于线框表示立体的线隐藏，也用于面隐藏。for(场景中的每一个物体){将其与场景中的其它物体比较，确定其表面的可见部分；显示该物体表面的可见部分；}隐藏线（面）的消除的两种基本算法特点是：算法可以达到相当高的精度。第二种是像空间算法。它以构成图形的每一个像素为处理单元的，确定场景中哪些表面的像素相对于观察点而言是可见的，用该表面的颜色

4、填充该像素。常用于隐藏面。特点是：算法精度低，只能达到屏幕精度为止，但速度往往更高。其算法是对每一个像素:在和投影点到像素的连线相交的表面中找到离观察点最近的表面用该表面上交点处的颜色填充该像素。for(窗口内的每一个像素){确定距视点最近的物体，以该物体表面的颜色来显示像素}算法复杂度假设场景中有k个物体，平均每个物体表面由h个多边形构成，显示区域中有mxn个像素，则：第一种算法的复杂度为：O((kh)×(kh))第二种算法的复杂度为：O(mnkh)9物空间消隐算法:需对物体表面的h个多边形中的

5、每个面与其余h-1个面进行比较，精确地求出物体上每个棱边或每个面的遮挡关系。算法的计算量正比于h2，即算法复杂度为：O((h)2)。则：k个物体的算法复杂度为：O((kh)2)。10象空间消隐算法：这类算法对屏幕上的每个象素进行判断，以决定物体上哪个多边形在该象素点上是可见的。若屏幕上有m×n个象素点，每个物体表面上有h个多边形，则该类消隐算法计算量正比于mnh。则：k个物体的算法复杂度为：O(mnkh)。各种消隐算法均采用一定形式的几何排序。通过排序，可搜查出位置上靠近观察者的几何元素，确定几何

6、元素之间在位置上的遮挡关系，解决消隐计算的主要问题。各种算法都有各自的排序方法和排序次序。排序次序影响算法的效率。算法排序二、消隐基本技术为了提高消隐算法的效率，各种消隐算法常采用一些有效的消隐基本算法。利用连贯性将透视投影转换成平行投影包围盒技术背面剔除空间分割技术物体分层表示物体连贯性面的连贯性区域连贯性扫描线的连贯性深度连贯性利用连贯性连贯性是指从一个事物到另一个事物，其属性值(如颜色值、空间位置)通常是平缓过渡的性质。例如：棱边的连贯性是指：棱边的可见性在它与其他棱边相交时才发生变换；面的

7、连贯性是指：如果面的一部分是可见的，则一般情况下整个面都是可见的。物体连贯性若物体A与物体B是完全分离的，消隐时只需要比较两物体之间的遮挡关系即可，不需要对它们的表面多边形逐一进行测试；面的连贯性一张面内的各种属性值一般是缓慢变化的，可采用增量的形式对其进行计算；区域连贯性一个区域一般指屏幕上一组相邻的象素，他们通常为同一个可见面所占据，可见性相同；扫描线的连贯性在相邻两条扫描线上，可见面的分布情况相似；深度连贯性同一表面上的相邻部分深度是相近的，而占据屏幕上同一区域的不同表面的深度不同，这样只需

8、取其上一点计算出深度值，比较该深度值便能得出结果；包围盒技术一个形体的包围盒指的是包围它的简单形体。比如，2D的矩形，3D的立方块、长方体、球等。目的：避免盲目的求交测试；各物体间的比较等。一个好的包围盒要具有两个条件：包围和充分紧密包围着形体；对其的测试比较简单。例：矩形包围盒及长方体包围盒提高算法效率包围盒不相交，线段和多边形也不相交，线段完全可见，无需就线段和多边形的遮挡关系进行进一步判断。可推广到面与面的遮挡快速判断。例如：两个空间多边形A、B在投影平面上的投影分别为A’，