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