Patent Description:
Ray tracing is a technique for generating an image by tracing the path of light through pixels in an image plane and simulating the effects of its encounters with virtual objects. The technique is capable of producing a very high degree of visual realism, usually higher than that of typical scanline rendering methods, but at greater computational and memory costs.

<NPL>, propose an algorithm for accelerating intersection testing of a large collection of rays with a large scene database. The strategy utilizes bounding hierarchies over both the cast rays as well as the scene database. The ray hierarchy construction is based on line space concepts. <CIT> describes identifying a plurality of rays for a frame; defining an oriented bounding box for at least a portion of the rays using an average ray direction of all rays and two other orthogonal vectors forming; generating a ray hierarchy based upon a portion of the rays in the oriented bounding box; and simultaneously traversing the ray hierarchy and a hierarchy of objects, utilizing at least one processor. <NPL>), describe an algorithm based on a ray-space hierarchy, proposed to handle truly dynamic scenes without the need to rebuild or update the scene hierarchy.

The invention, in its various aspects, is as described in the appended claims.

Some aspects of the disclosure include systems and methods for grouping rays into sets according to their directions. In some cases, the rays of the directional sets may then be organized into a hierarchy according to their origins and bounding cones are generated for the hierarchy nodes. The resulting bounding cone hierarchy may be intersected with a bounding volume hierarchy or other scene hierarchy.

According to the invention there is provided a method according to claim <NUM>.

Preferably the directional ranges of the directional groups are predetermined to partition at least a portion of a directional sphere.

The claimed method further comprising generating a conical boundary for the rays of a directional group of the plurality of directional groups.

The claimed method further comprises the step of intersecting the rays with a scene hierarchy comprises intersecting the conical boundary with a bounding volume of the scene hierarchy to test if a ray contained in the conical boundary may intersect with a scene element contained in the bounding volume.

The claimed method further comprises the step of generating the conical boundary comprises:.

Preferably the method further comprises:.

More preferably, the method further comprises:.

In a preferred embodiment, the method further comprises:.

Preferably the method further comprises storing the rays in a bounding cone hierarchy comprising a plurality of levels, where each level of the plurality of levels comprises directional subgroups or origination subgroups.

According to the present invention there is provided a non-transitory computer readable medium according to claim <NUM>.

According to claim <NUM> the instruction set is further configured to cause the ray tracing renderer to perform the step of generating a conical boundary for the rays of a directional group of the plurality of directional groups.

According to claim <NUM> the instruction set is further configured to cause the ray tracing renderer to perform the step of intersecting the rays with a scene hierarchy to make an image, wherein the step comprises intersecting the conical boundary with a bounding volume of the scene hierarchy to test if a ray contained in the conical boundary may intersect with a scene element contained in the bounding volume.

According to claim <NUM> the step of generating the conical boundary comprises:.

Preferably the instruction set is further configured to cause the ray tracing renderer to perform the steps of:.

Preferably the instruction set is further configured to cause the ray tracing renderer to perform the step of:.

More preferably the instruction set is further configured to cause the ray tracing renderer to perform the step of:.

In a preferred embodiment the instruction set is further configured to cause the ray tracing renderer to perform the steps of:.

Preferably the instruction set is further configured to cause the ray tracing renderer to perform the step of storing the rays in a bounding cone hierarchy comprising a plurality of levels, where each level of the plurality of levels comprises directional subgroups or origination subgroups.

According to the present invention there is provided a system according to claim <NUM>.

According to claim <NUM> the program is further configured to cause the processor to perform the step of generating a conical boundary for the rays of a directional group of the plurality of directional groups.

Preferably the program is further configured to cause the processor to perform the steps of:.

Preferably the program is further configured to cause the processor to perform the step of:.

In one preferred embodiment the program is further configured to cause the processor to perform the step of:.

In a further preferred embodiment the program is further configured to cause the processor to perform the steps of:.

In another preferred embodiment the program is further configured to cause the processor to perform the step of storing the rays in a bounding cone hierarchy comprising a plurality of levels, where each level of the plurality of levels comprises directional subgroups or origination subgroups.

Other features and aspects will become apparent from the following detailed description, taken in conjunction with the accompanying figures. The summary is not intended to limit the scope of the application, which is defined solely by the claims attached hereto. It will be readily apparent to the skilled person that any of the preferred features described above can be used in combination with any of the other preferred features unless expressly stated otherwise.

