System and method of image generation and encoding using primitive reprojection

• US 6,057,847 A
• Filed: 05/09/1997
• Issued: 05/02/2000
• Est. Priority Date: 12/20/1996
• Status: Expired due to Term

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Barry Jenkins
• Inventors: Jenkins, Barry
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/852,899
• Time in Patent Office: 1,089 Days
• Field of Search: 345/422, 345/421, 345/423, 345/113, 345/114, 345/115, 345/473, 345/474
• US Class Current: 345/422
• 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, performed on an encoder including a first database of graphics primitives, of encoding graphics information for generating a computer generated image sequence to be displayed, the method comprising the steps of:

a) determining graphics primitives that actually become newly visible for substantially each frame of the image sequence; and

b) adding encoded visibility event information describing the newly visible primitives to a second database for substantially each frame of the sequence.

2. The method according to claim 1, wherein the step of determining graphics primitives that become newly visible for a frame comprises the step of determining a set of all graphics primitives that become newly visible for the frame.

3. The method according to claim 1, wherein the step of determining graphics primitives that become newly visible for a frame comprises the step of determining a set of only the graphics primitives that become newly visible for the frame.

4. The method according to claim 1, wherein the step of determining graphics primitives that become newly visible for a frame comprises the step of determining a set of all of and only the graphics primitives that become newly visible for the frame.

5. The method according to claim 1, further comprising the steps of:

c) determining primitives that become newly invisible for substantially each of said frames, and

d) adding, for substantially each frame, graphics information describing said newly invisible primitives to the second database.

6. The method according to claim 5, wherein the step c) of determining comprises the step of determining primitives that become completely occluded for substantially each of said frames.

7. The method according to claim 5, wherein the step b) of adding information describing said newly visible primitives comprises the substeps of:

b1) determining, for each of the newly visible primitives, an insertion location, by array index, in an unused position of a list of visible primitives comprising a source display list of primitives, and

b2) adding information to the second database representing the newly visible primitives together with the array index in the source display list of visible primitives for the frame whereby the process of adding newly visible primitives to a destination display list, having a sequence equivalent to the source display list, during decoding is simplified because the addition location is predetermined.

8. The method according to claim 7, wherein the step d) of adding information describing said newly invisible primitives comprises the substeps of

d1) determining the existing location, by array index, of substantially each newly invisible primitive in the source display list for the frame, and

d2) adding, for the frame, the array index values of the newly invisible primitives into the second database, whereby the process of removing or inactivating newly invisible primitives in a destination display list, having a sequence equivalent to the source display list, during subsequent decoding is simplified because the removal location is predetermined.

9. The method according to claim 7, further comprising the step of adding information indicating that the encoded information for newly visible and newly invisible primitives applies to a specific destination display list in a plurality of destination display lists maintained by a decoding unit.

10. The method according to claim 9, further comprising the step of adding information indicating that a specific destination display list should be flushed.

11. The method according to claim 9, further comprising the step of adding information indicating that display of a specific destination display list should be suspended.

12. The method according to claim 7, further comprising the steps of:

c) determining, for substantially each frame of the sequence, the size of said source display list of primitives; and

d) decreasing the size of the source and destination display list if the size of the size exceeds a predetermined size, the method of decreasing comprising the step of;

subsequently encoding newly visible primitives using a reduced level-of-detail representation;

whereby the size of the destination display list is limited to a predetermined size commensurate with the storage and display capabilities of a decoding unit.

13. The method according to claim 5, wherein the step c) of determining comprises the sub-steps of:

c1) determining primitives that become newly invisible for substantially each of said frames, and

c2) determining vertices belonging to the newly invisible primitives that are not shared by currently visible primitives; and

wherein the step d) of adding comprises the substeps of;

d1) adding graphics information describing the newly invisible primitives for the frames to said second database, and

d2) adding information describing the vertices, determined in step c2) to said second database whereby the second database represents the encoded visibility event information including the newly invisible primitives and the corresponding vertices that are not shared by currently visible primitives.

14. The method according to claim 13, wherein the step d2) of adding information describing said vertices, determined in step c2) comprises the substeps of:

d2a) determining the existing location, by array index, of each of the determined vertices in said source display list of vertices for the frame, and

d2b) adding information to said second database representing said determined vertices wherein said information comprises the array index value of the vertex in said source display list of vertices whereby the process of removing or inactivating vertices in a destination display list, having a sequence equivalent to the source display list, during subsequent decoding is simplified because the removal location is predetermined.

15. The method according to claim 5, in which the step a) of determining comprises the sub-steps of:

a1) assigning each of plural subimage processors a respective subimage of a tiling of an overall image, wherein the each of the plural subimage processors is connected to both a data storage device that is shared with other of the plural subimage processors, and at one of a local storage device and a cache data storage device;

a2) maintaining, by each of the plural subimage processors, a corresponding list of visible primitives for each corresponding subimage using a corresponding subimage depth-buffer, the step of maintaining comprising the sub-steps of;

a2a) transforming the previously visible primitives in the corresponding subimage list of primitives,

a2b) classifying, by subimage, primitives in the corresponding subimage list of primitives which redistribute to other subimages,

a2c) redistributing to other subimages the primitives in the corresponding list of primitives which redistribute to the other subimages,

a2d) adding to the corresponding list of primitives the primitives redistributed from other subimages,

a2e) rasterizing, using a subimage augmented depth buffer, the primitives in the current subimage list of visible primitives,

a2f) storing both depth and primitive references for samples written to said subimage augmented depth buffer for the current frame and an earlier frame,

a2g) determining, after the step a2f) of storing, and using the subimage augmented depth buffer, locations in the current frame where previously invisible primitives may be newly exposed,

a2h) visibility tracing in the locations of the current frame where the invisible primitives may be newly exposed to find newly exposed primitives for the corresponding subimages, and

a2i) subsequently rasterizing newly exposed primitives using depth-comparison rasterization; and

a3) testing, for each subimage, corresponding primitives determined to be newly visible to the subimage in step 6 against a global visibility array wherein said global visibility array indicates the primitives that were visible in the entire image during the earlier frame,

