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:
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!
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.