Development Journal of a Raytracer

Today I looked for a problem with the Geometry Mapping I intended to use for the tea spoon. It was a stupid bug (I had forgotten to invalidate some cached splines), but it still took a lot of time to find it. It is fixed now, but I still can't use it, I tried and the limitations of the object are too big to bend the front of tea spoon. The object works in rows and columns of control points, so I don't even have the limits of a fixed raster, but it is still not flexible enough, the problem is, that I won't get the top of the tea spoons head into one plane. So I will try something else and hope to finally finish that object tomorrow.

Today I added two new features to the Sweep Constructor. The first was to make it possible to close the path. I had some troubles because I technically can't guarantee for it to work. Due to the rotation minimizing frames I can't really close the path correctly. The profile could be rotated in nearly arbitrary ways at the one but last point. But the case I needed it for was a simple window and there the profile does not rotate. I expect that general form (extrusion of a profile along a rectangular path) to be a rather important case and so implemented the closed paths as if I was sure it would fit.

The second feature was also needed for the window. As I don't use splines for the path (yet), I need to calculate artificial tangents for the RMF. I use the half vector between two line segments for that. The frame of reference I get then is used to project the profile points to 3D and those points are then connected with the previous profile. The problem with the projections is, that the cross section of the profile stays the same. For organic objects like a snake that is absolutely correct. But for rectangular paths it has the effect of shrinking the profile in one dimension but not the other. It is very hard that way to define a usable profile. So the second feature was to project the profile so that the cross section is correct at the line between path points.

I tried to finally implement braking today and failed. Somehow the effect is very, very small and I don't see, what is wrong. I tried to compute the power the brakes remove from the maximum friction the car can have on the ground. But compared to the motor power the power I calculated for braking is tiny.

Today I changed a quite old piece of code, the 2D Geometry Mapping. That is an object which can be used to define a mapping from a plane into a height field, but interactively by moving the supports. I use it to deform objects, for example I tried to use it to form the front of a spoon from a flat surface. But it didn't really work, the thing was originally written for big objects and had some issues with small items. So I fixed those little problems and hope I can create a tea spoon tomorrow using it.

I found and fixed the problems, there were more than the one I had already localized yesterday. It turned out to be rather hard to remove the duplicated hit points on an edge. So instead I tried to filter them out, but couldn't find a good way. The points where very close, but not identical. Then I remembered I had forgotten to bring the hit points back into my fixed raster I had started with. That immediately solved the problem, I could easily find the duplicates.

But that didn't work either. The next problem was much simpler, when an edge of the first geometry hits one of the second geometry, I sometimes get a hit which really belongs to the neighboring face. They are easy to find, I can't find a second point in that case and so could easily drop the edge loops when they were too short.

The next problem appeared, my simple test case resulted in edge loops which always only contained one single vertex in the middle of the face and two vertices one the edges of the face. But with a cylinder that changes and I found out, that nearly all inner points were resulting in two hits (which is logical, every edge belongs to two faces). So I also had to find and sort out those duplicates.

But then it worked. Mostly, I found some more problems. The first is really bad, the code to create convex faces doesn't work properly, so the geometry was right, the rendering was wrong. So nothing with the new code. The second problem seems worse. I tried to cut a square hole out of a sphere and the code crashed with a stack overflow. It seems to be a problem in the Change Geometry (it ran into an endless loop).

But overall I am happy with the thing. It is still not finished, but I think I will first change some other small stuff I have found while modeling in the last few days. And then finish the rest of the problems, I might even find time to test it a bit before I get back to change it.

Though I might make a small change to the thing tomorrow. Currently I have defined the three operations "Union", "Intersection" and "Difference", I will probably add the "Symmetric Difference" (although I have no idea if it will ever be useful) and one which does not really do any CSG operation, but just splits the object. I think that operation could be useful, e.g. as a basis for extrusions.

Now I have also implemented the last part of the algorithm. It works quite nicely with two boxes, but on more complex objects it fails currently. I tried to swap one of the boxes with a cylinder and the program no longer was able to calculate the edge loops. When I looked at the data I saw, that the same point was appearing twice. One of the cases when that happens I have already eliminated, but there seems to be another one.  I have to check, if the first code which should sort out those points doesn't work correctly, a condition could be wrong for example. If that is not the case (what is what I expect), then I will have to sort those vertices out in the function looking for edge loops.