wherein the adding the step c) of adding comprising adding those primitives found to be newly visible to a subimage and not previously visible in the image as determined by absence of the primitive on said global visibility array to said information describing newly visible primitives for the frame.

16. The method according to claim 15, wherein the step c) of determining newly invisible primitives comprises the substeps of:

c1) reading said augmented depth buffer corresponding to said subimage following the rasterization of all primitives in the reprojection list of primitives for the corresponding subimage;

c2) determining, during the step of reading, those primitives in said reprojection list of visible primitives for the subimage those primitives that are not represented by at least one sample in a visible level of said augmented depth buffer corresponding to the subimage;

c3) removing those primitives determined in step c2) from said reprojection list of visible primitives corresponding to said subimage;

c4) testing each of said newly occluded graphics primitives for each of the subimages to determine which other subimages the each said graphics primitive projects to; and

c5) determining, by read of appropriate subimage visible primitive lists, any of said primitives newly occluded to a subimage that are not visible in any other subimage to which they project to be newly occluded to the entire image,

wherein the step d) of adding comprises adding information describing said newly invisible primitives determined in the determining step c) to said second database whereby this database represents the encoded visibility event information including the newly visible and newly invisible primitives for substantially each frame of the encoded sequence.

17. The method according to claim 5, wherein the step a) of determining comprises the sub-steps of:

a1) assigning each of plural subimage geometry processors a respective subimage of a tiling of an overall image, wherein the each of the plural subimage is connected to both a data storage device that is shared with other of the plural subimage processors, and at one of a local storage device and a cache data storage device;

a2) maintaining, by each of the plural subimage geometry processors, a corresponding list of visible primitives, in object-space representation, for each corresponding subimage, the substep a2) of maintaining comprising the sub-substeps of;

a2a) transforming the previously visible primitives in the corresponding subimage list of primitives,

a2b) classifying, by subimage, primitives in the corresponding subimage list of primitives which redistribute to other subimages,

a2c) redistributing to other subimage lists the primitives in the corresponding list of primitives which redistribute to the other subimages, and

a2d) adding to the corresponding list of primitives the primitives redistributed from other subimages;

a3) assigning each of plural subimage rasterization-visibility tracing processors a respective subimage of a tiling of an overall image, wherein the each of the plural subimage rasterization-visibility tracing processors is connected to both a data storage device that is shared with other of the plural subimage rasterization-visibility tracing processors and to a corresponding subimage geometry processor and at one of a local storage device and a cache data storage device;

a4) rasterizing, by subimage rasterization-visibility tracing processor, using a subimage augmented depth buffer, the primitives in the current subimage list of visible primitives;

a5) storing both depth and primitive references for samples written to said subimage augmented depth buffer for the current frame and an earlier frame;

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

a7) visibility tracing in the locations of the current frame where the invisible primitives may be newly exposed to find newly exposed primitives for the corresponding subimages;

a8) subsequently rasterizing newly exposed primitives using depth-comparison rasterization;

a9) transmitting, to the corresponding subimage geometry processor, data representing the newly visible subimage primitives determined in the visibility tracing step a7); and

a10) testing, for each subimage by corresponding geometry processor, those primitives determined to be newly exposed in a subimage, as determined by the visibility tracing step b7), against a global visibility array wherein said global visibility array indicates the primitives that were visible in the entire image during the earlier frame,

wherein the adding the step b) of adding comprising adding those primitives found to be newly visible to a subimage and not previously visible in the image as determined by absence of the primitive on said global visibility array to said information describing newly visible primitives for the frame.

18. The method according to claim 1, wherein the step b) of adding information comprises adding separate data packets which represent newly visible primitive information for each of the corresponding frames.

19. The method according to claim 18, wherein the step b) of adding information further comprises the steps of;

adding separate data packets which represent newly visible primitive information for each of the corresponding frames; and

adding separate data packets which represent newly invisible primitive information for each of the corresponding frames.

20. The method according to claim 19, wherein the step b) of adding information as separate data packets for each of said frames comprises the substeps of:

b1) determining a size of each of said data packets,

b2) comparing each of said sizes to a threshold value to determine if the size of each of said data packets exceeds said threshold value,

b3) modifying the data packets which have a size larger than said threshold value to have a size less than said threshold value,

whereby the sequence comprises a predetermined minimum number of packets to be transmitted and decoded per unit time corresponding to a desired frame rate.

21. The method according to claim 20, wherein the step b3) of modifying comprises the step of redetermining said newly visible primitives for the corresponding frame data packets wherein the redetermining employs a database of graphics primitives containing represented objects having a lower level of geometric detail.

22. The method according to claim 20, wherein the step b3) of modifying comprises adding information describing newly visible primitives for said frames having corresponding datapackets larger than said threshold value to datapackets corresponding to earlier frames in said sequence wherein said earlier frames have corresponding datapackets that are smaller than said threshold value, and removing the information added in the adding step from the data packets to which the primitives were originally assigned.

23. The method according to claim 22, wherein the information describing newly visible primitives for said frames having corresponding datapackets larger than said threshold value that is moved to data packets corresponding to said earlier frames contains information for each primitive indicating the frame number of the sequence of frames when each of said primitives actually becomes visible in said sequence whereby the pretransmitted primitives are not actively displayed during decoding until said frame number is encountered.

24. The method according to claim 19, wherein the step b) of adding information as separate data packets for each of said frames comprises the substeps of:

b1) determining the size of each of said data packets;

b2) comparing each of said sizes to a predetermined minimum value to determine if the size of each of said data packets is less than said threshold value; and

b3) modifying the data packets which have a size smaller than said minimum value to have a size equal to said minimum value by adding information describing primitives that became visible in an earlier frame than the corresponding data packet and which are still visible in the image sequence,

whereby the unused replay/transmission bandwidth produced by frame packets that have a size below said minimum value is used to repeatedly resend visible primitives thereby reducing the time between initiation of reception of a datastream comprising the encoded information and the reception of a full set of visible primitives for a frame.

