Development Journal of a Raytracer

I have been looking for a hard to find bug. When I tried to use a circular constraint and a plane as snap object I never got a snap. So I started to look into the function, into the nonlinear solver and never quite found the bug. I found one deep in the line search, a small oversight, sometimes the result of the quadratic fit returns a NaN and I had written a check in the wrong way. I had written if (a < 1e-40) instead of if (1e-40 > a). Mathematically they are identical, but the first condition evaluates to false, if a is a NaN, the second to true, which is what I need.

But that wasn't the problem. So I followed another train of thought. The two parts of the equation had one difference I am still not sure matters. The plane function minimizes the square of the distance between the point and the plane, the circle function instead minimizes the distance to the power of 4. I am not sure if that doesn't bias the results and leads to poor convergence. It was easier to write the function that way, but I have now done the function to also use the square of the distance. When implementing it I found out, that the problem was something completely different, I had forgotten a parenthesis in the implementation. So a simple programming bug. But now it works.

But at least I had a good idea while working on this stuff. I think it makes sense, that I mark the snap point, even if it isn't hit yet. It is easy to implement and should help to use the program.

Today I created the objective function and the gradient for the last of the objects, the circle. I think I had a good idea, I wanted to create a compound function which uses the distance to the plane and the distance to a cylinder so that the minimum lies on a circle. But the cylinder would have a rather complex function and I had the idea, that it is not necessary to use it, I can also use a circle as second element. That function is much easier to calculate.

The functions are now in the program, but I didn't have time to test it yet. I also had another good idea, I think I know how to make sure, that the bounds of line constraints are not ignored. I will constrain the point resulting from the minimization and see, if it moves. If it does, then the solution is not acceptable and I should use the original, constrained point. I think, that should fix the last issues.

I added support for the schemas today and the sign up page finally works. I also fixed some of the problems I had with logging errors and finally found the position where I lost the diagnostic message. I still haven't made the change to treat a missing connection to the database as error. That is the next thing I will do and probably work a bit more on logging code.

Then I need to continue with the layout component which prints the user name (and the logout-button) or the login-button. Now that I can log in (by creating a new account) I need to be able to print the user name. I haven't added that yet, but I am glad, as I originally intended to use the database to turn the user id into a name. That wouldn't have worked at all and it would be a stupid idea in any case as the same query would have to be made a lot of times. But I will have to think about a way to make it possible, that layout components make database queries. The problem is, that processing of the request has to be suspended and I don't yet have a good idea. I would prefer a solution which handles this problem without too many code needed in the pages using the components.

I completely removed the snap offset for the constraints. It is wrong in that case and now the code is working as expected. There is still a slight problem, but that I will solve when I have more grasp on nonlinear optimization. I can define, that a line constraint is bounded and that I can not yet express in the equations. I know, that there are ways to do that, but currently I don't think it would be a good idea to start work on that part. When reading the book about optimization the chapters on how to integrate inequalities and hard boundaries were the ones where I had the feeling I didn't really understand what is happening. As I found out, I didn't even understand the parts I found comprehensible, so I assume, that adding support for it would need considerable time.

There was a very simple reason why the sign up page didn't work, the database connection was never established, so waiting for the completion of requests was pretty hopeless. But I think I will make a change to the database object, I it is pretty rare, that you want to queue up requests when there is no database connection, much more likely you would prefer an error.

I also have to add some logging code to the database layer. It would have helped to see, what had happened.

And finally I need to add two new settings to the password abstraction, the names of the schemas. I need the schemas (one contains the data the server can access freely and then other sensitive data only accessible via stored procedures) and I don't really want to use the schema search path.

When I tried to test the code to constrain a point to a line and snap to a plane I found out, that snapping to a line doesn't seem to work. I have the impression, that I broke something with constraining in general. Somewhere the additional offset (the amount the point was moved due to the constraint) is added back to the point. That offset is necessary to guarantee smooth movements and is especially necessary for snapping. Without it you can't move a point away from a snap. The additional offset accumulates the small movements and once they are big enough so the point is outside the snap range it gets free from the snap.

