Way to group coplanar triangles in THREEJS mesh?

Question

I'm working on a modeling tool that lets you directly manipulate meshes. For instance, you can grab a face and drag it around. The user's perception of the "face" could be of more than one coplanar triangle. For instance, the top "face" of a cube would actually be two triangles that get dragged together as one square.

To accomplish this, I'd like to collect all coplanar, adjacent faces to any particular triangle for use when dragging. I've looked at Simplifier, as well as this post as examples, but I want to retain the underlying triangles, not reduce/remove them.

In the good ol' days, you'd build an edge model ala Mantlya, where you could walk each edge to see adjacent faces and check normals.

I was hoping there might be some code already written somewhere for THREEJS that groups coplanar triangles together. If I write this from scratch, the best algorithm I can think of is O(n^2), something like:

1. Build edges hash (both directions) by walking all vertices of all faces. Each entry is an array of 2 face pointers. You only need to do this step once when a mesh is created or modified.
2. When user picks a face to manipulate, create empty evaluation stack and put picked face into that stack. Also, create empty coplanar face array.
3. Pop face off evaluation stack, and walk edges of that face. Look up all faces adjacent to that edge in the edges hash. If face is coplanar, push that face onto evaluation stack and store in coplanar face array.
4. Repeat steps 3-4 until evaluation stack is empty.

When this algorithm finishes, you should have an array of all faces coplanar and adjacent to the face you start with. But it seems relatively inefficient to me.

Any and all suggestions/pointers welcomed!

Answer 1

I've coded a solution that works for me, along the lines of the bullets in the question I posted originally, and that does not use recursion. Perhaps this will be useful to someone. (Note: I use underscorejs for convenience with hashes and arrays etc).

This algorithm first adds mappings on the mesh vertices that list all faces that every vertex belongs to. From there, I can start at a particular face, and then look for all coplanar faces that share at least one vertex with the starting face (and go from there). If two vertices are shared, that's OK.

var COPLANAR_ANGLE_TOLERANCE = .1; // degrees, not radians
var RAD_TO_DEG = 180 / Math.PI;
var FACELEN = 3; // meshes have triangles by default

function checkCoplanarity(f1, f2) {
  return ((f1.normal.angleTo(f2.normal) * RAD_TO_DEG) <= COPLANAR_ANGLE_TOLERANCE);
}

function assignVertexFaceHashes(geometry) {
  var vertices = geometry.vertices;
  var faces = geometry.faces, face;
  var theVertex;
  for (var faceIndex in faces) {
    face = geometry.faces[faceIndex];
    for (var vertIndex of [face.a, face.b, face.c]) {
      theVertex = vertices[vertIndex];
      if (!theVertex.hasOwnProperty('inFaces')) {
        theVertex.inFaces = {};
      }
      theVertex.inFaces[faceIndex] = true;
    }
  }
}


