Method and system for efficiently drawing subdivision surfaces for 3D graphics

• US 6,078,331 A
• Filed: 09/30/1996
• Issued: 06/20/2000
• Est. Priority Date: 09/30/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Pulli, Kari Antero, Segal, Mark Gordon
• Primary Examiner(s): Kim, Matthew M.
• Assistant Examiner(s): MANCUSO, HUEDUNG XUAN CAO
• Application Number:
  US08/719,818
• Time in Patent Office: 1,359 Days
• Field of Search: 345/421, 345/422, 345/423, 345/425
• US Class Current: 345/423
• CPC Class Codes: A63F 2300/663 for simulating liquid objects, e.g. water, gas, fog, snow, clouds
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A process for efficiently drawing subdivision surfaces. The present invention operates within a computer system for visually displaying 3 dimensional (3D) surfaces on a display. The present invention pulls polygons from a polygon mesh of a 3D surface. The polygons are stored into a 2 dimensional array such that the vertices of the polygons occupy nodes of the 2 dimensional array and are readily accessed. The polygons are subsequently divided into a plurality of resulting polygons. The resulting polygons are then sent to a graphics pipeline, wherein the graphics pipeline renders the resulting polygons into a 3D image on the computer display.

Claims

1. In a computer system having a processor and a display, a computer implemented method for computing a subdivision surface by incrementally processing and outputting the subdivision surface to a final subdivision level to more accurately render a 3 dimensional (3D) surface, the method comprising the computer implemented steps of:

a) pulling polygons from a polygon mesh of a 3D surface;

b) storing the polygons into a 2 dimensional array such that the vertices of the polygons occupy nodes of the 2 dimensional array;

c1) subdividing the polygons stored in a first portion of the 2 dimensional array into resulting polygons;

c2) outputting the resulting polygons stored in the first portion to the graphics pipeline such that memory previously storing the first portion can be reused, wherein the resulting polygons stored in the first portion have been subdivided by at least three levels;

c3) subdividing the polygons stored in a second portion of the 2 dimensional array into resulting polygons;

c4) outputting the resulting polygons stored in the second portion to the graphics pipeline; and

d) outputting the resulting polygons into a graphics pipeline wherein the graphics pipeline renders the resulting polygons into a 3D image on a computer display.

2. The method of claim 1 further including the step of subdividing the polygons stored in the 2 dimensional array by using a plurality of graphics co-processors in the computer system.

3. The method of claim 1 further comprising the steps of:

a1) pulling a plurality of triangle polygon pairs from the polygon mesh, when the polygon mesh is built with a plurality of triangle polygons; and

b1) storing the plurality of triangle polygon pairs into the 2 dimensional array such that the vertices of the plurality of polygon pairs occupy the nodes of the 2 dimensional array.

4. The method of claim 3, wherein step a1) further comprises the step of pulling the plurality of triangle polygon pairs from the polygon mesh such that the polygon mesh is not broken into a plurality of discontiguous polygon meshes.

5. The method of claim 4, wherein step a1) further comprises the steps of:

assigning a priority to each of the plurality of triangle polygons such that triangle polygons, out of the plurality of triangle polygons, having a larger number of neighboring polygons are assigned a higher priority; and

pairing the triangle polygons, out of the plurality of triangle polygons, having the higher priority before pairing other triangle polygons, out of the plurality of polygons.

6. The method of claim 1 further comprising the steps of:

a2) pulling a plurality of quadrilateral polygons from the polygon mesh, when the polygon mesh is built with a plurality of quadrilateral polygons; and

b2) storing the plurality of quadrilateral polygons into the 2 dimensional array such that the vertices of the plurality of quadrilateral polygons occupy the nodes of the 2 dimensional array.

7. The method of claim 1, further comprising the steps of:

determining whether the resulting polygons stored in the first portion are at a final subdivision level;

subdividing the resulting polygons stored in the first portion, if the resulting polygons stored in the first portion are not at a final subdivision level, comprising the steps of;

subdividing the polygons stored in the first portion into resulting polygons at the final subdivision level;

calculating final positions and normals for the resulting polygons stored in the first portion; and

