寻找边缘，算法优化

Question

我在 THREE.Geometry() 中有识别边缘的直接函数。

var edges = []; 

for(var i = 0, l = geometry.faces.length; i < l; i++) {  findAdjacentFaces(i, edges, geometry); }


function findAdjacentFaces(face_, edges_, geometry_){

    var adjacentFaces = [];

    if(face_ >= 0 && face_ < geometry_.faces.length){

            for(var i = 0, l = geometry_.faces.length; i < l; i++){

                if(i != face_){

                    if(checkAdjacent(geometry_.faces[face_], geometry_.faces[i]) == true ){

                            adjacentFaces.push(i);

                    }

                }

                if(adjacentFaces.length > 2) { break; }

            }

    }

    if(adjacentFaces.length == 2){

        edges_.push(setEdge(face_, adjacentFaces[0], adjacentFaces[1], geometry_));

    }

}

function checkAdjacent(faceA_, faceB_){

    var values = [faceA_.a, faceA_.b, faceA_.c, faceB_.a, faceB_.b, faceB_.c].sort();

    var counter = 0;
    var duplicates = {}; 

    values.forEach(function(x) { duplicates[x] = (duplicates[x] || 0) + 1; if(duplicates[x] > 1) { counter++; } });

    if(counter == 2) { return true; } else { return false; }

}

function setEdge(faceA_, faceB_, faceC_, geometry_){

    var vertices = [], peak, tmpA, tmpB;
    var values =  [ geometry_.faces[faceA_].a, geometry_.faces[faceA_].b, geometry_.faces[faceA_].c, 
                    geometry_.faces[faceB_].a, geometry_.faces[faceB_].b, geometry_.faces[faceB_].c, 
                    geometry_.faces[faceC_].a, geometry_.faces[faceC_].b, geometry_.faces[faceC_].c ].sort();

    var sideA = [geometry_.faces[faceA_].a, geometry_.faces[faceA_].b, geometry_.faces[faceA_].c];
    var sideB = [geometry_.faces[faceB_].a, geometry_.faces[faceB_].b, geometry_.faces[faceB_].c];
    var sideC = [geometry_.faces[faceC_].a, geometry_.faces[faceC_].b, geometry_.faces[faceC_].c];

    var counter = 0;
    var duplicates = {}; 

    values.forEach(function(x) { duplicates[x] = (duplicates[x] || 0) + 1; });

    for (const key of Object.keys(duplicates)) { 

        if(duplicates[key] == 2) { vertices.push(key); } 
        else if(duplicates[key] == 3) { peak = key; } 

    }

    return  [ Number(vertices[0]), Number(vertices[1]) ];

}

它returns 几何体边上的所有顶点索引。工作正常，但很慢。什么可以优化以加快速度？

Answer 1

问题的初始代码检查每个几何面的所有几何面，以确定相邻面对和相应的边。虽然这会提取所有非边界边，但这会导致几何体/网格面数的二次算法复杂性（以及边或顶点数量的二次复杂性）。可能有一些额外的实际开销（例如 setEdge() 函数）可以删除。

这是一个提取网格所有边的提议（这使用了额外的工作空间，其数量与网格中的面数相同）具有拟线性时间复杂度（N log N 由于边排序）并且可能更少的开销：

从网格面中提取所有未定向的边（作为两个顶点索引的排序对），
丢弃所有唯一的无向边，只保留属于至少两个面的无向边。

下面是一个可能的实现示例：

// A cube
var faces = [
  {a: 0, b: 1, c: 2}, {a: 2, b: 3, c: 0}, // Front
  {a: 1, b: 5, c: 6}, {a: 6, b: 2, c: 1}, // Right
  {a: 5, b: 4, c: 7}, {a: 7, b: 6, c: 5}, // Back
  {a: 4, b: 0, c: 3}, {a: 3, b: 7, c: 4}, // Left
  {a: 3, b: 2, c: 6}, {a: 6, b: 7, c: 3}, // Top
  {a: 4, b: 5, c: 1}, {a: 1, b: 0, c: 4}, // Bottom
];

function compareEdges(edge1, edge2) {
  var i1 = edge1[0];
  var i2 = edge2[0];

  if (i1 != i2)
    return i1 < i2 ? -1 : 1;

  var j1 = edge1[1];
  var j2 = edge2[1];

  if (j1 != j2)
    return j1 < j2 ? -1 : 1;

  return 0;
}

