High Performance Ray Tracing Scene Graphs
AssigneeSURVICE Engineering Company
InventorAlexis Naveros
Life of this patent
Estimating the term…
Abstract
Systems and methods for high performance ray tracing scene graphs are provided by constructing a complex three dimensional special structure of sectors and nodes. Sectors are regions of space which can take any shape or size in three dimensional space. The non tree-based space partitioning structure allows rays to traverse the spatial structure to directly resolve the primitives they intersect. Traversal cost is efficiently minimized by constructing large sectors to contain empty space and constructing relatively smaller sectors to contain the geometric primitives. Each sector contains information associated with each of its surfaces including whether the surface leads to another sector or a node.
Claims11
A method for tracing rays through a computer generated three dimensional scene having a plurality of geometric primitives, comprising:
- initializing a data structure configured to store information related to the three dimensional scene;
- identifying a plurality of geometric primitives within the three dimensional scene;
- defining one or more three dimensional sectors, wherein each of the one or more three dimensional sectors contains at least one of the identified plurality of geometric primitives;
- storing information related to each of the one or more three dimensional sectors in the data structure;
- identifying one or more regions of contiguous empty space within the three dimensional scene;
- defining one or more three dimensional space sectors, wherein each of the one or more three dimensional space sectors contains an identified region of contiguous empty space;
- storing information related to each of the one or more three dimensional space sectors in the data structure;
- identifying a sector having a face that is contiguous with two or more neighboring sectors;
- defining a first node in association with a first portion of the face of the identified sector, the first node comprising an identifier that identifies a first neighboring sector;
- defining a second node in association with a second portion of the face of the identified sector, wherein the first portion of the face and the second portion of the face do not overlap, the second node comprising an identifier that identifies a second neighboring sector;
- storing information related to the first node and the second node in the data structure in association with the identified sector face.
A method for tracing a ray through a computer generated three dimensional scene having a plurality of geometric primitives, comprising:
- identifying a ray within the three dimensional scene;
- determining a first sector traversed by the ray;
- determining a first face of the first sector traversed by the ray;
- analyzing information associated with the first face to determine a path for the ray within the sector;
- calculating the result of an intersect test for the determined path of the ray to identify each geometric primitive within the first sector that the ray will intersect;
- determining a second face of the first sector traversed by the ray;
- analyzing information associated with the second face to determine a path for the ray outside of the sector;
- and
- determining a second sector the traversed by the ray based on the determined path of the ray.
Dependencies are inferred from the claim text.