技术摘要：
本发明公开了一种基于计算机进行多线程并行的非结构网格体绘制方法，包括：计算四面体网格单元的深度信息；对四面体数据进行基于深度的并行可见性排序生成有序的四面体数据；对有序的四面体数据进行归一化的拆分处理生成构造数据；对构造数据采用计算偏移量的方法生成  全部
背景技术：
目前尚无专利针对非结构网格的线程级并行体绘制算法。计算流体力学(CFD)进 行实验时会产生大量的模拟数据，其中包含了大量的非结构网格数据。体绘制是三维标量 场数据重要的可视化形式，它直接把体数据映射为二维屏幕图像，具有强大的空间表现能 力。目前，在非结构网格体绘制领域的专利相对于结构网格而言比较少，原因在于非结构网 格几何结构和拓扑结构的复杂性，它的网格之间的邻接关系是无规则的，一般通过显式存 储邻接矩阵的方式表达其连接关系。如果要寻找一个网格单元的邻接单元，可能需要局部 搜索甚至全局搜索，这也是目前非结构体绘制算法效率普遍较低的重要原因。体元投影法 是基于对象空间的经典非结构网格数据体绘制算法，它的前提是要有正确的可见性顺序。 其中投影四面体算法又是应用最广泛的体元投影法，它通过沿着视线方向把四面体的投影 分解为一系列三角形，并把三角形顶点数据载入GPU显存，利用GPU光栅化三角形顶点，以半 透明的三角形面片近似表示体绘制结果。但是，该方法具有如下缺点： (1)沿着视线方向对网格单元进行可见性排序是一个耗时的过程； (2)对于四面体单元的投影进行分类和拆分需要大量的浮点运算。 以上缺点导致投影四面体算法效率较低，特别是对于大规模网格(网格数上百 万)，不能满足实时交互的需求。因此，本发明基于目前的串行投影四面体算法性能的不足 的问题，设计了多线程并行的可见性排序算法和多线程并行的四面体投影分类与拆分算 法，充分利用当前多核CPU的计算资源，提升了投影四面体算法的效率，算法能够满足大规 模非结构网格体绘制实时交互的需求。 体绘制直接从体数据中生成可交互的二维屏幕图像，因此也称为直接体绘制，是 探索、浏览和展示体数据最重要的可视化技术，支持用户直观方便地理解体数据内部感兴 趣的区域信息，具有强大的空间表现能力。体数据采取几何拓扑网格(即空间网格)刻画三 维标量场数据，因此它具有几何结构和拓扑结构。根据网格形态划分，可以分为结构网格和 非结构网格。结构网格的几何结构和拓扑结构在空间中是有规律的，可以通过简单的算法 计算出与某个网格单元相邻的其他网格单元，目前，有很多支持该类型网格的体绘制算法， 其中，光线投射算法以其效率高、绘制结果精确而被广泛使用。根据光线投射算法易于并行 特点以及各种图像显卡技术的迅速发展，基于GPU加速的光线投射算法提供了效率更快、效 果更好的体绘制结果。但是，对于非结构网格，由于它的几何结构和拓扑结构的无规律性， 单元之间的面相邻关系需要显式存储，在计算某一个单元的邻接单元时，可能需要局部搜 索甚至全局搜索，这也导致应用于非结构网格的体绘制算法效率普遍低下，不能满足实时 交互的需求。 目前，非结构网格的体绘制算法主要有两类，一类是基于可见性排序的体绘制算 3 CN 111598991 A 说　明　书 2/7 页 法，另一类是光线投射算法。 (1)基于可见性排序的算法：顾名思义，需要正确的可见性顺序。可见性顺序是指， 给定一条视线，单元A遮挡单元B，就把A排到B前面的全序关系。这类体绘制算法中最具代表 性的是体元投影算法，其中投影四面体算法是经典的体元投影算法，四面体是三维基本单 元中最简单的单元，其他多面体网格都可以通过四面体化处理转化为四面体网格。执行投 影四面体算法前需要正确的可见性顺序，经过可见性排序后，将四面体投影分类和拆分(如 图1和图2所示)为一系列半透明的三角面片，图中新产生的顶点，则是通过线性插值的方法 计算得到其颜色值和透明度值。经过投影处理后得到的顶点数据需要载入显存，通过 OpenGL调用图形显卡进行三角面片渲染，最终得到体绘制的近似结果。 (2)基于光线投射的算法：此类方法不需要进行预先的可见性排序，其原理如图3 所示，从视点出发，沿着屏幕上像素点发射光线，沿着光线方向进行等距离采样，按照从前 向后或者从后向前的顺序进行光学积分，将积分结果作为最终的像素值，同样的操作需要 对屏幕上的每个像素进行，生成最终的体绘制图像。在进行采样过程中，需要根据当前采样 点和采样距离计算出下一个采样点位置。对于结构网格，可以很容易计算出下一个采样点 的位置，但是，对于非结构网格来说，单元面之间的关系通过显式存储，在计算下一个采样 点的位置时，往往需要进行局部搜索甚至全局搜索，因此效率甚低。基于光线投射的非结构 网格体绘制算法一般把采样点限制到体单元面上并对采样点积分，需要存储单元面之间的 邻接关系，对于内存的占用较高。
技术实现要素：
本发明主要目的是通过计算机对于四面体网格进行快速体绘制，达到实时交互的 目的。为了实现上述目的，本发明提供了一种基于计算机进行线程并行的快速四面体投影 体绘制算法。 本发明采用如下技术方案实施： 1、一种基于计算机进行多线程并行的非结构网格体绘制方法，包括： —存储有计算程序的存储器， —执行所述程序的处理器及显示器，其中所述处理器执行所述程序实现如下步 骤： 计算四面体网格单元的深度信息 对四面体数据进行基于深度的并行可见性排序生成有序的四面体数据； 对有序的四面体数据进行拆分归一化处理生成构造数据； 对构造数据采用计算偏移量的方法生成顶点数组； 顶点数组载入显存并光栅化顶点生成最终体绘制图像。 所述并行可见性排序对四面体数据先进行粗排序，再细排序，其中： 粗排序是对四面体数据划分成若干个数值区间没有交集的子数组， 细排序是对子数组采用线程并行方式进行排序生成有序的四面体数据。 所述构造数据是对四面体投影分类和拆分，过程分为两层循环，外层循环对子数 组集合进行遍历，内层循环根据子数组中的ID对每个四面体单元进行处理。 有益效果 4 CN 111598991 A 说　明　书 3/7 页 本发明基于现有的投影四面体算法进行改进，大幅度提升了算法的效率。硬件技 术发展十分迅速，对于一个四核的CPU，如果执行单线程的投影四面体算法，CPU占用只有 25％左右，同时当四面体网格数达到百万级别，单线程算法不能满足实时交互的需求。相比 之下，多线程版本的算法可以充分利用单块CPU的计算资源，且能大幅度提升算法效率。本 发明中通过多线程并行的方法对现有的投影四面体算法进行加速处理，对于四核CPU，采用 四个线程进行并发执行，CPU资源的占用会达到90％以上，可以充分利用CPU计算资源，同时 算法效率大幅度提升，可以满足实时交互需求。相比于目前的单线程投影四面体算法，本发 明中提出的多线程算法设计上有如下优点： (1)可见性排序算法：当视线方向发生变化时，四面体单元可见性顺序也会发生变 化。因此，可见性排序在进行交互的时候会不断进行，需要高效的排序算法才能满足需求， 目前的排序算法大多是串行版本，效率较高的为快速排序算法。本发明中先将待排序的数 组划为若干个子数组，要求子数组的数值区间没有交集，处理后子数组之间的数据独立，使 用多线程对子数组排序，不会影响最终排序结果，同时可以提高排序效率。 (2)四面体投影分类和拆分：对于排序后的每个四面体都需要进行投影分类和拆 分，拆分得到的顶点数据必须以正确的顺序载入显存，为了保证多线程执行下顶点数据存 储的正确顺序，本发明将所有四面体投影归为一类，即任意四面体投影拆分后均产生4个三 角形。当循环处理四面体单元时，产生的顶点数据可以根据当前的循环迭代变量经过计算 偏移量存储到顶点数组中的正确位置，即使在多线程执行顺序未知的情况下也能保证顶点 数据的正确顺序，经过多线程并行处理的循环不仅充分利用CPU计算资源，而且大幅度提升 了四面体投影分类和拆分的效率。 附图说明 图1PT算法投影多边形形状分类。 图2四种投影多边形的拆分方法。 图3光线投射过程。 图4算法流程图。 图5四面体投影。