Constructive solid geometry

Last updated
CSG objects can be represented by binary trees, where leaves represent primitives, and nodes represent operations. In this figure, the nodes are labeled [?] for intersection, [?] for union, and -- for difference. Csg tree.png
CSG objects can be represented by binary trees, where leaves represent primitives, and nodes represent operations. In this figure, the nodes are labeled ∩ for intersection, ∪ for union, and — for 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 operators to combine simpler objects, [1] potentially generating visually complex objects by combining a few primitive ones. [2] [3]

Contents

In 3D computer graphics and CAD, CSG is often used in procedural modeling. CSG can also be performed on 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 primitives . Typically they are the objects of simple shape: cuboids, cylinders, prisms, pyramids, spheres, cones. [1] 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, intersection and difference, as well as geometric transformations of those sets. [1]

A primitive can typically be described by a procedure which accepts some number of parameters; 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:

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

CSG operations being applied in the context of rays in a ray tracer Boolean raytrace.svg
CSG operations being applied in the context of rays in a ray tracer

Constructive solid geometry has a number of practical uses. It is used in cases where simple geometric objects are desired,[ citation needed ] or where mathematical accuracy is important. [4] 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 and Unreal Engine both use this system, as does 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. [3] 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. [5] This can be important for some manufacturing or engineering computation applications. By comparison, when creating geometry based upon boundary representations, additional topological data is required, or consistency checks must be performed to assure that the given boundary description specifies a valid solid object. [1]

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. [6] This is a desirable quality for some applications such as ray tracing. [6]

Conversion from meshes to CSG

With CSG models being parameterized by construction, they are often favorable over usual 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-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. [7]

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. [8]

There are also approaches that use genetic algorithms to iteratively optimize an initial shape towards the shape of the desired mesh. [9]

Notable applications with CSG support

Generic modelling languages and software

Ray tracing and particle transport

Computer-aided design

Gaming

Others

Related Research Articles

<span class="mw-page-title-main">Computer-aided design</span> Constructing a product by means of computer

Computer-aided design (CAD) is the use of computers 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 communications through documentation, and to create a database for manufacturing. Designs made through CAD software help protect products and inventions when used in patent applications. CAD output is often in the form of electronic files for print, machining, or other manufacturing operations. The terms computer-aided drafting (CAD) and computer-aided design and drafting (CADD) are also used.

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity.

<span class="mw-page-title-main">Geometric primitive</span> Basic shapes represented in vector graphics

In vector computer graphics, CAD systems, and geographic information systems, geometric primitive is the simplest geometric shape that the system can handle. Sometimes the subroutines that draw the corresponding objects are called "geometric primitives" as well. The most "primitive" primitives are point and straight line segment, which were all that early vector graphics systems had.

<span class="mw-page-title-main">Ray casting</span> Methodological basis for 3D CAD/CAM solid modeling and image rendering

Ray casting is the methodological basis for 3D CAD/CAM solid modeling and image rendering. It is essentially the same as ray tracing for computer graphics where virtual light rays are "cast" or "traced" on their path from the focal point of a camera through each pixel in the camera sensor to determine what is visible along the ray in the 3D scene. The term "Ray Casting" was introduced by Scott Roth while at the General Motors Research Labs from 1978–1980. His paper, "Ray Casting for Modeling Solids", describes modeled solid objects by combining primitive solids, such as blocks and cylinders, using the set operators union (+), intersection (&), and difference (-). The general idea of using these binary operators for solid modeling is largely due to Voelcker and Requicha's geometric modelling group at the University of Rochester. See solid modeling for a broad overview of solid modeling methods. This figure on the right shows a U-Joint modeled from cylinders and blocks in a binary tree using Roth's ray casting system in 1979.

<span class="mw-page-title-main">Solid modeling</span> Set of principles for modeling solid geometry

Solid modeling is a consistent set of principles for mathematical and computer modeling of three-dimensional shapes (solids). Solid modeling is distinguished within the broader related areas of geometric modeling and computer graphics, such as 3D modeling, by its emphasis on physical fidelity. Together, the principles of geometric and solid modeling form the foundation of 3D-computer-aided design, and in general, support the creation, exchange, visualization, animation, interrogation, and annotation of digital models of physical objects.

<span class="mw-page-title-main">Boundary representation</span> Method of representing a 3D object by defining the limits of its volume

In solid modeling and computer-aided design, boundary representation 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 elements, which define the boundary between interior and exterior points.

<span class="mw-page-title-main">Polygonal modeling</span> Object modeling method

In 3D computer graphics, polygonal modeling is an approach for modeling objects by representing or approximating their surfaces using polygon meshes. Polygonal modeling is well suited to scanline rendering and is therefore the method of choice for real-time computer graphics. Alternate methods of representing 3D objects include NURBS surfaces, subdivision surfaces, and equation-based representations used in ray tracers.

A geometric modeling kernel is a solid modeling software component used in computer-aided design (CAD) packages. Available modelling kernels include:

<span class="mw-page-title-main">Open Cascade Technology</span> Open-source 3D modelling software

Open Cascade Technology (OCCT), formerly called CAS.CADE, is an open-source software development platform for 3D CAD, CAM, CAE, etc. that is developed and supported by Open Cascade SAS company.