To implement the two missing functions and their gradient proved to be harder than I had thought. I had some problems to find the function for the line (mostly due to taking it not seriously enough). I think I have done it now and only have to test it. The distance of a point from a line is also the basis for the function calculating the distance of a point from a cylinder. The square of distance from the axis minus the radius should be the last function I need.

Now there are only the implementations of the functions creating the functors for the minimization of the line and circle constraint missing and it should all be finished. At least until I start using it, as I assume I will find bugs in the code. So I guess I will have to do some more derivation and I still have to find an equation for the circles, I haven't really thought about how to do it. I think I will have to split it in two parts, minimizing the distance of the points from a line (the axis of a cylinder) and the distance from the circles plane. I think summing those two functions should work.

I think I have done most of the changes I wrote about yesterday. I can now snap to multiple objects and have added the new code to the function getting multiple points. I haven't tested that last one yet, though. I have also extended the interface to make movement parallel to a constraint possible, but have not changed the code calling the function yet. When that is done I only need to write the functions to create the objective function and the gradient for the line and the circle and it should all work.

I have implemented a very first version where only the planes work. But the result looks very promising. Currently the code only checks one snap object, so I have to add to run through all of them and select the one result which moves the object the shortest distance. Then I have to implement the functions to get the function to optimize and its gradient for the other two constraints. And finally I have to make a rather big change, currently the object always snaps to the constraint, but I have a mode where objects move parallel to the constraint. That means I need to modify the objective functions a bit.

And finally I have to add all this to the case where multiple points move independently. Then it should work and I can test if it works well in practice on the bridge model.

I fixed some small problems I found while playing some more with the code. Then I started to add the functions to build the equations I need to find the intersections. Next is to write the first of these functions and I guess I will start with the intersection of two planes. Then I only need to implement one set of functions, it is easy to define them to have intersections and I can probably see, what is happening should anything go wrong.

The snap objects are working, in some kind. Currently only when no constraint is active and I check each snap object and use the closest snap point. That is not correct, I would have to also check snap point at the intersection of two snap objects. That one should probably be preferred, if it is close enough. Also I still have a problem, the snap point doesn seem to be stable, if the point snapped to the object and I move the mouse a bit, the point moves a little bit away from the snapped point. I don't know yet what causes this behavior.

But I guess the next step is to actually start to implement the solution of the equations so I can handle active constraints and active snaps at the same time.

Today I started to add the snap objects. As I use the same objects, I could just take the code from the constraints, change it slightly and now have the snap objects in the program. Next the property pages will get a second button, so I can either create a constraint or a snap object. And then I need to add them to the snap function. I will do that in two steps. The first one is easy, when no active constraint exists, then I only need to snap to the object.

The problem enters the picture, when a constraint is active. Then the point may not leave the constraint and I have to find an intersection between the constraint and the snap, then check, if the snap is within range and only then use it. The big problem will be the intersection. I don't want to add code for every kind of intersection between constraint and snap object. That would make it hard to add new objects (I have three now, if I added a fourth, e.g. a sphere I would have to implement four new intersection functions, with a fifth constraint I would have five new ones). I plan to instead minimize a equation. The point has to be on both objects, so I only need functions which minimize the distance of a point to the objects. If I sum them I get exactly what I need.

Today I did the rest of the implementation. It works mostly as intended, there are some strange effects from the constraints I might have to look into in the future. I think I already know, where the bug is, though.

So next are the snap objects.

I had to do a bit of clean up before I can continue. I found out (more by accident), that I had two classes which were exactly identical. Well, it were actually three pairs of classes, they are gone now and the code only uses one variant now.

I think I have most of the support code to move multiple vertices with different transformations, but the code isn't used yet and there is some missing code for storing and loading a small new operator. Next is connecting the code and trying it. I hope it works well, then I will have to implement a function to snap multiple vertices. I have until now only implemented the one which snaps one point. I learned in the past, that it is often better to leave functions unimplemented if you can't test them.