25. The method according to claim 24, wherein said added information representing previously encoded visible primitives is added to said datapacket with size less than threshold by adding the information as a separate sub-packet, wherein the information of said sub-packet is not decoded by a subsequent decoding if the decoding unit is not in an initiation phase of the decoding but actually has the current full set of visible primitives,

whereby the decoding process is able to ignore re-encoded primitives except during initiation.

26. The method according to claim 1,

wherein the step a) of determining comprises the sub-steps of:

a1) determining graphics primitives that actually become newly visible for substantially each frame of the image sequence,

a2) determining vertices belonging to the newly visible primitives that are currently not encoded; and

wherein the step b) of adding comprises the sub-steps;

b1) adding information describing the newly visible primitives for the frames to the second database, and

b2) adding information describing the corresponding vertices determined in step a2) to the second database so that, for substantially each frame of the sequence, the second database contains encoded visibility event information including the newly visible primitives and corresponding vertices that are not already encoded.

27. The method according to claim 26, wherein the step b2) of adding comprises the substeps of:

b2a) determining, for each of said vertices determined in step a2), an insertion location, by array index, in an unused position in a list of vertices of visible primitives comprising a source display list of vertices, and

b2b) adding information to the second database representing said vertices together with said array index value in said source display list of vertices for the frame whereby the subsequent process of adding new vertices to a destination display list of vertices, having a sequence equivalent to the source display list of vertices, during decoding of said information is simplified because the addition location is predetermined and whereby a newly visible primitive may reference a vertex encoded in an earlier frame thereby substantially reducing storage and transmission requirements by exploiting the considerable amount of vertex sharing that occurs within primitive meshes.

28. The method according to claim 1, wherein the step a) of determining comprises the step of determining the newly visible graphics primitives for a viewport that is larger than the displayed viewport.

29. The method according to claim 1, wherein the step a) of determining comprises the step of determining the newly visible graphics primitives determined from a plurality of substantially adjacent viewports representing a field-of-view that is greater than the instantaneously displayed field-of-view displayed during decoding whereby the destination display list of visible primitives that result from the decoding contains a superset of visible primitive that is sufficient to allow interactive rotation of the view direction vector about the viewpoint to obtain dynamic yaw, pitch and roll capability during decoding and display of encoded sequence.

30. The method according to claim 1, wherein the step a) of determining comprises determining the newly visible graphics primitives from a plurality of viewpoints for a single frame of said sequence wherein the plurality of viewpoints for a single frame are arranged on a first curve and wherein the step b) of adding information comprises adding information which represents primitives that are newly visible from said plurality of viewpoints for each of said frames.

31. The method according to claim 30, further comprising the step of determining a second space curve wherein the second space curve represents a space-time trajectory of viewpoint motion for the image sequence and intersects the first curve containing said viewpoints for the single frame whereby said encoding represents the visibility from a surface containing said space-time trajectory.

32. The method according to claim 1,

wherein the step of a) determining comprises the steps of:

arranging a plurality of viewpoints for a single frame on a substantially planar region;

determining the newly visible graphics primitives from the plurality of viewpoints for a single frame of said sequence; and

wherein the step b) of adding information comprises adding separate data packets which represents newly invisible primitive information from said plurality of viewpoints for each of said frames.

33. The method according to claim 32, further comprising the step of determining a second space curve that represents a space-time trajectory of viewpoint motion for the encoded image sequence and intersects the substantially planar region containing said viewpoints for a single frame, whereby said encoding represents the visibility from a volume containing said space-time curve.

34. The method according to claim 1, wherein said information additionally includes information describing the motion of camera and other objects during said sequence.

35. The method according to claim 1, further comprising the step of periodically adding material information comprising parameters that affect the shading of encoded primitives.

36. The method according to claim 1, further comprising the step of periodically adding material information comprising parameters that reference specific material information that is prestored in a decoder.

37. The method according to claim 36, wherein the parameters are modifiable by a user of the decoder to allow selection of the prestored material information.

38. The method according to claim 1, further comprising the steps of:

c) determining image regions, for substantially each frame of the image sequence, that contain exposed surfaces which require rendering methods that can not be performed on a decoder but which can be performed on the encoder; and

d) rendering said image regions on the encoder;

wherein the step b) of adding comprising the step of adding information

     1) describing the newly visible primitives; and

     2) generated in the rendering step d) describing said image regions.

39. The method according to claim 1, wherein the step b) of determining comprises the sub-steps of:

b1) rendering for substantially each frame of said sequence, said graphics primitives, wherein said rendering comprises writing samples from said primitives to an augmented depth buffer wherein said augmented depth buffer includes, for substantially each sample location, a reference to the source primitive for the sample;

b2) determining, for substantially each frame of said sequence, the set of primitives that are visible in said frames by reading said augmented image buffer to determine the closest primitive at each sample location; and

b3) comparing the set of primitives determined to be visible for the current frame to the set of primitives determined to be visible for an earlier frame wherein the comparing is made to identify those primitives visible in the set of visible primitives for the current frame but not in the set of visible primitives for the earlier frame,

wherein the step c) of adding comprises adding those primitives identified to be newly visible in the comprising step b3).

40. The method according to claim 39, wherein the comparing step b3) further comprises the step of comparing the set of primitives determined to be visible for the current frame to the set of primitives determined to be visible for an earlier frame wherein the comparing is made to identify those primitives visible in the set of visible primitives for the earlier frame but not in the set of visible primitives for the current frame, and wherein step c) of adding further comprises the step of adding information representing primitives, identified in said additional comparing step, as newly invisible primitives.

41. The method according to claim 1 wherein the step a) of determining comprises the substeps of:

a1) transforming previously visible primitives in a current frame;

a2) classifying the previously visible primitives to a viewport;

a3) rasterizing the previously visible primitives;

a4) storing both depth and primitive references for each of the previously visible primitives for a preceding frame and the current frame in an augmented depth buffer;

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

a6) visibility tracing in the locations of the current frame where the invisible primitives may be newly exposed to find newly exposed visible primitives; and

a7) subsequently rasterizing newly exposed primitives using depth-comparison rasterization.

