At Last an ISO C Binding of GKS

The C⁴ bindings of GKS1 and other semantic computer graphics standards like GKS–3D² and PHIGS³ are long overdue. While GKS was completed in 1985 and GKS–3D² (and PHIGS³) became an international standard in 1988, none of their C bindings could be standardized, for the simple reason that the C language itself was not a standard. Instead, a host of de facto GKS/C bindings⁹ appeared.
This paper will give the flavour of the ISO C binding^5,6 of GKS; the main features will be outlined.
1983 CR Categories: D.3.0,I.3.0,I.3.4.     

A Method for the Representation, Evaluation and Display of CSG Models in PHIGS and PHIGS+

The Programmer's Hierarchical Interactive Graphics System (PHIGS) is about to become a standard graphics system ^† which caters for the definition, display and modification of two and three-dimensional graphical data.
PHIGS , however, is mainly a wireframe system, and the PHIGS⁺ , extensions to it have been put forward to allow the incorporation of shaded 3D graphics into PHIGS. ,
One area that is important to a large constituency and which has so far not been considered in PHIGS , and PHIGS⁺ , is that of solid modelling. This paper addresses one aspect of solid modelling by describing a simple method for the representation, evaluation and display of Constructive Solid Geometry (CSG) models in PHIGS , and PHIGS⁺. .     

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.     

Parametric Surfaces in PHIGS PLUS: a New Chance for Patterning and Hatching?

The Polygon Fill style PATTERN and HATCH, which are quite successful in 2D graphics standards as GKS¹ and CGI² have proved to be less suitable for 3D graphics standards as GKS-3D³ and PHIGS⁴. However, the emerging standard PHIGS PLUS⁵ offers a unique chance to successfully employ these Interior Styles (under another name and in a slightly different form), because PHIGS PLUS supports a.o. topologically rectangular parametric surfaces In this article it is shown how these Interior Styles could be efficiently applied to curved surfaces in PHIGS PLUS. In addition, the possible interaction between the tessellation method and the patterning is shown.     

The role of native grammars in correcting errors in second language learning

This paper describes VP², a system that has been implemented to tutor nonnative speakers in English. This system differs from many tutoring systems by employing an explicit grammar of its user's native language. This grammar enables VP² to customize its responses by addressing problems due to interference of the native language. The system focuses on the acquisition of English verb-particle and verb-prepositional phrase constructions. Its correction strategy is based upon comparison of the native language grammar with an English grammar. VP² is a modular system: its grammar of a user's native language can easily be replaced by a grammar of another language. The problems and solutions presented in this paper are related to the more general question of how modelling previous knowledge facilitates instruction in a new skill.     

COMPLEXITY RESULTS FOR SAS+ PLANNING

We have previously reported a number of tractable planning problems defined in the SAS⁺ formalism. This article complements these results by providing a complete map over the complexity of SAS⁺ planning under all combinations of the previously considered restrictions. We analyze the complexity of both finding a minimal plan and finding any plan. In contrast to other complexity surveys of planning, we study not only the complexity of the decision problems but also the complexity of the generation problems. We prove that the SAS⁺-PUS problem is the maximal tractable problem under the restrictions we have considered if we want to generate minimal plans. If we are satisfied with any plan, then we can generalize further to the SAS⁺-US problem, which we prove to be the maximal tractable problem in this case.     

Reduced game property of the Egalitarian Non-k-Averaged Contribution (EN k AC-) value and the Shapley value

The Egalitarian Non- k -Averaged Contribution (EN ^k AC-) value for TU-game represents the equal division of the surplus of the total profits, given that each player is already allocated his individual contribution specified by worths of coalitions of size k . This paper deals with the axiomatic characterization of the EN ^k AC-value on the class of cooperative games with a fixed player set as well as a variable player set. The latter axiomatization involves a consistency axiom in terms of the reduced games. The EN ^k AC-value is the unique value on the class of cooperative games with a variable player set which possesses the relative invariance under strategic equivalence, the equal treatment property and the reduced game property for two types of reduced games. We also propose a new reduced game in terms of which the Shapley value is axiomatized.     

G1 Hierarchical Bézier Surface over Arbitrary Meshes

This paper presents a method for constructing composite surfaces based on a collection of quadrilateral patches. A global parameterization using bilinear quadrilateral meshes and FEM like minimization procedure are introduced. Smoothing conditions such as C¹ and G¹ are handled by constraint equation and a related duality argument is implemented. The surfaces that can be constructed in this way include conforming and non-conforming connections (3 n 6, T-nodes) between elementary patches. Non-manifold surfaces are automatically treated also by this data structure. The underlying quadratic programming with linear constraints is solved by duality methods. Hierarchical data structure with bordering matrices methods are implemented to deal with local refinement (subdivision). The present work details the actual implementation for the case of Bézier patches.     

Bounds on the largest singular value of a matrix and the convergence of simultaneous and block-iterative algorithms for sparse linear systems

We obtain the following upper bounds for the eigenvalues of the matrix A ^† A . For any a in the interval [0, 2] let and c_a and r_a the maxima of the c_aj and r_ai , respectively. Then no eigenvalue of the matrix A ^† A exceeds the maximum of over all i , nor the maximum of over all j . Therefore, no eigenvalue of A ^† A exceeds c_ar_a .
Using these bounds, it follows that, for the matrix G with entries no eigenvalue of G ^† G exceeds one, provided that, for some a in the interval [0, 2], we have and
Using this result, we obtain convergence theorems for several iterative algorithms for solving the problem Ax = b , including the CAV, BICAV, CARP1, SART, SIRT, and the block-iterative DROP and SART methods.     

An Algorithm for Minimal Insertion in a Type Lattice

The problem of inserting a new element x into a lattice of types L is addressed in the paper. As the poset L + x obtained by the direct insertion of x in L is not necessarily a lattice, some set of auxiliary elements should be added to restore the lattice properties. An approach toward the lattice insertion is presented which allows the set of auxiliary elements to be kept minimal. The key idea is to build the final lattice L ⁺ as isomorphic to the Dedekind–McNeille completion of the order L + x . Our strategy is based on a global definition of the set of auxiliary elements and their locations in L ⁺. Each auxiliary is related to a specific element of L , an odd , which represents GLB (LUB) of some elements in L superior (inferior) to x . An appropriate computation scheme for the auxiliary types is given preserving the subtyping in the lattice L ⁺. The insertion strategy presented is more general than the existing ones, since it deals with general kinds of lattices and makes no hypothesis on the location of x in L . An algorithm computing L ⁺ from L and x of time complexity O (| L || J ( L )| ω ^3( L )) is provided.