A softer way of life

Soft computing course: completed! A sparkling 30/30 cum laude closes an astonishing and inspiring experience.

I chose this course primarly because of simulated annealing and neural networks, for I studied these techniques in a very formal way (cybernetics) and from a philosophic point of view (epistemology). I was interested into a more concrete approach, and I found it here. But there was much more!

I discovered a wide range of special neural networks, Hopfield's and Kohonen's in particular, which show several interesting capabilities that I'd like to experiment soon. I finally studied the infamous back-propagation, able to learn non-linearly separable tasks, and that was good. But despite my initial expectations, these weren't the most interesting parts.  

Genetic algorithms, for instance. It's funny to think of data structures "sharing genetic material", maybe discriminating partners according to their own sexual tastes (Booker's model), with their children being subject to random mutations. Well, believe it or not, but that funny stuff works! My experimental data clearly say that GA are a strong and robust way to tackle NP problems. The drawback is the difficulty of modeling the solutions' search space by using simple codified strings. Moreover, genetic algorithms can find a global optimum for a specific problem, but not whole classes.

So, here comes the Genetic Programming. Yep, double upper case here. Whereas the GA were funny because of data sharing genetic information, what we have here are copulating programs... so nice! Massive derivation trees create brand new offspring generation after generation, letting new abilities to emerge and spontaneously losing the useless (a process called automatic feature selection). The way GP works  immediatly calls for a LISP implementation, and that's what I tried to do... even though I'm still stuck on a pure functional, recursive crossover function.

In the end, my personal favourite model, whose I dedicated my blog to: the Particle Swarm Optimization. Yeah, triple upper case. As I wrote in the past, I love the spectrum of emergent behaviours this bunch of simple coordinates show. Just like Conway's game of life, there seems to be some kind of unpredictable lifeforms inside the model, and that is cool. Moreover, it can be quickly extended:


This example is an interesting kind of PSO that prof. Vanneschi proposed, named Multiswarm Repulsive PSO (or MRPSO). It features more than just one swarm living on different "islands", all looking for the same global optimum. After some generation, best individuals are cloned and replace the worst ones by migrating to the next island. Moreover, on some island, the particles run away from the best individual, instead of following its "pheromones trails". This approach solves two possible drawbacks of PSO: the lack of diversity and the tendancy that individuals show of blindly following the leader, thus keeping away from interesting unknown zones of the search space. The boost of performance is stunning, and still there's a lot of space for inventing new ways to improve it!

The evolution of parallax

Once upon a time, videogames were bidimensional, and it was fine.
One day, in order to give some depthness to the scene, programmers introduced a technique called parallax scrolling: by moving the elements of the background at different speed, a sense of spatiality and immersivity emerged.

The sensation was outstanding for the age, but the drawback was a very high computational cost, that kept this strategy confined on 16bit machines. With the arrival of 3D graphics, parallax scrolling was abandoned.

In 2001, a Japanese researcher named Tomomichi Kaneko introduced a brilliant modification of texture mapping able to provide "the capability to represent the motion parallax effect to the textures placed on 3D objects". His algorythm was basically a normal mapping, whose strategy is to use a texture's RGB channels to map a 3D normal, overriding the vectors on surfaces; Tomomichi basically suggested to enhance the feeling of movement by displacing textures by a function of the view angle in tangent space.

The tangent space itself is the trick behind all, and let us compute stuff in a comfortable space: instead of doing tons of computations in world space, we "look at things" from the top of the texture.

The generation of the special coordinates (normal, tangent and binormal) is done "client side" during the geometries loading, and sent to the server as vertex attributes.

The normal mapping itself requires at least a couple of textures to be sent and, guess what, I faced again the limits of DirectX9 compliant boards. I wanted to keep at least 4 lights on the scene, and use three textures (diffuse, normal map, and a gloss map). I quickly overflowed the capabilities of my VGA card and learnt an interesting thing.

GLSL is paranoid

I'm not sure it's a GLSL thing, but that's it: it's paranoid. It expects the worst scenario to happen. And therefore does not optimize a thing. I explain.

Suppose you have a code similar to this:

void DoSomething(int number_of_light) {
  ...
  Use( gl_LightSource[number_of_light] );
  ...
}

void main() {
  ...
  for (int i=0; i<TOTAL; i++) dosomething(i); 
  ...
}

What do you expect? You may think that your GLSL compiler will smartly recognize the boundaries of your  request and will fetch from memory just the informations about the TOTAL lights you're going to use. Well, wrong: it will allocate all MAX_GL_LIGHTS informations as uniforms. A mess. By keeping your code so general you instantly reach the limits of the card and the program does not link anymore. I didn't know about this (never read about that) and there's no way to optimize it. You must do several fetches to each specific light source you want to use on the scene, and that way you keep the uniforms count down. Weird.

Fixed functionality beats programmable pipeline 10:0?

Something's terribly wrong somewhere... Blinn-phong shader is wasting all GPU's power!

I've done some optimization, but I'm afraid that writing general code, good for all seasons is not the best way to achieve performance.

I can't imagine how many compromises serious 3D engines hide under the hood!