Development Journal of a Raytracer

Time for the review of October and the outlook for November.

Today I finally did what I didn't want to do, I dropped the matrix stuff and went to the simpler way to control where the car is by using the combination of position and relative angle. That can be set together to form the matrix I need to position the car-object.

And after trying forever to get something working, this solution indeed does work. The car moves as intended, top speed is too slow and the turn radius is also too small, though. So now I hope I can finally find out, where I went wrong with the matrix code I created before as I can now compare the two matrices when they start to develop in different directions. Then I can look into where I limited top speed and limit the turn radius to sensible values.

I have finally finished the selection mode as well. Now only one big area is remaining, the ability to reposition the camera so that the work plane is aligned to some structure or selection of the model. But first I have to fix another problem I knew about for some days but have chosen to ignore. Currently the editor for the Free Edit Modifier only works when the object is at the origin of world space. I have ignored the matrices which can be in use for the element. I have done that, as it is hard enough to get this editing stuff right without getting confused by the matrices all the time. Additionally in my experience it is easier to get matrix stuff right when you have a working program where only some transformations are wrong.

I continued with the selection mode. The new functions in the mouse handlers are added and should be called now. The selection of vertices, edges and faces with the ability to toggle or deselect should also work now. I just couldn't test it, if you used VS 2008 you probably know of the problems it sometimes has with its PDB-files. It seems to be rather good in damaging them. Well, it refused to attach the debugger as something was wrong with the PDB, so I need a rebuild to test the new stuff.

The program also should be able to discern, if any existing object was clicked and branch into a special handler if nothing was found. This branch will then set the plane origin which I also use as the center of rotation. So that should soon also work.

The last thing to add is handling rectangle selection. That shouldn't be hard either. So I hope to finish this thing soon.

Today I have a good excuse for not having done much, I ordered parts for my new system. And had troubles with a stupid shopping system. The new box will be a quad core Opteron with two processors and 8GB RAM. So I will have to do a lot of parallelization to get my raytracer to take advantage of it. I will also try to make the editor take advantage of that power. I have some ideas already, but I have to see, how much they get me and if the necessary code makes the program harder to debug or use. Most ideas should also benefit me on my single core laptop, I plan to e.g. move the creation of the structure needed to render polyhedron to a helper thread. That should make the program quite a bit more responsive at the cost of not seeing the result in real time but at a short delay.

Apart of that I also started on the mode switch. Not much, but at least I started. I hope to get the selection stuff into the program tomorrow. They only thing a bit more complex is the selection of an arbitrary point as the plane origin.

I was really lazy today and did not do a lot. I checked that Visual Studio 2008 can handle the code changes I needed for GCC 4.2.2 and it seems to be ok. So porting to GCC 4.2.2 is done for now.

I also changed the point size of selected vertices. Then I thought about how to continue with the Free Edit Modifier. The next thing to do is the enhanced selection. I think I will add a mode switch to change between editing and selecting. In selection mode I will make all my regular selection commands available (so I can also deselect an edge for example), will add support for rectangle selection and will also make it possible to just set the point to define the distance of the work plane from the camera plane. That will allow me to rotate or scale with a completely freely selected point.

If I would not slowly get annoyed with this thing, I would have probably been able to implement that already. But this Free Edit Modifier takes so long, that I slowly loose my motivation. I keep telling myself that it isn't much I am missing, but every time I hit another gap in my plans, that doesn't help my motivation either.

The last thing I looked into today was the changes to the virtual image I plan. The virtual image is a class which basically receives the raw rendered image and then applies the filters and writes the finished image to disk. I plan to extend that abstraction to also control the rendering. That way I should be able to implement multithreading support to the program. It won't be the only change needed, but it is a first important step.

