A new family of clipping algorithms is described. These algorithms are able to clip polygons against irregular convex plane-faced volumes in three dimensions, removing the parts of the polygon which lie outside the volume. In two dimensions the algorithms permit clipping against irregular convex windows.
Polygons to be clipped are represented as an ordered sequence of vertices without repetition of first and last, in marked contrast to representation as a collection of edges as was heretofore the common procedure. Output polygons have an identical format, with new vertices introduced in sequence to describe any newly-cut edge or edges. The algorithms easily handle the particularly difficult problem of detecting that a new vertex may be required at a corner of the clipping window.
The algorithms described achieve considerable simplicity by clipping separately against each clipping plane or window boundary. Code capable of clipping the polygon against a single boundary is reentered to clip against subsequent boundaries. Each such reentrant stage of clipping need store only two vertex values and may begin its processing as soon as the first output vertex from the preceeding stage is ready. Because the same code is reentered for clipping against subsequent boundaries, clipping against very complex window shapes is practical.
For perspective applications in three dimensions, a six-plane truncated pyramid is chosen as the clipping volume. The two additional planes parallel to the projection screen serve to limit the range of depth preserved through the projection. A perspective projection method which provides for arbitrary view angles and depth of field in spite of simple fixed clipping planes is described. This method is ideal for subsequent hidden-surface computations.
Artificial Intelligence and Machine Learning
Advertisement
A fast method for solving a class of tridiagonal linear systems
The solution of linear systems having real, symmetric, diagonally dominant, tridiagonal coefficient matrices with constant diagonals is considered. It is proved that the diagonals of the LU decomposition of the coefficient matrix rapidly converge to full floating-point precision. It is also proved that the computed LU decomposition converges when floating-point arithmetic is used and that the limits of the LU diagonals using floating point are roughly within machine precision of the limits using real arithmetic. This fact is exploited to reduce the number of floating-point operations required to solve a linear system from 8n - 7 to 5n + 2k - 3, where k is much less than n, the order of the matrix. If the elements of the subdiagnals and superdiagonals are 1, then only 4n + 2k - 3 operations are needed. The entire LU decomposition takes k words of storage, and considerable savings in array subscripting are achieved. Upper and lower bounds on k are obtained in terms of the ratio of the coefficient matrix diagonal constants and parameters of the floating-point number system.
Various generalizations of these results are discussed.
Syntax-directed least-errors analysis for context-free languages: a practical approach
A least-errors recognizer is developed informally using the well-known recognizer of Earley, along with elements of Bellman's dynamic programming. The analyzer takes a general class of context-free grammars as drivers, and any finite string as input. Recognition consists of a least-errors count for a corrected version of the input relative to the driver grammar. The algorithm design emphasizes practical aspects which help in programming it.
In his interesting contribution to the study of the conversion of limited-entry decision tables to flowcharts or sequential testing procedures, Verhelst [1] presents two algorithms, one of which is claimed to produce the optimal flowchart with respect to run-time. Unfortunately this minimum run-time algorithm does not always produce the result claimed, as we illustrate by example below.
Advanced cryptographic techniques for computer
Cryptographic techniques which can be used to maintain the confidentiality of information processed by computers are dealt with. Special emphasis is paid to the unique characteristics of computer files that make many cryptographic methods of little use. Relative security, costs, and preferred methods are included in this paper.
A case study in programming for parallel-processors
An affirmative partial answer is provided to the question of whether it is possible to program parallel-processor computing systems to efficiently decrease execution time for useful problems. Parallel-processor systems are multiprocessor systems in which several of the processors can simultaneously execute separate tasks of a single job, thus cooperating to decrease the solution time of a computational problem. The processors have independent instruction counters, meaning that each processor executes its own task program relatively independently of the other processors. Communication between cooperating processors is by means of data in storage shared by all processors.
A program for the determination of the distribution of current in an electrical network was written for a parallel-processor computing system, and execution of this program was simulated. The data gathered from simulation runs demonstrate the efficient solution of this problem, typical of a large class of important problems. It is shown that, with proper programming, solution time when NP processors are applied approaches 1/NP times the solution time for a single processor, while improper programming can actually lead to an increase of solution time with the number of processors. Storage interference and other measures of performance are discussed. Stability of the method of solution was also investigated.
APAREL—A parse-request language
APAREL is described: this language is an extension to an algorithmic language (PL/I) that provides the pattern-matching capabilities normally found only in special purpose languages such as SNOBOL4 and TMG. This capability is provided through parse-requests stated in a BNF-like format. These parse-requests form their own programming language with special sequencing rules. Upon successfully completing a parse-request, an associated piece of PL/I code is executed. This code has available for use, as normal PL/I strings, the various pieces (at all levels) of the parse. It also has available, as normal PL/I variables, the information concerning which of the various alternatives were successful. Convenient facilities for multiple input-output streams, the initiation of sequences of parse-requests as a subroutine, and parse-time semantic checks are also included.
APAREL has proven convenient in building a powerful SYNTAX and FUNCTION macro system, an algebraic language preprocessor debugging system, an on-line command parser, a translator for Dataless Programming, and as a general string manipulator.
An interactive graphical display monitor in a batch-processing environment with remote entry
A graphic monitor program is described. It was developed at Carnegie-Mellon University for the CDC G21 computer, which is a general purpose, batch-processing system with remote entry. The existing G21 system and the graphics hardware are described. The graphic monitor is a resident auxiliary monitor which provides comprehensive managerial capability over the graphical system in response to commands from the human user. It also will respond to commands from a user program through a similar interface, where routine calls take the place of manual actions. Thus the human and program can interact on a symmetrical and equal basis through the medium of the graphic monitor.
The choices made in designing the graphic monitor, given the constraints of the existing hardware and computer system, are discussed.
The structure of the monitor program and the human and program interfaces are described. There is also a transient swapping version with a small resident part, and provision for swapped used submonitors.
A modular computer sharing systems
An alternative approach to the design and organization of a general purpose interactive multiterminal computing system is presented. The system organization described is a conceptually simple arrangement of a bank of interchangeable computers, each of which is a memory/proputor pair, that are assigned to process terminal jobs as they arrive. One of the computers serves as the master or control computer and supervises the collection and distribution of messages from and to the remote terminals. In the simplest form there is a disk drive for each connected terminal. A crosspoint switching network allows any such disk drive to be connected to any computer in the bank, under control of the control computer. Thus, while each active terminal user “occupies” a dedicated disk drive, he may share the computer with many other terminal users in a simple manner. The ratio of users to computers is dependent on both the size and power of the machines used and the computation requirements of the particular mix of users.
This system organization is inherently a simpler and therefore more reliable approach to time-sharing computers and has the potential of a highly available system at relatively low cost. Economic configurations are possible for a range of systems sizes that span at least one order of magnitude. Finally, problem programs developed by remote terminal users can be run on a dedicated batch system if compatible computers are used.
A comment on optimal tree structures
In Y.N. Patt's paper “Variable Length Tree Structures Having Minimum Average Search Time” [Comm. ACM 12 (Feb. 1969)], the tree structures obtained are not actually optimal with respect to the two-dimensional chaining devised by Sussenguth in his 1963 paper. This note points out that the result can be described as “optimal” only under the constraint—which Patt implicity assumes—that no key be allowed to prefix another.
The teachable language comprehender: a simulation program and theory of language
The Teachable Language Comprehender (TLC) is a program designed to be capable of being taught to “comprehend” English text. When text which the program has not seen before is input to it, it comprehends that text by correctly relating each (explicit or implicit) assertion of the new text to a large memory. This memory is a “semantic network” representing factual assertions about the world.
The program also creates copies of the parts of its memory which have been found to relate to the new text, adapting and combining these copies to represent the meaning of the new text. By this means, the meaning of all text the program successfully comprehends is encoded into the same format as that of the memory. In this form it can be added into the memory.
Both factual assertions for the memory and the capabilities for correctly relating text to the memory's prior content are to be taught to the program as they are needed. TLC presently contains a relatively small number of examples of such assertions and capabilities, but within the system, notations for expressing either of these are provided. Thus the program now corresponds to a general process for comprehending language, and it provides a methodology for adding the additional information this process requires to actually comprehend text of any particular kind.
The memory structure and comprehension process of TLC allow new factual assertions and capabilities for relating text to such stored assertions to generalize automatically. That is, once such an assertion or capability is put into the system, it becomes available to help comprehend a great many other sentences in the future. Thus the addition of a single factual assertion or linguistic capability will often provide a large increment in TLC's effective knowledge of the world and in its overall ability to comprehend text.
The program's strategy is presented as a general theory of
A program for the syntactic analysis of English sentences
A program is described which produces syntactic analyses of English sentences with respect to a transformational grammar. The main features of the analyzer are that it uses only a limited dictionary of English words and that it pursues all analysis paths simultaneously while processing the sentence from left to right.
The form of representation used for the dictionary and the grammar is indicated and an outline account is given of the analysis procedure. Techniques for keeping the size of the analysis record within reasonable limits and for avoiding the need for dynamic application of certain transformational rules are described.
A number of examples of output produced by the program are given. The output includes timing information.
Some methods for contour mapping by means of a digital plotter are dicussed, and a new method is presented that is simple enough to be implemented by programs with a rather small number of instructions (about 120 FORTRAN IV instructions are required). Comparisons with some methods proposed by other authors are also performed.
A FORTRAN IV program implementing the proposed method is availabel at the Istituto di Elettrotecnica ed Elettronica, Politecnico di Milano.
Some techniques for using pseudorandom numbers in computer simulation
An alogorithm is described by which uniform pseudorandom integers may be used to construct binary “numbers” in which the probability that each bit in the word is a 1-bit and can assume any desired parameter value.
Techniques for making use of such “numbers” in simulation programming are described.
Simulation of traffic flows in a network
A computer simulation program which deals with traffic flows in the network of a large area is described. Each road is segmented into blocks of several ten-meter lengths and is represented by a bidirectional list in computer memory. The movement of cars, i.e. the transfer of cars from one block to the next, is expressed by a proper formula. This formula is based on the supposition that the speed of cars in a block is determined only by the density of cars in the block, and this speed-versus-density curve is empirically given the numerical values.
This simulation scheme has its excellent point in that it makes it possible to trace the dynamic behavior of traffic flows in a variety of situations, some examples of which are given for an actual area of the city of Kyoto, Japan.
Three-dimensional computer display
A stereographic display terminal has been produced using the raster display (BRAD) recently developed at Brookhaven. The system uses a rotating refresh memory to feed standard television monitors.
To produce a stereographic display the computer calculates the projected video images of an object, viewed from two separated points. The resulting video maps are stored on separate refresh bands of the rotating memory. The two output signals are connected to separate color guns of a color television monitor, thus creating a superimposed image on the screen. Optical separation is achieved by viewing the image through color filters.
The display is interactive and can be viewed by a large group of people at the same time.
A computer system for transformational grammar
A comprehensive system for transformational grammar has been designed and implemented on the IBM 360/67 computer. The system deals with the transformational model of syntax, along the lines of Chomsky's Aspects of the Theory of Syntax. The major innovations include a full, formal description of the syntax of a transformational grammar, a directed random phrase structure generator, a lexical insertion algorithm, an extended definition of analysis, and a simple problem-oriented programming language in which the algorithm for application of transformations can be expressed. In this paper we present the system as a whole, first discussing the general attitudes underlying the development of the system, then outlining the system and discussing its more important special features. References are given to papers which consider some particular aspect of the system in detail.
Automated printed circuit routing with a stepping aperture
A computer program for routing interconnections on a two-sided printed circuit board with a regular pattern of lines, pins (terminals), and vias (feed-through holes) is described.
In this program, each interconnection is given a planned routing—typically, down from the upper pin, through a via, and horizontally to the lower pin. From the top, a virtual aperture (i.e. a long horizontal slit) is stepped down the board. The planned routing is the basis for rerouting interconnections within the aperture to resolve conflicts for lines and vias below the aperture and to maximize the effective line usage. If a conflict has not been resolved before the aperture arrives at the lower pin, interconnections are deleted to resolve the conflict.
Extensions of this technique to the control of crosstalk between routed interconnections and to the problem of obtaining 100 percent interconnect are also discussed.
A note on reliable full-duplex transmission over half-duplex links
A simple procedure for achieving reliable full-duplex transmission over half-duplex links is proposed. The scheme is compared with another of the same type, which has recently been described in the literature. Finally, some comments are made on another group of related transmission procedures which have been shown to be unreliable under some circumstances.
An algorithm for solving a special class of tridiagonal systems of linear equations
An algorithm is presented for solving a system of linear equations Bu = k where B is tridiagonal and of a special form. This form arises when discretizing the equation - d/dx (p(x) du/dx) = k(x) (with appropriate boundary conditions) using central differences. It is shown that this algorithm is almost twice as fast as the Gaussian elimination method usually suggested for solving such systems. In addition, explicit formulas for the inverse and determinant of the matrix B are given.
On coordination reduction and sentence analysis
A class of coordination phenomena in natural languages is considered within the framework of transformational theory. To account for these phenomena it is proposed that certain machinery be added to the syntactic component of a transformational grammar. This machinery includes certain rule schemata, the conditions under which they are to be applied, and conditions determining the sequence of subtrees on which they are to be performed. A solution to the syntactic analysis problem for this class of grammars is outlined. Precise specification of both the generative procedure of this paper and its inverse is given in the form of LISP function definitions.
Shape the Future of Computing
ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.
Get InvolvedCommunications of the ACM (CACM) is now a fully Open Access publication.
By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.
Learn More