Segmenting compressed graphics data for parallel decompression and rendering

• US 6,459,429 B1
• Filed: 06/14/1999
• Issued: 10/01/2002
• Est. Priority Date: 06/14/1999
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Deering, Michael F.
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US09/332,827
• Time in Patent Office: 1,205 Days
• Field of Search: 345/419, 345/420, 345/423, 345/555, 345/556, 382/232-234, 382/239-240
• US Class Current: 345/423
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A graphics system and method for reducing redundant transformation and lighting calculations performed on vertices that are shared by more than one geometric primitive is disclosed. The amount of data transmitted in certain data blocks may be reduced by incorporating a multicast/unicast bit into each data block. This bit may then be set to instruct the control unit to use the current 3D geometry data or state information for subsequent vertices. This may increase efficiency by allowing subsequent vertices using the same 3D geometry data to transfer less data. Conversely, if a vertex has wholly independent 3D geometry data, then its multicast/unicast bit may be set to invoke use of the current 3D geometry data on the current vertex as opposed to all future vertices. The reduction in redundant calculations is accomplished by delaying the formation of geometric primitives until after transformation and lighting has been performed on the vertices. Transformation and or lighting are performed independently on a vertex-by-vertex basis without reference to which geometric primitives the vertices belong to. After transformation and or lighting, geometric primitives may be formed utilizing previously generated connectivity information. The connectivity information may include mesh buffer references, vertex tags, and or other types of information.

Claims

1. A graphics system comprising:

a control unit configured to receive compressed 3D geometry data;

a plurality of geometry decompressors, wherein each of said decompressors is configured to receive a portion of said compressed 3D geometry data from said control unit and decompress said portion of said compressed 3D geometry data into a plurality of vertices, wherein said decompressors are configured to operate independently and in parallel; and

a plurality of processors, wherein each processor is configured to transform said vertices from a corresponding one of the decompressors into a different coordinate frame for rendering, wherein said processors transform said vertices prior to primitive assembly.

2. The graphics system as recited in claim 1, further comprising one or more setup units configured to assemble geometric primitives from said transformed vertices provided by said processors, wherein a first of said setup units is configured to use and reuse said transformed vertices stored in a first transformed vertex memory to form a first subset of said geometric primitives.

3. The graphics system as recited in claim 2, wherein said first setup unit is configured to reuse said transformed vertices stored in said transformed vertex memory to assemble non-sequential geometric primitives.

4. The graphics system as recited in claim 1, wherein each decompressor is configured to maintain a separate copy of state information used by the decompressor in performing decompression.

5. A graphics system comprising:

a control unit configured to receive compressed 3D geometry data; and

a plurality of decompressors, wherein said control unit is configured to convey portions of said 3D geometry data to each of said decompressors, wherein said decompressors are configured to decompress the 3D geometry data into one or more vertices, wherein said control unit is configured to route a first subset of said portions to individual decompressors, and wherein said control unit is configured to route a second subset of said portions to all of said decompressors.

6. The graphics system as recited in claim 5, wherein said compressed 3D geometry data comprises an ordered sequence of blocks, wherein said blocks are either unicast or multicast, wherein said control unit is configured to convey each unicast block to one of said decompressors according to a load balancing scheme, wherein said control unit is configured to convey said multicast blocks to more than one of said decompressors.

7. The graphics system as recited in claim 6, wherein said control unit is configured to detect control information within said multicast blocks, wherein said control unit is configured to use said control information to determine which of said plurality of decompressors will receive said multicast blocks.

8. The graphics system as recited in claim 6, wherein said blocks comprise an multicast/unicast bit, and wherein said control unit is configured to read said multicast/unicast bit to determine whether a particular block is a multicast block or unicast block.

9. The graphics system as recited in claim 6, wherein said blocks further comprise a fixed-length field indicative of the length of said block.

10. The graphics system as recited in claim 6, wherein said blocks further comprise a variable-length field indicative of the length of said block.

11. The graphics system as recited in claim 6, wherein said blocks further comprise a plurality of header-body pairs, wherein each header is indicative of either the location of the corresponding body or the length of the corresponding body.

12. The graphics system as recited in claim 6, wherein said headers have a fixed length, and wherein said bodies have a variable length.

13. The graphics system as recited in claim 6, wherein each header is separated from the corresponding body by one or more other headers.

14. The graphics system as recited in claim 6, wherein said blocks are variable length, and wherein each block comprises a variable-length no-op, wherein said variable-length no-op comprises length information for the block.

15. The graphics system as recited in claim 6, wherein each bock further comprises instructions that set state information usable by said decompressors during compression.

16. The graphics system as recited in claim 15, wherein each bock further comprises instructions that set state information within said decompressors, wherein each decompressor is configured to utilize said state information to decompress said geometry data.

17. The graphics system as recited in claim 16, wherein said state information comprises at least color state information and normal state information.

18. The graphics system as recited in claim 16, wherein said multicast blocks comprise solely state-changing information.

