I am going to discuss a difficult problem related to geometrical algorithms for space partitioning (2d, 3d, hyperspace).
The problem is concerning a special kind of tree called *Octree*(in 3d) or *Quadtree*(2d). The Octree/Quadtree structures are used to hierarchically partition objects present inside 3d or 2d space. There was a recent paper from NVIDIA which proposes a fast algorithm for constructing *Octree*. Here is the link to the paper: http://research.nvidia.com/sites/default/files/publications/karras2012hpg_paper.pdf The author proposes constructing the Octree using another primitive kind of tree called* binary radix tree. * *The Octree construction as described in paper consists of of seven steps: * > (1) calculate Morton codes for the points, > (2) sort the Morton codes, > (3) identify duplicates, i.e. points falling within the same leaf node, by > comparing each pair of adjacent Morton codes, > (4) remove the duplicates using parallel compaction, > (5) construct a binary radix tree, > *(6) perform parallel prefix sum to allocate the octree nodes, and * > *(7) find the parent of each node. * > I am working on implementing this algorithm and so far I have understood and implementing steps (1-5) of the algorithm in the paper. *However the final 2 steps i.e step 6 and 7 in the paper are not described properly and I am having hard time understanding it*. *Below is the paragraph which offers some explanation about steps 6 and 7 (copy pasted verbatim from paper) but not in a clear way* *Octrees. To construct an octree for a set of points, we observe that each > 3k-bit prefix of a given Morton code maps directly to an octree node at > level k.* > *We can enumerate these prefixes by looking at the edges of a > corresponding binary radix tree - an edge connecting a parent with a prefix > of length Dparent * > *to a child with a prefix of length Dchild represents all subprefixes of > length Dparent+1, ....Dchild. * > *Out of these, Floor( Dchild/3 ) - Floor( Dparent/3 ) are divisible by 3. * > *We evaluate these counts during radix tree construction, and then perform > a parallel prefix sum to allocate the octree nodes. * > *The parents of the octree nodes can then be found by looking at the > immediate ancestors of each radix tree node.* > I am trying to decipher the algorithm for final 2 steps but it is proving a bit difficult as I am not an algorithm expert. If anyone is willing to spend time to with me to solve this problem, I will be more than happy. ;) Thanks N. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
