Patent ID: 8842117

Claim:
A method in a grid traversal unit (GTU) of ray traversal comprising: receiving, by digital circuitry comprising the GTU, a ray for traversal through a scene that is represented by an N-level hierarchy of cells, wherein cells at a level i (“level i cells”) comprise a plurality of level (i+1) cells; identifying, by the digital circuitry, dirty cells intersected by the ray at each level in the N-level hierarchy of cells, including identifying a first plurality of level N dirty cells by traversing a level (N−1) dirty cell at level N; (i) identifying, by the digital circuitry, a group of level N dirty cells from the first plurality of level N dirty cells; (ii) generating, by the digital circuitry, lookahead data indicative of whether or not each level N dirty cell in the group contains a level (N+1) dirty cell that is intersected by the ray (contains “a hit”) by concurrently performing a level (N+1) traversal of the ray through each of the level N dirty cells in the group, the lookahead data comprising data representative of partitioning planes that define each level N dirty cell; (iii) using, by the digital circuitry, the lookahead data to identify a candidate level N dirty cell in the group that contains a hit and testing the candidate level N dirty cell for intersection with an object, including updating the lookahead data to indicate that the candidate level N dirty cell has been tested; (iv) identifying, by the digital circuitry, a second plurality of level N dirty cells by traversing the level (N−1) dirty cell at level N including using the updated lookahead data to exclude from the second plurality of level N dirty cells previously tested level N dirty cells; and repeating, by the digital circuitry, (i) through (iv) using the second plurality of level N dirty cells in place of the first plurality of level N dirty cells.