Skip to main content
main-content

Über dieses Buch

Raster graphics differs from the more traditional vector or line graphics in the sense that images are not made up from line segments but from discrete elements orderly arranged in a two-dimensional rectangular region. There are two reasons for the growing popularity of raster graphics or bit-mapped displays: I) the possibilities they offer to show extremely realistic pictures 2) the dropping prices of those displays and associated processors and memories. With the rise of raster graphics, all kinds of new techniques, methods, algorithms and data representations are associated -such as ray tracing, raster operations, and quadtrees-bringing with them a lot of fruitful research. As stated above raster graphics allows to create extremely realistic (synthesized) pictures. There are important applications in such diverse areas as industrial deSign, flight Simulation, education, image processing and animation. Unfortunately many applications are hampered by the fact that with the present state of the art they reqUire an excessive amount of computing resources. Hence it is worthwhile to investigate methods and techniques which may be of help in redudng computer costs associated with raster graphics applications. Since the choice of data srtuc­ tures influences the efficiency of algorithms in a crudal way, a workshop was set up in order to bring together a (limited) number of experienced researchers to dis­ cuss this topic. The workshop was held from 24 to 28 June 1985 at Steensel, a tiny village in the neighbourhood of Eindhoven, the Netherlands.

Inhaltsverzeichnis

Frontmatter

Problems with raster graphics algorithms

Abstract
Assorted unusual problems with raster graphics digitization or scan conversion algorithms, where the implementation is much harder than the concept, are considered. They include digitizing a line that is on a plane so that the line is always visible, and digitizing a subset of a line correctly. Raster graphics is harder than vector graphics, in a deep sense.
Wm. Randolph Franklin

Display algorithms for quadtrees and octtrees and their hardware realisation

Abstract
For interactive use images have to be displayed in the shortest possible time: this implies the use of special hardware. Accordingly, the fast display of quadtrees and octtrees depends on scan conversion algorithms which are simple enough to be implemented in hardware. Three hardware systems for the display of quadtrees are described; the algorithms which underlie the hardware implementations are described together with the data structures on which they work. Several algorithms for the display of octtrees are described together with hardware possibilities.
M. A. Oliver

Intermediate data structures for display algorithms

Abstract
This paper describes two algorithms and implicit data structures to display 3D scenes composed of polygons on a raster device. Both algorithms are based on the so-called painter’s technique; the first one uses a depthsort algorithm for the visible surface calculation a la Newell, Newell, and Sancha ([l]), the other one uses a priority tree as proposed by Fuchs, Kedem, and Naylor ([2]).
Both algorithms were designed to be used in interactive applications. In order to update an image on the screen as fast as possible and to prevent the recomputation of the whole image after a change in the scene has occurred, an intermediate representation of the scene is needed. This intermediate representation might also be of use in detecting which polygon is meant when a pixel on the screen is pointed at.
For both display algorithms some intermediate representations will be considered, as well as the implications of alterations in the scene upon both these representations and their display.
Marloes L. P. van Lierop

Data structures for ray tracing

Abstract
Methods to improve the efficiency of the ray tracing process are reviewed. Special attention is given to algorithms for tracing a ray through box and cell structures of hierarchical box and spatial subdivision methods.
Frederik W. Jansen

An approach for a PHIGS machine

Abstract
The Programmer’s Hierarchical Interactive Graphics System (PHIGS) proposal specifies a powerful interface for the development of interactive graphics applications. Throughout the development of PHIGS, emphasis has been placed on providing a high level of functionality along with the ability to provide rapid, dynamic display modifications. Any implementation of PHIGS should strive toward the ultimate goal of providing real-time support for the full functionality. This goal will be impossible to achieve using current, readily available graphics hardware. This is due to the inherent complexity introduced by the desired level of functionality and not to any of the specific approaches that PHIGS has taken to providing that functionality. One possible solution to this problem is the development of a “PHIGS machine.” Such a machine will play the role of a PHIGS logical workstation. This machine must include customized hardware to perform many of the functions required to meet the PHIGS specifications. Some of the more important PHIGS features which one must consider when approaching the architecture of such a machine include structure manipulation, structure traversal and the viewing pipeline.
Salim S. Abi-Ezzi, Michael A. Milicia

Using linear quadtrees to store vector data

Abstract
The linear quadtree is adapted to store vector data by defining a new data structure called a segment quadtree. It uses a constant or bounded, amount of storage per node, represents straight lines exactly (i.e., it is not a digitized representation), and enables updates in a consistent manner (i.e., when a vector feature is deleted, the database can be restored to the state it would have been in had the deleted feature never been inserted). The segment quadtree is shown to meet these requirements whereas existing quadtree-like methods (e.g., the edge quadtree, strip tree, etc.) fail to satisfy them. In order to illustrate the usefulness of the segment quadtree, sample algorithms are discussed to insert and delete line segments as well as perform boundary following. The space requirements of segment quadtrees are also investigated.
Hanan Samet, Clifford A. Shaffer, Robert E. Webber

A model for raster graphics language primitives

Abstract
Raster graphics systems are becoming increasingly popular due to improved technology and lower costs. However, this positive development has not had its follow-up in the software department: currently there is virtually no integrated raster graphics software available.
We propose a hierarchical model in which the applicability in raster graphics is of primary importance. The model is based upon a number of 0D, ID and 2D primitives to generate graphical patterns. These patterns may also be formed by means of expressions over other patterns. They form the end-nodes of a data structure consisting of a directed, acyclic graph, the pattern graph, the nodes of which contain attributes. By using priority ordering in the graph ’2.5D’ pictures may be constructed. Attributes in the graph govern detectability, visibility, highlighting, level and graphical transformations. This two-stage approach to making pictures has been developed in order to achieve a model for raster graphics, catering for interaction.
Wim J. M. Teunissen, Jan van den Bos

Pattern representation

Abstract
This paper discusses the representation of patterns given certain requirements. Patterns are area oriented picture elements. The requirements are that the picture making devices can use raster technology and that the applications using the pictures are highly interactive, making intensive use of real-time picture change.
P. J. W. Ten Hagen, C. G. Trienekens

A 3D animation system

Abstract
A hardware architecture for image generation is described that allows the combination of polygon rendering and ray casting. Since special purpose hardware is used for both tasks, a considerable speed up is achieved.
Pascal Leray

Applications of the method of invariants in computer graphics

Abstract
In order to evoke a discussion about possible future research themes for the Eindhoven Department of Mathematics and Computing Science, a small overview about the scientific background of the group is presented. We sketch the global framework of the method of invariants in deriving algorithms, and we apply this method to two well-known basic algorithms in computer graphics.
Kees van Overveld

Bibliography on quadtrees and related hierarchical data structures

Abstract
This bibliography is an updated version of the one published in ACM Computing Surveys [214].
Hanan Samet
Weitere Informationen