Article

Free access

Sweeping Simplices: A Fast Iso-Surface Extraction Algorithm for Unstructured Grids

Authors:

Han-Wei Shen,

Christopher R. JohnsonAuthors Info & Claims

VIS '95: Proceedings of the 6th conference on Visualization '95

Page 143

Published: 29 October 1995 Publication History

PDF eReader Publisher Site

Abstract

We present an algorithm that accelerates the extraction of iso-surfaces from unstructured grids by avoiding the traversal of the entire set of cells in the volume. The algorithm consists of a sweep algorithm and a data decomposition scheme. The sweep algorithm incrementally locates intersected elements, and the data decomposition scheme restricts the algorithm's worst-case performance. For data sets consisting of hundreds of thousands of elements, our algorithm can reduce the cell traversal time more than 90% over the naive iso-surface extraction algorithm, thus facilitating interactive probing of scalar fields for large-scale problems on unstructured three-dimensional grids.

References

[1]

[1] W. E. Lorensen and H. E. Cline. Marching cubes: A high resolution 3d surface construction algorithm. Computer Graphics, 21(4):163-169, July 1987.

Digital Library

Google Scholar

[2]

[2] J. Wilhelms and A. Van Gelder. Octrees for faster isosurface generation. ACM Transactions on Graphics, 11(3):201-227, July 1992.

Digital Library

Google Scholar

[3]

[3] M. Giles and R. Haimes. Advanced interactive visualization for CFD. Computing Systems in Engineering , 1(1):51-62, 1990.

Digital Library

Google Scholar

[4]

[4] R. S. Gallagher. Span filter: An optimization scheme for volume visualization of large finite element models. In Proceedings of Visualization '91, pages 68-75. IEEE Computer Society Press, Los Alamitos, CA, 1991.

Digital Library

Google Scholar

[5]

[5] J. Wernecke. The Inventor Mentor. Addison-Wesley Publishing Company, 1994.

Google Scholar

[6]

[6] J. Neider, T. Davis and M. Woo. Open GL Programming Guide. Addison-Wesley Publishing Company, 1993.

Google Scholar

Cited By

View all

Tsuzuki MSato AUeda EMartins TTakimoto RIwao YAbe LGotoh TKagei S(2018)Propagation-based marching cubes algorithm using open boundary loopThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-017-1417-234:10(1339-1355)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s00371-017-1417-2
Martin SShen HMcCormick P(2010)Load-balanced isosurfacing on multi-GPU clustersProceedings of the 10th Eurographics conference on Parallel Graphics and Visualization10.5555/2386208.2386223(91-100)Online publication date: 2-May-2010
https://dl.acm.org/doi/10.5555/2386208.2386223
Zhou YGarland MHaber R(2004)Pixel-Exact Rendering of Spacetime Finite Element SolutionsProceedings of the conference on Visualization '0410.1109/VISUAL.2004.81(425-432)Online publication date: 10-Oct-2004
https://dl.acm.org/doi/10.1109/VISUAL.2004.81
Show More Cited By

Recommendations

Isosurface stuffing: fast tetrahedral meshes with good dihedral angles

The isosurface stuffing algorithm fills an isosurface with a uniformly sized tetrahedral mesh whose dihedral angles are bounded between 10.7° and 164.8°, or (with a change in parameters) between 8.9° and 158.8°. The algorithm is whip fast, numerically ...
Isosurface stuffing: fast tetrahedral meshes with good dihedral angles
SIGGRAPH '07: ACM SIGGRAPH 2007 papers

The isosurface stuffing algorithm fills an isosurface with a uniformly sized tetrahedral mesh whose dihedral angles are bounded between 10.7° and 164.8°, or (with a change in parameters) between 8.9° and 158.8°. The algorithm is whip fast, numerically ...
Nonconforming Mesh Refinement for High-Order Finite Elements

We propose a general algorithm for nonconforming adaptive mesh refinement (AMR) of unstructured meshes in high-order finite element codes. Our focus is on $h$-refinement with a fixed polynomial order. The algorithm handles triangular, quadrilateral, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

VIS '95: Proceedings of the 6th conference on Visualization '95

October 1995

478 pages

ISBN:0818671874

Publisher

IEEE Computer Society

United States

Publication History

Published: 29 October 1995

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
392
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)10

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Tsuzuki MSato AUeda EMartins TTakimoto RIwao YAbe LGotoh TKagei S(2018)Propagation-based marching cubes algorithm using open boundary loopThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-017-1417-234:10(1339-1355)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s00371-017-1417-2
Martin SShen HMcCormick P(2010)Load-balanced isosurfacing on multi-GPU clustersProceedings of the 10th Eurographics conference on Parallel Graphics and Visualization10.5555/2386208.2386223(91-100)Online publication date: 2-May-2010
https://dl.acm.org/doi/10.5555/2386208.2386223
Zhou YGarland MHaber R(2004)Pixel-Exact Rendering of Spacetime Finite Element SolutionsProceedings of the conference on Visualization '0410.1109/VISUAL.2004.81(425-432)Online publication date: 10-Oct-2004
https://dl.acm.org/doi/10.1109/VISUAL.2004.81
Livnat YTricoche X(2004)Interactive Point-Based Isosurface ExtractionProceedings of the conference on Visualization '0410.1109/VISUAL.2004.52(457-464)Online publication date: 10-Oct-2004
https://dl.acm.org/doi/10.1109/VISUAL.2004.52
von Rymon-lipinski BHanssen NJansen TRitter LKeeve E(2004)Efficient Point-Based Isosurface Exploration Using the Span-TriangleProceedings of the conference on Visualization '0410.1109/VISUAL.2004.29(441-448)Online publication date: 10-Oct-2004
https://dl.acm.org/doi/10.1109/VISUAL.2004.29
Chhugani JVishwanath SCohen JKumar SBonneau GHahmann SHansen C(2003)ISOSLIDERProceedings of the symposium on Data visualisation 200310.5555/769922.769951(259-266)Online publication date: 26-May-2003
https://dl.acm.org/doi/10.5555/769922.769951
Chiang Y(2003)Out-of-Core Isosurface Extraction of Time-Varying Fields over Irregular GridsProceedings of the 14th IEEE Visualization 2003 (VIS'03)10.1109/VISUAL.2003.1250375Online publication date: 22-Oct-2003
https://dl.acm.org/doi/10.1109/VISUAL.2003.1250375
Bordoloi UShen H(2003)Space Efficient Fast Isosurface Extraction for Large DatasetsProceedings of the 14th IEEE Visualization 2003 (VIS'03)10.1109/VISUAL.2003.1250373Online publication date: 22-Oct-2003
https://dl.acm.org/doi/10.1109/VISUAL.2003.1250373
Banks DLinton S(2003)Counting Cases in Marching CubesProceedings of the 14th IEEE Visualization 2003 (VIS'03)10.1109/VISUAL.2003.1250354Online publication date: 22-Oct-2003
https://dl.acm.org/doi/10.1109/VISUAL.2003.1250354
Cox JKarron DFerdous N(2003)Topological Zone Organization of Scalar Volume DataJournal of Mathematical Imaging and Vision10.1023/A:102211311431118:2(95-117)Online publication date: 1-Mar-2003
https://dl.acm.org/doi/10.1023/A%3A1022113114311
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Isosurface stuffing: fast tetrahedral meshes with good dihedral angles

Isosurface stuffing: fast tetrahedral meshes with good dihedral angles

Nonconforming Mesh Refinement for High-Order Finite Elements