csg.js

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:

var cube = CSG.cube();
var sphere = CSG.sphere({ radius: 1.3 });
var polygons = cube.subtract(sphere).toPolygons();

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.build(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.build(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.

License

Copyright (c) 2011 Evan Wallace (http://madebyevan.com/), under the MIT license.

 
             		           
                               
                            
                                
               
class CSG
             		                            
             		           
                               
                            
                                
               
Holds a binary space partition tree representing a 3D solid. Two solids can
be combined using the union(), subtract(), and intersect() methods.
             		                            
CSG = function() {
  this.polygons = [];
};
             		           
                               
                            
                                
               
Construct a CSG solid from a list of CSG.Polygon instances.
             		                            
CSG.fromPolygons = function(polygons) {
  var csg = new CSG();
  csg.polygons = polygons;
  return csg;
};

CSG.prototype = {
  clone: function() {
    var csg = new CSG();
    csg.polygons = this.polygons.map(function(p) { return p.clone(); });
    return csg;
  },

  toPolygons: function() {
    return this.polygons;
  },
             		           
                               
                            
                                
               
Return a new CSG solid representing space in either this solid or in the
solid csg. Neither this solid nor the solid csg are modified.



A.union(B)

+-------+            +-------+
|       |            |       |
|   A   |            |       |
|    +--+----+   =   |       +----+
+----+--+    |       +----+       |
     |   B   |            |       |
     |       |            |       |
     +-------+            +-------+

             		                            
  union: function(csg) {
    var a = new CSG.Node(this.clone().polygons);
    var b = new CSG.Node(csg.clone().polygons);
    a.clipTo(b);
    b.clipTo(a);
    b.invert();
    b.clipTo(a);
    b.invert();
    a.build(b.allPolygons());
    return CSG.fromPolygons(a.allPolygons());
  },
             		           
                               
                            
                                
               
Return 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   |
     |       |
     +-------+

             		                            
  subtract: function(csg) {
    var a = new CSG.Node(this.clone().polygons);
    var b = new CSG.Node(csg.clone().polygons);
    a.invert();
    a.clipTo(b);
    b.clipTo(a);
    b.invert();
    b.clipTo(a);
    b.invert();
    a.build(b.allPolygons());
    a.invert();
    return CSG.fromPolygons(a.allPolygons());
  },
             		           
                               
                            
                                
               
Return 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   |
     |       |
     +-------+

             		                            
  intersect: function(csg) {
    var a = new CSG.Node(this.clone().polygons);
    var b = new CSG.Node(csg.clone().polygons);
    a.invert();
    b.clipTo(a);
    b.invert();
    a.clipTo(b);
    b.clipTo(a);
    a.build(b.allPolygons());
    a.invert();
    return CSG.fromPolygons(a.allPolygons());
  },
             		           
                               
                            
                                
               
Return a new CSG solid with solid and empty space switched. This solid is
not modified.
             		                            
  inverse: function() {
    var csg = this.clone();
    csg.polygons.map(function(p) { p.flip(); });
    return csg;
  }
};
             		           
                               
                            
                                
               
Construct an axis-aligned solid cuboid. Optional parameters are center and
radius, which default to [0, 0, 0] and [1, 1, 1]. The radius can be
specified using a single number or a list of three numbers, one for each axis.



Example code:



var cube = CSG.cube({
  center: [0, 0, 0],
  radius: 1
});

             		                            
CSG.cube = function(options) {
  options = options || {};
  var c = new CSG.Vector(options.center || [0, 0, 0]);
  var r = !options.radius ? [1, 1, 1] : options.radius.length ?
           options.radius : [options.radius, options.radius, options.radius];
  return CSG.fromPolygons([
    [[0, 4, 6, 2], [-1, 0, 0]],
    [[1, 3, 7, 5], [+1, 0, 0]],
    [[0, 1, 5, 4], [0, -1, 0]],
    [[2, 6, 7, 3], [0, +1, 0]],
    [[0, 2, 3, 1], [0, 0, -1]],
    [[4, 5, 7, 6], [0, 0, +1]]
  ].map(function(info) {
    return new CSG.Polygon(info[0].map(function(i) {
      var pos = new CSG.Vector(
        c.x + r[0] * (2 * !!(i & 1) - 1),
        c.y + r[1] * (2 * !!(i & 2) - 1),
        c.z + r[2] * (2 * !!(i & 4) - 1)
      );
      return new CSG.Vertex(pos, new CSG.Vector(info[1]));
    }));
  }));
};
             		           
                               
                            
                                
               
Construct a solid sphere. Optional parameters are center, radius,
slices, and stacks, which default to [0, 0, 0], 1, 16, and 8.
The slices and stacks parameters control the tessellation along the
longitude and latitude directions.



Example usage:



var sphere = CSG.sphere({
  center: [0, 0, 0],
  radius: 1,
  slices: 16,
  stacks: 8
});

             		                            
CSG.sphere = function(options) {
  options = options || {};
  var c = new CSG.Vector(options.center || [0, 0, 0]);
  var r = options.radius || 1;
  var slices = options.slices || 16;
  var stacks = options.stacks || 8;
  var polygons = [], vertices;
  function vertex(theta, phi) {
    theta *= Math.PI * 2;
    phi *= Math.PI;
    var dir = new CSG.Vector(
      Math.cos(theta) * Math.sin(phi),
      Math.cos(phi),
      Math.sin(theta) * Math.sin(phi)
    );
    vertices.push(new CSG.Vertex(c.plus(dir.times(r)), dir));
  }
  for (var i = 0; i < slices; i++) {
    for (var j = 0; j < stacks; j++) {
      vertices = [];
      vertex(i / slices, j / stacks);
      if (j > 0) vertex((i + 1) / slices, j / stacks);
      if (j < stacks - 1) vertex((i + 1) / slices, (j + 1) / stacks);
      vertex(i / slices, (j + 1) / stacks);
      polygons.push(new CSG.Polygon(vertices));
    }
  }
  return CSG.fromPolygons(polygons);
};
             		           
                               
                            
                                
               
Construct a solid cylinder. Optional parameters are start, end,
radius, and slices, which default to [0, -1, 0], [0, 1, 0], 1, and
16. The slices parameter controls the tessellation.



Example usage:



var cylinder = CSG.cylinder({
  start: [0, -1, 0],
  end: [0, 1, 0],
  radius: 1,
  slices: 16
});

             		                            
CSG.cylinder = function(options) {
  options = options || {};
  var s = new CSG.Vector(options.start || [0, -1, 0]);
  var e = new CSG.Vector(options.end || [0, 1, 0]);
  var ray = e.minus(s);
  var r = options.radius || 1;
  var slices = options.slices || 16;
  var axisZ = ray.unit(), isY = (Math.abs(axisZ.y) > 0.5);
  var axisX = new CSG.Vector(isY, !isY, 0).cross(axisZ).unit();
  var axisY = axisX.cross(axisZ).unit();
  var start = new CSG.Vertex(s, axisZ.negated());
  var end = new CSG.Vertex(e, axisZ.unit());
  var polygons = [];
  function point(stack, slice, normalBlend) {
    var angle = slice * Math.PI * 2;
    var out = axisX.times(Math.cos(angle)).plus(axisY.times(Math.sin(angle)));
    var pos = s.plus(ray.times(stack)).plus(out.times(r));
    var normal = out.times(1 - Math.abs(normalBlend)).plus(axisZ.times(normalBlend));
    return new CSG.Vertex(pos, normal);
  }
  for (var i = 0; i < slices; i++) {
    var t0 = i / slices, t1 = (i + 1) / slices;
    polygons.push(new CSG.Polygon([start, point(0, t0, -1), point(0, t1, -1)]));
    polygons.push(new CSG.Polygon([point(0, t1, 0), point(0, t0, 0), point(1, t0, 0), point(1, t1, 0)]));
    polygons.push(new CSG.Polygon([end, point(1, t1, 1), point(1, t0, 1)]));
  }
  return CSG.fromPolygons(polygons);
};
             		           
                               
                            
                                
               
class Vector
             		                            
             		           
                               
                            
                                
               
Represents a 3D vector.



Example usage:



new CSG.Vector(1, 2, 3);
new CSG.Vector([1, 2, 3]);
new CSG.Vector({ x: 1, y: 2, z: 3 });

             		                            
CSG.Vector = function(x, y, z) {
  if (arguments.length == 3) {
    this.x = x;
    this.y = y;
    this.z = z;
  } else if ('x' in x) {
    this.x = x.x;
    this.y = x.y;
    this.z = x.z;
  } else {
    this.x = x[0];
    this.y = x[1];
    this.z = x[2];
  }
};

CSG.Vector.prototype = {
  clone: function() {
    return new CSG.Vector(this.x, this.y, this.z);
  },

  negated: function() {
    return new CSG.Vector(-this.x, -this.y, -this.z);
  },

  plus: function(a) {
    return new CSG.Vector(this.x + a.x, this.y + a.y, this.z + a.z);
  },

  minus: function(a) {
    return new CSG.Vector(this.x - a.x, this.y - a.y, this.z - a.z);
  },

  times: function(a) {
    return new CSG.Vector(this.x * a, this.y * a, this.z * a);
  },

  dividedBy: function(a) {
    return new CSG.Vector(this.x / a, this.y / a, this.z / a);
  },

  dot: function(a) {
    return this.x * a.x + this.y * a.y + this.z * a.z;
  },

  lerp: function(a, t) {
    return this.plus(a.minus(this).times(t));
  },

  length: function() {
    return Math.sqrt(this.dot(this));
  },

  unit: function() {
    return this.dividedBy(this.length());
  },

  cross: function(a) {
    return new CSG.Vector(
      this.y * a.z - this.z * a.y,
      this.z * a.x - this.x * a.z,
      this.x * a.y - this.y * a.x
    );
  }
};
             		           
                               
                            
                                
               
class 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 clone(),
flip(), and interpolate() methods that behave analogous to the ones
defined by CSG.Vertex. This class provides normal so convenience
functions like CSG.sphere() can return a smooth vertex normal, but normal
is not used anywhere else.
             		                            
CSG.Vertex = function(pos, normal) {
  this.pos = new CSG.Vector(pos);
  this.normal = new CSG.Vector(normal);
};

CSG.Vertex.prototype = {
  clone: function() {
    return new CSG.Vertex(this.pos.clone(), this.normal.clone());
  },
             		           
                               
                            
                                
               
Invert all orientation-specific data (e.g. vertex normal). Called when the
orientation of a polygon is flipped.
             		                            
  flip: function() {
    this.normal = this.normal.negated();
  },
             		           
                               
                            
                                
               
Create a new vertex between this vertex and other by linearly
interpolating all properties using a parameter of t. Subclasses should
override this to interpolate additional properties.
             		                            
  interpolate: function(other, t) {
    return new CSG.Vertex(
      this.pos.lerp(other.pos, t),
      this.normal.lerp(other.normal, t)
    );
  }
};
             		           
                               
                            
                                
               
class Plane
             		                            
             		           
                               
                            
                                
               
Represents a plane in 3D space.
             		                            
CSG.Plane = function(normal, w) {
  this.normal = normal;
  this.w = w;
};
             		           
                               
                            
                                
               
CSG.Plane.EPSILON is the tolerance used by splitPolygon() to decide if a
point is on the plane.
             		                            
CSG.Plane.EPSILON = 1e-5;

CSG.Plane.fromPoints = function(a, b, c) {
  var n = b.minus(a).cross(c.minus(a)).unit();
  return new CSG.Plane(n, n.dot(a));
};

CSG.Plane.prototype = {
  clone: function() {
    return new CSG.Plane(this.normal.clone(), this.w);
  },

  flip: function() {
    this.normal = this.normal.negated();
    this.w = -this.w;
  },
             		           
                               
                            
                                
               
Split 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.
             		                            
  splitPolygon: function(polygon, coplanarFront, coplanarBack, front, back) {
    var COPLANAR = 0;
    var FRONT = 1;
    var BACK = 2;
    var SPANNING = 3;
             		           
                               
                            
                                
               
Classify each point as well as the entire polygon into one of the above
four classes.
             		                            
    var polygonType = 0;
    var types = [];
    for (var i = 0; i < polygon.vertices.length; i++) {
      var t = this.normal.dot(polygon.vertices[i].pos) - this.w;
      var type = (t < -CSG.Plane.EPSILON) ? BACK : (t > CSG.Plane.EPSILON) ? FRONT : COPLANAR;
      polygonType |= type;
      types.push(type);
    }
             		           
                               
                            
                                
               
Put the polygon in the correct list, splitting it when necessary.
             		                            
    switch (polygonType) {
      case COPLANAR:
        (this.normal.dot(polygon.plane.normal) > 0 ? coplanarFront : coplanarBack).push(polygon);
        break;
      case FRONT:
        front.push(polygon);
        break;
      case BACK:
        back.push(polygon);
        break;
      case SPANNING:
        var f = [], b = [];
        for (var i = 0; i < polygon.vertices.length; i++) {
          var j = (i + 1) % polygon.vertices.length;
          var ti = types[i], tj = types[j];
          var vi = polygon.vertices[i], vj = polygon.vertices[j];
          if (ti != BACK) f.push(vi);
          if (ti != FRONT) b.push(ti != BACK ? vi.clone() : vi);
          if ((ti | tj) == SPANNING) {
            var t = (this.w - this.normal.dot(vi.pos)) / this.normal.dot(vj.pos.minus(vi.pos));
            var v = vi.interpolate(vj, t);
            f.push(v);
            b.push(v.clone());
          }
        }
        if (f.length >= 3) front.push(new CSG.Polygon(f, polygon.shared));
        if (b.length >= 3) back.push(new CSG.Polygon(b, polygon.shared));
        break;
    }
  }
};
             		           
                               
                            
                                
               
class Polygon
             		                            
             		           
                               
                            
                                
               
Represents a convex polygon. The vertices used to initialize a polygon must
be coplanar and form a convex loop. They do not have to be CSG.Vertex
instances but they must behave similarly (duck typing can be used for
customization).



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).
             		                            
CSG.Polygon = function(vertices, shared) {
  this.vertices = vertices;
  this.shared = shared;
  this.plane = CSG.Plane.fromPoints(vertices[0].pos, vertices[1].pos, vertices[2].pos);
};

CSG.Polygon.prototype = {
  clone: function() {
    var vertices = this.vertices.map(function(v) { return v.clone(); });
    return new CSG.Polygon(vertices, this.shared);
  },

  flip: function() {
    this.vertices.reverse().map(function(v) { v.flip(); });
    this.plane.flip();
  }
};
             		           
                               
                            
                                
               
class Node
             		                            
             		           
                               
                            
                                
               
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.
             		                            
CSG.Node = function(polygons) {
  this.plane = null;
  this.front = null;
  this.back = null;
  this.polygons = [];
  if (polygons) this.build(polygons);
};

CSG.Node.prototype = {
  clone: function() {
    var node = new CSG.Node();
    node.plane = this.plane && this.plane.clone();
    node.front = this.front && this.front.clone();
    node.back = this.back && this.back.clone();
    node.polygons = this.polygons.map(function(p) { return p.clone(); });
    return node;
  },
             		           
                               
                            
                                
               
Convert solid space to empty space and empty space to solid space.
             		                            
  invert: function() {
    for (var i = 0; i < this.polygons.length; i++) {
      this.polygons[i].flip();
    }
    this.plane.flip();
    if (this.front) this.front.invert();
    if (this.back) this.back.invert();
    var temp = this.front;
    this.front = this.back;
    this.back = temp;
  },
             		           
                               
                            
                                
               
Recursively remove all polygons in polygons that are inside this BSP
tree.
             		                            
  clipPolygons: function(polygons) {
    if (!this.plane) return polygons.slice();
    var front = [], back = [];
    for (var i = 0; i < polygons.length; i++) {
      this.plane.splitPolygon(polygons[i], front, back, front, back);
    }
    if (this.front) front = this.front.clipPolygons(front);
    if (this.back) back = this.back.clipPolygons(back);
    else back = [];
    return front.concat(back);
  },
             		           
                               
                            
                                
               
Remove all polygons in this BSP tree that are inside the other BSP tree
bsp.
             		                            
  clipTo: function(bsp) {
    this.polygons = bsp.clipPolygons(this.polygons);
    if (this.front) this.front.clipTo(bsp);
    if (this.back) this.back.clipTo(bsp);
  },
             		           
                               
                            
                                
               
Return a list of all polygons in this BSP tree.
             		                            
  allPolygons: function() {
    var polygons = this.polygons.slice();
    if (this.front) polygons = polygons.concat(this.front.allPolygons());
    if (this.back) polygons = polygons.concat(this.back.allPolygons());
    return polygons;
  },
             		           
                               
                            
                                
               
Build 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).
             		                            
  build: function(polygons) {
    if (!polygons.length) return;
    if (!this.plane) this.plane = polygons[0].plane.clone();
    var front = [], back = [];
    for (var i = 0; i < polygons.length; i++) {
      this.plane.splitPolygon(polygons[i], this.polygons, this.polygons, front, back);
    }
    if (front.length) {
      if (!this.front) this.front = new CSG.Node();
      this.front.build(front);
    }
    if (back.length) {
      if (!this.back) this.back = new CSG.Node();
      this.back.build(back);
    }
  }
};