Fully parallel construction of k-d trees, octrees, and quadtrees in a graphics processing unit

Patent metadata

Field	Value
Publication number	US-9396512-B2
Application number	US-201313791738-A
Country	US
Kind code	B2
Filing date	Mar 8, 2013
Priority date	Mar 9, 2012
Publication date	Jul 19, 2016
Grant date	Jul 19, 2016

Abstract

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.

First claim

What is claimed:

1. A non-transitory computer-readable medium having computer-executable instructions for causing a computer system to perform a method comprising:
assigning a Morton code for each of a plurality of primitives, wherein said plurality of primitives correspond to leaf nodes of a binary radix tree;
sorting said plurality of Morton codes;
building said binary radix tree requiring at most a linear amount of temporary storage with respect to a total number of leaf nodes;
building an internal node of said binary radix tree in parallel with one or more of its ancestor nodes; and
for each internal node of said binary radix tree, partitioning said plurality of Morton codes into categories based on a corresponding highest differing bit to build a k-d tree over said plurality of primitives, wherein a prefix of an internal node having a length δ corresponds to a plane perpendicular to the dth main axis, wherein d=δ mod D, and D is equal to a number of dimensions, and wherein said partitioning comprises:
classifying a first category of Morton codes on a first side of a corresponding axis-aligned split plane in three dimensions (3D); and
classifying a second category of Morton codes on a second side of said corresponding axis-aligned split plane.

2. The non-transitory computer-readable medium of claim 1 , wherein said axis-aligned split plane splits a corresponding space in half.

3. The non-transitory computer-readable medium of claim 1 , wherein said plurality of primitives comprises a plurality of points.

4. The non-transitory computer-readable medium of claim 3 , wherein said assigning a Morton code for each of a plurality of primitives in said method further comprises:
assigning a first Morton code for a first primitive according to a centroid point of a bounding volume encompassing said primitive.

5. A non-transitory computer-readable medium having computer-executable instructions for causing a computer system to perform a method comprising:
assigning a Morton code for each of a plurality of primitives, wherein said plurality of primitives correspond to leaf nodes of a binary radix tree;
sorting said plurality of Morton codes;
building said binary radix tree requiring at most a linear amount of temporary storage with respect to a total number of leaf nodes;
building an internal node of said binary radix tree in parallel with one or more of its ancestor nodes;
determining a number of octree nodes for each node of said binary radix tree by determining, for each edge of said binary radix tree, a number of bit triplet boundaries crossed when moving from a parent node to a child node in said binary radix tree to determine a number of octree nodes corresponding to an edge;
determining a total number of octree nodes;
allocating said total number of octree nodes; and
outputting each of said total number of octree nodes.

6. The non-transitory computer-readable medium of claim 5 , wherein said allocating said total number of octree nodes in said method comprises:
performing a parallel prefix sum.

7. The non-transitory computer-readable medium of claim 5 , wherein said outputting each of said total number of octree nodes in said method comprises:
determining a parent of an octree node based on its immediate ancestors in said binary radix tree.

8. The non-transitory computer-readable medium of claim 5 , wherein said plurality of primitives comprises a plurality of points.

9. The non-transitory computer-readable medium of claim 8 , wherein said assigning a Morton code for each of a plurality of primitives in said method further comprises:
assigning a first Morton code for a first primitive according to a centroid point of a bounding volume encompassing said primitive.

10. The non-transitory computer-readable medium of claim 5 , wherein said sorting said plurality of Morton codes in said method further comprises:
identifying duplicate Morton codes; and
removing said duplicate Morton codes.

11. A computer system comprising:
a processor; and
memory coupled to said processor and having stored therein instructions that, if executed by said compute system, cause said computer system to execute a method comprising:
assigning a Morton code for each of a plurality of primitives, wherein said plurality of primitives correspond to leaf nodes of a binary radix tree;
sorting said plurality of Morton codes;
building said binary radix tree requiring at most a linear amount of temporary storage with respect to a total number of leaf nodes;
building an internal node of said binary radix tree in parallel with one or more of its ancestor nodes;
determining a number of octree nodes for each node of said binary radix tree by determining, for each edge of said binary radix tree, a number of bit triplet boundaries crossed when moving from a parent node to a child node in said binary radix tree to determine a number of octree nodes corresponding to an edge;
determining a total number of octree nodes;
allocating said total number of octree nodes; and
outputting each of said total number of octree nodes.

12. The computer system of claim 11 , wherein said allocating said total number of octree nodes in said method comprises:
performing a parallel prefix sum.

13. The computer system of claim 11 , wherein said outputting each of said total number of octree nodes in said method comprises:
determining a parent of an octree node based on its immediate ancestor in said binary radix tree.

14. The computer system of claim 11 , wherein said plurality of primitives comprises a plurality of points.

15. The computer system of claim 14 , wherein said assigning a Morton code for each of a plurality of primitives in said method further comprises:
assigning a first Morton code for a first primitive according to a centroid point of a bounding volume encompassing said primitive.

16. The computer system of claim 11 , wherein said sorting said plurality of Morton codes in said method further comprises:
identifying duplicate Morton codes; and
removing said duplicate Morton codes.

Assignees

• Nvidia Corp

Inventors

• Karras Tero

Classifications

• G06T17/005 Primary

  Tree description, e.g. octree, quadtree · CPC title

• G06T2210/52

  Parallel processing · CPC title

• G06T1/20 Primary

  Processor architectures; Processor configuration, e.g. pipelining · CPC title