 This figure shows one level of a hierarchical object and its three subspaces. Each subspace has an associated 4x4 transformation matrix that converts to the co-ordinates of that subspace. |
© Academic Press (1982). This is the author's version of the work. It is posted here by permission of Academic Press for your personal use. Not for redistribution. The definitive version was published in Computer Graphics and Image Processing 19, 1982, pp291-298.
The complexity of computer generated scenes is often greater than the display can handle. As a result, it is important to be able to select a subset of the scene which is appropriate for display. Without this subset filtering, small objects are aliased, producing moiré patterns, flickering, and other disturbing display artifacts. This paper presents a scene representation and an associated display algorithm that together provide ease of subset filtering. The scene is hierarchically constructed and the filter selects an appropriate sub-tree of the hierarchy for display. The bottom nodes of the display sub-tree are visually faded with their parent nodes to produce a pleasing fade-out of objects that approach the limit of resolution. Combined with conventional anti-aliasing, this technique produces satisfying images, both still and animated, of scenes with a wide range of detail.
In computer renderings of complex scenes it is important to know what to display in order to reduce time and increase quality. When too much detail falls into a small area of the display, aliasing effects appear, making the image unattractive. This paper presents a scene representation and an associated display algorithm that provide flexible representation, ease of display subset selection, and are well suited to proper anti-aliasing.
The representation used here is a hierarchical one that allows arbitrary detail to be stored by the use of unlimited levels of the hierarchy [6, 11]. The object space is constructed completely out of hierarchically structured subspaces. The terminal nodes do not contain another type of primitive but are themselves displayable. Some of the advantages of this uniformity are an ability to examine the object at arbitrary magnification and the flexibility of combining common subspaces that share micro-descriptions. The subspaces used in this work are rectangular parallelepipeds. This simple unit can be described and traversed with a single transformation matrix, thus lending the display process to hardware implementation.
The display procedure filters out small objects by selecting a sub-tree of the scene hierarchy which terminates at an appropriate depth for correct visual display. Objects at the bottom of the display tree are visually faded with higher level objects to produce a fade-out of detail that is particularly attractive in animated sequences.
Selection of a subset of the object for display is a filtering technique that is used often in flight simulation [4]. The Singer/Link system reduces the contrast of objects when their size approaches the screen resolution [7]. Evans and Sutherland select objects for display only when their size exceeds a varying threshold, but no fading of the objects is done [8]. McDonnell Douglass fades the entire scene along the eye axis to simulate horizon fading [9]. The detail fading scheme presented here is a combination of these techniques that takes advantage of the hierarchical object representation to effectively find the limit of resolution and fade objects.
Conventional visibility calculations suffer a combinatorial explosion when confronted with complex object descriptions [10]. Typical algorithms for hidden surface elimination require that each surface in the scene be sorted into a computationally effective order and then compared with a neighborhood of other surfaces. As the scene becomes complex, the neighborhood size becomes combinatorially unmanageable.
A structured object space makes hidden surface elimination more efficient. By dividing the object into a small number of subspaces at each level (perhaps five), the object is effectively clipped by frequent rejection of paths that are out of the display [16]. In addition, it is a simple matter to determine when a subspace is too small for display and should be faded out because everything below a given level is, by definition, smaller than the bounding volume at that level. Each subspace is an arbitrarily rotated, translated and scaled rectangular parallelepiped. It is described with a four-by-four transformation matrix which transforms the subspace into its parent space and recursively into the screen space (see Figure 1).
This figure shows one level of a hierarchical object and its three subspaces. Each subspace has an associated 4x4 transformation matrix that converts to the co-ordinates of that subspace. |
An important advantage of hierarchical representations is the ability to conserve storage at lower levels when there are common object space features. Any subspaces in the tree that have common detail, regardless of the environment, can share their hierarchical descriptions since all environmental information (location, orientation, and scale) is contained in the higher levels of the hierarchy. Most objects can take advantage of this feature because they have some common properties (usually surface details such as tree bark, windows on buildings, etc.) Thus, the hierarchy of subspaces is actually constructed as a graph instead of a tree. No efficiency is lost and much space is saved: in the database used here, the size is reduced by a factor of 50.
It should be mentioned that this scheme provides much generality of object descriptions. Any object can be represented since, in the limit, the parallelepipeds can form a point representation. Two parallelepipeds can be added when on the same level of the hierarchy. The result is that the union of their volume is represented. Similarly, parallelepiped volumes can be subtracted by placing them vertically in the hierarchy (one below the other). Since each object must be within the bounding volume of all of its parents, the intersection of the vertically linked volumes is represented.
In addition to arbitrary polygonal representations, curves can be stored. In one implementation of this scheme, a bi-parametric curved surface is represented by dynamically generating levels of hierarchy as they are needed until the proper display resolution has been produced [6]. Thus, rectangular parallelepipeds are very simple objects with which to work yet provide uniformity and flexibility of the object description.
Creation of hierarchical databases is currently done manually with an interactive editor. Although it is possible to envision automatic schemes for converting conventional representations into hierarchies, that is beyond the scope of this paper and is discussed elsewhere [6]. The manual scheme is adequate for the database used in this work, even though it is a complex scene.
The structure editor maintains two representations of the scene: a conventional point/line/surface representation and a hierarchical representation. The conventional form is useful when converting to hierarchies as it can be displayed while the hierarchies are being fitted. A separate object editor allows the conventional form to be manipulated. Thus, complete control of object descriptions is available.
The hierarchy editor uses a wire-frame display to show any single level of the hierarchy, consisting of the parent volume and all of its children. By moving into and out of child volumes, the hierarchy is traversed. Volumes can be created, deleted, rotated, translated, scaled, and visually manipulated to aid the hierarchy designer. The editor is able to delete levels of the hierarchy, causing lower levels to be inherited by upper levels. It can also create intermediate levels, inserting them anywhere and arbitrarily re-organizing the hierarchy. For example, it is possible to move a volume horizontally across the hierarchy (up any number of levels and then down to any other place) with a single command.
The hierarchy editor is stable and has been running for over a year. It has been used to create a number of databases, the most complex being a city scene which has over 1000 volumes forming a hierarchy with over 50,000 nodes. In all, it took about three man-weeks of work to create this database.
The other half of the hierarchy system is the program which displays images of the scenes created by the hierarchy editor. Two such programs were written: an early version that uses ray tracing [6] and a more recent depth-buffer algorithm that will be discussed here.
Prior to a description of the display algorithm, it is important to discuss anti-aliasing and its role. The problem of aliasing in images is one of mis-alignment between the objects to be drawn and the medium on which they are drawn. Sampling theory explains more formally that when the frequency of the object is less than half the frequency of the display, aliasing effects appear [1].
Aliasing effects manifest themselves in many ways. Straight lines appear jagged and produce moiré patterns when in aggregates. Very small objects which cover only a few pixels are grossly misrepresented and often disappear completely (scintillation). Animated scenes are particularly affected by aliasing because the nature of the display artifact changes from frame to frame. Thus, jagged lines appear to ripple and crawl, thin lines break up randomly, and tiny objects flicker in and out of the display causing a sparkling effect.
Techniques to eliminate aliasing effects fall into two categories: those that increase the detail of the display and those that reduce the detail of the scene. Increased screen detail is the intuitively obvious solution: if the observer can see granularity in the image, then finer grain must be used. Formulas exist for determining the necessary grain size given various human observer conditions [2], however increased screen resolution is very expensive since display costs increase with the square of the screen size. It is possible to use some intelligence to increase resolution only in busy areas. Although these adaptive techniques increase the screen detail less of the time, they still suffer from expensive display costs, especially when the scene contains great detail.
Anti-aliasing methods that reduce the scene detail by filtering are more popular than those which increase screen resolution. Some filtering techniques blur the scene in various ways [3] and some clip out small objects [4, 8]. The most successful techniques average all objects that fall into each pixel's area [5, 15] thus permitting the display of objects smaller than a pixel in size. These techniques are not only better than other filtering methods, but also produce better displays than high-granularity techniques of the previous paragraph. Because it is important to precisely represent very small objects, the area-averaging method of anti-aliasing is used in this work.
The display algorithm traverses a Y-sorted list of displayable objects. Each scan line that is to be displayed examines the list of objects corresponding to that line. Each object is either a hierarchical level or a polygon. If the object is a hierarchical level, it is removed from the list and expanded. This expansion causes new hierarchical levels to be placed in the Y-list unless the object is un-subdivided in which case polygons are created and placed in the Y-list. Thus, only the top level of the hierarchy needs to be placed in the Y-list since all appropriate sublevels will be placed there as the image is being created.
When a polygon is encountered in the Y-list, it is sliced horizontally and the pixel-high slice is passed to the shader. The shader creates a depth list, or Z-buffer, of polygons at each pixel. Typical polygons for a pixel are square, but at the edges of an object, arbitrary shaped pixel polygons may appear. When all objects in the Y-list of a scan line have been examined, the Z-buffer is converted into a display line by performing a hidden surface elimination on each pixel. This is a simplified hidden surface algorithm because the polygons do not intersect in Z and are already Z-sorted. Finally, anti-aliasing is done by weighting the areas of every polygon that intersects the pixel. This display algorithm is taken from Whitted [17] and Catmull [5].
Clark suggested that hierarchical representations can be used to easily clip objects that are too small for the display [11]. However, his detail clipping scheme can manifest itself as a flickering of small objects for many moving scenes. The detail fading presented here modifies the notion of detail clipping by merging the coloration of a terminal box with its parent box. This not only gives a pleasing appearance for dynamic scenes, but it simulates the visual effect of "blurring" that appears at the periphery of perception.
The decision to fade detail is made when a hierarchical level is explored and found to be below a threshold in size. At this point, the hierarchical level is treated as if it had no child levels below it: the parallelepiped is converted to displayable polygons. In addition, the amount of fade with the parent hierarchical level is determined by the size of this parallelepiped relative to the detail fading threshold. For the best display, this threshold should be such that the human eye cannot resolve anything smaller. According to the Rayleigh criterion, the angle between two resolvable objects must be:
| sin-1 | [ | 1.22λ ---------- δ |
] |
where δ is the pupil diameter of 0.3 centimeters and λ is the wavelength of 0.000055 centimeters [12]. For a standard view of a television monitor, 1500 to 1800 scan lines are needed [12, 13] which means that for a 512x512 display, objects as small as 1/3 pixel are resolvable.
One can intuitively verify the above minimum resolvable object size. This size should be such that multiple objects cannot occupy one pixel. Assuming that the distance between objects is approximately the same as the size of the objects (typical of texture patterns) then the minimum size of an object is 1/3 of a pixel. Anything smaller than 1/3 pixel in size can be fit two-to-a-pixel and anything larger can not.
In experiments, the lower limit of fading is set to 1/3 pixel. The upper limit of fading, the point at which objects begin to blend into their surroundings, must be large enough to allow a smooth transition. An empirical value of 1 pixel was used and produced pleasing results (see Figure 2). Thus, any object whose size (in either dimension) falls between 1/3 and 1 pixel in size is detail faded. At a size of 1/3 pixel or less, the object is not displayed.
These images were generated from the city database with different magnification. Objects such as the windows in the top center building fade with the background as the view becomes more distant. |
The hierarchical representation of a city scene, mentioned earlier, was used for experiments in detail fading. A large range of detail is available in this database: buildings, rivers, and roads are at the high end and windows, room furniture, and desk pens are at the low end. The range of parallelepiped sizes is so great that the 32-bit word size of the computer is pushed to the limit: the largest objects are nine orders of magnitude larger than the smallest objects. The display program runs on a VAX-11/780 computer running the UNIX operating system.
The system is able to generate anti-aliased and detail faded images of the city in about 20 minutes per frame (512x512 pixels). An animated sequence which zooms into the city has been generated and shows no artifacts of small object aliasing. For example, windows gradually appear as the magnification is increased.
A representation of three-dimensional objects has been presented that hierarchically decomposes the scene. This representation has a number of attractive properties including efficient display access, compact storage of detail, and ease of display subset selection. A display algorithm has also been presented that fades scene detail in a way that makes animated sequences visually pleasing. Using the hierarchical representation, a complex city scene was constructed and displayed. It demonstrates the power of hierarchies in computer graphics.