But at least it is working now. Even if only with one specific model, I hope to soon get it into to work with arbitrary geometry. Then I have two more problems to solve I have ignored for now. The easier one is handling of the materials. Currently I drop the materials of the second object, I think it would be better to clone the materials and assign the faces the right material identifier. The second problem is something for which I am considering different options, but haven't found one I like yet. My program does not handle holes in faces. I opted against that from the beginning and still believe to have been right. But it means, that I have to subdivide faces when an edge loop never touches any edge and have no good idea how to integrate it into the algorithm.

Again a day I was a bit lazy, but at least the uv-mapping is fixed and the classification of the faces which were split is also in the program. That was fairly easy, I looked for the vertices of the faces which were the result of splitting of an edge. There I have the face normal from the second geometry (which is always facing outward). I then take the vertices immediately preceding and following it and look which one is in the general direction of that face normal, the other direction should result from the intersection with the face and therefor be orthogonal to the face normal. Then I can decide if the face is inside or outside of the second objects geometry.

To handle degenerate cases which will surely appear, I check all those edges and test, if they result in a consistent result. If they don't the face is not marked as either inside or outside.

Next is a simple algorithm to look at the neighboring faces to also classify them and then to actually create the new geometry. That last step should be fairly easy, but it will be important to identify the common vertices so that the finished object is closed again. This is also fairly easy, I already have that information, I only have to reformat it. When I find an intersection point with a face of the other geometry I always add the point to the second geometry and split the edge at the same place. Both index values for the vertices are then stored together as I need them later to create the edges and split the faces.

Today I wasn't working on the program very much. I was watching the first part of Dr. Mabuse, der Spieler and it is a tad bit long, but interesting. I was again trying to model the tea spoon and ran yet again into a problem with the Draw on Plane-modifier. I haven't found the cause of the problem yet, I can only see why it does no longer work, but not what I could change so the program would no longer run into that problem. Tomorrow I will try to get on with the CSG stuff and I have started planning what to do next.

Some days ago I had tried to render an older scene I used for profiling quite some time ago. It was one of the terrain scenes and it completely crashed the parallelized version. I found out, that the reason was some delayed initialization function, multiple threads changed the same global state at the same time. So I introduced a monitor so only one of the threads would initialize the structure. But that didn't help. I found out, that an old condition which should only start a new initialization of the structure was wrong and so that initialization was executed thousands of times. Fixing it also gave the single threaded version of the raytracer a speed up.

But there are still problems. At least the atmosphere is not rendered correctly, neither in single threaded nor in the parallelized raytracer. In the single threaded version it is too dark and missing all structure, in the parallelized version it is also too dark but full of color noise. I will try to first fix the single threaded version and then see, why the parallelized one is so different.

Today I managed to implement the rest of the geometry functionality. The faces are now properly split into the right parts. I still have one open issue, the uv-coordinates of the new edges have not been set. Currently I just set them to a fixed value of (0,0). But it is quite easy to do, I will have to change one interface and just supply the uv-coordinates, as I use parts of the raytracer they are already calculated, I just throw them away. I didn't do it today, because I need to go to the same position to start with the topology stuff.

The first thing for that is to store the normals of the faces being hit by an edge. That information I will use to classify faces as inside and outside. When I have all the faces classified which were split, I can then use the information about neighboring faces to also classify them. After having done that for both geometries I can create the new object. E.g. a union will take the outsides of both objects, throwing away the insides. Intersection only uses the insides of both objects, but additionally has to flip the faces. The difference between the operations is very small and so I will create a function which just needs some flags to govern what is created.

I didn't finished the third step today. I was a bit tired and didn't get as far as I wanted. But it is still making quite some progress, the edge loops are now formed out of the points and I have also added them to the models to see, if they are correct. Doing so I found a problem where intersection points were found twice, I had to add a little bit of code to sort them out. I think, the raytracing function correctly returns them, when a ray hits an edge it can generate two hits, one for each face on either side of the edge. So I didn't check, if the raytracing function is wrong (I am quite certain it isn't) and instead added the filter function.

The next issue is to actually partition the faces. The first partitioning is easy, the next ones then have to find out, which of the faces to use. I still have to implement a new function in the ChangeGeometry-class to partition faces alongside an edge loop. Currently I can only partition faces along an edge. I looked into that function and I think it will be rather easy to extend it to also handle multiple edge segments. I can then change the current function to use that extended version. So I hope to get the geometry side of the modifier finished tomorrow, then I will start with the topology part.