The figures are provided for purposes of illustration only and merely depict typical or example embodiments. These figures are provided to facilitate the reader's understanding and shall not be considered limiting of the breadth, scope, or applicability of the invention.

Tracing rays or cone, one at a time, is memory and processing intensive. Even with a scene hierarchy, large numbers of rays require high amounts of memory bandwidth to traverse the queries across scene nodes and perform the large number of intersection computations.

<FIG> illustrates an example method for intersecting rays with a scene in a ray tracing scene rendering system. In step <NUM>, rays are obtained for processing. This may include obtaining rays <NUM> by generating camera rays, generating reflection rays, generating refraction rays, generating shadow rays, generating light rays, or generating any other rays utilized during conventional ray tracing rendering processes. The obtained rays may be a single ray type or a mixture of different ray types. In some cases, the step of obtaining rays <NUM> includes loading all of the rays that will be used in the method into memory. In other cases, subsets of the entire set of rays may be loaded into memory for iterative processing.

In step <NUM>, the rays are organized or classified into directional groups according to the rays' directions. Each ray may be described as a vector comprising an origin in a three-dimensional space, and a three-dimensional direction. Each directional group comprises rays having directions falling within a three-dimensional directional boundary for the directional group. Conceptually, the directional sphere, or a portion thereof, is partitioned into boundaries. The rays are grouped into the directional groups according to their encompassing boundaries. The grouping may be performed based only on the direction of the rays without regard to their origins.

As an example, <FIG> shows a unit directional sphere that illustrates the grouping <NUM> of rays into directional groups. The unit sphere <NUM> is partitioned into a plurality of directional ranges <NUM>, <NUM>, <NUM>. The rays' directions are then used to group the rays into the corresponding directional ranges. For example, rays <NUM> having a direction falling within the range <NUM> are grouped into a first directional group; rays <NUM> having a direction falling within the range <NUM> are grouped into a second directional group; and rays <NUM> having a direction falling within the range <NUM> are grouped into a third directional group.

In the illustrated case, the directional sphere is partitioned into the boundaries subtended by a truncated icosahedron, and is therefore composed of pentagonal ranges <NUM> and hexagonal ranges <NUM>. In other cases, the directional sphere can be partitioned into ranges in other manners - for example, other polyhedra may be employed, or the sphere can be partitioned into irregularly shaped ranges. In still further cases, only a portion of the directional sphere is used. For example, for camera rays, the hemisphere facing the scene may be partitioned for directional ray grouping.

Although the rays <NUM>, <NUM>, and <NUM> are illustrated as having a common origin, rays may be organized into directional groups without regard to origin. For example, the rays may be stored as data elements having an origin and a direction. Alternatively, the rays may have their directions determined from their native storage format. For example, in step <NUM>, the rays may be temporarily translated to a common origin for organization into the directional groups. As another example, in step <NUM>, the direction of each ray may be independently evaluated in a spherical coordinate system having a common origin to the ray. Any other method of evaluating the rays' directions may also be used.

In some cases, the directional groups may have a maximum number of rays per group. The maximum number of rays may be determined according to various considerations, such as coherence requirements and processing time. For example, a maximum number of between <NUM> million to <NUM> million may be suitable to provide sufficient coherence for ray tracing rendering without excessive processing time requirements. When a maximum number of rays per group is employed and a directional group is filled, additional directional groups corresponding to the same directional range may be used to store additional rays. Alternatively, additional rays may be discarded or saved for a future processing iteration.

In the implementation illustrated in <FIG> , the directional groups have predetermined directional boundaries. In other implementations, the boundaries for the directional groups may be determined during ray processing. In one implementation, directional groups are added until a predetermined number of groups are reached. For example, when a group has reached a certain number of rays, the group may be partitioned. This process may continue until the maximum number of directional groups are reached.

Step <NUM> may continue until any of various conditions are met. For example, in some cases, step <NUM> continues until all rays obtained in step <NUM> are organized into directional groups. In other cases, step <NUM> continues until a predetermined number of directional groups are filled. In still further cases, step <NUM> continues until at least one directional group for each directional range is filled.

In other implementations, steps <NUM> and <NUM> may be performed simultaneously. For example, every time a ray is generated during ray tracing, a method may be called to place that ray into a directional group. In these implementations, each time a directional group is filled, it may be organized into a bounding cone hierarchy (as described below) and intersected with the scene.

