The farm of convexity

I'm working on my first scientific visualization "job" in these days; it's a computational fluid dynamics simulation, which has to be displayed to make some inference.

Instead of importing datas into VTK, I loaded them into my 3D framework. And it was a fail, because of three conceptual errors:

• my engine was written to display polygons; instead, we have ~3000 point samples which have to be manipulated in different ways
  
• datas were in double precision! all my framework used to be in floating point, and the loss of data was unacceptable
• a single point dispersed in a sea is not recognizable; its impossible to make inferences. Therefore, I thought it could be nice to partition data in sets, and display a convex hull of similar points.

Convex envelopes
Given a set of points, a convex hull is the minimum convex boundary which contains them.

There exist many algorythms for computing it, by my choice fall on Jarvins' March: also called "the gift wrapping algorythm", consists in... well... rotating around your set trying to keep your sheeps inside the corral!

1. the algorythm starts choosing a single point which surely lies on the hull (p0 in the image)
   
2. you trace a vector from your point to any other point in your set
3. [important] you compute the angle formed by an axis and the previously traced vectors, and you pick the minimum one by using the arcotangent.
4. now you have the second point and iterate from 2; on step 3 you'll naturally won't pick just the minimum, but you'll check that the new angle is greater than the last one

If "h" is the number of points in the convex hull, and "n" the number of points in the set, the complexity of this algorythm is O(nh), which is cool.


Going back to the CFD job, I used the convex hull to display the set of points featuring the highest values. Well, the first screenshot shows how useless it is: the points are too far, and this representation, again, does not help us in any way. Probably, a better way could be to keep together the closest points, using some kind of "distance" function. I'll work on it.

Wavefront .OBJ files & Vertex Buffer Objects

OBJ files are handy for many reasons:

• they're text files
• well documented
• easy to parse
• and many professional softwares can export them

This is why they are so popular as standard files for 3D graphics.

Their structure is basically a (long) list of vectors definitions (spatial, normals, texture coordinates, and so on) followed by a (long) list of structures defining faces. What are faces? Faces are tuples of indexes, which point specific vertexes, normals and texture coordinate in the previous lists. At least three vertexes are needed for each face, because it forms a triangle, that is the smaller polygon we can create.

Why is this needed? Well, because a single vertex could be shared by many faces (=polygons). That's important in real-time 3D programming, because avoiding redundancy is good for performances!

This is the very same idea behind OpenGL's indexed vertex arrays: rather than sending to the video card a list of vertexes, normals and texture coordinates (the so called immediate mode) we prepare a couple of arrays filled with informations, and another array of indexes which tell OpenGL what vertex use in a certain primitive.

Sounds good, uh? Well, there is a couple of drawbacks actually.

The biggest is that every index points simultaneously at vertex, normals and texture arrays! For instance, if our first index is "1", that face points vertex[1], normal[1] and texture_coord[1]. That's a real nightmare, because there's no ensurance that our modeling softwares will produce .OBJ files featuring correctly ordered lists! Moreover, there's often a few of vertexes (which are often shared by many faces) and lot of normals!

So what?? Well, OpenGL does not aid us in any way: you gotta solve with your hands. My solution is the following:

• parse the OBJ file, loading vertexes, normals, and faces;
• from faces, create a definitive vertex index and a temporary arrays for normals and textures coordinates;
• for each i in number_of_indexes do
  definitive_normal_array[ index_array[i] ] :=
  Temporary_normals_array[ TemporaryNormalIndexes[i] ]

And there you go, you have correct normals bound to the right vertex. You could even have time for re-normalizing them, if they aren't.

The most interesting way for drawing this series of arrays is the use of Vertex Buffer Objects (VBO). They're similar to the indexed vertex arrays, but have interesting features... like dropping geometries in the fastest video card memory and use it! The boost of performances is impressive, and they are easy enough to deal with.

My PLTmesh::Draw() method is this:

// PLT_VBOnames are references to the VBOS - see glGenBuffers()

glEnableClientState(GL_NORMAL_ARRAY);
glBindBuffer(GL_ARRAY_BUFFER, PLT_VBOnames[2]);
glNormalPointer(GL_FLOAT, 0, NULL);

