Optimizing Evolutionary CSG Tree Extraction

Friedrich, Markus; Fayolle, Pierre-Alain; Gabor, Thomas und Linnhoff-Popien, Claudia (2019): Optimizing Evolutionary CSG Tree Extraction. In: Proceedings of the 2019 Genetic and Evolutionary Computation Conference (Gecco'19): S. 1183-1191

Abstract

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.

• Dokumententyp: Zeitschriftenartikel
• Fakultät: Mathematik, Informatik und Statistik > Informatik
• Themengebiete: 000 Informatik, Informationswissenschaft, allgemeine Werke > 004 Informatik
• Sprache: Englisch