From time to time, I like playing with 3D graphics, especially from a programmer’s point of view.

Constructive solid geometry, or CSG, is a modeling technique involving combining simpler objects with Boolean operations to obtain more complex ones.

A while ago, I found an implementation as a JavaScript library: CSG.js.

It really is brilliant because it is a complete tool in less than 600 rows, half of which are explanatory comments.

Its foundations are the clipping and the inversion operation. The former removes parts of a BSP tree inside another BSP tree, the latter swaps solid and empty space.

CSG.js combines them cleverly to implement Boolean union, subtraction, and intersection.

Even from a software engineering perspective, its author made some acute choices. And as a result, this project did not need to be updated in the latest ten years!

For example, library users can implement vertices with custom properties thanks to duck typing. They just need to implement a few methods and have a pos member. In this way, it is possible, for instance, to manage texture coordinates.

However, there are also some downsides. For example, CSG.js does not share vertices between polygons. Therefore, running some algorithms may require a merge by distance.

Anyway, it should be more than enough for my needs.

The only problem I have encountered so far is that the produced polygons can have any number of edges. I solved it with Earcut.

Earcut works only in 2D (the dimension parameter should be called stride instead), but it is not an issue with CSG.js because every polygon lies on a plane.

Therefore, for each polygon, it is possible to compute an orthonormal basis so that the third coordinate of each vertex is 0. Or, in other words, creating a reference system centered in the first vertex and computing the coordinates of each vertex in this space.

function tessellate(polygon) {
  // Translate everything so that the first vertex is the new origin
  let verts = Array.from(polygon.vertices, (v) =>
    v.pos.minus(polygon.vertices[0].pos)
  );

  // Normalize v1 - v0, and use it as a first vector for the new basis
  let d1 = verts[1].unit();
  // Create an orthogonal vector with the Gram–Schmidt process (d1 is already unitary, so we do not need to divide by its norm)
  let d2 = verts[2].minus(d1.times(verts[2].dot(d1))).unit();

  // Create a flattened array to pass to Earcut
  let coords = [];
  verts.forEach((v) => {
    coords.push(v.dot(d1), v.dot(d2));
  });

  return earcut(coords);
}

The indices obtained in this way can be used with the original vertices.

Earcut allows specifying holes in polygons, but CSG.js should already deal with them. At least according to my simple tests.