# US 12,118,643 B2 · Hardware-accelerated nearest neighbor queries for arbitrary data primitives > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,118,643 B2 - Document ID: US12118643B2 - Status: Granted - Kind: B2 - Application number: 17/560,845 - Filed: 2021-12-23 - Published: 2023-06-29 - Granted: 2024-10-15 - Earliest claimed: 2021-12-23 - Assignees: NVIDIA Corporation - Applicants: NVIDIA Corporation - Inventors: Nathan Vollmer Morrical - Web page: https://patentgrep.com/patent/US12118643B2 ## CPC - G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining - G06T 15/06: Ray-tracing - G06F 9/3877: {using a secondary processor, e.g. coprocessor (peripheral processor G06F13/12)} - G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues} - G06F 9/5044: {considering hardware capabilities} - G06F 9/505: {considering the load} - G06F 9/5072: {Grid computing} - G06T 15/10: Geometric effects - G06F 2209/5017: Task decomposition - G06F 2209/505: Clust - G06T 2210/12: Bounding box - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) The method of claim 1, wherein distance to a primitive is determined using an axis-aligned bounding box (“AABB”). ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 1) 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. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 1) 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. ### Claim 8 (depends on 1) 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. ### Claim 9 (depends on 1) 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. ### Claim 10 (depends on 1) 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. ### Claim 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. ### Claim 12 (depends on 11) 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. ### Claim 13 (depends on 11) The processor of claim 11, wherein distance to a primitive is determined using an axis-aligned bounding box (“AABB”). ### Claim 14 (depends on 11) 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. ### Claim 15 (depends on 11) 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. ### Claim 16 (depends on 11) 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. ### Claim 17 (depends on 11) 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. ### Claim 18 (depends on 11) 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. ### Claim 19 (depends on 11) 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. ### Claim 20 (depends on 11) 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. ### Claim 21 (depends on 11) 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. ### Claim 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. ### Claim 23 (depends on 22) 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. ### Claim 24 (depends on 22) The non-transitory machine-readable medium of claim 22, wherein distance to a primitive is determined using an axis-aligned bounding box (“AABB”). ### Claim 25 (depends on 22) 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. ### Claim 26 (depends on 22) 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. ### Claim 27 (depends on 22) 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 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. ### Claim 28 (depends on 22) The non-transitory machine-readable medium of claim 22, wherein performance of the set of instructions to adjust the number of the one or more primitives further comprise instructions that cause the one or more processors 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. ### Claim 29 (depends on 22) The non-transitory machine-readable medium of claim 22, wherein performance of the set of instructions to adjust the number of the one or more primitives further comprise instructions that cause the one or more processors 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. ### Claim 30 (depends on 22) 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 more processors to further determine the result by analyzing a set of primitives that does not include the one or more primitives. ### Claim 31 (depends on 22) 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 more processors to further: 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.