摘  要

三维模型的网格简化算法提出了挑战，很多不同的技术都试图在大数据的外存访问效率和网格的简化质量中间取得平衡，有的方法只顾及了一方面，有的能做到两者兼顾。本论文的方法能兼顾大数据访问效率和简化质量，相比同类型的方法，它只需要对网格做一次处理，且能处理输出网格无法载入内存的情况。本论文的方法对网格中顶点而非三角形进行分片，同时所使用的边收缩操作对分片中顶点的拓扑结构改变可以保持在分片之内，边界简化因此变得可能。在一次简化处理之内，简化的网格在分片边界处不会出现密度不一致的情况，因此不需再做处理。经测试表明，本论文的算法能够在较短的时间内提供和内存简化算法相比拟的简化质量。

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

关键词：大规模网格；网格分片；流式处理；单形分割；并行八叉树

Abstract

The grid simplification algorithm of 3 D models poses challenges. Many different techniques try to balance the external access efficiency of big data with the simplified quality of the grid. Some methods take only on one thing, while others can do both. The method of this paper can take into account the efficiency of big data access and the simplified quality. Compared with the same type of method, it only needs to process the grid once, and can handle the situation where the output grid cannot be loaded in memory. The method of this paper sharhes the vertices in the grid, and the edge shrinkage operation can keep the topology change within the grid, so that the boundary simplification becomes possible. Within a simplified process, the simplified grid will not have the density inconsistency at the fragmentation boundary, so there is no further processing.

The is shows that the algorithm in this paper can provide simplified quality compared to the memory simplification algorithm in a short time. Based on the original serial monorphic segmentation algorithm, the segmentation method is simplified to reduce the error caused by the bulk data function and improved in parallel. The main contribution of the algorithm in this paper is to provide a complete set of GPU parallel-based octet tree building with minimal edge finding methods. It establishes the octa tree from top down, and when finding the smallest edge, adds the segmentation result of the current layer edge with the new edge and the new edge introduced by the current layer segmentation of the next layer. In practical testing, the algorithm in this paper is able to produce a manifold without selfing adaptive isosurface and achieves high speed-up ratios relative to the serial algorithm when processing large-scale data.

KEY WORDS:  Massive Mesh; Mesh Cutting; Streaming Processing; Simplicial Partition; Parallel Octree