glEnableClientState(GL_VERTEX_ARRAY);
glBindBuffer(GL_ARRAY_BUFFER, PLT_VBOnames[0]);
glVertexPointer(3, GL_FLOAT, 0, (char *) NULL );

glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, PLT_VBOnames[1]);

glDrawElements(GL_TRIANGLES, this->IndexesArray.size(), GL_UNSIGNED_INT, (GLvoid*)((char*)NULL));

glDisableClientState(GL_VERTEX_ARRAY);
glDisableClientState(GL_NORMAL_ARRAY);

glBindBuffer(GL_ARRAY_BUFFER, 0);
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0);

Quite simple and clear! :)

We meet again, dear wheel

Soon after my experience at CINECA, I took the decision to implement my own 3D engine.

I'm not trying to develop the ultimate graphic experience, of course. I just wanna own a set of libraries useful for easily handling and displaying scientific information, without too much effort.

Actually, I tried to avoid the huge effort of programming a whole 3D framework from scratch by using OpenSceneGraph; well, I tried, but it turned out that making it work was going to take more time than coding my own! Furthermore, I probably won't make always use of a scenegraph for my representations, so here we go.

The first thing I focused on are shaders: PLT is going to be a GLSL-centric engine. The fixed pipeline is still supported, more or less, but there's no future for it, and it's time to leave it alone.

Besides the qualitative leap that shaders allow (the screenshot shows a comparison between fixed functionality and a phong-blinn lighting), there's another huge benefit: the engine can easily be ported onto embedded systems. That's the second aspect I'm focusing on: portability. I want PLT to run on every system I could code on: Windows, Linux, and Windows Mobile.

What misses at the moment? A true geometry loader, for instance. There's already full support for vertex buffer objects, and I can manually load vertexes, normals and so on, but I must code at least an handy .OBJ loader.

As I told, there's no a scene graph, not even a rudimentary one. I'll surely need a bunch of matrix functions for manipulating my objects loaded server-side.

And naturally, I'm going to extend the PLTlights classes for shadow maps support as soon as possible! :)

Nei panni del neo laureato

A differenza di molti neo-laureati, essendo già un dipendente a tempo indeterminato non ho avuto alcun problema nell'annaspare tra le offerte lavorative radunatemi dagli uffici di job placement subito dopo la proclamazione. Devo anzi ammettere che mi sta procurando un certo diletto osservare la nonchalance delle aziende nel chiedere la Luna in cambio di un tozzo di pane.

Nella fattispecie, qualche giorno fa mi è arrivata questa perla:

"Multinazionale X, impegnata nel settore Y (che naturalmente non c'entra nulla con l'IT), cerca un tirocinante che dovrà creare e sviluppare software che (traduco dall'inglese) 'ci faccia guadagnare di più'. Il tirocinante deve sviluppare programmi, aggiungendo features a richiesta e, quando sono completati, mantenerli, supportarli, formare le utenze, fare supporto regionale e nazionale e creare soluzioni ancor più complesse.
E' richiesta una laurea, esperienza in C#, C, C+ (cos'è!!), C++ (seh..), Java e .NET, e in generale della programmazione OOP. Sono considerati bonus: esperienza in VBscript, ASP e SQL (evvai!). Necessario inglese di buon livello. Lo stage durerà sei mesi."

Ora, una persona che ha già esperienza (non conoscenza!) di metà di quei linguaggi è già un ottimo elemento, da trattare coi guanti. Si è laureato, quindi non è l'ultimo dei fessi. Ha un inglese di buon livello, che già per un italiano medio è una chimera. E tu, trovato uno così, gli offri sei mesi di stage sottopagato, in giro per la nazione, a fornire supporto e formare i clienti? Mabbaff...

100th post!

Arrivoooooo!!

Una bella infornata di OpenGL a livelli massicci... e soprattutto OpenScenegraph! Non vedo l'ora!

Spero solo che il mio nuovo Presario arrivi entro domani! Daje mediaworld!