README
¶
csg
import "github.com/reactivego/csg"
Constructive Solid Geometry (CSG) is a modeling technique that uses Boolean operations like union and intersection to combine 3D solids. This library implements CSG operations on meshes elegantly and concisely using BSP trees, and is meant to serve as an easily understandable implementation of the algorithm. All edge cases involving overlapping coplanar polygons in both solids are correctly handled.
Example usage:
import "github.com/reactivego/csg"
cube := csg.Cube()
sphere := csg.Sphere(csg.Radius(1.3))
polygons := cube.Subtract(sphere).Polygons
Operations
This library provides three CSG operations: union, subtract, and intersect. The operations are rendered below.
 |
 |
|---|---|
a |
b |
The solids a and b were generated with the following code:
import . "github.com/reactivego/csg"
a := Cube(Center(-0.25, -0.25, -0.25))
b := Sphere(Center(0.25, 0.25, 0.25), Radius(1.3))
 |
 |
 |
|---|---|---|
a.Union(b) |
a.Subtract(b) |
a.Intersect(b) |
Combined CSG Example
Below is a solid constructed from a combination of operations:
 |
 |
 |
 |
 |
|---|---|---|---|---|
a |
b |
c |
d |
e |
The solids above were generated with the following code:
import . "github.com/reactivego/csg"
a := Cube()
b := Sphere(Radius(1.35), Stacks(12))
c := Cylinder(Radius(0.7), Start(-1, 0, 0), End(1, 0, 0))
d := Cylinder(Radius(0.7), Start(0, -1, 0), End(0, 1, 0))
e := Cylinder(Radius(0.7), Start(0, 0, -1), End(0, 0, 1))
 |
