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?

More about Framebuffer Objects

In the past, when I was writing about hardware-accelerated graphics – i.e., graphics rendered by the GPU – such as in this article, I chose the phrasing, according to which the Fragment Shader eventually computes the color-values of pixels ‘to be sent to the screen’. I felt that this over-simplification could make my topics a bit easier to understand at the time.

A detail which I had deliberately left out, was that the rendering target may not be the screen in any given context. What happens is that memory-allocation, even the allocation of graphics-memory, is still carried out by the CPU, not the GPU. And ‘a shader’ is just another way to say ‘a GPU program’. In the case of a “Fragment Shader”, what this GPU program does can be visualized better as shading, whereas in the case of a “Vertex Shader”, it just consists of computations that affect coordinates, and may therefore be referred to just as easily as ‘a Vertex Program’. Separately, there exists the graphics-card extension, that allows for the language to be the ARB-language, which may also be referred to as defining a Vertex Program. ( :4 )

The CPU sets up the context within which the shader is supposed to run, and one of the elements of this context, is to set up a buffer, to which the given, Fragment Shader is to render its pixels. The CPU sets this up, as much as it sets up 2D texture images, from which the shader fetches texels.

The rendering target of a given shader-instance may be, ‘what the user finally sees on his display’, or it may not. Under OpenGL, the rendering target could just be a Framebuffer Object (an ‘FBO’), which has also been set up by the CPU as an available texture-image, from which another shader-instance samples texels. The result of that would be Render To Texture (‘RTT’).

Continue reading More about Framebuffer Objects

Why R2VB Should Not Simply be Deprecated

The designers of certain graphics cards / GPUs, have decided that Render-To-Vertex-Buffer is deprecated. In order to appreciate why I believe this to be a mistake, the reader first needs to know what R2VB is – or was.

The rendering pipeline of DirectX 9 versus DirectX 11 is somewhat different, yet also very similar, and DirectX 9 was extremely versatile, with a wide range of applications written that use it, while the fancier Dx 11 pipeline is more powerful, but has less of an established base of algorithms.

Dx 9 is approximated in OpenGL 2, while Dx 10 and Dx 11 are approximated in OpenGL 3(+) .

Continue reading Why R2VB Should Not Simply be Deprecated

I have been test-driving Visual Studio Express 2015.

One of the projects which I attempted today on the Windows 7 desktop computer I name ‘Mithral’, was to compile OGRE 1.10 . This is an unstable build of OGRE, and it would be helpful for me to know whether this instability comes more, from the software, or from the weaker graphics card on my Linux laptop ‘Klystron’, which I have already had to switch to OGRE 1.9 .

My initial attempt to compile OGRE 1.10 failed in a foreboding way: The rendering window would open, and then be black for a second, and then give way to the nondescript Windows Error box, telling me that the program had crashed. There were no traces of error messages in the log to explain why. This is called “a silent crash”. Hypothetically, it could point to a borked compiler setup.

So what I did next was to download an OGRE 1.9 SDK, which had been entirely pre-compiled by OGRE devs. But then I knew this had been a waste of time, because it nowhere proves that my compiler can actually compile. And yes, that SDK was unstable on my stronger graphics card.

I have come to learn something. Even having a Microsoft compiler does not guarantee that I will be able to compile a DirectX rendering engine. The main reason for this, is the fact that DirectX 9 is almost deprecated. The up-to-date Microsoft SDK no longer includes libraries and header files, which legacy DirectX applications linked against – including OGRE. This means that the OGRE SDK can offer DirectX 11 support, not Dx 9, and its DirectX 11 support is unstable out-of-the-box. This is ultimately a fault of the software.

What I did next was to compile OGRE 1.9 . When I was setting up the CMake parameters to do so, I realized that when I had been setting up CMake for 1.10 , I had made mistakes that could have led to severe code-linking issues. Specifically, under Windows, it is tedious how we need to link to each core-dependency one-by-one. Under Linux or MinGW these can all get picked up in an automated batch. But with MSVC, it is not so easy.

Compiling OGRE 1.9 with the OpenGL2 and the OpenGL3+ rendering engines was a success, and so finally proved that my new compiler can produce moving, 3D images. Unfortunately though, 1.9 was code that still used the deprecated way of linking to the Windows SDK for Dx 9 and 11 , so that I could not build the DirectX 11 engine after all.

I found that just with OGRE 1.9.0 , and OpenGL2, I was able to get a larger set of animations to run, from the Sample Browser, than I was on my laptop. This proves, that much of the trouble I was having with ‘Klystron’, or before that, ‘Maverick’, were in fact hardware issues.

The Iso-Surface Demo works along a different principle than I had anticipated. It is one of those applications, which use a Fragment Shader, which renders to a Vertex Buffer, set up to look like a Pixel Buffer. The Pixel format output has been cleverly engineered also to correspond to a vertex attribute structure, thus achieving what was once known as ‘a poor mans Geometry Shader’.

The Iso-Surface Demo is supposed to work, even with the OpenGL2 rendering engine. Only, on my laptop, there is no support for Render To Vertex Buffer, aka ‘R2VB’.

With OGRE 1.9 , the OpenGL3+ rendering engine remains unstable as heck, unusable.

There is an issue with how VS 2015 ultimately works. Since ‘Mithral’ possesses 8 cores, threaded as 4, VS will ultimately try to build up to 8 targets at once. This pushes performance to the max, but at the expense of stability. Today I was pushing this compiler for hours and hours – and I later learned that it truly maxes out all 8 cores.

I found a setting to correct this for the future. Given 8 cores, I would like a maximum of 6 compile targets worked on concurrently. This is just, so that the system will have a full CPU left, to work on other tasks, should things go wonky. Because by the end of the day, things did go wonky – for whatever reason.

Dirk

(Edit 09/16/2016 : ) Another disadvantage, If we have an 8-core CPU, and If our compiler wants to build 8 targets concurrently for that reason, is the fact that 1 source file being compiled at a time, for each target, can consume an unpredictable amount of RAM. If the amount of RAM on the system is not taken into consideration, an ‘OOM’ (‘Out Of Memory’) condition can arise, because of the arbitrary 8 jobs running at once.

And I think that last night, such an OOM condition did arise, because I was installing tons of software… I have 8GB of RAM on ‘Mithral’. I performed numerous defragmentations as well, and, because many programs do have memory leaks, everything last night may have led up to an OOM condition by the end of the day.

I also installed Boost 1.61, and Boost 1.59, where before I only had Boost 1.47. And Boost 1.61 may in fact be necessary for OGRE 1.10 to compile, as another reason why my first attempt to compile that had failed.