An international conference connecting people
in CAD research, education and business
Bookmark and Share
Copyright (C) CAD Solutions, LLC. All rights reserved.
Proceedings of CAD'17, 2017, 32-36
A Hybrid Solution to Calculating Augmented Join Trees of 2D Scalar Fields in Parallel

Paul Rosen, Junyi Tu, Les A. Piegl, University of South Florida

Abstract.  In CAD applications, scalar fields are used to describe a variety of details from photographs, to laser scans, to x-ray, CT or MRI of machine parts. These scalar fields are invaluable for a variety of tasks, such as fatigue detection in parts. However, analyzing scalar fields can be quite challenging due to their size, complexity, and the need to understand both local details and global context. Join trees are the key data structure used in the computation of merge trees, split trees, and contour trees. By capturing geometric properties, including local minima, local maxima, and saddle points, these trees are useful in the evaluation and simplification (i.e. denoising) of scalar field data. However, computing these trees is expensive, and their incremental construction makes parallel computation nontrivial. In its naïve implementation, the algorithm to compute join trees seems efficient. It has an O( n lg n ) sort phase and O( n + k ) computation phase, where n is the number of elements in the scalar field and k is the aggregate cost of the find operation of a disjoint-set data structure. However, this algorithm has three practical challenges. First, as the dimensions of the field are doubled, the number of elements, n, in 2D fields grow quadratically. Secondly, the compute time per element in the computation phase is very high. Third, the computation phase requires ordered incremental construction, making it challenging to parallelize.

Keywords. Data Analysis, Computational Topology, Scalar Field

DOI: 10.14733/cadconfP.2017.32-36