A forgotten Historical benefit, of Marching Tetrahedra?

One of the facts which the WiKiPedia mentions, is, that for 20 years, there was a patent on the “Marching Cubes” algorithm, which basically forced some software developers – especially Linux and other, open-source developers – to use “Marching Tetrahedra” as an alternative. But I think that this article has one flaw:

Its assumptions are too modern.

What this article states is that, like Marching Cubes, individual tetrahedra can be fed to the GPU as “Triangle Strips”. The problem with this is the fact, that triangle strips are only recognized by the GPU, if DirectX 10(+), or OpenGL 3(+) is available, which means, that ‘a real Geometry Shader’ needs to be running.

Coders were working with Iso-surfaces, during the DirectX 9.0c / OpenGL 2 days, when there were no real Geometry Shaders. And then, one of the limitations that existed in the hardware was, that even if the Fragment Shader received vertices grouped as triangles, usually, Vertex Shaders would only get to probe one vertex at a time. So, what early coders actually did was, to implement a kind of poor man’s geometry shader, within the Fragment Shader. This was possible because one of the pixel formats which the FS could output, also corresponded to one of the vertex formats, which a VS could read as input.

Hence, a Fragment Shader running in this fashion would render its output – under the pretense that it would form an image – into the Vertex Buffer of another rendering pipeline. This was therefore appropriately named “Render-To-Vertex-Buffer”, or, ‘R2VB‘. And today, graphics cards exist, which no longer permit R2VB, but which permit OpenGL 4 and/or real Geometry Shaders, the latter of which, in turn, can group their Output Topologies into Triangle Strips.

This poses the question, ‘Because any one shader invocation can only see its own data, how could this result in a Marching Tetrahedra implementation?’ And I don’t fully know the answer.

Today, I can no longer imagine in a satisfyingly complete way, how the programmers in the old days solved such problems. Like many other people today, I need to imagine that the GPU does offer a Geometry Shader – a GS – explicitly, in order to implement a GS.


 

In a slightly different way, Marching Tetrahedra will continue to be important in the near future, because coders needed to implement the algorithm on the CPU, not the GPU, because they had Iso-Surfaces to render, but no patent-rights to the Marching Cubes algorithm, and, because programmers are not usually asked to rewrite all their predecessors’ code. Hence, code exists, which does all this purely on the CPU, and for which the man-hours don’t exist, to convert it all to Marching Cubes code.

(Update 5/09/2020, 17h30… )

Continue reading A forgotten Historical benefit, of Marching Tetrahedra?