W:Blut HE_Mesh

Down­load the lat­est ver­sion here.

Coded, recoded, lost, recoded and recoded … HE_Mesh, the half-edge mesh library for Pro­cess­ing has slowly accreted to a state that war­rants a release. A release in more than one way. In ret­ro­spect, the cur­rent func­tion­al­ity looks depress­ingly small, espe­cially com­pared to the hun­dreds of hours that already went into cod­ing it. But like a broke home-owner with a base­ment and a half-finished first floor, I com­fort myself with the thought that it holds poten­tial for growth.

At least, that’s what I wrote more than a year ago. Some of the base­ment turned out mouldy, the first floor is some­what basic but live­able. The sec­ond floor is tak­ing shape and the gar­den is filled with a vari­ety of half-finished sheds… No doubt about it, I’m a bel­gian.

What is HE_Mesh?

HE_Mesh is an imple­men­ta­tion of a half-edge datas­truc­ture for manip­u­lat­ing 3D meshes in Pro­cess­ing. Basi­cally it’s a toolset to extend my Pro­cess­ing sand­box to a proper playground.

Gen­er­at­ing and dis­play­ing a mesh requires noth­ing more than a list of ver­tices and a list of faces con­nect­ing them. This hardly requires a spe­cial dataset. How­ever, manip­u­lat­ing a mesh in any but a triv­ial way requires a lot of con­nec­tiv­ity infor­ma­tion: neigh­bor­ing ver­tices, neigh­bor­ing faces, shared edges,… Keep­ing track of this in a sim­ple facelist type struc­ture is dif­fi­cult. Hence the need for a datas­truc­ture that incor­po­rates con­nec­tiv­ity infor­ma­tion in an effi­cient way: the half-edge mesh.

What can HE_Mesh do?

The library is cur­rently focused on the stuff I coded it for: generative/degenerative geom­e­try. So with HE_Mesh we can cre­ate and manip­u­late 3D meshes. Sev­eral prim­i­tives are built-in, but any kind of 2-manifold mesh can be turned into a half-edge mesh from its ver­tices and facelist. The weight of the imple­men­ta­tion lies in closed meshes but open sur­faces are han­dled as well.

Cre­at­ing meshes is cool (for a given amount of cool) but destroy­ing them is cooler. Sev­eral mod­i­fiers are pro­vided, either as part of the basic mesh func­tion­al­ity or as sep­a­rate mod­i­fier classes. Sub­di­vi­dors are a spe­cial class of mod­i­fier ori­ented towards sub­di­vi­sions. (The names might not be orig­i­nal but I guess it’s eas­ier to remem­ber than quaghot and umpsink.)

What HE_Mesh can’t do…

The half-edge datas­truc­ture has a few lim­i­ta­tions in itself. In prac­tice, each edge in a mesh can be shared by at most two faces. The imple­men­ta­tion is strongly face-based, iso­lated ver­tices and edges are not sup­ported and will lead to ouchie.

The ini­tial intent of HE_Mesh was to build a sys­tem to pro­to­type geo­met­ric play. So large-scale sys­tems were never a goal. Sev­eral imple­mented algo­rithms are O(n²) and use a lot of stor­age. Con­naiseurs and lec­tors in com­pu­ta­tional geom­e­try are advised to avoid perus­ing the code, bleed­ing eyes often offend. On the pos­i­tive side, there’s room for improvement…

HE_Mesh doesn’t turn Pro­cess­ing into Rhi­no­Java or 3D Stu­dio Pro­cess­ing. It does not pro­vide a GUI to manip­u­late meshes on-screen. Nei­ther was it con­ceived as a mod­el­ling library. Still, HE_Mesh pro­vides the ele­ments needed to build such an appli­ca­tion if needed.

Get­ting HE_Mesh

The library is main­tained at code.google.com. HE_Mesh is cur­rently at beta ver­sion 1.5.0. Down­load and extract the archive inside the Pro­cess­ing ‘libraries’ folder. The ‘ref­er­ence’ and ‘tuto­r­ial’ sub­fold­ers con­tain sev­eral examples.

Future

At this time, the library reflects my cur­rent inter­ests. If you want it to do some­thing else, have a sug­ges­tion or HE_Mesh goes hay­wire on you, let me know!

import wblut.hemesh.modifiers.*;
import wblut.core.processing.*;
import wblut.hemesh.creators.*;
import wblut.hemesh.core.*;

HE_Mesh mesh;
WB_Render render;

void setup() {
  size(800, 800, P3D);
  createMesh();

  HEM_SphereInversion modifier=new HEM_SphereInversion();
  modifier.setRadius(200);
  modifier.setCenter(50, 0, 0);
  modifier.setCutoff(1000);
  modifier.setLinear(false);
  mesh.modify(modifier);

  render=new WB_Render(this);
}

