Graphics system and method for rendering independent 2D and 3D objects using pointer based display list video refresh operations

• US 6,518,965 B2
• Filed: 10/04/2001
• Issued: 02/11/2003
• Est. Priority Date: 04/27/1998
• Status: Active Grant

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Interactive Silicon, Inc.
• Inventors: Dye, Thomas A., Geiger, Peter D., Alvarez, Manuel J. II
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US09/971,107
• Publication Number:
  US 20020158865A1
• Time in Patent Office: 495 Days
• Field of Search: 345/419, 345/420, 345/421, 345/619, 345/620, 345/426, 345/428
• US Class Current: 345/419
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 15/10 Geometric effects

Abstract

A spanning based method for rendering and display of 3D graphical data on a display device. The method first parses the geometry data, generates independent vertex-sorted geometric primitives (e.g., triangles) and then performs setup on the geometric primitives. The method then computes horizontal segments that make up each triangle, performs a Y sort of the triangles for each span line, and performs an X sort of triangle segments and vertices for each span line. The method then performs a Z rules determination for each span line to discard or reject hidden segments. The method then constructs the 3-D VDRL list for each span line comprising pointers which reference viewed triangle spans. During execution, the 3-D VDRL is read and interpreted to generate pixel data. The pixel data includes the viewed triangle spans and may include texture data or other data referenced by the VDRL.

Claims

1. A method for rendering one or more three dimensional images, the method comprising:

receiving geometry data, wherein the geometry data includes a plurality of parameters defining a plurality of vertices, wherein said plurality of vertices are usable to form a plurality of polygon primitives, and wherein said plurality of polygon primitives represent a surface of at least one three-dimensional object;

constructing a 3D virtual display refresh list in a memory in response to the geometry data, wherein said constructing comprises;

performing setup on polygons defined by said vertices, wherein said performing setup includes assembling a list of the parameters for each of the vertices and determining slope values for the polygon edges;

positioning the polygons in a spanning manner using the vertices of the polygons and the slope values for the polygon edges; and

constructing the 3D virtual display refresh list for each span line, the 3D virtual display refresh list comprising pointers which reference viewed polygon spans;

executing the 3D virtual display refresh list, wherein said executing includes reading the virtual display refresh list and generating pixel data in response thereto, wherein the pixel data is useable for rendering the one or more three dimensional images on a display device.

2. The method of claim 1, further comprising:

storing the pixel data into a system memory after said executing.

3. The method of claim 2, wherein the method operates to render the three dimensional images on a display screen of a display device, the method further comprising:

accessing the pixel data from the system memory; and

displaying said pixel data on the display screen of the display device in response to said accessing, wherein the pixel data is displayed in a spanning manner, wherein said displaying displays the one or more three dimensional images on the display screen.

4. The method of claim 1, wherein the method operates to render the three dimensional images on a display screen of a display device, the method further comprising:

displaying said pixel data on the display screen of the display device in response to said executing, wherein the pixel data is displayed in a spanning manner, wherein said displaying displays the one or more three dimensional images on the display screen.

5. The method of claim 1, wherein said positioning the polygons in a spanning manner comprises positioning the polygons in a manner corresponding to how the polygons are displayed on a display device.

6. The method of claim 1, wherein said positioning the polygons in a spanning manner comprises:

performing a Y sort of the polygons to sort the polygons in a Y order; and

performing an X sort of triangle segments for each span line.

7. The method of claim 1, further comprising:

performing a Z rules determination for each span line to eliminate unseen portions of polygons, wherein the Z rules determination is performed after said positioning the polygons in the spanning manner.

8. The method of claim 7, wherein said performing the Z rules determination operates to eliminate unseen triangle segments for one or more span lines.

9. The method of claim 1, further comprising:

compressing said pixel data to produce compressed pixel data;

storing said compressed pixel data into a memory;

decompressing said compressed pixel data after said storing to produce uncompressed pixel data; and

displaying said uncompressed pixel data on the display screen of the display device after said decompressing, wherein said displaying displays the one or more 3D images.

10. The method of claim 1, wherein the 3D virtual display refresh list contains information to determine changes in a rasterization state of triangle span segments;

and

wherein said rasterization state is synchronized with the flow of 3D VDRL data through a 3D graphics engine.

11. The method of claim 1, wherein said constructing the 3D virtual display refresh list is performed a plurality of times to produce a plurality of 3D virtual display refresh lists;

wherein said executing comprises executing the plurality of 3D virtual display refresh lists to generate the pixel data.

12. The method of claim 1, further comprising:

storing polygon static data in a memory;

wherein said constructing the 3D virtual display refresh list includes utilizing the polygon static data in constructing the 3D virtual display refresh list.

13. The method of claim 12, wherein the 3D virtual display refresh list references a plurality of texture map source addresses;

wherein said executing includes accessing texture data using the texture map source addresses and generating at least a subset of the pixel data in response to the texture data.

14. The method of claim 12, wherein 3D virtual display refresh list references a plurality of compressed texture map source addresses;

