Method and system for reducing overflows in a computer graphics system

Abstract

A method and system for providing a graphical image on a display of a system is disclosed. The graphical image is provided from data describing a plurality of primitives. The display includes a plurality of pixels. The method and system include providing a plurality of variable-sized bins containing the plurality of primitives and rendering the plurality of primitives by rendering each of the plurality of variable-sized bins variable-sized bin by variable-sized bin.

What is claimed is:  
     
         1 . A method for providing a graphical image on a display of a system, the graphical image being provided from data describing a plurality of primitives, the display including a plurality of pixels, the method comprising the steps of: 
 (a) providing a plurality of variable-sized bins containing the plurality of primitives; and    (b) rendering the plurality of primitives by rendering each of the plurality of variable-sized bins variable-sized bin by variable-sized bin.    
     
     
         2 . The method of  claim 1  wherein the system includes a plurality of processors for processing a portion of the plurality of primitives in parallel, and wherein the variable-sized bin providing step (a) further includes the steps of: 
 (a1) storing the plurality of primitives in a plurality of bins;  
 (a2) determining if a part of a portion of the plurality of bins can be combined without causing the plurality of processors to overflow; and  
 (a3) combining the part of the portion of plurality of bins to provide the plurality of variable-sized bins if the part of the portion of the plurality of bins can be combined without causing the plurality of processors to overflow;  
 wherein the plurality of variable-sized bins can include fewer bins than the plurality of bins.  
 
     
     
         3 . The method of  claim 2  wherein the combining step (a3) further includes the steps of: 
 (a3i) combining the part of the portion of the plurality of bins so that a particular primitive of the plurality of primitives is provided only once for a corresponding variable-sized bin of the plurality of variable-sized bins.  
 
     
     
         4 . The method of  claim 2  wherein the variable-sized bin providing step (a) further includes the steps of: 
 (a4) providing a display list containing the plurality of primitives, the display list including the plurality of primitives ordered according to the plurality of variable-sized bins, wherein a particular primitive of the plurality of primitives is provided to the display list only once for a corresponding variable-sized bin of the plurality of variable-sized bins.  
 
     
     
         5 . The method of  claim 2  wherein each of the plurality of bins includes a first boundary, wherein each of the plurality of primitives intersects a second portion of the plurality of bins, and wherein the storing step (a1) further includes the step of: 
 (a1i) storing each of the plurality of primitives in the second portion of the plurality of bins based on whether the first boundary is crossed.  
 
     
     
         6 . The method of  claim 5  wherein each of the plurality of primitives includes a minimum y value, a top scan line, and bottom scan line, and wherein the storing step (a1) further includes the step of: 
 (a1ii) storing each of the plurality of primitives in the second portion of the plurality of bins in an order based on the minimum y value; and  
 (a1iii) storing the top scan line and the bottom scan line for each of the plurality of primitives in the second portion of the plurality of bins.  
 
     
     
         7 . The method of  claim 1  wherein the variable-sized bin providing step (a) further includes the steps of: 
 (a1) determining a plurality of bins for a previous frame; and  
 (a2) providing the plurality of bins containing the plurality of primitives.  
 
     
     
         8 . The method of  claim 7  wherein the system further includes a plurality of processors for processing a portion of the plurality of primitives in parallel and wherein the variable-sized bin providing step (a) further includes the step of: 
 (a3) storing the plurality of primitives in the plurality of bins;  
 (a4) determining if a part of a portion of the plurality of bins can be combined without causing the plurality of processors to overflow; and  
 (a5) combining the part of the portion of the plurality of bins to provide the plurality of variable-sized bins if the part of the portion of the plurality of bins can be combined without causing the plurality of processors to overflow;  
 wherein the plurality of variable-sized bins can include fewer bins than the plurality of bins.  
 
     
     
         9 . The method of  claim 8  wherein the combining step (a5) further includes the steps of: 
 (a5i) combining the part of the portion of the plurality of bins so that a particular primitive of the plurality of primitives is provided only once for a corresponding variable-sized bin of the plurality of variable-sized bins.  
 
     
     
         10 . The method of  claim 8  wherein the variable-sized bin providing step (a) further includes the steps of: 
 (a6) providing a display list containing the plurality of primitives, the display list including the portion of the plurality of primitives for each of the plurality of variable-sized bins ordered variable-sized bin by variable-sized bin, wherein a particular primitive of the plurality of primitives is provided to the display list only once for a corresponding variable-sized bin of the plurality of variable-sized bins.  
 
     
     
         11 . The method of  claim 7  wherein the system further includes a plurality of processors for processing a portion of the plurality of primitives in parallel and wherein the variable-sized bin providing step (a) further includes the step of: 
 (a3) determining if a portion of the plurality of bins causes the plurality of processors to overflow; and  
 (a4) splitting each bin of the portion of the plurality of bins into two bins.  
 
     
     
         12 . The method of  claim 1  wherein a second portion of the plurality of primitives intersects each of a portion of the plurality of variable-sized bins, wherein the plurality of primitives include a plurality of fragments intersecting each pixel of a portion of the plurality of pixels and wherein the rendering step (b) further includes the steps of: 
 (b1) rendering each of the plurality of variable-sized bins pixel by pixel in raster order, the plurality of fragments being provided pixel by pixel for the portion of the plurality of pixels.  
 
     
     
         13 . A computer-readable medium containing a program for providing a graphical image on a display of a system, the graphical image being provided from data describing a plurality of primitives, the display including a plurality of pixels, the program including instructions for: 
 (a) providing a plurality of variable-sized bins containing the plurality of primitives; and    (b) rendering the plurality of primitives by rendering each of the plurality of variable-sized bins variable-sized bin by variable-sized bin.    
     
     
         14 . The computer-readable medium of  claim 13  wherein the system includes a plurality of processors for processing a portion of the plurality of primitives in parallel, and wherein the variable-sized bin providing instructions (a) further includes instructions for: 
 (a1) storing the plurality of primitives in a plurality of bins;  
 (a2) determining if a part of a portion of the plurality of bins can be combined without causing the plurality of processors to overflow; and  
 (a3) combining the part of the portion of the plurality of bins if the portion of plurality of bins can be combined without causing the plurality of processors to overflow;  
 wherein the plurality of variable-sized bins can include fewer bins than the plurality of bins.  
 
     
     
         15 . The computer-readable medium of  claim 14  wherein the combining instructions (a3) further includes instructions for: 
 (a3i) combining the part of the portion of the plurality of bins so that a particular primitive of the plurality of primitives is provided only once for a corresponding variable-sized bin of the plurality of variable-sized bins.  
 
     
     
         16 . The computer-readable medium of  claim 14  wherein the variable-sized bin providing instructions (a) further includes instructions for: 
 (a4) providing a display list containing the plurality of primitives, the display list including the plurality of primitives ordered according to the plurality of variable-sized bins, wherein a particular primitive of the plurality of primitives is provided to the display list only once for a corresponding variable-sized bin of the plurality of variable-sized bins.  
 
     
     
         17 . The computer-readable medium of  claim 14  wherein each of the plurality of bins includes a first boundary, wherein each of the plurality of primitives intersects a second portion of the plurality of bins, and wherein the storing instructions (a1) further includes instructions for: 
 (a1i) storing each of the plurality of primitives in the second portion of the plurality of bins based on whether the first boundary is crossed.  
 
     
     
         18 . The computer-readable medium of  claim 17  wherein each of the plurality of primitives includes a minimum y value, a top scan line, and bottom scan line, and wherein the storing instructions (a1) further includes instructions for: 
 (a1ii) storing each of the plurality of primitives in the second portion of the plurality of bins in an order based on the minimum y value; and  
 (a1iii) storing the top scan line and the bottom scan line for each of the plurality of primitives in the second portion of the plurality of bins.  
 
     
     
         19 . The computer-readable medium of  claim 13  wherein the variable-sized bin providing instructions (a) further includes instructions for: 
 (a1) determining a plurality of bins for a previous frame; and  
 (a2) providing the plurality of bins containing the plurality of primitives.  
 
     
     
         20 . The computer-readable medium of  claim 19  wherein the system further includes a plurality of processors for processing a portion of the plurality of primitives in parallel and wherein the variable-sized bin providing instructions (a) further includes instructions for: 
 (a3) storing the plurality of primitives in the plurality of bins;  
 (a4) determining if a part of a portion of the plurality of bins can be combined without causing the plurality of processors to overflow; and  
 (a5) combining the part of the portion of the plurality of bins if the part of the portion of the plurality of bins can be combined without causing the plurality of processors to overflow;  
 wherein the plurality of variable-sized bins can include fewer bins than the plurality of bins.  
 
     
     
         21 . The computer-readable medium of  claim 20  wherein the combining instructions (a5) further includes instructions for: 
 (a5i) combining the part of the portion of the plurality of bins so that a particular primitive of the portion of the plurality of primitives is provided only once for a corresponding variable-sized bin of the plurality of variable-sized bins.  
 
     
     
         22 . The computer-readable medium of  claim 20  wherein a portion of the plurality of primitives intersect each of a second portion of the plurality of variable-sized bins and wherein the variable-sized bin providing instructions (a) further includes instructions for: 
 (a6) providing a display list containing the plurality of primitives, the display list including the portion of the plurality of primitives for each of the plurality of variable-sized bins ordered variable-sized bin by variable-sized bin, wherein a particular primitive of the portion of the plurality of primitives is provided to the display list only once for a corresponding variable-sized bin of the plurality of variable-sized bins.  
 
     
     
         23 . The computer-readable medium of  claim 19  wherein the system further includes a plurality of processors for processing a portion of the plurality of primitives in parallel and wherein the variable-sized bin providing instructions (a) further includes instructions for: 
 (a3) determining if a portion of the plurality of bins causes the plurality of processors to overflow; and  
 (a4) splitting each bin of the portion of the plurality of bins into two bins.  
 
     
     
         24 . The computer-readable medium of  claim 13  wherein a second portion of the plurality of primitives intersects each of a portion of the plurality of variable-sized bins, wherein the plurality of primitives include a plurality of fragments intersecting each pixel of a portion of the plurality of pixels and wherein the rendering instructions (b) further includes instructions for: 
 (b1) rendering each of the plurality of variable-sized bins pixel by pixel in raster order, the plurality of fragments being provided pixel by pixel for the portion of the plurality of pixels.  
 
     
     
         25 . A system for providing a graphical image on a display, the graphical image being provided from data describing a plurality of primitives, the display including a plurality of pixels, the system comprising: 
 means providing a plurality of variable-sized bins containing the plurality of primitives, the plurality of bins having a variable size; and    means, coupled with the providing means, for rendering the plurality of primitives by rendering each of the plurality of variable-sized bins variable-sized bin by variable-sized bin.    
     
     
         26 . The system of  claim 25  wherein the system includes a plurality of processors for processing a portion of the plurality of primitives in parallel, and wherein the variable-sized bin providing means further includes: 
 means for storing the plurality of primitives in a plurality of bins;  
 means for determining if a part of a portion of the plurality of bins can be combined without causing the plurality of processors to overflow; and  
 means for combining the part of the portion of the plurality of bins if the part of the portion of the plurality of bins can be combined without causing the plurality of processors to overflow;  
 wherein the plurality of variable-sized bins can include fewer bins than the plurality of bins.  
 
     
     
         27 . The system of  claim 26  wherein the variable-sized bin providing means further includes: 
 means for combining the part of the portion of the plurality of bins so that a particular primitive of the plurality of primitives is provided only once for a corresponding variable-sized bin of the plurality of variable-sized bins.  
 
     
     
         28 . The system of  claim 26  wherein the variable-sized bin providing means further includes: 
 means for providing a display list containing the plurality of primitives, the display list including the plurality of primitives ordered according to the plurality of variable-sized bins, wherein a particular primitive of the plurality of primitives is provided to the display list only once for a corresponding variable-sized bin of the plurality of variable-sized bins.  
 
     
     
         29 . The system of  claim 25  wherein the variable-sized bin providing means further includes: 
 means for determining a plurality of bins for a previous frame; and  
 means for providing the plurality of bins containing the plurality of primitives.  
 
     
     
         30 . The system of  claim 29  system further including a plurality of processors for processing a portion of the plurality of primitives in parallel and wherein the variable-sized bin providing means further includes: 
 means for storing the plurality of primitives in the plurality of bins;  
 means for determining if a part of a portion of the plurality of bins can be combined without causing the plurality of processors to overflow; and  
 means for combining the part of the portion of the plurality of bins if the portion of the plurality of bins can be combined without causing the plurality of processors to overflow;  
 wherein the plurality of variable-sized bins can include fewer bins than the plurality of bins.  
 
     
     
         31 . The system of  claim 30  further comprising a plurality of processors for processing a portion of the plurality of primitives in parallel and wherein the variable-sized bin providing means further includes: 
 means for determining if a portion of the plurality of bins causes the plurality of processors to overflow; and  
 means for splitting each bin of the portion of the plurality of bins into two bins.