首页>
外国专利>
FULLY PARALLEL CONSTRUCTION OF K-D TREES, OCTREES, AND QUADTREES IN A GRAPHICS PROCESSING UNIT
FULLY PARALLEL CONSTRUCTION OF K-D TREES, OCTREES, AND QUADTREES IN A GRAPHICS PROCESSING UNIT
展开▼
机译:图形处理单元中的K-D树,八叉树和四叉树的完全并行构造
展开▼
页面导航
摘要
著录项
相似文献
摘要
A non-transitory computer-readable storage medium having computer-executable instructions for causing a computer system to perform a method for constructing k-d trees, octrees, and quadtrees from radix trees is disclosed. The method includes assigning a Morton code for each of a plurality of primitives corresponding to leaf nodes of a binary radix tree, and sorting the plurality of Morton codes. The method includes building a radix tree requiring at most a linear amount of temporary storage with respect to the leaf nodes, wherein an internal node is built in parallel with one or more of its ancestor nodes. The method includes, partitioning the plurality of Morton codes for each node of the radix tree into categories based on a corresponding highest differing bit to build a k-d tree. A number of octree or quadtree nodes is determined for each node of the k-d tree. A total number of nodes in the octree or quadtree is determined, allocated and output.
展开▼