Patent ID: 8717357

Claim:
A machine-implemented method of producing an acceleration structure for use in rendering from a three dimensional (3-D) scene, comprising: subdividing a 3-D scene into a plurality of volumetric portions, wherein subsets of the volumetric portions have one or more of different sizes and different forms, and each volumetric portion is addressable using a respective unique address; processing each primitive of a stream of primitives located in the 3-D scene, comprising characterizing the primitive according to one or more criteria; selecting a set of volumetric portions that collectively bound the primitive, the selecting using an output of the characterizing; storing identifying data for the primitive in respective locations of a cache for each volumetric portion of the selected set of volumetric portions; selecting a cache location to evict, responsive to a cache eviction decision made during the processing; and generating an element of an acceleration structure according to the contents of the evicted cache location.