19. The graphics system as recited in claim 16, wherein each decompressor comprises a mesh buffer.

20. The graphics system as recited in claim 16, further comprising:

a plurality of transformation units, each configured to receive and transform vertices from one of said decompressors; and

one or more setup units, each comprising a transformed vertex memory, wherein said setup units are configured to receive said transformed vertices and assemble geometric primitives therefrom.

21. The graphics system as recited in claim 20, further comprising one or more draw units, wherein said draw units are configured to receive and render said geometric primitives from said setup units.

22. The graphics system as recited in claim 21, further comprising a sample buffer, and or more sample-to-pixel calculation units, wherein said draw units are configured to render samples into said sample buffer, and wherein said sample-to-pixel calculation units are configured to filter said samples into pixels that are usable to refresh a display device.

23. The graphics system as recited in claims 20, 16 wherein said transformation units are further configured to perform selected vertex processes on said transformed vertices.

24. A method for decompressing compressed 3D geometry data, the method comprising:

receiving said compressed 3D geometry data, wherein said compressed 3D geometry data comprises a series of blocks;

examining at least a portion of each block to determine whether the block is a multicast block or a unicast block;

routing each multicast block to a plurality of decompressors, wherein each decompressor stores an individual copy of state information, wherein said multicast blocks serve to update said individual copies of state information;

routing each unicast block to a single one of said plurality decompressor; and

decompressing said multicast and unicast blocks in said decompressors to form vertices, wherein each decompressor'"'"'s state information is used by the decompressor to perform said decompressing.

25. The method as recited in claim 24, wherein said series of blocks are ordered, and wherein said routing the unicast blocks is performed according to a load balancing scheme.

26. The method as recited in claim 24, further comprising conveying said vertices to one or more setup units, wherein each setup unit comprises a transformed vertex memory, wherein said setup units are configured to assemble said vertices into geometric primitives using a transformed vertex memory.

27. The method as recited in claim 26, wherein said geometric primitives are triangles.

28. The method as recited in claim 24, further comprising conveying said vertices to one or more setup units, wherein each setup unit comprises a transformed vertex memory, wherein said setup units are configured to assemble said vertices into geometric primitives using a transformed vertex memory.

29. The method as recited in claim 24, further comprising determining the length of each multicast and unicast block by reading a length field at a predetermined location within the block.

30. The method as recited in claim 24, further comprising determining the length of each multicast and unicast block by performing a computational process on a subset of data in each block.

31. The method as recited in claim 24, wherein said decompressing comprises reading header and body portion pairs from said blocks, wherein said header portions contain length information regarding said corresponding body portions, and wherein said header and body portions are separated by at least one intervening header/body portion.

32. The method as recited in claim 24, wherein said multicast and unicast blocks are variable length, and wherein each of said blocks comprises length information and routing information for the block.

33. The method as recited in claim 24, wherein said unicast blocks comprise per-vertex information.

34. The method as recited in claim 24, wherein said multicast blocks comprise state changing information usable by said decompressors to decompress said blocks into vertices.

35. The method as recited in claim 24, wherein each block comprises a multicast/unicast bit at a predetermined position, wherein said multicast/unicast bit is indicative of whether the block is a multicast block or a unicast block.

36. The method as recited in claim 24, wherein at least part of each decompressor'"'"'s state information is configured to be invalidated upon receiving a new multicast block.

37. The method as recited in claim 24, wherein said decompression state information includes color and transparency information.

38. The method as recited in claim 24, wherein said multicast blocks include solely state information and no per-vertex information.

39. The method as recited in claim 24, wherein said unicast blocks include solely per-vertex geometry information.

40. The method as recited in claim 24, further comprising setting at least part of said decompression state information for a particular decompressor in response to said particular decompressor beginning decompression of a new unicast block.

41. The method as recited in claim 24, wherein each unicast block comprises geometry data describing one or more vertices, wherein each unicast block comprises a restart tag associated with the first described vertex, wherein the restart tag causes the decompressor decompressing the unicast block to reset at least part of its decompression state information.

42. The method as recited in claim 24, wherein the first block in said series of blocks is configured to not rely upon any preexisting inheritable state information that is not explicitly inheritable.

43. The method as recited in claim 24, wherein each block in said series of blocks is configured to rely upon the state information set by the previous block in the series.

44. The method as recited in claim 24, wherein each of said blocks in said series of blocks may rely upon the state of a transformed vertex memory as set by a previous block in said series of blocks.

45. The method as recited in claim 24, wherein the first vertex in each unicast block is explicitly specified, wherein delta encoding is limited to vertexes after the first vertex, and wherein delta-delta encoding is limited to vertices occurring after the second vertex.

46. The method as recited in claim 24, wherein said unicast blocks comprise compressed geometry information describing a plurality of vertices using mesh buffer references, wherein said mesh buffer references do not rely upon vertices stored in said mesh buffer by previous blocks.