I fixed the problem with the speedometer today. It was quite easy, once you find out, where the function you need is hiding. To be able to change the text of a Text2D object you need to give the appearance of it the capability to write the texture. So if text is the Text2D-object, you need to call text.getAppearance().setCapability(Appearance.ALLOW_TEXTURE_WRITE) and you can change the text.

I find it a bit strange, that is not in the explanation of the Text2D-class. But honestly why does it not just have a method to set this capability, I would expect that Text2D-objects are quite frequently used to display changing text.

In any case I was able to display the speed. And that showed me, that the car was speeding up when going uphill and getting slower when going downhill. I fixed a sign and now it matches reality. I have also changed the camera position a bit and can now say, that the car is not flying above the track, it was just a poor choice of camera position. So slowly I sort out my problems.

I managed to implement step two and even started on the third one. I needed to write a new function to do the "raytracing step", the existing function only returned the nearest hit point. I need all of them and so I implemented a function so I can use it for other stuff, should I need it.

I checked the result and it looks good. So the next step is to form edges out of the hit points. That is not so easy. I have two sets of hit points, those of the edges of the first geometry with the faces of the second and the one where the edges of the second geometry intersected the faces of the first geometry. I have to mix them together to get the full set of new vertices. I write the following from the view of the first geometry so I don't have to repeat every sentence.

The second set of vertices is easy to integrate, they are just some vertices in the middle of faces, normally far away from any edge. So I can just add them. The first set is different, they are on the edges, so I can't just add the vertices, I have to split the edges. To do that, I have to know all the hit points on an edge (there can and will frequently be multiple points). I just noticed while writing this, that I made an error, I thought it would make sense to handle those together with splitting the faces. But that is wrong, I already get the full list of new vertices on all the affected edges, it actually is the return value of the raytracing function. So tomorrow I will rewrite the code to do the splitting earlier. That will also fix another problem I ran into, which I can't explain without posting the code.

When I finally have all the vertices in the model, I can try to find and create the edges. It is quite easy, as I always know which intersection created which hit point, especially I know the faces which where hit or were containing the edge. As the faces have been made convex and planar in the first step, I know that every face can have at most two hit points in a face. So the edges should not be hard to find.

When I finally have all the edge loops which split faces, I can do the last step, splitting the faces. With that work on the geometry will be finished. The rest is topology, I need to decide, if a face is inside or outside the other geometry. And then I can finish the operation. I hope I can get the face splitting finished tomorrow.

Unbelievable, but I managed to do exactly what I had planned yesterday, the first step of the CSG-implementation is indeed finished. I have ignored one special case, if two vertices are very close together and get mapped to the same vertex when brought into the raster. I fear I will have to handle that case sometime in the future and it shouldn't be too complicated, but I don't want to do that now.

The next step is also not too complex. I need to find intersections between the two geometries. I have chosen to look for the intersection of the edges of one of the geometries with the faces of the other geometry. I will have to calculate the intersections for each of the two geometries and then have to find the edges from them. The alternative would be to intersect face with face directly. Using the edges has one big advantage, though, I can use parts of the raytracer code to find the intersections. Finding the intersection of a line (or ray) with a heap of geometry is the core of a raytracer, after all. So I hope that by doing it this way I gain an advantage with complex and big objects, but I have to do a bit more processing afterwards. I will see, if it is a good idea, I guess.

Today I (finally) started implementing Constructive Solid Geometry (CSG). As often I first need to spend time to integrate the stuff into the system before even starting to do any real work. I have no clue how long it will take to implement, the theory is simple enough, but I fear that there will be a lot of stupid special cases. Tomorrow I should be able to implement the first part of the algorithm. It is rather simple, I will simplify the meshes by putting the two meshes in one coordinate system, moving all the vertices onto a grid and substituting concave or nonplanar faces with their substitutes, so that all faces are convex and planar. I hope, that by moving all vertices and also all of the intermediate results into a grid I will reduce or even eliminate problems with precision. One of the problems of calculating intersections between two faces (e.g. triangles or quadrangles) is to handle rounding errors which result in faces with dimensions very close to 0. By moving all vertices to a grid I should either have the same points and therefore see, that two edges coincide or a real split of a face where all the edges have a fixed minimum length I know I can handle.