Direct ray tracing of 3D scenes

A computer program product directly loadable into an internal memory of a computer for executing a method for determining possible spatial intersections between an initial set of rays and an initial set of primitives for the purpose of creating a computer graphics image of a three dimensional scene using a deterministic approach, the method comprising:

• a) Determining a multidimensional space region related to the three dimensional scene comprising all primitives of the initial set of primitives;
• b) Testing if a halting criterion is met;
• if the halting criterion is met, determining intersections between the initial set of rays and the initial set of primitives by testing all possible ray/primitive intersections and continuing with step f);
• if the halting criterion is not met, continuing with step c);
• c) dividing the initial region into two or more subregions;
• d) determining for each one of the two or more subregions, a subset of rays from the initial set of rays which are intersecting the one of the two or more subregions;
• determining a subset of primitives from the initial set of primitives which are intersecting the one of the two or more subregions;
• and streaming all the rays of the initial set of rays or all the primitives of the initial set of primitives, wherein the streaming is performed in-place using up to three pivots;
• e) recursively repeating step b) for each one of the two or more subregions, wherein the initial region, the initial set of rays, and the initial set of primitives are respectively replaced by the subregion, the subset of rays and the subset of primitives;
• f) updating the spatial intersections;
• g) grouping rays into one or more packets, where the packets are defined as cones comprising a cone origin, a cone main direction and a cone angle, where the initial set of rays is replaced by the one or more packets;
• and
• h) triangle sorting per rendering pass.

A computer system for providing digital image data to a first interface and a second interface for obtaining information about a space to be imaged, the system using a method for determining possible spatial intersections between an initial set of rays and an initial set of primitives for the purpose of creating a computer graphics image of a three dimensional scene using a deterministic approach, the method comprising:

• a) Determining a multidimensional space region related to the three dimensional scene comprising all primitives of the initial set of primitives;
• b) Testing if a halting criterion is met;
• if the halting criterion is met, determining intersections between the initial set of rays and the initial set of primitives by testing all possible ray/primitive intersections and continuing with step f);
• if the halting criterion is not met, continuing with step c);
• c) dividing the initial region into two or more subregions;
• d) determining for each one of the two or more subregions, a subset of rays from the initial set of rays which are intersecting the one of the two or more subregions;
• determining a subset of primitives from the initial set of primitives which are intersecting the one of the two or more subregions;
• and streaming all the rays of the initial set of rays or all the primitives of the initial set of primitives, wherein the streaming is performed in-place using up to three pivots;
• e) recursively repeating step b) for each one of the two or more subregions, wherein the initial region, the initial set of rays, and the initial set of primitives are respectively replaced by the subregion, the subset of rays and the subset of primitives;
• f) updating the spatial intersections;
• g) grouping rays into one or more packets, where the packets are defined as cones comprising a cone origin, a cone main direction and a cone angle, where the initial set of rays is replaced by the one or more packets;
• and
• h) triangle sorting per rendering pass.

A method for determining possible spatial intersections between a first initial set of primitives and a second initial set of primitives for the purpose of creating a computer graphics image of a three dimensional scene using a deterministic approach, the method comprising:

• a) Determining a multidimensional space region related to the three dimensional scene that comprises all primitives of the first initial set of primitives;
• b) Testing if a halting criterion is met;
• if the halting criterion is met, determining intersections between the first initial set of primitives and the second initial set of primitives by testing all possible primitive/primitive intersections and continuing with step f);
• if the halting criterion is not met, continuing with step c);
• c) dividing the initial region into two or more subregions;
• d) determining for each one of the two or more subregions, a first subset of primitives from the first initial set of primitives which are intersecting the one of the two or more subregions;
• determining a second subset of primitives from the second initial set of primitives which are intersecting the one of the two or more subregions;
• and streaming all the rays of the initial set of rays or all the primitives of the initial set of primitives, wherein the streaming is performed in-place using up to three pivots;
• e) recursively repeating step b) for each one of the two or more subregions, wherein the initial region, the first initial set of primitives, and the second initial set of primitives are respectively replaced by the subregion, the first subset of primitives and the second subset of primitives;
• f) updating intersections;
• g) grouping rays into one or more packets, where the packets are defined as cones comprising a cone origin, a cone main direction and a cone angle, where the initial set of rays is replaced by the one or more packets;
• and
• h) triangle sorting per rendering pass.