Formal Specification in the Revision of GKS: An Illustrative Example

The first ISO/IEC standard for computer graphics, the Graphical Kernel System (GKS) was published in August 1985. In accordance with ISO/IEC procedures, GKS is now being reviewed and revised. This paper describes how formal specification techniques are being used by the authors to analyse key parts of proposals being made for changes to the framework of GKS to bring the standard into line with the requirements of applications and the operating environment likely to be found in the mid-1990's.     

Better Understanding through Formal Specification

The Graphical Kernel System (GKS) is now registered as an ISO International Standard for computer graphics programming. One of the major innovations of the Standard is the bundled specification of aspects, a mechanism which gives the applications programmer the ability to tailor the appearance of a picture independently on each of the workstations on which it is displayed, using the capabilities of the workstations. GKS also incorporates the traditional method of individual specification of aspects in which each workstation does the best it can to represent global aspect values. In this paper a formal specification technique, the Vienna Development Method (VDM), is used to describe aspect specification. The GKS model of aspect specification is progressively constructed from simpler models. Properties of these simpler models are formulated and the specifications are proved to conform to these. The properties are then traced through the more complex models. The paper demonstrates the applicability of formal specification to the design of graphics software and the ability of formal techniques to catalyse the deeper understanding of designs.     

GKS certification—An overview

The rapid emergence of GKS implementations indicates the widespread acceptance of GKS as an international standard for computer graphics. It is essential however if the interests of the standard are to be preserved, that there be a feasible means of validating GKS implementations to ensure that adherence to the standard is maintained. This paper describes an overall methodology for GKS certification, and outlines in more detail the validation of data returned by GKS to an application program. Validation of output generated by GKS is discussed in general terms in this paper, and in more detail in other papers in this issue.     

Standards in computer graphics

GKS, which recently became the International Standards Organization (ISO) standard for computer graphics programming, is the first of a set of interlocking graphics standards. This paper outlines the important ideas behind GKS, describes its relationship with other standards and discusses the benefits of standardization.     

GKS-9x: Some Implementation Considerations

The Graphical Kernel System (GKS) was published as an ISO standard for computer graphics programming in August 1985. GKS is now undergoing revision in ISO/IEC and at the time of writing the text of the Draft International Standard of GKS-9x was being finalized. This paper presents a way in which a key part of the new functionality in GKS-9x, namely namesets and selection criteria, can be implemented effectively.     

A Multi-Microprocessor GKS Workstation

Implementers of graphical application sytems hesitate to interface their applications to the GKS standard not only because GKS functionality seems to be less suffcient for a particular application but also because the use of GKS-as it is offered in portable software implementions-uaually means a loss of system performance. This article describes an installation of GKS on a multi-microprocessor that is based on functional distribution principles as well as on the object-oriented distribution of a graphics system. The main concepts and advantages of a GKS workstation using more than one processing unit with at least one output pipeline are described. The flexibility of this approach opens a perspective view to a GKS workststion that is configurable to application requirements.     

The GKS Input Model in Manifold

This paper describes the specification of the GKS input model in M anifold . The aim of the work reported in this paper was two-fold: first, to review the communication patterns implied by the GKS input model, and second, to evaluate the suitability of the M anifold language as a tool for defining complex dynamic interaction patterns that are common in non-trivial user interfaces.
The GKS input model is also adopted by all more recent ISO graphics standard documents. A more formal scrutiny of the inter-communication of the components of this model, excluding the implementation details of their functionality, is instructive in itself. It can reveal directions for improvement of its shortcomings and for generalization of its strengths for the ongoing effort to define the functionality of future graphics packages.
M anifold is a language for describing inter-process communications. Processes in M anifold communicate by means of buffered communication links called streams and by reacting to events raised asynchronously by other processes. Our experience shows that M anifold is a promising tool for describing systems of cooperating parallel processes. Our M anifold specification of the GKS input model offers a very flexible way to structure user defined logical input devices. Furthermore, it is simple and modular enough to allow easy extensions to include more functionality by local modifications. As such, it can serve as a basis for possible extensions and enhancements envisioned for future graphics packages.
1987 CR Categories: C.1.2, C.1.3, C.2.m, D.1.3, F.1.2, I.1.3, I.3.6, I.3.4.
1885 Mathematical Subject Classification: 68N99, 68Q10,68U05.     

