Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
2000-02-23
2004-03-09
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
C345S582000, C345S606000, C345S609000
Reexamination Certificate
active
06704017
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computerized graphics systems in general, and in particular to computerized graphics systems for rendering images of three-dimensional terrain.
BACKGROUND OF THE INVENTION
Rendering terrain based on data representations of three-dimensional (3D) topographies for viewing on a computer display is known in the art. Typically, a three-dimensional terrain is represented as a collection of data points and stored in a data structure. Terrain rendering techniques generally apply some form of ray tracing to a set of data points. Known ray tracing techniques involve tracing a ray from the view point through each pixel in the display until the ray reaches the surface of the data. The primary disadvantage of ray tracing is that its implementation is quite slow, taking minutes or hours to produce an image of a single scene, even using state of the art hardware and software.
SUMMARY OF THE INVENTION
The present invention seeks to provide novel apparatus and methods for rendering three-dimensional terrains that do not require ray tracing for all data points in a viewable area. The present invention provides an improved system which overcomes the known disadvantages of the prior art as discussed above. The rendering is performed using a variation on known ray tracing techniques where a first ray is traced for a first display pixel, and adjacent pixels are calculated by moving the point of contact between the first ray and the surface of the data to a point on a ray that goes through an adjacent pixel. The point is then moved forward or backward along the new ray until it contacts the surface of the data.
There is thus provided in accordance with a preferred embodiment of the present invention a method for rendering a three-dimensional terrain, the method including providing at least one previous display pixel having a previous ray from a point of view through the at least one previous display pixel to a previous terrain unit intersecting an axis of the previous ray, the previous ray having a length, and computing a subsequent ray from the point of view through a subsequent display pixel, whereby the subsequent ray has a length equal to the length of the previous ray.
Further in accordance with a preferred embodiment of the present invention the providing step includes tracing the at least one previous ray through the at least one previous display pixel.
Still further in accordance with a preferred embodiment of the present invention the providing step includes previously computing the at least one previous ray.
Additionally in accordance with a preferred embodiment of the present invention the providing step includes providing a plurality of the previous display pixels, and wherein the computing step includes computing a subsequent ray the subsequent display pixel is adjacent to at least two of the plurality of the previous display pixels, and whereby the subsequent ray has a length equal to the shortest of the lengths of the previous rays of the plurality of previous display pixels to which the subsequent display pixel is adjacent.
Moreover in accordance with a preferred embodiment of the present invention the preceding claims and further including the step of maintaining any of the lengths in a Z-buffer, and the providing step includes retrieving any of the lengths from the Z-buffer.
Further in accordance with a preferred embodiment of the present invention the length of the subsequent ray is adjusted for a subsequent terrain unit intersecting an axis of the subsequent ray.
Still further in accordance with a preferred embodiment of the present invention the adjusting step includes comparing a position of a ray point at an end of the subsequent ray to an elevation of the subsequent terrain unit, correcting the length of the subsequent ray by either of increasing the length of the subsequent ray if the position of the ray point is above the subsequent terrain unit, and decreasing the length of the subsequent ray if the position of the ray point is below the subsequent terrain unit, and repeating the correcting step until the ray point is in propinquity to the subsequent terrain unit.
Additionally in accordance With a preferred embodiment of the present invention the repeating step includes repeating until the ray point is in propinquity to the subsequent terrain unit within a predetermined tolerance.
Moreover in accordance with a preferred embodiment of the present invention the correcting step includes increasing the length of the subsequent ray by a factor, and incrementing the factor by a base value subsequent to the increasing step.
Further in accordance with a preferred embodiment of the present invention the incrementing step includes providing the base value equal to V
r
+2
d
, the V
r
, is equal to a unit vector value of the subsequent ray and d is equal to Log
2
of the length of the subsequent ray.
Still further in accordance with a preferred embodiment of the present invention the correcting step includes decreasing the length of the subsequent ray by a base value.
Additionally in accordance with a preferred embodiment of the present invention the correcting step includes providing the base value equal to V
r
+2
d
, the V
r
, is equal to a unit vector value of the subsequent ray and d is equal to Log
2
of the length of the subsequent ray.
There is also provided in accordance with a preferred embodiment of the present invention a method of determining a scan direction, the method including providing a perspective axis passing through a view point and being substantially perpendicular to a data plane, the data plane includes a plurality of terrain units of a uniform elevation, providing a perspective point at an intersection of the perspective axis and a display plane of a display, rotating the perspective axis about the perspective point until the perspective axis lies in the display plane, thereby providing a longitudinal quadrant axis, providing a latitudinal quadrant axis perpendicular to the longitudinal quadrant axis and intersecting the longitudinal quadrant axis at the perspective point, and setting the scan direction as being either of away from the perspective point if the view point is above the perspective point, and toward the perspective point if the view point is below the perspective point.
Further in accordance with a preferred embodiment of the present invention either of the quadrant axes are moved in the display plane until the perspective point meets an edge of the display.
Still further in accordance with a preferred embodiment of the present invention either of the perspective axis and the display plane are adjusted until the perspective axis and the display plane intersect.
There is also provided in accordance with a preferred embodiment of the present invention a method of storing a terrain image in a data structure, the method including providing the terrain image in at least one resolution, dividing each resolution into at least one tile including at least one picture element.
Further in accordance with a preferred embodiment of the present invention either of a color attribute and an elevation attribute are stored for each of the picture elements.
Still further in accordance with a preferred embodiment of the present invention the dividing step includes providing the tile with a fixed number of the picture elements.
Additionally in accordance with a preferred embodiment of the present invention the providing the terrain image step includes providing a plurality of the resolutions and further including providing at least one pointer from a parent tile of a first of the plurality of the resolutions to a child tile of a second of the plurality of the resolutions, the first of the plurality of the resolutions is of lesser detail than the second of the plurality of the resolutions.
Moreover in accordance with a preferred embodiment of the present invention the first of the plurality of the resolutions has four times more detail than the second of the plurality of the resolutions.
There is also
Shor Ofer
Yaron Ronnie
Brier Jeffery
Duane Morris LLP
Good-Johnson Motilewa
Skyline Software Systems Ltd.
LandOfFree
Method for determining scan direction for three-dimensional... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for determining scan direction for three-dimensional..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for determining scan direction for three-dimensional... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3195599