42. The method according to claim 41, wherein the step a6) of visibility tracing comprises ray casting using a set of grids wherein the grids comprise a subdivision of the represented space containing said graphic primitives.

43. The method according to claim 42, wherein said set of grids comprises a hierarchy of grids wherein grids at deeper levels of the hierarchy reference primitives from a high level-of-detail representation of the represented objects and grids at upper levels of the hierarchy reference primitives from a low level-of-detail representation of the represented objects.

44. The method according to claim 41, wherein the step b) of adding comprises the substeps of:

b

     1) adding separate data packets which represent newly visible primitive information for substantially each of the corresponding frames;

b2) determining the size of each of said data packets;

b3) comparing each of said sizes to a predetermined threshold value to determine if the size of each of said data packets exceeds said threshold value; and

b4) modifying the data packets which have a size larger than said threshold value to have a size less than said threshold value, wherein the step c3) of modifying comprises the substeps of;

b4a) redetermining said newly visible primitives for the corresponding frame data packets, by visibility tracing in said regions of potentially newly exposed primitives using a lower level-of-detail database, and

b4b) adding information describing redetermined newly visible primitives to corresponding data packets, whereby the number of newly visible primitives and the size of the corresponding packet is reduced.

45. The method according to claim 41, further comprising the steps of:

c) determining image regions, for substantially each frame of the image sequence, that contain exposed surfaces which require ray tracing that cannot be performed on a decoder unit but which can be performed on an encoding unit; and

d) rendering said image regions on the encoder by ray tracing,

wherein the step b) of adding comprises the step of adding information

     1) describing the newly visible primitives, and

     2) describing said image regions generated in the rendering step d), whereby said image information can be displayed on a decoder that cannot be produced by rendering the visible primitives on the decoder.

46. The method according to claim 1, wherein the step a) of determining comprises the steps of:

a1) reading, for substantially each frame of said sequence, data representing each of said frames wherein said data representing comprises of an augmented depth buffer wherein said augmented depth buffer includes, for substantially each sample location, a reference to the source primitive for the sample,

a2) determining, for substantially each frame of said sequence, the set of primitives that are visible in said frames by reading said augmented image buffer to determine the closest primitive at each sample location,

a3) comparing the set of primitives determined to be visible for the current frame to the set of primitives determined to be visible for an earlier frame wherein the comparing is made to identify those primitives visible in the set of visible primitives for the current frame but not in the set of visible primitives for the earlier frame,

wherein the step c) of adding comprises adding those primitives identified to be newly visible in the step b3).

47. The method according to claim 46, wherein the comparing step a3) further comprises the additional step of comparing the set of primitives determined to be visible for the current frame to the set of primitives determined to be visible for an earlier frame wherein the comparing is made to identify those primitives visible in the set of visible primitives for the earlier frame but not in the set of visible primitives for the current frame, and wherein step c) of adding further comprises the step of adding information representing primitives, identified in said additional comparing step, as newly invisible primitives.

78. The method according to claim 15, further comprising the steps of:

c) determining, based on changes in an input device to said decoder, the current position of the view direction vector in a predetermined region in three space wherein said region contains a viewpoint trajectory corresponding to the viewpoint trajectory used during the encoding of said information;

d) transforming said potentially visible primitives by a transformation matrix describing the viewing transformation corresponding to said current position of the view direction vector; and

e) rasterizing, after the step of transforming, said primitives.

48. In a computer-implemented method of encoding an image sequence by visibility event encoding, a method of separately encoding a synchronizing data stream, the method of separately encoding comprising the steps of:

determining substantially all primitives that form a complete set of visible primitives for substantially each frame of the sequence; and

encoding a separate initiation data stream including the substantially all primitives determined in the determining step to form a complete set of visible primitives for substantially each frame of the sequence, wherein each packet of the separate initiation data stream corresponds to a frame packet of a visibility event encoding, whereby a decoding unit accessing the separate initiation stream does not need an extended time to receive a completely visible set of primitives during the initiation of decoding at an arbitrary frame.

49. The method according to claim 48, further comprising the step of, for each frame packet of the sequence, including information indicating the number of frames until a full set of visible primitives is encoded, whereby the display of an incomplete set of visible primitives by a decoder can be prevented by delaying the display process by said number of frames from the initiation of decoding.

50. A method, performed on a decoder, of maintaining a display list of graphics primitives to be displayed, the method comprising the steps of:

a) receiving information describing the primitives that become newly visible for substantially each frame of an image sequence; and

b) adding information describing the newly visible primitives for a corresponding frame of said sequence to said display list, whereby said information comprises a visibility event encoding and said method of maintaining comprises a decoding of the encoded information.

51. The method according to claim 50, further comprising the steps of:

c) transforming primitives, wherein said primitives are stored in object-space representation, by a 3-D transformation corresponding to a current frame of said sequence of images; and

d) rendering primitives using a depth buffer.

52. The method according to claim 51, wherein the step b) of adding comprises adding information describing the newly visible primitives for a corresponding frame of said sequence to said list of visible primitives after the display of said corresponding frame whereby the delayed addition of said newly visible primitives does not delay the display of said frame and whereby the transient failure to display said primitive is relatively unnoticed by a viewer because of the visual system'"'"'s limited acuity for newly exposed objects.

53. The method according to claim 50, wherein the step b) of adding comprises adding information describing newly visible primitives for a corresponding frame of said sequence before the display of said corresponding frame.

54. The method according to claim 50, further comprising the steps of:

c) receiving information describing the primitives that become newly invisible for substantially each frame of said sequence; and

d) removing from said list of visible primitives the graphics information associated with the newly invisible graphics primitives.

55. The method according to claim 54,

wherein the step c) of receiving information describing newly invisible graphics primitives comprises the step of receiving an index, i, with the information for each of said newly invisible graphics primitives;

and

wherein the step d) of removing comprises marking as unused the i-th location in said list of visible graphics primitives.

56. The method according to claim 54,

wherein the step a) of receiving information describing newly visible primitives comprises the step of receiving an index, i, with the graphics information for each of said newly visible graphics primitives;

and wherein the step b) of adding comprises the sub-step of adding the graphics information at the i-th location in said list of visible graphics primitives;

