Hardware-accelerated nearest neighbor queries for arbitrary data primitives

Patent metadata

Field	Value
Publication number	US-12118643-B2
Application number	US-202117560845-A
Country	US
Kind code	B2
Filing date	Dec 23, 2021
Priority date	Dec 23, 2021
Publication date	Oct 15, 2024
Grant date	Oct 15, 2024

Abstract

Apparatuses, systems, and techniques to perform a K-nearest-neighbor query. In at least one embodiment, a set of bounding boxes corresponding to a set of primitives is generated that allows the query to be solved using light transport simulation acceleration features of a GPU.

First claim

What is claimed is:

1. A method comprising:
receiving a request to identify, from a set of one or more primitives, a specified number of primitives based, at least in part, on performing a nearest neighbor query using a point of interest;
generating a bounding box around each of the one or more primitives; and
adjusting a number of the one or more primitives to be excluded from a result set of the request by adjusting a size of each of the one or more bounding boxes to change a number of the one or more bounding boxes that comprise the point of interest.

2. The method of claim 1 , wherein the one or more bounding boxes are animated by expanding a bounding box over a time parameter using a hardware-accelerated processing core of a graphical processing unit.

3. The method of claim 1 , wherein distance to a primitive is determined using an axis-aligned bounding box (“AABB”).

4. The method of claim 1 , wherein at least one primitive of the set of one or more primitives is represented by a line segment and a corresponding bounding box is a rectangle that encompasses one or more points equidistant from individual endpoints of the line segment.

5. The method of claim 1 , wherein at least one primitive of the set of one or more primitives is a represented by a polygon and a corresponding bounding box is a rectangle that encompasses points equidistant from individual vertexes of the polygon.

6. The method of claim 1 , further comprising determining the number of the one or more bounding boxes that comprise the point of interest is less than a specified number.

7. The method of claim 1 , wherein adjusting the number of the one or more primitives further comprises increasing the size of the one or more bounding boxes as a result of determining that a number of primitives within a distance of the point of interest is less than the specified number.

8. The method of claim 1 , wherein adjusting the number of the one or more primitives further comprises decreasing the size of the one or more bounding boxes as a result of determining that a number of the one or more bounding boxes that enclose the point of interest is greater than a threshold value, the threshold value being determined as a function of the specified number.

9. The method of claim 1 , further comprising determining the result by analyzing a set of primitives that does not include the one or more primitives.

10. The method of claim 1 , further comprising:
determining a distance from the point of interest to a primitive of the set of one or more primitives;
determining whether the point of interest is in the result based at least in part on the distance; and
storing a value representing the distance in association with the primitive.

11. A processor comprising one or more processing units to:
receive a request to identify, from a set of one or more primitives, a specified number of primitives as a result of performing one or more nearest neighbor queries using a point of interest;
generate a bounding box around each of the one or more primitives; and
adjust a number of the one or more primitives to be excluded from a result set of the request by adjusting a size of each of the one or more bounding boxes based, at least in part, on modifying a number of one or more bounding boxes that include the point of interest.

12. The processor of claim 11 , wherein the one or more bounding boxes are animated by expanding a bounding box over a time parameter using a ray tracing core of a graphical processing unit.

13. The processor of claim 11 , wherein distance to a primitive is determined using an axis-aligned bounding box (“AABB”).

14. The processor of claim 11 , wherein at least one primitive of the set of one or more primitives is represented by a line segment and a corresponding bounding box is a rectangle that encompasses one or more points equidistant from individual endpoints of the line segment.

15. The processor of claim 11 , wherein at least one primitive of the set of one or more primitives is a represented by a polygon and a corresponding bounding box is a rectangle that encompasses one or more points equidistant from individual vertexes of the polygon.

16. The processor of claim 11 , wherein the processor is further to increase the size of the one or more bounding boxes as a result of determining that a number of the one or more bounding boxes that enclose the point of interest is less than the specified number.

17. The processor of claim 11 , wherein the processor is further to increase the size of the one or more bounding boxes as a result of determining that a number of primitives within a distance of the point of interest is less than the specified number.

18. The processor of claim 11 , wherein the processor is further to decrease the size of the one or more bounding boxes as a result of determining that a number of the one or more bounding boxes that enclose the point of interest is greater than a threshold value, the threshold value being determined as a function of the specified number.

19. The processor of claim 11 , wherein the processor is further to determine the result by analyzing a set of primitives that does not include the one or more primitives.

20. The processor of claim 11 , wherein the processor is further to:
determine a distance from the point of interest to a primitive;
determine whether the point of interest is in the result based at least in part on the distance; and
store a value representing the distance in association with the primitive.

21. The processor of claim 11 , wherein the one or more bounding boxes are animated by expanding a bounding box over a time parameter using a light transport simulation core of a graphical processing unit.

22. A non-transitory machine-readable medium having stored thereon a set of instructions, which if performed by one or more processors, cause the one or more processors to:
receive a request to identify, from a set of one or more primitives, a specified number of primitives based, at least in part, on performing a set of nearest neighbor queries using a point of interest;
generate a bounding box around each of the one or more primitives; and
adjust a number of the one or more primitives to be excluded from a result set of the request by adjusting a size of each of the one or more bounding boxes to adjust a number of the one or more boxes that include the point of interest.

23. The non-transitory machine-readable medium of claim 22 , wherein the one or more bounding boxes are modified over a time parameter using a light transport simulation core of a graphical processing unit.

24. The non-transitory machine-readable medium of claim 22 , wherein distance to a primitive is determined using an axis-aligned bounding box (“AABB”).

25. The non-transitory machine-readable medium of claim 22 , wherein a primitive is represented by a line segment and a corresponding bounding box is a rectangle that encompasses points equidistant from individual endpoints of the line segment.

26. The non-transitory machine-readable medium of claim 22 , wherein a primitive is a represented by a polygon and a corresponding bounding box is a rectangle that encompasses points equidistant from individual vertexes of the polygon.

27. The non-transitory machine-readable medium of claim 22 , wherein performance of the set of instructions by the one or more processors, causes the one or mo

Assignees

• Nvidia Corp

Inventors

• Morrical Nathan Vollmer

Classifications

• G06T2210/12

  Bounding box · CPC title

• G06T15/10

  Geometric effects · CPC title

• G06F9/3877

  using a secondary processor, e.g. coprocessor (peripheral processor G06F13/12) · CPC title

• G06F9/5044

  considering hardware capabilities · CPC title

• G06F2209/505

  Clust · CPC title