outputting the resulting polygons at the final subdivision level stored in the first portion before subdividing the polygons in the second portion.

8. The method of claim 1 further including the step of subdividing the polygons stored in the 2 dimensional array by using a plurality of central processing units in the computer system.

9. In a computer system having a processor and a display for visually displaying 3 dimensional (3D) surfaces, a computer implemented method for computing a subdivision surface by incrementally processing and outputting the subdivision surface to a final subdivision level, the surface modeled by a polygon mesh built with triangle polygons (triangles), the method comprising the computer implemented steps of:

a) pulling a plurality of triangles from a triangle mesh in a plurality of triangle pairs;

b) storing the plurality of triangle pairs into a 2 dimensional array such that the vertices of the plurality of triangle pairs occupy nodes of the 2 dimensional array;

c1) subdividing the triangles stored in a first portion of the 2 dimensional array into resulting triangles;

c2) outputting the resulting triangles stored in the first portion such that memory previously storing the first portion can be reused, wherein the resulting polygons stored in the first portion have been subdivided by at least three levels;

c3) subdividing the triangles stored in a second portion of the 2 dimensional array into resulting triangles;

c4) outputting the resulting triangles stored in the second portion; and

d) outputting the plurality of resulting triangles.

10. The method of claim 9 further including the steps of:

of subdividing the triangles stored in the 2 dimensional array by using a plurality of graphics co-processors in the computer system; and

outputting the plurality of resulting triangles into a graphics pipeline, wherein the graphics pipeline renders the plurality of resulting triangles into a 3D image on a computer display.

11. The method of claim 9, wherein step a) further comprises the step of pulling the plurality of triangle pairs from the triangle mesh such that the triangle mesh is not broken into a plurality of discontiguous triangle meshes.

12. The method of claim 9 wherein step c) further comprises steps of:

c1) subdividing the triangles stored in a first portion of the 2 dimensional array into resulting triangles;

c2) outputting the resulting triangles stored in the first portion;

c3) subdividing the triangles stored in a second portion of the 2 dimensional array into resulting triangles; and

,

c4) outputting the resulting triangles stored in the second portion.

13. The method of claim 9, further comprising the steps of:

determining whether the resulting triangles stored in the first portion are at a final subdivision level;

subdividing the resulting triangles stored in the first portion, if the resulting triangles stored in the first portion are not at a final subdivision level, the subdividing comprising the steps of;

subdividing the triangles stored in the first portion into resulting triangles at the final subdivision level;

calculating final positions and normals for the resulting triangles stored in the first portion; and

outputting the resulting triangles stored in the first portion before subdividing the triangles in the second portion.

14. The method of claim 9 further including the step of partitioning the 2 dimensional array storing the plurality of triangles and subdividing the triangles stored in the 2 dimensional array by using a plurality of central processing units in the computer system.

15. A computer system having a processor coupled to a bus and a memory coupled to the bus, the memory for containing a set of instructions that when executed by the processor causes the computer system to implement a method of computing a subdivision surface by incrementally processing and outputting the subdivision surface to a final subdivision level to more accurately render a 3 dimensional (3D) surface, the method comprising the computer system performing the steps of:

a) pulling polygons from a polygon mesh of a 3D surface;

b) storing the polygons into a 2 dimensional array such that the vertices of the polygons occupy nodes of the 2 dimensional array;

c1) subdividing the polygons stored in a first portion of the 2 dimensional array into resulting polygons;

c2) outputting the resulting polygons stored in the first portion to the graphics pipeline such that memory previously storing the first portion can be reused, wherein the resulting polygons stored in the first portion have been subdivided by at least three levels;

c3) subdividing the polygons stored in a second portion of the 2 dimensional array into resulting polygons;

c4) outputting the resulting polygons stored in the second portion to the graphics pipeline; and

d) outputting the resulting polygons into a graphics pipeline wherein the graphics pipeline renders the resulting polygons into a 3D image on a computer display.

16. The method of claim 15 further including the step of subdividing the polygons stored in the 2 dimensional array by using a plurality of graphics co-processors in the computer system.

17. The method of claim 15 further comprising the steps of:

