Editing Constructive solid geometry (section)

==Conversion from meshes to CSG==
With CSG models being parameterized by construction, they are often favorable over usual [[Polygon mesh|meshes]] when it comes to applications where the goal is to fabricate customized models. For such applications it can be interesting to convert already existing meshes to CSG trees. This problem of automatically converting meshes to CSG trees is called '''inverse CSG'''.

A resulting CSG tree is required to occupy the same volume in 3D space as the input mesh while having a minimal number of nodes. Simple solutions are preferred to ensure that the resulting model is easy to edit.
Solving this problem is a challenge because of the large search space that has to be explored. It combines continuous parameters such as dimension and size of the primitive shapes, and discrete parameters such as the Boolean operators used to build the final CSG tree.

Deductive methods solve this problem by building a set of [[Half-space (geometry)|half-spaces]] that describe the interior of the geometry. These half-spaces are used to describe primitives that can be combined to get the final model.<ref>{{cite journal |last1=Buchele |first1=Suzanne F. |last2=Crawford |first2=Richard H. |title=Three-dimensional halfspace constructive solid geometry tree construction from implicit boundary representations |journal=Computer-Aided Design |date=2004 |volume=36 |issue=11 |pages=1063–1073 |doi=10.1016/j.cad.2004.01.006}}</ref>

Another approach decouples the detection of primitive shapes and the computation of the CSG tree that defines the final model. This approach exploits the ability of modern [[program synthesis]] tools to find a CSG tree with minimal complexity.<ref>{{cite journal |last1=Du |first1=Tao |last2=Inala |first2=Jeevana Priya |last3=Pu |first3=Yewen |last4=Spielberg |first4=Andrew |last5=Schulz |first5=Adriana |last6=Rus |first6=Daniela |last7=Solar-Lezama |first7=Armando |last8=Matusik |first8=Wojciech |title=InverseCSG: automatic conversion of 3D models to CSG trees |journal=ACM Trans. Graph. |date=2018 |doi=10.1145/3272127.3275006|doi-access=free }}</ref>

There are also approaches that use [[Genetic algorithm|genetic algorithms]] to iteratively optimize an initial shape towards the shape of the desired mesh.<ref>{{cite journal |last1=Fayolle |first1=Pierre-Alain |last2=Pasko |first2=Alexander A. |title=An evolutionary approach to the extraction of object construction trees from 3D point clouds |journal=Computer-Aided Design |date=2016 |volume=74 |pages=1–17 |doi=10.1016/j.cad.2016.01.001|url=http://eprints.bournemouth.ac.uk/23373/1/tree_recovery.pdf }}</ref>