wherein said executing includes;

reading the virtual display refresh list;

reading a plurality of compressed texture map source data using the texture map source addresses;

decompressing said compressed texture map source data to produce uncompressed texture map source data;

generating at least a subset of the pixel data in response to the uncompressed texture map source data.

15. The method of claim 12, wherein constructing and executing the 3D virtual display refresh list uses data cache management for improved performance;

the method further comprising;

storing at least a portion of said polygon static data in a cache memory, wherein said storing includes performing allocation and reallocation of static data storage for constructing and/or executing the 3D virtual refresh list.

16. The method of claim 1, wherein the pixel data corresponds to the viewed polygon spans.

17. The method of claim 1, wherein the polygons are triangles;

wherein the 3D virtual display refresh list comprises pointers which reference viewed triangle spans; and

wherein the pixel data corresponds to the viewed triangle spans.

18. A method for rendering one or more three dimensional images, the method comprising:

receiving geometry data, wherein the geometry data includes a plurality of parameters defining a plurality of vertices, wherein said plurality of vertices are usable to form a plurality of polygon primitives, and wherein said plurality of polygon primitives represent a surface of at least one three-dimensional object;

constructing a 3D virtual display refresh list in a memory, wherein the 3D virtual display refresh list comprises pointers which reference viewed polygon spans, wherein said pointers reference the viewed polygon spans in a spanning manner as the viewed polygon spans are rendered on a display device; and

executing the 3D virtual display refresh list, wherein said executing includes reading the virtual display refresh list and generating pixel data in response thereto, wherein the pixel data is useable for rendering the one or more three dimensional images on a display device.

19. The method of claim 18, wherein said constructing the 3D virtual display refresh list comprises:

performing setup on polygons defined by said vertices, wherein said performing setup includes assembling a list of the parameters for each of the vertices and determining slope values for the polygon edges;

positioning the polygons in a spanning manner using the vertices of the polygons and the slope values for the polygon edges; and

constructing the 3D virtual display refresh list for each span line.

20. The method of claim 18, wherein the method operates to render the three dimensional images on a display screen of a display device, the method further comprising:

displaying said pixel data on the display screen of the display device after said executing, wherein said displaying displays the one or more three dimensional images on the display screen.

21. A system for rendering one or more three dimensional images, the system comprising:

an input for receiving geometry data, wherein the geometry data includes a plurality of parameters defining a plurality of vertices, wherein said plurality of vertices are usable to form a plurality of polygon primitives, and wherein said plurality of polygon primitives represent a surface of at least one three-dimensional object;

a memory for storing data;

a first engine coupled to the memory for constructing a 3D virtual display refresh list in the memory, wherein the first engine is operable to;

perform setup on polygons defined by said vertices, wherein said setup includes assembling a list of the parameters for each of the vertices and determining slope values for the polygon edges;

position the polygons in a spanning manner using the vertices of the polygons and the slope values for the polygon edges; and

construct the 3D virtual display refresh list for each span line, the 3D virtual display refresh list comprising pointers which reference viewed polygon spans; and

a second engine for executing the 3D virtual display refresh list, wherein the second engine is executable to read the virtual display refresh list and generate pixel data in response thereto, wherein the pixel data is useable for rendering the one or more three dimensional images on a display device.

22. The system of claim 21, wherein the pixel data is stored in the memory for later display.

23. The system of claim 21, wherein, in positioning the polygons in a spanning manner, the first engine is operable to:

perform a Y sort of the polygons to sort the polygons in a Y order; and

perform an X sort of triangle segments for each span line.

24. The system of claim 21, wherein the first engine is further operable to performing a Z rules determination for each span line to eliminate unseen portions of polygons, wherein the Z rules determination operates to eliminate unseen triangle segments for one or more span lines.

25. The system of claim 21, further comprising:

a display device coupled to the second engine;

wherein the second engine is operable to provide signals to the display device corresponding to the pixel data, and wherein the display device is operable to display the one or more three dimensional images on the display screen in response to the signals.

26. The system of claim 25, wherein the polygons are positioned in a spanning manner corresponding to how the polygons are displayed on the display device.

27. The system of claim 25, further comprising:

a compression/decompression engine, wherein the compression/decompression engine is operable to compress said pixel data to produce compressed pixel data and store said compressed pixel data into the memory;

wherein the compression/decompression engine is further operable to decompress said compressed pixel data to produce uncompressed pixel data and provide the uncompressed pixel data to the display device for display.

28. The system of claim 21, wherein the 3D virtual display refresh list contains information to determine changes in a rasterization state of triangle span segments;

and

wherein said rasterization state is synchronized with the flow of 3D VDRL data through the second engine.

29. The system of claim 21, wherein the first engine is operable to construct a plurality of 3D virtual display refresh lists;

wherein the second engine is operable to execute the plurality of 3D virtual display refresh lists to generate the pixel data.

30. The system of claim 21,

wherein the memory stores polygon static data;

