Development Journal of a Raytracer

This month is the first one where I won't manage to do my two items. I had too many problems with my program to make it. I post at least the image of the fork. There is still a problem with the distances between the teeth, I will see if I can fix that problem.

Today I continued to look for the problem of why I could not change the material from Ward BRDF back to Phong. I found some problems and it now seems to work. I didn't even manage to create the image for which I have fixed this stuff. I would really like to post one more image to at least get my two images for the month out.

Somehow today nothing worked at all. First I tried to model a bit and thought I had found another bug. When I looked into the source I saw the program behaved as programmed, just that it is not very well thought out. Then I tried to fix it and did it wrong so ended up to not use it.

Then I tried to finally render an image of one of the models and I again fail. I tried the Ward BRDF again, but a metallic object comes out very dark (nothing to reflect). So I tried to switch back to Phong and the program failed. I had that problem before but I thought I could at least switch back, but not even that works. So somehow I did nothing today, but at least I spent a lot of time doing nothing.

Today I again did a lot of modeling, I have to create some renderings to show soon. But I also added yet another modifier to the program. This time something I wanted to add to the extrusions, but failed to do. The modifier is used to move boundary edges of a selection. The idea is to select some faces and have all the edges which define the boundary of the selection being moved perpendicular in the plane of the face they belong to. That way I can do something like a bevel by hand. So when extruding some faces, then moving the edges as described above, then extrude again and move the edges again I can define a profile.

It is pretty primitive, but I hope for it to be useful. I wanted to add that as a step to the extrusion modifier, but the way that one is written makes it very hard to implement. I would have to also move the extrusions to the Change Geometry, something I should probably do, but don't want to do now.

What is a bit funny is, that the modifier didn't work correctly on the box I tested it with. I wondered why it failed and finally found out, that the box constructor has a bug. I can define how many segments the edges of a box have along each major axis. The way I calculate those points is not stable, though. So sometimes it results in slightly different points and as I create the faces directly via 3d points it does not in all cases close the object. The correct solution is to first create the vertices and create the faces by referencing the vertices. That is also how I do it in most modifiers, but the Box Constructor is so old, that I had not completely understood the problems and so works differently.

I have mostly been modeling today. I will try to soon post some images, probably tomorrow. While doing so I again missed a modifier, one to mirror the geometry. As it is very simple, I just implemented it.

I have now also tested the release build and it also shows an utilization of around 60% in the task manager. The behavior is a bit different, though. Now four cores are running at 80-90% utilization, the other four are below 40%. Really strange. So I guess next is a different STL-implementation.

I was too curious so I didn't work on the game today. I instead changed the header of the Standard C++ Library which Microsoft is using with VS 2008 to see, if it is possible to switch off locking. It isn't, the lock as such is part of the runtime and so the resulting executable no longer works reliably.

So I see only two paths, try to get by without the Standard C++ Library or use a different implementation. The first is nearly impossible, as I don't want to do it and second it would be even more wasted time. As I only tried in Debug-Builds up to now I could try if a release build would be better, I was shown a reference today (by a colleague which I can't find) which seems to imply that at least VS 2010 switches off the locks in release builds. I don't know if VS 2008 does the same. Though quite honestly I think that is a even worse idea. Locking issues are hard enough to find and fix without the compiler adding locks behind your back when you switch to a debug build.

I have done the change to separate the blocks for the allocator in the polyhedron. It didn't work either and today I looked for the reason why. It is quite simple, actually, Microsoft's STL (Standard C++ Library actually) implementation is simply useless for any multithreaded application. It uses one global lock for a number of STL containers (not even all of them says the documentation). So when I hit "break all" I see one thread working and seven waiting at the STL lock.

I don't need that bullshit, a "thread safe" STL is not even possible, because locking based on individual functions is completely useless. E.g. if you query the size of a vector and then try to access the last element by subtracting one from the result and use operator[] there is nothing guaranteeing you, that another thread hasn't just called reset on the vector which will make the access fail. It only guarantees, that both functions will run uninterupted, until the program crashes from the access, that is. Iterating the vector will have that problem even more any way you try to do it, as long as you don't use a critical section controlling access to the container. So basically the stuff in the STL makes it impossible to write efficient multithreaded applications, as it will impose completely useless blocks killing performance. I guess I will switch to a different STL implementation now.

