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.     

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.     

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.     

Manganese(II)-selective PVC membrane electrode based on a pentaazamacrocyclic manganese complex

Manganese(II) complex of 14,16-dimethyl-1,4,7,10,13-pentaazacyclohexadeca-13,16-diene [Me₂(16)dieneN₅] (I) was synthesized and used in the fabrication of Mn²⁺-selective ISE membrane in PVC matrix. The membrane having Mn(II) macrocyclic complex as electroactive material along with sodium tetraphenylborate (NaTPB) as anion discriminator and dioctylphthalate (DOP) as plasticizer in poly(vinylchloride) (PVC) matrix was prepared for the determination of Mn²⁺. The best performance was observed by the membrane having Mn(II) complex–PVC–NaTPB–DOP in the ratio 1:5:1:3. The sensor worked well over a concentration range of 1.25 × 10⁻⁵ to 1.0 × 10⁻¹ M between pH 3.0 and 8.0 and had a fast response time of 20 s with a lifetime of 4 months. Their performance in partially non-aqueous medium was found satisfactory up to 30% (v/v) alcoholic content. Electrodes exhibited excellent selectivity for Mn²⁺ ion over other mono-, di-, trivalent cations. It can also be used as indicator electrode in the potentiometric titration of Mn²⁺ against EDTA.     

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.     

The Probabilistic Minimum Vertex-covering Problem

An instance of the probabilistic vertex-covering problem is a pair ( G =( V , E ),Pr) obtained by associating with each vertex υ _i ∈ V an 'occurrence' probability p _i . We consider a modification strategy Μ transforming a vertex cover C for G into a vertex cover C _I for the subgraph of G induced by a vertex-set I ⊆ V . The objective for the probabilistic vertex-covering is to determine a vertex cover of G minimizing the sum, over all subsets I ⊆ V , of the products: probability of I times C _I . In this paper, we study the complexity of optimally solving probabilistic vertex-covering.     

Scaled rotation regularization

A new regularization method - a scaled rotation - is proposed and compared with the standard linear regularized discriminant analysis. A sense of the method consists in the singular value decomposition S=TDT′ of a sample covariance matrix S and a use of the following representation of an inverse of the covariance matrix S⁻¹=T(D+λI)⁻¹T ′. For certain data structures the scaled rotation helps to reduce the generalization error in small learning-set and high dimensionality cases. Efficacy of the scaled rotation increases if one transforms the data by y=(D+λI)^−1/2T ′x and uses an optimally stopped single layer perceptron classifier afterwards.     

ON COMPUTING THE MINIMAL LABELS IN TIME POINT ALGEBRA NETWORKS

We analyze the problem of computing the minimal labels for a network of temporal relations in point algebra. Van Beek proposes an algorithm for accomplishing this task, which takes O (max( n ³, n² m) ) time (for n points and m ≠ -relations). We show that the proof of the correctness of this algorithm given by van Beek and Cohen is faulty, and we provide a new proof showing that the algorithm is indeed correct.     

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.     

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.     

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.     

A Novel Approach Makes Higher Order Wavelets Really Efficient for Radiosity

Since wavelets were introduced in the radiosity algorithm ⁵, surprisingly little research has been devoted to higher order wavelets and their use in radiosity algorithms. A previous study ¹³ has shown that wavelet radiosity, and especially higher order wavelet radiosity was not bringing significant improvements over hierarchical radiosity and was having a very important extra memory cost, thus prohibiting any effective computation. In this paper, we present a new implementation of wavelets in the radiosity algorithm, that is substantially different from previous implementations in several key areas (refinement oracle, link storage, resolution algorithm). We show that, with this implementation, higher order wavelets are actually bringing an improvement over standard hierarchical radiosity and lower order wavelets.     

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.     

Supporting the programmer of a rule based language

