Back to results
US 8,947,447 B1Granted
Computer hardware architecture and data structures for ray binning to support incoherent ray traversal
AssigneeRaycast Systems, Inc.
InventorAlvin D. Zimmerman
Life of this patent
Estimating the term…
Abstract
A new hardware architecture defines an indexing and encoding method for accelerating incoherent ray traversal. Accelerating multiple ray traversal may be accomplished by organizing the rays for minimal movement of data, hiding latency due to external memory access, and performing adaptive binning. Rays may be binned into coarse grain and fine grain spatial bins, independent of direction.
Claims20
A system for ray traversal comprising:
- a first memory configured to receive ray data for a plurality of rays, each ray intersecting a given level 1 cell in a scene that is partitioned into a plurality of level 1 cells, each level 1 cell in the scene being partitioned into a plurality of level 2 cells, each level 2 cell of the scene being partitioned into a plurality of level 3 cells;
- a first array of counters;
- first control circuitry that updates one or more of the first counters each time the 8 first memory receives ray data for a ray, the one or more first counters being updated in accordance with a level 3 cell address that the ray is associated with;
- a second memory;
- a second array of counters;
- second control circuitry that stores ray data, from the first memory, into the second memory at locations determined using the first counters, wherein the second control circuitry further updates one or more of the second counters each time the second memory receives ray data for a ray from the first memory, the one or more second counters being updated in accordance with a level 2 cell address that the given ray is associated with;
- a third memory;
- and
- third control circuitry that stores ray data, from the second memory, into the third memory at locations determined using the second counters.
6 more elements
A system for ray traversal comprising:
- a first memory;
- a second memory;
- a third memory;
- a fourth memory;
- and
- control circuitry operative to:
- store a plurality of ray data into the first memory;
- generate addresses of the second memory using first criteria contained in the ray data stored in the first memory and store the addresses of the second memory into the fourth memory;
- store ray data from the first memory into locations in the second memory using the addresses stored in the fourth memory, wherein the ray data in the second memory are sorted according to the first criteria;
- generate addresses of the third memory using second criteria contained in the ray data stored in the second memory and store the addresses of the third memory into the fourth memory;
- and
- store ray data from the second memory into the third memory using the addresses of the fourth memory.
9 more elements
A method for ray traversal comprising:
- storing in a first memory ray data for a plurality of rays, each ray intersecting a given level 1 cell in a scene that is partitioned into a plurality of level 1 cells, each level cell in the scene being partitioned into a plurality of level 2 cells, each level 2 cell of the scene being partitioned into a plurality of level 3 cells;
- generating first addressing information, each time ray data for a ray is stored in the first memory, using a level 3 cell address associated with the ray;
- storing ray data, from the first memory, into a second memory at locations determined using the first addressing information;
- generating second addressing information each time ray data for a ray is stored in the second memory, using a level 2 cell address associated with the ray;
- and
- storing ray data, from the second memory, into a third memory at locations
- determined using the second addressing information.
4 more elements
Dependencies are inferred from the claim text.