Development

I continued work on the LSCM implementation. There were still more bugs I found and fixed today. Some were really stupid, e.g. I had a stupid bug in the function calculating the length of the vector which led to the residuum becoming 0 on the first iteration, terminating the iteration. I fixed that problem. I also checked the over relaxation and the code seems to be correct. The simple relaxation showed the same diverging behavior, but for now I will stay with relaxation.

The next thing I found was, that the a priori values were not right. I changed the points I use to pin so the second point actually has an u- and a v-offset from the first point. The paper uses a more complex criterion, I hope mine also works, as their precondition is much harder to calculate. More bug hunting tomorrow, I guess.

It slowly seems to get better. I found and fixed some bugs and I think I finally understand what the "consistently oriented" means. The coordinate systems indeed have to be as similar as possible, because if one triangle uses the u-coordinates for an edge and another one the v-coordinates for the same edge I think it will lead to difficulties to solve the equations.

I still have to look at more cases, the most simple one now works correctly, but a field of 5x5 vertices forming 16 quadrangles still creates funny results.

Another long day working on the texture mapping. The code to handle pivots was much harder than I had anticipated. Also the over relaxation didn't work (I think I have made some stupid error), I switched it off for now and only use relaxation. The first simple example (a quadrangle) ran through without a problem. But the result was not what I had expected. I tried a bit more complex object, an array of 4 times 4 quadrangles and got an error from that.

Today I implemented the rest of the algorithm up to the point where the matrix has to be solved. I had to fix some smaller bugs (e.g. I accidentally stored the imaginary components also into the matrix representing the real values) and created a function to turn two sparse matrices representing a complex matrix (one holding the real and the other the imaginary parts) into one real valued matrix.

As the algorithm also separates the matrix it generates into two parts (one of them is a bunch of preconditions so the solver doesn't only return the trivial solution, the paper calls them a priori values) I also implemented that. I had quite some troubles to finally get this thing to work (and do so efficiently), but it now seems to work correctly. So I could finally fire up the solver and it didn't even start, but stopped in the check for the precondition that the diagonal elements all have to be different from 0.

Now I at least know for sure, that I either have to change the algorithm to use some kind of pivot structure or that the matrix has to be resorted (the rows have to be swapped to bring nonzero elements to the diagonal). The last bit of information I needed was generated by the example I choose. By some strange luck the first (and most simple) example already showed, that I won't get around that problem. The example generated a 0 as the very first component and that means that even with careful scheduling of the way I am building the matrix I can always just luck out and run into a condition which creates a 0 on the diagonal. I fear that there is no good way to implement all the necessary checking into the building process.

Today I worked on creating the matrix. I didn't completely finish with it, but I now have the components of the complex matrix called M in the paper I referenced previously. The next step is to choose two points and fix them in the plane (I don't want to implement the suggested solution, it seems quite expensive). Then I can create the real data I need to solve the system.

I also found out, that my solver won't work before even using it. The SOR solver I implemented has an important precondition, the diagonal elements may not be 0 and I have already seen, that I can't guarantee that. So I will have to either change the sequence of the rows (which would be expensive) or at least have an additional data structure which guides the algorithm to behave as if the rows were reordered. So even when the equation is created, I will have more work to do until I can even test it.

I spent quite some time today to find out, why the selections didn't work as expected. I found out, that they basically do. There is only one kind of selection which doesn't work and that is selecting everything. I will fix that tomorrow as it would be quite useful for the kind of thing I tried to do. I also tried something else yesterday and it didn't work, but today it did, I will see if I can reproduce what happened.

I also finally started with the work to create the equations. For the beginning I will ignore the selections completely, I will always map the complete surface and I will require it to be topologically equivalent to a discus so I can handle it. The first surface I will use is a simple quad.

The very first step is turning the surface into triangles. The paper I linked yesterday needs 2D coordinates which are created from the triangle by choosing a suitable orthonormal basis. All rather standard stuff, but the first problem I have is, that neighboring triangles have to get a local base which is "consistently oriented". I don't know what "consistently" is supposed to mean in this context.

