Python, my first time

When it comes to learning a new technology I need some starting project that pushes me and gives me "momentum". In particular, it was years that I wanted to learn Python. I touched this language two years ago, at CINECA's SciViz course, and I toyed around with Django, but they have been momentary encounters and I was waiting for some small-sized, not too trivial problem to solve with it.

Recently, a friend of mine was experiencing problems with some visual representations of temporal series, stochastic in nature and very irregular as number of points. The dataset was huge (in the order of gigabytes) therefore an automatic solution was needed.

Probably PERL would have been a better choice, but I have taken the chance and, this morning, in a couple of hours I've completed my first Python project. It took a while to learn the syntax for dictionaries, lambda functions and some useful I/O classes, but the rest was really piece of cake. My final implementation works as follows:

• a brief preprocessing, in order to determine the length of each temporal series, done with regular expressions and a dictionary;
• some filtering on the dictionary, in order to remove spurious results;
• reading the file again while skipping, in every time series, as many rows as are needed to make the time series uniform.

The final code is about 50 rows long (comments included); an equivalent C++ implementation, probably, would have been much longer and complex. For sure, files I/O is much more verbose than the Python's with open(...) as descriptor syntax. 

I'm very far from a serious knowledge of Python's potential, but I'm impressed: the learning curve is astonishing, as is the clarity of the source code. I'm pretty sure that my future implementations that will not require some low-level functionality (eg., CUDA) or extreme performances will be Python-based.

Automated twits from a workstation, using IFTTT

When optimizing parameters of stochastic systems you can have hard time predicting when the process is going to end. It would be nice if the workstation itself warns you when it's done, just like Joshua used to give Lightman a call asking him to keep playing

Hello, Mr. Falken. You are a hard man to reach.

Telephone calls are demodé, anyway. It is much more web 2.0 if the workstation twits you that the jobs are completed and you can check the results out (or something went wrong and you gotta fix the code and so on).

Twitter does offer a RESTful interface for directly twitting stuff around, but handling the authentication takes a lot of work and time (that I don't have, actually). So, I tried something different. Something like this:

Spannometric :) sequence diagram of the system

The key of the process is IFTTT, a nice tool that "[puts] the internet to work for you by creating tasks that fit this simple structure if-this-then-that". In this case, IF "a new message from the workstation is received" THEN "twit the message to @aresio", message that is then forwarded to my Android terminal automatically. IFTTT does a 15' polling, so it's not a real-time thing, but pretty close.

Almost anything was already done, I just glued the pieces together by developing all the stuff on the web server: a simple RESTful interface exposed to the workstation and a plain RSS feed; matter of five minutes, and it works.

Thanks Joshua! 

CUDA, random numbers inside kernels

Evolutive algorithms have an intrinsic stochastic nature, therefore they make large use of random numbers generators, for instance the C/C++ rand() function. Anyway, when GPGPU comes into play, using random numbers could be tricky.

The naive solution of create and pour them into GPU's global memory is a bad idea, because of the huge bandwidth that would be wasted. Therefore, it takes a device-bound generator. Nvidia's CURAND library makes it easy to generate random numbers directly inside CUDA kernels.

A bit of theory...

