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 algogeeks+unsubscr...@googlegroups.com.