a1) pulling a plurality of triangle polygon pairs from the polygon mesh, when the polygon mesh is built with a plurality of triangle polygons; and

b1) storing the plurality of triangle polygon pairs into the 2 dimensional array such that the vertices of the plurality of polygon pairs occupy the nodes of the 2 dimensional array.

18. The method of claim 17, wherein step a1) further comprises the step of pulling the plurality of triangle polygon pairs from the polygon mesh such that the polygon mesh is not broken into a plurality of discontiguous polygon meshes.

19. The method of claim 18, wherein step a1) further comprises the steps of:

assigning a priority to each of the plurality of triangle polygons such that triangle polygons, out of the plurality of triangle polygons, having a larger number of neighboring polygons are assigned a higher priority; and

pairing the triangle polygons, out of the plurality of triangle polygons, having the higher priority before pairing other triangle polygons, out of the plurality of polygons.

20. The method of claim 15 further comprising the steps of:

a2) pulling a plurality of quadrilateral polygons from the polygon mesh, when the polygon mesh is built with a plurality of quadrilateral polygons; and

b2) storing the plurality of quadrilateral polygons into the 2 dimensional array such that the vertices of the plurality of quadrilateral polygons occupy the nodes of the 2 dimensional array.

21. The method of claim 15, further comprising the steps of:

determining whether the resulting polygons stored in the first portion are at a final subdivision level;

subdividing the resulting polygons stored in the first portion, if the resulting polygons stored in the first portion are not at a final subdivision level, comprising the steps of;

subdividing the polygons stored in the first portion into resulting polygons at the final subdivision level;

calculating final positions and normals for the resulting polygons stored in the first portion; and

outputting the resulting polygons at the final subdivision level stored in the first portion before subdividing the polygons in the second portion.

22. The method of claim 15 further including the step of subdividing the polygons stored in the 2 dimensional array by using a plurality of central processing units in the computer system.

23. In a graphics computer system for rendering 3D images, a computer implemented method for efficiently computing a subdivision surface of a 3D object by incrementally processing and outputting the subdivision surface to a final subdivision level, the method comprising the computer implemented steps of:

pulling polygons from a polygon mesh representative of a 3D surface;

storing the polygons into a 2 dimensional array such that the vertices of the polygons occupy nodes of the 2 dimensional array, the 2 dimensional array realized in a computer readable memory;

incrementally processing the 2 dimensional array to a final subdivision level using a sliding window process comprising the steps of;

a) storing an initial portion of the 2 dimensional array into intermediate storage to initialize a window of the 2 dimensional array for processing;

b) incrementally calculating subdivision vertex coordinates for each row of the initial portion;

c) upon subdividing one row of the initial portion to a final subdivision level, wherein the one row has been subdivided by at least three levels, transferring the one row from intermediate storage to a graphics pipeline for rendering;

d) replacing the one row in the initial portion with a subsequent row of the 2 dimensional array to reuse memory previously occupied by the one row; and

e) repeating steps b) through d) until the 2 dimensional array is processed to a final subdivision level, such that the window for processing the 2 dimensional array slides from the initial portion through the entirety of the 2 dimensional array.

24. The method of claim 23, wherein the intermediate storage is a subportion of the computer readable memory which stores the 2 dimensional array, and wherein the sliding window process enables the processing of the 2 dimensional array to the final subdivision level without geometrically expanding an amount of the computer readable memory occupied by the 2 dimensional array.

25. The method of claim 23, wherein the sliding window process stores three rows of the 2 dimensional array for each level of subdivision in the initial portion.

26. The method of claim 25, wherein an additional two rows of the 2 dimensional array are stored in the initial portion for computing final vertex coordinates and normal vectors.

27. The method of claim 23, wherein the sliding window processes progresses through the 2 dimensional array processing successive 3 row increments of the 2 dimensional array.

28. In a graphics computer system for rendering 3D images, a computer implemented method for efficiently computing a subdivision surface of a 3D object by incrementally processing and outputting the subdivision surface to a final subdivision level, the method comprising the computer implemented steps of:

pulling polygons from a polygon mesh representative of a 3D surface;

