本发明提供一种无冗余计算的高效Marching Cubes等值面提取方法与系统，利于额外的数据结构存储立方体中能够重复利用的边上的插入顶点的坐标，以及用一个数组存储立方体中八个顶点的最大最小值，在比较时先比较这个最大最小值与等值面的值的关系。其速度快，减少了冗余计算，相邻立方体的同一个边的插入点只用计算一次，第二次直接取出，极大的提高了cpu的利用率，并且存储空间小，插入点信息和等值面是分开存储的，对于相同的插入点的具体信息，只用存储一次，在绘制等值面时不同等值面的同一个插入点直接利用同一个顶点信息，减少存储空间，同时提高了输出到文件中的速度。本发明应用于数据可视化处理领域。
1.一种无冗余计算的高效Marching Cubes等值面提取方法，其特征在于，利于额外的数据结构存储立方体中能够重复利用的边上的插入顶点的坐标，以及用一个数组存储立方体中八个顶点的最大值、最小值，在比较时先分别比较最大值、最小值与等值面的值的关系；
第一步：申请包含两个int类型的变量的结构体，分别存储单个立方体中的最大值和最小值；
第二步：以先X方向再Y方向，最后Z方向遍历所有的立方体以减少冗余计算，根据以上遍历方式将所有的立方体分成八种情形：①：x＝y＝0，z＝0、②：x≥1，y＝0，z＝0、③：x＝0，y≥1，z＝0、④：x≥1，y≥1，z＝0、⑤：x＝y＝0，z≥1、⑥：x≥1，y＝0，z≥1、⑦：x＝0，y≥1，z≥1、⑧：x≥1，y≥1，z≥1；
申请数组来存储能够减少冗余计算的边上的插入点，对于以上八种情形有以下的存储结构：情形一：用三个数据结构分别存储X(4,5,6,7),Y(0,4,8,9),Z(3,7,8,11)方向上的四个边上的插入点；
情形二：用情形一X方向上的数据结构继续存4,5,6,7边上的插入点，再用一个大小为X方向立方体个数减一的一维数组存储该方向上每个立方体0,4,8,9边上的插入点；
情形三：用情形一Y方向上的数据结构继续存0,4,8,9边上的插入点，再用一个大小为Y方向立方体个数减一的一维数组存储该方向上每个立方体4,5,7边上的插入点；
情形四：用情形二中的一维数组存储0,4,8,9边上的插入点，用情形三中的一维数组存储4,5,7边上的插入点，再用一个大小为X方向立方体个数减一乘以Y方向立方体个数减一大小的二维数组存储7,8边上的插入点；
情形五：用情形一Z方向上的数据结构存3,7,8,11边上的插入点；
情形六：在情形二存储结构基础上再用一个大小为X方向立方体数减一的一维数组存储7,8,11边上的插入点；
情形七：在情形三存储结构基础上再用一个大小为Y方向立方体数减一的一维数组存储3,7,8边上的插入点；
第三步：遍历所有立方体，将每个立方体的最大值、最小值存储在固定的数据结构中；
第四步：在计算与等值面相交的点之前利用第二步存储的最大值、最小值判断该立方体中是否存在与等值面的交点，如果存在交点则执行第五步，否则继续对下一个立方体从第三步开始进行判断；
第五步:情形一、二、三、四依次处理完各个数据，情形五、六、七、八放在一个大循环中处理；
Ⅰ、判断各个情形的数据中每个立方体顶点的值与阈值的大小关系进而得到一个索引值，之后根据索引值查找情形二、情形五、情形六的一维数组，获取立方体12条边中具有交点的边；
对于情形二中的立方体，第0,1,2,3,条边上的插入点的值可以从前面的提到的存储4,
5,6,7边结构中取出，不用计算，其它边照常计算；
对于情形三中的立方体，第2,6,10,11边上的插入点的值从存储0,4,8,9边结构中取出，不用计算，其它边照常计算；
对于情形四中的立方体，第2,6,10,11边上的插入点的值从存储0,4,8,9边结构中取出，第0,1,3边上的值从存储4,5,7边结构中取出，不用计算，其它边照常计算；
对于情形五中的立方体，第1,5,9,10边上的插入点的值从存储3,7,8,11边结构中取出；
对于情形六中的立方体，第0,1,2,3边上的插入点从存储4,5,6,7边结构中取出，第5,
9,10边上的插入点从存储7,8,11边结构中取出，不用计算，其它边照常计算；
对于情形七中的立方体，第2,6,10,11边上的插入点的值从存储0,4,8,9边结构中取出，第1,5,9边上的插入点从存储3,7,8边结构中取出，不用计算，其它边照常计算；
对于情形八中的立方体，第2,6,10,11边上的插入点的值从存储0,4,8,9边结构中取出，第0,1,3边上的值从存储4,5,7边结构中取出，第5,9边上的插入点的值从存储7,8边结构中取出，不用计算，其它边照常计算；
Ⅲ、处理完立方体的每条边后，按照第一步提到的把每种情形中后面能够利用的边上的插入点的值再存储到对应结构中；
Ⅳ、查找情形二、情形五、情形六的二维数组，提取每种情形的等值面，绘制成图像。
2.一种无冗余计算的高效Marching Cubes等值面提取系统，其特征在于，包括存储器和处理器，所述存储器存储有计算机程序，所述处理器执行所述计算机程序时实现权利要求1所述方法的步骤。
一种无冗余计算的高效Marching Cubes等值面提取方法与
系统
技术领域
[0001] 本发明涉及数据可视化处理领域，尤其涉及一种无冗余计算的高效Marching Cubes等值面提取方法与系统。
背景技术
[0002] 随着计算机硬件平台的不断发展，数值计算模拟的规模也不断增大，所产生的数据量也已经达到TB甚至PB量级，对于海量数据的可视化处理是当今可视化研究的热点与难点问题。由于等值面提取方式是捕捉海量数据典型特征的一种常用方法，因而近年来，海量数据的等值面提取方法一直是国内外可视化领域研究的重点。在众多的等值面提取方法中，Marching Cubes算法凭借其原理简单、易于实现的优点，成为了目前海量数据等值面提取的公认标准算法，在各个应用领域中均得到广泛应用。
[0003] 然而在处理大量数据时传统的Marching Cubes算法中重复的计算以及一些重复数据的存储，同时对于一个立方体中八个顶点与等值的判断才知道该立方体中有没有等值面，这些都让传统的Marching Cubes算法满足不了现在大量数据的需求，在提取等值面时进行了大量不必要且费时的计算，同时在显示中也保存了大量重复顶点的坐标信息，浪费了存储空间且更加费时。
[0004] 为了加快计算速度和输出显示的速度，提高CPU利用率；缩小存储空间，提高磁盘利用率，必须减少原始算法里的冗余计算，以及改进原来的存储方法。在原始算法中是以立方体为单位提取等值面的，每一个立方体都需要进行一次完整的运算，包括立方体八个顶点的值与等值面的值的比较，查256行的二维数组，算出三角面片的每一个点的插入值。之后以三角面片为基本单位显示出来或者是输出到文件中，这就存在了大量的重复计算和存储空间的浪费。
发明内容
[0005] 针对现有技术存在的不足，本发明的目的是提供一种无冗余计算的高效Marching Cubes等值面提取方法与系统，有效的减少占据计算过程中大部分时间的重复计算和减少判断次数。
[0006] 为了实现上述发明目的，本发明提供一种无冗余计算的高效Marching Cubes等值面提取方法，其采用的技术方案是：
[0007] 一种无冗余计算的高效Marching Cubes等值面提取方法，利于额外的数据结构存储立方体中能够重复利用的边上的插入顶点的坐标，以及用一个数组存储立方体中八个顶点的最大最小值，在比较时先比较这个最大最小值与等值面的值的关系。
[0008] 作为上述技术方案的进一步改进，参考图1，本发明具体包括以下步骤：
[0009] 第一步：申请包含两个int类型的变量的结构体，分别存储单个立方体中的最大值和最小值；
[0010] 第二步：以先X方向再Y方向，最后Z方向遍历所有的立方体以减少冗余计算，根据以上遍历方式将所有的立方体分层八种情形：①：x＝y＝0，z＝0、②：x≥1，y＝0，z＝0、③：x＝0，y≥1，z＝0、④：x≥1，y≥1，z＝0、⑤：x＝y＝0，z≥1、⑥：x≥1，y＝0，z≥1、⑦：x＝0，y≥1，z≥1、⑧：x≥1，y≥1，z≥1；
[0011] 申请数组来存储能够减少冗余计算的边上的插入点，对于以上八种情形有以下的存储结构：
[0012] 情形一：用三个数据结构分别存储X(4,5,6,7),Y(0,4,8,9),Z(3,7,8,11)方向上的四个边上的插入点；
[0013] 情形二：用情形一X方向上的数据结构继续存4,5,6,7边上的插入点，再用一个大小为X方向立方体个数减一的一维数组存储该方向上每个立方体0,4,8,9边上的插入点；
[0014] 情形三：用情形一Y方向上的数据结构继续存0,4,8,9边上的插入点，再用一个大小为Y方向立方体个数减一的一维数组存储该方向上每个立方体4,5,7边上的插入点；
[0015] 情形四：用情形二中的一维数组存储0,4,8,9边上的插入点，用情形三中的一维数组存储4,5,7边上的插入点，再用一个大小为X方向立方体个数减一乘以Y方向立方体个数减一大小的二维数组存储7,8边上的插入点；
[0016] 情形五：用情形一Z方向上的数据结构存3,7,8,11边上的插入点；
[0017] 情形六：在情形二存储结构基础上再用一个大小为X方向立方体数减一的一维数组存储7,8,11边上的插入点；
[0018] 情形七：在情形三存储结构基础上再用一个大小为Y方向立方体数减一的一维数组存储3,7,8边上的插入点；
[0019] 情形八：存储结构与情形四一样；
[0020] 第三步：遍历所有立方体，将每个立方体的最大最小值存储在固定的数据结构中；
[0021] 第四步：在计算与等值面相交的点之前利用第二步存储的最大最小值判断该立方体中是否存在与等值面的交点，如果存在交点则执行第五步，否则继续对下一个立方体从第三步开始进行判断；
[0022] 第五步:情形一、二、三、四依次处理完各个数据，情形五、六、七、八放在一个大循环中一处理。
[0023] 作为上述技术方案的进一步改进，第五步中，对每种情形中的每个立方体的处理步骤为：
[0024] Ⅰ、判断各个情形的数据中每个立方体顶点的值与阀值的大小关系进而得到一个索引值，之后根据索引值查找256种情况的一维数组，获取立方体12条边中具有交点的边；
[0025] Ⅱ、获取立方体12条边中具有交点的边后：
[0026] 对于情形一中的立方体，每条边都要计算；
[0027] 对于情形二中的立方体，第0,1,2,3,条边上的插入点的值可以从前面的提到的存储4,5,6,7边结构中取出，不用计算，其他边照常计算；
[0028] 对于情形三中的立方体，第2,6,10,11边上的插入点的值从存储0,4,8,9边结构中取出，不用计算，其他边照常计算；
[0029] 对于情形四中的立方体，第2,6,10,11边上的插入点的值从存储0,4,8,9边结构中取出，第0,1,3边上的值从存储4,5,7边结构中取出，不用计算，其他边照常计算；
[0030] 对于情形五中的立方体，第1,5,9,10边上的插入点的值从存储3,7,8,11边结构中取出；
[0031] 对于情形六中的立方体，第0,1,2,3边上的插入点从存储4,5,6,7边结构中取出，第5,9,10边上的插入点从存储7,8,11边结构中取出，不用计算，其他边照常计算；
[0032] 对于情形七中的立方体，第2,6,10,11边上的插入点的值从存储0,4,8,9边结构中取出，第1,5,9边上的插入点从存储3,7,8边结构中取出，不用计算，其他边照常计算；
[0033] 对于情形八中的立方体，第2,6,10,11边上的插入点的值从存储0,4,8,9边结构中取出，第0,1,3边上的值从存储4,5,7边结构中取出，第5,9边上的插入点的值从存储7,8边结构中取出，不用计算，其他边照常计算；
[0034] Ⅲ、处理完立方体的每条边后，按照第一步提到的把每种情况中后面能够利用的边上的插入点的值再存储到对应结构中；
[0035] Ⅳ、查找256种情况的二维数组，提取每种情况的等值面，绘制成图像。
[0036] 为了实现上述发明目的，本发明提供一种基于Marching Cubes的数据可视化处理系统，其采用的技术方案是：
[0037] 一种无冗余计算的高效Marching Cubes等值面提取系统，包括存储器和处理器，所述存储器存储有计算机程序，其特征在于，所述处理器执行所述计算机程序时实现上述方法的步骤。
[0038] 本发明的有益技术效果：
[0039] 1.速度快，减少了冗余计算，相邻立方体的同一个边的插入点只用计算一次，第二次直接取出，极大的提高了cpu的利用率。
[0040] 2.存储空间小，插入点信息和等值面是分开存储的，对于相同的插入点的具体信息，只用存储一次，在绘制等值面时不同等值面的同一个插入点直接利用同一个顶点信息，减少存储空间，同时提高了输出到文件中的速度。
附图说明
[0041] 图1是本发明立方体顶点和边的编号，规定的XYZ轴方向；
[0042] 图2是本发明总体流程图；
[0043] 图3是原始Marching Cubes算法，减少判断次数的方法和减少冗余计算加判断次数算法运行时间比较图；
[0044] 图4是原始Marching Cubes和本发明方法计算的顶点个数对比。
具体实施方式
[0045] 为了使本公开的目的、技术方案和优点更加清楚明白，下结合具体实施例，并根据附图，对本发明进一步详细说明。需要说明的是，在附图或说明书描述中，未描述的内容以及部分英文简写为所属技术领域中普通技术人员所熟知的内容。本实施例中给定的一些特定参数仅作为示范，在不同的实时方式中该值可以相应地改变为合适的值。
[0046] 如图2所示是本实施例总体流程图；
[0047] 第一步：计算所有立方体各自8个顶点的最大最小值；
[0048] 第二步：申请空间存储插入点信息；
[0049] 第三步：N＝1；
[0050] 第四步：判断N是否小于立方体个数，如果小于则进入第五步否则结束整个算法；
[0051] 第五步：判断等值面的值是否介于第N个立方体的最大值最小值之间，如果介于则进入第六步，否则N+1后进入第四步；
[0052] 第六步：判断顶点的值与阀值的大小关系计算索引值；
[0053] 第七步：根据索引值查表得到交点编号及三角面片个数M；
[0054] 第八步：判断M是否大于0，如果大于则进入第九步，否则N+1后进入第四步；
[0055] 第九步：K＝3；
[0056] 第十步：判断K是否大于0，如果大于则进入第十一步，否则存储第M个三角面片的信息，并将M‑1后进入第八步；
[0057] 第十一步：判断第N个立方体的第M个三角面片中的第k条边是否可直接使用之前存储的值，如果可以则进入第十二步否则进入第十三步；
[0058] 第十二步：直接使用之前存储的顶点信息并跳转到第十五步；
[0059] 第十三步：计算交点坐标；
[0060] 第十四步：判断交点是否需要存储，如果需要则存储到对应结构体；
[0061] 第十五步：K＝K‑1并跳转到第十步；
[0062] 采用实验验证本实施例方法的高效性。实验中对比了原始Marching Cubes算法与TM本实施例算法的性能。实验平台配置Intel Core i7‑6700HQ CPU,主频2.6GHz，内存容量
8GB，运行操作系统为Windows10家庭版(64位)。实验中采用不同规模的数据进行测试，数据的相关信息及测试结果如表1。表1及图2给出了本实施例方法与原始算法方法的性能加速对比。参考图3与图4，可以看出，本实施例方法的性能优于原始算法。AVL树方法是现有三种方法中性能最优的，而本实施例的性能较AVL树方法的稳定提高80％左右，证明了本实施例方法的性能优于已有方法。
[0063] 表1.实验数据
[0064]
[0065] 以上包含了本发明优选实施例的说明，这是为了详细说明本发明的技术特征，并不是想要将发明内容限制在实施例所描述的具体形式中，依据本发明内容主旨进行的其他修改和变型也受本专利保护。本发明内容的主旨是由权利要求书所界定，而非由实施例的具体描述所界定。
