论文标题
通过图形分配加速进化建筑树提取
Accelerating Evolutionary Construction Tree Extraction via Graph Partitioning
论文作者
论文摘要
从潜在的嘈杂点云中提取建筑树是计算机辅助设计中反向工程任务的重要方面。基于算法几何形状的解决方案对可用的模型表示（例如二次表面）和噪声鲁棒性施加了约束。将问题重新构建为组合优化问题并用进化算法解决问题，可以以增加计算复杂性的成本来减轻其中一些约束。本文提出了一种基于图的搜索空间分配方案，该方案能够加速进化的构造树提取，同时利用现代CPU的并行化功能。评估表明，与基线方法相比，速度高达46.6美元，而导致的树尺寸增加了$ 25.2 \％$至$ 88.6 \％\％$。
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\%$.
