有些体数据生成的等值面过大，超过了内存的装载能力。如果将这些网格完全生成出来再使用out-of-core简化，会使得整个处理过程耗时过长。本论文提出了在内存中生成一部分等值面就进行简化的方法。以往同类型的方法因为需要不断输出简化的网格使简化质量打了折扣，且它们对顶点何时退出生成边界的判断没有充分考虑体数据本身的特性。本论文的方法在内存中保持了一个全局的简化操作最优队列，尽量保证他们能够得到更多比较；并结合体数据生成的特点，来指导算法获知顶点何时离开生成边界，使得简化过程内存占用较小且具有可预测性。本论文还在生成过程中对等值面的拓扑关系进行了重建。经测试，本论文的算法能够在较短时间内产生类似于高质量内存简化的结果。

直接对体数据进行自适应的等值面生成能够对等值面进行自动简化，但大部分自适应等值面生成算法无法保证生成的网格流形且无自交。有一种基于对体数据八叉树单形分割的串行算法能够解决这个问题。本论文在原先串行单形分割算法的基础上，对分割方法做了简化以减少体数据函数近似产生的误差，并对它做了并行的改进。本论文算法的主要贡献是提供了一套完整的基于GPU并行的八叉树建立与最小边查找方法。它自顶向下分层建立八叉树，并在查找最小边的时候，将当前一层边的分割结果与当前一层八叉树节点所展开的新边、当前一层面分割所引入的新边一起加入到下一层待分割的边中。在实际测试中，本论文的算法能够产生流形且无自交的自适应等值面，并在处理大规模数据时获得了相对于串行算法较高的加速比。

In this paper, we first propose a simplification algorithm for massive meshes based on cutting the mesh into pieces by partition the vertices instead of the triangles. The trianlge boundaries generated by the vertex-seperating approach need not be preserved during the simplification of each piece. The edge collapse operator we use can keep the topology change of each mesh piece independent from the others automatically, which makes it possible for the bounadaries to be simplified. Such an algorithm needs only one simplification process over the whole mesh without further processing. When stitching the pieces, we only keep the boundary vertices in memory without caching the whole simplified mesh, so our algorithm can generate large simplfied meshes which cannot be loaded into the main memory.

Second, we propose an on-the-fly simplification algorithm for massive isosurfaces which the main memory is not able to hold if fully generated. We use the edge collapse operator and keep the generation boundary unchanged. The boundary marches through the whole mesh as isosurfaces generated. We reconstruct the topology of the original Marching Cubes surfaces for in-core simplification algorithm. To determine when the primitives in the mesh can be modified, we classify the vertices generated by Marching Cubes algorithm and finalize them based on different rules. When a vertex is finalized, it leaves the generation boundary and becomes collapsable. We keep an collapsalbe edge priority queue all along the simplification process and try to make more operators to compare. Thus, simplification quality can be enhanced.

Finally, we propose an adaptive isosurface generation algorithm based on simplicial complex partition of the volume data octree, which is parallel on GPU. This approach can generate manifold and intersection-free isosurfaces without any crack. Our main contribution is that we provide a group of parallel algorithms for building the octrees and traversing the minimal edges on GPU. We build the octree from top to the bottom and calculate the dual vertices, error incurred from expanding the nodes and configuration of child nodes in parallel for each layer. We use a parallel scan to calculate the offset of child nodes and keep a starting offset as well as a count of child nodes for each parent node as pointers to its children. In our octree data structures, all nodes are stored layer by layer in the GPU memory. In each layer, nodes with identical parent are stored continuously. When traversing the minimal edges, we caculate the splitting number of each edge corresponding to a layer and use a parellel array partition to separate the minimal edges and splittable edges. We also add the new edges incurred from expanding the nodes to the need-to-split edge array for the next layer. We form tetrahedron for each minimal edge and generate isosurfaces from the tertrahedron.

 

Key Words: Massive Mesh; Mesh Cutting; Streaming Processing; Simplicial Partition; Parallel Octree