function discardUniqueEdges(edges) {
  var i, j, n;
  var count;

  edges.sort(compareEdges);

  count = 0;
  j = 0; // The range [0, j[ of the array stores duplicated edges

  for (i = 0, n = edges.length; i < n; i++) {
    if (!count) {
      count = 1;
      continue;
    }

    if (!compareEdges(edges[i - 1], edges[i])) {
      ++count;
      continue;
    }

    // edges[i - 1] != edges[i]
    if (count <= 1)
      continue;

    // edges[i - 1] != edges[i] && count > 1
    edges[j][0] = edges[i - 1][0];
    edges[j][1] = edges[i - 1][1];
    j += 1;
    count = 1;
  }

  if (count > 1) {
    edges[j][0] = edges[i - 1][0];
    edges[j][1] = edges[i - 1][1];
    j += 1;
  }

  edges.length = j;

  return edges;
}

function extractEdges(faces) {
  var edges = [];
  var face;
  var i, n;

  // Store all edges
  for (i = 0, n = faces.length; i < n; i++) {
    face = faces[i];
    edges.push([face.a, face.b].sort());
    edges.push([face.b, face.c].sort());
    edges.push([face.c, face.a].sort());
  }

  return discardUniqueEdges(edges);
}

var edges = extractEdges(faces);
console.log(edges.length)
console.log(edges)

Answer 2

// A cube
var faces = [
  {a: 0, b: 1, c: 2}, {a: 2, b: 3, c: 0}, // Front
  {a: 1, b: 5, c: 6}, {a: 6, b: 2, c: 1}, // Right
  {a: 5, b: 4, c: 7}, {a: 7, b: 6, c: 5}, // Back
  {a: 4, b: 0, c: 3}, {a: 3, b: 7, c: 4}, // Left
  {a: 3, b: 2, c: 6}, {a: 6, b: 7, c: 3}, // Top
  {a: 4, b: 5, c: 1}, {a: 1, b: 0, c: 4}, // Bottom
];

function compareEdges(edge1, edge2) {

  if(edge1[0] == edge2[0] && edge1[1] == edge2[1]) { edge1[2]++; edge2[2]++; }

  var i1 = edge1[0];
  var i2 = edge2[0];

  if (i1 != i2)
    return i1 < i2 ? -1 : 1;

  var j1 = edge1[1];
  var j2 = edge2[1];

  if (j1 != j2)
    return j1 < j2 ? -1 : 1;

  return 0;
}

function discardUniqueEdges(edges) {
  var i, j, n;
  var count;

  edges.sort(compareEdges);

  count = 0;
  j = 0; // The range [0, j[ of the array stores duplicated edges

  for (i = 0, n = edges.length; i < n; i++) {
    if (!count) {
      count = 1;
      continue;
    }

    if (!compareEdges(edges[i - 1], edges[i])) {
      ++count;
      continue;
    }

    // edges[i - 1] != edges[i]
    if (count <= 1)
      continue;

    //edges[i - 1] != edges[i] && count > 1
    edges[j][0] = edges[i - 1][0];
    edges[j][1] = edges[i - 1][1];
    edges[j][2] = edges[i - 1][2];
    j += 1;
    count = 1;
  }

  if (count > 1) {
    edges[j][0] = edges[i - 1][0];
    edges[j][1] = edges[i - 1][1];
    edges[j][1] = edges[i - 1][2];
    j += 1;
  }

  edges.length = j;

  return edges;
}

function extractEdges(faces) {
  var edges = [];
  var face;
  var i, n;

  // Store all edges
  for (i = 0, n = faces.length; i < n; i++) {
    face = faces[i];
    edges.push([face.a, face.b].sort()); edges[edges.length - 1].push(0);
    edges.push([face.b, face.c].sort()); edges[edges.length - 1].push(0);
    edges.push([face.c, face.a].sort()); edges[edges.length - 1].push(0);
  }

  return discardUniqueEdges(edges);
}

var edges = extractEdges(faces);
console.log(edges.length)
console.log(edges)

我尝试在您的 extractEdges() 函数之后添加另一个参数 [2] 作为重复项计数器和排序边，以捕获那些没有副本的边。

Answer 3

function discardUniqueEdges(edges) {

var hash = {};

for(var i = 0, l = edges.length; i < l; i++){

    var ab = [edges[i][0], edges[i][1]];

    if (!(ab in hash)) { hash[ab] = 1; }

    if((ab in hash)) { hash[ab]++; }

}

var sorted = [];

Object.keys(hash).forEach(function(key) {
  if (hash[key] == 2) { sorted.push(key.split(",")); }
});

return sorted;

}

除了 @user3146587 提议之外，这也很有效。

寻找边缘，算法优化

Looking for edges, algorithms optimization

algorithm

optimization

three.js

3d

edge-detection