CN105957134A - Systems and methods for 3-d scene acceleration structure creation and updating - Google Patents

Abstract

Systems and methods for generating acceleration structures propose subdividing a 3-D scene into multiple volume portions, the volume portions having different sizes, each volume portion can be addressed using a multi-part address, the multi-part The addresses indicate the location and relative size of each volume portion. A stream of primitives is processed by characterizing each primitive according to one or more criteria, selecting a relative size of volume portions for enclosing the primitive, and finding the , a collection of volume parts of this relative size. A primitive ID is stored in each location of a cache associated with each volume part in the set of volume parts. In response to each cache eviction decision made during the process, a cache location is selected for eviction. In response to the evicted cache location, an element of an acceleration structure is generated based on the contents of the evicted cache location.

Description

Systems and methods for accelerated structure creation and updating of 3-D scenes

This application is a divisional application of an invention patent application with an international filing date of August 4, 2012, a national application number of 201280037833.4, and a title of “System and Method for Creating and Updating 3-D Scene Acceleration Structures”.

Cross References to Related Applications

This application claims priority to U.S. Provisional Application No. 61/515,801, filed August 5, 2011, entitled "Systems and methods of Acceleration Structure Creation," which for all purposes is adopted by The citations are hereby incorporated in their entirety.

technical field

One aspect of this subject matter relates to the creation of a scene acceleration structure for a 3-D scene to be rendered and, in a more specific aspect, to the creation and updating of such an acceleration structure for use with ray tracing for processing images from 3-D A 2-D image of a 3D scene description is rendered.

Background technique

Rendering realistic 2-D images from 3-D scene descriptions with ray tracing is well known in the art of computer graphics. Ray tracing typically involves obtaining a scene description composed of various geometric shapes that describe the surfaces of structures in the scene. These geometries are often referred to as primitives if they are shapes of a shape type that can be processed using a rendering system; otherwise, these geometries are typically processed to generate primitives based on these geometries. For example, patches can be processed to generate triangle primitives.

A primitive may be associated with textures and other information that instructs the computer how the quality of the primitive should affect light hitting the primitive. Ray tracing can faithfully render complex lighting, light transmission, reflection, refraction, etc., because ray tracing can model the physical behavior of light interacting with the elements of the scene.

A common operation in ray tracing is to determine the intersection between a ray and one or more primitives in the scene. An example of a primitive used in defining objects for a ray-tracing system is a triangle composed of a collection of vertices in 3-D scene space; this specification continues with this familiar example, but the use of triangle primitives It is for clarity, not limitation.

A ray definition may consist of an origin, and a direction and the current clipping distance along the ray, which for a ray may be denoted as "t". The current clipping distance identifies the current closest intersection detected for the ray, or in the case of no detected intersection, the ray's intersection has been tested at a distance beyond this distance and no intersection was found. When a ray completes the intersection test, the most recent detected intersection may be returned and information for that intersection determined, such as the identity of the primitive that the ray intersected.

Naively, these results can be determined for a given ray by iteratively testing every triangle in the scene to identify the closest intersecting triangle. While this naive approach works acceptably for scenes with a small number of triangles, it is intractable for complex scenes and for commercial products where, for each Frame-wise, the intersection of millions or even tens or hundreds of millions of rays with millions of triangles may need to be tested.

To speed up this intersection test, a 3-D spatial acceleration structure is used. These acceleration structures typically work by subdividing the 3D space into a number of different regions, where each of these regions can bound multiple primitives. Each of these regions can then be first tested for intersection in order to determine whether primitives in that region need to be tested individually. In some cases, the acceleration structure may be hierarchical such that multiple tests of different regions within the acceleration structure are performed in order to identify a relatively small set of primitives to be tested for intersection with a given ray.

For a properly assembled acceleration structure, the total number of ray intersection tests should be substantially less than the ray triangle tests already performed between each ray and each triangle in the scene.

Contents of the invention

This overview describes an overview of systems and methods in which various more specific aspects can be practiced or implemented. Some of these specific aspects are then introduced.

In one aspect, a method and apparatus for generating an acceleration structure for a stream of primitives is disclosed. These primitives are located in the 3-D scene. The acceleration structure can be of a selected type, such as a bounding volume hierarchy, or a kD tree. A bounding volume hierarchy can use a selected type of shape, such as a sphere or an axis-aligned bounding box.

To generate the acceleration structure, a hierarchical spatial subdivision is formed for the 3-D scene and includes multiple sets of elements at different levels of granularity. Each streaming primitive is classified to select a level of granularity under which the primitive is to be surrounded by a set of elements from the selected level of granularity. As a specific example, a larger number of smaller spatial subdivisions may be used to collectively enclose a given primitive, or a smaller number of larger spatial subdivisions may be used. A larger number of smaller spatial subdivisions can be within a finer-grained layer of the hierarchical spatial subdivision.

For the selected level of granularity, one or more elements of the spatial subdivision of the hierarchy are identified, which collectively enclose the primitive. The primitive ID is added to the cache entry for each identified element of this hierarchical spatial subdivision. Further primitives can be treated similarly, so that multiple primitives can be collected into a given element of the hierarchical spatial subdivision.

Within each element of the spatial subdivision of the hierarchy, the coverage of those primitives collected within that element is tracked. In one example, coverage is tracked by determining a subvolume within the element that surrounds the primitives (or portions of primitives) with that element. In this aspect, for a given shape of the bounding volume (such as a cube or a sphere), coverage can be viewed as the union of volumes.

Finally, a cache entry for a given element of the hierarchical space subdivision may be evicted from the cache. The coverage of this element is used to form, define or select an element of the acceleration structure that will be used for ray intersection testing. The coverage of the element is also aggregated, wherein the coverages of other elements of the spatial subdivision of the level are aggregated into one larger element of the spatial subdivision of the level. One or more primitives can be directly associated with this larger element (and other elements at that level of granularity), and coverage can be maintained as the union of all these elements. This information can also be cached (identifying these enclosing elements and/or primitives) and this information can eventually be used to define another element of the acceleration structure, and possibly be aggregated into a still larger one of the hierarchical space subdivisions elements, etc., until one or more root nodes for the acceleration structure have been identified.

In a particular aspect, systems and methods according to the present disclosure coalesce primitives and bounding box elements to form an acceleration structure. The elements of the acceleration structure are determined using a workspace subdivision hierarchy, where the elements are easily addressable or identifiable. In one example, elements can be uniquely addressed using a 3-D location and a level of granularity; in other words, each 3-D spatial location is identified by exactly only An element contains. One type of acceleration structure built (shapes and/or interrelationships of elements) can be decoupled from how the workspace subdivision hierarchy is represented.

In another aspect, a method for generating an acceleration structure for use in 3-D rendering includes aligning with one or more axes of a 3-D coordinate system, an absolute size of a primitive, and One or more heuristics of the aspect ratio of the primitive to characterize each primitive in the primitive stream. This method provides a set of elements used to determine a work subdivision structure for the 3-D scene in which the primitive resides. The set of elements may have the same form and/or the same size, may be selected from a plurality of forms, and each form has a plurality of sized subdivision elements. Different primitives in this primitive stream can be surrounded by elements of different shapes and sizes. Each element can also have part (or all) of multiple primitives within a volume defined by the element. Elements based on the work breakdown structure form a leaf node of the acceleration structure. Each leaf node includes a corresponding bounding volume that surrounds the primitive or primitives within the elements of the work subdivision structure for that leaf node. The method also includes recursively condensing the bounding volume to produce larger and larger bounding volumes. In each recursive condensation, an element of the acceleration structure includes a bounding volume which is the union of each bounding volume condensed into that element.