and wherein the step c) of receiving information describing newly invisible primitives comprises the step of receiving an index, n, with the list of newly invisible graphics primitives;

and wherein the step d) of removing comprises marking as unused the n-th location in said list of visible graphics primitives.

57. The method according to claim 50,

wherein the step a) of receiving information comprises the sub-step of receiving an index, i, with the information for each of said newly visible graphics primitives;

and

wherein the step b) of adding the graphics information comprises the sub-step of adding the graphics information at the i-th location in said list of visible graphics primitives, wherein said list comprises a destination display list of primitives.

58. The method according to claim 50, wherein said information describing newly visible primitives is stored in a data storage device and wherein the step of receiving comprises the sub-step of receiving information from a streaming source wherein said streaming source is produced by reading from said storage device.

59. The method according to claim 50, wherein the step a) of receiving comprises the sub-steps of:

receiving graphics information before the graphics information is needed, the graphics information including a specified initial frame number at which the graphics information is to be added to the list of visible graphics;

buffering the graphics information until the graphics information is needed; and

the step b) of adding comprises the substep of adding the graphics information to the list of visible graphics primitives when said primitive'"'"'s specified initial frame number is equal to or greater than the frame number of the currently displayed frame.

60. The method according to claim 59, wherein the step a) of receiving comprises the sub-step of receiving graphics information before the graphics information is needed, the graphics information including a specified initial frame number at which the graphics information is to be displayed from the list of visible primitives;

and the step of displaying comprises the substep of displaying primitives from said list of visible primitives if said primitive'"'"'s specified initial frame number is equal to or greater than the frame number of the currently displayed frame.

61. The method according to claim 50, wherein said information describing newly visible primitives and newly invisible primitives is stored in a data storage device and wherein the step of receiving comprises the sub-step of receiving information from a streaming data source wherein said streaming source is produced by reading from said storage device.

62. The method according to claim 61, wherein the step a) of receiving further comprises the sub-steps of:

a1) determining, based on changes in an input device to said decoder, the current position of the viewpoint on a predetermined space-time curve wherein said space-time curve represents a viewpoint trajectory corresponding to the viewpoint trajectory used during the encoding of said information describing newly visible primitives for said sequence; and

a2) controlling the read rate of said storage device containing said information describing newly visible primitives wherein said information comprises packets of information wherein each packet contains information describing the newly visible for a specific frame of the sequence,

wherein said controlling comprises serially reading said data packets containing said information at a rate that causes the reading of the datapacket corresponding to the current position of the viewpoint to occur at a time that is substantially equal to the display time for the currently displayed frame,

whereby said input to decoder unit allows interactive control of viewpoint velocity along said space-curve during decoding.

63. The method according to claim 62 further comprising the steps displaying frames of the sequence that are between times corresponding to the encoded visibility event packets using transformation values interpolated from keyframe data, wherein said keyframe data is received as part of the information received in the step a) of receiving;

whereby the display rate can be maintained during periods when the desired viewpoint velocity during decoding is slower than the viewpoint velocity employed during encoding of said information.

64. The method according to claim 50, wherein the step a) of receiving information describing newly visible primitives comprises the substeps of receiving a streaming information from a streaming source wherein the streaming data source is an encoding unit encoding said information substantially in real-time.

65. The method according to claim 64, wherein the step a) of receiving information describing newly visible primitives in real-time further comprises the substeps of:

a1) determining, based on changes in an input device to said decoder, the position of the viewpoint and orientation of the view direction for the current frame;

a2) transmitting, from said decoder, information describing the current viewpoint position and view direction to an encoding unit;

a3) determining, on said encoding unit, the newly visible primitives for said frame based on the position of said viewpoint and said view direction;

a4) transmitting, from said encoding unit, said information describing newly visible primitives; and

a5) receiving, on said decoding unit, an index, i, with the graphics information for each newly visible graphics primitive,

wherein the step b) of adding the graphics information comprises the sub-step of adding the graphics information at the i-th location in said list of visible graphics primitives.

66. The method according to claim 50 wherein said information comprises additional information describing motion of camera and other represented objects that occurs during said image sequence.

67. The method according to claim 66 wherein said additional information is represented as keyframe data and wherein the method further comprises the steps of:

c) transforming primitives, wherein said primitives are stored in object-space representation, by a 3-D transformation corresponding to a current frame of said sequence of images wherein said transformation is determined from said keyframe data; and

d) rendering primitives using a depth buffer.

68. The method according to claim 50, further comprising the additional step of periodically receiving information describing primitives that are visible in a current frame but that are not newly visible in the current frame;

whereby the number of missed primitives that occur during the initiation of decoding and display is reduced.

69. The method according to claim 68, wherein said additional information is received as a sub-packet of information distinct from a sub-packet of information comprising the description of the newly visible primitives for a frame;

and wherein the step b) of adding comprises adding information from these said subpackets only if the decoder does not have the current complete set of visible primitives.

70. The method according to claim 68, wherein the step of receiving additional information comprises receiving both previously visible primitives and receiving information indicating at which frame a complete set of visible primitives will have been received;

and delaying display of said list of visible primitives until said information indicates that said list contains a complete set of visible primitives, whereby incomplete images are not displayed.

71. The method according to claim 50, further comprising the step of:

c) receiving from a transmitting data source, during the initiation of decoding, information describing the complete set of visible primitives for a starting frame of the sequence,

wherein the receiving step a) comprises receiving from a second transmitting data source, after the reception of a complete set of visible primitives for a frame, information describing the primitives that become newly visible for substantially each frame of said sequence subsequent to the starting frame whereby the subsequent display of graphics information received in the receiving steps occurs without missed primitives.

72. The method according to claim 50, further comprising the steps of:

c) sending a signal, from said decoder, to an initiation server unit wherein said signal is a request for a complete set of visible primitives for a frame of said sequence that is substantially equal to the frame of said sequence for which information describing the newly visible and newly invisible primitives that is currently being transmitted from a transmission source received by said decoder; and

d) receiving, from said initiation server unit, data comprising the complete set of visible primitives for the requested frame or a later frame,

