Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
2000-05-17
2003-07-22
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
C345S420000, C345S423000, C345S424000, C345S619000, C345S645000
Reexamination Certificate
active
06597359
ABSTRACT:
BACKGROUND OF THE INVENTION
Technical Field of the Invention
This invention most generally relates to the process of rendering a synthetic image with a computer. More particularly, the present invention relates to an apparatus and process of ray tracing.
Background of the Invention
Ray Tracing
Ray tracing is one of several methods of rendering an image from a computer scene description. It is distinguished from other methods by the high quality of the resulting images, which can include shadows, reflections, and refractive effects.
FIG. 1
illustrates the basic concept behind ray tracing. In computer rendering, a bitmap of pixels
3
can be thought of as suspended a short distance in front of an eye point
1
. The task of the renderer is to find the color value for each bitmap pixel that represents the light seen from the eye point coming from the scene in the direction of that pixel.
The ray tracing method accomplishes this for each pixel by tracing a ray from the eye point through that pixel into the scene, then determining the qualities of the light emanating from the scene backwards along the ray towards the eye point. Ray
2
in
FIG. 1
is an example of this. Ray
2
is traced in the view direction corresponding to the center of the fourth pixel from the right in the third row down. The ray tracer performs some computations to eventually determine that the first scene object ray
2
intersects is sphere
4
. The ray tracer then computes the light color and intensity reflected by the sphere backwards along the ray from the intersection point. This light color and intensity then becomes one data point of a known color value within the bitmap, in this case at the center of the fourth pixel from the right in the third row down.
The fundamental operation in a ray tracer is to find the apparent color and intensity of the light coming back along a ray. This is known as “tracing” the ray.
Ray Recursion
Note that this operation of tracing a ray does not require that the ray start at the eye point, or any other point. The name “eye ray” is commonly used to distinguish rays that originate at the eye point from those that originate elsewhere. The ability to find the light coming to any specific point from any specific direction is used inside the ray tracer to produce effects like shadows, refraction, and transparent objects.
FIG. 2
illustrates how a ray tracer might create and trace additional rays as part of the overall effort of tracing a single eye ray. As in
FIG. 1
, ray
2
is traced from the eye point
1
. The first scene object intersected by ray
2
is the transparent object
5
. The light seen from a point on a transparent object comes from two possible directions, the light reflected off the surface and the light transmitted through the object. The ray tracer creates and traces ray
6
to determine that portion of ray
2
resulting from the transmitted light, and ray
9
to determine the reflected portion. The result for ray
2
then becomes a weighted sum of the results for rays
6
and
9
.
This process continues deeper. The value of ray
6
is a combination of the internal reflection, solved by tracing ray
8
, and the transmitted light entering object
5
, solved by ray
7
. Ray
7
in turn strikes the reflective object
10
, which requires tracing ray
11
in the direction the reflected light comes from. Meanwhile ray
9
intersects the opaque object
12
. The light perceived backwards along ray
9
depends on the illumination at the point where ray
9
intersects object
12
. Ray
13
is traced in a slightly different manner to determine whether the light
14
shines on the point on object
12
or whether the light is occluded by another object. In this case no object occludes the light, and light
14
is therefore taken into account in determining the perceived light back along ray
9
. If the light had been occluded, then it would not have been taken into account. This would have yielded the visual effect of the point on object
12
being in a shadow from light source
14
.
Note that ray
13
is traced in a different manner. The ray tracer does not solve for the light coming back along the ray, but rather whether the ray makes it to the light source or not. This type of ray is commonly referred to as a “light ray”.
Recursively launching additional rays as part of solving a previous ray is how ray tracers simulate many of the effects they are well known for. In
FIG. 2
, rays
9
and
11
provide the effect of reflective objects. Rays
6
and
7
provide transparency, ray
8
internal reflections, and launching light rays such as ray
13
provides for shadows.
Finding Ray/Object Intersections
Part of a ray tracer's job in tracing a ray is to determine which scene object, if any, is the first intersected by the ray. The simplistic approach is to check the ray against every object in the scene. While this works, it requires far too much computation to be a useful method. All “real world” ray tracers employ some sort of speedup technique aimed at eliminating unnecessary ray/object intersection checks.
There are two broad classes of techniques for reducing the number of ray/object intersection checks to perform. These are called “object hierarchy” and “space subdivision”. The object hierarchy techniques group a set of objects together and find a simple bounding volume that encloses the whole group, like a sphere or a box. Rays are then intersected with the bounding volume. If the ray does not intersect the bounding volume then there is no need to check for intersection with the objects inside the bounding volume, since none of these objects could possibly intersect the ray.
The bounding volumes can also be arranged in a hierarchy. Thus, a bounding volume may contain scene objects and other bounding volumes. A scene may then consist of only a small number of bounding volumes at the top level. Intersection checks are only performed on the objects within a bounding volume if the ray is found to intersect that bounding volume.
Object hierarchy techniques vary from each other by how the objects within a bounding volume are chosen, the shape of the bounding volumes, how the bounding volumes are found, etc.
The space subdivision techniques subdivide the scene volume instead of the list of objects. The scene space is subdivided into chunks. The data for each chunk contains a list of all the scene objects that could result in a positive ray/object intersection check within the chunk. As a ray is traced, the chunk database is traversed in order along the ray. The ray is checked for intersection with all the objects in each chunk before proceeding to the next chunk along the ray. Only a small number of ray/object intersection checks are performed if the chunk only contains a small number of objects.
Space subdivision techniques can also be static or dynamic. In a static system, all the chunks are found and their object lists determined before any rays are traced. A dynamic system allows chunks to be created, deleted, and otherwise rearranged dynamically, driven by rays being traced through the scene. Static systems may require less overall computation to generate the chunks and their lists of objects since this is all done once up front. The chunks in static systems may also be more regular, thereby decreasing the computation required in determining the next chunk along a ray.
The main advantage of dynamic systems is that they only create complexity (requiring computation and memory) when and where it is needed, based on the ray activity and other criteria. For example, the space around a complex object behind a wall from the eye point may never be subdivided if no rays are traced behind the wall. Some static space subdivision techniques and generally all dynamic techniques are hierarchical. If an existing chunk is deemed too complex, it is subdivided into two or more sub-chunks. This process is repeated on the sub-chunks until they are no longer too complex to require subdivision, or some arbitrary subdivision limit has been reached.
An example of a static non-hierarchic
Maine & Asmus
Nguyen Kimbinh T.
Raychip, Inc.
Zimmerman Mark
LandOfFree
Hierarchical space subdivision hardware for ray tracing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hierarchical space subdivision hardware for ray tracing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hierarchical space subdivision hardware for ray tracing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3042145