Another aspect involves photon mapping and forming acceleration structures for use when interrogating mapped photons. In one example, a method includes forward tracing rays from light sources in a 3-D scene to identify corresponding locations in 3-D space at which one or more photons are to be deposited. Select a level of granularity within the voxel hierarchy at which to store each photon. The granularity level is selected based on an indication of the photon's effective radius and distance from the light source. In one example, a ray differential is used to represent this effective radius; the hardware or software performing the photon emission can also provide metadata about this effective radius. Each photon is located within a voxel of a granularity level selected based on the effective radius, and the voxel includes an identified location in 3-D space for the photon. The data of the photon relative to the voxel is cached. In response to an indication to evict a cache location, photon data associated with the location is written out and used to generate an element of an acceleration structure representing the written out photon data. In this case, during processing of the stream of photons, the photons may be mixed or otherwise combined into a distribution, function or parametric representation. Other methods of photon mapping include mapping all photons to each level in the hierarchy and then selectively pruning the nodes in the hierarchy to produce nodes with a balanced number of photons, and/or to produce a The degree represents the accelerated structure of the photon. In some examples, photon data is mixed for larger nodes in an acceleration structure and collected for the faces of these nodes or collected at the center of a node, for example.

Another aspect of note is that systems practicing the disclosed aspects can maintain high bandwidth links of streaming data to and from external memory, while the relatively small memory integrated with the processing elements provides room for caching as described above. Thus, primitive and acceleration structure data are streamed, and large amounts of acceleration structure state are not maintained in external memory. In general, systems built according to the present disclosure can produce accelerated structures in a worst-case build time of O(n log n), where n represents the number of primitives processed. In some implementations, primitives can be processed with minimal floating-point computations that allow relatively small fixed-function hardware implementations and thus can be cost-effectively implemented in hardware. Systems and methods can be tuned to form special kinds of accelerating structures.

Description of drawings

For clarity, the figures represent primitives and other volume elements defined by 2-D shapes in 3-D space. However, these elements are still called and treated as elements defined in 3-D space. Those of ordinary skill in the art will understand from these disclosures how to implement these techniques in 3-D rendering.

FIG. 1 depicts an overview of an example system in which aspects of the present disclosure can be implemented;

Figure 2 depicts an example method according to the present disclosure;

FIG. 3 depicts an example component method that may be used to support the method depicted in FIG. 2;

4A-4F depict various aspects of an example of multi-level subdivision of a 3-D scene for use in methods and systems according to the present disclosure;

Figure 5 depicts an example micro-collection of primitives for which an acceleration structure is to be created;

Figure 6 depicts some of the primitives mapped to voxels at a selected level of granularity (LOG);

Figure 7 depicts relatively large and regular primitives mapped to voxels under a different LOG than the primitives of Figure 6;

Figure 8 depicts an example where primitives appearing in Figure 6 are mapped to voxels under a finer-grained LOG than in Figure 6;

Figure 9 depicts a cubic coverage volume for a portion of primitives mapped onto concrete voxels

FIG. 10 depicts an axis-aligned coverage volume for a portion of a primitive mapped onto the voxel of FIG. 9;

Figure 11 depicts an example where the axis-aligned coverage volume of Figure 10 is extended to include another primitive;

Figure 12 depicts a coverage volume including primitives from the finer-grained LOG and from voxels directly under the coarser-grained LOG;

Figure 13 depicts aspects of the operation of a cache according to the present disclosure;

Figure 14 depicts a logical view of an acceleration structure that can be generated using implementations of the present disclosure;

Figure 15 depicts a packaged memory representation of an acceleration structure that can be produced using implementations of the present disclosure;

Figure 16 depicts an example of photon deposition in a 3-D scene using ray tracing with ray differentiation;

Figure 17 depicts the process of determining the acceleration level for photons;

Figure 18 depicts another process for determining the acceleration level for photons; and

FIG. 19 depicts an example system in which implementations of the present disclosure may be provided.

detailed description

The following information relates to an example of an algorithm for generating an acceleration structure comprising elements surrounding a surface in a 3-D scene. In one particular example, the surfaces are defined by primitives, and the acceleration structure is used for ray tracing. In another example, the acceleration structure can be created for use in photon interrogation.

Acceleration structures can be created according to various methods. Although the acceleration structure was expected to speed up the testing of ray intersections, and did achieve that goal, the use of the acceleration structure created additional overhead within the overall rendering system. For example, there is the overhead of building an acceleration structure for a given scenario.

Some acceleration structures can be designed for static 3-D scenes (ie, not animated 3-D scenes), and instead, the viewpoints and lights in the scene can be variably placed. In this case, it would be reasonable to speed up the relatively careful and time-consuming construction of the structure. If a static scene is to be used invariably over a long period of time (for example, a model of a building to be constructed is observed from one point of view), then for this purpose the costs involved in constructing the accelerated structure can be ignored in the overall judgment of the quality of the accelerated structure. required time.

However, in a dynamic scene, objects can enter, leave or move within the scene, change their geometry, etc. In these kinds of applications, the magnitude of the overhead of building or updating the acceleration structures can become a substantial portion of the computation required to render images from the scene. For these more frequently updated scenes (as in animated scenes), or when real-time changes can be made to the scene, speeding up the reconstruction or build time of the structure (and the amount of computer resources required to achieve this build time ) can be a factor in judging the usability of a given method for building an acceleration structure. Therefore, for dynamic applications, the approach to building and using acceleration structures should factor in both the time and resources required to build (or rebuild/modify) the acceleration structure, and the extent to which the acceleration structure helps accelerate the actual ray tracing of the scene inside.

This case also takes into account the general fact that, for a given method of building an acceleration structure, more computational resources are expended to build a given acceleration structure in the sense that each ray will require fewer intersection tests to produce A "better" acceleration structure. In the context of ray tracing, one goal of using an accelerated structure is to obtain a closer to constant resolution time for ray intersection tests as the scene becomes more complex.

The approach to creating an accelerated structure can be judged based on the time required to assemble the structure for a given triangle count and the average time it takes to resolve each ray intersection (referred to herein as "traversal time"). Example units of measurement could be "triangles per second" and "rays per second" respectively (this could be analyzed for a specific architecture or a fixed and specific set of computing resources). It may be useful to further express these factors as "number of node tests per ray" and "number of triangle tests per ray", which may make the metric more independent of specific computing resources.

It would also be interesting given the generality of accelerated structure building algorithms. For example, some kinds of accelerated structure building algorithms may perform better than others for some kinds of 3-D scenes. Also, some kinds of algorithms can produce better accelerated structures if special kinds of shapes or programs are used in the accelerated structure. For example, "long-skinny" and/or off-axis geometries may be poorly enclosed (eg, too loosely) in many typical enclosing volumes for acceleration structures. Shapes that are not sensitive to this feature are more expensive to intersect with rays during traversal and are difficult to generate during accelerated structure assembly.

If it is desired to apply a given accelerated structure-building method to variable and often unknown scene-building conditions, it may be desirable to collect such metrics for a variety of sample scenes, which may have different kinds of characteristics , these features may challenge the accelerated structure-building algorithm in different ways. Rather, some accelerated structural methods may have favorable traversal times at the expense of slow build times (on the order of many seconds or minutes), unrealistic requirements for a commercially viable implementation, or both. Scene-specific effects can also be made apparent.

