Evaluation of Manifold Dual Contouring Algorithms Based on K-d Tree and Octree Data Structures
DOI:
https://doi.org/10.31449/inf.v48i3.5420Abstract
This study evaluated the performance and efficiency of manifold dual contouring algorithms using k-d trees and octrees, therefore, addressing a critical gap in comparative analysis of these data structures. Despite the popularity of k-d trees and octrees in isosurface extraction, their performance has not been empirically compared. This research specifically focuses on visualization quality, performance metrics, and efficiency across various simplification error thresholds. A comprehensive comparative analysis was conducted to identify the conditions under which each data structure is most suitable. Both algorithms employed the manifold vertex clustering scheme for dual contouring of isosurfaces. The methodology involved evaluating visual output, build time, extraction time,and efficiency based on triangle counts during the simplification process. Computational experiments demonstrated that the octree-based algorithm is superior for rendering large models, producing an average of 20% more visual detail due to a higher triangle count. In contrast, the k-d tree-based algorithm showed a 40% reduction in build time and a 35% reduction in extraction time, making it more efficient for processing large implicit models by reducing geometric complexity. These findings provide metrics to assist researchersand practitioners in selecting the most suitable adaptive data structure for achieving optimal simplification results in manifold dual contouring algorithm implementations.References
C. Hansen, C. Johnson, The visualization handbook, Cambridge, MA: Academic Press, 2004.
I. Bankman, Handbook of medical image processing and analysis, Cambridge, MA: Academic Press, 2009.
J. O’Brien, G. Turk, Modelling with implicit surfaces that interpolate, ACM Transactions on Graphics 21 (2002) 855–873.
M. Edmunds, R. Laramee, G. Chen, N. Max, E. Zhang, C. Ware, Surface-based flow visualization, Computers Graphics 36 (2012)
–990.
W. Lorensen, H. Cline, Marching cubes: A high resolution 3d surface construction algorithm, ACM SIGGRAPH Computer Graphics
(1987) 163–169.
S. Schaefer, J.Warren, Dual marching cubes: Primal contouring of dual grids, in: Proceedings of the Pacific Conference on Computer
Graphics and Applications, 2004, pp. 70–76.
S.-W. Lee, H.-Y. Jung, R. Prost, A. Senot, Regularized marching cubes mesh, in: Proceedings of the IEEE International Conference
on Image Processing, volume 3, 2005, pp. 788–791.
J. Jin, Q. Wang, Y. Shen, J. Hao, An improved marching cubes method for surface reconstruction of volume data, in: Proceedings
of the World Congress on Intelligent Control and Automation, volume 2, 2006, pp. 10454–10457.
R. Strand, P. Stelldinger, Topology preserving marching cubes-like algorithms on the face-centered cubic grid, in: Proceedings of
the 14th International Conference on Image Analysis and Processing, 2007, pp. 781–788.
Z. Xu, C. Xiao, X. Xu, An improved marching cubes algorithm based on edge contraction, in: Proceedings of the International
Conference on Signal Processing Proceedings, 2010.
G. Vignoles, M. Donias, C. Mulat, C. Germain, J.-F. Delesse, Simplified marching cubes: an efficient discretization scheme for
simulations of deposition/ablation in complex media, Computational Materials Science 50 (2011) 893–902.
Q. Du, J. Zhao, L. Shi, L. Wang, Efficient improved marching cubes algorithm, in: Proceedings of the 2nd International Conference
on Computer Science and Network Technology, 2012, pp. 416–419.
A. Greß, R. Klein, Efficient representation and extraction of 2-manifold isosurfaces using kd-trees, in: Proceedings of the 11th Pacific Conference on Computer Graphics and Applications, 2003, pp. 370–397.
J. Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM 18 (1975) 509–517.
D. Meagher, Octree generation, analysis and manipulation, Ph.D. thesis, Rensselaar Polytechnic Institute, Troy New York, 1982.
T. Ju, F. Losasso, S. Schaefer, J. Warren, Dual contouring of hermite data, ACM Transactions on Graphics 21 (2002) 339–346.
J.-D. Boissonnat, S. Oudot, Provably good sampling and meshing of surfaces, Graphical Models 67 (2005) 405–451.
M. Garland, P. Heckbert, Surface simplification using quadric error metrics, in: Proceedings of the ACM SIGGRAPH Conference on
Computer Graphics, 1997, p. 209–216.
Y. Livnat, C. Hansen, C. Johnson, Isosurface extraction for large-scale data sets, in: Proceedings of the Conference on Data Visualization: The State of the Art, 2003, pp. 77–94.
T. Newman, H. Yi, A survey of the marching cubes algorithm, Computers Graphics 30 (2006) 854–879.
D. Rajon, W. Bolch, Marching cube algorithm: review and trilinear interpolation adaptation for image-based dosimetric models,
Computerized Medical Imaging and Graphics 27 (2003) 411–435.
C. Maple, Geometric design and space planning of the International Conference on Geometric Modeling and Graphics, 2003, pp. 90–95.
C. Andujar, P. Brunet, A. Chica Calaf, J. Rossignac, A. Vinacua, Optimizing the topological and combinatorial complexity of
isosurfaces, Computer-Aided Design 37 (2005) 847–857.
X. Renbo, L. Weijun, Y. Wang, A robust and topological correct marching cube algorithm without look-up table, in: Proceedings of the 5th International Conference on Computer and Information Technology, 2005, pp. 565–569.
N. Chrisochoides, D. Nave, Simultaneous mesh generation and partitioning for delaunay meshes, Mathematics and Computers in Simulation 54 (1999) 321–339.
S. H. Cui, J. Liu, Simplified patterns for extracting the isosurfaces of solid objects, Image and Vision Computing 26 (2008) 339–346.
T. Etiene, C. Scheidegger, L. Nonato, R. Kirby, C. Silva, Verifiable visualization for isosurface extraction, IEEE Transactions on Visualization and Computer Graphics 15 (2009) 1227–1234.
Q. Xiaoqing, W. Davis, An extended cuberille model for identification and display of 3d objects from 3d gray value data, in: Proceedings of the Conference on Graphics Interface, 1992, pp. 70–77.
L. Custodio, T. Etiene, S. Pesco, C. Silva, Practical considerations on marching cubes 33 topological correctness, Computers Graphics 37 (2013) 840–850.
E. Tcherniaev, Marching cubes 33: Construction of topologically correct isosurfaces, Technical Report, Institute for High Energy Physics, 1996.
T. Lewiner, H. Lopes, A. Vieira, G. Tavares, Efficient implementation of marching cubes’ cases with topological guarantees, Journal of Graphics Tools 8 (2012) 1–15.
J. Chen, X. Jin, Gpu-based polygonization and optimization for implicit surfaces, The Visual Computer 31 (2014) 119–130.
T. Athawale, E. Sakhaee, E. Alireza, Isosurface visualization of data with nonparametric models for uncertainty, IEEE Transactions
on Visualization and Computer Graphics 22 (2015) 777–786.
Y. Ronghuan, X. Wei, W. Lingda, H. Hongxing, Research on multi-resolution isosurface extraction method for 3d scalar field, in: Proceedings of the 2nd IEEE International Conference on Data Science in Cyberspace, 2017, pp. 359–362.
N. Zhang, W. Hong, A. Kaufman, Dual contouring with topology-preserving simplification using enhanced cell representation, in:
Proceedings of the IEEE Visualization Conference, 2004, pp. 505–512.
S. Schaefer, T. Ju, J. Warren, Manifold dual contouring, IEEE Transactions on Visualization and Computer Graphics 13 (2007) 610–619.
Y. Zhang, J. Qian, Dual contouring for domains with topology ambiguity, Computer Methods in Applied Mechanics and Engineering 217–220 (2012) 34–45.
X. Liang, Y. Zhang, An octree-based dual contouring method for triangular and tetrahedral mesh generation with guaranteed angle
range, Engineering with Computers 30 (2014) 211–222.
A. Peixoto, C. Moura, Topology preserving algorithms for implicit surfaces simplifying and sewing, in: Proceedings of the International
Conference on Computational Science and Its Applications, 2014, pp. 352–367.
T. Rashid, S. Sharmin, M. Audette, Watertight and 2-manifold surface meshes using dual contouring with tetrahedral decomposition
of grid cubes, Procedia Engineering 163 (2016) 136–148.
G. Varadhan, S. Krishnan, Y. Kim, D. Manocha, Feature-sensitive subdivision and isosurface reconstruction, in: Proceedings of the IEEE Visualization Conference, 2003, pp. 99–106.
G. Nielson, Dual marching cubes, in: Proceedings of the IEEE Visualization Conference, 2004, pp. 489–496.
S. Kim, Y. Ohtake, Y. Nagai, H. Suzuki, A novel interpolation scheme for dual marching cubes on octree volume fraction data, Computers and Graphics 66 (2017) 169–178.
R. Grosso, D. Zint, A parallel dual marching cubes approach to quad only surface reconstruction, The Visual Computer 38 (2022) 1301–1316.
Y. He, M. Mirzargar, S. Hudson, M. Kirby, R. Whitaker, An uncertainty visualization technique using possibility theory: Possibilistic marching cubes, International Journal for Uncertainty Quantification 5 (2015) 433–451.
D. El-Rushaidat, R. Yeh, X. Tricoche, Accurate parallel reconstruction of unstructured datasets on rectilinear grids, Journal of Visualization 24 (2021) 787–806.
J. Stewart, Calculus early transcendentals, Cengage Learning, 2015.
Downloads
Published
How to Cite
Issue
Section
License
I assign to Informatica, An International Journal of Computing and Informatics ("Journal") the copyright in the manuscript identified above and any additional material (figures, tables, illustrations, software or other information intended for publication) submitted as part of or as a supplement to the manuscript ("Paper") in all forms and media throughout the world, in all languages, for the full term of copyright, effective when and if the article is accepted for publication. This transfer includes the right to reproduce and/or to distribute the Paper to other journals or digital libraries in electronic and online forms and systems.
I understand that I retain the rights to use the pre-prints, off-prints, accepted manuscript and published journal Paper for personal use, scholarly purposes and internal institutional use.
In certain cases, I can ask for retaining the publishing rights of the Paper. The Journal can permit or deny the request for publishing rights, to which I fully agree.
I declare that the submitted Paper is original, has been written by the stated authors and has not been published elsewhere nor is currently being considered for publication by any other journal and will not be submitted for such review while under review by this Journal. The Paper contains no material that violates proprietary rights of any other person or entity. I have obtained written permission from copyright owners for any excerpts from copyrighted works that are included and have credited the sources in my article. I have informed the co-author(s) of the terms of this publishing agreement.
Copyright © Slovenian Society Informatika
