RAY SHADOWING METHOD UTILIZING GEOMETRICAL STENCILS
Aspects comprise a ray tracing shadowing 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 having stencil based shadowing, implemented on a grid of cells, comprising the steps of:
a. generating data structure of a scene, wherein said data structure is based on a grid of cells;
b. mapping scene objects onto cells in the grid of cells;
c. generating shadow stencils at cells, said shadow stencils cast by a light source;
d. generating local segments of shadow rays at cells in the grid of cells, said shadow rays having a direction from a light source;
e. at each data filled cell in the grid of cells, testing each said local ray segment of a shadow ray for a hit with a shadow stencil;
wherein in the event of a hit, the primary point of intersection associated with the tested local ray segment is in shadow; and
wherein in the event of no hit, the tested ray segment is further tested for shadow by intersection tests with local objects.
2 . The method of claim 1 , wherein said grid of cells comprises uniform cells.
3 . The method of claim 1 , wherein said grid of cells is generated in a preprocessing stage.
4 . The method of claim 1 , wherein said shadow stencils are generated in a preprocessing stage.
5 . The method of claim 1 , wherein for small and medium models the said method is implemented on a shared memory parallel computing system.
6 . The method of claim 1 , wherein shadow stencils are reconstructed only when there are changes in the scene or light sources.
7 . The method of claim 1 , wherein the object data of a scene are represented by polygon model or by geometric model.
8 . The method of claim 1 , wherein for large models the said method is implemented on a distributed memory parallel computing system.
9 . The method of claim 1 , wherein said shadow stencils are projections of non-local objects cast on a cell's facets by a light source.
10 . The method of claim 1 , wherein shadow rays originate at a light source and pass through the primary points of intersection, wherein said primary points of intersection are previously generated by the primary ray shooting.
11 . The method of claim 1 , wherein at each data filled cell, local ray segments are generated for those shadow rays that pass through the local primary intersection points.
12 . The method of claim 1 , wherein in each data filled cell, the number of shadow ray segments substantially equals the number of primary intersection points, and wherein each local segment of a shadow ray is associated with a different primary intersection point.
13 . The method of claim 11 , wherein a hit between local segments of shadow rays and shadow stencil indicates that said primary intersection points are in shadow.
14 . The method of claim 1 , wherein the said method is implementable on general purpose processors, special purpose processors, multicore processors and GPUs.
15 . The method of claim 1 , wherein all shadowing tests are strictly local to a cell.
16 . The method of claim 13 , wherein in the event of further testing, when an intersection is found located amid primary intersection point and the light source, it indicates that the said primary intersection point is in shadow.
17 . The method of claim 1 , wherein the shadowing process has the characteristics of a static process locality.
18 . The method of claim 1 , wherein the shadowing workload in a cell can be pre-calculated based on the surface area of the shadow stencil and on the number of local objects in a cell.
19 . The method of claim 18 , wherein load balancing of the system is achievable, and such load balancing is assisted by pre-calculating the distribution of shadowing workloads among cells.
20 . The method of claim 1 , wherein the said method is implemented on one or more computers selected from the group consisting of a PC-level computer, information server computer, cloud server computer, parallel computer, laptop, portable processing system, tablet, Smartphone, and any computer-based machine.