Abstract: In this paper we take up the plight of the programmer of a rule based language. Our focus is on the type of development environment that is most supportive of such programmers. Our view will be that programming is programming, whether it be with a rule based, functional or imperative language. While it is true that rule based languages have strong links to the Expert Systems field, our discussion in this paper has less to do with 'expert systems' per se ¹ , and more to do with the view of rule based languages as yet another computational paradigm, often included under the same roof with non-rule-based languages. Just as programming environment research has progressed for non-rule-based languages, we would like to build more powerful environments in the rule based world as well. We report here on an attempt to build such an environment. ²     

Determination of reduced glutathione using an amperometric carbon paste electrode chemically modified with TTF–TCNQ

The development of an amperometric sensor for the determination of reduced glutathione (GSH) is described. The sensor is based on tetrathiafulvalene–tetracyanoquinodimethane (TTF–TCNQ) incorporated into the graphite powder/Nujol oil matrix. The electrooxidation of GSH was monitored amperometrically at 200 mV versus SCE (saturated calomel electrode). The amperometric response of the sensor was linearly proportional to the GSH concentration between 20 and 300 μmol l⁻¹, in 0.1 mol l⁻¹ phosphate buffer (pH 8.0), containing 0.1 mol l⁻¹ KCl and 0.5 mmol l⁻¹ Na₂H₂EDTA, as supporting electrolyte.

The detection limit, considering signal/noise ratio equal three, was 4.2 μmol l⁻¹ for GSH and the repeatability obtained as relative standard deviation was of 5.1% for a series of 10 successive measurements.     

Ray Tracing Triangular Bézier Patches

We present a new approach to finding ray–patch intersections with triangular Bernstein–Bézier patches of arbitrary degree. This paper extends and complements on the short presentation¹⁷ . Unlike a previous approach which was based on a combination of hierarchical subdivision and a Newton–like iteration scheme²¹ , this work adapts the concept of Bézier clipping to the triangular domain.
The problem of reporting wrong intersections, inherent to the original Bézier clipping algorithm¹⁴ , is inves-tigated and opposed to the triangular case. It turns out that reporting wrong hits is very improbable, even close to impossible, in the triangular set–up. A combination of Bézier clipping and a simple hierarchy of nested bounding volumes offers a reliable and accurate solution to the problem of ray tracing triangular Bézier patches.     

Simulation and fabrication of piezoresistive membrane type MEMS strain sensors

Two piezoresistive (n-polysilicon) strain sensors on a thin Si₃N₄/SiO₂ membrane with improved sensitivity were successfully fabricated by using MEMS technology. The primary difference between the two designs was the number of strips of the polysilicon patterns. For each design, a doped n-polysilicon sensing element was patterned over a thin 3 μm Si₃N₄/SiO₂ membrane. A 1000×1000 μm² window in the silicon wafer was etched to free the thin membrane from the silicon wafer. The intent of this design was to fabricate a flexible MEMS strain sensor similar in function to a commercial metal foil strain gage. A finite element model of this geometry indicates that strains in the membrane will be higher than strains in the surrounding silicon. The values of nominal resistance of the single strip sensor and the multi-strip sensor were 4.6 and 8.6 kΩ, respectively. To evaluate thermal stability and sensing characteristics, the temperature coefficient of resistance [TCR=(ΔR/R₀)/ΔT] and the gage factor [GF=(ΔR/R₀)/] for each design were evaluated. The sensors were heated on a hot plate to measure the TCR. The sensors were embedded in a vinyl ester epoxy plate to determine the sensor sensitivity. The TCR was 7.5×10⁻⁴ and 9.5×10⁻⁴/°C for the single strip and the multi-strip pattern sensors. The gage factor was as high as 15 (bending) and 13 (tension) for the single strip sensor, and 4 (bending) and 21 (tension) for the multi-strip sensor. The sensitivity of these MEMS sensors is much higher than the sensitivity of commercial metal foil strain gages and strain gage alloys.     

Geometric construction of spline curves with tension properties

In this paper a class of C²∩FC³ spline curves possessing tension properties is described. These curves can be constructed using a simple modification of the well-known geometric construction of C⁴ quintic splines; therefore their shape can be easily controlled using the control net. Their applications in approximation and interpolation of spatial data will be discussed.     

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.