Fast CSG Tree Reconstruction from Triangle Meshes via User-guided Partitioning

The use of triangle meshes to represent geometric designs is ubiquitous in virtual prototyping. While geometric design is typically performed in computer-aided design (CAD) systems, triangle meshes usually do not allow for convenient shape modeling. Therefore, adjustment of the prototype's geometric design can be laborious and complex, if its CAD data is missing. To recover CAD data from a triangle mesh, we present a user-guided reconstruction method to obtain a constructive solid geometry (CSG) tree representing the geometry of the triangle mesh. In an interactive step, the user partitions identi_able design parts selecting mesh segments of common curvature. The user-guided partitioning allows for localized, per-partition reconstruction in a substantially reduced search space. To boost e_ciency, we present GPU-accelerated primitive shape _tting as well as genetic evolution of CSG trees. As a result, our method enables fast CSG reconstruction improving run time performance by up to two orders of magnitude compared to state-of-the-art methods that require many minutes or even hours for complex reconstruction tasks. In addition, our method provides accurate reconstruction results reducing reconstruction errors by up to one order of magnitude compared to state-of-the-art methods.