After step <NUM>, the directional groups are organized into a bounding cone hierarchy. <FIG> illustrates an example of a bounding cone hierarchy data structure <NUM> of the type that may be generated in step <NUM>. Bounding cone hierarchy <NUM> has a tree structure having a root <NUM> comprising one of the directional groups generated in step <NUM>. The leaf nodes of the tree <NUM> are the individual rays <NUM>,. , <NUM> of the directional group <NUM>. In other implementations, the leaf nodes of the tree <NUM> are the lowest level of origin subgroups (as described below). The rays are further contained in one or more subset levels <NUM>, <NUM>, <NUM> of origin-based sub-groups.

Each set of daughter subgroups is a sorting of the parent group by origin. For example, directional group <NUM> is sorted into N daughter origin subgroups <NUM>, <NUM>,. Origin subgroup <NUM> is sorted into M daughter origin subgroups <NUM>, <NUM>. Origin subgroup <NUM> is sorted into R daughter origin subgroups <NUM>, <NUM>, and so on until ray nodes <NUM>,. In some implementations, each group has two daughter subgroups (i.e. N, M, R ,. In other implementations, the number of daughter subgroups is a predetermined power of two, or some other integer. The sorting of the rays into the origin subgroups may be performed in various manners. For example, various selection algorithms, such as partitioned-based general selection algorithms, or nth element selection algorithms may be used to sort or partially sort the rays in a parent group into daughter subgroups.

In the illustrated tree <NUM>, only three levels of origin subgroups are present. In other implementations, greater or fewer levels may be employed. In a particular implementation, each node has two daughter nodes and there are three or four levels (to provide <NUM> or <NUM> origin subgroup leafs).

Additionally, in some implementations the sub-levels <NUM>, <NUM>, <NUM> may be sorted based on direction as well as origin. For example, level <NUM> may be based on further partitioning of the origin subgroups <NUM>, <NUM>, <NUM> into directional subgroups. Indeed, the levels of the hierarchy may alternate in any order of directional or origin based groupings.

The bounding cone hierarchy <NUM> further comprises a bounding cone for each node of the tree. In some cases, the bounding cones are circular cones generated to encompass the rays contained in the node. <FIG> illustrates an example of a bounding cone. In this example, rays <NUM>, <NUM>, <NUM>, and <NUM> are reflection or refraction rays with origins located on scene objects <NUM> or <NUM> in the scene <NUM>. In particular, the rays <NUM>, <NUM>, <NUM>, and <NUM> are the members of a directional group or an origin subgroup. A bounding cone <NUM> for the set of rays is generated to encompass the rays <NUM>,<NUM>,<NUM>,<NUM>.

The bounding cone <NUM> is generated by finding an axis <NUM> for the cone by averaging the rays <NUM>, <NUM>, <NUM>, <NUM> of the group. Then, the ray having the highest deviation (ray <NUM> in <FIG> ) from the axis <NUM> is used to define a circular boundary <NUM> for the cone. The cone is then defined by extending the boundary ray <NUM> to an apex <NUM> and generating a right circular cone <NUM> about the axis <NUM> with the apex <NUM> and a solid angle subtending boundary <NUM>. In some cases, the bounding cone <NUM> may be truncated at the closest ray origin to the apex <NUM> in the direction defined by the axis <NUM> (i.e., at the origin of ray <NUM>, <NUM>, or <NUM>). When the bounding cone <NUM> is truncated, a circular base may be defined perpendicular to the axis <NUM> and surrounding the closest ray origin(s) so that the truncated cone contains all ray origins. The truncated cone may aid in intersection testing by reducing the cone's bounds. In other implementations, other cone types may be used to generate the bounding cones. For example, oblique circular cones or pyramids - truncated or not - may be used as bounding cones. Additionally, truncated cones may have bases that are oblique to the cones' axes.

<FIG> illustrates an example method of creating a bounding ray cone hierarchy. In step <NUM>, a batch of rays is obtained. The batch of rays may be fixed in size or adaptable. In a specific implementation, the batch has a fixed size of up to <NUM> million rays.

In step <NUM>, the batch of rays is partitioned into a fixed number of directional I groups. In a specific implementation, the batch of rays is partitioned into <NUM> groups by direction.

In step <NUM>, each of the directional groups are partitioned by origin into fixed-size subgroups. In a specific implementation, each directional group is partitioned into origin-based subgroups of <NUM>,<NUM> rays.

In step <NUM>, each of the origin-based subgroups is partitioned into fixed-size directional sub-subgroups. In a specific implementation, each origin-based subgroup is portioned into directional sub-subgroups of <NUM> rays.

Returning to <FIG> , in step <NUM>, a scene bounding hierarchy is obtained. The scene bounding hierarchy may comprise a tree of bounding volumes for the scene objects, such as spheres, axis-aligned bounding boxes, oriented bounding boxes, or other bounding volumes.

Various methods for traversing the bounding cone hierarchy and the scene bounding hierarchy for intersection detection may be employed. For example, the scene hierarchy may be provided as a stream of bounding volumes, and the cone hierarchy may be intersected with each element of the stream.

As another example, the scene bounding hierarchy may be traversed in a hierarchical manner. A particular implementation is illustrated in <FIG>. In this method, a cone <NUM> is selected from the current level of the bounding cone hierarchy for testing against the bounding volumes of the current level of the scene bounding hierarchy. In step <NUM>, the bounding volumes of the current level are tested against selected bounding cone. In some cases, the bounding cones are tested in order from front to back, along the direction of the selected cone's axis.

When an intersection is detected between a bounding cone and a scene bounding volume, then the system tests the bounding cone's daughters against the scene bounding volume, or tests the scene bounding volume's daughters against the bounding cone. In step <NUM>, the system determines if the bounding cone or the bounding volume is larger. Many tests for size may be employed. For example, the bounding cone's size may be taken to be the bounding cone's volume, the length of the bounding cone's axis, or the area of the cone's base. The bounding volume's size may be the volume of the bounding volume, the length of one of the bounding volume's axes (such as the length of the longest axis), or the area of a face of the bounding volume (such as the face that first intersects with the cone's axis).

If the bounding cone is larger, then the system tests the cone's daughter nodes against the bounding volume in step <NUM>. If the bounding volume is larger, then the system tests the volume's daughter nodes against the bounding cone in step <NUM>. If further intersections are detected at the daughter levels, the system repeats the determination <NUM> of which bounding shape is larger and descends into the larger object's daughters.

Processing improvements in other computer graphics systems may be obtained simply from completion of step <NUM>. For example, the bounding cone hierarchy may be used in global illumination algorithms. Additionally, simply reordering the rays according to direction and, optionally, position may provide processing advantages. For example, performing ray tracing against a scene hierarchy with the rays reordered according to direction and position may provide processing improvements over standard ray tracing algorithms.

Where components or modules are implemented in whole or in part using software, in one embodiment, these software elements can be implemented to operate with a computing or processing module capable of carrying out the functionality described with respect thereto. After reading this description, it will become apparent to a person skilled in the relevant art how to implement the disclosure using other computing modules or architectures.

<FIG> presents an exemplary diagram of a system for providing a ray cone hierarchy renderer. The system includes workstation <NUM>, display <NUM>, input device <NUM>, network <NUM>, server <NUM>, and data <NUM>. Workstation <NUM> includes processor <NUM>, memory <NUM>, and graphics processing unit (GPU) <NUM>. In addition to memory <NUM>, the workstation <NUM> may include other non-transitory computer readable media, such as non-volatile storage devices. Various data elements and programs may be stored in memory <NUM>. For example, the rendering program <NUM> may be stored and executed from memory <NUM>. Data that is used by the rendering program <NUM> may also be stored in memory <NUM>. As described above, such data may include rays <NUM> and scene geometry data <NUM>. In some cases, all rays <NUM> that will be used by rendering program <NUM> are stored in memory <NUM>. In other cases, rays <NUM> are a subset of the total rays to be processed. Other rays may streamed to the workstation <NUM> over the network <NUM> or may be stored in local non-volatile storage. Additionally, the memory <NUM> may store the rendering program's <NUM> output image <NUM>.

Workstation <NUM> may comprise any computing device such as a rackmount server, desktop computer, or mobile computer. A system user may utilize input device <NUM>, for example a keyboard and mouse, to direct the operation of rendering application <NUM> executing from memory <NUM> by processor <NUM>. Additionally, aspects of rendering application <NUM> may be executed by GPU <NUM>. In some implementations, scene data <NUM> or ray data <NUM> may be received over network <NUM> from data store <NUM> or server <NUM>. Alternatively, some or all of the scene data <NUM> or ray data <NUM> may be generated in the workstation <NUM>. Network <NUM> may be a high speed network suitable for high performance computing (HPC), for example a <NUM> GigE network or an InfiniBand network.

Once completed, output image <NUM> may also be copied to non-volatile storage. In some cases, output image <NUM> is only a single frame. However, in alternative embodiments, the scene data may further include motion data for object geometry <NUM>, in which case several animation frames may be rendered by rendering application <NUM>.

Moreover, some embodiments may render multiple frames of the same scene concurrently, for example to provide alternative camera angles or to provide stereoscopic rendering. Other data may also be stored in data <NUM>, for example virtual camera parameters and camera paths.

While various implementations have been described above, it should be understood that they have been presented by way of example only, and not of limitation. Likewise, the various diagrams may depict an example architectural or other configuration for the disclosure, which is done to aid in understanding the features and functionality that can be included in the disclosure. The disclosure is not restricted to the illustrated example architectures or configurations, but the desired features can be implemented using a variety of alternative architectures and configurations. Indeed, it will be apparent to one of skill in the art how alternative functional, logical or physical partitioning and configurations can be implemented to implement the desired features of the present application. Also, a multitude of different constituent module names other than those depicted herein can be applied to the various partitions. Additionally, with regard to flow diagrams, operational descriptions and method claims, the order in which the steps are presented herein shall not mandate that various embodiments be implemented to perform the recited functionality in the same order unless the context dictates otherwise.

Although described above in terms of various exemplary embodiments and implementations, it should be understood that the various features, aspects and functionality described in one or more of the individual embodiments are not limited in their applicability to the particular embodiment with which they are described, but instead can be applied, alone or in various combinations, to one or more of the other embodiments of the application, whether or not such embodiments are described and whether or not such features are presented as being a part of a described embodiment. Thus, the breadth and scope of the present application should not be limited by any of the above-described exemplary embodiments.

Terms and phrases used in this document, and variations thereof, unless otherwise expressly stated, should be construed as open ended as opposed to limiting. As examples of the foregoing: the term "including" should be read as meaning "including, without limitation" or the like; the term "example" is used to provide exemplary instances of the item in discussion, not an exhaustive or limiting list thereof; the terms "a" or "an" should be read as meaning "at least one," "one or more" or the like; and adjectives such as "conventional," "traditional," "normal," "standard," "known" and terms of similar meaning should not be construed as limiting the item described to a given time period or to an item available as of a given time, but instead should be read to encompass conventional, traditional, normal, or standard technologies that may be available or known now or at any time in the future. Likewise, where this document refers to technologies that would be apparent or known to one of ordinary skill in the art, such technologies encompass those apparent or known to the skilled artisan now or at any time in the future.

The presence of broadening words and phrases such as "one or more," "at least," "but not limited to" or other like phrases in some instances shall not be read to mean that the narrower case is intended or required in instances where such broadening phrases may be absent. The use of the term "module" does not imply that the components or functionality described or claimed as part of the module are all configured in a common package. Indeed, any or all of the various components of a module, whether control logic or other components, can be combined in a single package or separately maintained and can further be distributed in multiple groupings or packages or across multiple locations.

Claim 1:
A computer-implemented method, comprising:
obtaining a ray of a set of rays, the ray having an origin and a direction;
organizing the rays into a directional group of a plurality of directional groups, each directional group having a corresponding directional range and comprising rays of the set of rays having directions within the corresponding directional range; and
generating a conical boundary for the rays of a directional group of the plurality of directional groups;
intersecting the rays with a scene hierarchy to make an image by:
intersecting the conical boundary with a bounding volume of the scene hierarchy to test if a ray contained in the conical boundary may intersect with a scene element contained in the bounding volume; and
wherein the step of generating the conical boundary comprises:
determining an axis for the conical boundary, the axis comprising the average direction of the rays of the directional group;
determining a set of deviations of the rays of the directional group from the average direction;
generating a circular boundary for the conical boundary, the circular boundary encompassing a ray having a greatest deviation from the average direction;
generating an apex for the conical boundary such that the conical boundary comprising the circular boundary and the apex encloses the rays of the directional group; and
generating a base of the conical boundary such that the base encircles a ray origin of a ray of the directional group that is closest to the apex in the average direction dimension.