Here is brief list of background concepts needed to understand the problem - Space Filling Curves (SFC) : Morton codes are one particular kind of SFC implmeentation. Gray code and Hilber code are two more types of SFCs that can be generated - Binary tree and traversal - Prefix trees - Basic sorting - Conceptual understanding of Octree/Quadtree
Regards N. On Tuesday, 10 June 2014 16:10:42 UTC+5:30, nurabha wrote: > > 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].