Experiences with implementing GKS on a PERQ and other computers

Driven by a need for a graphics system that would provide a wider range of functions than is common and that would require less support effort when installed on about 50 mainframes, Rutherford Appleton Laboratory has implemented the Graphical Kernel System (GKS). The development project has used PERQ and VAX computers equally. This paper describes some of the design decisions and their effect on the resulting package. In particular, it describes the philosophy of the “workstation interface” and how this provides for devices and systems of greater complexity in the future. The way in which the facilities of the PERQ are matched to GKS concepts is outlined.     

Algorithms for Handling the Fill Area Primitive of GKS

The fill area primitive of GKS (Graphical Kernel System)¹ is one of the more powerful features which differentiates it from earlier device independent graphics software and systems. Its specification is extremely general in the form of a closed boundary, possibly self-intersecting, and whose interior can be filled in a variety of styles. However a complete implementation of this primitive is very complex. It is difficult to find a single graphics workstation incorporating this primitive in hardware or firmware. Most GKS implementations will have to include software for simulating the appearance of this primitive on the commonly available displays and hard-copy graphics devices. Correct and efficient algorithms are necessary for developing this software. Because of the generality many of the existing algorithms are not directly applicable. In this paper we describe:
1. a new algorithm for clipping a fill area polygon, using what we have named as the Bridge Technique.
2. implementation of a plane sweep algorithm, by Nievergelt and Preparata,² for solid filling and hatching, particularly applicable to vector devices.
3. extension of the plane sweep algorithm for filling with any given pattern on raster as well as vector devices.
The algorithms have been designed to work for all special cases as well. In fact they have been implemented having in mind the fill area set primitive of GKS-3D extension.³ All these algorithms have been very successfully implemented in a commercially available GKS implementation, namely indoGKS.     

GKS-the standard for computer graphics

GKS is about to be ratified as the first international standard for computer graphics. It will provide a unique base on top of which portable graphical applications software can be built. This paper traces the history of GKS and describes its main concepts.     

GKS-94: an overview

A revision of the Graphical Kernel System (GKS), the first ISO standard for computer graphics programming, was completed in 1994. This summary of GKS-94 also describes an implementation of part of its new functionality. We have demonstrated that fast selection is possible with GKS-94. Thus, an application can use namesets and selection criteria as its main method of subdivision, selection and creating hierarchy within the application, and performance is acceptable given a reasonable implementation. European organizations are showing interest in implementing GKS-94, and new products are anticipated early in 1996     

3D extension to GKS

The Graphical Kernel System GKS has [1] been established as the first standard in the field of Computer Graphics covering two-dimensional (2D) graphics. Now work is going on to develop standards in related areas. One important effort is the extension of GKS for three-dimensional (3D) graphics. This paper will briefly overview the history of standardization efforts with respect to 3D graphics and then report the current activities of various national and international standardization bodies for extending GKS to 3D. Then the paper will concentrate on GKS-3D [2], a proposal for a 3D extension of GKS which is developed by the Dutch standardization committee NNI in close collaboration with the International Organization for Standardization ISO/TC97/SC21/WG2. Technical work is expected to finish in 1985. Scope and purpose of this future 3D standard and goals of the design are given and the functionality of the 3D extension is described in some detail. As technical work on GKS-3D is going on, changes may occur to the standard document. The major issues will be surveyed and trends will be sketched.     

结合形式化的面向对象设计方法与支撑系统

