Today I was a lumberjack and flattened a (quad) tree

My review of the hotel we stayed at in London is now available “Berjaya Eden Park Hotel” As you can see it got a glowing review, I’d prefer to spend an evening with my mother and then catch syphilis (not that she has that).

So worked on the mobile audio lib again, added in lock free load queue which was something I worked out while on a treadmill last week. Then started looking at cutting the size of the quad tree down. Originally 36 bytes, 8 bytes each for min / max extent, 16 bytes for 4 child pointers and the content pointer. So started off converting that to a flat array, after large amounts of scribbling, came up with the obvious formula of (n*4)+1 will give you the offset of any node in a flat array. The children are then all linear, so the root node (0) will have 4 children 1, 2, 3, 4, using that formula you can then visit any of the children so node 1 which is the child of node 0 has 4 children, they will be 5, 6, 7, 8. Likewise node 2 which is also the child of node 0 will have 4 children 9, 10, 11, 12. To find it’s children apply the same formula, so 9 will be 37, 38, 39, 40. 10 will be 41, 42, 43, 44 etc. You know when you have run out of children as the offset will be greater than or equal to the number of nodes. So the only thing you have to store is the 4 byte pointer to the contents, you can calculate the min / max extent as you do the traversal. So that was actually good fun and well worth doing. Needs more testing and I need to apply the same thing to an octree.

Walked the dog (we are speaking again now), it was raining so wasn’t the longest walk ever done (she didn’t seem to mind). Went to the gym and did combat. Now have the Japanese GP still to watch. May well do that and have a bit of an early one and catch a film on the iPad. Oh the wine tasting is finally booked for November 17th.

Leave a Reply

Your email address will not be published. Required fields are marked *