The Free Edit Modifier now can handle the two other transformations as well. The idea to use the point which defines the plane as origin indeed seems to be good. But (there always is a but, isn't there?) it also has some issues. The first is simple to fix, I can't clearly see the selected point, I will have to change the way it is rendered a bit. The second is, that it is hard to set it. I can't set it to an arbitrary point as that would create a new vertex. But I can't even set it to an arbitrary vertex, as I am constantly in the danger to create a new edge or split a face. I will have to think about a way to handle those problems.

The implementation of this feature and especially testing it revealed some bugs. Most I finished, one is still open. Currently I can't connect two existing vertices, I had thought I had added code to do that. I will have to check where the problem is. The bugs I fixed were missing checks, e.g. I tried to split a face on an edge which is part of the edge loop of the face. It is impossible to place a split there. The case is now handled correctly.

And I found a bug in very old code, the code to calculate the angle between two vectors resulted in an NaN. The problem was caused by a precision issue, to calculate the angle I use the dot product. The dot product of two vectors u and v is |uv|cos a with a being the enclosed angle. So to get the angle I divide the dot product by the factor uv (the absolute is then unnecessary, the sign of numerator and denominator cancel out) and then calculate the arccos. What happened was, that the numerator was slightly bigger than the denominator and arccos is not defined on values bigger than 1.

In the last few days I have occasionally tried to finish the porting to GCC 4.2. I ran into some bugs which GCC 3.3 and Visual Studio 8 didn't complain about. And I ran into one big problem. One of the weak areas of C++ is in the template support when you don't want to put the implementation into a header. I would have to check the standard if it is supposed to work or not, I think I remember that it was supposed to work. But there were in the past so many problems with that that you normally can't use it portably, instead you put the implementation into a header.

But there is one way it is still useful to put the implementation of a template in a source file and not in a header, if the template is supposed to be used only by functions in that source. That second, more limited way, is what I have been doing. But it is not purely an implementation artifact, I have the declaration in the header as some classes derive from that template. So I can use the template normally, but only for the types I have instanced in the source file.

That last thing is the problem. In theory I need an explicit template instantiation. But in the past I had problems doing that as Visual C++ 6 didn't handle that correctly. I found out, that VC6, GCC3 and VS8 also were content with an guiding template specialisation in the header. But GCC 4.2 no longer works with that, it needs the instantiation. I just hope VS8 can handle that as well, because I don't really want to put ifdefs around those things. I will try that tomorrow.

Moving of vertices now also works. I had expected to run into a bug, I just had not anticipated where I would find it, the Change Geometry Helper had one. And I now also know how to implement rotation and scaling. The rotation needs an axis, the direction was already clear, the direction orthogonal to the camera plane. I only had no good idea of what point to use in the plane to fully define an axis. The same was true with the scaling, I need a fix point to define into which direction to scale the vertices.

The solution is simple, I already had the point, I just didn't recognize it. I had a similar problem at the start, I needed a point to define where the plane lies. And I can use that point as center of rotation and scaling. The advantage is, that I can already move it to any vertex. The vertices are very likely centers of rotation. So all I need is to add an additional function to be able to move that point freely without changing the plane and I can fully control rotating and scaling the vertices without influencing the rest of the modifier.

I don't get it. I don't move a bit with this stupid movement stuff. The car still does something completely wrong, but whatever I have the program check, it seems to be correct. Just the result is wrong. I slowly run out of options.

Today I have implemented the code to transform vertices. I didn't have enough time to test it, so it will probably have some stupid bugs. But I think it should be complete. So next is the handling of rotation and scaling operations. And then the second group of operations should be implemented and only one is remaining.

The last group of operations doesn't change the geometry or topology, it changes the camera. As the camera defines the plane in which new vertices are created and defines some parameters for the transformations, it is necessary to be able to define the plane by being able to move the camera. I intend to add operations so I can define a plane (e.g. by showing a face) and the code moves the camera so that the work plane is then in that face.

The next feature the Free Edit Modifier will get is to move vertices. Or rather to transform them, I also want to have the ability to scale and rotate the vertices. I started with the translations as they are simpler than the other two as I don't need to come up with a good idea for the center of scaling or rotation and the translation from mouse movement to a matrix is straight forward.

The code currently tracks the mouse and calculates how far the mouse has moved on the work plane I use. It also gets the selected vertices and passes all that information to the modifier. The next step is to write the operator to transform vertices and then translations should work. Then I will start to think about the other two transformations.

I continued with the changes to the build system for the Unix version. Today I tried to switch to GCC version 4.2.2. I am trying to get the command line versions of the raytracer to compile. I still have a problem linking it, but at least I have a clue what might be wrong. The problem is, that the implementations of some functions instantiated from a template seem to have not been added to a object file (the linker is missing them).

That work is one of the things I want to have working when I get my new box, as I have reason to believe that the 4.2 and 4.3 series of GCC create better code for the quad cores. The really hard part will be to get the raytracer properly parallelized to really benefit from the new CPU I am intending to buy.

The preview is now much better. It still has one weakness, there is no line when a face would be split, but the rest is all implemented. I even added new abilities to my program to have more powerful preview capabilities. The preview is completely independent from a concrete object and is only bound to an editor. So an editor can very easily show some simple graphics to visualize changes.

One of the additions was that I can now show an arbitrary number of vertices as preview. I only could show vertices when using a line of length zero. It was mostly sufficient, but I think, that especially the previews should play a more important role in the future. With that new capability I intend to show which of the snap points are close when starting to implement moving around vertices. That should make it much easier to hit the right point. The costs should be fairly low, I will have to add some additional code in the snapping function to not only return a list of points a vertex should snap to, but also a list of all the potential snap points which are close by. I have to calculate the distance in any case, so I can also collect the ones close by.

Today I didn't work as much on the program as on other days. One of the reasons was, that I finally sorted out some issues I had with Corel Draw to create an image I want to use with a new mouse pad (Nova Magic Classic). It is a nice pad which is open at the side so you can slide an image in. I intend to use a new image each month, it will use the same image I put on a photo-calendar I create each year and overlay it with small calendar sheets at the side with the past, current and next month.

The other thing I did was to clean up the build scripts a bit. Up to this day the Unix version built static libraries for the modules and linked them to one big image. It always was a bit tiring to test the program, as I had to build the library where the code change was in, then delete the executable and build it again. I just never found time to finally change the Makefiles to build shared libraries in Unix. Today I fixed that problem.

And as I was at it I also moved the optimization flags to a common include file. That is in preparation to a new system. The system I thought had a damaged disk seems to have a broken graphics card. As it is now a very old box (Sempron 3000+, only a 32 bit system), I will substitute it with a new machine. I intended to swap it for quite some time, but first I wanted to make the raytracer faster and multithreaded. But it seems, that as long as I don't have a machine where it is beneficial I won't do it. So I will soon get a quad core, I am only waiting for the AMD Shanghai to be released.