International
Tables for
Crystallography
Volume B
Reciprocal space
Edited by U. Shmueli

International Tables for Crystallography (2006). Vol. B, ch. 3.3, p. 376   | 1 | 2 |

Section 3.3.1.5.6. Advanced hidden-line and hidden-surface algorithms

R. Diamonda*

aMRC Laboratory of Molecular Biology, Hills Road, Cambridge CB2 2QH, England
Correspondence e-mail: rd10@cam.ac.uk

3.3.1.5.6. Advanced hidden-line and hidden-surface algorithms

| top | pdf |

Hidden surfaces may be handled quite generally with the z-buffer technique described in the previous section[link] but this technique becomes very inefficient with very complicated scenes. Faster techniques have been developed to handle computations in real time (e.g. 25 frames s−1) on raster machines when both the viewpoint and parts of the environment are moving and substantial complexity is required. These techniques generally represent surfaces by a number of points in the surface, connected by lines to form panels. Many algorithms require these panels to be planar and some require them to be triangular. Of those that permit polygonal panels, most require the polygons to be convex with no re-entrant angles. Yet others are limited to cases where the objects themselves are convex. Some can handle interpenetrating surfaces, others exclude these. Some make enormous gains in efficiency if the objects in the scene are separable by the insertion of planes between them and degrade to lower efficiency if required, for example, to draw a chain. Some are especially suited to vector machines and others to raster machines, the latter capitalizing on the finite resolution of such systems. In all of these the basic entities for consideration are entire panels or edges, and in some cases vertices, point-by-point treatment of the entire surface being avoided until after all decisions are made concerning what is or is not visible.

All of these algorithms strive to derive economies from the notion of `coherence'. The fact that, in a cine context, one frame is likely to be similar to the previous frame is referred to as `frame coherence'. In raster scans line coherence also exists, and other kinds of coherence can also be identified. The presence of any form of coherence may enable the computation to be concerned primarily with changes in the situation, rather than with the totality of the situation so that, for example, computation is required where one edge crosses in front of another, but only trivial actions are involved so long as scan lines encounter the projections of edges in the same order.

The choice of technique from among many possibilities may even depend on the viewpoint if the scene has a statistical anisotropy. For example, the depiction of a city seen from a viewpoint near ground level involves many hidden surfaces. Distant buildings may be hidden many times over. The same scene depicted from an aerial viewpoint shows many more surfaces and fewer overlaps. This difference may swing the balance of advantage between an algorithm which sorts first on z or one which leaves that till last.

These advanced techniques have, so far, found little application in crystallography, but this may change. Ten such techniques are critically reviewed and compared by Sutherland et al. (1974[link]), and three of these are described in detail by Newman & Sproull (1973[link]).

References

Newman, W. M. & Sproull, R. F. (1973). Principles of inter-active computer graphics. New York: McGraw-Hill.Google Scholar
Sutherland, I. E., Sproull, R. F. & Schumacker, R. A. (1974). A characterization of ten hidden surface algorithms. Comput. Surv. 6, 1–55.Google Scholar








































to end of page
to top of page