javascript - 在半边(DCEL)数据结构中有效地找到双边？

Question

我正在使用 HalfEdge 数据结构来表示网格上面之间的连接。

我正在导入一个外部模型，我在导入过程中构建了HalfEdge结构。然而，对于具有许多三 Angular 形的网格，构建过程会占用太多时间。

具体来说，连接半边的过程似乎占用了最多的时间。我想就如何改进我的算法获得一些建议。

下面是我用来初始化数据结构的代码。第一个 for 循环使用顶点数据创建一个 Face，同时将构成 Face 的 HalfEdges 插入一个单独的数组以供稍后使用。

第二个 for 循环负责查看所有 HalfEdge 的数组，并找到匹配对(即，两个是彼此的双胞胎)。

我注销了每个进程前后的时间，并注意到第二个循环是导致一切变慢的原因。

这是时间戳

start constructing DCEL 14:55:22

start making faces 14:55:22

end making faces 14:55:22

/* this is where it takes long.. almost 6 seconds on a mesh with 13000 triangles */

start linking halfEdges 14:55:22

end linking halfEdges 14:55:28

end constructing DCEL 14:55:28

这是实际的代码

console.log('start constructing DCEL', new Date().toTimeString());

// initialize Half-Edge data structure (DCEL)
const initialFaceColor = new THREE.Color(1, 1, 1);
const { position } = geometry.attributes;
const faces = [];
const edges = [];
let newFace;

console.log('start making faces', new Date().toTimeString());
for (let faceIndex = 0; faceIndex < (position.count / 3); faceIndex++) {
  newFace = new Face().create(
    new THREE.Vector3().fromBufferAttribute(position, faceIndex * 3 + 0),
    new THREE.Vector3().fromBufferAttribute(position, faceIndex * 3 + 1),
    new THREE.Vector3().fromBufferAttribute(position, faceIndex * 3 + 2),
    faceIndex);
  edges.push(newFace.edge);
  edges.push(newFace.edge.next);
  edges.push(newFace.edge.prev);
  newFace.color = initialFaceColor;
  faces.push(newFace);
}

console.log('end making faces', new Date().toTimeString());
console.log('start linking halfEdges', new Date().toTimeString());

/**
  * Find and connect twin Half-Edges
  * 
  * if two Half-Edges are twins:
  * Edge A   TAIL ----> HEAD
  *           =          =
  * Edge B   HEAD <---- TAIL
  */
let currentEdge;
let nextEdge;
for (let j = 0; j < edges.length; j++) {
  currentEdge = edges[j];

  // this edge has a twin already; skip to next one
  if (currentEdge.twin !== null) continue;

  for (let k = j + 1; k < edges.length; k++) {
    nextEdge = edges[k];

    // this edge has a twin already; skip to next one
    if (nextEdge.twin !== null) continue;

    if (currentEdge.head().equals(nextEdge.tail()) 
      && currentEdge.tail().equals(nextEdge.head())) {
          currentEdge.setTwin(nextEdge);
    }
  }
}

console.log('end linking halfEdges', new Date().toTimeString());
console.log('end constructing DCEL', new Date().toTimeString());

如何优化双边搜索过程？

Answer 1

我会尝试散列并查找边缘，例如像那样:

function hash(p1, p2) {
  return JSON.stringify(p1)+JSON.stringify(p2);
}
const lookup = {}
for (let j = 0; j < edges.length; j++) {
  lookup[hash(edge.head(), edge.tail())] = edge;
}
for (let j = 0; j < edges.length; j++) {
  const twin = lookup[hash(edge.tail(), edge.head())];
  !edge.twin && twin && !twin.twin && edge.setTwin(twin);
}