Generalized alternative implementation to transvoxel

[goatchurchprime]

I might have this wrong, but I spent a lot of work making various subdividing 2.5D voxel-type surface meshers (for 3-axis CNC simulation), and always thought that the marching cubes algorithm was a bit of a red herring.

My point is: I don't think you need a look-up table to work out those triangulations across each cell.

In my case (which was admittedly in 2D, but with heights) I had to make the right choice for the ambiguous faces (in Figure 3.1 of the paper). One idea was to test the value of the interiorness function in the middle of the quad and use (a) if was outside, or (b) if it was inside. If I didn't do this, then a long thin channel would get fragmented into a line of pockets.

If you take the 8 vertices of the cube connected by the 12 edges, and you paint the vertices and the parts of the edges green where they are inside the volume, you will have defined a number of connected components in green.

If you take one of these components -- which is just a connected set of wires with cut ends -- you will know the points at the ends of these wires, and they will form a non-planar polygon. (It will important to get the points in the correct order.)

Now, you can triangulate this non-planar polygon anyway you like, but some ways are better than others. For example, if you consider the simple 4 point one in &hash;11 of Table 3.2, you can see there are two ways to cut the diagonal. But you can use the one that the normals indicate will fold better.

Now I think this approach will apply to those trans-voxels exactly the same. For example, if one of the faces of the cube is split into four, and you pull the middle vertex out slightly, you've got a nice nonahedron, and the same algorithm applies.

The advantage of not using a lookup table and instead using a general purpose algorithm is that it doesn't form a blocker against having non-cubic or subdividing lattices.

---

I've not gone too deep into how everything works; just looking at the stuff I have past experience with. I have the code running in the C++ debugger in Visual Studio (never thought I'd be doing this again; my fingers can remember all the hot-keys).

The code I have looked at is where VoxelMesherTransvoxel::build() takes each block of 16x16x16 nodes, which have been embedded in a 19x19x19 block to include enough of the neighbours. This function applies VoxelMesherTransvoxel::build_internal() to create the surface triangles in the middle block of 15x15x15 cells, and then VoxelMesherTransvoxel::build_transition() on the blocks of 15x15x1 cells adjacent to each of the 6 faces of the middle block.

Now, I think there should be an intermediate structure between where you have the nodes and their values and the final mesh surface. I used to call this the weave. Consider a 16x16x16 cell block, this will have 3x17x17 fibres running through the nodes parallel to each of the 3 axes. Each fibre has a series of segments where you enter and exit the volume (it's most important that the crossing points are consistent). The endpoints of the segments (not on the external faces) will become the vertices in the mesh, so you can have them all allocated and indexed from the start without any complicated business of working it out as you go along, or recalculating each normal vector four times.

The weave doesn't need to be recorded as an array of 867 arrays of pairs of endpoints. You can pack it down as a list of (fibre-index, endpoint, normal), and this should take less space than the original 3D voxel volume (if you pack the normal into 3 bytes). Then it's probably in a better form for making and recording accurate edits, instead of having to hack the underlying voxel values to get the surface you wanted.

It might also lend itself to handling multiple terrain textures, because each entry in the list refers to one vertex, whereas a voxel value can influence between 0 and 6 vertices.

I haven't thought too hard about the LOD issues. Because my old code was for doing engineering of small metal parts, it needed to do subdivisions so as to model the sharp edges accurately.

I'll test out these ideas in isolation in a python notebook to see if there is a show-stopper somewhere in it, before I doing any C++ code. I was monolingual in C++ till about 8 years ago when I quit after 20 years in CAM software.

[Zylann]

I doubt Eric Lengyel spent all this time designing Transvoxel only to find out lookup tables were unnecessary. His use case was clearly real-time games. I don't really do research to find brand new techniques, I only look for existing ones, and those I implemented are the one that sounded more interesting and fit to what I wanted / could understand at the time. Surely there is probably a way to not use lookup tables, but that probably means slower computations and more complex code? Even the blocky mesher (the only one I wrote from scratch without a paper) still uses lookup tables, because it makes the code much more canonical, less redundant, easier to tweak.

Now if you think you have an idea for a new mesher, by all means, experiment to make it work, and compare its results with the others. I don't really get well what you are trying to achieve (and I must admit I don't dedicate much time into this for now, maybe I'll do one day, I do this in long cycles). You mentionned an intermediate structure: to my understanding of material I read so far, this is called a "dual" method. That is, using an intermediate data structure, between the voxel grid and the final result, as opposed to "primal" methods which use the grid directly (like MC or Transvoxel). In VoxelMesherDMC I used a dual method, but I'm not sure I got it entirely right (while it produced correct meshes, the simplification part was poor) and it turned out much slower than VoxelMesherTransvoxel. Speed plays a big role here. A fancier algorithm is not welcome if it performs too slowly to be usable in game (though it can still be implemented if need is).

Finally, the reason why voxels are ultimately a dense grid is also because anything can happen to them. Generators can model them from complex formulas, players can edit whatever they like, store any kind of data they want in cells, and it's very convenient and fast to access. It's also very simple to manage. There are forms of compression to reduce memory usage, and that's it. Also, there is no intention of going "infinite detail" or anything too fancy, this remains a moderate voxel engine for games, for which primary use are terrains or block-based structures.

So I'll wait to see what you have in mind ;)

[goatchurchprime]

It looks like it works.

The cut face traversing function is just ten lines long, when you use a foreright/backleft linking strategy between the edges of the polyhedron (eg split-faced cube). Like I said, I was doing this years ago, but with voxels that were tall and one-layer thick. Thinking back on what I was doing then, we were constrained by RAM that was less than 1% of what is routinely available now. This made the code a lot more complex.

The python code and further notes out the structures is at: https://github.com/goatchurchprime/digreality/blob/master/python_notebooks/cubical_barmesh.ipynb

Here's a picture of the half-voxel join without the transvoxels to show the cracks:

And here's one with the transvoxels split at the joining faces:

The cyan voxels are the last messy problem where a full voxel meets a half-voxel diagonally on only one edge. This took me an extra day to work out.

I guess I'm mainly looking for a sanity check that EL's transvoxel approach may be redundant (as it seems to me) -- because there's always a chance I'm wrong and wasting my time.

I think the technique can be extended to a lattice of polyhedra (cubes), not just a cube on its own (this code doesn't do that yet).

Currently the steps of the algorithm are:

[A: scalar function f(x,y,z)] --> [B: evaluations on a space grid (voxels) ] --> [C: cut points on a lattice ] --> [D: triangulated mesh surface]

At the moment the player edits [B] and it ripples through, but I believe they should be editing [C], which can have a lot more different shapes and control (eg a long thin tube around a lattice line, which would be a chain of octahedral beads if done at stage [B]). I think the [C] model would take less memory, because it only encodes the surface, and more easily handle different materials.

Also, with some extra mesh node labelling of how it embeds into the lattice, it might be possible to make the conversion of [D] back to [C], apply any edits, and then go back to [D], so that you wouldn't need to carry two copies of the geometry in different forms when it was in use.