Clap your hands say yeah right

I tried to balance the HBV-tree (i.e. by putting approximately the same amount of triangles within each branch throughout the tree) this morning. I did not gain anything. On the contrary, it became slightly slower.

This might not come as a surprise after all. Reasons for this might be:

• On average the triangles might already be uniformly distributed within each AABB which will make a mid-point split essentially the same as dividing the amount of triangles into two equally big sets … but with the additional cost (log N) of ordering the triangles in the latter case.
• We must remember that this is not really a one-dimensional problem. It is not like sorting Strings for instance. The intuitive approach is to balance the tree with regards to amount of triangles in very much the same way as we would like to have a TreeSet of Strings well-balanced regarding the amount of strings in each branch. Instead the midpoint-split strategy will balance the three with regards to space. i.e. we can discard spaces instead of approximately half the triangles in each step … Well. I think.

I need to investigate this further when I have time. I guess it would be possible to add some simple heuristic too, making better splits. Intuitively: Lowest possible total area of each daughter-AABB is probably something worth striving for (ehh, inevitably going in a SAH-direction) … Well. Another time.

Implemented the simplest spatial data structure I could think of, Hierarchical Bounding Volumes. Now each mesh recursively subdivides the space it occupies into a hierarchy of axis aligned bounding boxes until each leaf-box contains a maximum of 3 triangles (will try different numbers here in due time). Each AABB is simply split on the mid-point along the longest axis of the AABB forming two smaller daughter-AABB:s. Splitting mid-point was the easiest I could think of but unfortunately this does not balance the tree. I will try a balanced version when I have time for it.

The results (rendering of 15k-tri-bulldog at 800×800, 16 samples per pixel):

• Before implementation of HBV: 13000 seconds
• After implementation of HBV: 97 seconds

Surprisingly good.

Ok, anyone into rendering and speedup-structures might ask: Why don’t you go for a SAH-kd-tree directly, they have been shown to be superior to HBV?

And my answer is: For now a simple approach will do. Kd-trees, although faster, are much more complex and will just make my code harder to read. HBV could be implemented in 15-20 lines of easy-to-understand code. Looking at the results above I would say that HBV give hell of a bang for the buck.

Interesting program this year addressing an even wider audience than last year.

Some samples from the program:

• Sting
• Anna Christoffersson och Steve Dobrogosz
• Moneybrother

I had two days commuting to Uppsala during this weekend which was just enough to give me the time to start looking at step 3 of Verso – adding meshing capabilities. Unfortunately I realized that this is something you hardly implement during 4*40 minutes on a train. Partly because of the rather crowded 30-degree-celsius-compartment, partly because this feature requires some additional things I had forgot. In practise the meshing cannot really exist on its own. To have some use of it we also need a mesh-loader/importer and some spatial-speedup structure. Without those two it is rather useless.

Ok, so I’m only halfway through step 3 at the moment:

• The “Mesh-primitive” has been written.
• Rudimentary loading of a 3DS-file done.
• Bounding-box-functionality added to the system.
• The mesh can be rendered with flat polygons.

Still to be done:

• Spatial data structure.
• Normal-interpolation (aka bye bye mr flat-dog).
• Better importer/loader.

The image (well not the thumbnail version) above which consist of 15.000 polygons took 3.5 hours to render. This is of course pathetic (since any scan-line engine would be able to draw 50 pictures like that … per second) and indicates the need of some kind of spatial ordering of the data.

I guess I’ll get back to it next time I am on a train commuting somewhere.


BTW: On shaving bulldo… eh… yaks.