teaching machines

Boolean Utilities

June 9, 2021 by . Filed under public, slai-2021.

This post is part of a course on geometric modeling at the Summer Liberal Arts Institute for Computer Science held at Carleton College in 2021.

Composing boolean meshes is a complex task that requires time and knowledge exceeding the bounds of this camp. Instead of implementing the boolean operations yourself, you will use a library named CSG.js. CSG is an abbreviation of constructive solid geometry, a fancy name for the idea of composing shapes together to make other shapes. In this exercise, you will import the library and add some utility code that will convert between your mesh object format and the model format that the CSG library uses.

csg.js

You must import the CSG library into your project. There are many ways to do this. Since the CSG library is made up of a single text file, copying and pasting is the simplest way. Make a file in your project named csg.js and paste in the contents from the library’s csg.js.

In index.html, add a script element to head to load in this new file:

<script src="csg.js/csg.js"></script>

triplets

Your mesh objects have been using flat arrays, which look like this:

[x1, y1, z1, x2, y2, z2, ...]
[0, 1, 2, 1, 3, 2, ...]

The CSG library expects the coordinates and the vertex indices to be grouped together in triplets, which look like this:

[
  [x1, y1, z1],
  [x2, y2, z2],
  ...
]

[
  [0, 1, 2],
  [1, 3, 2],
  ...
]

You can turn a flat array into a grouped array with a loop that jumps by three indices on every iteration and an array method named slice, which extracts a subarray. The loop might look like this:

function triplets(array) {
  const groups = [];
  for (let i = 0; i < array.length; i += 3) {
    groups.push(array.slice(i, i + 3));
  }
  return groups;
}

Add this function to shapes.js.

meshToCsg

You need a function that turns a mesh object into a CSG object. Here’s a function that does the job:

function meshToCsg(mesh) {
  // Group the vertex coordinates together.
  const positions = triplets(mesh.positions);

  // Turn each face into a polygon, which is an array of vertices.
  return CSG.fromPolygons(triplets(mesh.triangles).map(indices => {
    return new CSG.Polygon([
      new CSG.Vertex(new CSG.Vector(positions[indices[0]]), {}),
      new CSG.Vertex(new CSG.Vector(positions[indices[1]]), {}),
      new CSG.Vertex(new CSG.Vector(positions[indices[2]]), {}),
    ]);
  }));
}

Add this function to shapes.js.

Notice how this code calls the triplets function above to group the coordinates and vertex indices together. The map call turns the array of index arrays into an array of CSG.Polygon objects. Each polygon is a triangle made of the coordinates of its three vertices. The CSG library does not use indexed geometry.

The sequence for generating a mesh and preparing it for boolean composition will look something like this:

const mesh = generateCube();
const csg = meshToCsg(mesh);

csgToMesh

Once you have a CSG object, you can call its union, subtract, or difference methods. Any parameters you send these methods must CSG objects as well. The result you get back is also a CSG object. To render it, you must convert it back to the mesh object format you have been using. Here’s a function that performs this conversion:

function csgToMesh(csg) {
  const positions = [];
  const triangles = [];

  let nvertices = 0;
  for (let polygon of csg.polygons) {
    // Each polygon is a list of vertices. Append those vertices' coordinates
    // to positions.
    for (let vertex of polygon.vertices) {
      positions.push(vertex.pos.x, vertex.pos.y, vertex.pos.z);
    }

    // The polygon will have 3 or more vertices. We triangulate the polygon by
    // taking three of its vertices at a time to form triangles.
    for (let j = 1; j < polygon.vertices.length - 1; ++j) {
      triangles.push(nvertices, nvertices + j, nvertices + j + 1);
    }

    nvertices += polygon.vertices.length;
  }

  return {positions, triangles};
}

Add this function to shapes.js.

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *