Hardware-accelerated nearest neighbor queries for arbitrary data primitives

Patent metadata

Field	Value
Publication number	US-2023206378-A1
Application number	US-202117560845-A
Country	US
Kind code	A1
Filing date	Dec 23, 2021
Priority date	Dec 23, 2021
Publication date	Jun 29, 2023
Grant date	—

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 that are nearest to 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 the size of each of the one or more bounding boxes.

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 increasing 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.

7 . The method of claim 1 , further comprising 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 , further comprising 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 that are nearest to 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 the size of each of the one or more bounding boxes.

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 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 that are nearest to 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 the size of each of the one or more bounding boxes.

23 . The machine-readable medium of claim 22 , 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.

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

25 . The 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 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 machine-readable medium of claim 22 , wherein performance of the set of instructions by the one or more processors, causes the one or more processors to further:
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.

28 . The machine-readable medium of claim 22 , wherein performance of the set of instructions by the one or more processors, causes the one or more processors to further increase the size of the one or more

Assignees

• Nvidia Corp

Inventors

• Morrical Nathan Vollmer

Classifications

• G06T1/20 Primary

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

• G06F9/3877

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

• G06F9/5044

  considering hardware capabilities · CPC title

• G06T15/10

  Geometric effects · CPC title

• G06T2210/12

  Bounding box · CPC title