“On storing and changing shape information” by Braid

A data structure for modelling engineering components and assemblies is described. It is shown how the same structure, slightly extended, can also be used to represent a single component defined as boolean combinations of more primitive shapes. This leads to a unified method of handling both the concise boolean description and the longer explicit description in terms of faces, edges and vertices. The technique permits close control of evaluation from boolean to explicit description, and facilitates saving of partly evaluated results and back tracking. The data structure is built up and evaluation is controlled through a geometrical language embedded in Algol 68. The language is intended for the construction of computer-aided design systems, for simulating engineering production processes, or for any application in which shapes and changes to shapes must be recorded and manipulated.

1. Baumgart, B.G., Geometric modelling for computer vision, Stanford Artificial Intelligence Laboratory report STAN CS-74-463, (1974).
2. Braid, I.C., Lang, C.A., Computer-aided design of mechanical components with volume building bricks, proc. PROLAMAT ’73 (published as Computer Languages for Numerical Control by North Holland, Amsterdam), (1973).
3. Braid, I.C., Designing with volumes, Ph.D. Thesis, Cambridge University, England, (1974).
4. Braid, I.C., Six systems for shape design and representation – a review, proc. CAM-I Int. Seminar, Bournemouth, England, report P-75-MM-ol, pp. 60-67, (1975).
5. Braid, I.C., and Hillyard, R.C., Geometric modelling in ALGOL 68, ACM Sigplan Notices, vol. 12, no. 6, pp. 168-174, (1977).
6. Gnatz, R., Higher graphic languages. In: Nake, F. and Rosenfeld, A. (Eds.) Graphic Languages, North Holland, Amsterdam, pp 302-320, (1972).
7. Hagen T., et al, The intermediate language for pictures, Proc. IFIP ’77, (pub. North-Holland), pp. 173-178, (1977).
8. Kleene, S.C., Introduction to Metamathematics, p 334, D. Van Nostrand Inc., New York, (1952).
9. Lindsey, C.H. et al, Informal Introduction to Algol 68 (revised) North-Holland, (1976).
10. Okino, N. et al, TIPS-1: Technical information system for CAD, drawing and manufacture, proc. PROLAMAT ’73 (see above), (1973).
11. Voelcker, H.B. et al, An introduction to PADL, Report TM-22, Production Automation Project, University of Rochester, N.Y., (1974).
12. Williams, R. and Krammer, G., EX.GRAF: an extensible language including graphical operations, CGIP, vol.1, no.4, pp 317-340, (1972).