《计算机图形学》课件第五章.ppt

（2）计算物体的体积简便，只要从八叉树的根结点开始逐个累加标识为“满”的结点的立方体的体积，计算精度取决于八叉树的分割层数，当最下一层的“部分占有”叶结点都算作“满”时，算得的体积最大；反之，如果将这些叶结点都算作“空”时，所求得的体积最小。当然，更合理的算法是引入Montacarlor法，即产生随机数，根据随机数来取一部分“部分占有”的叶结点作为“满”结点。（3）八叉树的数据结构简化了隐藏线隐藏面的消除算法。由于消隐算法的核心是排序，即将待显示物体上的点、线、面按它们离观察点的远近排列次序，离观察点近的元素遮挡远的元素，而物体的八叉树表示中，物体的各元素已按空间位置排列成一定的顺序。同一层次的八叉树结点组成三维空间中可线性分离的丛，因此很容易建立丛的优先级树。例如，在我们所给的编码方式下，当观察点处于图5.28中z轴方向的E点附近时，只要按照0，1，2，3，4，

5，6，7的次序显示各体元，就可获得物体的消隐图。这种消隐算法的时间复杂度与所要显示物体的体元数目n成线性关系O(n)。图5.28八叉树结点编码下的消隐八叉树的缺点有以下几点：

（1）占用存储空间大；

（2）物体的坐标变换代价高。当物体旋转一角度后，整个八叉树需要重新生成。对于平移而言，物体的八叉树结点分割保持不变，但沿平移方向的所有结点都需要重新编码；

（3）与B-rep表示或CSG表示难以统一，而B-rep表示或CSG表示可以转化成八叉树表示。这种单向转换导致八叉树的表示形式难以集成到已有的基于B-rep表示或CSG表示的系统中。4.线性八叉树表示

减少八叉树表示所需的空间存储量的一种有效措施是线性八叉树。线性八叉树表示与八叉树表示类似，唯一的区别是存储方式不同。线性八叉树是用一个可变长度的一维数组存储一棵八叉树，数组中仅存储八叉树的终端结点，即描述一个物体的大大小小的立方体。对于2N×2N×2N的空间分割，每个结点在八叉树中的位置可用一个八进制数表示为（5.153）性质1设P(x，y，z)为空间任一点，其x，y，z的

二进制表示如下：（5.154）则点P对应的线性八叉树结点的编码为{qn－1qn－2…q0}，其中：性质2给定线性八叉树结点的编码{qn－1qn－2…q0}，则对应的子立方体的前下角的坐标为（5.157）式中［·］表示取整，il，jl，kl为ql的二进制表示，即ql=kljlil，l=0，1，…，n－1。例如，对于Q=51，有：q0=1=(001)2，q1=5=(101)2，

则x=(11)2=3，y=(00)2=0，z=(10)2=2，或者有：5.4分形

5.4.1分形的历史

1967年法国数学家B.B.Mandelbrot提出了“英国的海岸线有多长？”的问题，这个问题看起来好像极其简单，因为长度依赖于测量单位。以1km为单位测量海岸线，可得到的近似长度将短于1km的迂回曲折都忽略掉了，若以1m为单位测量，则能测出被忽略掉的迂回曲折长度将变大，测量单位进一步变小时,测得的长度将愈来愈大，这些愈来愈大的长度将趋近于一个确定值，这个极限值就是海岸线的长度。答案似乎解决了，但Mandelbrot发现：当测量单位变小时，所得的长度是无限增大的。因此，他认为海岸线的长度是不确定的，或者说，在一定意义上海岸线是无限长的。答案也许是因为海岸线是极不规则和极不光滑的。我们知道，经典几何研究光滑的曲线和曲面时，传统上将自然界大量存在的不规则形体规则化后再进行处理，我们必须将海岸线折线化才能得出一个有意义的长度。可贵之处是Mandelbrot突破了这一点，长度也许已不能正确概括海岸线这类不规则图形的特征。海岸线虽然很复杂，但却有一个重要的性质——自相似性。从不同比例尺的地形图上我们可以看出，海岸线的形状大体相同，其曲折、复杂程度是相似的。换言之，海岸线的任一小部分都包含有与整体相同的相似的细节。要定量地分析像海岸线这样的图形，引入分形维数是很有必要的。分形的研究可以上溯到很久以前。最早的工作可追朔到1875年，德国数学家维尔斯特拉斯（K.Weierestrass）构造了处处连续但处处不可微的函数，集合论创始人康托（G.Cantor，德国数学家）构造了有许多奇异性质的三分康托集。1890年，意大利数学家皮亚诺（G.Peano）构造了填充空间的曲线。1904年，瑞典数学家科赫（H.vonKoch）设计出