Patent ID: 8115767

Claim:
A method, executable in a computer processor operable to render images for display on a human-perceptible display element, the rendering comprising processing of data corresponding to triangles, each triangle having edges, vertices and an associated triangle plane, and the displaying comprising the display of shadows in three-dimensional (3D) scenes, the shadows being displayed in relation to a simulated light source, the method comprising: executing, in the computer processor, a shadow volume creation method, the shadow volume creation method comprising: for each non-degenerated triangle used in image rendering: (1) computing, in the computer processor, a parameter d of a triangle as the dot product between the surface normal and the direction from an arbitrary point on the triangle plane to the light source; (2) creating, in the computer processor, shadow caps, the creating of shadow caps comprising: (a) if necessary, rendering, in the computer processor, the triangle to create a near cap of the shadow volume: (b) extending, in the computer processor, triangle vertices to infinity and inverting their orientation to render a far cap of the shadow volume, if necessary; (c) If d is negative, performing (a) and (b) in the computer processor with inverted vertex orientation to ensure correct ordering of shadow volume faces; and (3) in the computer processor, extruding to infinity each edge of the triangle for which the d parameter of a triangle being processed has a different sign than the d parameter for an adjacent triangle, and rendering the resulting quadrilateral, extruding also to infinity edges that do not have an adjacent triangle associated therewith, and again utilizing the positive or negative sign of parameter d to adjust vertex ordering, and further comprising: executing, in the computer processor, a bounding volume hierarchy (BVH) traversal method, the BVH method comprising: (a) starting with the root node holding the entire scene, and recursively traversing: (b) generating the shadow volume of the current node, the generating comprising generating the shadow volume of the bounding volume of the current node, instead of the actual volumes of the enclosed geometry: (c) testing the generated shadow volume for intersection with the viewing frustum; and if it does not intersect, skipping the children of this node; otherwise, performing, asynchronously, an occlusion query on the volume geometry, without writing to the stencil buffer; and depending on the query result, disregarding the children or recursively traverse; and (d) when a leaf node is reached and its node shadow volume is found to be visible, rendering the actual geometry shadow volume into the stencil buffer.