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

Description:

 

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.

Paper download:  (21.4 MB)

Videos:

Paper video (application cases):

Virtual paper presentation at Eurographics 2021:

Fast-Forward for paper presentation at Eurographics 2021:

Get the videos:

Reference:

Yucheng Lu, Luyu Cheng, Tobias Isenberg, Chi-Wing Fu, Guoning Chen, Hui Liu, Oliver Deussen, and Yunhai Wang (2021) Curve Complexity Heuristic KD-trees for Neighborhood-based Exploration of 3D Curves. Computer Graphics Forum, 40(2):461–474, May 2021.
×

BibTeX entry:



@ARTICLE{Lu:2021:CCH,
  author      = {Yucheng Lu and Luyu Cheng and Tobias Isenberg and Chi-Wing Fu and Guoning Chen and Hui Liu and Oliver Deussen and Yunhai Wang},
  title       = {Curve Complexity Heuristic {KD}-trees for Neighborhood-based Exploration of {3D} Curves},
  journal     = {Computer Graphics Forum},
  year        = {2021},
  volume      = {40},
  number      = {2},
  month       = may,
  pages       = {461--474},
  doi         = {10.1111/cgf.142647},
  doi_url     = {https://doi.org/10.1111/cgf.142647},
  oa_hal_url  = {https://hal.science/hal-03151998},
  url         = {https://tobias.isenberg.cc/p/Lu2021CCH},
  url2        = {http://www.yunhaiwang.net/EG2021/curve/},
  pdf         = {https://tobias.isenberg.cc/personal/papers/Lu_2021_CCH.pdf},
}

This work was done at and in collaboration with the Interactive Data Exploration System (IDEAS) lab headed by Yunhai Wang at School of Computer Science and Technology, Shandong University, China, and several other collaborators. Also see the project webpage on Yunhai Wang's lab website.