Tuesday, August 30, 2005

3D Rendering with Iso-surfaces

I am back on iso-surface rendering. After reading a lot of stuff on the subject I decided to experiment using points to render the surfaces. This is very easy to implement: you go through the whole volume, detect where an iso-surface lies (take a ‘cube’ composed of 8 voxels and see if all of them have values higher or lower than the iso-surface value; if they do, there is no iso-surface there, otherwise mark the center of the cube as an iso-surface point), and draw an OpenGL point for every detected position. Points can be drawn using glDrawArrays for very fast results. You also need to enlarge the size of the points, so that they do not leave holes between them, otherwise the ‘surface’ looks like a point cloud. Do that with glPointSize. Round points can be drawn with glEnable(GL_POINT_SMOOTH).
The results were not very nice. The image looked very ‘blocky’, as you can see here (click on image to enlarge).

To improve this I thought I had to resort to constructing a true surface (of triangles). The best-known algorithm for doing that is the ‘marching cubes’, but it is patented (!). I found some alternatives, but I was concerned of the speed factor, besides the fact that they all seemed rather complicated to implement. Then I read ‘Interactive Ray Tracing for Isosurface Rendering’ and ‘Iso-splatting: A Point-based Alternative to Isosurface Visualization’ (search Google and you will find the pdf files). From these papers I realized that the problem was not the points per se, or the supposedly reduced resolution of the data, but the position of the points. I was placing each point in the center of the ‘cube’ of eight voxels, but the iso-surface could be passing through the cube at any position. In this way, the points were all aligned to each other, producing the ‘blocky’ effect. The solution was to move the points towards the iso-surface. The papers, mentioned above, describe some sophisticated ways to do that (using Newton-Raphson or solving a cubic equation), but, not being mathematically so proficient, I thought of a simpler method: I start from the center of the cube and iteratively move towards the iso-surface as follows: I use the gradient vector inside the cube to specify the direction I will move along. The gradient points from lower to higher values. Therefore, I start from the center of the cube and calculate the value there. If it is smaller than the iso-surface value (i.e. I am inside the surface), I move along the gradient by an amount equal to 1/4 the side of the cube, otherwise I move in the opposite direction. Then I calculate the value at the new position and repeat the process, but each time I halve the distance that I move. 3 or 4 such steps are enough to give the result shown in the second image. The solution is approximate but the result is great and the extra code incurs a very small time penalty.

Notice that, no matter how many times you iterate, you will never end up outside the ‘cube’. Conversely, if the iso-surface is very close to one of the corners, you will never reach it, but that does not seem to affect the result much.

Monday, August 29, 2005

Delphi 2005, Firefox and Hyper-threading

I got Delphi 2005. Installed it, tested it, liked it, went back to Delphi 7. Why? Because it seems to have annoying bugs. The first thing I noticed was the very long loading time. This is, of course, not a bug, but still, it is irritating. Presumably there are a lot of things to load, because Delphi 2005 comes with .NET support and a whole lot of other stuff. Anyway, I am willing to put up with this, but then I noticed that things were really moving very slowly. Response was lethargic and there was no explanation (my machine is a 3GHz with 1Gb of RAM). Then, there were problems with loading the TLB library of my project (by the way, the Delphi 7 project loaded with no compatibility problems, which is a huge plus). The library editor would not show the contents properly and Delphi kept asking to save the TLB file every time I exited, even if nothing had been changed.
The most serious problem was the very slow response of the program. I searched the Internet and finally found the answer: Delphi 2005 seems to be incompatible with hyperthreading. What is this, you may ask. Well, as far as I understand, the new motherboards have a special feature that makes Windows think that there are two processors available, when you only have one. This way, some programs are supposed to work faster. However, it seems that this may cause incompatibilities. There is a way to disable this from inside Windows, but it has to be done every time you start the specific program. I tried it with Delphi 2005 and after disabling the ‘dual processor’, things breezed along. I then remembered that I had the same problems with Firefox. Firefox just hung up for long intervals and I had to give it up and return to Internet Explorer. However, after disabling the ‘dual processor’, Firefox worked fine. So, in the end, I decided to disable this feature completely. This was easily done by using the BIOS setup. You need to go to Advanced CPU configuration and disable Hyper-Threading technology. After that, Windows sees only one processor and everything works great.
The end result? I am back on Firefox, but I am waiting till Borland issues an update on Delphi 2005 to start using it.