three-halfedge-dcel

Doubly-Connected-Edge-List (DCEL) or Half-Edge data structure implementation for three.js

The Doubly-Connected-Edge-List (DCEL) or Half-Edge data structure is a compact and efficient representation of all faces, edges and vertices in a mesh, allowing fast spatial travel and queries.
DCEL Contains a list of faces in a geometry, each holding a cyclic linked-list of half-edges. Each half-edge is composed of two vertices and its twin half-edge on the adjacent face.
For more information wikipedia. Illustration:

Demo

This demo color the face pointed by the user, and color all its adjacent faces and their adjacent faces, upto the k-th steps distance, with color according to its adjacency steps distance from the pointed face.
https://erasta.github.io/three-halfedge-dcel

Install

npm install --save three-halfedge-dcel

Usage

import { Dcel } from 'three-halfedge-dcel';
const mesh = new THREE.Mesh(...); // get your mesh from somewhere
const dcel = new Dcel(mesh.geometry, {
    mergeVerticesThreshold: identical_vertices_max_dist // default: 1e-4
});
dcel.forAdjacentFaces(faceIndex, (adjacentFaceIndex) => {
    ... // do something with adjacent faces
})