Logo Logo
Switch Language to German
Friedrich, Markus; Fayolle, Pierre-Alain; Gabor, Thomas; Linnhoff-Popien, Claudia (2019): Optimizing Evolutionary CSG Tree Extraction. In: Proceedings of the 2019 Genetic and Evolutionary Computation Conference (Gecco'19): pp. 1183-1191
Full text not available from 'Open Access LMU'.


The extraction of 3D models represented by Constructive Solid Geometry (CSG) trees from point clouds is a common problem in reverse engineering pipelines as used by Computer Aided Design (CAD) tools. We propose three independent enhancements on state-of-the-art Genetic Algorithms (GAs) for CSG tree extraction: (1) A deterministic point cloud filtering mechanism that significantly reduces the computational effort of objective function evaluations without loss of geometric precision, (2) a graph-based partitioning scheme that divides the problem domain in smaller parts that can be solved separately and thus in parallel and (3) a 2-level improvement procedure that combines a recursive CSG tree redundancy removal technique with a local search heuristic, which significantly improves GA running times. We show in an extensive evaluation that our optimized GA-based approach provides faster running times and scales better with problem size compared to state-of-the-art GA-based approaches.