47. The method as recited in claim 24, further comprising guaranteeing that any multicast blocks occurring before a particular unicast block in said series of blocks will be received in sequence by every one of said plurality of decompressors before any subsequent blocks and said particular unicast block in said series of blocks.

48. The method as recited in claim 24, further comprising guaranteeing that any multicast blocks occurring before a particular unicast block in said series of blocks will be received by every one of said plurality of decompressors before any subsequent blocks and said particular unicast block in said series of blocks.

49. The method as recited in claim 24, wherein multicast blocks invalidate at least part of the previous global state attributes.

50. A computer software program embodied on a carrier medium, wherein said program comprises a plurality of instructions, wherein said instructions are configured to:

receive a set of compressed 3D geometry data, wherein said set of compressed 3D geometry data comprises a series of blocks;

examine at least a portion of each block to determine whether the block is a multicast block or a unicast block;

route each multicast block to a plurality of decompressors, wherein each decompressor stores an individual copy of decompression state information, wherein said multicast blocks serve to update said individual copies of decompression state information;

route each unicast block to a single one of said plurality decompressor; and

decompress said multicast and unicast blocks in said decompressors to form vertices, wherein each decompressor'"'"'s state information is used by the decompressor to perform said decompressing.

51. The method as recited in claim 50, wherein said carrier medium is either a carrier medium or a transmission medium.

52. The method as recited in claim 50, wherein said software program is a verifier program that is configured to verify the format of the compressed 3D geometry data before decompression of the 3D geometry data is begun.

53. A method for compressing 3D geometry data, the method comprising:

receiving said 3D geometry data, wherein said 3D geometry data comprises a plurality of vertices;

dividing said plurality of vertices into triangle meshes based upon said vertices'"'"' xyz position;

embedding mesh buffer references to reduce repetition of vertices in said meshes; and

formatting said meshes into a series of blocks to allow parallel decompression, wherein a first subset of said blocks are multicast blocks configured to be conveyed to a plurality of parallel decompressors, wherein a second subset of said blocks are unicast blocks configured to be conveyed to a single decompressor.

54. The method for as recited in claim 53, wherein said unicast blocks comprise decompression state information, and wherein said multicast blocks comprise geometry data.

55. The method for as recited in claim 53, wherein multicast blocks occurring before a particular unicast block in said series of blocks are configured to be received by every one of said plurality of decompressors before any subsequent blocks in said series of blocks.

56. The method as recited in claim 53, wherein said mesh buffer references create a mesh buffer state in each decompressor, wherein said mesh buffer state information is not shared between blocks.

57. The method as recited in claim 53, wherein said mesh buffer references create a transformed vertex memory state in each decompressor, wherein said transformed vertex memory state is not shared between blocks.

58. The method as recited in claim 53, wherein said multicast blocks convey state information to multiple decompress/render pipelines.

59. A computer software program for compressing 3D graphics, wherein the computer software program is embodied on a computer-readable media, wherein the program is configured to compress the 3D graphics data so as to allow parallel decompression in a graphics system having a plurality of parallel decompressors, wherein the computer software program comprises a plurality of instructions, wherein the plurality of instructions are configured to:

receive the 3D graphics data, wherein the 3D graphics data includes a plurality of vertices; and

form a sequence of blocks from the 3D graphics data, wherein the sequence of blocks includes multicast blocks and unicast blocks, wherein each unicast block includes one or more vertices configured to be distributed to one or more of the parallel decompressors in sequential order, wherein each multicast block includes state information configured to be distributed to all of the parallel decompressors.

60. The program as recited in claim 59, wherein the 3D graphics data is deterministic for each block in the sequence.

61. The program as recited in claim 59, wherein the results from decompressing the compressed 3D graphics data is the same regardless of which of the parallel decoders receives a particular unicast block.

62. A computer software program for decompressing 3D graphics data that has been compressed into a sequence of multicast and unicast blocks, wherein the software program comprises a plurality of instructions, wherein the plurality of instructions are configured to:

receive the sequence of multicast and unicast blocks; and

distribute the multicast and unicast blocks to a plurality of parallel decompressors, wherein the distributing is performed according to the following rules;

all multicast blocks are distributed to all of the decompressors in the same order as encoded in the sequence;

the unicast blocks are distributed to only one of the decompressors; and

all blocks are distributed in the same order as in the sequence.

63. A graphics system comprising:

a control unit configured to receive compressed 3D geometry data;

a plurality of geometry decompressors, wherein each of said decompressors is configured to receive a portion of said compressed 3D geometry data from said control unit and decompress said portion of said compressed 3D geometry data into a plurality of vertices, wherein said decompressors are configured to operate independently and in parallel; and

a plurality of processors, wherein each processor is configured to transform said vertices from a corresponding one of the decompressors into a different coordinate frame for rendering;

one or more setup units configured to assemble geometric primitives from said transformed vertices provided by the processors.

64. The graphics system of claim 63, wherein the one or more setup units are configured to assemble geometric primitives from said transformed vertices using connectivity information generated by the decompressors.