algorithm - 如何在三个JS网格中对共面三角形进行分组？

我正在开发一个建模工具，可以让你直接操纵网格例如，可以抓住一个面并将其四处拖动。用户对“脸”的感知可能不止一个共面三角形例如，立方体的顶部“面”实际上是两个三角形，作为一个正方形被拖到一起。
为了实现这一点，我想收集所有共面的，相邻的面到任何特定的三角形使用时，拖动我看了Simplifier和this post作为例子，但我想保留下面的三角形，而不是减少/删除它们。
在过去的好日子里，你可以建立一个边缘模型alaMantlya，在这里你可以走每条边缘来查看相邻的面并检查法线。
我希望已经有一些代码为3J编写了，把共面三角形组合在一起如果我从头开始写，我能想到的最好的算法是o（n^2），比如：
通过遍历所有面的所有顶点来构建边哈希（双向）。每个条目是一个由2个面指针组成的数组。创建或修改网格时，只需执行一次此步骤。
当用户选择要操作的面时，创建空的求值堆栈并将选择的面放入该堆栈另外，创建空共面面面阵列。
弹出面离评估堆栈，并漫游该面的边。在边哈希中查找与该边相邻的所有面如果面是共面的，则将该面推到求值堆栈上并存储在共面面面阵列中。
重复步骤3-4，直到求值堆栈为空。
当此算法完成时，应该有一个所有面的数组共面，并且与开始的面相邻但对我来说，这似乎相对低效。
欢迎任何和所有的建议/建议！

最佳答案

你的主意管用。
我增加了一个角度阈值，这样你就可以得到一个稍微不共面的地形，我必须做一个事件来考虑一个不确定的递归时间。应该修改为将vertexhash放在mesh.userdata中。
//编辑。我已经更新了这个类，使用了一个clamp参数，当设置为true时，它允许您将maxAngle钳制到原始面当设置为false时，它会将每个面与下一个面进行比较。

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);
  }
}

用法很简单：

         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);

我把这门课加到别人的小提琴上，效果很好。http://jsfiddle.net/fnuaw44r/
我更新了小提琴以使用钳制选项：http://jsfiddle.net/ta0g3mLc/
我认为它的效率极低，正如你所建议的，但这取决于网格。我添加了一个“pendingRecursive”变量只要它不等于零，您就可以建立一个gif，并在值再次为零时删除它。
无论如何，这是一个起点。我相信聪明的人可以在没有嵌套for循环的情况下翻过脸。