In one aspect, the present disclosure relates to accelerated structure building methods that are useful in dynamic scenes (such as in animation) or other situations where the 3-D scene needs to be updated many times per second, but where the computational requirements are Realistic and well-balanced (however, not required for use with dynamic scenes). In some aspects, the present disclosure relates to methods that can be scaled based on target available computing resources or given performance goals, or both. Thus, in some aspects, the present disclosure relates to methods for implementing a balanced system that takes into account accelerated structure build time and ray traversal time.

Example features of accelerated structure construction algorithms according to the present disclosure may include any of the following: streamlined pipeline avoiding recursion, O(nlogn) worst case construction time, where n=triangle count (triangle_count). Simple and efficient method for determining spatial adjacency in bottom-up construction. Triangles are handled in a similar way to voxelization/3D scan conversion which uses simple integer arithmetic and avoids/reduces floating point calculations. Intermediate data transfers/bandwidth usage can be constrained to stay within a certain amount of on-chip local memory. A tradeoff between the quality of the resulting acceleration structure and the available local memory storage can be determined. Off-chip data transfers/bandwidth usage can be streamed, such as streaming geometry reads and streaming acceleration structure definition data writes.

The present disclosure provides algorithms that can place multiple bounding volumes across elongated geometries to tighten the geometry's bounding so as to reduce wasted ray node tests. Kd-trees provide examples of regular structures, and bounding volume hierarchies (BVHs) are a classification of possibly irregular acceleration structures. Acceleration structures can also be homogeneous (where a given element directly surrounds only other elements or primitives, and leaf nodes directly surround all primitives) or dissimilar, where any given element can directly surround other elements Combination with primitives.

In the following disclosure, a vertex may be considered to define a point in 3-D space, and the vertex may be represented by a tuple of multiple values. A triangle primitive can be defined by 3 vertices. In a triangular mesh, multiple vertices can be shared between different primitives, rather than each primitive being defined by a unique set of 3 values. A mesh can also include an interpretation rule, such as a winding order. For example, a triangle strip mesh defines multiple triangles using an additional vertex combined with two previous vertices of a previous triangle. Thus, for n vertices, n-2 triangles are described. A "triangle" mesh uses 3 individual vertices to define a triangle. Thus, for n vertices, n/3 triangles are described (n is divisible by 3). Various other representations of triangle primitives may be implemented. Also, in various implementations, primitives need not be triangular but can be formed from other kinds of surfaces. As such, the examples of triangle primitives are not limiting, but serve to clearly and concisely illustrate aspects of the present disclosure.

The systems and methods can process meshes of primitives (eg, triangle strips) and can input or otherwise access vertex connectivity rules for the mesh to be processed. A mesh can be identified using an identifier; a pointer can refer to an array of vertex data that defines the triangle mesh. Information such as the total triangle count.

The present disclosure is primarily concerned with an example where a fixed 3-D scene subdivision (eg, voxel grid) is used as a working scene subdivision to map primitive streams onto portions of 3-D space. After mapping a collection of primitives onto a portion of the 3-D scene, one or more elements of an acceleration structure to be used in the rendering process are created from the mapping. Thus, in the present disclosure, a final acceleration structure can be produced that has elements different from the scene subdivision used to map primitives onto 3-D space. However, this final acceleration structure is not necessarily characteristically different from the 3-D scene subdivision used for mapping.

In one example, the geometry is defined with respect to a position in the 3-D scene, such as using 3-D world space coordinates, often referenced from a (0,0,0) position. This way, all geometry will lie somewhere in 3-D space, collectively defining the extent of that geometry in all dimensions of the scene. The 3-D scene subdivision can be matched to the space occupied by the geometric shape (eg, the position of the top level part of the scene subdivision can be aligned with the geometric shape). However, in one approach here, the full range of 3-D scene subdivisions is rounded to the next higher power of 2 in size. All scene subdivisions are then sized and placed according to powers of 2 and indexed using integers.

In one example, the 3-D scene is subdivided into a multilevel collection of axis-aligned cubic volumes, each of which is referred to herein as a voxel for simplicity. A voxel can be analogized to a pixel in 3-D. Multilevel involves any given point in the 3-D scene being surrounded (enclosed) by several voxels of different sizes, where the voxels of different sizes are in different levels of the multilevel set. Here each level in the hierarchy is identified by a level of granularity (LOG), causing a progression from larger to smaller cubes within the multi-level set. For example, the entirety of a 3-D scene may be identified as LOG=0, and it may contain a single cube. In one example, the number of cubes under a given LOG can be found to be (LOG+1)^3, making progressions of 1, 8, 27, 64, etc. The voxels under each LOG collectively cover the 3-D scene. In one example, there are 32 levels of granularity, which would allow 32,768 voxels at LOG=31. Unless otherwise stated, the 3-D scene subdivision onto which primitives are mapped may represent the space as a 3D grid set of discrete voxels at various resolutions within the 3-D scene.

As will be explained in detail, each voxel under a given LOG can be individually addressed using 3-D integer coordinates [xi, yi, zi]. In order to adequately define any voxel in the multilevel set, the LOG of that voxel must also be defined. Defining the 3-D integer coordinates defines a voxel set of all LOGs with the defined integer coordinates. Accordingly, the present disclosure provides a 3-D scene subdivision that allows any member of the 3-D scene subdivision to be easily addressed or uniquely identified. Voxels are exemplary approaches, not exclusive. More generally, any kind of approach that allows subdivisions of 3-D space to be addressed with neighborhoods that vary from small to large can be used. Still more generally, any approach that allows addressing a subdivision of a 3-D space that defines one or more of the following: the form of the subdivision, the relative The orientation of the scene axes, and the relative size of the subdivisions. For example, as exemplified above, points in 3-D space and a set of offsets may be used to describe a set of bounding volumes rather than an explicit set of integer coordinates for each voxel. In view of the above, various details and examples are set forth below with respect to the accompanying drawings.

FIG. 1 depicts an example system 50 . The system 50 has a classifier 52 that inputs a stream 51 of primitives. Classifier 52 generates a voxel coordinate [XYZ] and a LOG ([XYZ]LOG 59 as an example) for each primitive processed. Classifier 52 is coupled to the output of scan converter 54, which has access to data 53 representing a voxel coordinate system. Scan converter 54 outputs to a voxel cache 56 . Scan converter 54 may operate as a digital differential analyzer for stepping along the edges of the primitives and determining whether each pixel encountered is within the primitive. In some implementations, the scan converter 54 can operate using integers for defining the boundaries of the subdivision elements; in some implementations, by increasing the size of the space to align all subdivision elements with integer boundaries, the surrounding elements are Placed in this space to allow the alignment described above. In contrast to traditional scan conversion algorithms, which may require the edge to traverse at least the center of the polygon, scan conversion here tracks any portion of a voxel that falls within the primitive. Scan conversion can be beneficially implemented in fixed-function hardware. Various approaches can be implemented to provide scan conversion for use in implementations of the present disclosure. More generally, implementations may provide a description that generates a collection of one or more 3-D shapes that completely contain the primitive, and may address each shape separately, such as for each such Create a cache entry for each shape (described below).

