Evaluation of Manifold Dual Contouring Algorithms Based on K-d Tree and Octree Data Structures
Abstract
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 researchers
and practitioners in selecting the most suitable adaptive data structure for achieving optimal simplification results in manifold dual contouring algorithm implementations.
Full Text:
PDFReferences
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.
DOI: https://doi.org/10.31449/inf.v48i3.5420
This work is licensed under a Creative Commons Attribution 3.0 License.