wherein in the receiving step a) comprises the substep of subsequently receiving information from said transmission source, whereby the subsequent display of graphics information received in the receiving steps occurs without missed primitives.

73. The method according to claim 50, wherein the step of b) of adding the graphics information describing the newly visible primitives to said list of visible primitives comprises the steps of:

adding the graphics information to a first destination display list when the rendering step is rendering newly visible graphics primitives from a second destination display list; and

adding the graphics information to the second destination display list when the rendering step is rendering newly visible graphics primitives from the first destination display list; and

wherein the step of rendering comprises the steps of;

periodically rendering from the first destination display list; and

periodically rendering from the second destination display list.

74. A method, performed on a decoder, of maintaining a display list of graphics primitives, the method comprising the steps of:

a) receiving information describing the primitives that become potentially newly visible for substantially each frame of an image sequence; and

b) adding information describing the potentially newly visible primitives for a corresponding frame of said sequence to said display list,

whereby said information comprises a visibility event encoding representing primitives visible from a specified set of viewpoints and/or view volumes whereby the set of encoded primitives allows a predefined degree of viewpoint and/or view direction vector motion during decoding of the encoded information.

75. The method according to claim 74 wherein the step a) of receiving comprises the step of receiving information describing graphics primitives that become visible from a plurality of viewpoints during substantially each frame of said sequence.

76. The method according to claim 75 further comprising the steps of:

c) determining, based on changes in an input device to said decoder, the current position of the viewpoint in a predetermined region in three space wherein said region contains a viewpoint trajectory corresponding to the viewpoint trajectory used during the encoding of said information;

d) transforming said potentially visible primitives by a transformation matrix describing the viewing transformation corresponding to said current position of the viewpoint; and

e) rasterizing, after the step d) of transforming, said primitives.

77. The method according to claim 74, wherein the step a) of receiving comprises the step of receiving information describing graphics primitives that become visible from a plurality of view directions during substantially each frame of said sequence.

79. The method according to claim 74, wherein the step a) of receiving comprises the step of receiving information describing graphics primitives that become visible from a plurality of viewpoints and view directions during substantially each frame of said sequence.

80. The method according to claim 74, wherein said information describing newly visible graphics primitives comprises the set of primitives that are determined to be newly visible from a plurality of view frustrums wherein said view frustrums share a common viewpoint.

81. A computer apparatus for generating a computer generated image sequence, the computer apparatus comprising:

a transformer for transforming previously visible primitives, wherein said primitives are stored in a storage area for previously visible primitives;

a classifier for classifying the previously visible primitives to a viewport;

a rasterizer for rasterizing the previously visible primitives;

an augmented depth buffer for storing both depth and primitive references for each of the previously visible primitives for a preceding frame and the current frame, and for determining in the current frame where invisible primitives may be newly exposed; and

a visibility tracer for visibility tracing in the locations in the current frame where the invisible primitives may be newly exposed to find newly exposed visible primitives;

wherein the rasterizer also rasterizes newly exposed primitives using depth-comparison rasterization;

and wherein newly visible primitives are added to said storage device storing previously visible primitives.

82. A computer program product comprising:

a computer storage medium and a computer program code mechanism embedded in the computer storage medium for causing a computer to generate an image sequence, the computer program code mechanism comprising;

a first computer code device configured to transform previously visible primitives wherein said primitives are stored in a storage area for previously visible primitives;

a second computer code device configured to classify the previously visible primitives to a viewport;

a third computer code device configured to rasterize the previously visible primitives;

a fourth computer code device configured to store both depth and primitive references for each of the previously visible primitives for a preceding frame and the current frame in an augmented depth buffer;

a fifth computer code device configured to determine, after storing by the fourth computer code device, and using the augmented depth buffer, locations in the current frame where invisible primitives may be newly exposed;

a sixth computer code device configured to find newly exposed visible primitives by performing visibility tracing in the locations in the current frame where the invisible primitives may be newly exposed;

a seventh computer code device configured to rasterize potentially newly exposed primitives using depth-comparison rasterization; and

an eighth computer code device configured to add the newly exposed primitives to said storage area for visible primitives.

83. A computer-implemented method of generating an image sequence, 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 for a current frame;

d) storing, in a first augmented depth buffer for a current frame, depth values and primitive references produced by rasterizing the previously visible primitives for the current frame;

e) retaining, in a second augmented depth buffer for the previous frame, the depth values and primitive references produced by rasterizing said previously visible primitives for the previous frame;

f) comparing pixels of the first augmented depth buffer to corresponding pixels of the second augmented depth buffer to identify a location in the current frame that may contain a newly exposed primitive;

g) searching in said location to find a newly visible primitive in the current frame using an image-order, front-to-back visibility tracing method of visible surface determination;

h) adding the newly exposed primitive to a list of visible primitives; and

i) rasterizing the newly visible primitive using depth-comparison rasterization to complete the current frame.

84. The method according to claim 83, wherein said graphics primitives are polygons.

85. The method according to claim 84, wherein the step f) of comparing comprises the step of determining, using the first augmented depth buffer, locations in the current frame in which none of the previously visible primitives are rasterized.

86. The method according to claim 84, wherein the step f) of comparing comprises the step of comparing pixels of the first augmented depth buffer to corresponding pixels of the second augmented depth buffer to identify a location in the current frame in which:

1) a first primitive of the previously visible primitives was rasterized for the current frame whereas a second primitive of the previously visible primitives was rasterized for the previous frame, and

2) a depth value of the location in the current frame is greater than the depth value of the location in the previous frame.

87. The method according to claim 84, wherein the step f) of comparing comprises the step of restricting a region of the first augmented depth buffer in which visibility tracing for a newly visible primitive is performed by exploiting visibility coherence of convex surface representations by comparing pixels of the first augmented depth buffer to corresponding pixels of the second augmented depth buffer to identify a location in the current frame in which:

1) a first primitive of the previously visible primitives of a first convex object was rasterized for the current frame whereas a second primitive of the previously visible primitives of a substantially different convex object was rasterized for the preceding frame, and