Voxel cache 56 outputs cache entries through voxel cache selector/output 58 . Voxel cache selector/output 58 may reclaim data from an evicted cache entry (referred to as Vbnode data 55 as explained below). This data also goes to a format converter 60 which produces accelerated structure elements stored in memory 62 . Vbnode data 55 may also be stored in memory 62 . If the voxel cache selector 58 does not evict, the format converter may evict the Vbnode data 55 . Example operations and uses of these components are disclosed in more detail below.

The Vbnode data defines a temporary data structure representing one element of the spatial subdivision to which the primitive is mapped. Therefore, each Vbnode represents a spatial 3D volume. Each Vbnode may contain data indicating relationships to other Vbnodes. For example, a Vbnode may have two link pointers, respectively pointing to a same-level Vbnode and pointing to either a first sub-Vbnode or a vertex. A Vbnode is transient in the sense that it does not describe the final element in the final hierarchy. Instead, they are created during the mapping of primitives onto workspace subdivisions, passed to the copy-out stage for conversion into final elements of the accelerated structure and then no longer needed. In some implementations, no matter how large the overall scene hierarchy ends up, the Vbnodes are managed so that they will all remain in local storage memory. In one example, Vbnodes are designed to be as small as reasonably possible to allow a sufficient number of them to be active during hierarchy construction in local storage. In one implementation, each requires 32 bytes, allowing 2 to be reserved for every 64 cache lines.

Example information that may be provided in a Vbnode includes an indication of whether the node is a leaf node, a count of references to the node. If the node has zero references, there is no need to keep the node. Indicates where the node is relative to the parent node (eg, in an octree implementation, Vbnode may indicate the hexagram limit of the parent node). Vbnodes can also carry data through the pipeline, making the data available to downstream functions or functions performed at a later time.

Figure 2 depicts an overview of an example method. At 120 , the primitive data is input to the classifier 21 . At 122, characteristics of the primitive are determined; at 124, the determined characteristics are used or analyzed to select a level of granularity (LOG) at which the primitive is surrounded by voxels. In short, a finer-grained LOG results in the use of smaller voxels, while a coarse-grained LOG results in the use of fewer larger voxels. Classifier 21 may work according to one or more heuristics using different kinds of data inputs. Further details related to an example method of primitive classification are provided with respect to FIG. 3 .

At 126, a spatial locator is identified for each voxel that contains a portion of the primitive under the selected LOG; essentially, the set of voxels that contain any portion of the primitive is identified. The spatial locator and LOG for each voxel determine the set of entries in cache 56 that will be associated with that primitive (see FIG. 13 ).

At 128, and for each voxel determined at 126, a coverage is calculated. In one example, the coverage is represented by a pre-selected shape, with multiple dimensions and a position within the selected voxel, such that the coverage is only one that encloses all parts of all primitives within the voxel A single continuous shape of . In one example, the footprint may be cube-shaped, or an axis-aligned bounding box, but it does not require all sides to be of equal dimensions. Other examples of covering shapes include polygons and spheres. The shape used to represent the coverage can be chosen based on the one that will be used in the final resulting acceleration structure.

At 130 , the coverage computed at 128 is stored in cache 56 . As described above, each of 126, 128, and 130 is performed for each voxel identified as containing a portion of the primitive being processed. Thus, after a primitive is processed, one or more voxel cache entries may be updated with a link to the processed primitive, and the voxel cache entries associated with each of these voxel cache entries will be updated accordingly. One or more corresponding coverage areas.

After 130, further primitives can be processed. Eventually, a voxel in the cache will be evicted, because in most implementations, the amount of memory allocated for the cache will be less than the amount of memory required to store data for all primitives of the scene , such that the elements of the acceleration structure must be created in real-time and transient in the system performing the disclosed method.

At 142, one or more elements of the acceleration structure are determined from the evicted cache contents. A larger cache size allows for the creation of better acceleration structures where the acceleration structure elements cannot be modified or edited after creation. This occurs when geometry and other content is only maintained transiently, potentially making the state required to edit acceleration structure nodes unavailable. This can also be avoided for minimal benefit, for practical considerations such as causing too many calculations to be performed.

Coverage information for content evicted from the cache is provided to 128, wherein coverage is calculated for higher level voxels based on the provided coverage information and existing coverage information. In other implementation manners, the coverage information may also continue to go through steps 120 to 126 .

In practice, primitives can be streamed, and when the cache is full, voxels can be evicted from the cache so that coarser-grained voxels start receiving coverage from finer-grained voxels. In a similar implementation, all primitives are surrounded by leaf nodes, so that the coarser-grained voxels only surround the coverage of the leaf nodes, but do not directly surround the primitives themselves. In various implementations, the cache 56 may be flushed or the pipeline otherwise run to complete processing of all primitives before processing the coverage box. In some implementations, cache 56 may have two independently controllable portions that are allocated to leaf nodes and non-leaf nodes, respectively.

FIG. 3 depicts an example method of classifying primitives in order to select the LOG in which the primitives to be surrounded reside. Examples of how FIGS. 2 and 3 behave with different kinds of primitives are disclosed with respect to FIGS. 4 to 12 .

At 152, the surface area of the axis-aligned box enclosing the primitive being characterized is calculated. At 154, the absolute size of the classified primitive can be found, and at 156, the aspect ratio of the primitive can be determined. The aspect ratio of this primitive is a calculation of the ratio of length to width; thin triangles have relatively tall aspect ratios. For example, a tall aspect ratio is used as an indicator that the primitive may not be able to properly utilize a single large bounding volume.

At 160, for the primitive, a ratio of the surface area of the primitive to the surface area of the bounding volume is calculated. This ratio is used as an indication of how well the primitive is aligned with respect to one or more axes of the bounding box (corresponding to scene axes unless transformed). For example, a triangle may typically run vertically, and thus align with a vertical face of the bounding volume, which may be of lesser thickness and have a smaller surface area, making the The surface area ratio will be greater. This calculation is one example method of determining such characteristics; other methods may be provided. As with all such determinations or calculations, the numbers may be scaled or otherwise changed, and they do require expressing any quantity externally usable or available as an absolute comparison. For example, for axis alignment ratios, twice the area of the primitive can be used to calculate the ratio while still maintaining a consistent metric. Similarly, constants can be cleared to simplify calculations where appropriate.

The remainder of Figure 3 provides an example of evaluating these data to achieve LOG selection. As will become apparent, such evaluations need not have firm or hard decisions, but instead can be heuristic. The evaluations depicted in Figure 3 are shown as all being performed in parallel, but that is an implementation detail. Tuning can be performed by testing different sets of parameters or conditions. At 162, the relatively high aspect ratio induces a more fine-grained tendency at 165. Relatively large (absolute size) primitives with low aspect ratios at 163 cause a coarser grained trend at 166 . At 164 , an axis alignment score indicating a relatively high axis alignment provides a more coarse-grained trend at 167 . At 170, selection of a granularity level is made based on one or more of these inputs. As introduced above, the input to this selection is typically on a continuum of values, and can have quite a few levels of granularity (32 in one example).

Further, certain heuristics are more relevant for some situations than others. For example, the concept of coverage within a given voxel has been introduced above and will be described in more detail below. If AABB is used to track coverage, axis alignment can be a more heavily weighted input. Aspect ratios can be weighted higher if tracking is done for spherical coverage. An automated tuning algorithm can be performed that will search the input space and determine what selection criteria are appropriate for different accelerated build settings; manual tuning can be performed, or a combination of the above. Other inputs may be provided to such a process, and these are exemplary. In all cases, not all inputs need to be provided.