I continued with the automatic texture mapping modifier. There are still problems with the handling of the two selections I need. The first selection is the faces that are supposed to be handled. The second consists only of edges which define a cut to make the surface topologically equivalent to a discus. Most objects need to be cut at some places so they have the correct topology.

The other thing I did was to read the paper about Least Squares Conformal Maps (LSCM) and I think I will try to implement that. There are still some things I am not clear about, but I think actually trying to implement it is a good way to understand it.

I guess todays Sunday qualifies as weird, I worked on some classes to store sparse matrices and implemented a rather simple solver, a successive over relaxation solver. I know that it is (by far) not the best solver you can use, but currently I am more interested in having a solver than having an efficient one.

In case you don't know, what a solver does, it calculates a solution to the equation Ax-b=0, A is a NxN matrix and x and b are N dimensional vectors. The solution is not exact but normally only an approximation. The solver I implemented is an incremental solver, it calculates a new value of x based on the values of the last iteration, the over relaxation means, that when we calculate a new value for a x_i we assume that the true value is a bit more in the direction we have to move from the last x_i to the next. When the factor for that additional step is chosen well the iteration will converge faster.

The algorithm is rather easy to implement and should be fast enough for my first tries. It might even be fast enough for quite a while, I will see.

The second thing I did was start on the first user of the solver. It is an algorithm which is supposed to calculate a texture mapping. I haven't written any algorithmic parts yet, only the framework around it. I will use either Least Squares Conformal Maps (LSCM) or Angle Base Flattening (ABF). Although there are algorithms to choose cuts in the model when the model needs to be cut up to not have overlapping parts, I think I will not use them. I didn't see any algorithm I particularly liked and think compared to the time needed to create a good mapping by hand, the selection of some edges to cut up the mesh is trivial. And I think that is an area where human intuition is much better than algorithms, at least currently.

Today I finally found out what was wrong with my server. It seems a strike of lightning which hit nearby some weeks ago damaged the RAM. As soon as I started memtest86 it nearly immediately found an error and then the machine froze. I bought two new 1GB modules and inserted them and now I hope it works better. The first problem is, that my OS didn't recognize the 2GB, it only found 1GB. I will fix that tomorrow. Memtest86 ran for an hour without any problem with the new memory.

As I didn't have a lot of energy left after this week and the troubles with hardware again, I only modeled a bit and started to implement the context menu in the KDE-UI. It is already appearing, but it doesn't seem to execute the callbacks. I will debug tomorrow to find out, what is wrong.

The idea I had yesterday worked. It basically added another value I could check to detect a change in topology. So finally this thing is working again. At least it seems to, I was not able to get the program to present a wrong rendering. But I also haven't checked, if the optimization is still working at all, but I am sure I will notice that soon enough.

And today I even have a very good excuse for having done so little. I normally don't like to post links to things not related to my program, but this time I make an exception. Though many people probably already know, The Times has today opened their archive. I think it is very interesting to read about historic events from a newspaper which was printed when it happened, it is a quite different viewpoint. If only the confirmation mail would get through, so I could read the paper which aren't linked from the start page.

