![Csg tree](https://upload.wikimedia.org/wikipedia/commons/8/8b/Csg_tree.png)
Constructive solid geometry (CSG; formerly called computational binary solid geometry) is a technique used in
solid modeling
Solid modeling (or solid modelling) is a consistent set of principles for mathematical and computer modeling of three-dimensional shapes '' (solids)''. Solid modeling is distinguished from related areas of geometric modeling and computer graphi ...
. Constructive solid geometry allows a modeler to create a complex surface or object by using
Boolean operators to combine simpler objects,
[,] potentially generating visually complex objects by combining a few primitive ones.
[.]
In
3D computer graphics
3D computer graphics, or “3D graphics,” sometimes called CGI, 3D-CGI or three-dimensional computer graphics are graphics that use a three-dimensional representation of geometric data (often Cartesian) that is stored in the computer for th ...
and
CAD
Computer-aided design (CAD) is the use of computers (or ) to aid in the creation, modification, analysis, or optimization of a design. This software is used to increase the productivity of the designer, improve the quality of design, improve co ...
, CSG is often used in
procedural modeling
Procedural modeling is an umbrella term for a number of techniques in computer graphics to create 3D models and textures from sets of rules. L-Systems, fractals, and generative modeling are procedural modeling techniques since they apply algorit ...
. CSG can also be performed on
polygonal meshes, and may or may not be procedural and/or parametric.
Contrast CSG with
polygon mesh
In 3D computer graphics and solid modeling, a polygon mesh is a collection of , s and s that defines the shape of a polyhedral object. The faces usually consist of triangles (triangle mesh), quadrilaterals (quads), or other simple convex polyg ...
modeling and
box modeling.
Workings
The simplest solid objects used for the representation are called ''
geometric primitive
In vector computer graphics, CAD systems, and geographic information systems, geometric primitive (or prim) is the simplest (i.e. 'atomic' or irreducible) geometric shape that the system can handle (draw, store). Sometimes the subroutines that d ...
s''. Typically they are the objects of simple shape:
cuboids,
cylinder
A cylinder (from ) has traditionally been a three-dimensional solid, one of the most basic of curvilinear geometric shapes. In elementary geometry, it is considered a prism with a circle as its base.
A cylinder may also be defined as an infin ...
s,
prism
Prism usually refers to:
* Prism (optics), a transparent optical component with flat surfaces that refract light
* Prism (geometry), a kind of polyhedron
Prism may also refer to:
Science and mathematics
* Prism (geology), a type of sedimentary ...
s,
pyramids
A pyramid (from el, πυραμίς ') is a structure whose outer surfaces are triangular and converge to a single step at the top, making the shape roughly a pyramid in the geometric sense. The base of a pyramid can be trilateral, quadrilat ...
,
sphere
A sphere () is a Geometry, geometrical object that is a solid geometry, three-dimensional analogue to a two-dimensional circle. A sphere is the Locus (mathematics), set of points that are all at the same distance from a given point in three ...
s,
cone
A cone is a three-dimensional geometric shape that tapers smoothly from a flat base (frequently, though not necessarily, circular) to a point called the apex or vertex.
A cone is formed by a set of line segments, half-lines, or lines con ...
s.
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 operations on
sets:
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
,
intersection and
difference
Difference, The Difference, Differences or Differently may refer to:
Music
* ''Difference'' (album), by Dreamtale, 2005
* ''Differently'' (album), by Cassie Davis, 2009
** "Differently" (song), by Cassie Davis, 2009
* ''The Difference'' (al ...
, as well as
geometric transformation
In mathematics, a geometric transformation is any bijection of a set to itself (or to another such set) with some salient geometrical underpinning. More specifically, it is a function whose domain and range are sets of points — most often b ...
s of those sets.
A primitive can typically be described by a
procedure which accepts some number of
parameter
A parameter (), generally, is any characteristic that can help in defining or classifying a particular system (meaning an event, project, object, situation, etc.). That is, a parameter is an element of a system that is useful, or critical, when ...
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:
File:Boolean union.PNG, Union
Merger of two objects into one
File:Boolean difference.PNG, Difference
Subtraction of one object from another
File:Boolean intersect.PNG, Intersection
Portion common to both objects
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. 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
![Boolean_raytrace](https://upload.wikimedia.org/wikipedia/commons/d/da/Boolean_raytrace.svg)
Constructive solid geometry has a number of practical uses. It is used in cases where simple geometric objects are desired, or where mathematical accuracy is important.
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
The ''Quake'' engine is the game engine developed by id Software to power their 1996 video game '' Quake''. It featured true 3D real-time rendering and is now licensed under the terms of GNU General Public License v2.0 or later.
After rele ...
and
Unreal engine
Unreal Engine (UE) is a 3D computer graphics game engine developed by Epic Games, first showcased in the 1998 first-person shooter game '' Unreal''. Initially developed for PC first-person shooters, it has since been used in a variety of g ...
both use this system, as does
Hammer (the native
Source engine
Source is a 3D game engine developed by Valve. It debuted as the successor to GoldSrc in 2004 with the release of '' Counter-Strike: Source'' and '' Half-Life 2''. Updates to Source were released in incremental versions, with the engine being su ...
level editor), and
Torque Game Engine
Torque Game Engine, or TGE, is an open-source cross-platform 3D computer game engine, developed by GarageGames and actively maintained under the current versions Torque 3D as well as Torque 2D. It was originally developed by Dynamix for the 2001 ...
/
Torque Game Engine Advanced. CSG is popular because a modeler can use a set of relatively simple objects to create very complicated geometry.
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. This can be important for some manufacturing or engineering computation applications. By comparison, when creating geometry based upon
boundary representation
In solid modeling and computer-aided design, boundary representation (often abbreviated B-rep or BREP) is a method for representing a 3D shape by defining the limits of its volume. A solid is represented as a collection of connected surface ...
s, additional topological data is required, or consistency checks must be performed to assure that the given boundary description specifies a valid solid object.
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.
[.] This is a desirable quality for some applications such as
ray tracing.
Conversion from meshes to CSG
With CSG models being parameterized by construction, they are often favorable over usual
meshes
A mesh is a barrier made of connected strands of metal, fiber, or other flexible or ductile materials. A mesh is similar to a web or a net in that it has many attached or woven strands.
Types
* A plastic mesh may be extruded, oriented, ex ...
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-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.
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 In computer science, program synthesis is the task to construct a program that provably satisfies a given high-level formal specification. In contrast to program verification, the program is to be constructed rather than given; however, both fields ...
tools to find a CSG tree with minimal complexity.
There are also approaches that use
genetic algorithms
In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to gene ...
to iteratively optimize an initial shape towards the shape of the desired mesh.
Notable applications with CSG support
Generic modelling languages and software
*
HyperFun
HyperFun (from Hyperdimensional Functions) is a programming language{{cite web , work = HyperFun language specification, version 2.0 , title = HyperFun: Language for FRep Volume Modeling , url = http://hyperfun.org/wiki/doku.php?id=hyperfun:la ...
*
PLaSM
PLaSM (Programming Language of Solid Modeling) is an open source scripting languageA. Paoluzzi: Geometric Programming for Computer Aided Design, Wiley, 2003 for solid modeling, a discipline that constitutes the foundation of computer-aided design ...
Ray tracing and particle transport
*
PhotoRealistic RenderMan
Pixar RenderMan (formerly PhotoRealistic RenderMan) is proprietary photorealistic 3D rendering software produced by Pixar Animation Studios. Pixar uses RenderMan to render their in-house 3D animated movie productions and it is also available as ...
*
POV-Ray
The Persistence of Vision Ray Tracer, most commonly acronymed as POV-Ray, is a cross-platform ray-tracing program that generates images from a text-based scene description. It was originally based on DKBTrace, written by David Kirk Buck and Aaro ...
Computer-aided design
*
AutoCAD
AutoCAD is a commercial computer-aided design (CAD) and drafting software application. Developed and marketed by Autodesk, AutoCAD was first released in December 1982 as a desktop app running on microcomputers with internal graphics controllers. ...
*
Autodesk Inventor
Autodesk Inventor is a computer-aided design application for 3D mechanical design, simulation, visualization, and documentation developed by Autodesk.
Features
Inventor allows 2D and 3D data integration in a single environment, creating a virt ...
*
Autodesk Fusion 360
Fusion 360 is a commercial computer-aided design (CAD), computer-aided manufacturing (CAM), computer-aided engineering (CAE) and printed circuit board (PCB) design software application, developed by Autodesk. It is available for Windows and m ...
*
BRL-CAD
BRL-CAD is a constructive solid geometry (CSG) solid modeling computer-aided design (CAD) system. It includes an interactive geometry editor, ray tracing support for graphics rendering and geometric analysis, computer network distributed frame ...
*
CATIA
CATIA (, an acronym of computer-aided three-dimensional interactive application) is a multi-platform software suite for computer-aided design (CAD), computer-aided manufacturing (CAM), computer-aided engineering (CAE), 3D modeling and Product ...
*
FreeCAD
FreeCAD is a general-purpose parametric 3D computer-aided design (CAD) modeler and a building information modeling (BIM) software application with finite element method (FEM) support. It is intended for mechanical engineering product design bu ...
*
NX CAD
*
SolveSpace
SolveSpace is a free and open-source 2D/ 3D constraint-based parametric computer-aided design (CAD) software that supports basic 2D and 3D constructive solid geometry modeling.
It is a constraint-based parametric modeler with simple mechanic ...
*
Onshape
Onshape is a computer-aided design (CAD) software system, delivered over the Internet via a software as a service (SAAS) model. It makes extensive use of cloud computing, with compute-intensive processing and rendering performed on Internet-bas ...
*
OpenSCAD
OpenSCAD is a free software application for creating solid 3D computer-aided design (CAD) objects. It is a script-only based modeller that uses its own description language; parts can be previewed, but cannot be interactively modified by mouse i ...
*
PTC Creo Parametric (formerly known as
Pro/Engineer
Creo Parametric, formerly known, together with Creo Elements/Pro, as Pro/Engineer and Wildfire, is a solid modeling or CAD, CAM, CAE, and associative 3D modeling application, running on Microsoft Windows.
Creo Parametric should not to be confu ...
)
*
Realsoft 3D
Realsoft 3D is a modeling and raytracing application created by Realsoft Graphics Oy. Originally called Real 3D, it was developed for the Amiga computer and later also for Linux, Irix, Mac OS X, and Microsoft Windows.
It was initially written ...
*
Rhino
A rhinoceros (; ; ), commonly abbreviated to rhino, is a member of any of the five extant species (or numerous extinct species) of odd-toed ungulates in the family Rhinocerotidae. (It can also refer to a member of any of the extinct species o ...
*
SelfCAD
*
Solid Edge
Solid Edge is a 3D CAD, parametric feature and synchronous technology solid modeling software. It runs on Microsoft Windows and provides solid modeling, assembly modelling and 2D orthographic view functionality for mechanical designers. Throu ...
*
SolidWorks
SolidWorks is a solid modeling computer-aided design (CAD) and computer-aided engineering (CAE) application published by Dassault Systèmes.
According to the publisher, over two million engineers and designers at more than 165,000 companies w ...
*
Tinkercad
Tinkercad is a free-of-charge, online 3D modeling program that runs in a web browser. Since it became available in 2011 it has become a popular platform for creating models for 3D printing as well as an entry-level introduction to constructive s ...
*
Vectorworks
Vectorworks, Inc. is a U.S.-based software development company that focuses on CAD and BIM software for the architecture, engineering, and construction (AEC), landscape, and entertainment industries. Vectorworks is owned by the Nemetschek Grou ...
Gaming
*
Dreams
A dream is a succession of images, ideas, emotions, and sensations that usually occur involuntarily in the mind during certain stages of sleep. Humans spend about two hours dreaming per night, and each dream lasts around 5 to 20 minutes, althou ...
*
Godot
*
GtkRadiant
Based on Id Software's open stance towards game modifications, their ''Quake'' series became a popular subject for player mods beginning with '' Quake'' in 1996. Spurred by user-created hacked content on their previous games and the company's ...
*
Unity
Unity may refer to:
Buildings
* Unity Building, Oregon, Illinois, US; a historic building
* Unity Building (Chicago), Illinois, US; a skyscraper
* Unity Buildings, Liverpool, UK; two buildings in England
* Unity Chapel, Wyoming, Wisconsin, US; a h ...
, via free or paid plug-ins from the
Unity Asset Store.
*
UnrealEd
Unreal Engine (UE) is a 3D computer graphics game engine developed by Epic Games, first showcased in the 1998 first-person shooter game ''Unreal (1998 video game), Unreal''. Initially developed for Personal computer, PC first-person shooters, i ...
*
Valve Hammer Editor
Source is a 3D game engine developed by Valve. It debuted as the successor to GoldSrc in 2004 with the release of '' Counter-Strike: Source'' and '' Half-Life 2''. Updates to Source were released in incremental versions, with the engine being su ...
*
Roblox
''Roblox'' () is an online game platform and game creation system developed by Roblox Corporation that allows users to program games and play games created by other users. Created by David Baszucki and Erik Cassel in 2004 and released i ...
Others
*
3Delight
3Delight, also known as 3DelightNSI, is 3D computer graphics software that runs on Microsoft Windows, MacOS and Linux. It is developed by Illumination Research. It is both a photorealistic and NPR path tracing offline renderer based on its NSI ...
*
Aqsis
Aqsis is a free rendering suite compliant with the RenderMan standard. It is available under the BSD, previously under GPL. Its main author and project manager is Paul Gregory.
The Aqsis project consists of a renderer, shader compiler and a ...
(as of version 0.6.0)
*
Blender
A blender (sometimes called a mixer or liquidiser in British English) is a kitchen appliance, kitchen and laboratory appliance used to mix, crush, purée or emulsion, emulsify food and other substances. A stationary blender consists of a 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
Geant4 (for GEometry ANd Tracking) is a platform for "the simulation of the passage of particles through matter" using Monte Carlo methods. It is the successor of the GEANT series of software toolkits developed bThe Geant4 Collaboration and t ...
*
MCNP
Monte Carlo N-Particle Transport (MCNP) is a general-purpose, continuous-energy, generalized-geometry, time-dependent, Monte Carlo radiation transport code designed to track many particle types over broad ranges of energies and is developed by L ...
*
SketchUp
SketchUp is a suite of subscription products that include SketchUp Pro Desktop, a 3D modeling Computer-Aided Design (CAD) program for a broad range of drawing and design applications — including architectural, interior design, industrial an ...
References
{{reflist
Computer-aided design
3D computer graphics
Euclidean solid geometry