维普资讯 http://www.cqvip.com 第３３卷 第１４期 计算机工程 ２００７年７月 Ｖｏ１．３３ Ｎｏ．Ｊ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ Ｊｕｌｙ ２００７ ・软件技术与数据库・ 文章编号：１００ｏ－＿３４２８（２００７）１４＿＿００３３—０３ 文献标识码：Ａ 中圈分类号：ＴＰ３１１ 基于分块混合八叉树编码的海量体视化研究 张传明，潘慈，徐绘宏 （北京大学地球与空间科学学院，北京１００８７１） 摘要：在介绍当前体数据的数据模型与绘制方法的基础上，使用混合八叉树进行体数据的描述，实现了对其自适应分块存储。并用体元 投射和三维纹理映射方法分别实现了混合八叉树的体绘制与多分辨率绘制。实验结果表明，该文的算法较好地实现了基于混合八叉树结构 的海量体数据的组织、存储和绘制。 关健词：混合八叉树；分块；三维纹理映射；体元投射 Ｈｙｂｒｉｄ Ｂｌｏｃｋｉｎｇ Ｏｃｔｒｅｅ—ｂａｓｅｄ Ｍａｓｓ Ｖｏｌｕｍｅ Ｒｅｎｄｅｒｉｎｇ ＺＨＡＮＧ Ｃｈｕａｎｍｉｎｇ，ＰＡＮ Ｍａｏ，ＸＵ Ｈｕｉｈｏｎｇ （Ｓｃｈｏｏｌ ｏｆ Ｅａｒｔｈ ａｎｄ Ｓｐａｃｅ Ｓｃｉｅｎｃｅｓ，Ｐｅｋｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ １００８７１） ［Ａｂｓｔｒａｃｔ］Ｂａｓｅｄ ｏｎ ｔｈｅ ｉｎｔｒｏｄｕｃｔｉｏｎ ｏｆ ｃｏｍｍｏｎ ｄａｔａ ｍｏｄｅｌｓ ａｎｄ ｒｅｎｄｅｒｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｖｏｌｕｍｅ ｄａｔａ，ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ ｈｙｂｒｉｄ ｏｃｔｒｅｅ ｅｎｃｏｄｉｎｇ ｔｏ ｄｅｓｃｒｉｂｅ ｉｔ．Ｓｅｌｆ－ａｄａｐｔｉｖｅ ｂｌｏｃｋｉｎｇ ｍｅｔｈｏｄ ｉｓ ａｐｐｌｉｅｄ ｔｏ ｓｔｏｒｅ ａｎｄ ｍａｎａｇｅ ｍａｓｓ ｖｏｌｕｍｅ ｄａｔａ．Ｖｏｌｕｍｅ ｒｅｎｄｅｒｉｎｇ ａｎｄ ｍｕｌｉｔ—ｒｅｓｏｌｕｔｉｏｎ ｒｅｎｄｅｒｉｎｇ ｆｏｒ ｈｙｂｒｉｄ ｏｃｔｒｅｅ ｖｉａ ｃｅｌｌ ｐｒｏｊｅｃｔｉｏｎ ａｎｄ ３Ｄ—ｔｅｘｔｕｒｅ ｍａｐｐｉｎｇ ａｒｅ ｉｍｐｌｅｍｅｎｔｅｄ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍｓ ｅｆｆｅｃｔｉｖｅｌｙ ｓｏｌｖｅ ｓｔｏｒａｇｅ，ｍａｎａｇｅｍｅｎｔ ｎａｄ ｒｅｎｄｅｒｉｎｇ ｆｏｒ ｈｙｂｒｉｄ ｏｃｔｒｅｅ ｂａｓｅｄ ｍａｓｓ ｖｏｌｕｍｅ ｄａｔａ． ［Ｋｅｙ ｗｏｒｄｓ］ｈｙｂｒｉｄ ｏｃｔｒｅｅ；ｂｌｏｃｋｉｎｇ；３ｄ—ｔｅｘｔｕｒｅ ｍａｐｐｉｎｇ；ｃｅｌｌ ｐｒｏｊｅｃｔｉｏｎ 随着体数据在各领域的广泛应用，人们对其可视化方法 存储调入。以往对于分块并没有过多的研究，而仅仅采用简 的研究日益深入。同时由于数据量激增，海量体数据的组织 单８“划分的方法，如图１中方案Ａ所示。 方式也成为一个关键问题。最简单的体数据结构是三维规则 格网，但规则格网内不仅可能有“空数据区”，还可能存在大 量邻近且属性一致的体元，形成数据冗余。八叉树结构很好 区域含 地解决了这个问题，它采用“渐进描述”的思想，当体数据 四面体 复杂度不大时，可以极大地节省存储量【ｌ Ｊ。然而，经典八叉 树结构描述的三维物体在边界处可能存在锯齿现象。因此， 本文使用分块的混合八叉树以改进经典的八叉树结构。 体数据可视化的目的是将物体内部的细节表现到屏幕 上，形成体最终图像，这种模式使得观察者可以把握整个三 ｌｉｅＩ ｉｌｅ３ …・ Ｆｉｌｅ８ ｉｌｅｌ ｉｌｅ３ …‘ Ｆｉｌｅ８ …‘‘ Ｆｉｌｅｌ ５ 维数据场分布整体特征。体绘制从实现方法上可以分为软件 （ａ）方案Ａ （ｂ）方案Ｂ 法和硬件法两种 Ｊ，软件方法主要以光线跟踪法、体元投射 图１两种分块方案 法为代表，这类算法效果最好但速度较慢。硬件方法以三维 当应用经典八叉树时，能在理论上计算某层八叉树所有 纹理映射为代表，速度快且绘制效果好。 节点数据量的上限，故方案Ａ能有效分配内存。但混合八叉 本文讨论了基于混合八叉树结构的体数据分块编码算 树的某些区域可能因含有大量四面体而导致方案Ａ的某些分 法，用体元投射和三维纹理分别实现了体数据的可视化，通 块超出预定大小，而若再做一次细分，则又会造成某些简单 过“节点综合”技术实现了多分辨率的体绘制。 分块不必要的八分。如果能根据数据量的大小创建出图１中 １ 自适应分块混合八叉树编码 方案Ｂ的分块结构，则能有效减少分块的个数，进而提高绘 １．１混合八叉树数据结构 制的效率。但随之而来的困难是无法通过在内存中创建出整 为解决规则八叉树在边界处的锯齿问题，李清泉等人提 棵八叉树来进行“全局规划”，下文便针对此问题讨论在仅有 出了混合八叉树 Ｊ，它的主体结构仍然是八叉树，但当节点 矢量外壳时直接创建分块混合八叉树的方法。 位于物体边界且外形不是规则立方体时，则改用若干四面体 １．３索引八叉树结构 描述物体在该体元处的真实外形。本文亦采用该结构，混合 本文对分块八叉树用索引八叉树加以组织。索引八叉树 八叉树的节点结构如下： 对应着全树去除所有子文件所对应的细节节点而剩下的主体 部分，使用它不仅能够方便地组织各个分块，还能在海量绘 作者简介：张传明（１９８２一），男，博士研究生，主研方向：三维地理 １．２常规分块与自适应分块 信息系统；潘懋，教授、博士生导师；徐绘宏，博士研究生 对于海量数据，不可能同时将其调入内存，因此需分块 收稿日期：２００６—０８—２５ Ｅ－ｍａｉｌ：ｃｈｕａｎｍｉｎｇ＿ｚｈａｎｇ＠ｐｋｕ．ｏｒｇ．ｃａ ３３— 维普资讯 http://www.cqvip.com 制时快速地根据光线方向确定分块的绘制顺序，并且索引树 本身也构成了一个粗略的体数据。 索引八叉树的所有叶节点都必须唯一对应一个子八叉 当调用Ｐｒｏｃｅｓｓ（Ｒｏｏｔ）完成后，一系列子树就被存储，而 内存中未被删除的八叉树便是索引八叉树。 ２海量体视化的实现 树，这是由体绘制的性质决定的，具体来说需满足如下２点： （１）索引八叉树的所有叶节点都必须对应子块，但索引八叉树本 身不应参与绘制，否则绘制结果可能错误。如图２中的叶节点１１１、ｎ 不属于任何子块，但它们对应的体数据仍须参与绘制，因此只能绘 制索引八叉树。若光线的方向决定了绘制必须按照顺序（ａ，ｂ，ｍ，ｃ， ｄ，ｅ，ｎ，ｆ）进行，则ｍ，ｎ必须分开绘制，这和三维纹理映射的特性是相 矛盾的（索引八叉树必须被整体地转化为三维格网并且一次性绘制 完毕）。 （２）索引八叉树的每个叶节点只能对应一个子块，即子块之间不 允许有嵌套关系。图２说明了违反该准则可能导致的问题，子块８ 的第６节点因包含细节过多，被子块９来描述，形成嵌套关系。根 据绘制的顺序，应当在块８绘制到第６节点处“转而”绘制块９， 完成后再进行块８其余部分的绘制。但事实上，由于三维纹理的整 体性，因此这２个子块是无法实现交叉绘制的。 ａ ｂ ｍ Ｃ ｄ ｅ ｎ ｆ Ｆｉｌｅｌ Ｆｉｌ…ｆｅ３…Ｆｉｌｅ６ 圈２两种错误的分块方法 １．４生成分块ｉＩ茜合八叉树 该算法使用的节点数据结构在１．１节中的Ｎｏｄｅ结构上添 加了一个辅助布尔量ｓｔｏｐｓａｖｅ（初始为ｆａｌｓｅ）以及一个整型变 量ＴｏｔａｌＳｉｚｅ，存储了节点的累计大小（该节点和所有子节点的 大小之和，含四面体大小）。下面给出递归函数Ｐｒｏｃｅｓｓ的 伪码： Ｐｒｏｃｅｓｓ（Ｎｏｄｅ）｛ ｉｆ（Ｎｏｄｅ深度不够）｛ 分出子节点并在内存中与当前节点建立指针关联； ｉｆ（子节点属性一致） 直接删除子节点 ｅｌｓｅ｛ Ｐｒｏｃｅｓｓ（ｃｈｄ［０］）； Ｐｒｏｃｅｓｓ（ｃｈｄ［１】）； ｒＰｏｃｅｓｓ（ｃｈｄ［７】）； ｝ ｝ ｅｌｓｅ｛ ｉｆ（节点自身ｓｔｏｐｓａｖｅ＝＝ｆａｌｓｅ）ｆ ｉｆ（父节点ｓｔｏｐｓａｖｅ为ｔｒｕｅ） 存储当前节点对应的子树并将子树从八叉树中去除 ｅｌｓｅ ｉｆ（节点ＴｏｔａｌＳｉｚｅ过大）｛ 将节点的８ 个子节点对应子树各存储为一个文件 在内存中删除８个子节点对应的所有子树 将节点及所有父、祖节点的ｓｔｏｐｓａｖｅ都设置为ｔｒｕｅ ） ｅｌｓｅ 父节点的累计大小＋＝当前节点累计大小 ）ｅｌｓｅ 检查８个孩子节点，将未存储的存储并在内存中删除 ）） ３４一 ２．１确定绘触的分块晨序 当光线以某一角度射入分块后的体数据时，必然会有某 些分块先被绘制，而某些后被绘制，以往的研究者归纳出了 ８种最基本的情况 Ｊ，在图３中列出了这些情况（从后向前）。 光线方向 绘制顺序 ｘ＜Ｏ，ｙ＜Ｏ，ｚ＜Ｏ ７ ６．５ ３ ４ ２．１．Ｏ ｘ＜Ｏ．ｙ＜Ｏ．ｚ＞＝Ｏ ６．７．４ ２．５ ３ Ｏ １ ｙ ｘ＜Ｏ，ｙ＞＝Ｏ，ｚ＜Ｏ ５－４．７．１．６ Ｏ ３．２ ｘ＜《）’ｙ）＝０，ｚ＞＝０ ４．５．６．Ｏ－７．１．２ ３ ｘ＞＝Ｏ．ｙ＜Ｏ．ｚ＜Ｏ ３．２．１．７．Ｏ．６．５ ４ ｘ＞：Ｏ ，ｚ＞＝Ｏ ２．３．Ｏ ６．１．７．４．５ ｘ＞＝Ｏ，ｙ＞＝０，ｚ＜Ｏ １ Ｏ ３ ５．２ ４ ７．６ ｘ＞－－Ｏ，ｙ＞＝Ｏ，ｚ＞＝Ｏ Ｏ １ ２ ４．３．５ ６．７ 圈３给定光线的节点绘翻晨序 当未在第１层生成子文件块时，需要递归地确定绘制顺 序，此时应按图３的顺序遍历整个索引八叉树。在绘制时， 按队列顺序执行“读入子树一绘制一保留绘制结果一删除子 树一读入下一子树……”，即可完成海量体数据的绘制。 ２．２基于体元投射的绘倒 ２．２．１体元投射概述 体元投射是一种精度较高的软件实现算法，它的核心思 想是分别绘制每个体元，并按从后往前的顺序叠加各个体元 的绘制结果，最终形成屏幕图像 Ｊ。由于屏幕分辨率远细于 体元大小，因此采用体元投射能够避免不规则边界处的走样 现象。在对八叉树进行体元投射绘制时，应先将所有节点根 据光线方向顺序绘制，具体排序方法见２．１节。 ２．２．２绘制四面体 Ｊａｎｅ［６１指出，穿过某厚度体元后的光线不透明度值为Ｏ 。 ＝ｌ—ｅ～，其中ｍ为各处对光线的“阻碍度”在厚度上的积分。 因四面体内属性均一，所以ｍ与厚度成正比，这样问题便转 化为求得各条光线穿过四面体的厚度。而在所有的光线中， 必然存在一条入射厚度最大的光线，后文称作“最佳光线”。 当最佳光线及其入射厚度获得后，其余光线的厚度均可以通 过插值得到。绘制过程分为如下２步： （１）确定最佳光线。４个顶点在像平面上的投影组成的凸 壳为四边形或三角形（见图４）。当凸壳为四边形，光线穿过对 角线交点时便有最大厚度；当凸壳为三角形时，必然有一个 顶点在三角形内部或是在三角形边上，只要入射光穿过此点， 则会有最大厚度。 △ 图４四面体投影的４种情况 （２）完成厚度计算。获得最佳光线并计算出最大厚度后， 可以据此将四面体在象平面上的投影分割为若干三角形。这 些三角形顶点中，除了最佳光线穿过的顶点有最大厚度之外， 其余顶点厚度均为０。对每个三角形内的各点根据３个顶点 的厚度进行插值即可完成体元厚度计算过程。 ２．２．３绘制立方体 一个直观的绘制立方体的思路是将立方体分解为若干个 维普资讯 http://www.cqvip.com 四面体进行绘制，但此法效率极低。考虑到组成物体的所有 子节点均值并不一定正确。图６中，ｇ节点拥有与兄弟节点 立方体存在某些“共性”，Ｊａｎｅ提出了基于模板的立方体元投 迥异的属性，当该异常为噪音时，应当在节点综合中滤去； 射法 ，利用模板只需进行一次计算，便可通过在像平面上 若是体数据的重要特征点，应在父节点中完全保留。 的二维平移来绘制所有等大的规则节点。 模板体元的绘制也分为确定最佳光线和计算入射厚度两 步，实现思路和四面体类似，并已在文献［６】中有了详细的阐 述，此处不再展开。 ２．３基于三维纹理的绘倒 ２．３．１三维纹理概述 三维纹理是随着图形硬件技术发展而提出的一种高性能 图６ ３种不同的节点综合方法 体绘制算法，最早由Ｃｕｌｌｉｐ 提出，其思想仍然是“采样一合 为解决该问题，本文提出如下的“节点综合”算法： 成”。以图像空间法为例，用户通过若干个与Ｚ方向垂直的平 （１）计算ｐｒｏｐ ＝（ｐｒｏｐｌ＋ｐｒｏｐ２＋…＋ｐｒｏｐｓ）／８；（２）选出属性距 面去切割属性为颜色值的纹理块获得若干切面，最后合成这 ｐｒｏｐ 最大的ｋ个元素（】＜ｋ＜８），ｋ称为“综合系数”；（３）取 些切面得到图像。三维纹理的绘制效果主要由纹理的分辨率 上述ｋ个元素属性的均值，作为父节点的属性。 和切片的次数决定，因此在多分辨率绘制模式下往往用较少 不难看出，ｋ的值越小，越倾向于认为异常值节点是“真 的切片和较小的纹理块来实现低分辨率的绘制【３】。 实异常”；而当ｋ增大，则说明异常值属噪音的概率增大；当 但在当纹理块较小时，三维纹理往往无法精确绘制边界 ｋ取８时，父节点即为８个子节点的均值。可以在计算时通 体元。因此一种扬长避短的设想是在对某八叉树的规则叶节 过调整ｋ的值，获得不同的效果。 点使用三维纹理映射的同时，使用体元投射绘制边界四面体。 ３实验结果 而事实上，这个思路并不可行。例如图５中某光线穿过混合 笔者在单机上进行了下列对比实验。实验环境为ＡＭＤ 八叉树的６个节点，应按照６—５—４・３—２・１顺序合成这些体元的 Ａｔｈｌｏｎ ２４００＋，５１２ＭＢ的ＲＡＭ，ＮＶＩＤＩＡ６８００＋显卡。 绘制结果，但规则体元３、１已作为一个整体进行绘制，在其 （１）分块方案对比测试。从矢量外壳分别进行规则细分和 中是无法插入不规则体元２的。 自适应细分生成混合八叉树后，均完全从磁盘分块读入并用 三维纹理进行硬件绘制。对比结果如下 、、、 、、 ５ 、 ３ 、、 、 、（２）四面体加入三维纹理效果测试。分别绘制了将四面体 、 ▲ 加入三维纹理网格和半透明化后再加入的结果，见图７中Ａ、 图５同时进行三堆纹理和体元投射绘倒 Ｂ。可见半透明化四面体增强了三维纹理绘制的真实感。 综上所述，采用三维纹理映射时应将不规则体元也一并 （３）多分辨率绘制实验。分别用减少切片数和“节点综 纳入纹理内存进行绘制。 合”算法进行了粗略绘制（ｋ＝１），见图７中Ｃ、Ｄ。可见本文 ２．３．２由混合八叉树构建三维纹理块 的算法能通过调整“综合系数”有效地保留特征点。 三维纹理块实际上相当于一个三维数组，每个元素对应 于真实物体的某一区域。而由上节所述可知，若将边界体元 直接映射到纹理块，将产生与规则八叉树类似的边缘锯齿问 题。借鉴图形学中对二维直线的反走样算法，本文通过根据 不规则体元的体积占规则相应体元体积的比例来削弱该体元 的不透明度，达到简单的反走样效果。削弱后的不透明度可 用如下公式计算： Ａｌｐｈａ ｅ ＝Ａｌｐｈａ×（Ｖｔ ｔＩ＋Ｖｔ ｔ２＋．．．＋Ｖｔ“ｎ）／Ｖｃｕｂｅ ２．３．３切片与合成 构建三维纹理块后，需要用若干平面切割纹理块。在实 现中，ＯｐｅｎＧＬ对三维纹理提供了方便的接口，只要提供三 维纹理数组和一系列切面多边形的纹理坐标，ＯｐｅｎＧＬ就能 图７测试绘倒结果 借助硬件完成切面颜色值的插值与合成。 ４结论 ２．３．４多分辨率的实现 本文引入的混合八叉树结构既保留了八叉树方便访问、 多分辨率在很多场合是必需的，实现的难点是对某些区 减少冗余的优点，又精确地描述了体数据的外壳。然而由于 域使用较少的时间绘制尽可能真实的图像。Ｉｍｍａ提出了一种 内存和纹理内存的限制，因此海量体数据必须在磁盘上分块 减少切片次数，并用插值算法调整每个切面的颜色值后再加 存储读取，本文可以在未知剖分后四面体数量的情况下实现 以合成的策略Ｉ 。本文则用较浅的八叉树节点填充入较小的 对体数据外壳直接自适应地生成分块数据，保证了每个分块 纹理块，自然减少了切片的次数，有效节约了绘制时间。 的大小限制在阈值内。本文将生成的分块数据用索引八叉树 在图６中，为了用节点Ｋ表示子节点ａ．ｈ的总体情况， 组织，并保证索引八叉树的所有叶节点均对应且仅对应一个 需要先计算出Ｋ的属性值，即实现子节点的综合，而简单取 文件分块。 （下转第７８页） ３Ｓ一 维普资讯 http://www.cqvip.com ２．４测试树生成 构造测试树算法描述如下： ｕｎｐｒｏｃｅｓｓｅｄ＝｛ｘ１Ｉｘ１∈ｓ１）×｛ｘ２１ｘ２∈ｓ２｝．．． ｐｒｏｃｅｓｓｉｎｇ＝￣ ｐｒｏｃｅｓｓｅｄ＝￣ ｐｒｏｃｅｓｓｉｎｇ＝｛ｎｅｗＮｏｄｅ（Ｚ０）｝ ｒｅｐｅａｔ ｓｅｌｅｃｔ ｏｎｅ ｎｏｄｅ Ｚ Ｅｐｒｏｃｅｓｓｉｎｇ ｆｏｒ ｅａｃｈｔｒａｎｓｉｔｉｏｎｔ ＥＴａｔＺ｛ ｉｆｔｉｓ ｅｎａｂｌｅｄ ａｔＺ｛ ｙ＝ｒｅｓｕｌｔＳｔａｔｅ（Ｚ，ｔ） ｉｆ（ｙ诺ｐｒｏｃｅｓｓｅｄｕｐｒｏｃｅｓｓｉｎｇ）｛ ｎｅｗＮｏｄｅ（ｙ） ｐｒｏｃｅｓｓｉｎｇ＝ｐｒｏｃｅｓｓｉｎｇ ｕ｛Ｙ） ｒｅｍｏｖｅ Ｙ ｆｒｏｍ ｕｎｐｒｏｃｅｓｓｅｄ｝） ｅｌｓｅ｛ ｙ＝ａｂｎｏｒｍａｌ ａｐｐｅｎｄ（Ｚ，Ｙ，ｔ））） ｒｅｍｏｖｅ Ｚ ｒｏｍ ｐｒｏｃｅｓｓｉｆｎｇ ｐｒＯｃｅｓｓｅｄ＝ｐｒＯｃｅｓｓｅｄ Ｕ Ｚ ｕｎｔｉｌ ｐｒｏｃｅｓｓｉｎｇ＝￣ Ｄ￣Ｄｅｐｏｓｉｔ ～Ｗｉｔｈｄｒａｗ 测试用例是调用序列和数据的组合。测试人员需根据测 试要求选择测试用例生成准则，即：（１）从测试树的根结点到 ＤＸ（Ｉ）￣Ｄ（１３），Ｄ（１４），Ｄ（Ｉ５），Ｄ（１６），Ｄ（Ｉ７） ＷＸ（１卜 Ｉ４）， Ｉ５）， Ｉ６）， Ｉ７） 叶子结点至少测试１次。（２）每个状态至少被测试１次。 （３）每个迁移至少被测试１次。 圈３属性ｂａｌａｎｃｅ的测试树 ３结论 如果构件的状态对应为事物的整体抽象描述，则需从高 层次上构造状态图或状态迁移图，且测试人员在设计测试用 属性ｂａｌａｎｃｅ不与其他属性存在关联关系，可作为独立的 属性关联关系构造测试树。假设Ａ取值为２００，Ｂａｌａｎｃｅ的理 想状态空间为（【Ｏ，Ｏ］，（Ｏ，１ ｏｏｏ），［１ ０００，１ ０００］，（１ ０００，１ ２００）， ［１ ２００，１ ２００］，（１ ２００，２ ｏｏｏ），［２ ０００，２ ０００］】，分别命名为 例时，必须考虑行为之间上下文依赖和内容的依赖关系。 参考文献 １ Ｊｅｒｒｙ Ｇ Ｍｏｎｉｔｏｒｉｎｇ Ｓｏｆｔｗａｒｅ Ｃｏｍｐｏｎｅｎｔ ａｎｄ Ｃｏｍｐｏｎｅｎｔ—ｂａｓｅｄ ｛ｓ１，ｓ２，ｓ３，ｓ４，ｓ５ Ｊ。状态迁移集见表２。构造好测试树后，根 据测试覆盖准则产生测试用例。根据测试用例生成准则Ｉ生 成测试用例见表３。 表３部分测试用倒 Ｓｏｆｔｗａｒｅ［Ｃ］／／Ｐｒｏｃ．ｏｆ ｔｈｅ ２４ Ａｎｎｕａｌ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｍｐｕｔｅｒ Ｓｏｆｔｗａｒｅ＆Ａｐｐｌｉｃａｔｉｏｎｓ Ｃｏｎｆｅｒｅｎｃｅ．２０００—０８． ２ Ｂｅｙｄｅｄａ Ｓ．Ｇｒｕｈｎ Ｖ Ｔｅｓｔｉｎｇ Ｃｏｍｐｏｎｅｎｔ—ｂａｓｅｄ Ｓｙｓｔｅｍｓ Ｕｓｉｎｇ ＦＳＭｓ［Ｍ］．Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ．２００４：３６３—３７９． ３ Ｓｏｈｎ Ｈ Ｗ Ｋｕｎｇ Ｄ Ｃ，Ｈｓｉａ Ｅ Ｓｔａｔｅ—ｂａｓｅｄ Ｒｅｐｒｏｄｕｃｉｂｌｅ Ｔｅｓｔ— ｉｎｇ ｆｏｒ ＣＯＲＢＡ Ａｐｐｌｉｃａｔｉｏｎｓ［Ｃ】／／Ｐｒｏｃ．ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ ｆｏｒ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｉｂｕｔｅｄ ｒ构造的测试树如图３所示。 Ｓｙｓｔｅｍｓ．１９９９． （上接第３５页） 在体元投射算法中，组成体数据的所有体元最终被转化 为四面体和立方体分别绘制。在应用三维纹理映射时，本文 提出了将四面体纳入三维纹理的反走样算法以及用自由度较 ４李德仁，李清泉．一种三维ＧＩＳ混合数据结构研究［ＪＪ．测绘学报， １９９７，２６（２）：１２８—１３３． ５ Ｓｒｉｎｉｖａｓａｎ Ｒ，Ｆａｎｇ Ｓｈｉａｏｆｅｎ，Ｈｕａｎｇ Ｓｕ．Ｖｏｌｕｍｅ Ｒｅｎｄｅｒｉｎｇ ｂｙ 大的“节点综合”法实现多分辨率，测试结果证明，本文提 出的算法在应用中获得到了很好的效果。 Ｔｅｍｐｌａｔｅ—ｂａｓｅｄ Ｏｃｔｒｅｅ Ｐｒｏｊｅｃｔｉｏｎ［Ｃ］／／Ｐｒｏｃ．ｏｆ ｔｈｅ ３ ｍｕｒｏｇｒａｐｈｉｃｓ Ｗｏｒｋｓｈｏｐ ｏｎ Ｖｉｓｕａｌｉｚａｔｉｏｎ ｉｎ Ｓｃｉｅｎｔｉｉｃ Ｃｏｍｐｕｔｉｆｎｇ．１ ９９７．４： ｌ５５—１６３． 参考文献 １ Ｓａｍｅｔ Ｈ，Ｗｅｂｂｅｒ Ｒ Ｅ．Ｈｉｅｒａｒｃｈｉｃａｌ Ｄａｔａ Ｓｔｒｕｃｔｕｒｅｓ ａｎｄ Ａｌｇｏｒｉｔｈｍｓ ６ Ｗｉ￣ｅｌｍｓ Ｊ．Ｖａｎ Ｇｅｌｄｅｒ Ａ．Ａ Ｃｏｈｅｒｅｎｔ Ｐｒｏｊｅｃｔｉｏｎ Ａｐｐｒｏａｃｈ ｆｏｒ Ｄｉｒｅｃｔ Ｖｏｌｕｍｅ Ｒｅｎｄｅｒｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｈｅ ｌ ｔ８ Ａｎｎｕａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ ｎｄ ａＩｎｔｅｒａｃｔｉｖｅ Ｔｅｃｈｎｉｑｕｅｓ．１９９１．７：２７５—２８４． ７ Ｃｕｌｌｉｐ Ｔ Ｊ．Ｎｅｕｍａｎｎ Ｕ．Ａｃｃｅｌｅｒａｔｉｎｇ Ｖｏｌｕｍｅ Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｗｉｈ ３Ｄ ｔｏｒ ｆＣｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ［Ｊ］．ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈ，１９８８，８（４）：５９—７５． ２唐泽圣．三维数据场可视化［Ｍ】．北京：清华大学出版社，１９９９． ３ Ｂｏａｄａ Ｉ，Ｎａｖａｚｏ Ｉ，Ｓｃｏｐｉｇｎｏ Ｒ．Ｍｕｌｔｉ—ｒｅｓｏｌｕｔｉｏｎ Ｖｏｌｕｍｅ Ｖｉｓｕａｌｉｚａｔｉｏｎ ｗｉｔｈ ａ Ｔｅｘｔｕｒｅ—ｂａｓｅｄ Ｏｃｔｒｅｅ［Ｊ］．Ｔｈｅ Ｖｉｓｕａｌ Ｃｏｍｐｕｔｅｒ，２００１，ｌ７（３）： １８５—１９７． Ｔｅｘｔｕｒｅ Ｍａｐｐｉｎｇ Ｈａｒｄｗａｒｅ［Ｒ］．Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｎｏｒｔｈ Ｃａｒｏｌｉｎａ， Ｔｅｃｈｎｉｃａｌ Ｒｅｐｏｒｔ：ＴＲ９３—０２７，１９９３． —－７８～
