Beam tracing

Patent metadata

Field	Value
Publication number	US-9569559-B2
Application number	US-201514662090-A
Country	US
Kind code	B2
Filing date	Mar 18, 2015
Priority date	Sep 4, 2014
Publication date	Feb 14, 2017
Grant date	Feb 14, 2017

Abstract

An apparatus, computer readable medium, and method are disclosed for performing an intersection query between a query beam and a target bounding volume. The target bounding volume may comprise an axis-aligned bounding box (AABB) associated with a bounding volume hierarchy (BVH) tree. An intersection query comprising beam information associated with the query beam and slab boundary information for a first dimension of a target bounding volume is received. Intersection parameter values are calculated for the first dimension based on the beam information and the slab boundary information and a slab intersection case is determined for the first dimension based on the beam information. A parametric variable range for the first dimension is assigned based on the slab intersection case and the intersection parameter values and it is determined whether the query beam intersects the target bounding volume based on at least the parametric variable range for the first dimension.

First claim

What is claimed is:

1. A method, comprising:
receiving, by a computer system, an intersection query comprising beam information associated with a query beam, the query beam comprising a plurality of query rays;
receiving, by the computer system, slab boundary information for a first dimension of a target bounding volume, the target bounding volume being a bounding box for a target object, and the slab boundary information for the first dimension of the target bounding volume indicating a position range of the target bounding volume along the first dimension;
calculating, by the computer system, intersection parameter values for the first dimension based on the beam information and the slab boundary information, the intersection parameter values calculated according to intersections of the query rays within the position range of the target bounding volume along the first dimension;

determining, by the computer system, a slab intersection case for the first dimension based on the beam information, the slab intersection case being a combination of at least two of the intersection parameter values calculated for the first dimension;
assigning, by the computer system, a parametric variable range for the first dimension based on the slab intersection case;
determining, by the system, whether the query beam intersects the target bounding volume using the parametric variable range for the first dimension;
responsive to determining that the query beam intersects the target bounding volume, performing, by the computer system, additional intersection analysis between each ray in the plurality of query rays and the target object; and
generating, by the computer system, an image of the target object from true intersections determined from the additional intersection analysis.

2. The method of claim 1 , wherein the slab boundary information is specified within a three-dimensional space, and the first dimension corresponds to a coordinate axis of the three-dimensional space.

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

4. The method of claim 1 , wherein the beam information comprises a first ray and a second ray specified within a three-dimensional space that includes the first dimension, the first ray associated with a first direction vector and a first origin, and the second ray associated with a second direction vector and a second origin.

5. The method of claim 4 , wherein determining the slab intersection case comprises comparing the first direction vector with zero in the first dimension and comparing the second direction vector with zero in the first dimension.

6. The method of claim 4 , wherein the slab boundary information comprises a slab minimum value and a slab maximum value for the first dimension.

7. The method of claim 4 , wherein calculating intersection parameter values comprises calculating a first intersection parameter value by performing a first multiplication between a first inverse component of the first direction vector and a first distance, and calculating a second intersection parameter value by performing a second multiplication between a second inverse component of the second direction vector and a second distance.

8. The method of claim 1 , wherein assigning a parametric range comprises assigning a minimum range value to a product of a first inverse component of a first direction vector of the query beam and a first distance between a first origin of the query beam and a slab minimum value associated with the slab boundary information, and assigning a maximum range value to a product of a second inverse component of a second direction vector of the query beam and a second distance between a second origin of the query beam and a slab maximum value associated with the slab boundary information.

9. The method of claim 1 , wherein the intersection query comprises an additional parametric variable range and determining whether the query beam intersects the target bounding volume comprises:
assigning an overall parametric variable range bounded by a first value and a second value by:
selecting the first value as a maximum value from a first set of values comprising minimum values of the parametric variable ranges for the intersection query and at least the first dimension;
selecting the second value as a minimum value from a second set of values comprising maximum values of the parametric variable ranges for the intersection query and at least the first dimension; and

determining that the query beam intersects the target bounding volume if the first value is less than or equal to the second value.

10. The method of claim 1 , wherein the query beam is generated according to a dilation operator applied to a query ray.

11. The method of claim 1 , wherein the plurality of query rays include a first query ray and a second query ray, and wherein the beam information includes a first query origin and a first query direction for the first query ray, and a second query origin and a second query direction for the second query ray.

12. The method of claim 11 , wherein the bounding box for the target object is defined by bounding planes in each dimension of coordinate space occupied by the target object, and wherein the position range of the target bounding volume along the first dimension includes a minimum position of the target bounding volume along the first dimension and a maximum position of the target bounding volume along the first dimension.

13. The method of claim 12 , wherein the intersection parameters values include:
first intersection parameter values calculated, respectively, according to an intersection between the minimum position of the target bounding volume and each of the first query ray and the second query ray, and
second intersection parameter values calculated, respectively, according to an intersection between the maximum position of the target bounding volume and each of the first query ray and the second query ray.

14. The method of claim 13 , wherein the slab intersection case is a combination of:
at least one value of the first intersection parameter values, and
at least one value of the second intersection parameter values.

15. A system, comprising:
a memory configured to store a target bounding volume, the target bounding volume being a bounding box for a target object; and
a processing unit coupled to the memory and configured to:
receive an intersection query comprising beam information associated with a query beam, the query beam comprising a plurality of query rays;
receive slab boundary information for a first dimension of the target bounding volume, the slab boundary information for the first dimension of the target bounding volume indicating a position range of the target bounding volume along the first dimension;
calculate intersection parameter values for the first dimension based on the beam information and the slab boundary information, the intersection parameter values calculated according to intersections of the query rays within the position range of the target bounding volume along the first dimension;
determine a slab intersection case for the first dimension based on the beam information, the slab intersection case being a combination of at least two of the intersection parameter values calculated for the first dimension;
assign a parametric variable range for the first dimension based on the slab intersection case;
determine whether the query beam intersects the target bounding volume using the parametric variable range for the first dimension;
responsive to determining that the query beam int

Assignees

• Nvidia Corp

Inventors

• Karras Tero Tapani
• Aila Timo Oskari
• Laine Samuli Matias
• Lindholm John Erik

Classifications

• G06T9/001

  Model-based coding, e.g. wire frame · CPC title

• G06T9/40

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

• G06T17/10

  Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes · CPC title

• G06T15/06

  Ray-tracing · CPC title

• G06T15/08

  Volume rendering · CPC title