function findCoplanarAdjacentFaces(startFaceIndex, geometry) {
  var adjoiningFaceIndexes;
  var coplanarAdjacentFaces = {};
  var coplanarAdjacentVertices = {};
  var examQueue = [];
  var examined = {};
  var examFace, examFaceIndex;
  var adjoiningFace, adjoiningFaceIndex;
  var faces = geometry.faces;
  var vertices = geometry.vertices;
  var startFace = faces[startFaceIndex];
  examQueue.push(startFaceIndex);
  // include the start face as a coplanar face
  coplanarAdjacentVertices[startFace.a] = true;
  coplanarAdjacentVertices[startFace.b] = true;
  coplanarAdjacentVertices[startFace.c] = true;
  coplanarAdjacentFaces[startFaceIndex] = true; 
  // Map vertices back to all faces they belong to
  assignVertexFaceHashes(geometry);

  while (examQueue.length > 0) {
    examFaceIndex = examQueue.pop();
    examFace = faces[examFaceIndex];
    // console.log('examQueue:', examQueue.length);
    adjoiningFaceIndexes = [];
    for (var vertIndex of [examFace.a, examFace.b, examFace.c]) {
      adjoiningFaceIndexes = _.union(adjoiningFaceIndexes, _.map(_.keys(vertices[vertIndex].inFaces), function(c) { return parseInt(c); }));
    }
    //console.log('adjoiningFaceIndexes:', adjoiningFaceIndexes);
    for (adjoiningFaceIndex of adjoiningFaceIndexes) {
      //console.log('Examining adjoining face index:', adjoiningFaceIndex);
      if (!examined.hasOwnProperty(adjoiningFaceIndex)) {
        if ((adjoiningFaceIndex != examFaceIndex) && (!coplanarAdjacentFaces.hasOwnProperty(adjoiningFaceIndex))) {
          //console.log('adjoiningFaceIndex:', adjoiningFaceIndex);
          adjoiningFace = faces[adjoiningFaceIndex];
          if (checkCoplanarity(examFace, adjoiningFace)) {
            var overlap1 = [adjoiningFace.a, adjoiningFace.b, adjoiningFace.c];
            var overlap2 = [examFace.a, examFace.b, examFace.c];
            var vertsInCommon = _.intersection(overlap1, overlap2);
            // Check for vertices in common. If any vertices are in comment, these coplanar faces touch at least one vertex.
            if (vertsInCommon.length > 0) {
              //console.log('Pushing adjoining face due to vertices in common:', adjoiningFaceIndex);
              coplanarAdjacentFaces[adjoiningFaceIndex] = true;
              examQueue.push(adjoiningFaceIndex);
              coplanarAdjacentVertices[adjoiningFace.a] = true;
              coplanarAdjacentVertices[adjoiningFace.b] = true;
              coplanarAdjacentVertices[adjoiningFace.c] = true;
            } else {
              // it's possible the adjoining face only touches vertices to the middle of edges, so check for that.
              edgeIntersectExam:
              for (var i = 0; i < FACELEN; ++i) {
                adjoinP1 = overlap1[i];
                adjoinP2 = overlap1[(i + 1) % FACELEN];
                for (var j = 0; j < FACELEN; ++j) {
                  splitPoint = distToSegmentSquared3d(vertices[overlap2[j]], vertices[adjoinP1], vertices[adjoinP2]);
                  if (splitPoint.distance < POINT_ON_LINE_TOLERANCE) {
                    console.log('adding adjoining face due to edge intersection:', adjoiningFaceIndex);
                    console.log('j=', j, 'Source face:', examFaceIndex, examFace, 'We found split point on adjoining face index:', adjoiningFaceIndex, adjoiningFace);
                    coplanarAdjacentFaces[adjoiningFaceIndex] = true;
                    examQueue.push(adjoiningFaceIndex);
                    coplanarAdjacentVertices[adjoiningFace.a] = true;
                    coplanarAdjacentVertices[adjoiningFace.b] = true;
                    coplanarAdjacentVertices[adjoiningFace.c] = true;
                    break edgeIntersectExam;
                  }
                }
              }              
            }
          }
        }
      }
    }
    examined[examFaceIndex] = true;
  }

  return ({ faces: coplanarAdjacentFaces, vertices: coplanarAdjacentVertices });
}

function assignFacesToCoplanarGroups(csgPrimitive) {
  var geometry = csgPrimitive.geometry;
  var faceIndexList = _.mapObject(_.keys(geometry.faces), function() { return true; });
  var processedFaces = {};
  var coplanarFaces;
  var faces = geometry.faces;
  var intIndex;
  var coplanarGroupMax;
  var coplanarGroups = [];
  for (var processFaceIndex in faceIndexList) {
    intIndex = parseInt(processFaceIndex);
    if (!processedFaces.hasOwnProperty(intIndex)) {
      coplanars = findCoplanarAdjacentFaces(processFaceIndex, geometry);
      coplanarGroups.push({ faces: coplanars.faces, vertices: coplanars.vertices });
      coplanarGroupMax = coplanarGroups.length - 1;
      for (var groupedFaceIndex in coplanars.faces) {
        faces[groupedFaceIndex].coplanarGroupIndex = coplanarGroupMax;
        faces[groupedFaceIndex].color.setHex(0x0000ff); // just to help see the results
        processedFaces[groupedFaceIndex] = true;
      }
    }
  }
  geometry.coplanarGroups = coplanarGroups;
  geometry.colorsNeedUpdate = true;
}

