Coded, recoded, lost, recoded and recoded … hemesh, 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 at least it holds poten­tial for growth.

What is hemesh?

hemesh 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 hemesh do?

The library is cur­rently focused on the stuff I coded it for: 3D voronoi and ran­dom plane divi­sions. So with hemesh we can cre­ate 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 hemesh 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 hemesh 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…

Get­ting hemesh

The library is main­tained at code.google.com. hemesh is cur­rently at beta ver­sion 1.1.0 Down­load and extract the archive inside the Pro­cess­ing ‘libraries’ folder. The ‘hemesh’ sub­folder con­tains sev­eral exam­ples. A Pro­cess­ing ver­sion sup­port­ing JAVA 1.5 syn­tax is rec­om­mended, Rev 180 or higher. In the com­ing days, I’ll post some tuto­ri­als and spiel­erei to illus­trate fur­ther use.

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 hemesh goes hay­wire on you, let me know! One major addi­tion is already planned: boolean mesh oper­a­tions. This is a small step away from completion.