Saturday, 29 August 2009

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.