Task-based Augmented Contour Trees with Fibonacci Heaps
作者： J Tierny , J Jomier , P. Fortin , Charles Gueunet
DOI:
关键词:
摘要: This paper presents a new algorithm for the fast, shared memory, multi-core computation of augmented contour trees on triangulations. In contrast to most existing parallel algorithms our technique computes trees, enabling full extent tree based applications including data segmentation. Our approach completely revisits traditional, sequential re-formulate all steps as set independent local tasks. includes procedure Fibonacci heaps join and split two intermediate structures used compute tree, whose constructions are efficiently carried out concurrently thanks dynamic scheduling task parallelism. We also introduce combination these into output global tree. Overall, this results in superior time performance practice, both OpenMP runtime. report numbers that compare reference multi-threaded implementations merge trees. These experiments demonstrate run-time efficiency its scalability common workstations. utility segmentation applications.
arxiv.org参考文章(61)
M. de Berg, M. van Kreveld, Trekking in the Alps without freezing or getting tired Algorithmica. ,vol. 18, pp. 306- 323 ,(1997) , 10.1007/PL00009159
Dmitriy Morozov, Gunther H. Weber, Distributed Contour Trees Mathematics and Visualization. pp. 89- 102 ,(2014) , 10.1007/978-3-319-04099-8_6
Leila De Floriani, Ulderico Fugacci, Federico Iuricich, Paola Magillo, Morse complexes for shape segmentation and homological analysis: discrete models and algorithms Computer Graphics Forum. ,vol. 34, pp. 761- 785 ,(2015) , 10.1111/CGF.12596
A. Gyulassy, P.T. Bremer, R. Grout, H. Kolla, J. Chen, V. Pascucci, Stability of Dissipation Elements: A Case Study in Combustion eurographics. ,vol. 33, pp. 51- 60 ,(2014) , 10.1111/CGF.12361
Nithin Shivashankar, Pratyush Pranav, Vijay Natarajan, Rien van de Weygaert, E.G. Patrick Bos, Steven Rieder, Felix: A Topology Based Framework for Visual Exploration of Cosmic Filaments IEEE Transactions on Visualization and Computer Graphics. ,vol. 22, pp. 1745- 1759 ,(2016) , 10.1109/TVCG.2015.2452919
Attila Gyulassy, Aaron Knoll, Kah Chun Lau, Bei Wang, Peer-Timo Bremer, Michael E. Papka, Larry A. Curtiss, Valerio Pascucci, Interstitial and Interlayer Ion Diffusion Geometry Extraction in Graphitic Nanosphere Battery Materials IEEE Transactions on Visualization and Computer Graphics. ,vol. 22, pp. 916- 925 ,(2016) , 10.1109/TVCG.2015.2467432
Attila Gyulassy, David Günther, Joshua A Levine, Julien Tierny, Valerio Pascucci, None, Conforming Morse-Smale complexes IEEE Transactions on Visualization and Computer Graphics. ,vol. 20, pp. 2595- 2603 ,(2014) , 10.1109/TVCG.2014.2346434
Shen Dong, Peer-Timo Bremer, Michael Garland, Valerio Pascucci, John C. Hart, Spectral surface quadrangulation international conference on computer graphics and interactive techniques. ,vol. 25, pp. 1057- 1066 ,(2006) , 10.1145/1141911.1141993
B.-S. Sohn, Chandrajit Bajaj, Time-varying contour topology IEEE Transactions on Visualization and Computer Graphics. ,vol. 12, pp. 14- 25 ,(2006) , 10.1109/TVCG.2006.16
Attila Gyulassy, Mark Duchaineau, Vijay Natarajan, Valerio Pascucci, Eduardo Bringa, Andrew Higginbotham, Bernd Hamann, Topologically Clean Distance Fields IEEE Transactions on Visualization and Computer Graphics. ,vol. 13, pp. 1432- 1439 ,(2007) , 10.1109/TVCG.2007.70603