System and method of image generation and encoding using primitive reprojection

• US 6,111,582 A
• Filed: 07/23/1997
• Issued: 08/29/2000
• Est. Priority Date: 12/20/1996
• Status: Expired due to Term

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Barry L. Jenkins
• Inventors: Jenkins, Barry L.
• Primary Examiner(s): Zimmerman, Mark K.
• Assistant Examiner(s): Sealey, Lance W.
• Application Number:
  US08/899,122
• Time in Patent Office: 1,133 Days
• Field of Search: 345/421, 345/422, 345/427
• US Class Current: 345/421
• CPC Class Codes: G06T 15/20 Perspective computation
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

A computer-implemented method of image generation that makes efficient use of reprojective techniques to reduce the cost of image generation. The method employs a technique of primitive reprojection in which convex graphics primitives are the reprojected elements. The visibility of elements known to be visible in a previous frame is first determined by transformation and depth-comparison rasterization of these elements. Regions of the image that may contain newly visible elements are located by occlusion-exposure transitions in the depth buffer and from incremental view volume motion. In these regions a depth-prioritized, data-access method of visible surface determination, spatial-subdivision ray casting, is employed to identify newly visible primitives which are added to the list of previously visible primitives for rasterization. The method employs a system of classifying objects based on their dynamic occlusive properties to increase the accuracy, efficiency and versatility of the reprojective approach. Because the method employs a hybrid approach to visible surface determination in which newly visible primitives are identified for each frame it can be implemented as a graphics server employing an efficient on-demand, progressive geometry transmission protocol for client-server image generation. This client-server system employs a method of visibility event encoding in which data representing newly visible and newly invisible primitives for each frame are transmitted to a client unit which is a conventional graphics display system. The visibility event codec method can also be used to encode and store information representing a computer animation for later interactive playback.

Claims

1. A method of generating a computer generated image sequence from primitives stored in a list of visible primitives, wherein said image sequence comprises consecutive frames representing simultaneous viewpoint translation and view direction vector rotation, the method comprising the steps of:

a) transforming graphics primitives visible in a previous frame by a translational component of a view transformation;

b) repositioning extents of a viewport on a viewplane by an amount that reflects a view direction vector rotation angle;

c) classifying previously visible primitives to the repositioned viewport;

d) rasterizing the previously visible primitives into the repositioned viewport;

e) storing, in an augmented depth buffer, both depth value and primitive references for image samples produced by rasterizing each of the previously visible primitives for the previous frame and a current frame;

f) determining, using said augmented depth buffer after the step e) of storing, locations in the current frame where previously invisible primitives may be newly exposed by finding in corresponding locations of said augmented depth buffer, locations in which;

1) a first primitive of the previously visible primitives rasterized for the current frame belongs to a different substantially convex object than a second primitive of the previously visible primitives rasterized in the corresponding location for a preceding frame, and

2) depth values of the locations for the current frame are greater than the depth values for the preceding frame;

g) searching in the locations to find newly visible primitives using visibility tracing;

h) rasterizing the newly visible primitives using depth-comparison rasterization;

i) adding the newly exposed primitives to the list of visible primitives; and

j) repositioning the image samples, produced by rasterizing the primitives which are not yet rotated, by rotating the image samples by an amount that reflects the view direction vector rotation.

2. The method according to claim 1, wherein the step j) of repositioning comprises the sub-steps of:

j1) transforming the previously visible primitives by a rotational component of the view transformation; and

j2) rasterizing a primitives transformed in sub-step j1) into the canonical viewport.

3. A method of generating a computer generated image sequence from primitives stored in a list of visible primitives, the method comprising the steps of:

a) transforming previously visible graphics primitives visible in a previous frame;

b) rasterizing the previously visible primitives to a viewport;

c) determining locations in a current frame where previously invisible primitives may be newly exposed, the step c) of determining comprising the sub-steps of;

c1) determining a three-space volume that is formed by a difference between a first view volume corresponding to a first camera state for the current frame minus a second view volume corresponding to a second camera state for the previous frame,

c2) truncating the difference volume by a plane that is substantially congruent to a viewplane;

c3) determining a region of the current frame that contains a projection of the three-space volume;

d) searching in said locations in the current frame to find newly visible primitives using visibility tracing;

e) rasterizing the newly visible primitives using depth-comparison rasterization; and

f) adding the newly visible primitives to the list of visible primitives.

4. A method of generating a computer generated image sequence from primitives stored in a list of visible primitives, the method comprising the steps of:

a) transforming previously visible graphics primitives visible in a previous frame;

b) rasterizing the previously visible primitives to a viewport;

c) determining locations in a current frame where previously invisible primitives may be newly exposed, the step c) of determining comprising the sub-steps of;

c1) determining a three-space volume that is formed by a difference between a first view volume corresponding to a first camera state for the current frame minus a second view volume corresponding to a second camera state for the previous frame,

c2) truncating the difference volume by a plane that is at a greater distance from the viewpoint than a viewplane is from the viewpoint, and

c3) determining a region of the current frame that contains a projection of the three-space volume;

d) searching in said locations in the current frame to find newly visible primitives using visibility tracing;

e) rasterizing the newly visible primitives using depth-comparison rasterization; and

f) adding the newly visible primitives to the list of visible primitives,

whereby a section of a view frustum between the viewpoint and said plane define an exclusionary volume in which no new primitives are allowed to penetrate and whereby the truncated difference volume has a smaller projection on an image plane than when the viewplane is a limiting plane and consequently results in smaller view volume incursion regions, enabling a search with less visibility tracing for newly visible primitives.

5. The method according to claim 4, wherein the step d) of searching by visibility tracing comprises:

searching using front-to-back, depth prioritized visibility tracing to a maximum depth equal to a depth of a corresponding image-space sample in a search region wherein said corresponding image-sample is produced by rasterizing previously visible primitives and wherein a source primitive for said corresponding image-sample is not tested for primitive-visibility tracing structure intersection during visibility tracing whereby a presence of image-samples from previously visible primitives reduces a number of primitive-visibility tracing structure intersections required.

6. A method of generating a computer generated image sequence from primitives stored in a list of visible primitives, the method comprising the steps of:

a) transforming graphics primitives visible in a previous frame;

b) classifying the previously visible primitives to a viewport;

c) rasterizing the previously visible primitives;

d) storing, in an augmented depth buffer, both depth value and primitive references for samples produced by rasterizing each of the previously visible primitives for the previous frame and a current frame;

e) determining, using the augmented depth buffer after the step d) of storing, locations in the current frame where previously invisible primitives may be newly exposed;

f) searching, using visibility tracing, in said locations to find newly visible primitives using a demand-driven, depth-prioritized, data-access method of visible surface determination;

g) rasterizing newly visible primitives using depth-comparison rasterization; and

h) adding newly exposed primitives to the list of visible primitives,

wherein the step f) of searching using visibility tracing comprises;

searching using front-to-back, depth prioritized visibility tracing to a maximum depth equal to a depth of a corresponding image-space sample in a search region wherein said corresponding image-sample is produced by rasterizing previously visible primitives and wherein a source primitive for said corresponding image-sample is not tested for primitive-visibility tracing structure intersection during visibility tracing whereby a presence of image-samples from previously visible primitives reduces a number of primitive-visibility tracing structure intersections required.