In recent years, substantial progress has been made in the art of computer graphics. However, certain problems have endured, as the hidden line or surface problem. The hidden surface/line problem consists of removing those parts of a computer generated image which are hidden from a given viewpoint because they are occluded by other objects in the scene. At least one technical commentator describes the problem as one of the most enduring in computer graphics. Still, it is an intrinsic part of any non-trivial rendering scheme in the computer generation of pictures.
The hidden surface problem is treated in some detail in U.S. Pat. No. 3,889,107, System of Polygon Sorting by Dissection issued to Ivan E. Sutherland. Somewhat related to the above patent, it is generally recognized that the hidden line/surface problem is essentially a reformulation of the sorting problem--in x, y and z. Most algorithms address the problem by restricting the object type displayed, thus many deal only with planar facets, which can be employed to give a piecewise linear approximation to more complex assemblies. This has the advantage that features of the plane can be used to accelerate the sorting. The most widely known viewing algorithms sort planar polygons, using knowledge of the structure to reduce what would ordinarily be an n-squared problem to an n times log(n) problem.
A system implementing one algorithm, the so-called z-buffer algorithm, is disclosed in the Proceedings of the Conference on Computer Graphics, Pattern Recognition and Data Structure, 1975 IEEE, New York, "Computer Display of Curved Surfaces" by E. E. Catmull. The z-buffer system sorts in linear time. This method maps a surface through the viewing transformations into its screen coordinates. The z coordinate values associated with given x and y values in screen coordinates are then sorted by a simple exchange so that the current z is the one nearest the viewer. The pre-images of the sorted values are used along with the corresponding surface normals to determine the picture element intensity at (x,y) in screen space. Generally, the system of the present invention, the techniques of which might be collectively referred to as exhaustive sampling, involves z-buffer techniques. In that regard, two observations about z-buffers are useful to note specifically:
1. The z-buffer achieves efficient sorting at the expense of z value calculations. The more complex the surface is, the more difficult it is to determine all possible z values for given values of x and y. As before, many versions require the surface to be faceted since it is easier to solve for z on planar surfaces. More general techniques must solve roots of high order equations.
2. Finding the normal to the surface for all points which emerge from the sort can also be costly. The normal is needed for the illumination effects if the surface is to be rendered by a shading technique. The faceted surface approximation has the ostensible advantage here, but in order to do a reasonable job of faceting non-planar surfaces, knowledge of the surface curvature is needed. Both methods, therefore, require finding derivatives of the surface. Depending on the surface this can be expensive.
In general, the system of the present invention is directed to an improved form of z-buffer, specifically with regard to the above observations.
Much of the recent research in image rendering techniques has dealt with very general surfaces. Particular attention has been paid to parametrically defined polynomial surfaces and recently, more general surfaces. Exhaustive sampling techniques in accordance herewith are applicable to these and other very general surface types; and to a variety of display styles, for example, hidden-line, half-tone, cast shadows, texturing, and so on.
The techniques of the present system have some affinity to a rudimentary program for small computing facilities. Specifically, see "An Inexpensive Technique for Displaying Algebraically Defined Surfaces", Graphics Techniques in Geometry and Topology, Notices of Amer. Math. Soc., Evanston, Ill., Apr. 1977, by A. Rockwood and R. P. Burton. Subsequently, a similar routine was developed and that has been documented to render fractal surfaces. See "Dial: A Diagrammatic Animation Language", IEEE Computer Graphics and Applications, Vol. 2, No. 7, Sept. 1982, by S. Feiner, P. Salesin, and T. Banchoff. These techniques, however, apparently have not had a serious exposition per se. Reasons for this benign neglect are probably apparent algorithmic inconsistencies. Exhaustive sampling in accordance herewith is subtle in that it works well in spite of some ostensible problems.
Some analytical considerations will be helpful in understanding the system of the present invention. In that regard, there is only one requirement for a surface to be displayable by the present technique of exhaustive sampling; namely, a function or procedure must exist which produces a dense (exhausted) scan of sample points on the entire surface. EQU Let E.sub.S =(x.sub.i,y.sub.i,z.sub.i), i=1,2, . . . N
be a set of points on the surface S. If for every point of S there is a point of E.sub.S within a distance r, then E.sub.S is said to exhaust the surface S to resolution r.
Let T be the transformation which maps a point from object space to screen space. T may typically be a composition of translation, rotation, scaling and perspective transformations; and let the points (XMAX,YMAX) and (XMIN,YMIN) define the corners of the viewing window. Let NUMX and NUMY be the number of desired pixels in the respective x and y directions.
For any (x,y,z) in E.sub.S, EQU let (X,Y,Z)=T(x,y,z), EQU let I=integer((X-XMIN)/(XMAX-XMIN))*NUMX EQU and let J=integer((Y-YMIN)/(YMAX-YMIN))*NUMY,
where I and J are indices for the z-buffer array ZBUF(1 . . . 3,1 . . . NUMX,1 . . . NUMY). If ZBUF(3,I,J) is empty or if ZBUF(3,I,J)&lt;Z then, EQU let (ZBUF(1,I,J),ZBUF(2,I,J),ZBUF(3,I,J) )=(x,y,z),
otherwise make no change. Continue this for every point in E.sub.S.
The parameter r must be chosen so that there are enough samples to saturate the z-buffer. This will depend very much on the surface rendered.
Once the z-buffer is created the surface normal approximation can be constructed for all but the last column and last row by computing the cross product of the vector difference between the ZBUF points at (I,J) and (I+1,J) and the vector difference between the ZBUF points at (I,J) and (I,J+1).
To conceptualize the system, imagine a dense set of points on the surface. Each point is mapped into screen space and sorted into the appropriate pixel "bin" on the basis of x and y coordinates. Only the point (x,y,z) with the largest z value is kept in the bin, effectively eliminating the hidden surface. That is, only the data for points nearest the viewer are kept. The cloud of points must be dense enough to saturate all bins which correspond to the surface.
Once the "binning" is accomplished then the surface normal at each point is estimated, as indicated, for forming vectors from the point to neighboring points and computing an approximation to the surface normal from their cross product. The neighbors can be picked arbitrarily as long as the derived vectors are not co-linear.