在 THREEJS 网格中对共面三角形进行分组的方法？

Question

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

为此，我想收集任何特定三角形的所有共面相邻面，以便在拖动时使用。我以 Simplifier, as well as this post 为例，但我想保留下面的三角形，而不是 reduce/remove。

在过去的好日子里，您可以构建一个边模型 Mantlya，您可以在其中遍历每条边以查看相邻面并检查法线。

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

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

此算法完成后，您应该拥有一个包含所有面的数组，这些面与您开始时的面共面且相邻。但是在我看来效率比较低

欢迎大家suggestions/pointers！

Answer 1

你的想法可行。

我添加了一个角度阈值，因此您可以抓取稍微非共面的 topography.I 必须创建一个 onEvent 以允许不确定的递归时间。应该修改为将 vertexHash 放在 mesh.userData 中。

//编辑。我已经更新了 class 以利用一个 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);

我将 class 添加到其他人的 fiddle 中，效果很好。 http://jsfiddle.net/fnuaw44r/

我更新了 fiddle 以使用钳位选项：http://jsfiddle.net/ta0g3mLc/

我想它会像您建议的那样效率低下，但这取决于网格。我添加了一个 "pendingRecursive" 变量。只要它不等于零，您就可以放置一个 gif 并在该值再次为零时将其删除。

无论如何这是一个起点。我相信聪明的人可以在没有嵌套 for 循环的情况下抛出面孔。

Answer 2

我已经按照我最初发布的问题中的项目符号编写了一个适合我的解决方案，并且不使用递归。也许这对某人有用。（注意：为了方便哈希和数组等，我使用 underscorejs）。

该算法首先在网格顶点上添加映射，列出每个顶点所属的所有面。从那里，我可以从一个特定的面开始，然后寻找与起始面共享至少一个顶点的所有共面面（并从那里开始）。如果共享两个顶点，那没关系。

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

下面是我的使用方法。我有一组网格（称为 csgPrimitives，因为它们来自 ThreeCSG.js。我为每个基元计算共面面组并将它们放在每个基元的几何体上。

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

每个生成的共面组包含共面数组和这些面使用的唯一顶点数组。使用顶点数组，我现在可以通过简单地应用 Vector3.add() 函数一次抓取并拖动网格中的所有共面面。

这项工作的原因可以通过下面的截图来阐明。为了创建所示的网格，生成了一个立方体，然后使用上面提到的 CSG 库从中减去一个球体。

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

球体距离足够远，实际上与立方体不相交，但经过运算后，立方体多了很多共面三角形，但不是一致的边界表示。例如，正如您在图中看到的那样，一些三角形与其他三角形的边缘的中间接触（几个示例由红色箭头指示）。

我写了另一个算法，尝试在三角形这样接触时进一步拆分三角形。该算法稍微改善了这种情况：

但仍然不完美，因为 CSG 库有时会生成接近直线的三角形（两个顶点靠得很近），导致舍入错误使我的算法失效。如果三角形边与网格中的多个其他三角形相交，它也不会很好地工作。

考虑到这一切，在一个完美的世界中，我实际上想将所有共面的面孔重新组合成一个面孔，然后让三个 js 正确地对生成的（更大的）面孔进行三角剖分（或使用其他一些库，如 libtess 去做）。

我正在寻找一种方法来执行此操作，现在我已将所有共面三角形组合在一起。在我看来，应该有一种算法，给定所有这些共面三角形的所有边，可以找到所有这些三角形的周长。这样我就可以生成一个新的三角形面来替换它们，使用 ShapeGeometry 之类的东西来创建一组新的三角形以插入到我的原始网格中。最终结果是，在应用所有这些之后，我将 return 到 CSG 库转换为 BSP 后首先创建的精确几何体，然后再转换为网格。

如果有人对实现第二个目标的最佳方法有任何想法，请发表评论。如果我想出一些好方法，我可能会把它贴在这里。现在我得到的最好的想法是：

想法 1：

在上述算法的相邻面的所有共面顶点集合中，找到离原点最远的顶点。
找到离开该顶点的所有边。
沿着从原点通过该顶点的向量到下一个顶点的最小角度的边。
在下一个顶点处，沿着使最大角度的边走到下一个顶点。（使用 dot() 和 cross() 以确保您正确选择一个角度，相对于所有共面的法线）。
到达第一个顶点时停止。理论上你已经走遍了所有面的周长（理论上！）

想法 2（光线投射）：

根据上述算法找到的共面创建一组唯一的共面边
从上述算法找到的共面顶点集中的每个顶点，沿着它所属的任何共面边投射一条射线。
如果顶点是内部顶点，则与其他顶点 and/or 边的交点数将为奇数。如果是，我们可以丢弃沿其投射光线的边以及内部顶点。
现在选择任何剩余的顶点。走它所属的任何边缘（现在应该只有两个）。继续走匹配的顶点与边（当然不是跟踪前一条边）直到你 return 到起始顶点。现在我们应该有了所有共面的周长。

要了解 CSG 库如何真正创建过于复杂的面，请查看当减去球体实际与立方体相交时的立方体网格：

如您所见，应该不受布尔运算影响的立方体边有大量内部三角形。

最后，拖动这些杂乱共面但不正确的 boundary-rep 网格表面的最终结果显示在下面的动画 gif 中。你会明白我为什么要简化网格，因为拖动会完全弄乱网格。

在 THREEJS 网格中对共面三角形进行分组的方法？

Way to group coplanar triangles in THREEJS mesh?

algorithm

computational-geometry

three.js

geometry-surface