A “Group Marching Cube” (GMC) Algorithm for Speeding up the Marching Cube Algorithm

Lih-Shyang CHEN; Young-Jinn LAY; Je-Bin HUANG; Yan-De CHEN; Ku-Yaw CHANG; Shao-Jer CHEN

doi:10.1587/transinf.E94.D.1289

A “Group Marching Cube” (GMC) Algorithm for Speeding up the Marching Cube Algorithm

Lih-Shyang CHEN, Young-Jinn LAY, Je-Bin HUANG, Yan-De CHEN, Ku-Yaw CHANG, Shao-Jer CHEN

Full Text Views

0

Share
Cite this

Summary :

Although the Marching Cube (MC) algorithm is very popular for displaying images of voxel-based objects, its slow surface extraction process is usually considered to be one of its major disadvantages. It was pointed out that for the original MC algorithm, we can limit vertex calculations to once per vertex to speed up the surface extraction process, however, it did not mention how this process could be done efficiently. Neither was the reuse of these MC vertices looked into seriously in the literature. In this paper, we propose a “Group Marching Cube” (GMC) algorithm, to reduce the time needed for the vertex identification process, which is part of the surface extraction process. Since most of the triangle-vertices of an iso-surface are shared by many MC triangles, the vertex identification process can avoid the duplication of the vertices in the vertex array of the resultant triangle data. The MC algorithm is usually done through a hash table mechanism proposed in the literature and used by many software systems. Our proposed GMC algorithm considers a group of voxels simultaneously for the application of the MC algorithm to explore interesting features of the original MC algorithm that have not been discussed in the literature. Based on our experiments, for an object with more than 1 million vertices, the GMC algorithm is 3 to more than 10 times faster than the algorithm using a hash table. Another significant advantage of GMC is its compatibility with other algorithms that accelerate the MC algorithm. Together, the overall performance of the original MC algorithm is promoted even further.

Publication: IEICE TRANSACTIONS on Information Vol.E94-D No.6 pp.1289-1298

Publication Date: 2011/06/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E94.D.1289

Type of Manuscript: PAPER

Category: Computer Graphics

Cite this

Copy

Lih-Shyang CHEN, Young-Jinn LAY, Je-Bin HUANG, Yan-De CHEN, Ku-Yaw CHANG, Shao-Jer CHEN, "A “Group Marching Cube” (GMC) Algorithm for Speeding up the Marching Cube Algorithm" in IEICE TRANSACTIONS on Information, vol. E94-D, no. 6, pp. 1289-1298, June 2011, doi: 10.1587/transinf.E94.D.1289.
Abstract: Although the Marching Cube (MC) algorithm is very popular for displaying images of voxel-based objects, its slow surface extraction process is usually considered to be one of its major disadvantages. It was pointed out that for the original MC algorithm, we can limit vertex calculations to once per vertex to speed up the surface extraction process, however, it did not mention how this process could be done efficiently. Neither was the reuse of these MC vertices looked into seriously in the literature. In this paper, we propose a “Group Marching Cube” (GMC) algorithm, to reduce the time needed for the vertex identification process, which is part of the surface extraction process. Since most of the triangle-vertices of an iso-surface are shared by many MC triangles, the vertex identification process can avoid the duplication of the vertices in the vertex array of the resultant triangle data. The MC algorithm is usually done through a hash table mechanism proposed in the literature and used by many software systems. Our proposed GMC algorithm considers a group of voxels simultaneously for the application of the MC algorithm to explore interesting features of the original MC algorithm that have not been discussed in the literature. Based on our experiments, for an object with more than 1 million vertices, the GMC algorithm is 3 to more than 10 times faster than the algorithm using a hash table. Another significant advantage of GMC is its compatibility with other algorithms that accelerate the MC algorithm. Together, the overall performance of the original MC algorithm is promoted even further.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.E94.D.1289/_p

Copy

@ARTICLE{e94-d_6_1289,
author={Lih-Shyang CHEN, Young-Jinn LAY, Je-Bin HUANG, Yan-De CHEN, Ku-Yaw CHANG, Shao-Jer CHEN, },
journal={IEICE TRANSACTIONS on Information},
title={A “Group Marching Cube” (GMC) Algorithm for Speeding up the Marching Cube Algorithm},
year={2011},
volume={E94-D},
number={6},
pages={1289-1298},
abstract={Although the Marching Cube (MC) algorithm is very popular for displaying images of voxel-based objects, its slow surface extraction process is usually considered to be one of its major disadvantages. It was pointed out that for the original MC algorithm, we can limit vertex calculations to once per vertex to speed up the surface extraction process, however, it did not mention how this process could be done efficiently. Neither was the reuse of these MC vertices looked into seriously in the literature. In this paper, we propose a “Group Marching Cube” (GMC) algorithm, to reduce the time needed for the vertex identification process, which is part of the surface extraction process. Since most of the triangle-vertices of an iso-surface are shared by many MC triangles, the vertex identification process can avoid the duplication of the vertices in the vertex array of the resultant triangle data. The MC algorithm is usually done through a hash table mechanism proposed in the literature and used by many software systems. Our proposed GMC algorithm considers a group of voxels simultaneously for the application of the MC algorithm to explore interesting features of the original MC algorithm that have not been discussed in the literature. Based on our experiments, for an object with more than 1 million vertices, the GMC algorithm is 3 to more than 10 times faster than the algorithm using a hash table. Another significant advantage of GMC is its compatibility with other algorithms that accelerate the MC algorithm. Together, the overall performance of the original MC algorithm is promoted even further.},
keywords={},
doi={10.1587/transinf.E94.D.1289},
ISSN={1745-1361},
month={June},}

Copy

TY - JOUR
TI - A “Group Marching Cube” (GMC) Algorithm for Speeding up the Marching Cube Algorithm
T2 - IEICE TRANSACTIONS on Information
SP - 1289
EP - 1298
AU - Lih-Shyang CHEN
AU - Young-Jinn LAY
AU - Je-Bin HUANG
AU - Yan-De CHEN
AU - Ku-Yaw CHANG
AU - Shao-Jer CHEN
PY - 2011
DO - 10.1587/transinf.E94.D.1289
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E94-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 2011
AB - Although the Marching Cube (MC) algorithm is very popular for displaying images of voxel-based objects, its slow surface extraction process is usually considered to be one of its major disadvantages. It was pointed out that for the original MC algorithm, we can limit vertex calculations to once per vertex to speed up the surface extraction process, however, it did not mention how this process could be done efficiently. Neither was the reuse of these MC vertices looked into seriously in the literature. In this paper, we propose a “Group Marching Cube” (GMC) algorithm, to reduce the time needed for the vertex identification process, which is part of the surface extraction process. Since most of the triangle-vertices of an iso-surface are shared by many MC triangles, the vertex identification process can avoid the duplication of the vertices in the vertex array of the resultant triangle data. The MC algorithm is usually done through a hash table mechanism proposed in the literature and used by many software systems. Our proposed GMC algorithm considers a group of voxels simultaneously for the application of the MC algorithm to explore interesting features of the original MC algorithm that have not been discussed in the literature. Based on our experiments, for an object with more than 1 million vertices, the GMC algorithm is 3 to more than 10 times faster than the algorithm using a hash table. Another significant advantage of GMC is its compatibility with other algorithms that accelerate the MC algorithm. Together, the overall performance of the original MC algorithm is promoted even further.
ER -