Combining coplanar polygons

[joostn]

Please forgive my enthusiasm for csg.js!

Take the following union of a cube and a larger, fully containing cube:

var cube1=CSG.cube({center: [0,0,0], radius: [1,1,1]});
var cube2=CSG.cube({center: [0,0,0], radius: [1.1, 1.1, 1.1]});
var result=cube1.union(cube2);
alert(result.polygons.length);
return result;

The resulting union contains 24 polygons while it can be represented with only 6 polygons (it's just a cube). Maybe not a big issue in this case but I'm running into problems when combining spheres and cylinders where the number of polygons quickly grows extremely large. I think the library should combine all overlapping coplanar polygons into one after each operation, do you have an idea where and how to implement this?

[joostn]

Here's a practical example of what I mean:

CSG.roundedCube = function(cuberadius, roundradius, resolution) {
  resolution = resolution || 8;
  cuberadius=new CSG.Vector(cuberadius);
  var innercuberadius=cuberadius.clone();
  innercuberadius.x -= roundradius;
  innercuberadius.y -= roundradius;
  innercuberadius.z -= roundradius;
  var result = CSG.cube({radius: [cuberadius.x, innercuberadius.y, innercuberadius.z]});
  result = result.union( CSG.cube({radius: [innercuberadius.x, cuberadius.y, innercuberadius.z]}));
  result = result.union( CSG.cube({radius: [innercuberadius.x, innercuberadius.y, cuberadius.z]}));
  for(var level=0; level < 2; level++)
  {
    var z = innercuberadius.z;
    if(level == 1) z = -z;
    var p1 = new CSG.Vector(innercuberadius.x, innercuberadius.y, z);
    var p2 = new CSG.Vector(innercuberadius.x, -innercuberadius.y, z);
    var p3 = new CSG.Vector(-innercuberadius.x, -innercuberadius.y, z);
    var p4 = new CSG.Vector(-innercuberadius.x, innercuberadius.y, z);
    var sphere = CSG.sphere({center: p1, radius: roundradius, slices: resolution, stacks: resolution});
    result = result.union(sphere);
    sphere = CSG.sphere({center: p2, radius: roundradius, slices: resolution, stacks: resolution});
    result = result.union(sphere);
    sphere = CSG.sphere({center: p3, radius: roundradius, slices: resolution, stacks: resolution});
    result = result.union(sphere);
    sphere = CSG.sphere({center: p4, radius: roundradius, slices: resolution, stacks: resolution});
    result = result.union(sphere);
    var cylinder = CSG.cylinder({start:p1, end: p2, radius: roundradius, slices: resolution});
    result = result.union(cylinder);
    cylinder = CSG.cylinder({start:p2, end: p3, radius: roundradius, slices: resolution});
    result = result.union(cylinder);
    cylinder = CSG.cylinder({start:p3, end: p4, radius: roundradius, slices: resolution});
    result = result.union(cylinder);
    cylinder = CSG.cylinder({start:p4, end: p1, radius: roundradius, slices: resolution});
    result = result.union(cylinder);
    if(level == 0) {
      var d = new CSG.Vector(0, 0, -2*z);
      cylinder = CSG.cylinder({start:p1, end: p1.plus(d), radius: roundradius, slices: resolution});
      result = result.union(cylinder);
      cylinder = CSG.cylinder({start:p2, end: p2.plus(d), radius: roundradius, slices: resolution});
      result = result.union(cylinder);
      cylinder = CSG.cylinder({start:p3, end: p3.plus(d), radius: roundradius, slices: resolution});
      result = result.union(cylinder);
      cylinder = CSG.cylinder({start:p4, end: p4.plus(d), radius: roundradius, slices: resolution});
      result = result.union(cylinder);
    }
  }
  return result;
}

return CSG.roundedCube([1,1,1], .2);

This creates a rounded cube but the flat part of each face is subdivided in more polygons than necessary.

[joostn]

By the way,

return CSG.roundedCube([1,1,1], .2, 32);

is resulting in a corrupted viewer display.

[evanw]

Yes csg.js has this problem because it is meant to be a simple implementation of the algorithm and so doesn't handle polygon merging. One way to implement polygon merging would be to keep track of which fragments came from which original polygon and just return the original polygon if no fragments were discarded. This gets tricky though because you have to flip the ancestor polygons as well as the current polygons when inverting a solid and invalidate ancestor polygons if fragments end up flipped in different orientations.

Another way would be to directly merge coplanar polygons in the result which would give you the nicest possible mesh. This involves detecting and removing T-junctions and then doing 2D CSG on the face contours and re-tessellating the outlining face contours back into convex polygons. Both of these approaches add a lot of complication however, and would really hurt the clarity of the code. I've thought about implementing these kind of things before but I would like to keep csg.js as a simple and easily understandable implementation of the algorithm.

This library has other issues as well and is not meant for production code, just to demonstrate the algorithm. Although it uses binary trees, there are no heuristics that attempt a balanced tree and so operations may be a lot worse then O(n log n) time. In particular, convex polyhedra will always generate linked lists which means operations will take O(n^2) time.

When you have a very complex solid with many tiny pieces, you may want to adjust CSG.Plane.EPSILON. Planes in csg.js have a thickness of twice that amount and any point within that distance of the plane is considered to be on that plane.

[joostn]

Thanks for the hints. I came to the same conclusion and ended up implementing your first suggestion, my fork now keeps track of the hierarchical splits of polygons and keeps the original polygon parts for the polygons that were split but not discarded. This greatly reduces polycount, especially if an object gets fully hidden inside a union, but it's not optimal yet.