改进的Dividing Cubes算法及其并行实现

IMPROVED DIVIDING CUBES ALGORITHM AND ITS PARALLEL IMPLEMENTATION

体绘制是三维数据场可视化的有力工具，而并行处理则是最有希望使其达到交互式显示速度的途径．本文首先提出一种DividingCubes算法的改进方案，以节省该算法的执行时间和空间．更为重要的是，改进后的算法在不同视线方向下的绘制时间的差别大为减少，这对于在实时状态下匀速显示一连串视角微小变化的三维数据场非常重要．在此基础上，本文给出该算法的基于分布式内存的MIMD结构的并行实现方案．高效的静态数据分解策略使并行算法在绘制阶段的负载平衡度很高，而通信量很小．实验结果表明，我们的并行算法可以在配备9个处理器的PA’95加速器上，以每秒两帧以上的速度交互显示大小为128×128×197的数据场．

Volume rendering is a useful tool to visualize volumetric data. Paral-lelization is currently the most promising way to achieve interactive rendering rate.An improved version for the Dividing Cubes algorithm is proposed to shorten both time and memory expenses. More important, it greatly releases the variation in rendering time for different viewing directions, which is very important to produce smooth display of 3D data set in real-time from a series of slightly changed viewing angles. Based on the improved dividing cubes algorithm, a parallel implementation on a distributed memory MIMD architecture is presented. By using an efficient static data partitioning strategy, the load balance during the parallel rendering peri-od is very good, and the communication overhead is very low. Experiment results show that the parallel renderer can render a 128×128×197 dataset at more than 2frames per second on a 9 processor PA'95 Accelerator.