Fermat's principle

Searching for topics
I've noticed lately that four major topics have found their way through my blog posts. That wasn't something that I did plan, it just happened, like it happens to a person of going through different periods in his music listening habits. Those are:

• C++ is premature optimization
• Shader programming is physical modelling (and artists are fitting algorithms)
  
• Iteration time is the single most important coding metric
• Huge, data-driven frameworks, are bad

We explore things moving our interests more or less randomly, until we find something that requires a spot, a local mininum in the space of things, were we spend some time and then eventually evade, starting another random walk searching for another minima.

And while that it's a good, smart, simple way to search (see metropolis random walks, that lead naturally to simulated annealing, that in turn is a very simple implementation of the tabu search ideas... a nice application of metropolis-hastings montecarlo methods is this one...), it's probably not a good way to write articles, as the result is non uniform, and I've found that the information that I think it's important is scattered among different posts.

As I'm not happy with the way I explained some concepts, I tend to increase the redundancy of the posts, they become longer, some ideas are repeated more times in slightly different perspectives, hoping that the real point I wanted to make eventually is perceived.
That eventually helps myself to have a clearer view of those ideas, I'm not pretending to write this blog as a collection of articles for others to read, I write on the things that I'm interested as writing helps me first and foremost, and then if someone else finds that interesting, it's just an added bonus.

Be water my friend
One of the things that I still don't feel to have clearly espressed is my view of data-driven designs.
Let's look at the last two items of my recurring-topics list: "Iteration time is the single most important coding metric", "Huge, parametric frameworks, are bad". The problem here is that most of the times, huge, parametric frameworks are made exactly to cut iteration times. You have probably seen them. Big code bases, with complex GUI tools that let you create your game AI / Rendering / Animation / Shading / Sounds / whatever by connecting components in a graph or tree, mhm usually involving quite a bit of XML, usually with some finite state machine and/or some badly written, minimal scripting language too (because no matter what, connecting components turns out not to be enough)

How can they be bad, if they are fulfilling my most important coding metric? There is a contraddiction, isn't it?