function assignFacesToAllCoplanarGroups() {
  var now = new Date();
  var startTime = now.getTime();
  for (var csgPrimitive of csgPrimitives.children) {
    assignFacesToCoplanarGroups(csgPrimitive);
  }
  var later = new Date();
  var duration = later.getTime() - startTime;
  console.log('Done assigning faces to coplanar groups in:', duration, 'ms');
}

Here is how I use it. I have an array of meshes (called csgPrimitives because they come from ThreeCSG.js. I calculate coplanar face groups for each primitive and put them on each primitive's geometry.

function assignFacesToAllCoplanarGroups() {
  var now = new Date();
  var startTime = now.getTime();
  for (var csgPrimitive of csgPrimitives.children) {
    assignFacesToCoplanarGroups(csgPrimitive);
  }
  var later = new Date();
  var duration = later.getTime() - startTime;
  console.log('Done assigning faces to coplanar groups in:', duration, 'ms');
}

Each resulting coplanar group contains an array of coplanar faces and an array of unique vertices used by those faces. Using the vertex arrays, I can now grab & drag all coplanar faces in a mesh at once by simply applying the Vector3.add() function.

The reason for this work may be clarified by the below screenshot. To create the mesh shown, a cube was generated and then a sphere was boolean subtracted from it using the CSG library mentioned above.

  var box = new THREE.Mesh( new THREE.BoxGeometry( width, height, length ) );

  // CSG GEOMETRY
  cube_bsp = new ThreeBSP( box );

  var cutgeo = new THREE.SphereGeometry( 0.5,32,32 );

  // move geometry to where the cut should be
  var matrix = new THREE.Matrix4();
  matrix.setPosition( new THREE.Vector3(0.25, 0, 1.88) ); // NB: sphere does not intersect with cube
  cutgeo.applyMatrix( matrix );

  var sub =  new THREE.Mesh( cutgeo );
  var substract_bsp  = new ThreeBSP( sub );
  var subtract_bsp  = cube_bsp.subtract( substract_bsp );

  csgPrimitiveMesh = subtract_bsp.toMesh(); 

The sphere is far enough away that it actually does not intersect with the cube, but nevertheless, after the operation, the cube has many additional coplanar triangles, yet is not a consistent boundary representation. For example, as you can see in the diagram, some triangles touch the middle of edges of other triangles (a couple examples are indicated by the red arrows).

I wrote another algorithm that attempts to split triangles up further when triangles touch like this. The algorithm improves the situation somewhat:

but still is imperfect because the CSG library sometimes produces triangles that are nearly lines (two vertices are very close together), causing rounding errors that throw my algorithm off. It also doesn't work well if a triangle edge is intersected by more than one other triangle in the mesh.

Given all this, in a perfect world, I would actually like to recombine all the coplanar faces into a single face, and then have THREEjs triangulate the resulting (larger) faces properly (or use some other library like libtess to do it).

I am looking for a way to do this, now that I have all the coplanar triangles grouped together. It seems to me that there ought to be an algorithm that, given all the edges of all these coplanar triangles, could find the perimeter of all of them. With that I could generate a newly triangulated face to replace them all using something like ShapeGeometry to create a new set of triangles to insert into my original mesh. The end result would be, after applying all this, I'd return to the exact geometry THREEjs BoxGeometry creates in the first place after conversion to BSP by the CSG library and then reconversion to a mesh.

If anybody has any ideas on best ways to accomplish this second goal, please comment. If I figure out some good way I may end up posting it here. Right now the best ideas I've got are:

Idea 1:

1. In the set of all coplanar vertices among adjoining faces from the above algorithm, find the vertex farthest from the origin.
2. Find all edges leaving that vertex.
3. Walk the edge that makes the minimum angle from a vector from the origin through that vertex, to the next vertex.
4. At the next vertex, walk the edge that makes the maximum angle to the next vertex. (use dot() and cross() to ensure you're picking an angle correctly, relative to the normal of all the coplanar faces).
5. Stop when you reach the first vertex. In theory you've walked the perimeter of all faces (in theory!)

Idea 2 (ray casting):

1. Create a collection of unique coplanar edges from the coplanar faces found by the above algorithm
2. Cast a ray from each vertex in the coplanar vertex set found by the above algorithm, along any coplanar edge it belongs to.
3. The number of intersections with other vertices and/or edges will be odd if the vertex is an interior vertex. If it is, we can discard the edge we cast a ray along, as well as that interior vertex.
4. Now pick any remaining vertex. Walk any edge it belongs to (there should now be only two). Continue to walk matching vertices with edges (not tracing over the previous edge of course) until you return to the start vertex. Now we should have the perimeter of all coplanar faces.

To see how the CSG library really creates overly complex faces, take a look at the cube mesh when a subtracting sphere actually does intersect the cube:

As you can see, the cube sides that should be unaffected by the boolean operation have a ton of internal triangles.

Finally, the end result of dragging these messy coplanar but incorrect boundary-rep mesh surfaces is shown in the animated gif below. You can see why I want to simplify the mesh as the dragging completely messes up the mesh.

Answer 2

Your idea works.

I added an angle threshold so you can grab slightly non-coplanar topography.I had to make an onEvent to allow for an indeterminate recursion time. It should be modified to put vertexHash in mesh.userData instead.

//edit. I've updated the class to utilize a clamp parameter that allows you to clamp the maxAngle to the original face when set to true. When set to false it will compare each face to next face.

faceUtils = function(){};
faceUtils.vertexHash = function(geometry){
  geometry.vertexHash = [];
  var faces = geometry.faces;
  var vLen = geometry.vertices.length;
  for(var i=0;i<vLen;i++){
    geometry.vertexHash[i] = [];
    for(var f in faces){
         if(faces[f].a == i || faces[f].b == i || faces[f].c == i){
            geometry.vertexHash[i].push(faces[f]);
       }
     }
   }
}

faceUtils.prototype.getCoplanar = function(maxAngle, geometry, face, clamp, out, originFace){
  if(clamp == undefined){
      clamp = true;
  }
  if(this.originFace == undefined){
    this.originFace = face;
  }
  if(this.pendingRecursive == undefined){
    this.pendingRecursive = 0;
  }
    this.result = out;
  if(out == undefined){
       this.result = {count:0};
  }
  if(geometry.vertexHash == undefined){
    faceUtils.vertexHash(geometry);
  }
  this.pendingRecursive++;
  var vertexes = ["a","b","c"];
  for (var i in vertexes){
    var vertexIndex = face[vertexes[i]];
    var adjacentFaces = geometry.vertexHash[vertexIndex];
    for(var a in adjacentFaces){
        var newface = adjacentFaces[a];
        var testF = this.originFace;
        if(clamp == false){
          testF = face
        }
        if(testF.normal.angleTo(newface.normal) * (180/ Math.PI) <= maxAngle){
          if(this.result["f"+newface.a+newface.b+newface.c] == undefined){
            this.result["f"+newface.a+newface.b+newface.c] = newface;
            this.result.count++;
            this.getCoplanar(maxAngle, geometry, newface, clamp, this.result, this.originFace);
          }
        }
    }
  }
  this.pendingRecursive--;

  if(this.pendingRecursive == 0 && this.onCoplanar != undefined){
    delete this.result.count;
    this.onCoplanar(this.result);
  }
}

Usage is simple:

         var faceTools = new faceUtils();
         faceTools.onCoplanar = function(rfaces){
           for(var i in rfaces){
              rfaces[i].color.setHex(0xff0000);
              intersects[0].object.geometry.colorsNeedUpdate = true;
           }
         }
         //params: maxangle, geometry, picked face
         faceTools.getCoplanar(13, geometry, face);

I added the class to someone else's fiddle and it works fine. http://jsfiddle.net/fnuaw44r/

I updated the fiddle to use a clamp option: http://jsfiddle.net/ta0g3mLc/

I imagine its terribly inefficient as you suggest, but it depends on the mesh. I added a "pendingRecursive" variable. So long as it's not equal to zero you could put up a gif and remove it when the value is zero again.

It's a starting point anyways. I am sure someone clever could toss through the faces without a nested for loop.