Title: Accelerating evolutionary construction tree extraction via graph partitioning
Authors: Friedrich, Markus
Feld, Sebastian
Phan, Thomy
Fayolle, Pierre-Alain
Citation: WSCG '2018: short communications proceedings: The 26th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision 2016 in co-operation with EUROGRAPHICS: University of West Bohemia, Plzen, Czech Republic May 28 - June 1 2018, p. 29-37.
Issue Date: 2018
Publisher: Václav Skala - UNION Agency
Document type: konferenční příspěvek
URI: wscg.zcu.cz/WSCG2018/!!_CSRN-2802.pdf
ISBN: 978-80-86943-41-1
ISSN: 2464-4617
Keywords: 3D rekonstrukce;reverzní inženýrství;počítačem podporovaný design;konstrukční geometrie tělesa;evoluční algoritmy;teorie grafů
Keywords in different language: 3D reconstruction;reverse engineering;computer aided design;constructive solid geometry;evolutionary algorithms;graph theory
Abstract: Extracting a Construction Tree from potentially noisy point clouds is an important aspect of Reverse Engineering tasks in Computer Aided Design. Solutions based on algorithmic geometry impose constraints on usable model representations (e.g. quadric surfaces only) and noise robustness. Re-formulating the problem as a combinatorial optimization problem and solving it with an Evolutionary Algorithm can mitigate some of these constraints at the cost of increased computational complexity. This paper proposes a graph-based search space partitioning scheme that is able to accelerate Evolutionary Construction Tree extraction while exploiting parallelization capabilities of modern CPUs. The evaluation indicates a speed-up up to a factor of 46:6 compared to the baseline approach while resulting tree sizes increased by 25:2% to 88:6%.
Rights: © Václav Skala - UNION Agency
Appears in Collections:WSCG '2018: Short Papers Proceedings

Files in This Item:
File Description SizeFormat 
Friedrich.pdfPlný text2,98 MBAdobe PDFView/Open

Please use this identifier to cite or link to this item: http://hdl.handle.net/11025/34653

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.