为了有效地结合形式化和非形式化设计方法各自的优点,克服其不足之处,以尽可能保证软件设计的质量与可靠性,文章提出了一种将形式化方法与非形式化的面向对象设计方法ＨＯＯＤ（ｈｉｅｒａｒｃｈｉｃａｌｏｂｊｅｃｔ－ｏｒｉｅｎｔｅｄｄｅｓｉｇｎ）相结合的途径,并介绍了其机器支撑环境的设计与实现．该途径在对层次式面向对象设计方法ＨＯＯＤ进行必要扩充的基础上,有机地集成了Ｚ语言等形式规约技术．支持这一途径的支撑环境提供了一套方便灵活的图形构筑工具、语法制导的形式语言与文本编辑工具,以及自动检查机制等．     

GKS Programming in a PHIGS Environment

GKS is an international standard for the functional interface to 2D graphics, whilst PHIGS is currently an ISO work item for 2D and 3D graphics. In addition, PHIGS allows improved control over structuring graphics data in the system. With a new work item, the upwards compatability from GKS to PHIGS is being called into question. This paper is an attempt to give direction to these discussions by listing the implications of introducing a software layer between a GKS application program and a PHIGS environment on which this application is to be run. It is intended to highlight differences between the systems and to answer questions such as, “How compatible?”, “Is it possible?”, “How much does the software layer have to do?”, etc.     

Evaluation of Standard Graphics Packages

In order to compare the quality of different implementations of GKS, the ISO0 standard for computer graphics, an evaluation method for GKS implementations is presented. It is based upon several groups of criteria. One group of criteria is concerned with performance, by which we understand here the memory requirements and time requirements for programs using GKS functions. A program that measures the performance of GKS packages is presented. Results of this evaluation method with several commercially available GKS implementations are described in summary. A checklist for evaluation of standard graphics packages is added as an appendix.     

An interactive FORTRAN 77 program using GKS graphics for 2.5 D modeling of gravity and magnetic data

An interactive 2.5 D gravity and magnetics modeling program has been written for an ICL PERQ 2 workstation using FORTRAN 77 and GKS graphics. All of the available hardware and software input devices are utilized through GKS to produce an easy-to-use menu-driven program. A large number of functions are controlled by the software in order than the user can concentrate on the model. A range of options also are provided for manipulating the observed anomaly. The use of FORTRAN 77 and GKS should make the program easily portable to other computer systems and graphics devices. The modular form of the program should facilitate readily further development including optimization and real time modeling, given a more powerful computer with high-speed graphics.     

GRAFLOG: Understanding Drawings through Natural Language

This paper describes an experimental interactive graphics interface, GRAFLOG, in which drawings receive linguistic interpretations. It is possible to emulate linguistic interaction in situations where graphics is thought to be necessary. The paper presents examples of such a kind of dialogue and the architecture of the implementation. The paper explains how representations of drawings can be constructed by treating graphical symbols as "objects", and how a parallel linguistic interpretation for these symbols can be constructed. It highlights the relevance of "deictic expressions" and "spatial prepositions" in building the interface mechanisms between these two kinds of representations. Lastly, it shows how a reasoning component is constructed for making deductions from premises that are found in both the graphical and linguistic domains. Using GRAFLOG, it is possible to represent knowledge through words and pictures. GRAFLOG is implemented, using an object oriented programming style, in PROLOG and GKS.     

A VLSI Implementation of the Graphics Standard GKS

The main advantage when using a standardized graphics system is quite obvious: the application programs become portable. Integrating such a system - and GKS (Graphical Kernel System) is the only one being standardized internationally - into VLSI (Very Large Scale Integration) chips, this graphics system may become an integral part of graphical devices. This guarantees a uniform interface of such devices to GKS applications. Devices of many different kinds will become compatible not only with respect to plugging but even in their logical behaviour, eliminating all device dependencies from the host software.
We have started to design the GKS-chip which will be able to be used in a great variety of devices (vector and raster type). The GKS-chip will bring the computational power to support real time picture updates, limited only by the maximally attainable output data rate.