Obviously, it is impossible to generate really random numbers on a deterministic machine. Any random function just applies some kind of transformation on another number, determining a succession that looks like a random one. Anyway, two successions starting from the same number (the seed) will be completely identical. If our kernels start from the same seed, regardless the algorithm, they will produce the same results. They must be different. Moreover, you have to store the previous numbers (let's call them global states) in order to produce the next ones during the following execution of each kernel. Fortunately, CUDA allows the storage and update of our partials directly inside GPU's memory.

...and some sample code
I post the example code - comments will follow.

__global__ void setup_kernel ( curandState * state, unsigned long seed )
{
    int id = threadIdx.x;
    curand_init ( seed, id, 0, &state[id] );
} 

__global__ void generate( curandState* globalState ) 
{
    int ind = threadIdx.x;
    curandState localState = globalState[ind];
    float RANDOM = curand_uniform( &localState );
    globalState[ind] = localState; 
}

int main( int argc, char** argv) 
{
    dim3 tpb(N,1,1);
    curandState* devStates;
    cudaMalloc ( &devStates, N*sizeof( curandState ) );
    
    // setup seeds
    setup_kernel <<< 1, tpb >>> ( devStates, time(NULL) );

    // generate random numbers
    generate <<< 1, tpb >>> ( devStates );

    return 0;
}

Obviously, you have to include not only CUDA's includes and libraries, but CURAND kernel's as well (curand_kernel.h). Let's see what happens in the code, starting from main.

First, we create a curandState pointer, that will point to our global states.

Kernel setup_kernel will invoke curand_init(), that takes some seeds (I used the seconds since the Epoch, but it's free to the user) and sets the global states.

Generate() kernel creates N threads. Each thread will have its own random floating point number, by using a local copy of its global state. In this case, the random number it's sampled from (0,1) with a uniform probability, but CURAND gives the possibility to sample from a standard normal distribution as well.

Finally, we store the new seed into the global memory, and return.

The BOIDS are back in town!

During the last lesson of complex systems course, prof. Vizzari showed a crowd simulation based on BOIDS, an intriguing model invented by Craig Reynolds in 1986 that simulates bird flocks, fish schools and all that kind of self-organizing masses of living stuff. The basic model is based on three simple assumptions:

1. each boid moves toward the other flockmates (cohesion)
2. each boid moves away from crowded situations (separation)
3. each boid follows the direction of the rest of the flock (alignment)

Even in its simplest formulation the model works very well, and gives a pleasant feeling of viability. I turned the model from 3D to 2D, by putting all boids on the y=0 plane, and here we go: we have a simple crowd simulator.

There exist several approaches to crowd simulation (like cellular automata or multi-agent systems) but I do think that BOIDS have many interesting capabilities.

In fact, one of the open issues in crowd simulations is the sponteneous formation of groups because of common goals, shared costumes, socio-political aspects, familiar relationships and so on. BOIDS leave a lot of space for embedding this wide spectrum of behaviours, whilst the model itself mantains the proxemic distances between people and let them gather peacefully, by the rules decribed above.

The video I embed shows my model in a simple scenario made of four groups (yellow, red, green and blue). Green people have their own goal to follow; red and blue have a shared one. Yellow people just walk around the space, with no specific purpose. In the middle of the screen there's a strong repulsor which keeps boids away. The dynamic works as I expect: there's the formation of clusters, boids belonging to the same group tend to aggregate and find their way even in overcrowded situations. What's fascinating is the emerging, unexpected behaviour of yellow ones: some of them hold still, some dodge the crowd, many other enter the moving groups and follow them wherever they go, conditioned by the first rule.Very nice.

Hajj - the annual pilgrimage to Mecca - is
one the most interesting scenario to simulate

Still, there's a lot of work to do that I'll share with my brilliant coursemate Michele. For instance, we'll try to identify the correct parameters that fit the experimental results, incorporating Elias Canetti's proxemic dynamics as well. We also could find a way to introduce different kind of non-penetrable contraints (walls, doors, and such). There's the problem of instructing complex goals (like finding a way to an exit in non-straight situations or following a leader), with an eye to stability and realism. Finally, there's lot of optimization to do: I wrote the code as general classes and new rules can be easily introduced by pushing a new function pointer to a "rules" vector. That's very flessible, allows a very rapid prototyping but it's very inefficient: the naive algorithm is O(n²), because every boid's position needs to be compared with the rest of the flock, and every rule is computed on its own, adding a costant factor. Too slow for serious business like sport events, concerts, and religious pilgrimages, just to name a few of the typical simulations that require millions of individuals at once.

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!

Ants gone wild!

I'm currently attending the soft computing course, and it's terrific! I always loved stuff like genetic algorithms, neural networks and such, but I wasn't prepared for particle swarms: it's been a shocking revelation. I really fell in love with them, I adore the wide spectrum of emerging behaviours those bunch of coordinates exhibit and I feel overwhelmed when I think about creative uses of the model.

Because of the nature of soft computing's solution spaces, it came natural to me to develop everything in C++, by using templates and wild meta-programming. Now I have a set of absolutely general algorithms and in particular an extended PSO which automatically adapts to any kind of solution and relative function to optimize. Everything seemlessly fit in my PLT graphic framework, and let me visually check its goodness with traditional benchmark functions: Rastrigin's and Shaffer's F6. Swarm perfectly finds a way to the optimum in a very natural-looking way.

Online Integral Evaluator or: yet another Wolfram|Alpha widgets hello world

I always loved Mathematica for its symbolic architecture, and that power is now freely available online through the stunning Wolfram|Alpha computational engine.

In these days, I'm studying for the third calculus course and I'm using Alpha extensively for definite integration. When I heard 'bout Wolfram's Alpha widget builder I felt natural to develop an on-line integral calculator.

It's simple indeed, but very nice. Too bad our university's facts knowledge base is too short, because I can't imagine any killer application for the website yet. I contacted the Wolfram labs, in order to extend it a bit. One day, who knows...

Aho-Corasick (multiple pattern match) in PHP

When I started programming Mergifier, my "RSS feeds dispenser", I knew I was going to need some kind of terms filtering. It's useless to take into account the most common words, for they don't bring any information.

My initial solution was to split the text into an array of substrings and use array_diff to remove those in my blacklist array. I don't know the asymptotic cost of array_diff algorythm, but using it with plenty of items (featuring long titles, summaries and descriptions) soon appeared a bit too expensive.

Recently I studied a lot of pattern matching algorythms, including the well known "Aho-Corasick" which checks occourrences of multiple patterns "at once" inside a text of length n in O(M+n), being M the total number of characters composing the patterns. Useful for virus signature detection and bioinformatics, I did not find its implementation anywhere, so I did my own!

Download the code



As you could see inside the code, this algorythm is cool because one can precalculate delta/phi transition tables and cache them, brutally speeding up computations on many different texts made of many terms.

If you find this code useful, or if you have any kind of suggestion to improve it, please let me know. :)

Mergifier: a bayesian RSS filter

The RSS feed is a popular format used to publish information. XML based, therefore machine-readable, it was thought as a "container" of news from frequently updated web pages. Personally, I love using iGoogle as aggregator to keep, in a single screen, lot of feeds that keep me constantly updated about intersting facts happening around the world.

We introduced early this technology on Bicocca's website, to spread interesting facts in an aggregate way; we placed RSS feeds in pages featuring news, events and so forth.

We recently talked about this system and we did not find it optimal. We think that it could be more effective to route all this informations into single feeds intended to particular audience, instead of fragmenting everything into many rarely-changed small feeds. Stefano has partially mitigated the problem by creating a feed's map, but we agreed that is sub-optimal: we still prefer something able to gather everything in a single channel and "skim" the news according to the reader's interest.

A similar project is Yahoo! Pipes, that I discovered during the course of knowledge representation. YP allows, among other, to "sum up" contribution of different feeds into a single one but cannot classify the outgoing items (or, at least, I can't find anything like that :) ). Reading some post from the project's board, it seems I'm not the only one lamenting this lack. Not a problem, because in the meanwhile I rediscovered the wheel.

"Mergifier", that's the name I gave to the software, draws from an arbitrary number of RSS feeds (and ATOM  as well) and integrates them in a big cauldron. The administrator - that is us, at the moment - is allowed to create as many categories as he wants and every item can be classified in one or more of those. Naturally, I'm not talking about a trivial table, because we don't want to classify every entry by hand. That's why I used a bayesian filter.

More ham for everyone

The idea comes from the bayesian spam filtering used in software like Mozilla Thunderbird: whenever you receive an unwanted letter, you classify it as "junk". The client stores words' frequencies and use those informations to determine the probability of future e-mail's to be spam.

The probability estimation is quite simple: 

where p1...Pn  is the individual probability of a word to be present in a "junk e-mail". How can we determine that? By using the following formula:

where

• Pr(S|W) is the probability of e-mail to be spam
• Pr(W|S) is the chance of finding the word in a junk e-mail
• Pr(S) is the "a priori" probability of a mail to be spam
• Pr(W|H) is the chance of finding the word in a good email
• Pr(H) is the "a priori" probability of a mail to be ham (that is the way "not spam" e-mail are called!)

The idea was to replace the concept of spam with our own categories, and compute those probabilities "online" by fetching from the feeds and letting us classify them. Naturally, the most common words are blacklisted in order to lower the work of database.

This method works stunningly fine; we're testing the results in order to release an alpha during the next weeks :) .

Just for fun: obfuscated hello world, in C

main(int argc,char*argv[]){memset(&argc,0,1);char*s[11]={0,-3,4,4,7,-40,15,7,10,4,-4};while(argc<11)printf("%c",s[argc++]+0x48);}

What could this code do? =)

The reason behind this code is here.

IE - object does not support property or method

Have you ever experienced the error message I wrote in the title? Are you hitting the walls with your head wondering what the frak it means? This post might be useful to you!

I wrote a page that worked seemlessly inside every know browser but Internet Explorers. Well, nothing new under the sun, web developers' work consists mainly in making things run inside that shit.

Anyway, I was surprised by the nature of the error message: "object does not support property or method", raised during a getElementById call:

foo = document.getElementById("foo");

Element "foo" was a DIV placed in the middle of the page.

So I asked to myself: "what is IE trying to say?". If it really meant that a method wasn't supported, therefore it had to be the getElementById() function, because no other method was involved. But I'm pretty sure that document object HAS a getElementById method. 

The other possibility is the lack of support for the property... but which one? The foo variable?? Yay man! The correct answer is this: you cannot give a variable the name of an element's id. By renaming the variable everything works correctly.

baz = document.getElementById("foo");

Here we go. Do you think this is nonsense? Well, so do I. 

• First, there's no reason why an HTML element should interfere with javascript variables. 
• Second, the error raised is totally incomprehensible and misleading. 
• Third, it's incredible that in 8 versions of IE Microsoft did not think of fixing this.

Inline-block and Internet Explorer

I use to collaborate with the press office of the University. In particular, I was asked to develop a sort of enhanced, multidimensional, collaborative "address book" that they use as a database of journalists.

During the development process they often changed requirements, with the result that the project grown way too much. In order to keep the user experience pleasant I did my effort to allow high interactivity to the operators, giving them a very intuitive interface. I do think that one of the best interfaces for contacts collection and relationships definition remains the Facebook's one. In particular, I love the way it displays collection of items as set of icons, in a web 2.0 fashioned way.

To obtain this kind of representation, I used HTML lists and set items' display property as inline-block. Bad idea: Internet Explorer (even the 8!!) does not understand it. Well, the latest release (that is supposed to be CSS 2.1 compliant) actually understands it, but only if the object is natively an inline, which is weird.

So, here comes the workaround:

display: inline-block; 
zoom: 1;
*display: inline;   

This fixes everything.

Deleting stuff with javascript

Would you like to clean house with js without messing around with hidden stuff? Piece of cake:

document.getElementById("thing_to_delete").parentNode.removeChild(document.getElementById("thing_to_delete"));

Yes, it's kinda weird, just like referring to myself as "the son of my father", but it actualy works.

3D collision detection

3D libraries are conceived as just drawing primitives, and nothing more. That's why graphics programmers are asked to reinvent the wheel several times.

One of those wheels is the "world space" partitioning. In particular, the collision detection of meshes.

I don't know how serious engines handle it on a per-pixel/vertex basis, but I think they just do miracles. I implemented something simpler for my PLT by using cheap bounding spheres.

The improved geometries loader "keeps in mind" the minimum and maximum coordinates for each axis, while it constructs the vertex arrays; at the end of the loading process, it uses those coordinates to find the middle point of the mesh and the farthest vertex from it: they are the bounding sphere center and radius, respectively.

Checking if a mesh collides with another is straightforward:

• transform the bounding centers from model to world space, and compute the distance (let's call this value "D") between them
• sum up the two bounding radius (let's call it "S")
• if D > S meshes don't collide
  

It's kind of a cheat, but it works.
Of course, using complex meshes will reveal its nature: it's far from being accurate. But it so fast!

I think there's a couple of possible optimizations.

The first one is, well, "CAD driven": I could simply cut down every model into many "groups", and give everyone its own bounding sphere. The drawback is, obviously, that the designer is asked to think meshes as a collection of separate tranches, and everything works better if each partition fills out its "space". Moreover, this solution makes LOD design slightly more complex.

The second one is more challenging: compute the partitions on fly, during geometry loading, by using a stochastic approach: areas denser of polygons are more likely to be relevant for the mesh, and should be enclosed by their own bounding sphere.

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.

Sprites, animations, and 3D textures

During the 80s real 3D was just a chimera. Apart some pioneer, embryonic vectorial engine, computer graphics was achieved by using small bitmap images, stored in contiguous memory locations: the sprites.

Borrowing from traditional techniques, sprites were animated by drawing the animations in separate images (a classic example) and displaying them in sequence, creating the feeling of dynamism.

Before the transition from 16 to 32 bits systems, many hardware engineers introduced several solutions for smoothly rendering lots of sprites on screen (eg.: DMA, dedicate co-processors, and so on), but they were soon forgotten as full 3D engines appeared and stole the scene.

So, why should anyone bother getting the sprites back from the past? Well, they could be useful even today, because there are aspects of computer graphics which work better pre-rendered: explosions, flames, debris, smoke and all that stuff it's too expensive to compute real-time.

An higher dimension
As I wrote, sprites animations used to be stored in different memory locations, and the pointer to the current frame was given to the scanline renderer. We could do the same now, creating several bitmaps and rendering them on screen. But this idea has a couple of drawbacks: we need to create many different texture objects for the same "thing" and, in order to obtain a smooth transition, we must load plenty of slightly different images.

Another idea could be to load a huge texture featuring all frames on it, and display the current one playing with offsets: this fixes the first issue, but not the second one.

A nice way to achieve both is to use a 3D texture. A 3D texture is, basically, a stack of normal 2D textures. The number of "stacks" is called "depth", and it's a parameter we must give during initialization. Pay attention here: as normal textures, even depth must be a power of 2.

Why do 3D texture give us no drawbacks? First, they aggregate lot of textures in one single texture object. Second, when you make request for an intermediate stack, you can be given the interpolated texture. This is transparent by turning on linear filtering, and does not impact on performances.

A nice explanation of this technique can be found here. The following step is billboarding, that is keeping the sprites frontal to the viewer. There's a cool NeHe tutorial about it. If you want to play with sprites but don't have time/skill for producing your own explosions, check this out.

Does your shader seamlessly compile, but inexplicably doesn't link?

Maybe it's due to the GL_MAX_VARYING_FLOATS limit.

If you go crazy obtaining the error "Fragment shader(s) failed to link", try reducing your explicit -and implicit- varyings variables.

It turns out that, for instance, you cannot combine 8 textures and 8 "blinn-phong light sources" inconsiderately, because if you would like to interpolate textures and light vectors, you end up using (8+8)*4 = 64 varyings floating point variables!

Keeping out useless textures coordinates (z,w) and the alpha channel, by using custom varyings instead of the built-in ones, you can go down to 8*2+8*3 = 40, which is lower than 44, limit for most common DX9 compliant boards.

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!

Arbitrarily turn static functions into individual threads

There's a lot of routines that are supposed to run "behind the scene", accomplishing repetitive and constant taks. For instance, in 3D engine the movements should be time-based, so that things behave the same way indipendently from the underlying architecture. We could define a class that "checks the clock" and computes the "amount of changes" to do in the scene. Our observers - that is a geometry transformers or a physic routine - simply "emphasize" their values proportionally to the elapsed time.

The best way for keeping "background duties classes" and the main engine separate is the use of threads. I already used them in the past, but in a statical way. This time, I wanted some kind of "abstract thread converter" which takes a pointer to a static function and turns it into a thread on its own.

Here comes some brief snippet. First of all, I defined a PLTthread class:

class PLTthread {
public:
  // empty constructor 
  PLTthread() {};
  // links the specified function, using specified  parameters
  void LinkFunction(static DWORD WINAPI fun, void* dwThrdParam = 0); 
private:
  // handler for the created thread
  HANDLE ThreadHandler;
  // thread ID
  DWORD dwThreadId;
}

Many additional methods could be created for handling thread's execution, but I wanna keep this example straightforward: you'll just pass a static method and it will start on its own. The actual code:

void PLTthread::LinkFunction(static DWORD WINAPI fun, void* dwThrdParam) {
    this->ThreadHandler = CreateThread(NULL, 0,
                            (LPTHREAD_START_ROUTINE)fun, &dwThrdParam,
                            0, &this->dwThreadId);  
    }

That's it. Now you can instantiate a PLTthread class and send it your function, casting it as DWORD.

Threads are a bit tricky, MFC are a pain in the ass; everything is a complete mess if you use to think object oriented. But this facility helps me a lot.

Meshes from points

It's been an hard job, but an interesting experience. My 3D engine "PLT" now features its own Delaunay triangulation. Now I can turn an arbitrary set of points into a continue, smooth, tridimensional mesh.

The algorythm is well explained on Wikipedia, and practically consists in breaking an encompassing triangle in smaller ones, ensuring that every triangle does not "contain" any other vertex.

This check is the heart of the algorythm and it's achieved by verifying that every vertex lie outside the circle identified by the three points of each triangle.

There's a lot of geometry, trigonometry and even a little bit of calculus inside of this piece of software; the exams of discrete algebra and calculus found a practical, consistent application.

The next step is to speed it up: the algorythm is far from its potential O(n log n) possibilities and must be optimized. It seems to be even greater than the expected O(n²), probably due to the STL internal sorting algorythms.

Thanks to Erazor for the idea and Gerry for the math support. =)