Splitting bounding volumes of primitives

Patent metadata

Field	Value
Publication number	US-9547932-B2
Application number	US-201314035899-A
Country	US
Kind code	B2
Filing date	Sep 24, 2013
Priority date	Jun 10, 2013
Publication date	Jan 17, 2017
Grant date	Jan 17, 2017

Abstract

A system, method, and computer program product are provided for splitting primitives. A plurality of primitives is received for a scene and a pre-determined plane that intersects the scene is identified. Bounding volumes of the plurality of primitives that are intersected by the pre-determined plane are split, where a bounding volume that encloses each intersected primitive of the plurality of primitives is split into a first bounding volume and a second bounding volume at an intersection of the bounding volume and the pre-determined plane.

First claim

What is claimed is:

1. A method, comprising:
receiving, by a parallel processing unit that is configured to execute threads in a group of threads in parallel, a plurality of primitives comprising a scene;
identifying a pre-determined plane that intersects the scene;
splitting, in parallel, bounding volumes of the plurality of primitives that are intersected by the pre-determined plane, wherein a bounding volume that encloses each intersected primitive of the plurality of primitives is split into a first bounding volume and a second bounding volume at an intersection of the bounding volume and the pre-determined plane and a first node in a hierarchical tree data structure stored in a memory corresponds to the first bounding volume;
calculating a priority value for each primitive in the plurality of primitives that indicates a relative importance for splitting the primitive compared with other primitives in the scene;
iteratively computing a scaling factor by bisecting a range bounding the scaling factor while ensuring that the scaling factor corresponds to a total number of splits for the scene that does not exceed a maximum number of splits;
Computing a number of splits allocated for each primitive in the plurality of primitives based on the priority value computed for the primitive and the scaling factor.

2. The method of claim 1 , wherein the pre-determined plane is a spatial median plane.

3. The method of claim 1 , wherein the bounding volume is an axis-aligned bounding box.

4. The method of claim 1 , wherein the at least one primitive is a triangle.

5. The method of claim 1 , further comprising:
determining that the bounding volume is intersected by a second pre-determined plane; and
determining that the pre-determined plane is dominant relative to the second pre-determined plane.

6. The method of claim 1 , wherein the pre-determined plane is included in a set of at least two planes that each intersect the scene.

7. The method of claim 6 , wherein the set of planes correspond to spatial median planes used to generate a bounding volume hierarchy (BVH) tree structure for the plurality of primitives.

8. The method of claim 1 , further comprising determining a fixed maximum number of splits to perform on the plurality of primitives.

9. The method of claim 8 , wherein the fixed maximum number of splits corresponds to an amount of memory allocated to store data associated with split bounding volumes.

10. The method of claim 1 , distributing a total number of splits among the plurality of primitives.

11. The method of claim 1 , further comprising:
determining a remaining split allocation for the at least one primitive; and
distributing the remaining split allocation among the first bounding volume and the second bounding volume.

12. The method of claim 1 , further comprising constructing an initial hierarchical tree data structure having the first node corresponding to the first bounding volume and a second node corresponding to the second bounding volume.

13. The method of claim 1 , wherein the splitting is performed in parallel by assigning each intersected primitives of the plurality of primitives within a treelet to a separate thread in a group of threads that are executed in parallel.

14. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to split a bounding volume of at least one primitive, comprising:
receiving, by a parallel processing unit that is configured to execute threads in a group of threads in parallel, a plurality of primitives comprising a scene;
identifying a pre-determined plane that intersects the scene;
splitting, in parallel, bounding volumes of the plurality of primitives that are intersected by the pre-determined plane, wherein a bounding volume that encloses each intersected primitive of the plurality of primitives is split into a first bounding volume and a second bounding volume at an intersection of the bounding volume and the pre-determined plane and a first node in a hierarchical tree data structure stored in a memory corresponds to the first bounding volume;
calculating a priority value for each primitive in the plurality of primitives that indicates a relative importance for splitting the primitive compared with other primitives in the scene;
iteratively computing a scaling factor by bisecting a range bounding the scaling factor while ensuring that the scaling factor corresponds to a total number of splits for the scene that does not exceed a maximum number of splits;
Computing a number of splits allocated for each primitive in the plurality of primitives based on the priority value computed for the primitive and the scaling factor.

15. The non-transitory computer-readable storage medium of claim 14 , further comprising constructing an initial hierarchical tree data structure having the first node corresponding to the first bounding volume and a second node corresponding to the second bounding volume.

16. The non-transitory computer-readable storage medium of claim 14 , wherein the splitting is performed in parallel by assigning each intersected primitives of the plurality of primitives within a treelet to a separate thread in a group of threads that are executed in parallel.

17. A system comprising: a memory storing a plurality of primitives for a three-dimensional scene; and a parallel processing unit that is coupled to the memory and executes threads in a group of threads in parallel and is configured to:
receive the plurality of primitives comprising a scene;
identify a pre-determined plane that intersects the scene;
split, in parallel, bounding volumes of the plurality of primitives that are intersected by the pre-determined plane, wherein a bounding volume that encloses each intersected primitive of the plurality of primitives is split into a first bounding volume and a second bounding volume at an intersection of the bounding volume and the pre-determined plane and a first node in a hierarchical tree data structure stored in a memory corresponds to the first bounding volume;
calculate a priority value for each primitive in the plurality of primitives that indicates a relative importance for splitting the primitive compared with other primitives in the scene;
iteratively computing a scaling factor by bisecting a range bounding the scaling factor while ensuring that the scaling factor corresponds to a total number of splits for the scene that does not exceed a maximum number of splits;
Computing a number of splits allocated for each primitive in the plurality of primitives based on the priority value computed for the primitive and the scaling factor.

18. The system of claim 17 , wherein the splitting is performed in parallel by assigning each intersected primitives of the plurality of primitives within a treelet to a separate thread in a group of threads that are executed in parallel.

Assignees

• Nvidia Corp

Inventors

• Karras Tero Tapani
• Aila Timo Oskari

Classifications

• G06T15/06 Primary

  Ray-tracing · CPC title