Computer Graphics & Visualization @ufrj.br
function HalfEdge(tail,head){
this.head = head; //Integer index in vertex list
this.tail = tail; //Integer index in vertex list
this.next = null;
this.prev = null; // Add a link for reverse face circulations
this.twin = null;
this.face = null;
//Here, the next and twin values will be populated as the mesh is created.
}
function Vertex(point){
this.point = point; // Coordinate position
this.halfedge = null;
this.index = -1; // Index in vertex table
}
HalfEdgeMesh = {
function HalfEdgeMesh(){
this.verts = [];
this.edges = {};
this.geom = null; // Store the original geometry too
}
HalfEdgeMesh.prototype.addVert = function(point){
let v = new Vertex(point);
v.index = this.verts.length
this.verts.push(v);
}
HalfEdgeMesh.prototype.addHalfEdge = function(tail,head){
if(!([tail,head] in this.edges)){
// To store halfedges, we use the head and tail as a key to reference the halfedge object.
var E = new HalfEdge(this.verts[tail],this.verts[head]);
this.edges[[tail,head]] = E;
return E;
}
}
HalfEdgeMesh.prototype.populateFromThreeGeom = function(geom){
this.geom = geom;
for(var V in geom.vertices){
//Populate the vertices. Three.js uses index-based vert references, so we will too.
this.addVert(geom.vertices[V]);
}
for(var faceIndex in geom.faces){
var F = geom.faces[faceIndex];
// Each face is a tri, so we know what the vert pairs are for each face.
var vertPairs = [[F.a,F.b],[F.b,F.c],[F.c,F.a]];
for(var i = 0; i<3; i++){
var E=vertPairs[i];
// Create our half edges
var newEdge = this.addHalfEdge(E[0],E[1]);
newEdge.face = F;
// If the source vert doesn't have a half-edge yet, populate it.
if(this.verts[E[0]].halfedge == null){
this.verts[E[0]].halfedge = newEdge;
}
}
for(var i=0; i<3; i++){
var E = vertPairs[i]
// We know the next from the order around our tri, so populate that
this.edges[E].next = this.edges[vertPairs[(i+1) % 3]];
this.edges[E].prev = this.edges[vertPairs[(i+2) % 3]];
// Look for the halfedge going the opposite direction to populate the twin.
if([E[1],E[0]] in this.edges){
this.edges[E].twin = this.edges[[E[1],E[0]]];
this.edges[[E[1],E[0]]].twin = this.edges[E];
}
}
}
//
// Make sure that every edge has its twin adding border halfedges
let loop = {};
for (let [i,j] of Object.keys(this.edges).map(key => key.split(","))) {
let he = this.edges[[i,j]];
if (!he.twin) {
console.assert (!([j,i] in this.edges))
let newEdge = this.addHalfEdge(j,i);
newEdge.twin = he
newEdge.face = null; // border edges have a null face
he.twin = newEdge;
console.assert (!(j in loop))
loop[j] = newEdge
}
}
// Stitch together border halfedges
// Note to self: this only works if border edges don't cross
for (let j of Object.keys(loop)) {
let he = loop[j];
console.assert(he.head.index in loop)
he.next = loop[he.head.index];
loop[he.head.index].prev = he;
}
}
// Given a 'start' halfedge that has the tail at a vertex v,
// Returns an array of all edges having tail at v
HalfEdgeMesh.prototype.vertexCirculation = function (start) {
let result = [start];
// Obs: we use 100 as a counter to avoid infinite loop bugs
for (let i = 0, he = start; i < 100; i++) {
if (he.twin) {
he = he.twin.next;
if (he == start) break;
result.push (he)
}
else {
break;
}
}
return result;
}
HalfEdgeMesh.prototype.faceCirculation = function (he) {
let start = he;
let result = [he];
// A reasonable cap to prevent infinite loops
let n = 100;
he = he.next;
while(n-- > 0 && he != start) {
result.push(he);
he = he.next
}
return result;
}
return HalfEdgeMesh
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
