Efficiently find twin edges in Half-Edge (DCEL) data structure?

Questions
1

Hello, I am using a HalfEdge data structure to represent the connectivity between the faces on my mesh.

I am importing an external model, and I am constructing the HalfEdge structure during the import process. However, with meshes with many triangles, the construction process takes up too much time.

Specifically, it appears that the process of linking the half-edges take up the most time.
I would like to get some advice on how to improve my algorithm.

Below is the code I am using to initialize my data structure. The first for-loop creates a Face with the vertices data, while pushing the HalfEdges that compose the Face into a separate array to be used momentarily after.

The second for-loop is reponsible for looking into the array of all HalfEdges, and finding matching pairs (i.e., the two that are twins of one another).

I logged out the time before and after each process, and noticed that the second loop is what slows everything down.

Here are the time stamps

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

And here is the actual code

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

How can I optimize the process of searching for twin edges?

2

/cc

1 Like
3

My question was indeed answered via that question on SO. I apologize if it is against the community standard to post duplicate questions across multiple forums. :cry: Should I delete this topic?

4

Don’t worry about that. I’m just linking the threads so it’s easier to follow the whole discussion. But in general, if your already have an answer at stackoverflow and this topic provides no further information, it’s better to delete it.