I have also added the last missing bit, the uv-mapping is now also done. It was quite easy to do, though I left out the faces closing the swept surface if the profile is closed. I don't see a good way to integrate them and I also doubt I would ever want them to be part of the same uv-map. If I really want that then my tools should be good enough to make it possible.

So with that the Sweep Constructor is considered finished.

I didn't have a lot of time today, but I finished the change I had started yesterday to give each polyhedron instance its own allocator. It seems to be a tiny bit better, but the difference is not exactly big and is only a wild guess from the levels I see in task manager. It is not even worth to measure the difference. So next is the version without locks. If it is still slow, I will have to look for the real reason. But in any case I think that the design without locks is the correct one even if it should not be the main reason for the slowdown, that is also why I didn't try to first find out, what makes the program so bad when using multiple threads.

Today I have started to make the big change needed to get the next allocator change into the program. I will have to make quite a lot of changes to get it to work, but I hope it won't take too long and I hope the parts I write will indeed turn out to be useful for whatever technique I will settle for in the end. Currently I use a virtual function in the small objects returned from hit testing to do the deletion. That function will in turn call a function on the object which created them to really delete them.  The small object already know which object have created them, I need that to calculate the effects of the shaders.

To allocate the object I will also need a function which handles the second half. Both functions have to do the locking so multiple threads coexist properly. I still think it will make sense to go to a solution which doesn't need locking in the end, but I first want to implement this simpler version which needs explicit locking. Mostly to get a better feeling for parallelization.

I worked a bit on the Sweep Constructor today. First I fixed an issue I found yesterday when using it, one of the transformations was wrong. That was why the added vertices were not where they belonged. Then I added the function to interpolate the third component when adding a new vertex. So now I have the uv-coordinates left and the Sweep Constructor is finished. At least for now, I intend to add at least the ability to define twist angles and change the scale of the profile along the path. I would also like to add the ability to define more complex scaling for the profile, e.g. to model the sprout of a coffee pot. They often are wider in one direction where they are attached to the pot. I would like to be able to define that in the Sweep Constructor.

I was strangely lazy today, I did hardly any development work, only fixed a crash in the raytracer. I also looked how to proceed with the parallelization. I want to make as small a change as possible until I know what is causing the slowdown and all the possible solutions I find result in big code changes.

But what I did was to try some of the changes I made in the last weeks in real modeling. I found some problems with the sweep modifier, it seems a transformation is missing somewhere. But overall it works quite nicely, but I have also found some little quirks I have no solution yet, mostly switching between the two editors. Then I found a problem somewhere deep in old code again. I have modeled a fork by defining the flat outline with the Draw On Plane modifier. I then bent it with the linear geometry mapping and then extruded it. It doesn't look too bad, but the bending was lacking. But changing it crashed the program (or rather it entered an endless loop). I am still not sure what is causing it, it crashes deep in the Delaunay Triangulation. So I have found some work to be done in the next week.

I have implemented the blocked allocator but the results are hardly any different from the results before. So either I was wrong and it is something completely different or the difference between my allocator (with synchronization) and the new/delete combination is small. It wouldn't even be very surprising, the way I had to implement it all the polyhedrons share one critical section for the allocator and as the whole scene only contains that kind of object it means that every allocation/deallocation passes through that same section. Perhaps I should change that first, it would make it necessary to change the implementation slightly, but that doesn't look like a big issue.

I have thought about the behavior I have observed and am fairly certain I know the reason for the bad performance. When I find a hit I allocate some small object and store all the data I need later to evaluate the shader at that point. I think that the allocation and deallocation is the reason it is so slow, as both operations are inherently serial. All the threads use the same heap, so when one allocates memory another thread wanting to allocate or release memory probably is blocked. I haven't check that in the documentation, but I would be very surprised if allocation/deallocation was done in parallel.

So now I will have to do what I intended some time ago, write a special allocator which mostly removes the new/delete calls by allocating bigger blocks and not releasing the memory. I will first try this solution with explicit locking. But I think there is a much better solution, use one of those allocators per thread. That way I don't have to do any locking, as long as it is guaranteed that only one thread is working on one the those objects, which is something I can guarantee. But first the simpler solution has to work and I hope it already gives the program a noticeable boost in performance. Even if it turns out to not have been the reason for the bad performance it is something I always intended to add.