void draw() {
  background(120);
  directionalLight(255, 255, 255, 1, 1, -1);
  directionalLight(127, 127, 127, -1, -1, 1);
  translate(400, 400, 0);
  rotateY(mouseX*1.0f/width*TWO_PI);
  rotateX(mouseY*1.0f/height*TWO_PI);
  fill(255);
  noStroke();
  render.drawFaces(mesh);
  stroke(0);
  render.drawEdges(mesh);
}

void createMesh() {
  HEC_Cube creator=new HEC_Cube(300, 1,1, 1);
  mesh=new HE_Mesh(creator);
  mesh.modify(new HEM_Extrude().setDistance(300));
  mesh=new HE_Mesh(new HEC_FromFrame().setFrame(mesh).setMaximumStrutLength(20));
}

Did you code all of HE_Mesh?

Some­times you get wrapped up in writ­ing a piece of code, get­ting it to work your only pur­pose. Inevitably you turn to exist­ing code, rip­ping and tear­ing through it to get at its beat­ing heart.

With the inter­net pro­vid­ing access to such an amount of infor­ma­tion, it can be easy to for­get where a par­tic­u­lar solu­tion came from. On the other hand, includ­ing com­plete generic libraries to ben­e­fit from a few classes in spe­cific instances would quickly bloat any project. I tried to com­pile a list of code that was rav­aged for the good of HE_Mesh:

1. Javo­lu­tion is included in the HE_Mesh dis­tri­b­u­tion. This high-performance library offers fast, reli­able alter­na­tives for many of JAVA’s basic classes. With­out Fast­Table and FastMap, HE_Mesh would be a lot slower.
2. libssrckdtree-j Generic k-d tree Java library: only a bare­bone skele­ton remains of this truly generic k-d tree imple­men­ta­tion, wblut.tree.WB_KDTree and wblut.tree.WB_KDNeighbor. It pro­vides lightning-fast closest-point cal­cu­la­tion and degenerate-vertex check­ing. Although k-d tree algo­rithms are well-described, imple­ment­ing a fast one your­self is a less than triv­ial task.
3. Sean Luke’s fast Mersenne Twister ran­dom num­ber gen­er­a­tor is my pre­ferred RNG through­out hemesh. For (my) con­ve­nience it is exposed through wblut.math.WB_MTRandom, WB_RandomDisc and WB_RandomSphere.
4. Mar­ius Watz’ unlekker­Lib pro­vided the foun­da­tion for the wblut.hemesh.HE_Mesh.saveToSTL function.
5. The Fortune’s sweep algo­rithm for 2D Voronoi is often dis­cussed but rarely imple­mented. wblut.geom.WB_Voronoi2D is a bare-bones adap­ta­tion of Zhenyu Pan’s JAVA tran­scrip­tion of Shane O’Sullivan’s C implementation
6. John Lloyd’s QuickHull3D pack­age makes a reap­pear­ance as a con­vex hull gen­er­a­tor for the wblut.hemesh.modifiers.HEM_Wireframe joints.

Not only code is scav­enged with­out mercy, a whole range of ref­er­ence mate­r­ial on algo­rithms is scoured:

1. The über-reference Paul Bourke. Invalu­able for many geo­met­ric algo­rithms, espe­cially in HEC_IsoSurface.
2. Chris­ter Ericson’s Real-time Col­li­sion Detec­tion for many of the geo­met­ric datas­truc­tures and inter­sec­tion algo­rithms in wblut.geom.
3. Code pro­vided by Jon Squire served as the start­ing point for the basic pla­tonic solid cre­ators in wblut.hemesh.
4. Scloopy‘s ref­er­ence to a paper by Man­dal and Esan proved just the thing I needed for wblut.hemesh.modifiers.HEM_Wireframe.
5. A thou­sand page tome has added its bur­den to my desk: Geo­met­ric Tools for Com­puter Graph­ics by Philip Schnei­der and David Eberly. Its con­tents are increas­ingly imple­mented in HE_Mesh’s geo­met­ric back­bone. If HE_Mesh turns out to be sta­ble, this book deserves the praise. If not, it’s me that messed up somewhere…
6. David Marec was so gra­cious to pro­vide me with metic­u­lously com­piled ver­tex and con­nec­ti­tiv­ity data for a whole host of poly­he­dra. Not only was the data flaw­less, it was also almost directly usable. A rare for­tune indeed.

While HE_Mesh grows into dif­fer­ent areas, these lists will undoubt­edly expand. I just hope the need for proper book­keep­ing won’t spoil the fun of coding…