Figures 4A-4F begin a simple example of applying the above disclosure. Figure 4A depicts voxels 5 to 9, provided as 3-D spatial subdivisions for use in building acceleration structures. The example of FIG. 4A shows a case where a plurality of voxels have the same form and are nested within each other. Here, the term "form" is used to describe aspects of the shape of one or more voxels used in spatial subdivision. For example, as shown in 2-D in Figure 4A, the cubic form provides equal length sides in all three dimensions, while the rectangular form has one elongated dimension. Form also refers to the aspect ratio of a non-cubic shape, since a rectangular shape can have a low aspect ratio surface (more cubic) and/or a high aspect ratio (elongated and less cubic). Due to the fact that voxels are in 3-D space, some faces of the rectangle may be cubic, while other faces are highly elongated. And, because voxels of a given form can be provided in different sizes (e.g., as a nested voxel structure, like that shown in FIG. or degree of reduction. In one approach, each dimension of the voxel is scaled uniformly (eg, scaled by a power of 2). In another approach, one or both dimensions are scaled uniformly, and the other dimension may be scaled differentially or not at all.

The term "form" may also refer to a difference in orientation of a voxel in 3-D space (eg, alignment to one plane or another in 3-D coordinate space). As shown with respect to FIGS. 4B-4F , various other forms having different relative sizes, orientation differences, etc. for different dimensions may be provided. In summary, Figure 4A depicts an approach in which all voxels have a cubic voxel form. Figures 4B-4F depict aspects of other forms of voxels that may be used individually or together in subdivision. In one particular approach, within any given subdivision of space, voxels in multiple voxel forms may be provided, and a suitable set of voxels from the available voxel forms may be selected for enclosing a particular primitive.

In FIG. 4B, example voxels 14a and 14b are rectangular in cross-section, having a non-cubic cross-section in the cross-sectional plane. In Figure 4B, depth is not depicted, and one of ordinary skill will appreciate from this disclosure that the depth of voxels 14a and 14b is another variable parameter within the form of these voxels. For example, the depth can be approximately equal to, less than or greater than the height. Figure 4B also depicts rectangular voxels 15a and 15b (having a form in which the aspect ratio of the cross-sectional plane is higher than voxels 14a and 14b), and also depicts that voxels 15a and 15b will nest like voxels 14b Volumes defined by the same voxels (within these volumes), since voxel 14b will be repeated across the space identified by the dashed box in which voxels 14ab and 15ab are defined. The orientation difference between voxels 14a and 14b shows that a voxel in a given dimensional form can also have multiple orientation differences. For clarity, in all these examples, for each voxel form depicted (e.g., voxel 14b), the entire 3-D space being used can be filled with voxels of that form, and again with the same Formal but smaller voxels. Each voxel form in a variety of different sizes and orientations can fill this 3-D space.

FIG. 4C depicts voxels 16a and 16b as 3-D elongated voxels, and the dashed line spans the face of voxel 16a, depicting the scaling of voxels of form 16a and 16b within the dimension of the face, but not the voxel. depth. Figures 4D-4F depict voxels 17-19 with different scales and orientations in 3-D space. In one approach, the voxels are axis-aligned bounding boxes, consistent with the examples of FIGS. 4A-4F .

From the above disclosure, it should be apparent in some embodiments that a 3-D scene is subdivided such that each position (location) in the 3-D scene is within a plurality of voxels, which may have different forms and /or one or more of different sizes. Each of these voxels can be addressed individually. Addresses may be constructed according to predetermined conventions. For example, a predetermined set of forms of voxels may be selected (eg, cubes, elongated rectangles with square ends, thin rectangles with large areas, etc.). Each of these forms can be arranged to fill the 3-D scene in more than one orientation, for example multiple thin and large can be stacked parallel to the XY plane with increasing Z and in the YZ plane with increasing X area of the rectangle. Thus, an address includes components identifying the form of the voxel, the orientation of the form and identifying the size and also the location of the voxel. Thus, these disclosures show that a complete set of voxels from which one or more voxels can be selected to enclose a particular primitive can be composed of voxels of many different forms, sizes and positions, allowing Better selection of voxels for better bounding volumes. For example, a lamppost and a telephone pole may be surrounded by voxels of similar form but different sizes, while a wall approximately the same size as the lamppost may be surrounded by voxels of similar height but generally different form.

Figure 5 depicts the primitives 10 to 13 in 3-D space, including the primitives for which the acceleration structure will be created. FIG. 6 depicts voxels 20-23 under a selected LOG, where voxels 10-12 are overlaid on voxels 20-23. FIG. 7 depicts a voxel 9 under a coarser-grained LOG, in which a graphic element 13 is included. Figures 6 and 7 illustrate that multiple primitives can be completely contained within a voxel (as in Figure 7) or can be surrounded by a series of voxels. Figures 6 and 7 also depict that primitives can have very different shapes, with different aspect ratios and axis alignments. FIG. 6 depicts that primitive 10 is more axially aligned than primitive 11 , and that both primitives 10 and 11 have a relatively high aspect ratio compared to primitive 13 . According to the heuristic of FIG. 3 , primitive 13 can be mapped to a coarser-grained LOG than those in FIGS. 10 and 11 .

FIG. 8 depicts voxels 25 to 31 , still under the finer-grained LOG, and these voxels collectively surround primitive 11 . Primitive 11 is less axis-aligned than primitive 10 and, therefore, a tighter fitting set of voxels 25 to 31 from which acceleration structural elements can be generated can be beneficially used. Of course, depending on the circumstances, it is also possible to choose a still finer-grained LOG, which will still provide tighter enclosing, but at the cost of more voxel elements, which is usually the same as having more elements in the final acceleration structure associated, thus giving an example of a compromise between avoiding bounding boxes that are too loose for primitives, but not generating too many accelerated elements that all need to be tested and stored.

Figure 9 depicts a voxel 20 within which a portion of the primitive 11 is located. Figure 9 depicts a coverage area 32, which in this example is itself a cube (requiring all edges to be of equal length). For a given voxel, a "voxel coverage" or simply "coverage" defines a portion of a voxel that at least partially encloses all geometry in that voxel (either directly or and surrounded by finer-grained voxels). In an example implementation, an axis-aligned bounding box within the voxel may represent the coverage and be defined proportionally to the voxel's scaling. Since the coverage box can be defined within a voxel position, it can be rendered with greatly reduced precision. In one example, 8 bits per axis may be used. In another example, the coverage volume is a cube. Other representations may be used, such as a position and extent in one or more directions relative to that position; in some implementations, coverage may be represented by arbitrarily complex shapes; however, implementations may require benefit from the minimization of the amount of data in the voxels, allowing more voxels to be represented simultaneously in a fixed-size cache.

Fig. 10 depicts an example according to Fig. 9, again depicting voxel 20 and primitive 11, except that coverage 33 is traced with an AABB shape instead of a cube. Figure 11 depicts the coverage as the spatial union that includes all parts of the primitives present within a voxel; specifically, primitive 11 is now added to voxel 20, and the coverage 34 is generated as The union of coverages 33 and is also required to enclose primitives 10.

Figure 12 depicts how coverage and primitives can be aggregated into voxels under a coarser-grained LOG. Coverage 32 and coverage 35 of voxels 21 and primitives 10 are also depicted. Coverage 35 and coverage 32 are added to voxels 38 as depicted. Primitives 36 are also added directly to voxels 36 . Thus, the coverage of voxel 38 is that of coverage 35, coverage 32, and primitive 36 under constraints determined by the kind of shape to be used to represent the coverage (e.g., voxel, AABB, sphere, or other shape). union. In this example, the coverage is based on a finer-grained voxel coverage and is calculated for any primitive (eg, primitive 36 ) that is directly surrounded by a voxel (eg, voxel 38 ). Therefore, coverage for coarser-grained voxels is not recalculated directly from the primitives in this example.

FIG. 13 depicts an example of cache 56 and its operation. As described above, the cache 56 stores the spatial position ID of each voxel and data indicating the LOG of the voxel. An example of this is depicted in FIG. 13 as spatial location IDs 205 , 207 and 209 . LOGs 206, 208, and 210 are associated with spatial locations 205, 207, and 209, respectively. Figure 13 depicts that each spatial location ID also has a maintained coverage indicating the union of all primitives and parts of primitives within (directly or indirectly surrounded by) the voxel. Additionally, an identifier for each footprint and the shape (primitive) being cached against that space ID is also provided. Such information should at least identify these coverages and/or shapes, but need not include their defining data.

In operation, cache 56 is addressed using spatial coordinates and a LOG (eg, [X,Y,Z] LOG 218 ) that are input to cache location mapper 220 . This can be for both adding coverage or primitives to existing voxel cache entries and creating new voxel cache entries. In this example, the mapper 220 hashes (231) the [X, Y, Z] LOG 218 to produce a hash value 235 for identifying (233) the candidate cache locations (Loc 237-239); Aspects are associated with an interleaving factor, and if the cache allows any voxel to be stored at any location, no candidate locations need be identified, and instead a list of free locations can be maintained. If the operation is an add voxel (240) operation, determine (245) whether there is a free location; if so, add the voxel there; if not, evict (249) an existing voxel location so that One slot is free. For adding to a location (241), a determination is made (242) whether there is still space in the location (242), and if so, the primitive or coverage is added, and if not, an eviction is performed (249). Which location to evict can be determined based on heuristics, such as using a metric, or the number of elements in that location, or the difference in the granularity level of voxels in that location compared to the average of other locations, or a combination of these, Or another heuristic as you see fit. Information associated with a coverage may include a thread identifier that generated the coverage, the address of the voxel to which the coverage depends, and a link to peers and child nodes (if any). Additional fields may be provided for passing data through the cache for application specific purposes.

It should be understood that various changes may be made in implementing the methods (and system operations) in accordance with the present disclosure. Not all possible permutations are disclosed, as these are a matter of implementation and one of ordinary skill will be able to determine if and when to use a certain permutation when implementing it given these disclosures. Examples of such variations are provided below.

As introduced in the examples above, the 3-D scene space is subdivided into a multi-level collection (eg voxel hierarchy) of axis-aligned cubic volumes. The input geometries can be described using real numbers in world space; thus, all input geometries can be transformed into coordinates within a voxel grid under a particular LOG (or LOGs). This transformation can be scaled and translated to a bounding cube that completely encompasses all input scene geometry. At the beginning of the hierarchy, it can be assumed that the axis-aligned bounding cube of known world space contains all such geometry (as output from previous vertex processing pipeline stages within the renderer, coupled to this acceleration structure builder. After the transformation, all internal operations can be performed in the local coordinate system. When a copy-out occurs, the inverse transformation is used to produce a corresponding world-space bounding volume in the scene hierarchy from the representation in the transformed 3-D space. To perform this inverse Change, the voxel level can be associated with data that can include specific data for each type of LOG. In one example, such data can include: (1) the minimum world space coordinates of the bounding cube at this level, (2) this The range of the cube surrounded by the hierarchical world space, (3) the scaling information per LOG, (4) the scaling factor from the scene voxel to the voxel under this LOG, (5) the world space size of the voxel under the given LOG, ( 6) The world space size of the voxel coverage unit under this LOG, and (7) the largest addressable voxel under this LOG.

Some implementations may also provide or enable internal transformations that provide enhanced axis alignment for a defined subset of acceleration structure elements that will typically surround an object. For example, objects in the scene may be surrounded by self-contained subtrees within the acceleration structure hierarchy. This object and its subtrees can be rotated to be axis-aligned relative to an internally meaningful set of axes by allowing the scene object to be rotated in any way, which means that the object is no longer consistently defined relative to these scene axes. During raytracing or other use of accelerated hierarchies and/or scene geometry, a ray can be transformed (origin, direction, and one or more clipping distances) as it enters this subtree into the set of internal axes and tested Its intersection under that varying condition, which allows for more efficient traversal in the hierarchy. Intersection points can be transformed back to scene space, e.g. for comparing collision distances, or during shading.

14 and 15 depict aspects of acceleration structures derived from the contents of evicted voxel cache locations. Figure 14 depicts leaf elements 277 and 278, which surround primitives 279-280 and primitives 281-282, respectively. These node elements are in turn surrounded by coarser grained elements 274 and 275 . Element 2725 surrounds element 275 and primitive 273. The dashed line between 275 and 274 indicates a sibling relationship. Figure 15 depicts packing of elements from Figure 14, which may be provided for storage in memory. An acceleration structure may store identifiers or pointers to definition data for primitives, and/or elements of the acceleration structure. However, primitives may require more storage, and possibly variable-sized storage, given that vertices may have different magnitudes of attributes associated with them.

In one aspect, the above disclosure describes example systems and methods for determining a bounding volume for a set of leaf nodes that bounds all geometric shapes in a 3-D scene. These leaf nodes may be of different sizes, selected according to one or more characteristics of the primitive, and possibly based on a type of node to be used in the acceleration structure. Bounding volumes can be recursively condensed into larger and larger bounding volumes with increasing levels of abstraction.

Figure 16 begins with an introduction to the approach used to build accelerating structures for photon mapping. Fig. 16 shows an example 3-D scene where lights 350 and 349 emit light into 3-D space. In photon mapping, photons are first deposited into a scene by forward tracing rays from multiple lights. Photons exhibit characteristics of light emitted from a location that can be received from a spatial location or volume, such that sampling photons from a point can provide lighting information about that point.

In this example, the ray traced forward from the light is assigned a differential based on the characteristics of that light. For example, ray 355 emanates from lamp 350 and is assigned a differential 351 . Ray 357 is emitted from lamp 349 and is assigned a differential 352 . Ray 355 was found to intersect a shape at intersection point 360 , while ray 357 was found to intersect at intersection point 361 . For simplicity, a single shape is depicted, but in real scenes the intersections are often widely spread out and many rays will be cast from a single light. FIG. 16 depicts a reflected ray 356 that is also assigned a differential 353 . This reflected light ray 356 can also be used to characterize the photon deposition.

As will be described, ray differentiation can be used to determine or otherwise track how photons should appear in the accelerating structure. Figure 17 provides an example of bottom-up construction of photon-accelerating structures. At 402, a light source is identified as a photon source (identifying a scene light source), and to determine the photons for each light, at 404, multiple rays and multiple derivatives are generated. The differentiation of each ray can be determined by the characteristics of the light source. For example, a focused light source will receive a smaller differential than a diffuse light source.

At 406, the resulting rays are traced to identify intersections (here, tracing includes tracing secondary rays that model reflection, refraction, etc.). At 408, photons are deposited at locations in the 3-D scene for the detected intersection points. At 410, the differentiation of each ray (now associated with a particular photon) is used to select the level of granularity of the voxel that will directly store that photon. As in the discussion above, there are multiple nested voxels, each of which may enclose a specific location in 3-D space. The ray differential and the distance to the ray's intersection point can be used to determine the ray's width around an intersection point. So, for example, a wide differential that intersects some distance away gives a wide ray at the point of intersection, while a ray with a narrower differential at the same intersection distance will be narrower. Rays with wider points at intersections are driven to use voxels at a coarser grain level (larger voxels), while conversely, rays with smaller grains are driven to use finer grain levels (smaller voxels). Smaller voxels allow more precise positioning of photons than larger voxels, but this precision is unnecessary if the ray is wide anyway. Thus, at 412, a LOG for each photon is selected, and at 414, each photon is associated with the voxel's cache location determined by the selected LOG and the location of the intersection point. At 416, cache evictions can be managed as described above. Format conversion can also be performed similarly, in which the shapes used in the acceleration structure need not be voxels; the above-mentioned shapes can be used. In some implementations, a ray may be fired with a hint or other metadata to be used to select the LOG for the photons deposited due to the intersection with the ray. This metadata can be thought of as the radius of the effect of the directionless photon specification.

Photon deposition can include correlating light color and intensity with a distribution of a point or points, or parameters that, by interpreting or using these parameters in a calculation, can be used to determine light color and/or intensity. Photon deposition is done by directly specifying the photons to be localized in the 3-D scene, and hints and other metadata can be used to select the voxel's LOG to contain these photons.

In another aspect, the photons within a given voxel can be mixed together (color mixing) and their positions all represented by a single point within that voxel, such as a center point. It is also possible to combine photon contributions into a distribution, such as a Gaussian lobe distribution for each facet of a voxel. Essentially, storage space is saved by mixing these photons together and not trying to distinguish the 3-D position of each photon within each voxel. This savings comes as a tradeoff with respect to accuracy, but the implementation can be tuned so that an appropriate balance of these factors is achieved. This mixing or merging can be done in conjunction with determining the addition of a given photon to a particular voxel. A sparse hierarchy of voxels can be created that contains voxels that have multiple photons and can be used for photon interrogation.

Figure 18 depicts a process for implementing different approaches to photon mapping. FIG. 17 depicts processing photons in a bottom-up manner, in which increasingly larger volumes abstracting larger regions of 3-D space are created in multiple passes. Figure 18 depicts a different approach. Specifically, at 418, rays are traced, and at 420, photons are deposited on intersection points. At 422, for the defined overall cell structure, photons are added to each voxel at all levels of granularity (e.g., for a voxel level of 32, the same photon is added to the voxel level 32 times, where, same spatial coordinates, but different LOG). Thus, a voxel structure containing all photons at all granularity levels is generated. Following this generation, at 428, the voxel structure is traversed a series of passes top-down.

At 430, when a voxel ("current voxel") is encountered at a given LOG, a count of photons present within that voxel is accessed or generated. If the count is greater than a threshold, the current voxel is cleared from the hierarchy, and the child nodes of the current (now cleared) voxel are directly connected to the parent node of the cleared voxel. At 432, for each child node of the current voxel, and if the current voxel is not cleared because it has fewer photons than a threshold number of photons, each child voxel of the current voxel is checked. For each sub-voxel that has less than (or equal to) the threshold number of photons, the sub-voxel is purged. Unless otherwise stated, when a child voxel has less than or equal to a threshold number of photons, then the photons of that voxel may be pushed into voxels of lower granularity levels (larger voxels). In other words, Figure 18 depicts an approach for pruning a complete voxel hierarchy according to the number of photons deposited into different parts of the hierarchy. In a sense, this pruning is aimed at maintaining a balance between multiple accelerating elements and multiple photons in different voxels. This approach allows the use of smaller voxels to preserve accuracy (in cases where they have a relatively high number of photons) where it is beneficial. For example, a lens can concentrate light and that concentrated point will have a large photon density. Therefore, due to the implementation in which the described process is carried out, voxels will naturally be kept small for those photons.

Figure 19 depicts aspects of an example system in which the disclosed implementations may be practiced. Figure 19 depicts a cluster array 511 that includes cores 512-518 that can perform computations, such as graphics computations. A collection of data management 504 - 510 may set up computations to be performed on the arrays of cluster 511 . Cluster array 511 may have texture pipelines 520 and 522 used by one or more cores 512-518. Certain kinds of computations can use the pack unit 524 , which has a ready stack 526 , a collection definition/voxel cache 528 , an empty stack 530 and a packer 532 . Scan converter 534 may be coupled to packet unit 524 and formatter 536 . Formatter 536 may in turn communicate with cache hierarchy 542 , which communicates with system memory interface 538 . Host interface 502 may provide communication capabilities to another computing system via bus 540 .

With particular regard to the current accelerated structure construction algorithm, scan converter 534 may use collection definition memory 528 to store voxels (eg, functioning as cache 56 of FIG. 1 ). Collection definition memory 528 otherwise functions to collect a collection of data for one or more keys, and may distribute this collection of data within multiple packages. Packet slots to be filled with data from collection memory can be retrieved from the empty stack 530 and entered into the ready stack 526, which is read by the scheduler 540 and the contents of such packets distributed across the cluster array 511 up for execution. In one example, rays are processed in packages, and collection definition memory 528 stores ray identifiers in a plurality of collections each associated with a shape or shapes to be tested The intersection with the rays identified in each collection.

Elements of the acceleration structure can be used to abstract a larger number of primitives. Nothing in the examples should be considered limited to implementations following the principles of operation and techniques outlined herein, the problems that can be solved, should be solved, or the extent to which these disclosures extrapolate, abstract, or apply them in a different Limitations of usefulness in the context of solving a different problem or implementing them in another way. Rather, the specificity provides specific examples that should be readily understood, and one of ordinary skill will be able to adopt and learn from the disclosure to implement them in specific settings. Each of the above disclosures describes determining certain conditions, characteristics or values; those of ordinary skill will appreciate from these disclosures that such determination need not be exact, but with a degree of precision sufficient for the circumstances.

Computer code and associated data may be provided for implementing certain portions of the processes and other aspects described herein by a processor configured to execute instructions in the execution of such processes and portions thereof. Computer code may include computer-executable instructions, which may be, for example, binary instructions, instructions in an intermediate format such as assembly language, firmware, or source code. The code may configure, or otherwise cause to be configured, a general purpose computer, special purpose computer, or special purpose processing device to perform a certain function or group of functions. Any such code may be stored on a tangible machine-readable medium (such as a solid-state drive, hard disk drive, CD-ROM, and other optical storage devices), transiently in volatile memory (such as DRAM), or non-transitory in SRAM.

Various implementations may be provided, which may include interoperable hardware, firmware, and/or software, which may also be embodied in any of a variety of form factors and devices, including Laptops, smart phones, small personal computers, personal digital assistants, and more. The functionality described here may also be embodied in peripheral devices or add-in cards. By way of further example, such functionality may also be implemented on a circuit board between different chips or different processes executing on a single device.

For example, machines according to these examples may include a fixed-purpose 3-D scan converter, programmable elements for analyzing primitives, and memories for cache memory. Further machine components include multiple communication links. Implementations of the systems described herein may be components of a larger system including other input and output devices, such as one or more application processors, network interfaces, disk drives or solid state drives, displays, and the like.

In the examples above, these accelerated structure building components are part of a system or machine that produces output that can be used for various purposes, such as for rendering images in a video game, or for animation, or for storing or transmission to users, etc.

While various examples and other information have been used to explain aspects within the scope of the appended claims, no limitations should be implied to the claims based on specific features or arrangements in such examples because ordinary skill One will be able to derive many implementations using these examples. Further, and although certain subject matter has been described in language specific to examples of structural features and/or methodological steps, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to these described features or acts. Example processes may be described in a linear flow fashion, and sequences of various process portions are described, but such description is for convenience and some such portions may be performed in parallel or in a different order. Furthermore, multiple threads may execute each process portion, and different threads may be assigned to execute different portions of the described process. Furthermore, functionality may be distributed in, or in, other than, additional, or fewer components than those identified herein implement. Rather, the described features and steps are disclosed as example components of systems and methods within the scope of the appended claims.

Claims (22)

1. A machine-implemented method for generating an accelerated structure for use in rendering a computer graphics image from a three-dimensional 3-D scene, comprising: mapping a set of primitives to nodes of a workspace subdivision of the 3-D scene, each node of the workspace subdivision surrounding a 3-D volume within the 3-D scene; Each of the nodes is represented by a corresponding temporary data structure stored on a machine-readable medium, the data in the temporary data structure including data identifying one or more of the following: a parent node, a child node, and a primitive in the set of primitives mapped to the node; Defining elements of a hierarchical acceleration structure from an input comprising data from a selection made from the temporary data structure, the definition comprising subdivisions from the workspace corresponding to the selected temporary data structure the 3-D volume within the node determines a respective 3-D volume for each of the elements of the hierarchical acceleration structure; and A hierarchical acceleration structure is generated in a machine-readable medium using the determined 3-D volume. 2. The machine-implemented method of claim 1, wherein said representing each of said nodes comprises providing data describing a subsection of said 3-D volume, said 3-D volume surrounding a map mapped to all parts in said primitive of the node, and said defining includes aggregating the respective subparts of each of the 3-D volumes in the 3-D volume surrounded by said node corresponding to the selected temporary data structure , the aggregation defines the respective 3-D volumes of the hierarchical acceleration structure defined for the selection of the temporary data structure. 3. The machine-implemented method of claim 1 , wherein the defining is performed based on a subset of the nodes of the temporary data structure for which data is stored in a cache . 4. The machine-implemented method of claim 1, wherein each of the nodes of the workspace subdivision is represented by a set of planes defining a bounding box. 5. The machine-implemented method of claim 4, wherein the 3-D volume within the node represented by the selected temporary data structure is represented by data locating a corresponding subvolume within each of the nodes to define. 6. The machine-implemented method of claim 5 , wherein locating the data of a subvolume within each of the nodes comprises locating the node relative to the node's position in the 3-D scene. The subvolume's data. 7. The machine-implemented method of claim 1 , wherein said defining comprises defining each element of said hierarchical acceleration structure as an axis-aligned bounding box, said axis-aligned bounding box being defined as being A union of axis-aligned bounding boxes positioned within nodes corresponding to said selection of said temporary data structure. 8. A machine-implemented method for generating an accelerated structure for use in rendering a computer graphics image from a three-dimensional 3-D scene, comprising: mapping a primitive of the plurality of primitives for which a hierarchical acceleration structure is to be created into a workspace subdivision of the 3-D scene, the mapping comprising determining to collectively enclose the primitive in 3-D space A corresponding collection of one or more 3-D volumes of ; forming, in the machine-readable medium, a hierarchical acceleration structure from the set of 3-D volumes determined for the mapped primitives, wherein the forming includes: determining a set of leaf elements, each leaf element having corresponding data describing a bounding volume that is a 3-D volume within a selection of one or more 3-D volumes from the corresponding set of determined 3-D volumes Union of D spaces; determining a hierarchy of non-leaf elements that respectively define a bounding volume including a 3-D volume within each leaf element that is a child of the non-leaf element, and that the non-leaf elements to is contained within the bounding volume of the non-leaf element. 9. The machine-implemented method of claim 8, further comprising determining respective relative sizes of the one or more 3-D volumes in the set of 3-D volumes based on characteristics of the primitives and location. 10. The machine-implemented method of claim 8 , wherein the heuristic comprises evaluating a surface area indicative of the primitive compared to a corresponding surface area of a candidate set of 3-D elements to which the primitive can be mapped. The ratio. 11. The machine-implemented method of claim 8, wherein each primitive is mapped to one or more volume elements, each volume element identifiable by a unique address indicating the location of the volume element. 12. The machine-implemented method of claim 8, wherein the heuristic comprises evaluating a size of the primitive relative to a dimension of the 3-D scene. 13. The machine-implemented method of claim 8, wherein the heuristic includes evaluating an aspect ratio of the primitive. 14. The machine-implemented method of claim 8, wherein the mapping includes determining a granularity of segmentation to be performed on the primitive, and then determining the set of 3-D volumes at the granularity of segmentation. 15. The machine-implemented method of claim 8 , further comprising tracking a 3-D overlay defined as a bounding volume of a predetermined shape, the predetermined shape containing the 3-D overlay dependent, positioned in the map Part of all primitives within the node determined during the period. 16. The machine-implemented method of claim 15, wherein the predetermined shape is selected according to a type of shape for an element of the hierarchical acceleration structure. 17. The machine-implemented method of claim 8, wherein said determining said hierarchy of non-leaf elements comprises maintaining 3-D coverage for multiple regions within said 3-D scene, and completing and start processing another region of the 3-D overlay hierarchically comprising the completed region of the hierarchical acceleration structure. 18. An apparatus for generating an acceleration structure for use in rendering a 3-D scene, comprising: a streaming input configured to receive a definition of primitives, each primitive being located in the 3-D scene, and to generate a hierarchical acceleration structure containing the primitives for the 3-D scene; a mapper configured to map each primitive to a corresponding set of temporary 3-D scene subdivision elements determined by applying heuristics to different candidate scene subdivisions to which the primitive can be mapped; a cache coupled to the mapper and capable of storing data associated with the primitive, the data identifying fewer than all temporary 3-D scene tessellation elements of the temporary 3-D scene tessellation element a subset of sub-elements; and a hierarchy builder configured to operate on the subset of cached temporary 3-D scene subdivision elements to produce a portion of the hierarchy acceleration structure, and write to system memory the portion defining the hierarchy acceleration structure and wherein the cache is configured to evict at least a portion of the data defining the subset of cached temporary 3-D scene subdivision elements, all of the cached temporary 3-D scene subdivision elements The subset is used in defining the portion of the hierarchical acceleration structure written to the system memory. 19. The system of claim 18 , further comprising a coverage module configured to determine a subvolume within each temporary scene subdivision element for each corresponding set of primitives, each subvolume enclosing the temporary scene subdivision The part of this primitive in the element. 20. The system of claim 18, wherein the overlay module is further configured to generate data defining each subvolume, the data positioning the subvolume relative to the position of a temporary 3-D scene subdivision element. 21. The system of claim 18, wherein the heuristic comprises evaluating a ratio indicating a surface area of the primitive compared to a surface area of a candidate set of bounding boxes to which the primitive may be mapped. 22. The system of claim 20, wherein the subvolume is defined according to a predetermined shape, the predetermined shape being the shape of an element used in the hierarchical acceleration structure, and the predetermined shape can be independent of is determined by defining the shape of the 3-D volume in the workspace subdivision.