Ray shooting method utilizing geometrical stencils
Aspects comprise a ray shooting method based on the data structure of a uniform grid of cells, and on local stencils in cells. The high traversal and construction costs of accelerating structures are cut down. The object's visibility from the viewpoint and from light sources, as well as the primary workload and its distribution among cells, are gained in the preprocessing stage and cached in stencils for runtime use. In runtime, the use of stencils allows a complete locality at each cell, for load balanced parallel processing.
1. A ray tracing method in a computer graphics system, having stencil based primary ray shooting, implemented on cells, comprising the steps of:
a preprocessing computing phase;
generating a data structure of cells wherein each cell represents a volumetric area by spatially dividing a 3D scene, wherein cell is a basic unit of processing and data locality;
distributing objects of the 3D scene into said cells based upon their location in the scene;
creating two dimensional shooting stencils cache data filled cells containing scene objects, wherein said shooting stencils cache data to enable locality of processing at each cell;
wherein the shooting stencils are a projection of 3D scene objects cast onto the facets of the volumetric areas of the cells;
a runtime computing phase;
in all cells having a shooting stencil, creating local segments of only those shooting primary rays that hit the shooting stencil by accessing said cache data;
in all cells having a shooting stencil, creating local segment of a shooting primary ray, finding a point of intersection between the local segment of a shooting ray and one of a plurality of objects located in a given cell being tested for intersection.
2. The method of claim 1 , wherein said data structure of cells comprises uniform grid of cells.
3. The method of claim 2 , wherein said grid of cells is generated in a preprocessing stage.
4. The method of claim 1 , wherein said shooting stencils are generated in a preprocessing stage.
5. The method of claim 1 , wherein said local segments of a shooting ray can be processed for intersection In any arbitrary order.
6. The method of claim 1 , wherein said shooting stencils are a 2D projection of objects, cast on cell facets.
7. The method of claim 1 , wherein each shooting ray comprises multiple segments, and each segment Is processed in a cell independently of segments in other cells.
8. The method of claim 1 , wherein the method is implemented on any computational-based machine selected from the group consisting of a PC-level computer, information server computer, cloud server computer, parallel computer, laptop, portable processing system, tablet, and smartphone.
9. The method of claim 1 , wherein the shooting workload in a cell can be pre-calculated based on the surface area of the shooting stencil.
10. The method of claim 1 , wherein the cells of a grid are processed in any arbitrary order for primary ray shooting.