2) a depth value of the location for the current frame is greater than the depth value for the preceding frame.

88. The method according to claim 84, wherein the step g) of searching comprises the step of visibility tracing by ray casting using a set of grids, wherein the set of grids comprise a subdivision of a represented object-space containing the visible graphics primitives.

89. The method according to claim 88, wherein the step g) of searching by ray casting further comprises the step of organizing the set of grids into a hierarchy of grids wherein grids at deeper levels of the hierarchy reference primitives from a high level-of-detail representation of represented objects and grids at upper levels of the hierarchy reference primitives from a low level-of-detail representation of the represented objects.

90. The method according to claim 88, wherein the step g) of searching by ray casting further comprises the sub-steps of:

g1) casting a ray into a sampled image-space region wherein the ray intersects cells of the set of grids in the represented object space using an image-space sampling density that reflects a minimum image-space size of intersected cells;

g2) determining a candidate set of all primitives associated with intersected cells;

g3) testing the candidate set of all primitives associated with the intersected cells against the list of visible primitives to determine primitives in the candidate set that are not in the list of visible primitives; and

g4) considering to be newly visible, primitives determined in the testing sub-step g3) even if not actually visible.

91. The method according to claim 90, wherein the sub-step g1) of casting comprises the sub-sub-step of detecting regions of the image which completely contain a projection of a substantially convex object thereby limiting the required depth of the visibility search, the sub-sub-step comprising the sub-sub-steps of:

g1a) identifying image space regions in which a plurality of samples form a convex pattern in image-space, wherein each of the plurality of samples intersects, as a closest ray-object intersection, primitives belonging to substantially one convex object; and

g1b) limiting a depth of rays cast into an image-region within said convex pattern to the depth of said intersections of said of rays with said substantially one convex object.

92. The method according to claim 84, wherein the step g) of searching by visibility tracing comprises the step of searching for newly visible primitives by employing substantially reduced sampling densities in regions between first and second samples from the same primitive if the first and second samples are separated by a predetermined object-space distance.

93. The method according to claim 84, further comprising the step of j) removing invisible primitives from the list of visible primitives.

94. The method according to claim 93, further comprising the step of classifying as non-removable a primitive corresponding to a moving object with an image-plane velocity greater than a threshold;

and

wherein the step j) of removing invisible primitives comprises the step of removing from the list of visible primitives only invisible primitives not classified as non-removable.

95. The method according to claim 93, further comprising the step of classifying primitives corresponding to moving objects as non-occludable;

and

wherein the step j) of removing invisible primitives comprises the step of removing from the list of visible primitives only invisible primitives not classified as non-occludable.

96. The method according to claim 93, further comprising the step of:

classifying poorly occluding primitives as non-occluding; and

wherein the step j) of removing invisible primitives comprises the steps of;

removing invisible primitives from the list of visible primitives that are occluded by primitives not classified as non-occluding; and

leaving invisible primitives on the list of visible primitives that are occluded by primitives classified as non-occluding.

97. The method according to claim 96, wherein the step of leaving invisible primitives comprises the steps of:

reading from a multi-level depth buffer; and

determining from the multi-level depth buffer if a rasterized candidate primitive would have been visible if the rasterized candidate primitive had not been obscured by a primitive classified as non-occluding.

98. The method according to claim 84, further comprising the step j) of removing invisible that are outside of the view frustum for the current frame.

99. The method according to claim 84, further comprising the step j) of removing invisible primitives that are completely occluded in the current frame.

100. The method according to claim 99, wherein the step j) of removing invisible primitives that are completely occluded comprises the sub-steps of:

j1) reading the augmented depth buffer for the current frame after rasterizing all of the previously visible and newly visible primitives;

j2) determining, during the step of reading, primitives in the list of visible primitives that are not represented by at least one sample in a visible level of the augmented depth buffer; and

j3) removing the primitives determined in step j2) from the list of visible primitives.

101. The method according to claim 84, further comprising the steps of:

j) assigning each of plural sub-image processors a respective sub-image forming a tiling of an overall image, wherein each of the plural sub-image processors is connected to both a data storage device that is shared among the plural sub-image processors, and at one of a local storage device and a cache data storage device;

k) maintaining, by each of the plural sub-image processors, a corresponding sub-image reprojection list of visible primitives for each corresponding sub-image, the step of maintaining comprising the sub-steps of;

k1) transforming, by each of the plural sub-image processors, primitives in the corresponding sub-image reprojection list of visible primitives,

k2) classifying, by sub-image, wherein the step b) of classifying comprises the sub-step of classifying primitives in the corresponding sub-image reprojection list of visible primitives to the corresponding sub-image and neighboring sub-images to which the primitives may redistribute,

k3) redistributing, to respective sub-image reprojection lists, the primitives in the corresponding sub-image reprojection list which redistribute to other respective sub-images, and

k4) adding, to the corresponding sub-image reprojection list the primitives redistributed from other sub-images; and

wherein, for each of the plural sub-image processors, the step c) of rasterizing comprises the sub-step c1) of rasterizing each of the primitives in the corresponding sub-image reprojection list into an augmented depth buffer corresponding to the sub-image;

wherein, for each of the plural sub-image processors, the step f) of comparing comprises the sub-step f1) of comparing pixels of the first augmented depth buffer to corresponding pixels of the second augmented depth buffer to identify locations in the current frame that may contain newly exposed primitives;

wherein, for each of the plural sub-image processors, the step g) of searching comprises the sub-step g1) of searching in said locations to find newly visible primitives using an image-order, front-to-back visibility tracing method of visible surface determination comprises the step of visibility tracing the locations in corresponding sub-images where invisible primitives may be newly exposed to find newly exposed primitives;

wherein, for each of the plural sub-image processors, the step h) of rasterizing, comprises the sub-step h1) of rasterizing corresponding newly exposed sub-image primitives to form the overall image; and

wherein, for each of the plural sub-image processors, the step i) of adding comprises the sub-step i1) of adding the newly visible primitives, determined in the step g) of searching by visibility tracing, to the corresponding sub-image reprojection list.

