Evaluation of Manifold Dual Contouring Algorithms Based on K-d Tree and Octree Data Structures
Open Access
- 9 September 2024
- journal article
- Published by Slovenian Association Informatika in Informatica
- Vol. 48 (3)
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 researchersand practitioners in selecting the most suitable adaptive data structure for achieving optimal simplification results in manifold dual contouring algorithm implementations.Keywords
This publication has 45 references indexed in Scilit:
- A parallel dual marching cubes approach to quad only surface reconstructionThe Visual Computer, 2021
- Accurate parallel reconstruction of unstructured datasets on rectilinear gridsJournal of Visualization, 2021
- GPU-based polygonization and optimization for implicit surfacesThe Visual Computer, 2014
- Topology Preserving Algorithms for Implicit Surfaces Simplifying and SewingLecture Notes in Computer Science, 2014
- Practical considerations on Marching Cubes 33 topological correctnessComputers & Graphics, 2013
- An octree-based dual contouring method for triangular and tetrahedral mesh generation with guaranteed angle rangeEngineering with Computers, 2013
- Surface-based flow visualizationComputers & Graphics, 2012
- A survey of the marching cubes algorithmComputers & Graphics, 2006
- Optimizing the topological and combinatorial complexity of isosurfacesComputer-Aided Design, 2005
- Isosurface Extraction for Large-Scale Data Sets2003