Generative Modelling Language (GML) in computer graphics and generative computer programming is a very simple programming language for the concise description of complex 3D shapes. It follows the "Generative Modelling" paradigm, where complex datasets are represented by "lists of operations" rather than by lists of objects, which is for instance the case in a relational database.

Function Representation is used in solid modeling, volume modeling and computer graphics. FRep was introduced in "Function representation in geometric modeling: concepts, implementation and applications" as a uniform representation of multidimensional geometric objects (shapes). An object as a point set in multidimensional space is defined by a single continuous real-valued function of point coordinates which is evaluated at the given point by a procedure traversing a tree structure with primitives in the leaves and operations in the nodes of the tree. The points with belong to the object, and the points with are outside of the object. The point set with is called an isosurface.

<span class="mw-page-title-main">Solid Edge</span> Computer-aided design software

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. Through third party applications it has links to many other Product Lifecycle Management (PLM) technologies.

<span class="mw-page-title-main">Geometric design</span> Branch of computational geometry

Geometrical design (GD) is a branch of computational geometry. It deals with the construction and representation of free-form curves, surfaces, or volumes and is closely related to geometric modeling. Core problems are curve and surface modelling and representation. GD studies especially the construction and manipulation of curves and surfaces given by a set of points using polynomial, rational, piecewise polynomial, or piecewise rational methods. The most important instruments here are parametric curves and parametric surfaces, such as Bézier curves, spline curves and surfaces. An important non-parametric approach is the level-set method.

<span class="mw-page-title-main">OpenSCAD</span> Free software for creating 3D objects

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; the 3D preview can be manipulated interactively, but cannot be interactively modified in 3D. Instead, an OpenSCAD script specifies geometric primitives and defines how they are modified and combined to render a 3D model. As such, the program performs constructive solid geometry (CSG). OpenSCAD is available for Windows, Linux, and macOS.

<span class="mw-page-title-main">Cobalt (CAD program)</span> 3D computer graphics software

Cobalt is a parametric-based computer-aided design (CAD) and 3D modeling program that runs on both Macintosh and Microsoft Windows operating systems. The program combines the direct-modeling way to create and edit objects and the highly structured, history-driven parametric way exemplified by programs like Pro/ENGINEER. A product of Ashlar-Vellum, Cobalt is Wireframe-based and history-driven with associativity and 2D equation-driven parametrics and constraints. It offers surfacing tools, mold design tools, detailing, and engineering features. Cobalt includes a library of 149,000 mechanical parts.

<span class="mw-page-title-main">3D modeling</span> Form of computer-aided engineering

In 3D computer graphics, 3D modeling is the process of developing a mathematical coordinate-based representation of a surface of an object in three dimensions via specialized software by manipulating edges, vertices, and polygons in a simulated 3D space.

<span class="mw-page-title-main">SolveSpace</span> Open-source computer-aided design software

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.

This is a glossary of terms relating to computer graphics.

References

  1. 1 2 3 4 Foley, James D. (1996), "12.7 Constructive Solid Geometry", Computer Graphics: Principles and Practice, Addison-Wesley Professional, pp. 557–558, ISBN   9780201848403 ,
  2. ↑ Roth, Scott (1982). "Ray Casting for Modeling Solids". Computer Graphics and Image Processing. 18 (2): 109–144. doi:10.1016/0146-664X(82)90169-1.
  3. 1 2 Bloomenthal, Jules; Bajaj, Chandrajit (1997), "5.2.5 Intersection with CSG Trees", Introduction to Implicit Surfaces, Morgan Kaufmann, pp. 178–180, ISBN   9781558602335 .
  4. ↑ Foley (1996), p. 559.
  5. ↑ van Rossen, Sander; Baranowski, Matthew (2011), "Real-time constructive solid geometry", in Ansari, Marwan (ed.), Game Development Tools, CRC Press, pp. 79–96, ISBN   9781439867723 .
  6. 1 2 Glassner, Andrew S. (1989), An Introduction to Ray Tracing, Morgan Kaufmann, p. 80, ISBN   9780122861604 .
  7. ↑ Buchele, Suzanne F.; Crawford, Richard H. (2004). "Three-dimensional halfspace constructive solid geometry tree construction from implicit boundary representations". Computer-Aided Design. 36 (11): 1063–1073. doi:10.1016/j.cad.2004.01.006.
  8. ↑ Du, Tao; Inala, Jeevana Priya; Pu, Yewen; Spielberg, Andrew; Schulz, Adriana; Rus, Daniela; Solar-Lezama, Armando; Matusik, Wojciech (2018). "InverseCSG: automatic conversion of 3D models to CSG trees". ACM Trans. Graph. doi: 10.1145/3272127.3275006 .
  9. ↑ Fayolle, Pierre-Alain; Pasko, Alexander A. (2016). "An evolutionary approach to the extraction of object construction trees from 3D point clouds" (PDF). Computer-Aided Design. 74: 1–17. doi:10.1016/j.cad.2016.01.001.
  10. ↑ Godot Engine - Godot gets CSG support
  11. ↑ Gregory, Paul (February 12, 2002). "Major release" . Retrieved May 20, 2020– via SourceForge.
  12. ↑ Magica CSG website
  13. ↑ Womp website
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.