storing the polygons into a 2 dimensional array such that the vertices of the polygons occupy nodes of the 2 dimensional array, the 2 dimensional array realized in a computer readable memory;

incrementally processing the 2 dimensional array to a final subdivision level using a sliding window process comprising the steps of;

a) storing an initial 3 rows of the 2 dimensional array into intermediate storage to initialize a window of the 2 dimensional array for processing, wherein the initial 3 rows are at a subdivision level J;

b) spliting the diagonal and vertical edges between the first and second row vertices of the initial 3 rows to obtain a first row support vertices at subdivision level J+1;

c) splitting the horizontal edges and updating the vertices between the first and second row vertices of the initial 3 rows to obtain a second row of support vertices at a subdivision level J+1;

d) splitting the vertical and diagonal edges connecting the second and third rows of the initial 3 rows to obtain a second row of support vertices at the subdivision level J+1;

e) storing a next row of vertices from the 2 dimensional array as a subsequent row of the initial portion such that the edges of the next row at level j provide neighbors needed for splitting the horizontal edges and updating the vertex coordinates in the middle rows, and such that resulting new and updated vertices become a new lowest row at level j+1;

f) repeating steps b-e until the first row is at a final subsivision level J+i, wherein the first row has been subdivided by at least three levels, and outputting the first row to a graphics pipeline for rendering and replacing the first row with a new row from the 2 dimensional array to reuse memory previously occupied by the first row; and

g) repeating steps b) through f) until the entire 2 dimensional array has been processed and rendered at the final subdivision level J+i such that the window for processing the 2 dimensional array slides from the initial three rows through the entirety of the 2 dimensional array.

29. The method of claim 28, wherein the intermediate storage is a subportion of the computer readable memory which stores the 2 dimensional array, and wherein the sliding window process enables the processing of the 2 dimensional array to the final subdivision level without geometrically expanding an amount of the computer readable memory occupied by the 2 dimensional array.

30. In a graphics computer system for rendering 3D images, a computer implemented method for efficiently computing a subdivision surface of a 3D object by incrementally processing and outputting the subdivision surface to a final subdivision level, the method comprising the computer implemented steps of:

pulling triangle polygons from a polygon mesh representative of a 3D surface, wherein the triangle polygons are pulled from the polygon mesh using a pairing algorithm, wherein the triangle polygons are pulled from the polygon mesh in unique pairs without breaking the polygon mesh into discontiguous portions;

storing the unique pairs of triangle polygons into a 2 dimensional array such that the vertices of the triangle polygons occupy nodes of the 2 dimensional array, the 2 dimensional array realized in a computer readable memory;

incrementally processing the 2 dimensional array to a final subdivision level using a sliding window process comprising the steps of;

a) storing an initial portion of the 2 dimensional array into intermediate storage to initialize a window of the 2 dimensional array for processing;

b) incrementally calculating subdivision vertex coordinates for each row of the initial portion;

c) upon subdividing one row of the initial portion to a final subdivision level, wherein the one row has been subdivided by at least three levels, and transferring the one row from intermediate storage to a graphics pipeline for rendering;

d) replacing the one row in the initial portion with a subsequent row of the 2 dimensional array to reuse memory previously occupied by the one row; and

e) repeating steps b) through d) until the 2 dimensional array is processed to a final subdivision level, such that the window for processing the 2 dimensional array slides from the initial portion through the entirety of the 2 dimensional array.

31. The method of claim 30, wherein the pairing algorithm includes the steps of:

f) inserting each triangle polygon of the polygon mesh into one of a plurality of priority sets as determined by a number of unpaired neighboring triangle polygons, wherein triangle polygons with 0 or 1 free neighboring triangle polygons are assigned to a highest priority set, and the triangles with 3 free neighbors are assigned to a lowest priority set;

g) selecting a triangle from a highest non-empty priority set and pairing it with a neighboring triangle polygon the highest priority set;

h) pulling the paired triangles from the polygon mesh; and

i) promoting a remaining neighboring triangle polygon to a higher priority set; and

repeating steps j) through k) to pull all triangle polygons from the polygon mesh.