I have implemented a HalfEdge data structure to represent the connectivity between faces in my mesh.
While importing an external model, I construct the HalfEdge structure. However, for meshes with numerous triangles, the construction process is time-consuming.
The most time-consuming part of the process seems to be linking the half-edges together. I am seeking advice on how to enhance my algorithm.
Below is the code used to initialize the data structure. The first loop creates a Face with vertex data and stores the corresponding HalfEdges in a separate array for later use.
The second loop aims to identify matching pairs of HalfEdges (twins).
I monitored the timestamps before and after each step and observed that the second loop significantly slows down the process.
Time stamps are as follows:
start constructing DCEL 14:55:22
start making faces 14:55:22
end making faces 14:55:22
/* This is where the process takes time... almost 6 seconds for a mesh with 13000 triangles */
start linking halfEdges 14:55:22
end linking halfEdges 14:55:28
end constructing DCEL 14:55:28
Here is the actual code snippet:
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];
// Skip this edge if it already has a twin
if (currentEdge.twin !== null) continue;
for (let k = j + 1; k < edges.length; k++) {
nextEdge = edges[k];
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());
What optimizations can be made to speed up the search for twin edges?