Editing Constructive solid geometry

{{short description|Creating a complex 3D surface or object by combining primitive objects}}
[[File:Csg tree.png|thumb|300px|CSG objects can be represented by binary trees, where leaves represent primitives, and nodes represent operations. In this figure, the nodes are labeled {{math|&cap;}} for [[Intersection (set theory)|intersection]], {{math|&cup;}} for [[Union (set theory)|union]], and {{math|&mdash;}} for [[Complement (set theory)#Relative complement|difference]].]]

'''Constructive solid geometry''' ('''CSG'''; formerly called '''computational binary solid geometry''') is a technique used in [[solid modeling]]. Constructive solid geometry allows a modeler to create a complex surface or object by using [[Boolean data type|Boolean]] [[Operator (programming)|operator]]s to combine simpler objects,<ref name="foley">{{citation|title=Computer Graphics: Principles and Practice|first=James D.|last=Foley|authorlink=James D. Foley|publisher=Addison-Wesley Professional|year=1996|isbn=9780201848403|contribution=12.7 Constructive Solid Geometry|url=https://books.google.com/books?id=-4ngT05gmAQC&pg=PA557|pages=557–558}},</ref> potentially generating visually complex objects by combining a few primitive ones.<ref>{{cite journal |last=Roth |first=Scott |title=Ray Casting for Modeling Solids |journal=Computer Graphics and Image Processing |pages=109–144 |volume=18 |date=1982|issue=2 |doi=10.1016/0146-664X(82)90169-1 }}</ref><ref name="bb">{{citation|title=Introduction to Implicit Surfaces|first1=Jules|last1=Bloomenthal|first2=Chandrajit|last2=Bajaj|author2-link=Chandrajit Bajaj|publisher=Morgan Kaufmann|year=1997|isbn=9781558602335|contribution=5.2.5 Intersection with CSG Trees|url=https://books.google.com/books?id=T3SSqIVnS4YC&pg=PA178|pages=178–180}}.</ref>

In [[3D computer graphics]] and [[Computer-aided design|CAD]], CSG is often used in [[procedural modeling]]. CSG can also be performed on [[Polygon mesh|polygonal meshes]], and may or may not be procedural and/or parametric.

Contrast CSG with [[polygon mesh]] modeling and [[box modeling]].

==Workings==
The simplest solid objects used for the representation are called ''[[geometric primitive]]s''. Typically they are the objects of simple shape: [[cuboid]]s, [[cylinder (geometry)|cylinder]]s, [[Prism (geometry)|prism]]s, [[Pyramid (geometry)|pyramids]], [[sphere]]s, [[cone (geometry)|cone]]s.<ref name="foley"/> The set of allowable primitives is limited by each software package. Some software packages allow CSG on curved objects while other packages do not.

An object is ''constructed'' from primitives by means of allowable ''operations'', which are typically [[Boolean algebra|Boolean]] [[operation (mathematics)|operations]] on [[set theory|sets]]: [[union (set theory)|union]] (OR), [[intersection (set theory)|intersection]] (AND) and [[complement (set theory)|difference]] (NOT), as well as [[geometric transformation]]s of those sets.<ref name="foley"/>

A primitive can typically be described by a [[Algorithm|procedure]] which accepts some number of [[parameter]]s; for example, a sphere may be described by the coordinates of its center point, along with a radius value. These primitives can be combined into compound objects using operations like these:

<gallery>
File:Boolean union.PNG|'''Union'''<br />Merger of two objects into one
File:Boolean difference.PNG|'''Difference'''<br />Subtraction of one object from another
File:Boolean intersect.PNG|'''Intersection'''<br />Portion common to both objects
</gallery>

Combining these elementary operations, it is possible to build up objects with high complexity starting from simple ones.

===Ray tracing===
Rendering of constructive solid geometry is particularly simple when [[Ray tracing (graphics)|ray tracing]]. Ray tracers intersect a ray with both primitives that are being operated on, apply the operator to the intersection intervals along the 1D ray, and then take the point closest to the camera along the ray as being the result.

==Applications==
[[File:Boolean_raytrace.svg|thumb|275px|CSG operations being applied in the context of rays in a [[Ray tracing (graphics)|ray tracer]]]]
Constructive solid geometry has a number of practical uses. It is used in cases where simple geometric objects are desired,{{cn|date=November 2014}} or where mathematical accuracy is important.<ref>{{harvtxt|Foley|1996}}, p. 559.</ref>
Nearly all engineering CAD packages use CSG (where it may be useful for representing tool cuts, and features where parts must fit together). 

The [[Quake engine|''Quake'' engine]] and [[Unreal Engine]] both use this system, as does [[Valve Hammer Editor|Hammer]] (the native [[Source engine]] level editor), and [[Torque Game Engine]]/[[Torque Game Engine Advanced]].  CSG is popular because a modeler can use a set of relatively simple objects to create very complicated geometry.<ref name="bb"/> When CSG is procedural or parametric, the user can revise their complex geometry by changing the position of objects or by changing the Boolean operation used to combine those objects.

One of the advantages of CSG is that it can easily assure that objects are "solid" or water-tight if all of the primitive shapes are water-tight.<ref>{{citation|title=Game Development Tools|editor-first=Marwan|editor-last=Ansari|publisher=CRC Press|year=2011|isbn=9781439867723|contribution=Real-time constructive solid geometry|pages=79–96|url=https://books.google.com/books?id=HKZuaUdmovsC&pg=PA79|first1=Sander|last1=van Rossen|first2=Matthew|last2=Baranowski}}.</ref> This can be important for some manufacturing or engineering computation applications.  By comparison, when creating geometry based upon [[boundary representation]]s, additional topological data is required, or consistency checks must be performed to assure that the given boundary description specifies a valid solid object.<ref name="foley"/>

A convenient property of CSG shapes is that it is easy to classify arbitrary points as being either inside or outside the shape created by CSG.  The point is simply classified against all the underlying primitives and the resulting boolean expression is evaluated.<ref name="rt">{{citation|title=An Introduction to Ray Tracing|first=Andrew S.|last=Glassner|publisher=Morgan Kaufmann|year=1989|isbn=9780122861604|page=80|url=https://books.google.com/books?id=YPblYyLqBM4C&pg=PA80}}.</ref> This is a desirable quality for some applications such as [[Ray tracing (graphics)|ray tracing]].<ref name="rt"/>

==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>

==Notable applications with CSG support==
<!--Listed applications should be notable with a sourced Wikipedia article.-->
===Generic modelling languages and software===
* [[HyperFun]] 
* [[PLaSM]]

===Ray tracing and particle transport===
* [[PhotoRealistic RenderMan]]
* [[POV-Ray]]

===Computer-aided design===
{{see also|CAD software}}
* [[AutoCAD]]
* [[Autodesk Inventor]]
* [[Autodesk Fusion 360]]
* [[BRL-CAD]]
* [[CATIA]]
* [[FreeCAD]]
* [[Siemens NX|NX CAD]]
* [[SolveSpace]]
* [[Onshape]]
* [[OpenSCAD]]
* [[PTC_Creo|PTC Creo Parametric]] (formerly known as [[Pro/Engineer]])
* [[Realsoft 3D]]
* [[Rhino3D|Rhino]]
* [[Solid Edge]]
* [[SolidWorks]]
* [[Tinkercad]]
* [[Vectorworks]]

===Gaming===
* [[Dreams_(video_game)|Dreams]]
* [[Godot_(game_engine)|Godot]]<ref>[https://godotengine.org/article/godot-gets-csg-support Godot Engine - Godot gets CSG support]</ref>
* [[GtkRadiant]]
* [[LittleBigPlanet]]
* [[Roblox]]
* [[Unity (game engine)|Unity]], via free or paid plug-ins from the [[Unity (game_engine)#Unity Asset Store|Unity Asset Store]].
* [[UnrealEd]]
* [[Valve Hammer Editor]]

===Others===
* [[3Delight]]
* [[Aqsis]] (as of version 0.6.0)<ref>{{cite web |url=https://sourceforge.net/p/aqsis/news/2002/02/major-release/ |title=Major release |last=Gregory |first=Paul |via=SourceForge |date=February 12, 2002 |access-date=May 20, 2020}}</ref>
* [[Blender (software)|Blender]] – primarily a surface mesh editor, but capable of simple CSG using meta objects and using the Boolean modifier on mesh objects.
* [[Clara.io]]
* [[Geant4]]
* [[Magica CSG]]<ref>[https://ephtracy.github.io/index.html?page=magicacsg Magica CSG website]</ref>
* [[Monte Carlo N-Particle Transport Code|MCNP]]
* [[SketchUp]]
* [[Womp]]<ref>[https://womp.com/index Womp website]</ref>
* [[Vectorworks]]

==References==
{{reflist}}

[[Category:Computer-aided design]]
[[Category:3D computer graphics]]
[[Category:Euclidean solid geometry]]