Fast Isosurface Generation Using the Volume Thinning Algorithm
Fast Isosurface Generation Using the Volume Thinning Algorithm
复制标题
使用体积细化算法快速生成等值面
DOI：
10.1109/2945.910819
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
K. Koyamada
中科院分区：
文献类型：
--
作者：
T. Itoh;Yasushi Yamaguchi;K. Koyamada
开发高效等值面算法的最有效的技术之一是减少对非等值面单元的访问。最近的算法已经大大减少了访问非等值面细胞的不必要的成本。实验结果表明，几乎最佳的性能，在他们的等值面过程。然而，它们中的大多数都有一个瓶颈，因为它们需要超过O（n）的计算时间来进行预处理，其中n表示细胞的总数。我们提出了一个有效的等值面技术，它可以应用于非结构化以及结构化的卷，它不需要超过O（n）的计算时间为它的预处理。预处理步骤通过体细化算法生成由单元格组成并连接所有极值点的极值骨架。每个等值面的所有不相交部分都与极值骨架中的至少一个单元相交。我们的实现生成等值面搜索等值面细胞的极值骨架，然后递归访问其相邻的等值面细胞，而它跳过了大部分的非等值面细胞。预处理的计算时间估计为O（n）。等值面过程的计算时间估计为O（n/sup 1/3/m+k），其中k表示等值面单元的数量，m表示极值点的数量，因为极值骨架中的单元的数量估计为O（n/sup 1/3/m）。
One of the most effective techniques for developing efficient isosurfacing algorithms is the reduction of visits to nonisosurface cells. Recent algorithms have drastically reduced the unnecessary cost of visiting nonisosurface cells. The experimental results show almost optimal performance in their isosurfacing processes. However, most of them have a bottleneck in that they require more than O(n) computation time for their preprocessing, where n denotes the total number of cells. We propose an efficient isosurfacing technique, which can be applied to unstructured as well as structured volumes and which does not require more than O(n) computation time for its preprocessing. A preprocessing step generates an extrema skeleton, which consists of cells and connects all extremum points, by the volume thinning algorithm. All disjoint parts of every isosurface intersect at least one cell in the extrema skeleton. Our implementation generates isosurfaces by searching for isosurface cells in the extrema skeleton and then recursively visiting their adjacent isosurface cells, while it skips most of the nonisosurface cells. The computation time of the preprocessing is estimated as O(n). The computation time of the isosurfacing process is estimated as O(n/sup 1/3/m+k), where k denotes the number of isosurface cells and m denotes the number of extremum points since the number of cells in an extrema skeleton is estimated as O(n/sup 1/3/m).