Computer Graphics Forum (Proc. of Eurographics 2021),2021

Curve Complexity Heuristic KD-trees for Neighborhood-based Exploration of 3D Curves

Yucheng Lu, Luyu Cheng, Tobias Isenberg, Chi-Wing Fu, Guoning Chen, Hui Liu, Oliver Deussen, Yunhai Wang

cch figure 1

Figure 1: Neighborhood-based exploration of 3D line data. (a) Selecting nearest lines with a radius r around two query points (white boxes in (a)). For the top query point, the nearest lines are shown in blue, for the bottom query point in green. Lines in violet are close to both query points; (b) varying opacity for the line segments is specified by using a measure based on the nearest line segments as importance. This allows us to better display large-scale vortex structures than a measure based only on local curvature, as shown in (c); and (d) abstraction of DTI fiber tracts at the scale of 5mm based on our neighborhood search, only major paths are shown.


We introduce the curve complexity heuristic (CCH), a KD-tree construction strategy for 3D curves, which enables interactive exploration of neighborhoods in dense and large line datasets. It can be applied to searches of k-nearest curves (KNC) as well as radius-nearest curves (RNC). The CCH KD-tree construction consists of two steps: (i) 3D curve decomposition that takes into account curve complexity and (ii) KD-tree construction, which involves a novel splitting and early termination strategy. The obtained KD-tree allows us to improve the speed of existing neighborhood search approaches by at least an order of magnitude (i. e., 28× for KNC and 12× for RNC with 98% accuracy) by considering local curve complexity. We validate this performance with a quantitative evaluation of the quality of search results and computation time. Also, we demonstrate the usefulness of our approach for supporting various applications such as interactive line queries, line opacity optimization, and line abstraction.

cch figure 4

Figure 4: Overview of our two-stage method—offline pre-processing (a–c) and online query (d–g): (a) set of input curves with point samples (white) and split points (orange); (b) the CCH KD-treebuilt for the input curves with the removed split points (green) and the newly added split points (yellow), the split axes’ (blue) thickness indicates the level, where the thicker the lines are the higher levels of the KD-tree; (c) the curve segment in each grid cell is approximated by a straight-line segment; (d,e,f) three steps in retrieving the two nearest curves k=2k = 2 for the given query point qq, where the related split axes are highlighted in purple; (d) the first nearest curve C3C_3 with the nearest sample v1v_1 is found from the leaf node; (e) backtracking to the upper level and finding the two nearest samples v2v_2 and v3v_3, which are from the same curve as v1v_1, continued backtracking gives us a new nearest sample v4 from curve C4C_4; (f) further backtracking to find the nearest samples in the circle with radius from qq to v4v_4. A closer sample v6v_6 is found, resulting in the fact that v4 and v5 (in red) are rejected; (g) the nearest curves are C2C_2 and C3C_3 and the corresponding nearest samples are v1v_1 and v6v_6 for query point qq.

cch figure 10

Figure 10: Comparing curve recall (downward triangles), curve precision (upward triangles), and query time (circle marks) of the three methods for performing KNC searches (a,b) and RNC searches (c,d) within the aneurysm dataset. Note that the lines of curve recall and curve precision overlap together in KNC search (a), while they might not overlap in RNC search (b).

Copyright © IDEAS Lab 2023
Shandong Univeristy, Qingdao, China
Visitor Map powered by ClustrMaps