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 researchersand practitioners in selecting the most suitable adaptive data structure for achieving optimal simplification results in manifold dual contouring algorithm implementations.