I am still trying to fix the optimization I wrote about yesterday. I was correct in the analysis, the problem stems from a change in topology while editing. When that happens I have to rebuild the index arrays. I now added all the checks I could do so in most cases the geometry is rendered correctly. Now there is only one case left (I think, I can't be sure yet).

The problem is, when a non convex face with many vertices is changed. Non convex faces are generally converted into triangles for rendering by a function implementing Delauney triangulation. That means, that the generated topology is dependent on the placement of the vertices, changing one can completely change all of the triangles. I currently have not enough data stored to detect when that happened and so can't invalidate the data for it to be reconstructed. I think I might have a solution, when I store one additional value per vertex. I will try that tomorrow and then will see, if I can still get the program into the defective state. I know, testing is no proof for a correct solution, but I think (or hope) any remaining cases would be rather obscure.

If I really run out of ideas how to handle this thing (it is an optimization, when it gets slower to check the validity than to render it the hard way, it obviously looses it effect), I have still one option left. I could count how often the geometry was changed and regularly recreate the geometry. Not a nice solution, but it should at least lead to a solution I should be able to work with. I would prefer not going down that road though as it isn't fixing the problem but trying to cover it with a poor heuristic.

After looking at the code and much debugging I think I know where the problem is I described yesterday. The optimization is, that the modifiers can specify that they will only modify a limited part of the geometry. The program then only updates some data that is used by that geometry in the OpenGL representation when the geometry changes.

But the way I have implemented it, there is a problem. I think I even remember that I knew about it and didn't think it would be a problem. The representation changes, when a face has to be rendered as multiple parts or vice versa. E.g. if I drag a vertex far enough out so that the face stops being planar then a quadrangle is rendered as two triangles. But that changes the topology of the data to be rendered and I don't adjust the index lists I use for rendering. So all I have to do is to additionally store the state of the face (convex/not convex and planar/non planar) and if it changes for any one face recreate some structure.

That should still be fast enough as in most cases the rebuild is not necessary. But the current behavior is unacceptable to work with, it is by far to confusing. I couldn't tell the wrong optimization from a bug in the program or a wrong modeling step.

Today I didn't really get anything done. I have started some days ago to model a skirt for the character. As I read a bit about how to automatically map a surface to texture coordinates, I want to try it. If I wouldn't have to to do it by hand it would make modeling much faster. And the process seems simple enough to try. But first I wanted something simple to map and a skirt sounds rather simple. Only if it worked I would continue with the face of the character which is still not mapped.

But I ran into some problems when modeling the skirt. The extrusion sub command to move vertices between extrusion steps didn't seem to work correctly. Sometimes the vertices just snapped to other vertices and sometimes it created complete chaos. So I first deactivated snapping for extrusions (an option not available when I last worked on the extrusions, now it only meant defining a function returning false). Then I found out, that I didn't store a bit of state and so the movement thing didn't work right after loading a scene, I also fixed that.

But it still didn't work correctly. I finally had the idea, that it might not be the extrusion modifier but something else. I have rewritten the OpenGL part which renders polyhedra and since done little modeling. I especially had one optimization I was suspicious about and as it is quite easy to deactivate I did so. And that fixed the problems completely. So I now at least know where to look for the bug. I haven't done that, yet.

The other thing which is still not working is the depth of field. Yesterday I spent some time to calculate coverage ratios for the nearby pixels which are covered fully or partially by the circle of confusion. I think I somewhere made a small error, as the factors didn't add up to 1. But at least I found out, that the diagonal pixel has negligible influence and then it was easy to find factors which will work.

But I have still some artifacts. And they get harder to find. I hope I can find out tomorrow where the problem lies, I slowly would like to end this project. And as long as that stuff I currently work on isn't solved I can't fix the rest of the issues, as they are rather meaningless when the thing produces very visible artifacts.

In march I had started to add a little feature to the program, to render only the lines of the models. I hadn't implemented any hidden line removal so the feature was of very dubious use and I actually never used it. As I still think rendering the faces as lines might help in finding bugs, I today finally implemented the missing parts.

It isn't hard at all, you basically render the faces filled first, but switch off the color buffer with glColorMask and only render to the depth buffer. Then you switch to line rendering with glPolyonMode and have to either set the depth compare function to less equal (= GL_LEQUAL) with glDepthFunc or use the function glPolygonOffset (negative values are right here) or the depth test will result in the lines not being drawn. Don't forget to enable writing to the color buffer before drawing the lines or you get a really boring picture.

A side effect of not being able to tell objects to not use complicated rendering stuff which won't be visible in any case (textures, materials, lighting) is, that the lines being rendered have the colors the faces would have at that place. I think it actually looks quite well, as I can still get a general idea about the colors and it helps to tell them apart.

Again a little feature needed much more work than anticipated. But now it is completed and even the check for a file with similar name and only a different number before the extension is handled. Currently the extension for my scene files is hard coded, but that would be easy to change, should I need to.