wherein the second engine is operable to utilize the polygon static data in constructing the 3D virtual display refresh list.

31. The system of claim 30, wherein the 3D virtual display refresh list references a plurality of texture map source addresses;

wherein, in executing the 3D virtual display refresh list, the second engine is operable to access texture data using the texture map source addresses and generate at least a subset of the pixel data in response to the texture data.

32. The system of claim 30, further comprising:

a compression/decompression engine;

wherein 3D virtual display refresh list references a plurality of compressed texture map source addresses;

wherein, in executing the 3D virtual display refresh list, the second engine is operable to;

read the virtual display refresh list;

read a plurality of compressed texture map source data using the texture map source addresses;

wherein the compression/decompression engine is operable to decompress the compressed texture map source data to produce uncompressed texture map source data; and

generate at least a subset of the pixel data in response to the uncompressed texture map source data.

33. The system of claim 30, further comprising:

a cache memory for storing at least a portion of said polygon static data, wherein the first and second processors are coupled to the cache memory and are operable to perform allocation and reallocation of static data storage in the cache memory for constructing and/or executing the 3D virtual refresh list.

34. A system for rendering one or more three dimensional images, the system comprising:

an input for receiving geometry data, wherein the geometry data includes a plurality of parameters defining a plurality of vertices, wherein said plurality of vertices are usable to form a plurality of polygon primitives, and wherein said plurality of polygon primitives represent a surface of at least one three-dimensional object;

a memory for storing data;

a first engine coupled to the memory for constructing a 3D virtual display refresh list in the memory, wherein the 3D virtual display refresh list comprises pointers which reference viewed polygon spans; and

a second engine for executing the 3D virtual display refresh list, wherein the second engine is executable to read the virtual display refresh list and generate pixel data in response thereto, wherein the pixel data is useable for rendering the one or more three dimensional images on a display device.

35. The system of claim 34, wherein, in constructing the 3D virtual display refresh list, the first engine is operable to:

perform setup on polygons defined by said vertices, wherein said setup includes assembling a list of the parameters for each of the vertices and determining slope values for the polygon edges;

position the polygons in a spanning manner using the vertices of the polygons and the slope values for the polygon edges; and

construct the 3D virtual display refresh list for each span line.

36. A method for rendering one or more three dimensional images, the method comprising:

receiving geometry data, wherein the geometry data includes a plurality of parameters defining a plurality of vertices, wherein said plurality of vertices are usable to form a plurality of line primitives, and wherein said plurality of line primitives represent a surface of at least one three-dimensional object;

constructing a 3D virtual display refresh list in a memory in response to the geometry data, wherein the 3D virtual display refresh list is constructed for a plurality of span lines, wherein the 3D virtual display refresh list comprises pointers which reference viewed line primitives;

executing the 3D virtual display refresh list, wherein said executing includes reading the virtual display refresh list and generating pixel data in response thereto, wherein the pixel data is useable for rendering the one or more three dimensional images on a display device.

37. The method of claim 36, wherein said constructing the 3D virtual display refresh list comprises:

performing setup on the line primitives defined by said vertices, wherein said performing setup includes assembling a list of the parameters for each of the vertices;

positioning the line primitives in a spanning manner using vertex position information of the vertices; and

constructing the 3D virtual display refresh list for each span line.

38. The method of claim 37, wherein said positioning the line primitives in a spanning manner comprises:

performing a Y sort of the line primitives to sort the line primitives in a Y order; and

performing an X sort of vertices for position within each span line.

39. The method of claim 37, further comprising:

performing a Z rules determination for each span line to eliminate unseen lines, wherein the Z rules determination is performed after said positioning the line primitives in the spanning manner.

40. The method of claim 36, further comprising:

displaying said pixel data on the display screen of the display device in response to said executing, wherein the pixel data is displayed in a spanning manner, wherein said displaying displays the one or more three dimensional images on the display screen.

41. A method for rendering one or more three dimensional images, the method comprising:

receiving geometry data, wherein the geometry data includes a plurality of parameters defining a plurality of vertices, wherein said plurality of vertices are usable to form a plurality of point primitives, and wherein said plurality of point primitives represent a surface of at least one three-dimensional object;

constructing a 3D virtual display refresh list in a memory in response to the geometry data, wherein said constructing comprises;

performing setup on points defined by said vertices, wherein said performing setup includes assembling a list of the parameters for each of the vertices;

positioning the points in a spanning manner using vertex position information of the points; and

constructing the 3D virtual display refresh list for each span line, the 3D virtual display refresh list comprising pointers which reference viewed points; and

executing the 3D virtual display refresh list, wherein said executing includes reading the virtual display refresh list and generating pixel data in response thereto, wherein the pixel data is useable for rendering the one or more three dimensional images on a display device.

42. The method of claim 41, further comprising:

displaying said pixel data on the display screen of the display device in response to said executing, wherein the pixel data is displayed in a spanning manner, wherein said displaying displays the one or more three dimensional images on the display screen.