A seminar-workshop on Computer Aided Design was held in Milan on 22-24 July, 1975. It was organised by a collection of Italian 'bodies' including FAST (Federazione delle Associazioni Scientifiche e Tecniche), the Italian Chapter of ACM and various groups concerned with mechanical and electronic engineering and CAD. The organizers were hop1ing to attract an international gathering and the workshop language was English. In fact, about 90 percent of the delegates were Italian. The discussion sessions probably suffered because the majority of delegates were not sufficiently confident in the workshop language to speak from the floor. Industry was well-represented.
The topics included the structuring of interactive graphics applications, general database management systems, the representation of complex curves and surfaces, a graphic extension to APL, greyscale shading, applications (piping and highways) and 3-dimensional model cutting.
There is a copy of the workshop papers in my possession.
Herzog considered the problems of organising the programming of an interactive graphics application and described DEX (Design EXecutive) which controls interactive user commands and imposes a common style on them. DEX appears to have been designed with similar aims to PIGS, although in a different environment. His paper does not appear in the proceedings, so a slightly fuller description is given here.
DEX is designed to run on a large host computer (currently a 360 using MTS) and deals with one interactive terminal. The interactive terminal could be a satellite computer with refreshed display and lightpen (for instance a GT40), a storage tube (Tektronix 4010) or a teletype.
The application programmer describes a menu by embedding its name and list of constituent commands in the FORTRAN program, unlike PIGS where the menus are prestored on disc. In order to read the user's command selection, the application program must call a DEX subroutine MENUIN - and perform a computed GOTO. In DEX therefore, the next menu can be determined dynamically by the program; however, there are disadvantages (pointed out at the seminar) in burying the control structure in the undergrowth of the application algorithm. PIGS separates the control from the FORTRAN algorithms.
In DEX, the device at which the user is sitting determines the layout of the current menu and the method by which a command is selected. On a refreshed display, a menu of commands can be displayed in the conventional way and one can be selected with the lightpen; messages can also be displayed and easily replaced.
The storage tube presents a problem because menus and messages cannot be replaced without regenerating the application-display. In DEX, messages are just accumulated down one side of the screen and after a preset number of them the application-display is regenerated by DEX. Whenever the application program requires the user to select a command the menu-name is added to the message area with a suitable message. The menu itself is displayed in a separate area so that any item can be selected with the crosshairs; the menu is displayed either (a) as a list of command names, in which case the display is regenerated every time the menu is changed or (b) as an invariant menu which could just be a list of numbers. Herzog claims that case (b) is reasonable, since users become very familiar with an application and also HELP facilities are provided if necessary.
Teletype interaction is simple; the contents of the current menu are not typed out unless the user requests it. All that is typed automatically is a request to key in a command from menu x, where x is the menu-name.
DEX is intended to be as portable as possible; so it is written in a limited ANSI FORTRAN and environment-dependent features are isolated in a few routines viz, operating system dependence (eg time of day), file structure, graphics, character manipulation and dynamic loading (DEX can load a succession of applications itself).
These 2 lecturers both talked about general database management schemes. One of them (Bracchi) spoke in exceedingly formal English and did this for 1½ hours before lunch and with renewed vigour after. Bracchi is on pp 1-31 and Valle pp 32-41 in the proceedings.
There were various reasons put forward for using a General Database Management System (GDMS), although most of the reasons given would be satisfied by a careful design of a specialised system without incurring the excessive overhead of GDMS's. The most common factor is the user who cannot summon programming effort. A further valid reason is the possibility of restructuring the database without disturbing the application programs using it ("data independence'). Also a GDMS imposes a common structure on separate databases and encourages the integration of them; this may be a good reason in a large technical database, but has well-known dangers when it involves the general populus.
A CDMS can make provision for security, whether this be control of access or resilience to failure of the computer system.
There are notes in the workshop papers (pp 21-29) about possible storage structures (based on a CODASYL report). Bracchi felt that CODASYL has shortcomings. For instance (he said), an application cannot be implemented by a non-programmer and the implementer must specify more about the physical organisation of the data than is necessary.
Both speakers discussed the "relational" technique of managing a database. Loosely, data is thought of by the user as being in tabular form. A row of the table contains items of data which together describe an element in the database (for instance a bridge member can be stored as a row of data which includes identifying name, startpoint, endpoint, loading value). A column of the table contains items of data which are similar in type (for instance all coordinates or all textnames). One column of the table is often a set of distinct keys or identifiers each of which labels the data in its respective rows. The database ' itself consists of a number of linked tables.
Examples are given in the figures below (taken from the Proceedings).
SUBASSEMBLY
ENAME EPOS TRANF GRDEF VALUE 1 VALUE 2
ELEM1 x1,y1,z1 T1 DEF 1 10 .
. . . . . .
. . . . . .
. . . . . .
ELEM5 . T5 DEF 5 3 .
. . . . . .
. . . . . .
SUBASSEMBLY = {<ENAME, TRASF, GRDEF, VALUE 1, VALUE 2,...>}
DEF 1
X Y Z MODE TYPE
. . . . .
. . . . .
. . . . .
DEF 1 = {<X, Y, Z, MODE, TYPE, ....>}
T 1
T11 T12 T13 T14
. . . .
. . . .
T41 T42 T43 T44
T 1 = {<T11, ... T44>}
LNAME = name of a library-set of elements
GRDEF = name of the graphical definition of each element in the libraries
OBNAME = name of a set of elements present in a design layout
ASNAME = name of an assembly of elements which should be operated
upon as a single entity
TRANSF = name of the set whose n-tuples are the transformation matrices
ELNAME = name of each element in the libraries
x,y,z,w = homogeneous coordinates of a point
C = control parameter for the line starting from the given point
and ending in the following one
EPOS = coordinates of the point location where each element is positioned
TRNAME = name of a transformation matrix
t1....,
t16 = coefficients of a 4 × 4 transformation matrix
A GDMS based on the relational technique formalises this description by treating each table as a set of n-tuples. Each n-tuple corresponds to a row of the table. It turns out that most operations on a database can be expressed as set operations which can be provided in the general system.
One consequence of the relational method is that there are no pointers in the notional data structure other than those explicit in the data (in the example shown above, T1 to T5 and DEF1 to DEF5 are pointers explicit in the data). However, the actual physical storage of the data is not prescribed by the notional data structure and could include pointers if this makes data manipulation more efficient.
This speaker (Encarnacao) talked about a general system called SAD which can implement particular associative data structure systems. Using this generalised scheme, the authors have implemented DATAS (their own design), CORAL and STDS. They believe that LEAP and SAM can also be implemented using SAD.
The speakers gave a very brief introduction to the representation of complex surfaces and curves including Coons and Bezier patches. A more detailed paper by A R Forrest is in the proceedings pp 77-108.
Both speakers concentrated mainly on 3-D curves since the examples were simpler but readily extensible to surfaces. The aim is to be able to manipulate and store shapes which are of practical use to a Computer Aided Designer.
In these 2 lectures, an additional aim is that constraints imposed by a designer should be satisfied using smooth curve segments or surface patches; the result is smooth even though non-analytic. It is also possible to use building blocks like cylinders, cuboids and cones and represent a model by assembling building blocks with no regard for continuity of slope. This different technique can be applied, for instance, to the production of machine parts and is dealt with in Grayer's lecture.
A point on a 3-D curve can be represented parametrically by:
P(u) = [hx(u) hy(u) hz(u) h(u)] This curve is unknown between say u=0 and u1. It can be represented by a combination of functions thus: P(u) = [F1(u) f2(u) f3(u) f4(u)] A
where A is a 4×4 matrix of coefficients. With suitable functions fi, the coefficients can be obtained if values and slopes of P are known at u=0 and u0.
The Coons approach uses the functions u3, u2, u and 1. One problem with Coons' choice of functions is that altering the boundary conditions does not always give a predictable change in the approximated shape. One reason is that the 4 functions are not sufficiently dissimilar; in particular u2 and u3 are very similar over the interval [0,0].
Curve fitting using Bezier's method approximates specified points in the interval [0, 1] without requiring that the curve actually passes through them. Suppose the intermediate points (which we call control points) are Q1, Q2,······, Qn-1 and the end-points are Q0 and Qn. Then the curve-fitting function is effectively the sum of the points weighted by the following' (n+1) functions in u:
n ( )ui (1-u)n-i i=0,...,n i
Unlike the Coons functions, these sum to 1 over the whole interval [0,1]. This has 2 advantages viz: that the approximation will remain the same under rotation and that, if the intermediate points are in a straight line, the approximation is in a straight line.
It was found that Bezier curves do not follow polygons well. Also each of the (n+1) functions has a significant effect over the whole interval; this means that the designer cannot easily predict the effect of a small local change in a control point. It was found that if the functions were B-splines, the effect of each could be localised better. Also all the functions are the same shape as each other.
Subsequent work has used trigonometric functions (cos4 (u+i#960;/2) - Manning) or rational functions; splines have also been used to satisfy a mixture of constraints at the control points (Weilinga). Some of this recent work appears in the proceedings of a conference on "Computer Aided Geometric Design" (1974) edited by R E Barnhill and R F Riesenfeld.
Forrest's article in the seminar proceedings contains many references to what he calls "Computational Geometry" and is probably a useful place to start for anyone wanting to read about the subject.
This talk was about APL-G which is a graphic extension of APL being developed at the University of Minnesota. The paper in the seminar proceedings (pp 69-76) is a copy of a paper from the National Computer Conference 1974 (pp 521-528). APL-G is intended to be used for interactive graphics. APL was deliberately chosen as a base language because:
(1) it is interpretive and therefore names are created at run-time;
(2) arrays are primitive objects.
APL is a genuine subset and the refreshed display terminal (in a satellite computer) is implemented as a second interactive device (the other being the normal APL keyboard/printer). The extension is implemented by a set of APL functions which cause display orders to be accumulated in a special array. The list of new functions is shown in the table below.
Sancha talked about some techniques used at the CAD Centre and some applications (pipe layout and highway engineering). He showed some good slides and he also carries around with him small booklets of photographs produced by the CAD Centre, which seems a good idea if the pictures are good. The photographs are mainly taken by directly photographing a display. The CAD Centre package GREYSCALES fills in areas with lines using a notional light source and optionally using the techniques of smooth shading developed by Gouraud of the University of Utah. It was noticeable that some 'scenes' were improved by not invoking the smooth shading option; the technique occasionally narrowed the contrast between 2 faces which were adjacent on the final 2-D picture and which needed to be distinguished.
Although the CAD Centre is commissioning a raster-scan display system, GCREYSCALES is currently implemented on a PDP9/340 display, modified to draw 64 intensity levels. The picture is scanned and quite detailed pictures can be displayed acceptably by interleaving the scan lines.
Emphasis was placed on the need for the CAD Centre to produce software which is independent of (a) the company it is initially produced for and (b) the computer hardware. Point (a) arises when considering the database. Some companies have rules and requirements about (for instance) standardisation of parts. In order that the software is independent of company, such rules must be part of the data and not embedded in the programs.
Point (b) arises at an early stage because typically the CAD Centre develops and tests software on a computer system distinct from the production machine. There may be good reasons for this. The production machine may be fast for the application but not for developing software; the development machine may have good compiling systems and utilities but be poor in execution speed.
Grayer talked about building an object representation by assembling simple objects; he also talked about the cutter at Cambridge which, under computer control, cuts objects out of a soft material (like soft wood, wax, high density polyethylene and polyurethane foam). The former is described in the seminar proceedings (pp 118-149) and also in Comm ACM April, 1975 ("The Synthesis of Solids bounded by many Faces" by I C Braid); the latter is described in the seminar proceedings (pp 150-161).
The object-building system that Grayer described is that developed by Braid at Cambridge. Braid has developed a calculus for combining objects, which deals with notional objects that intersect as well as objects that simply touch. It is possible to negate an object in this system; if A* is the negation of A and if B and A intersect, then the addition of B and A* is B with a cavity in it. The negation of a complex positive object is a die for that object. The system is implemented as a set of FORTRAN subroutines or as a set of commands that can be used from a display terminal.
The idea of using a computer-controlled model-making machine arose out of dissatisfaction with 2-D output as a tool for visualising 3-D, in spite of the many visualising techniques available. Two such machines have now been built at Cambridge. They are each similar to a conventional machine-cutting tool, but they are lighter and smaller. (since only soft material need be cut) and also faster. It is designed to be fast because the machine is intended to be used by someone who is using an interactive computer and who would prefer to see his model in the same session as he directs it to be made. It is claimed that the Mark II version cuts a complicated model in about 10 minutes; it is possible to make the machine cut more slowly to obtain a smoother model. The maximum size of model that Mark II can make is 50cm #215; 35cm #215; 25cm.
Both machines can only correctly cut shapes that are single-valued with respect to the cutter axis; no complex cavities.
Mark II is controlled by a programmable chip that adds, multiplies and jumps in equal times (500ns).
Other machines of this type (but larger) exist at Renault (Professor Bezier) and NPL (at Feltham). A model-making machine developed at Technical University, Twente, Netherlands uses a hot, variable-shape wire to cut models of ship hulls.
Guedj considered which input functions to provide in an interactive graphics system. He drew material from 2 papers in the "Proceedings of the IEEE" (April 1974) "Special issue on Computer Graphics" (one by Newman and Sproull and the other by Foley and Wallace).
Useful input functions are thought to include:
These input functions are useful and at the same time not awkward to implement in a general purpose system (even the hand-written character recognizer, it is claimed).