如何在 THREEJS 网格中对共面三角形进行分组？

Question

我正在开发一种建模工具，可以让您直接操作网格。例如，您可以抓住一张脸并将其拖动。用户对“脸”的感知可能是多个共面三角形。例如，立方体的顶“面”实际上是两个三角形，它们被拖到一起形成一个正方形。

为了实现这一点，我想收集任何特定三角形的所有共面、相邻面，以便在拖动时使用。我已经查看了Simplifier以及这篇文章作为示例，但我想保留底层三角形，而不是减少/删除它们。

在过去的美好时光，您可以构建一个边缘模型 ala Mantlya，您可以在每个边缘上行走以查看相邻的面并检查法线。

我希望可能已经为 THREEJS 编写了一些代码，将共面三角形组合在一起。如果我从头开始写这个，我能想到的最好的算法是 O(n^2)，类似于：

1. 通过遍历所有面的所有顶点来构建边缘哈希（两个方向）。每个条目都是一个包含 2 个面指针的数组。您只需在创建或修改网格时执行此步骤一次。
2. 当用户选择要操作的面孔时，创建空的评估堆栈并将选取的面孔放入该堆栈中。另外，创建空的共面面阵列。
3. 将面从评估堆栈中弹出，并遍历该面的边缘。在边缘散列中查找与该边缘相邻的所有面。如果面共面，则将该面推入计算堆栈并存储在共面面数组中。
4. 重复步骤 3-4，直到计算堆栈为空。

当该算法完成时，您应该拥有一个所有面共面且与开始的面相邻的数组。但对我来说，这似乎效率相对较低。

欢迎任何和所有建议/指示！

Answer 1

你的想法可行。

我添加了一个角度阈值，以便您可以抓取稍微不共面的地形。我必须创建一个 onEvent 以允许不确定的递归时间。应该修改它以将 vertexHash 放入 mesh.userData 中。

//编辑。我已经更新了该类以利用夹紧参数，该参数允许您在设置为 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 循环的情况下遍历面孔。