|---|
a.Intersect(b).Subtract(c.Union(d).Union(e)) |
The combined solid was generated with the code:
a.Intersect(b).Subtract(c.Union(d).Union(e))
Implementation Details
All CSG operations are implemented in terms of two functions, ClipTo() and
Invert(), which remove parts of a BSP tree inside another BSP tree and swap
solid and empty space, respectively. To find the union of a and b, we
want to remove everything in a inside b and everything in b inside a,
then combine polygons from a and b into one solid:
a.ClipTo(b)
b.ClipTo(a)
a.AddPolygons(b.AllPolygons())
The only tricky part is handling overlapping coplanar polygons in both trees.
The code above keeps both copies, but we need to keep them in one tree and
remove them in the other tree. To remove them from b we can clip the
inverse of b against a. The code for union now looks like this:
a.ClipTo(b)
b.ClipTo(a)
b.Invert()
b.ClipTo(a)
b.Invert()
a.AddPolygons(b.AllPolygons())
Subtraction and intersection naturally follow from set operations. If
union is A | B, subtraction is A - B = ~(~A | B) and intersection is
A & B = ~(~A | ~B) where ~ is the complement operator.
Acknowledgments
This package is a direct conversion of cgs.js to Go. The original JavaScript code was written by Evan Wallace and committed to git on November 30, 2011. As an odd coincidence, I am writing this a full 10 years later on Nov 30, 2021.
License
This library is licensed under the terms of the MIT License. See LICENSE file for copyright notice and exact wording.
Documentation
¶
Index ¶
- Constants
- type BSP
- type Option
- type Options
- type Plane
- type Polygon
- type Polygons
- type Solid
- type Vector
- func (v Vector) Cross(a Vector) Vector
- func (v Vector) DividedBy(a float64) Vector
- func (v Vector) Dot(a Vector) float64
- func (v Vector) Length() float64
- func (v Vector) Lerp(a Vector, t float64) Vector
- func (v Vector) Minus(a Vector) Vector
- func (v Vector) Negated() Vector
- func (v Vector) Plus(a Vector) Vector
- func (v Vector) Times(a float64) Vector
- func (v Vector) Unit() Vector
- type Vertex
Constants ¶
const PlaneEPSILON = 1e-5
PlaneEPSILON is the tolerance used by `SplitPolygon()` to decide if a point is on the plane.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BSP ¶
BSP holds a node in a BSP tree. A BSP tree is built from a collection of polygons by picking a polygon to split along. That polygon (and all other coplanar polygons) are added directly to that node and the other polygons are added to the front and/or back subtrees. This is not a leafy BSP tree since there is no distinction between internal and leaf nodes.
func (*BSP) AddPolygons ¶
AddPolygons builds a BSP tree out of `polygons`. When called on an existing tree, the new polygons are filtered down to the bottom of the tree and become new nodes there. Each set of polygons is partitioned using the first polygon (no heuristic is used to pick a good split).
func (BSP) AllPolygons ¶
AllPolygons returns a list of all polygons in this BSP tree.
func (BSP) ClipPolygons ¶
ClipPolygons recursively removes all polygons in `polygons` that are inside this BSP tree.
func (*BSP) ClipTo ¶
ClipTo removes all polygons in this BSP tree that are inside the other BSP tree `bsp`.
type Options ¶
type Options struct {
Center Vector
Radius float64
Size Vector
Slices int
Stacks int
Start Vector
End Vector
}
func OptionsFrom ¶
type Plane ¶
Plane represents a plane in 3D space.
func PlaneFromPoints ¶
func (Plane) SplitPolygon ¶
SplitPolygon splits `polygon` by this plane if needed, then put the polygon or polygon fragments in the appropriate lists. Coplanar polygons go into either `coplanarFront` or `coplanarBack` depending on their orientation with respect to this plane. Polygons in front or in back of this plane go into either `front` or `back`.
type Polygon ¶
Polygon represents a convex polygon. The vertices used to initialize a polygon must be coplanar and form a convex loop.
Each convex polygon has a `Shared` property, which is shared between all polygons that are clones of each other or were split from the same polygon. This can be used to define per-polygon properties (such as surface color).
func PolygonFromVertices ¶
type Solid ¶
type Solid struct {
Polygons Polygons
}
Solid holds a binary space partition tree representing a 3D solid. Two solids can be combined using the `Union()`, `Subtract()` and `Intersect()` methods.
func Cube ¶
Cube constructs an axis-aligned solid cuboid. Optional parameters are `Center` and `Size`, which default to `Center(0, 0, 0)` and `Size(2, 2, 2)`. The Size is specified a list of three numbers, one for each axis.
Example code:
cube := csg.Cube( csg.Center(0, 0, 0), csg.Size(2, 2, 2))
func Cylinder ¶
Cylinder constructs a solid cylinder. Optional parameters are `Start`, `End`, `Radius`, and `Slices`, which default to `Start(0, -1, 0)`, `End(0, 1, 0)`, `Radius(1)`, and `Slices(16)`. The `Slices` parameter controls the tessellation.
Example usage:
cylinder := csg.Cylinder( Start(0, -1, 0), End(0, 1, 0), Radius(1), Slices(16))
func SolidFromPolygons ¶
SolidFromPolygons constructs a CSG solid from a list of `csg.Polygon` instances.
func Sphere ¶
Sphere constructs a solid sphere. Optional parameters are `Center`, `Radius`, `Slices`, and `Stacks`, which default to `Center(0, 0, 0)`, `Radius(1)`, `Slices(16)`, and `Stacks(8)`. The `Slices` and `Stacks` parameters control the tessellation along the longitude and latitude directions.
Example usage:
sphere := csg.Sphere( Center(0, 0, 0), Radius(1), Slices(16), Stacks(8))
func (*Solid) Intersect ¶
Intersect returns a new CSG solid representing space both this solid and in the solid `csg`. Neither this solid nor the solid `csg` are modified.
A.intersect(B)
+-------+
| |
| A |
| +--+----+ = +--+
+----+--+ | +--+
| B |
| |
+-------+
func (*Solid) Inverse ¶
Inverse returns a new CSG solid with solid and empty space switched. This solid is not modified.
func (*Solid) Subtract ¶
Subtract returns a new CSG solid representing space in this solid but not in the solid `csg`. Neither this solid nor the solid `csg` are modified.
A.Subtract(B)
+-------+ +-------+
| | | |
| A | | |
| +--+----+ = | +--+
+----+--+ | +----+
| B |
| |
+-------+
type Vector ¶
type Vector struct {
X, Y, Z float64
}
Vector represents a 3D vector.
Example usage:
csg.Vector{1, 2, 3}
csg.Vector{X: 1, Y: 2, Z: 3}
type Vertex ¶
type Vertex struct{ Pos, Normal Vector }
Vertex represents a vertex of a polygon. Use your own vertex class instead of this one to provide additional features like texture coordinates and vertex colors. Custom vertex classes need to provide a `Pos` property and `Flip()`, and `Interpolate()` methods that behave analogous to the ones defined by `csg.Vertex`. This struct provides `Normal` so convenience functions like `csg.Sphere()` can return a smooth vertex normal, but `Normal` is not used anywhere else.
Source Files