Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
1999-07-21
2002-08-20
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S619000, C345S581000
Reexamination Certificate
active
06437795
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to methods and apparatus for clipping functions representing models of objects which are computer generated.
2. Background Art
Computer generated images are created from models of objects. It is desirable that the object depicted in a computer generated image resemble the real object to the maximum extent possible. As one aspect of modeling an object, it is desirable to accurately represent the shading of the object. Changes in color and intensity of light reflected by an object across its surface, or its shading, can be very complex. Variations in shading may result from a wide variety of factors such as surface texture, position, orientation, and the type, location and direction of the source of light. To accurately represent shading of a modeled object, high order shading functions may be used.
Another aspect of the modeling process is selecting that portion of the object which is being modeled that will lie within a field of vision. Commonly, an object to be modeled is represented as a number of smaller polygons. Once the object is modeled with the polygons, the polygons are “clipped” to eliminate that portion of the data which represents the modeled object which lies outside of a selected field of view.
The object may be modeled with one or more first degree functions. The polygon(s) used to model the object are planar in their three-dimensional geometric coordinates. The shading function may also be a first degree function representing a set of color or shading coordinates. Each geometric point on the polygon may be represented by coordinates (x,y,z) and the shading at each particular point represented by a color set (red (r), green (g), blue (b)), these coordinates and color sets varying linearly over the polygon.
When the geometric and shading functions are first degree, and are thus linear, as described above, the clipping process requires only linear interpolation of the data. For example, the geometric coordinates for each point where a clipping line or plane intersects the polygon may be determined from linear interpolation from other known points. Likewise, the shading values at the clipped points can be determined by interpolation the shading values linearly from those of known points.
This process of linear clipping is described in U.S. Pat. No. 3,816,726 to Sutherland et al., and in
Reentrant Polygon
Clipping by Sutherland and Hodges (Vol. 17, Number 1, Communications of the ACM, January 1974). These references describe a process whereby a linear interpolant ″ is used to calculate the intersection point of a clipping line or plane with an edge of a polygon between two vertices of the polygon. The interpolant ″ is derived from ratios of two similar triangles and the distances between points on the triangles to the clipping line. As provided in these references and referring to
FIG. 1
, the linear interpolant ″=SI/SP=SR
1
/|SR
1
+PR
2
| As described therein, the interpolant ″ can be applied to other linear functions associated with the polygon, such as color and intensity blending.
A problem is that many functions which are used to model objects are not first order. In order to improve the accuracy of the representation of the object's shading, it is now common to utilize a second or higher degree polynomial shading function. For example, a shading function for an object being modeled may be defined by a quadratic parametric surface. It is not possible to use the simple linear clipping algorithm directly to such a function in order to obtain the coordinates or parameters associated with clipping points (i.e. it is not possible to apply a linear interpolant such as that described above to the second or higher degree shading function). Instead, quadratic or other second degree or higher interpolation is necessary. Such a process is computationally demanding, however, and negates some of the gains realized by using a high order surface to obtain better shading results.
SUMMARY OF THE INVENTION
The invention is a method and apparatus for clipping a function, and in one or more embodiments, defining a new reparameterized clipped function.
An embodiment of the invention comprises a method of effectuating clipping of a second or higher order function in “linear” fashion by using barycentric coordinates.
In accordance an embodiment of the invention, the method comprises the steps of determining a second or higher order function to be clipped, determining barycentric coordinates for at least one clipping point associated with a first order function associated with the second or higher order function and generating at least one clipping point associated with the second or higher order function using the barycentric coordinates.
In one or more embodiments, the barycentric coordinates for at least one clipping point associated with the first order function are determined by linear interpolation. The barycentric coordinates are then substituted into the higher order function to define the clipped point(s) of the higher order function.
In one or more embodiments, the higher order function comprises a quadratic Bezier function defining a quadratic Bezier triangle. The first order function comprises a linear vector-valued function representing a planar triangle associated with the quadratic Bezier triangle.
In one or more embodiments of the invention, the method includes the steps of using the barycentric coordinates to determine a reparameterized clipped function.
In an embodiment where the higher order function comprises a quadratic Bezier function, this step comprises using a blossoming algorithm to generate six reparameterized points which define a new clipped quadratic Bezier function.
In accordance with one or more embodiments, the higher order function is a shading function for an object being modeled.
In one or more embodiments, computer hardware and/or software is arranged to one or more aspects of the method of the invention.
Further objects, features and advantages of the invention will become apparent from the detailed description of the drawings which follows, when considered with the attached figures.
REFERENCES:
patent: 3816726 (1974-06-01), Sutherland et al.
patent: 4646251 (1987-02-01), Hayes et al.
patent: 4918626 (1990-04-01), Watkins et al.
patent: 5361386 (1994-11-01), Brown et al.
patent: 5381519 (1995-01-01), Brown et al.
patent: 5675380 (1997-10-01), Florent et al.
patent: 5809219 (1998-09-01), Pearce et al.
patent: 0 319 165 (1989-06-01), None
patent: 0 637 814 (1995-02-01), None
Sutherland, I. and Hodgman, G., “Reentrant Polygon Clipping,” Communications of the ACM, Jan. 1974, vol. 17, No. 1.
Brown, R., “Modeling Specular Highlights Using Bézier Triangles,” The SML Technical Report Series, Sep. 1999, Sun Microsystems Laboratories, Sun Microsystems, Inc., Palo Alto, California.
Phong, B.T., “Illumination for Computer Generated Pictures,” Communications of the ACM, Jun. 1975, pp. 311-317, vol. 18, No. 6.
Blinn, J., “Models of Light Reflection for Computer Synthesized Pictures,” Proc. Siggraph 77, pp. 192-198, vol. 11, No. 2, ACM Press, New York.
Duff, T., “Smoothly Shaded Renderings of Polyhedral Objects on Raster Displays,” Proc. Siggraph 79, pp. 270-275, vol. 13, No. 2, ACM Press, New York.
Bishop, G. and Weimer, D., “Fast Phong Shading,” Proc. Siggraph 86, pp. 103-106, vol. 20, No. 4, ACM Press, New York.
Shantz, M. and Lien, S., “Shading Bicubic Patches,” Proc. Siggraph 87, pp. 189-196, vol. 21, No. 4, ACM Press, New York.
Kirk, D. and Voorhies, D., “The Rendering Architecture of the DN10000VS,” Computer Graphics, Aug. 1990, pp. 299-307, vol. 24, No. 4.
Seiler, L., “Quadratic Interpolation for Near-Phong Quality Shading,” Siggraph 98 technical sketch, 1998.
Kuijk, A.A.M. and Blake, E.H., “Faster Phong Shading via Angular Interpolation,” Computer Graphics Forum 8, 1989, pp. 315-324, North-Holland, the Netherlands.
Bergman, L., Fuchs, H., and Grant, E., “Image Rendering by Adaptive Refinement,” Proc. Siggraph 8
Gunnison McKay & Hodgson, L.L.P.
Harrison Chante′
Luu Matthew
McKay Philip J.
Sun Microsystems Inc.
LandOfFree
Method and apparatus for clipping a function does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for clipping a function, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for clipping a function will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2918031