Search

This paper discusses the hidden-surface problem from tile point of view of sorting. The various surfaces of an object to be shown in hidden-surface or hidden-line form must be sorted to find out which ones are visible at various places on the screen. Surfaces may be sorted by lateral position in the picture (X I'), by depth (Z), or by other criteria. The paper shows that the order of sorting and the types of sorting used form differences among the existing hidden-surface algorithms. To reduce the work of sorting, each algorithm capitalizes on some coherence property of the objects represented. ‘Scan-line coherence,’ the fact that one TV scan line of output is likely to be nearly the same as the previous TV scan line, is one commonly used kind of coherence. ‘Frame coherence,’ the fact that the entire picture does not change very much between successive frames of a motion picture can be very helpful if it is applicable. By systematically looking for additional kinds of coherence and untried sorting orders and sorting types, the paper is able to suggest two promising new approaches to the hidden-surface problem. The first, a combination of three existing algorithms, is promising because it would capitalize on both frame and scan-line coherence. The second new approach would sort in the order Y, Z, X, … the only sorting order for which an existing algorithm could not be found. [ABSTRACT FROM AUTHOR]

The bibliography appearing at the end of this article lists 37 sorting algorithms and 100 books and papers on sorting published in the last 20 years. The basic ideas presented here have been abstracted from this body of work, and the best algorithms known are given as examples. As the algorithms are explained, references to related algorithms and mathematical or experimental analyses are given. Suggestions are then made for choosing the algorithm best suited to a given situation. [ABSTRACT FROM AUTHOR]

This article focuses on September 1984 issue of "ACM Computing Surveys." Two articles in this issue explore efforts to improve system performance through parallelism. The articles examine parallel sorting algorithms. They present historical developments in parallel sorting, emphasizing feasibility of algorithms rather than their theoretical aspects. Most of these algorithms employ main memory, and are, therefore, internal sorting approaches, as contrasted with external sorting, where the size of the file to be sorted makes it impossible to use main memory exclusively. Another article discusses parallel algorithms and data structures for graph processing. Graphs are widely used, both in computer science and in related science and engineering fields. The paper gives attention to the feasibility of implementation of these algorithms on parallel processors. Much of the information in this article is very compactly presented in tabular form, showing the principal results by method, model, and complexity.