Yes, and no. The key point lies in observing how those frameworks are made. They usually don't grow up from generalizations made on an existing codebase. They are not providing common services that your code will use. They are driving the way you code instead. They fix a data format, and force your code to be built around it. To fix a data format, you have to make assumptions on what you will need. Assumptions of the future. Those, always, fail, so sooner or later, someone will need to do something that is not easily represented by the model you imposed.
And it's at that point that things go insane. Coders do their work, no matter what, using something close to the Fermat's principle (the basic principle our-rendering-engineers interpretation of light is built on). They try to solve problems following paths of minimal design change (pain minimization as Yegge would call it). And not because they are lazy (or because the deadlines are too tight, or not only anyways), but most of the times because we prefer (questionabily) uniformity to optimal solutions (that's also why a given programming language usually leads to a given programming style...).
So things evolve in the shape that the system imposes them, requirements change, we change solutions to still be fitting in that shape, until our solutions are so different from the initial design that the code looks like a twisted, bloated, slow pile of crap. At that point, a new framework is built, in the best case. In the worst one, more engineers are employed to manage all that crap, usually producing more crap (because they can't do any better, is the design that is rotten, not only the code!).

A common way to inject flexibilty in a rotten overdesigned framework is employing callbacks (i.e. prerendercallback, postrendercallback, preupdate, postendframe etc, etc etc...) to let users add their own code in the inner workings of the system itself. That creates monsters that have subshapes, built on and hanging from a main shape, something that even Spore is not able to manage.

What is the bottom line? That the more a library is general, the more shapeless it has to be. It should provide common services not shape future development. That's why for example when I talk about data-driven and fast iteration, most of the times I also talk about the virtues of reflection and serialization. Those are common services that can be abstracted and that should find a place in our framework, as it's a very safe assumption to say that our solutions will always have parameters to be managed...
Rigid shapes should be given as late as possible to our code.

Simple example
I still see that many rendering engines built on scenegraphs, and worse, using the same graph for rendering and for coordinate frame updates (hierarchical animations). Why? Probably because a lot of books show such ways of building a 3d engine, or because it maps so easily to a (bloated) OOP design that could be easily be an excercise in a C++ textbook.
Hierarchical animations are not so common anyway, they should not be a first-class item in our framework, that is an unreasonable assumption. They should be one of the possible coordinate frame updating subsystems, they should live in the code space that is as near as possible to user rendering code, not rooted in the structure of the system. Heck, who says that we need a single coordinate frame per object anyway? Instacing in such designs is made with custom objects in the graph that hide their instancing coordinates, making everything a big black box, that becomes even worse if you made the assumption that each object has to have a bounding volume. Then instancing objects will have a single volume encompassing all the instances, but that's suboptimal for the culler so you have to customize it to handle that case, or write a second culler in the instaced object, or split the instances in groups... And you can easily start to see how easily things are starting to go wrong...

Quality rule

The quality of any given program (or subsystem) obeys to the following rule (due to Dijkstra):

Where Qp is the quality, Sk the skill of the coders, and |p| the size of the system.

The bottom line is: big programs suck. Beauty lies in minimal complexity.

Interestingly the size here is not measured up to an additive constant as in Kolmogorov's complexity, but it's the actual line of code count, so finding the right abstractions, or using the right languages, can help building more expressive systems keeping the same quality.

So this is also the golden rule for discarding generalizations: if an abstraction does not simpfy you code (your current code, in your current project), discard it.

Corollary: generalizations should be made a-posteriori (via refactoring) and never a-priori (via some kind of optimistic design that tries to guess what's going to be useful in the future).

Below a given quality, the system will just fail. So no matter what, there is a size limit for our projects that can't be crossed by human beings. It's intresting to note how this is a quite general rule, before computers, people were computers, and other people (mathematicians) programmed them by trying to analitically optimize as far as was possible. With integrated circuits we moved all our work-force in the "outer" shell, the programming one. Data-driven designs, generic programming, code generation, domain specific languages are all attemps to make a jump towards another meta-level.

P.S. Of course, this is something I've completely made up, I wanted to see how I could embed math in my posts...

Normalize(Normal)

Rendering is going through a very illiterate era. Innumerical, really.

We had the software rendering era, triangle filling was hard, ninja-coders knew how to count instruction cycles and wrote routines in assembly. Stupid errors were made due to lack of mathematical knowledge, but they were not so important (even if I do think that knowing maths also helps optimization...)

Graphics was full of cheap hacks anyway. There's nothing too wrong in cheap hacks, as long as they look good, and if you can't do any better. We will always use hacks, because there will always be things that we can't do any better.
Light is simply too complex to get it completelly right. And we don't know too much about it too.

Still, you should know that you're doing a cheap hack. The main point is in knowing your limitations. The only thing that you know about a graphic hack is that you can't know its limits. Because you didn't start with any reasonable model, and so you can't tell which things that model is able to accurately simulate and what not, and more, you can't tell when you simplify a model how much error you have and in which cases you are committing an error.
When you know all that, you're moving from hacking to approximations, that are a way more refined tool.

Today, we have a lot of computing power. Computer graphics is relatively easy. Anyone can display a spinning cube with a few lines of code, in any language. So you would guess that we are dealing less with hacks and more with maths right? We should be more conscious, as we don't have to be concerned anymore with some implementation details like how to draw a triangle (fast enough). Our first optimization should be in the algorithms.

Well, unfortunately, it's not so. Not in the slightest. We actually most of the times managed to forget about the hacks we used to do and just assume that is the way things work. We are in a pop era. And don't get me wrong, I love pop, there are many geniuses in it, but we shouldn't be limited only to it!

We recently discovered that we did not know anything about color. We were producing colors, but we did not know anything about them. And we still don't know. I guess that most rendering engineers just skimmed through the concepts of gamma, looked how they could fix that in the shader or using appropriate samplers and render targets, and hoped really badly that noone will discover any other obvious flaws in their work.

More or less the same is happening with normals now. How many people asked themselves what normals are? What vector operators do on normals? What are we doing? Recently, someone tried to answer those questions. It's not a complete answer, but there are a few nice pictures, and again, everyone seems happy. How many people actually questioned that interpretation of normal vectors that Loviscach did? How many people are using his formulas consciously?

People encode normal data into two-channel textures by storing x/z and y/z, as it's faster to decompress (you just need to normalize(float3(tex2D(sampler,UV).xy,1)) and you're done) and maybe because they saw some pictures demonstrating that the error distribution of this technique is more even across the hemisphere. Who cares that you can't (easily) encode any normal that has an angle wider than 45° from the z axis? Maybe you don't really care, and that error is something you can afford. But still you should know...

You should know that your linear or anisotropic filter in the sampler is going to do an average of your normal data. And averaging does not preserve length, so you will end up with unnormalized normals. Well, that's easy, just normalize them right? Yeah, that's the least you can do. Every operation that denormalizes something, you can fix it with normalize. But what are you doing? Who knows.

Actually you shouldn't care less about normalizing, you could do that only at the end, in your shading formula. Of course you can easily build an algebra of vectors on the two-sphere (unit vectors) by taking your familiar linear algebra operators and appending a normalize to all of them. But what are you doing? We use normals as directions, we should have our operations that are linear on the direction space. If an operation denormalizes our vector, but is leaves it still pointing to the correct direction, it's quite fine! If it leaves it normalized, but on a wrong direction, it is not.

Actually, the only way we can avoid the filtering error, is by encoding angles and not cartesian coordinates.

So don't normalize! Know your operations. Know your errors! Or if you don't, then don't try to be "correct" in an unknown model. Just hack, and judge the final visual quality! Know your ignorance. But be conscious, don't code randomly.

And of course those are only examples. I can make a countless number of them. I've seen a axis-aligned bounding-box class using taking as input Vector4. Well, in fact, some functions were using Vector4, some other Vector3, some other were overloaded for both. What are you trying to say? That the AABB is four-dimensional? I don't think so. That you are handling 3d vectors in an homogeneous space? Maybe, but after checking the code, no, they did not correctly handle homogeneous coordinates... Actually, I will be really surprised to see a math library were Vector4 is actually intended for handling that... Well, I'm just digressing now...

The problem is, unfortunately, that errors in graphics usually won't make your code crash. It will just look fine. Maybe, it will look a litlle bit CG-ish, or you won't be able to replicate the look you were for. Maybe you'll blame your artists. Probably you will be able to see in what cases it does not look good, and add some more parameters to "fix" those errors, until you don't have enough computing power to run everything or your artists go crazy trying to find a value for all the parameters you added. Or you'll wait for more advanced algorithms...
Yeah, raytracing surely will save us all, it's physically correct, isn't it?

P.S. Reading this (and all) my articles is a lot more intresting if you care to follow the links...

Stuff I'm reading right now...

...and you should be reading too:

Steve Yegge Blog archieve (READ IT ALL)

Visualizing Quaternions (incredibly cool)

Geometric Algebra for Computer Science

ShaderX 6 (but only when I'm really bored at work)

Begin here

Often, people ask me how to begin programming. Or doing 3d effects. Or how to write elegant C code, how to develop an aestethic. Those questions are really hard to me. I can point you to some great books on C++ programming. Or on programming in general, but nothing for beginners.

How did I? Well I started poking characters on the screen of a commodore 64. Then I learned about the 16th dos interrupt and the VGA memory starting address (0xa0000). Then I wrote my VESA library, started programming in protected mode, and then eventually moved to Windows and OpenGL. [note: Wikipedia is CRAZY]

Hardly anything I've read those days is useful now. Sadly I don't think that most future rendering engineers will ever learn how to properly draw a triangle in software (I don't really think they do now, and I don't even think most of them know how a GPU does). Most of the sites and resources I used are dead now.

So I don't know. I'm clueless. I know a few good books that I would recomend, but I don't know if they're really good for learning.

What I know is that you should always have fun. Do it for fun, noone starts with the maths. At least if you start young as I did, I don't think you'll really appreciate them, that comes later. And to me maths are fun now, they're much more fun than coding, so I'm still doing everything only for my personal enjoyment.

I would say, start with proce55ing. It's the most fun language I know of, and it's Java basically, so you will do graphics in a mainstream programming language. There are a few tutorials and courses on the processing site itself, there is an incredibly active community, and Java is an incredibly widespread language, you won't have any problems in finding tutorials and books for starters.

Then move to more serious 3d stuff. I would say, C++ or C#, and OpenGL. You could start with the famous NeHe graphics programming tutorials. Another good way is C# and XNA, especially if you have a 360. Then you will need CG to code shaders.

If you reach that level, you can start reading everything. Books. Papers. Take your time. It could easily require your entire life.

Don't EVER think to know enough. You don't. If you've been programming for 4-5 years and took a 5 years university course, then you will have just the basics that are required to be able to understand almost anything, with some effort. They give you only the alphabet, from there on, there is the real knowledge! That's the single most important advice I can give you.
I've seen countless people making fool of themselves because they actually believed they knew how to do something, while they just knew the basics to start learning how to do it.
And they are evil, because they truly believe they can do it, and they will do it, and it will be wrong. Don't get me wrong, doing things wrong is fine. If you're not writing production code for a company, that is. Well, but that's another story...

I haven't finished to learn, I read every single day new stuff. And I hope I'll always do. And this is why I'm writing this blog as well.

P.S. Oh I forgot. This one looks promising too as a starting language. It seems to be made for the younger ones but I think it will be interesting for everyone. It's based on Ruby.

P.P.S. The "fatmap" article on triangle filling... is just a starting point, more advanced coders will like to add perspective correction to n-sided polygons to avoid the cost of emitting multiple triangles after clipping... ;)