Abstract:
Computer-generated objects are tessellated into generalized shading regions having any number of vertices. The shading regions are passed to a shader via a generalized parametric scheme that accommodates shapes having different numbers of vertices. The shader determines and assigns color values to the exact area defined by each shading region, without requiring the use of approximations such as bounding boxes or ellipsoids. The use of generalized shading regions facilitates greater flexibility and accuracy in shading operations.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates generally to computer-generated graphics, and more particularly to shading techniques for assigning colors to regions of objects.  
           [0003]    2. Description of the Background Art  
           [0004]    In computer graphics generation, the process of determining color values for regions of a graphic object is referred to as “shading.” Many different techniques for shading are well known in the art; see, for example, J. Foley et al.,  Computer Graphics: Principles and Practice,  2d ed. (1995), pp. 734-41. Typically, software for creating computer graphic images includes a renderer, for determining color values of pixels in the generated image, and a shader that performs shading operations for a computer-generated object. The shader uses any or all of an object definition, texture map, lighting and shadow parameters, and the like to generate a shaded object. The shader may use well known interpolation techniques, such as Gouraud or Phong shading, in order to determine color values for application to the graphic object.  
           [0005]    The task of a renderer is to determine a color value for each pixel of a graphic image. In determining a color value for a pixel; the renderer determines what portion of an object lies at that pixel location, and calls a shader to apply relevant shading algorithms to combine object surface features, textures, lighting, and the like, to generate a color value for a shading region for the pixel. The renderer then applies the color value to the pixel.  
           [0006]    One undesirable aspect of many conventional shading techniques is the presence of artifacts such as Moiré patterns, jagged edges, noise, and/or flickering. Such artifacts can be reduced somewhat by the conventional technique of antialiasing. Rather than computing colors at a single, arbitrarily small point within a pixel, antialiasing techniques involve estimating an average color at many points or across small regions of an object. Conventionally, this is accomplished by dividing, or tessellating, the object surface into a grid of small polygons having rectangular shape, referred to herein as micropolygons or shading regions. Shading regions are typically approximately the size of pixels, and are conventionally represented as a rectangle of given width and height. See, for example, R. L. Cook, L. Carpenter, E. Catmull, “The Reyes Image Rendering Architecture,” in Computer Graphics, Vol. 21, No. 4 (July 1987), pp. 95-102, and A. A. Apodaca, L. Gritz, “Advanced RenderMan,” (Morgan Kaufmann, 2000), pp. 136-43.  
           [0007]    Once the object has been tessellated, the renderer passes the shading regions to a shader. The shader assigns colors to the regions of the image corresponding to the shading regions. Conventionally, such shading regions are passed to the shader via an interface, wherein each shading region is specified by a coordinate location and a size. Conventional systems do not generally provide the ability to pass, to a shader, an accurate description of an arbitrarily shaped nonrectangular shading region. These limitations cause prior art shaders to produce inaccurate and substandard results for certain types of complex objects.  
           [0008]    Some prior art systems perform shading based on a single point for each shading region, such as the center of the shading region. Other systems determine shading over a rectangular or ellipsoidal surface constructed around, or approximated by, the shading region. Examples of such prior art techniques are described below.  
           [0009]    Referring now to FIG. 2A, there is shown a shading and rendering technique according to the prior art, as applied to image  430 . Object  201  is tessellated into rectangular shading regions  203  forming a grid, and is shown overlaid on pixel grid  224  in pixel space. Superimposing the shading region grid on pixel grid  224  yields a correspondence between pixel  225  locations and shading regions  203 ; specifically, each pixel  225  location that lies within the bounds of object  201  corresponds to at least one shading region  203 . The shader determines a color for each shading region  203  by retrieving, averaging, or accumulating the appropriate color or colors for the point or region represented by the shading region  203 . The renderer then applies shading region  203  colors to pixels  225  overlaying or proximate to shading region  205 .  
           [0010]    In some systems, only the center point  226  of each pixel  225  is considered. As depicted in FIG. 2A, the renderer determines colors as follows: for each pixel  225  to be shaded, the system determines which shading region  203  overlaps the center point  226  of that pixel  225 . The pixel  225  is assigned a color based on the color of whichever shading region overlays the center point  226 . The example of FIG. 2A shows center points  226  for three pixels  225 R. Three shading regions  203 R overlay the center points  226  of these three pixels  225 R, respectively. Thus, according to one prior art method, color values for these shading regions  203 R would be applied to pixels  225 R of the final image. However, the use of a single point for each pixel location in this manner can lead to undesirable artifacts such as color discontinuities, aliasing, and Moiré patterns.  
           [0011]    In other prior art systems, pixels  225  are considered to have dimensions, so that the area covered by a pixel  225  can include portions associated with more than one shading region  203 . Thus, a pixel  225  is assigned a color or colors based on the color or colors of one or more shading regions  203  that overlay (or are adjacent to) the pixel  225  given its actual or assumed dimensions.  
           [0012]    Examples of such prior art systems are depicted in FIG. 2B. In one prior art system, after object  201  has been tessellated into rectangular shading regions  203 , a representation of each shading region  203  is sent to a shader. A color value for each shading region  203  is determined. The renderer then colors individual pixels  225  by determining one or more shading regions  203  that overlay or are adjacent to each pixel  225 , and accumulating or averaging the colors associated with those shading regions  203 .  
           [0013]    In one such method, the shading region  203  representation that is sent to the shader consists of coordinates for the center point  227  of the shading region  203 . A color value for each pixel  225  is determined by accumulating or averaging the color values for shading regions  203  whose center points  227  overlay that pixel  225 . In the example shown in FIG. 2B, pixel  225 S would be assigned the color value associated with shading region  203 T, while pixel  225 V would be assigned an average of the color values of shading regions  203 U and  203 V. The average may be weighted according to the positions of the center points of the shading regions  203  being used with respect to the pixel  225  area.  
           [0014]    Conventionally, shading regions are often described in terms of micropolygons. One conventional process for micropolygon-based shading and rendering, therefore, includes the steps of: tessellating the object geometry into rectangular micropolygons; running shaders to determine colors of the micropolygons; and accumulating or averaging the micropolygon colors to obtain colors for the covered or nearby pixels. In general, in determining a color value for a pixel, conventional renderers calculate a weighted average of color values corresponding to the one or more micropolygons that overlap the area covered by the pixel. This is usually done by integrating over the area of the pixel, or by obtaining color values for determined sample points within a pixel. Some renderers also take into account color values of adjacent micropolygons, so as to provide smoother results from one point to the next.  
           [0015]    See, for example, RenderMan® and the RenderMan® Shading Language, both available from Pixar Animation Studios of Emeryville, Calif., and described in S. Upstill,  The RenderMan Companion,  (Addison Wesley 1989), pp. 292-95. The RenderMan® products expose to shaders only a single position and the change in the parametric dimensions (u, v) across the surface element, in order to define rectangles. Also see Mental Ray®, available from Mental Images GmbH &amp; Co. KG of Berlin, Germany, and described in Driemeyer,  Rendering with Mental Ray,  (Springer 2001), pp. 463-64.  
           [0016]    The above-described prior art techniques have several limitations. One limitation is that rectangular shading regions do not always provide sufficient precision in defining a region of the image to be shaded. In situations where the shape of the object does not easily map to rectangular shading regions, antialiasing problems can persist.  
           [0017]    Furthermore, prior art techniques for avoiding jagged edges, aliasing, and Moire patterns generally involve drawing bounding boxes or ellipsoids around shading regions, so that the shader can operate over a shading region rather than over a single point. Such techniques offer crude approximations of the actual area covered by the shading region, and often provide inaccurate results. Prior art systems are relatively inflexible in that they typically provide limited options for representing shading regions. Rather than passing a precise definition of each shading region, prior art systems generally provide, at most, the position and overall dimensions of a shading region. This allows construction of a bounding box or ellipsoid, but does not allow for precise shading within a region coextensive with the shading region itself. Conventional schemes are thus limited to a relatively inflexible, and often insufficiently general, definitional scheme that does not allow for accurate shading and rendering of arbitrarily shaped regions. For certain types of objects, conventional shading schemes are therefore unsuitable and may yield substandard results.  
         SUMMARY OF THE INVENTION  
         [0018]    The invention allows shading regions to be defined in terms of shading regions having any number of vertices; thus, shading regions need not be limited to rectangular areas. This allows the shader to perform shading operations on regions that more closely map to the features of the objects being rendered. The present invention thus provides improved flexibility, generality, and precision in defining shading regions and generates images of higher quality than does the prior art.  
           [0019]    In one embodiment, each shading region can be a single point, a line segment, a triangle, a general quadrilateral, or any polygonal shape having any number of vertices. A geometric descriptor of each shading region includes a representation of the region in terms of one, two, three, four, or more points. For example, a renderer can pass to the shader a set of coordinates representing vertex locations that define a shading region. The data passed to the shader contains, for example, positional coordinates in three-dimensional space, parametric (u,v) coordinates (in texture space), and/or arbitrary additional information for defining the shading region. Some embodiments enable shading region definitions of any dimension and having any number of points, parameters, or vertices; other embodiments limit the number of vertices for shading regions to four or to some other fixed maximum.  
           [0020]    Given the geometric descriptor for a shading region, the shader determines, to whatever degree of approximation is appropriate, the average color and/or other shading characteristics of the object across the shading region. The renderer then assigns a color to each pixel of the final image by accumulating color values for shading regions that overlay or that are close to that pixel. If more than one shading region overlays or is close to a pixel, the color value for the pixel is determined by averaging, integrating, or point-sampling the color values for the overlaying or nearby shading regions. Since such operations are performed using the exact dimensions and shape of the shading regions (which are not limited to rectangles), the resulting color value for a pixel can be more accurately determined than with prior art methods.  
           [0021]    The present invention allows greater precision in defining shading regions, and thereby facilitates improved shading results. Furthermore, the invention provides a greater degree of generality in defining shading regions and passing such definitions to shaders. This increased level of generality allows for improved representations of certain types of objects such as particles, curves (such as strands of hair or fur), and complex connected-surface geometry, that are difficult to describe accurately using rectangular shading regions.  
           [0022]    The present invention additionally provides an improved shader interface that allows shading regions having arbitrary numbers of vertices to be passed to a shader. This allows the shader to perform more accurate shading operations that extend over the exact shading regions. The interface allows for the passing of shading regions as sets of one or more vertices, so that a renderer can pass shading regions of various shapes, including points, lines, and N-sided polygons, to the shader. In one embodiment, the user is able to select the par-particular shape for each shading region. Furthermore, shading region shapes can also be determined by the rendering architecture (e.g. micropolygon-based, ray tracer, particle renderer, and the like). The shaders themselves need not be aware of which rendering architecture is used.  
           [0023]    The present invention is also applicable to computer graphics generation systems that employ ray tracing approaches. In ray tracing, a polygonal geometry is constructed. Pixel colors are computed from point samples that are intersected with the geometry and then shaded based on points and/or overall area sizes. Using the present invention, a ray tracer can pass, to shaders, shading region definitions representing either the exact intersection points, or an estimated quadrilateral area to be sampled (for example, approximately representing the present pixel), or the geometric polygon that was determined to intersect the ray (for example, a triangle). In either case, using the invention, existing shaders can be applied unmodified, and existing shaders can be used in the same manner as in a micropolygon-based renderer. This allows for more generality and accuracy in shading operations and computations.  
           [0024]    The features and advantages described in this summary and the following detailed description are not all-inclusive. Many additional features and advantages will be apparent to one of ordinary skill in the art in view of the drawings, specification, and claims hereof.  
           [0025]    Moreover, it should be noted that the language used in this disclosure has been principally selected for readability and instructional purposes, and may not have been selected to delineate or circumscribe the inventive subject matter, resort to the claims being necessary to determine such inventive subject matter. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0026]    [0026]FIG. 1 is a block diagram depicting functional modules for performing shading operations according to one embodiment of the present invention.  
         [0027]    [0027]FIG. 2A depicts a shading technique using pixel center points, according to the prior art.  
         [0028]    [0028]FIG. 2B depicts shading techniques using shading region center points, according to the prior art.  
         [0029]    [0029]FIG. 3 depicts a shading technique using shading regions having arbitrary numbers of vertices, according to one embodiment of the present invention.  
         [0030]    [0030]FIGS. 4A and 4B depict an example of applying the present invention to shade a transition region between two object areas.  
         [0031]    [0031]FIG. 5 depicts an example of texture map application using techniques of the present invention.  
         [0032]    [0032]FIGS. 6A and 6B depict mapping and shading for shading regions having various shapes.  
         [0033]    [0033]FIG. 7 is a flowchart depicting a method for practicing the present invention, according to one embodiment.  
         [0034]    [0034]FIG. 8 depicts a technique for applying a texture map by selecting individual points within a shading region, according to one embodiment of the present invention.  
         [0035]    The figures depict a preferred embodiment of the present invention for purposes of illustration only. One skilled in the art will readily recognize from the following discussion that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles of the invention described herein. 
     
    
     DETAILED DESCRIPTION  
       [0036]    System Architecture  
         [0037]    Referring now to FIG. 1, there is shown a block diagram of a set of functional modules for practicing the present invention. The functional modules depicted in FIG. 1 form a system  100  that can be implemented, for example, in a conventional personal computer or workstation using an Intel Pentium processor and running the Linux operating system. One skilled in the art will recognize that the particular arrangement of modules as well as their names and interconnections as depicted in FIG. 1 are merely exemplary, and that many variations are possible without departing from the essential characteristics of the invention.  
         [0038]    Graphics engine  101  performs most of the processing involved in generating computer graphics imagery. Such processing includes, for example: performing transformations to properly size, place, deform, and transform objects; hidden surface removal; animation; and the like. Shader  102 , which may be implemented as a plug-in or as an integrated or separate software component, assigns color values to objects and regions including those defined by engine  101 . Tessellator  103  divides objects (or portions thereof) into shading regions, according to techniques described in more detail below. Texture map  104  contains an image, such as a bitmap, that is to be mapped onto an object. One skilled in the art will recognize that texture map  104  may be omitted from such a system, and that the shading operations described herein can be based on color information from sources other than texture maps  104 , including for example object surface information, lighting, and other shading information  106 . For example, for area light sources, shader  102  may apply color values based on the nature of the surface emitting the light; for materials and surfaces, shader  102  may apply color values based on surface characteristics of the geometric primitives being shaded.  
         [0039]    Object definitions  105  include representations and descriptors that specify positions, sizes, surface characteristics, and the like for objects. Other shading information  106  includes additional parameters and data that affects shading operations, including for example shadow information, light sources, and the like. Renderer  107  is a software component that applies the determined color values and generates a final image that is ready to be output  108 . The final image can be stored, displayed, converted to other formats, or subject to further processing as needed.  
         [0040]    Shading Using Generalized Shading Regions  
         [0041]    Shader  102  determines and assigns color values for shading regions; based on these color values, renderer  107  determines colors for pixels and pixel regions in the final image. To do so, shader  102  combines information from: object definitions  105  specifying the position, size, and shape of each object; texture map  104  (or other surface characteristics) for objects; and other shading information  106  such as lighting characteristics.  
         [0042]    Referring now to FIG. 3, there is shown an example of a shading technique according to one embodiment of the present invention. Object  201  is tessellated into shading regions  203 , which in one embodiment can be of any shape. In one embodiment, only a portion of object  201  is tessellated; for example, the system may tessellate only that portion of object  201  that will be visible in the image. Reference herein to the tessellated object is to be understood to include reference to either the entire object, or to the tessellated portion of an object, as appropriate. In the example of FIG. 3, some shading regions are rectangular and some are triangular. In general, shading regions can be polygonal in shape, or can be any other shape that is definable in terms of one or more vertex points. One skilled in the art will recognize that other variations are possible, wherein the invention can handle other types of shapes as well.  
         [0043]    The tessellated object  201  is shown overlaid on pixel grid  224  in pixel space. Superimposing the tessellated object  201  on pixel grid  224  yields a correspondence between pixel  225  locations and shading regions  203 ; specifically, each pixel  225  location that lies within the bounds of object  201  overlays, at least in part, at least one shading region  203 . Shader  102  determines one or more colors for each shading region  203  by computing the appropriate color or colors for the point or region represented by the shading region  203 . The renderer  107  then applies the shading region  203  colors to pixels  225  covered by or near shading region  203 .  
         [0044]    The present invention additionally provides an improved interface to shader  102  that allows shading regions having arbitrary numbers of vertices to be passed to shader  102 . Shader  102  can thereby perform more accurate shading operations that extend over the exact shading regions. The interface allows for the passing of shading regions as sets of one or more vertices, so that renderer  107  can pass shading regions of various shapes, including points, lines, and N-sided polygons, to shader  102 . The shader interface is described in more detail below.  
         [0045]    In the example of FIG. 3, shading region  203 N is a quadrilateral defined by four vertices  120 , and shading regions  203 P and  203 Q are triangles defined by three vertices  120 . In other examples, some shading regions  203  might be defined as line segments or point locations, and others may be polygons. For each of these shading regions  203 , renderer  107  passes to shader  102  a precise description. The shading region definition is passed using a generalized parametric scheme as described herein. The description includes, for example, coordinate locations for all of the vertices of the shading region  203 . In one embodiment, renderer  107  passes a single shading region definition at a time to shader  102 ; in another embodiment, renderer  107  passes a plurality of shading region definitions concurrently to shader  102 , each shading region being defined by a set of one or more vertices. In one embodiment, renderer  107  passes this information to shader  102  using an interface that allows for any number of vertices, as described in more detail below. In another embodiment, the interface allows for a maximum of four vertices for each shading region; one skilled in the art will recognize that any fixed maximum can be established. In some embodiments, such maximum limits allow for performance optimizations and may facilitate improved memory allocation operations, since the compiler can allocate a predetermined fixed amount of memory to handle the shading region data being passed to shader  102 .  
         [0046]    A color value for each shading region  203  is determined. Individual pixels  225  are then colored by determining one or more shading regions  203  that overlay or are adjacent to each pixel  225 , and determining a color value for each pixel  225  based on the colors associated with those shading regions  203 . If more than one shading region  203  overlays a pixel  225 , the color value for the pixel  225  is determined by averaging, integrating, or point-sampling the color values for the overlaying shading regions  203 .  
         [0047]    Once shader  102  has determined color values, renderer  107  generates the final image, which is output  108  for display or storage.  
         [0048]    By allowing for shading regions  203  having arbitrary numbers of vertices, the present invention provides improved accuracy and generality for shading operations.  
         [0049]    Transition Regions  
         [0050]    Another advantage to the technique of the present invention is that it provides a mechanism for shading transition regions or other unusual areas of images.  
         [0051]    Referring now to FIGS. 4A and 4B, there is shown an example of such a situation. In FIG. 4A, image  430 , including two objects  201 A and  201 B, is shown. Each object  201 A,  201 B has been tessellated. Region  420  of image  430  is a transition region that lies between objects  201 A and  201 B. The size of transition region  420  is exaggerated for illustrative purposes. Conventional shading operations would leave a discontinuity in transition region  420 , resulting in an abrupt and often noticeable change in the colors in the regions. Alternatively, some type of blending operation might be performed between objects  201 A and  201 B to ameliorate the discontinuity. Either approach potentially produces undesirable artifacts and inaccuracies in the final image.  
         [0052]    The present invention avoids such problems by providing a mechanism for tessellating transition region  420  using shading regions  203  having arbitrary numbers of vertices. Referring to FIG. 4B, region  420  is tessellated into shading regions  203 A having triangular shapes. The particular shapes for shading regions  203 A can be selected according to the particular characteristics of transition region  203  and of the overall image. In one embodiment, transition region  420  is formed by stretching and gluing existing regions  201 A and  201 B. In the example shown, vertices of shading regions  203 A of transition region  420  are selected to coincide with vertices of shading regions  203  of regions  201 A and  201 B; this technique is employed, in one embodiment, so that transition region  420  is tessellated using as many preexisting vertices as possible.  
         [0053]    By providing the ability to pass shading regions  203  having arbitrary numbers of vertices to shader  102 , the present invention facilitates improved color accuracy for shading transition regions or other unusual areas.  
         [0054]    Texture Map Application  
         [0055]    In one embodiment, the present invention can be used to apply a texture map to a surface of an object. Here, shading regions are passed to shader  102  in terms of their (u,v) coordinates in texture space, rather than in terms of (x,y) pixel space coordinates. Referring now to FIG. 5, there is shown an example of this process.  
         [0056]    Texture map  104  is represented as an image, such as a bit-mapped image, defined in a texture space using coordinate system (u,v). Texture map  104  is divided into a grid of texels  501 , which are analogous to pixels in an ordinary image. A user (or other entity) defines a region of object  201  to which the texture is to be applied. Based on this definition, each relevant point of the object  201  has a corresponding (u,v) coordinate representing a location within texture map  104 .  
         [0057]    As described above, according to the techniques of the present invention, object  201  is tessellated into any number of arbitrary shading regions  203 . The shape of these shading regions  203  can be selected to match particular features of object  201 , so as to provide improved accuracy and quality of the final image. Each shading region  203  is passed to shader  102 .  
         [0058]    The center portion of FIG. 5 shows texture map  104  applied to object  201  in pixel (x,y) space. Each shading region  203  in the relevant portion of object  201  overlaps a portion of texture map  104  that corresponds to one or more texels  501 . For example, shading region  203 H, depicted as an arbitrary quadrilateral in the middle portion of FIG. 5, overlaps an area corresponding to several texels  501  of texture map  104 . Since object  201  has an arbitrary surface size, shape, and orientation in three-dimensional space, which maps to a two-dimensional area in the final image, texture map  104  is appropriately deformed when it is applied to object  201 .  
         [0059]    In the right-hand portion of FIG. 5, the same shading region  203 H is shown in texture (u,v) space. For clarity, other shading regions  203  of object  201  are omitted from the right-hand portion of FIG. 5. The mapping of shading region  203 H onto texture (u,v) space is performed by an inverse of the transformation that maps texture map  104  onto object  201 . Such transformations and inverses thereof, are well known in the art. The resultant shading region  203 H in (u,v) space is an arbitrary quadrilateral. In general, the shading region  203 H in (u,v) space may be a point, line, triangle, quadrilateral, or other shape, and it may overlap any number of texels  501 . Vertices  120  of the quadrilateral are passed to shader  102  using a generalized parametric scheme for passing shading regions having any number of vertices  120 .  
         [0060]    Prior art shading methods would pass an approximation of shading region  203 H to a shader. For example, a rectangular bounding box might be constructed around each shading region, so that the shader would receive coordinates and dimensions of the bounding box rather than receive a precise definition of the shading region  203 H itself. In another prior art method, an ellipsoid might be constructed around shading region  203 H, and the shader would receive coordinates and dimensions of the ellipsoid. Either way, because the shader would receive an approximation of the shading region, the resulting color determinations would be inaccurate.  
         [0061]    The present invention overcomes this problem by allowing the shader  102  to receive the vertex  120  locations for the actual shading region  203 H, so that shader  102  can precisely apply color values to the area defined by shading region  203 H. For each shading region  203  it receives for shading, shader  102  applies color data from the region of texture map  104  corresponding to the actual area defined by shading region  203 . Shader  102  performs this operation by mapping shading region  203  to a region on texture map  104 , determining which texels  501  lie within the texture map  104  region, and applying color values from those texels  501 . For example, if shading region  203 H maps to blue texels  501  in texture map  104 , shader  102  applies blue to the region of object  201  covered by shading region  203 H. If more than one texel  501  lies within the region, shader  102  determines a color for the region by combining color data from the texels  501  within the region. This combining operation may include, for example, averaging, integrating, or point-sampling across the region.  
         [0062]    Thus, rather than determining a texture map color at a single point, or over a rectangular or ellipsoid region that is an approximation of the shading region, the present invention applies texture map data to objects  201  using accurate representations of shading regions having arbitrary numbers of vertices, thus yielding more accurate results.  
         [0063]    As described above, once shader  102  has determined color values, renderer  107  generates the final image, which is output  108 .  
         [0064]    Referring now to FIGS. 6A and 6B, there are shown variations of the above-described technique for different types of shading regions. FIG. 6A depicts shading regions of various forms and shapes, including region  203 B (quadrilateral), region  203 C (triangle), region  203 D (line segment), and region  203 E (point) in pixel (x,y) space. Presumably, these shading regions  203 B,  203 C,  203 D,  203 E are part of an object  201 , although the object  201  has been omitted from FIGS. 6A and 6B for clarity. FIG. 6B depicts each shading region  203 B,  203 C,  203 D,  203 E in texture (u,v) space, overlaid on texture map  104 . Shader  102  determines color values for shading regions  203 B,  203 C,  203 D,  203 E based on the color values of the texels overlaid by each shading region  203 B,  203 C,  203 D,  203 E. As depicted in FIG. 6B, therefore, shader  102  determines:  
         [0065]    a color value for shading region  203 B using color values from texels  501 A through  501 H;  
         [0066]    a color value for shading region  203 D using color values from texels  501 J through  501 P;  
         [0067]    a color value for shading region  203 C using color values from texels  501 Q through  501 V; and  
         [0068]    a color value for shading region  203 E using a color value from texel  501 W.  
         [0069]    In an alternative embodiment, more sophisticated methods are used for determining color values for shading regions. For example, the shader  102  may take into account texels  501  that are close to, but not overlaid by, each shading region  203 ; specifically, a shading region  203  can be shaded using color values from texels  501  that lie within a predefined distance (measured in pixels or texels) from the boundaries of the shading region  203 . Alternatively, the shading region can be convoluted by a smooth filter kernel so that more texels  501  are taken into account in determining the final color. As described above, where a shading region  203  overlays more than one texel  501 , shader  102  averages the color values from all of the overlaid texels  501 . Weighted averaging, or integrating, or point-sampling is used to determine a final color value. Unlike prior art methods, the method of the present invention performs such averaging, integrating, or point-sampling over the exact area defined by the shading region  203 .  
         [0070]    Shadows  
         [0071]    Certain components of graphics systems compute the effect of shadows to be applied to surfaces, including determining which points or regions on an object are fully illuminated, occluded, or partially shadowed. See, for example, Woo et al., “A Survey of Shadow Algorithms,” in  IEEE Computer Graphics and Applications,  vol. 10, no. 6, pp. 13-32 (1990). These data are then combined with other characteristics of the objects, such as color, texture, and the like, to determine a final color value for each pixel of the image. The present invention can be used in conjunction with well-known shadow algorithms to more accurately determine and apply shadows factors to objects. Shader  102  determines shadows across a precise shading region having an arbitrary number of vertices (such as a point, line, triangle, quadrilateral, or arbitrary polygon). This is accomplished according to techniques analogous to the techniques described above. Since the shading regions are not limited to rectangles or other micropolygons, but rather can be defined based on particular characteristics of the object and lighting in the scene, the present invention allows for improved precision in applying shadows to images.  
         [0072]    In one embodiment, for example, shader  102  averages the shadow computation over each defined shading region. Alternatively, shader  102  selects points within each defined shading region, determines how to apply a shadow at each point, and averages the results.  
         [0073]    Shader Interface  
         [0074]    As discussed above, renderer  107  passes to shader  102  a precise description of the shading region defined by each shading region  203 , using a generalized parametric scheme. In one embodiment of the present invention, the following shader interface is used.  
         [0075]    Each shading region  203  has a number of vertices  120 . According to the shader interface, renderer  107  passes to shader  102  data describing coordinates of each vertex  120  (for example in pixel space, three-dimensional space, or texture (u,v) space). Depending on the number of vertices passed, a different type of shading region is described, as follows:  
                                                   Number of               Vertices   Type of Surface                           0   No Surface Area Available           1   Shade a Single Point           2   Area is a Line Segment           3   Triangle           4   Quadrilateral           . . .   . . .                      
 
         [0076]    In one embodiment, shader  102  makes appropriate calls to a shader library containing methods for shading regions of different shapes. The methods of the shader library handle various types of shading regions by defining tuples of values instead of single values. Unlike prior art systems that are limited to providing position and dimension (such as a (u,v) coordinate and a (Du,Dv) dimension), the present invention facilitates passing multiple tuples of values, thus allowing a number of vertices to be defined and passed for each shading region.  
         [0077]    More specifically, instead of using variables describing the position, texture coordinates, and perhaps other data for a single point, the shader library handles tuples or arrays of variables. These variables describe the positions, texture coordinates, and the like at multiple points.  
         [0078]    The following is an example of code for identifying the type of shading region, according to one embodiment. One skilled in the art will recognize that the maximum tuple size can be set to 4 or to any variable, to specify the maximum number of vertices per shading region; alternatively a more generalized scheme can be provided whereby each shading region can have any number of vertices.  
                                                                                                                                   /*                * a tuple is a polygonal region, which is empty, a point, a line, a            triangle, a quadrilateral, or another polygon.                */            /* is data type a tuple type? */       #define SHADER_DATA_TYPE_is_tuple(type) ((type) &gt;= SHADER_DATA_TUPLE)       /* get tuple type from element type */       #define SHADER_DATA_TYPE_tuple(type) ((type) + SHADER_DATA_TUPLE)       /* get element type from tuple type */       #define SHADER_DATA_TYPE_from_tuple(type) \                (SHADER_DATA_TYPE_is_tuple(type) ? (type) - SHADER_DATA_TUPLE :            (type))       /* data types for example for map evaluations */       /* layout so that tuple types are the base type + 16 */       typedef enum {                SHADER_DATA_NONE = 0,               SHADER_DATA_FLOAT,   /* float */           SHADER_DATA_FLOAT2,   /* V2F, e.g. bump offsets */           SHADER_DATA_FLOAT3,   /* V3F, color or vector */           SHADER_DATA_INTEGER,   /* int */           SHADER_DATA_POINTER,   /* void pointer */           SHADER_DATA_STRING,   /* char pointer */           SHADER_DATA_TUPLE = 0×10,                SHADER_DATA_FLOAT_TUPLE,   /* float[] tuple */           SHADER_DATA_FLOAT2_TUPLE,   /* V2F [], e.g. bump offsets array */           SHADER_DATA_FLOAT3_TUPLE,   /* V3F [], color or vector tuple */                SHADER_DATA_INTEGER_TUPLE,   /* int [] */           SHADER_DATA_POINTER_TUPLE,   /* void *[] */           SHADER_DATA_STRING_TUPLE   /* char *[] */            } SHADER_DATA_TYPE;                  
 
         [0079]    The following function type declaration shows a scheme for passing data through the interface, according to one embodiment. “Name” describes the particular data associated with the points (such as vertex positions, texture coordinates, or arbitrary other named data). “Type” identifies the type of data as defined above. “Data” is a pointer to the data, which are represented as mentioned above in the definition of the various types:  
                                                             /* callback to get data from a shader */           typedef int (*SHADER_DATA_CALLBACK) (SHADER *shader,                void *callback_data,           char *name,           SHADER_DATA_TYPE type,           void *data) ;                      
 
         [0080]    Point Sampling  
         [0081]    In one embodiment, shader  102  determines a color for a shading region by selecting a number of points within the shading region, and determining a color value for each point. Points can be selected according to any of several well known point selection methods, such as regular sampling, stochastic sampling, low discrepancy sequence sampling, or the like. The invention is not limited to any particular point selection technique.  
         [0082]    Color values determined at the various points within the shading region are then averaged or accumulated to develop a final value. In this manner, shader  102  is able to determine an appropriate color for the entire shading region.  
         [0083]    Referring now to FIG. 8, there is shown an example of point-sampling. Shading region  203  is shown in texture (u,v) space, overlaid on a portion of texture map  104 . Individual points  801  within shading region  203  are selected. For each point  801 , shader  102  determines a color value for the underlying texel  501 . Color values for points  801  throughout shading region  203  are accumulated and averaged, to determine a final color value for shading region  203 . Texels  501  containing more points  801  will be given greater weight in the averaging operation. Since the number of points  801  in a texel  501  provides an approximation of the relative area of shading region  203  found within that texel  501 , the point-sampling technique effectively approximates an average color value that would be determined by continuous integration across the surface defined by shading region  203 .  
         [0084]    In one embodiment, rather than sampling a texture map, shader  102  implements a procedural checkerboard map shader, wherein shader  102  counts the number of samples lying on areas of various colors (such as black, white, or other colors), and computes an average color.  
         [0085]    Method of Operation  
         [0086]    Referring now to FIG. 7, there is shown a flowchart depicting a method for practicing the present invention according to one embodiment. Object  201  is tessellated  701  into a number of shading regions  203  having arbitrary numbers of vertices. The tessellated object  201  is mapped  702  onto pixel (x,y) space, or texture map (u,v) space, or some other coordinate system. The transformation from object space into another coordinate system yields locations in the new coordinate system for each vertex  120  of each shading region  203 . These shading region vertex  120  locations are passed  703  to shader  102 . Shader  102  then determines  704  color values for each shading region  203 . This can be done by any of the above-described approaches (e.g., calculating an average across the region defined by the shading region  203 ; integrating across the shading region  203 ; point-sampling across the shading region  203 ) or their equivalents. The source of the color values used in the shading operation can be a texture map  104 , lighting information, surface characteristics of object  201 , or the like. Shader returns  707  the determined color values. Renderer  107  then applies  705  the colors to the appropriate areas of the image. The final result is then output  706  to storage or display.  
         [0087]    The foregoing description of the embodiments of the invention has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise forms disclosed. Persons skilled in the relevant art can appreciate that many modifications and variations are possible in light of the above teaching. Persons skilled in the art will recognize various equivalent combinations and substitutions for various components shown in the figures. It is therefore intended that the scope of the invention be limited not by this detailed description, but rather by the claims appended hereto.