102. The method according to claim 101,

wherein the step j) of assigning comprises assigning each of plural sub-image geometry processors as said sub-image processors, wherein each of the plural sub-image geometry processors is further connected to a sub-image rasterization-visibility tracing processor;

wherein the step k) of maintaining, including sub-steps k1) through k4), are performed by the plural sub-image geometry processors using a corresponding sub-image reprojection list of visible primitives for each corresponding sub-image in object-space representation;

wherein the steps c1), f1), g1), h1) and i1) are performed by corresponding processors of the sub-image rasterization visibility tracing processors.

103. The method according to claim 102, further comprising the steps of:

l) transmitting, after the sub-step k4) of adding, by each of said sub-image geometry processors, to a corresponding sub-image rasterization-visibility tracing processor, a transformed, image-space representation of each of the primitives in the corresponding sub-image reprojection list;

wherein, for each sub-image rasterization-visibility tracing processor, the step i) of adding comprises the step of transmitting the primitives in object-space representation, determined to be newly visible in a sub-image by the visibility tracing step g), to a corresponding sub-image reprojection list accessed by a corresponding sub-image geometry processor.

104. The method according to claim 103, wherein the step l) of transmitting comprises the sub-step of l1) storing the transmitted primitives, in image-space representation, in a list of visible primitives for the corresponding sub-image rasterization-visibility tracing processor whereby the sub-image rasterizing processor can directly access the list of visible primitives for the sub-image after the rasterization of the primitives.

105. The method according to claim 104, wherein the sub-step of l1) of transmitting enables removing primitives subsequently determined to be occluded by the rasterization-visibility tracing processor by further comprising the sub-steps of:

l1a) transmitting, with each primitive, the index location of the primitive in said object-space sub-image list of visible primitives maintained by the sub-image geometry processor; and

l1b) storing the transmitted primitive, together with a corresponding index location in the corresponding object-space list maintained by the corresponding sub-image geometry processor.

106. The method according to claim 105, further comprising the step m) of removing occluded graphics primitives from the corresponding object-space and image-space sub-image lists maintained by the respective sub-image processors, the step m) of removing comprising the sub-steps of:

m1) reading, by the sub-image rasterization-visibility tracing processor, exposed samples of the corresponding augmented sub-image depth buffer, after rasterizing all of the sub-image primitives;

m2) determining, using the augmented sub-image depth buffer, source primitives corresponding to the exposed samples;

m3) writing data to the corresponding image-space sub-image reprojection list to indicate which of the primitives are represented by exposed samples in the augmented sub-image buffer;

m4) subsequently reading the image-space sub-image reprojection list to identify primitives that were not indicated to be exposed by the indicating step m3);

m5) transmitting, to the corresponding sub-image geometry processor by the sub-image rasterization-visibility tracing processors, previously transmitted indices in the object-space visible primitive list, of those primitives not indicated to be exposed in the step m4); and

m6) indicating as removed from the object-space sub-image visible primitive list, by the corresponding sub-image geometry processor, the primitives for which indices are transmitted to the processor in step m5.

107. The method according to claim 106, wherein the sub-step m1) of reading comprises the step of reading using a spatially coherent read pattern that minimizes non-local memory accesses.

108. The method according to claim 106, wherein the sub-step m3) of writing comprises writing an index of the corresponding primitive in the image-space sub-image reprojection list;

and

wherein the determining sub-step m2) directly references the image-space sub-image display list for efficiency.

109. The method according to claim 101, wherein the step j) of assigning comprises the step of statically assigning each of plural sub-image processors to a respective sub-image before the step a) of transforming.

110. The method according to claim 101, wherein the step j) of assigning comprises statically assigning each of plural sub-image processors to a plurality of sub-images.

111. The method according to claim 101, wherein the sub-step k2) of classifying comprises the sub-sub-steps of:

k2a) storing a bitcode for each previously visible primitive in a sub-image indicating which borders of the sub-image are intersected by each edge of the each previously visible primitive; and

k2b) determining, for each frame, redistribution of the each previously visible primitive to adjacent sub-images based on changes in the bitcode.

112. The method according to claim 101, further comprising the step l) of removing occluded graphics primitives from corresponding sub-image reprojection lists maintained by the respective sub-image processors, the step l) of removing comprising the sub-steps of:

l1) reading, by the sub-image processor, the exposed samples of the corresponding augmented sub-image depth buffer, following the rasterization of all of the sub-image primitives;

l2) determining, during said sub-step l1) of reading of augmented sub-image depth buffer, the source primitives corresponding to the exposed samples of the buffer;

l3) indicating exposed primitives, by writing data to the corresponding sub-image reprojection list which indicates which of the primitives are represented by exposed samples in the augmented sub-image buffer;

l4) subsequently reading the sub-image reprojection list to identify those primitives that were not indicated to be exposed by indicating step l3); and

l5) removing the primitives identified as occluded in step l4) from the corresponding sub-image reprojection list.

113. A computer-implemented method of generating an image sequence, 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 for a current frame;

d) storing, in a first augmented depth buffer for the current frame, depth values and primitive references produced by rasterizing said previously visible primitives for the current frame;

e) retaining, in a second augmented depth buffer for the previous frame, the depth values and primitive references produced by rasterizing said previously visible primitives for the previous frame;

f) determining, using the first augmented depth buffer, a location in the current frame which potentially contains a primitive that has newly penetrated the view frustum, the step f) of determining comprising the sub-steps of;

f1) subtracting a previous view frustum from a current view frustum to produce a difference frustum,

f2) projecting the difference frustum onto the viewport for the current frame, and

f3) identifying locations in the first augmented depth buffer that correspond to the projection of the difference frustum;

g) searching in said location to find a newly visible primitive in the current frame using an image-order, front-to-back, visibility tracing method of visible surface determination;

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

i) rasterizing the newly visible primitive using depth-comparison rasterization to complete the current frame.

114. The method according to claim 113, wherein the step g) of searching comprises searching using an image-order, front-to-back ray casting method of visible surface determination wherein a depth of the search is limited to regions of space in which said difference frustum and rays of said ray casting method intersect.