General purpose building description systems

C. EASTMAN
(Institute of PhysicalPlanning, Carnegie-Mellon University, Pittsburgh, Pennsylvania 15213, USA)

A building description system is a database capable of describing buildings at a detail allowing design and construction.
One such system is described, BDS, that is able to represent custom-designed as well as system buildings. Attention is
given to the features distinguishing general from special-purpose building description systems, especially data-structures,
access schemes, and the method of interaction between the database and analysis programs.

(Received in final form on 8 September 1975)

Several organizations in both the UK and the USA are de-

veloping computer programs capable of describing buildings
at a detail allowing design and construction. These programs,
consisting of a large database, routines for manipulation, L Portscatalogue t
analysis and document preparation, have the potential of Analysisprograms
replacing drawings as construction contract documents.
From a machine-readable database, stored on disc or tape, Language features for
Preparation of analysis data
many reports can be cheaply and automatically prepared;
construction drawings are only one particular report format. Proiect f i l e
The potential value of such programs includes cost reduc-
Language features for
tions in the preparation of construction documents and in Element manipulation
the preparation and execution of all forms of quantitative
analyses. In addition, easier co-ordination during design
development is allowed, together with improved visual analy-
ses using computer graphic display techniques. Beyond the
advantages to design, this form of building description may
allow contractors to automatically derive parts order lists
and construction schedules; such descriptions allow and
could lead to automatic building code evaluation, and even-
tually, even the automatic fabrication of parts. I have
chosen to call such programs building description systems.
All the building description systems under development
consider a building as a large set of physical elements
arranged in space. In most cases, elements are limited to FIGURE I. Typical system organization of a building aes-
solid construction components. The task of design consists cription system
of the definition of each of the building elements and the
placement of each in three-space so as to result in a facility
with the desired performances. A building may consist of
from several thousand to a million elements. The methods
for selecting or defining the elements vary and may allow system. Examples are the SEAC system x2, the West Sussex
operations on sets of elements as well as single ones. County Council Housing system 14' is, and the OXSYS and
The usual computer system configuration used in com- HARNESS hospital building systems 8'1°. These building
posing such a description is organized as shown in Figure 1. description systems are characterized by capabilities tailored
A parts catalogue exists on some form of secondary to a particular (limited) spatial geometry, special purpose
memory, from which are retrieved descriptions of those ele- analyses programs, and the ability to manipulate only a
ments needed to design any particular building. The infor- limited vocabulary of parts. A desirable alternative would
mation in the parts catalogue includes a description of an be a general purpose building description system, capable
element's shape plus all significant attributes. The database of representing custom as well as industrialized buildings.
describing a particular building is located within a project Such a system requires at least:
file. In the project file, element descriptions are copied or 1. An open-ended catalogue of parts
indexed so as to allow as many instances of an element as
required. The project file is stored in rapid access memory. 2. Easy entry into the project file of custom fabricated
In most cases, it will be too large to reside in core memory parts
and some form of file management scheme utilizing secon-
3. Very general manipulation and drafting routines for
dary storage will be required.
operating on the database
Most building description systems have been special-
purpose, oriented towards a particular fabricated building 4. A general interface for applying analyses.

Volume 8 Number 1 January 1976 17

 C. E a s t m a n

Such a computer system could bring the benefits of build-

ing description systems to a broadened range of construc-
tion and lower the future development costs of special F v
purpose systems.
E
The philosophy for the design of general building descrip-
tion systems is quite necessarily distinct from that associated .\ F I /: / \\\1///
with special-purpose ones. In a special-purpose system all
drawing and analyses routines may be written to take advan- a b v c

tage of the common properties of the building system. In a FIGURE 2. (a-c) The vertex, edge and face retatzons defin-
general system, such a strategy is impossible. The analyses ing tbe topology of any closed polyhedral shape
and drawing programs must be completely general and all
information needed for them must reside in the database
itself. The database must incorporate information at a level
1. Concise representation of all information about an ele-
of detail necessary for any application program. Without a ment in enough detail for any form of analysis or
predefined building system, locations must be defined in a drafting
completely general way. No grid of possible locations exists
for elements. Without a grid, it is also impossible to pre- 2. Easy definition and entry of custom elements
assign storage for expected elements.
3. Easy modification of properties, including spatial proper
The level of a general purpose system is also somewhat
ties, as undertaken on-site during construction, for
different. Instead of incorporating analysis, special purpose
example, notching, drilling of holes, glueing or bonding.
arrangement and selection routines, it must instead provide
facilities for defining such programs. Thus, the system is not
necessarily the end product given to designers. Instead, a
Sbape description
firm or organiz-tion is likely to wish to add to the basic
facilities provided those extensions representing its particu-
Any shape may be considered as a polyhedron, made up of
lar methods of analysis, detailing, and design development.
vertices, edges, and faces. For our class of polyhedron,
These may require subroutines, written within the language
faces are planar but curved ones may be approximated by
of the building description system, to satisfy these needs.
multiple surfaces. The description of any polyhedron con-
The author is a member of a team currently implementing
sists of a topology of the adjacency relations between its
such a general building description system. The system is
constituent parts and a geometry specifying its dimensional
named BDS and is being developed in two versions, one on a
aspects. In most shape descriptions these two parts are not
Digital Equipment Corporation PDP-10 computer and
distinguished, but we have found a great advantage in doing
another on a PDP-1 1, at Carnegie-Mellon University. The
SO,
PDP-10 version is currently operational, whilst an extended
PDP-11 version is being implemented. Other descriptions A topology consists of the relations shown in Figure 2.
of BDS are available S,t~. This paper concentrates on database Specifically, any vertex is adjacent to an equal number (n)
design issues distinguishing general from special-purpose of edges and faces (n ~ 3); any edge is adjacent to two
buitding description systems. We have found that generality vertices and two faces; any face is adjacent to an equal
within a building description system dpeneds upon three number of edges and vertices. These relations are highly
broad considerations: redundant. If the relations in Figure 2(a) are stored
explicitly, then the relations in (b) and (c) may be derived
1. On the general but concise description of elements from them. Different operations require different subsets
2. On efficient methods for accessing elements or occasionally all of the relations shown. We have found
it expedient to store on secondary memory, a compact,
3. On a general method of interaction between the database non-redundant subset then expand it, when necessary, to
and analysis or other application programs. derive the other relations for particular operations. The
BDS compacted topology data-structure is shown in
Figure 3(a) and is sufficient for a n u m b e r of operations,
THE DESCRIPTION OF ELEMENTS particularly display (without hidden line removal). The
expanded topology is combined with the geometry, as
The elements comprising a building description may include shown in Figure 3(b).
not only hardware, but also activity areas, rooms and spaces, The geometry of a shape includes its vertex co-ordinates,
or other abstract entities having shape or other properties. edge coefficients, face coefficients and vertex angles. These
The mapping of properties between such abstract elements are also highly redundant, allowing a compacted and expand-
and building hardware is an important aspect of the design ed form. The compact form consists of a list of vertex co-
process. ordinates. The expanded version is combined with the
Considered most generally, the description of an element topology and incorporates the plane equations of each
can be defined completely in terms of its properties, where face (see Figure 3(b)).
a property is any form of measurement. Properties are A single topology may be used by a large class of build-
usually considered according to classes such as spatial, struc- ing elements. Most structural steel, for example, consists
tural, thermal and economic classes. In practice, the class of of only three different topologies: H, L, and pIate. This
spatial properties are of such concern in design to warrant commonality may be used to reduce greatly the storage
special attention and our database incorporates a special required for shape descriptions. Notice that the compacted
syntax for dealing with them. topology data-structure is related to a geometry only at the
If a building description system is to be general, the vertices where co-ordinates would normally be stored.
method of depicting elements must allow: Instead of storing the co-ordinates within this data-structure,

18 COMPUTER AIDED DESIGN

General purpose building description systems
Body Before describing the methods used in defining and
operating on standard or custom shapes, the storage of ele-

t
P o t t e r n size I
Number of faces Face list
ment attributes is described, which in the BDS implementa-
Numb. ofvertieesJ I I t l I I tion relies on common facilities with the geometry.

Adjacent face
,ve.,o.oo,o,.., 1 I I I Element attributes
II

All non-shape element information in BDS is stored as

attributes. In design, information becomes articulated
Body record
incrementally. It would be quite unnatural and inconvenient
Next body
to require a user to specify at the time an element is first
Vertex pointer
defined all the attributes needed in its future. Rather, the
Face pointer

Number of vertices
attribute description should be extensible, which is pre-
Number of faces ~__ Facerecord cluded by a fixed format. Attributes are treated in BDS as
if they are variable-value pairs in a high level language. As in
Body identifier Next foce

Length of record Edge ring m that case, an attribute consists of a name, a value, and a
Data type (in FORTRAN, types include INTEGER, BOOLEAN,
M i n i . - max COMPLEX, etc). Attributes are assumed to be vectors,
< envelope
dote

L
f ace
oefficients

Face identifier
each entry denoted by a subscript. If no range is specified,
the default value is one. A general structure for attributes
is to store the triplets in list form, as shown in Figure 5.
At least four attribute types are justified for describing
element properties: NUMBER (real), CHARACTER (string),
I Edgerecord SET and FUNCTION. All attribute names are coded and
I Next edge stored in a directory. If the type is CHARACTER, the
Vertexpointer directory stores, with a name, all the values that have been
Opposite face assigned for it in a variable length list format and their
Edge twin ordinal value is used as a code. NUMBER values are not
coded, but stored directly in the list. SETS also take
Vertex record characters as values, but have the additional feature of in-
Next vertex corporating an inverted file which points to all elements
having a particular attribute value. FUNCTIONS take as
Coordinates values expressions, allowing computation of their value
each time they are called. These four formats are coded in
V e r t e x identifier the attribute directory.
Data Two example uses of the SET attribute are to store the
b names of manufacturers from which elements are purchased
FIGURE 3. (a) The compacted topology data-structure; and the element specifications. In both cases, the inverted
(b) The expanded shape data-structure file is useful in collecting all elements for later listing or for
operation on a group of elements: in the first case for parts
ordering, in the second for control of the construction pro-
it is equally straightforward to store an index into an cess. An example of the use of FUNCTION is in the storing
ordered set of co-ordinate values. Different geometries may of an element's weight, when its length is expected to vary
be used by one topology simply by changing the base
address associated with the index. Thus a distinct geometry
may exist for doors, bricks, wood timber, and clay tiles,
each using a common (in this case rectangular) topology. 5
The topology and geometry together describe a shape in
local co-ordinates. As many instances of this shape may be
used as needed by storing for each instance a spatial trans-
form consisting of the three co-ordinates and three angles
defining any relative location. Together, the topology,
2
geometry and location define a three level hierarchy, as I I
--I
shown in Figure 4. At each level exists a one-many map-
ping. One topology may be used by many geometries, one xl = x 2 = z l =z4 = c o x I =x2=z 1 =z 4 : oo
x3--x4= 80
x 3 = x 4 = z 2 = z 3 = 50
Z2~Z3=60
geometry by many locations, thus allowing a large number x 5 z 5 = 25 x s = 40: z 5 = 30
Yl : Y2 = Y3 Y4 = 00
of shapes to be concisely described. In practice, we have Y5 : 50 Yl V2 = Y3
Y5 = 142
= Y4 = 0

been able to extend this structure to allow some geometry L ~

L O C A ~
information to reside at the location level. Many building
elements are extruded; they have a common section but
arbitrary length. By altering geometry information in sys-
tematic ways before applying the spatial transformation,
each location can also incorporate a unique shape, further
reducing the number of geometries needed to describe any FIGURE 4. Tbe three level hierarchy of tbe BDS data-
element (see section on storing geometries and attributes). structure

Volume 8 Number 1 January 1976 19

 C. Eastman

Attribute I Sub-directory Attribute I I

F directory index index directory index I Real I value
I I
I , i I
~. 2k )
W" Y
Character, Number
set or function
FIGURE 5. The organization of attributes within the BDS form record, The attribute directory stores names, a type code, and
for values of type CHAR, tbe possible values

from location to location. These four attribute types provide be specified during definition by the user or default values
the storage capabilities needed for most analyses and book assigned by the system. In the case of default values, the
keeping operations. subscripts are the integers next larger t h a n the largest
assigned thus far.

Storing g e o m e t r i e s and attributes

DEFINITION OF ELEMENT INFORMA TION
The overall scheme for storing element information in BDS
is shown in Figure 6. All element structures are accessible The topology and form files describing standard building
through a common directory. The geometry, attributes, components can be stored within a parts catalogue, accessed
and location information are all stored on a single record, and associated with locations as needed. However. for the
called a form file. user definition of custom elements, operations must be avail-
The co-ordinates defining a geometry are derived by a set able which allow the efficient definition of any desired
of pointers, one for each vertex co-ordinate. The geometry topology and geometry.
values stored at the location level are derived by transferring
them to the address required by the vertex co-ordinate
pointers. Thus, information at the location level can be used T o p o l o g y definition
in deriving a shape at little computational cost.
In order to speed the accessing of information needed to While the data-structures shown in Figure 3 hold the infor-
describe information about an element, the co-ordinates mation needed to completely describe a topology, a method
and attributes are stored at one end of a form disc file, and for entering them is required. A general mechanism for con-
information on instance locations is added at the other. structing topologies may be derived from Euler's proof of
Attribute information and new locations make use of the the theorem:
common available space between the two ends. In case the
file becomes full, location information is moved to a second vertices edges + faces = (2 x bodies) (2 x holes).
file adjacent to the first. Multiple files of locations may be
linked to a form. Euler's proof was based on showing that any polyhedron
Linkages through the database hierarchy are available can be constructed using a set of operators, each of which
both from top-to-bottom and bottom-to-top. The directory is consistent with the equation (see Figure 7). These
stores top-to-bottom linkages to facilitate deletions. The operators provide a set of primitive actions sufficient to con-
data blocks store bottom-to-top linkages to facilitate the struct or alter any topology without side effects or special
computation of shape information. cases. Each of the operators shown in Figure 7 has been
Elements are accessed by name, using a form name and a incorporated within BDS to operate on the expanded data-
subscript denoting an instance location. The subscripts may structure, see Figure 3(b). Their implementation is des-
cribed in detail by Stoker 13. All operations for constructing
and modifying shape topologies are done with these pnmi-
DIRECTORY TOPOLOGY TEMPLATE
twes. In our implementation, topologies may be buik-up
Header
either by interactively calling the different Euler operators
Pattern
enlry 1
with appropriate arguments or by sketching in the topology
on a digitizer tablet. Credit for the first use of the Euler
Expression
entry 1 operators for constructing topologies goes to Baumgart ~
E~pression
entry 2

Template Form definition

entry 1

Template
entry 2 The form consists of the shape geometry and all attributes.
Template
Each attribute consists of a declaration and an assignment,
en~ry 3 the assignment being local to a particular form record.
Sel The geometry information, entered as vertex co-ordinates,
entrv A
is highly regular. If a shape is a rectangle, for example, then
FIGURE 6. The overall structure of element information half the x, y, and z co-ordinate values each have some value
within tbe BDS database and half the values are zero (if sides are parallel to the co-

20 COMPUTER AIDED DESIGN

General purpose building description systems

custom-made elements can be described in terms of some

Equation
Operation (faces) - (edges) + (vertices) = (2*objects) (2*holes) combination of simpler shapes. It is most advantageous,
then, to incorporate operators allowing shape modification
Construct similar to those i m p l e m e n t e d by Braid z.
edge and One set of formally defined operators that achieve these
vertex +1 +1
ends are the spatial set operators of union, intersection, and
Construct complement. The intersection is useful in identifying spatial
face and
edge +1 +1 conflicts, the union in glueing elements together. The
notching or drilling can be treated as a subtraction, which
Construct is derived using the c o m p l e m e n t and intersection operators,
object and
face, des- specifically A fq B.
troy edge +1 --1 +2"1 The union and intersection operations can derive a new
Split an element with faces, edges and vertices that do not exist in
edge with either of the elements which are the arguments. Thus, both
a vertex +1 +1 a new t o p o l o g y and g e o m e t r y are created. Algorithms for
Divide an the set operations are being i m p l e m e n t e d in BDS.
object The Euler operations, subroutines for defining f o r m in-
with a f o r m a t i o n and the shape operators together provide a
plane +2 +2"1 p o w e r f u l range of tools for defining e l e m e n t information.
Fuse two In addition, though, a user needs efficient means to locate
objects and large numbers of standard and c u s t o m defined elements
remove the
t h r o u g h o u t a building project. This is facilitated by the
common
faces -2 -2"1 location operations and group naming.

Remove
two faces
and con-
struct a
hole -2 +2"1

FIGURE 7. The operations derived from Euler's equation

for manipulating shape topologies

v3

ordinates and the origin is at one corner). A rectangle should

be defined with only three values. Similarly, the f o r m a t for v1~ v2o ~
most catalogues of building products is to provide a graphic v s ~ vz4 / ~ 9 1
description of the shape and o t h e r properties of the general
line of products, and then a table illustrating the variations
within that line.
We can consider the concept 'rectangle' as a model geo-
metry, which defines consistent dimensional relations
within a family of shapes. The geometric properties of a
building product, as defined in the drawings within a vendor's
catalogue, may also be considered a m o d e l geometry. In
b o t h cases, the model g e o m e t r y is easily defined by a set of
algebraic expressions, stored as a subroutine. The subroutine
defines all co-ordinates in terms of a set o f critical variables,
passed as its arguments. Different members f r o m a family
FIGURE 8. A subroutine capable of generating the geo-
of shapes can be easily entered, either by a user interactively
metr~ of any standard wideflange beam from its five critical
dimensions. All non-assigned subscripts bare a default value
calling a subroutine or by naming a table in a parts catalogue
which correspond to the tables in a vendor's catalogue and
Oflzero
applying these parameters to the subroutine (see Figure 8). S U B R O U T I N E W I D E F L A N G E (AI, A2, A 3 , / t 4 , A5)
The subroutine can also declare and assign attributes.
We have also i m p l e m e n t e d programs allowing a user to x 3 =x4=x9=xlo=Xll ~x12=x17=x18=x19=x20 =
draw in shapes on a large digitizer tablet 9. In practice, then,
a user may enter g e o m e t r y information manually, call a sub- x23 = x24 = A 5
routine which defines a class of shapes a n d / o r attributes, or
Y13 = Y14 = Yl 5 = Y16 = Y17 = Y18 = Y19 = Y20 = A 3
enter it graphically.
Ys=Y6=Y7=Ys=Y9=YlO=Yll=Yl2=A 1- A 3
z7=zlo=Z15=z18 = ( A 2 - A4)/2.0
Interactive shape m o d i f i c a t i o n
z 6 = Zll = z14 = z19 = (A 2 + A4)/2.0
Many prefabricated parts are modified on the building site
Zl = z4 = z5 = z12 -'- z13 = z20 = z21 = z24 = A2
by bonding, notching, drilling, etc. In addition, m a n y

Volume 8 Number 1 January 1976 21

 (2. Eastman

Location definition The binding sequence found optimal for pre-stored ele-
ments is shown in Figure 9. Predefined elements are stored
Locating any element requires the definition of six numbers, in a parts catalogue in terms of topologies, subroutines, and
placing the element relative to all others. A location may values. The values are stored in tabular form. When selec-
be specified in the common world co-ordinates or in the co- ted for a project file, the routine and values are combined to
ordinate scheme of other located element. An asterisk (*) derive the constant shape dimensions and attributes collected
prior to a location indicates !world' co-ordinates, an element in the form file. New attributes may be added, if desired,
name denotes the element whose co-ordinate system is at either the form or location levelsl In core, two alterna-
desired. For example, if D O O R ( l ) i s located at *, tive representations are available, the compacted topology
100, 100, 100, O, 0, 0, then the locations defined by * which accesses vertex co-ordinates or the expanded shape
200, 150, 100, 0, 0, Oand DOOR(l), 100, 50, 0, 0, 0, 0, definition of Figure 3(b).
are equivalent. Trailing zeros need not be entered. To facilitate definition of custom elements, a number of
The locations of elements in most buildings are highly topologies and subroutines are prestored and can be modi-
regular. Many beams, columns, panels, etc, vary in location fied by the user. A user may also interactively enter his own.
from one another by a simple transformation. After placing Subroutines are initially simply typed and stored, for later
a single element, copies are easily defined using the relevant parsing and evaluation within the BDS user language. For
transformation. Also, the transformation can be iterated user defined elements, the user must enter all attribute and
from the last placed element a specified number of times. geometry information, plus the location of instances.
Thus; In use, most of these processes within BDS are trans-
parent to the user. In simply naming an element, all infor-
ITERATE DOOR(2) BY 48, 0, 0 *4 mation depicting it is automatically combined.

generates four copies of DOOR(2), each offset 48 units

from the previous one. DISPLA Y OPE RA TIONS
Sometimes, a user wishes to place not merely single ele-
ments, but collections of them, all in a consistent relative A building description system can be viewed as a Large infor-
placement to one another. BDS provides a group naming mation system encompassing database, routines for enter-
facility by which a collection of located elements are ing and editing the database contents, and report generating
assigned a single name and origin. All location operations, facilities, Drawings can be viewed as reports in particular
including the iterative ones, apply to groups as well as to graphic formats. In building design, a variety of graphic
single elements. formats are in common use and most of these have been
incorporated within BDS.
To-date, we have implemented perspective and ortho-
BINDINGS OF E L E M E N T I N F O R M A TION graphic projections, with the option of sectioning: Multiple
displays using these facilities are shown in Figure 10, which
The storage efficiencies gained by the three level hierarchy were derived from a database describing a smalI vacation
impose added computation cost every time an element is cabin designed for northern California. These displays are
examined or operated on. The tasks involved are the deriva- generated by defining a view in terms of a viewpoint and
tion of element co-ordinates and their link with the viewing line (with option cone of vision and orthographic
topology. Sequentially, the BDS database requires the fol- perspective, axiometric and sectioning options), and the set
lowing computations: of elements to be displayed.
The graphics in Figure t0 all come from the display
1. Applying the appropriate arguments to the subroutine
screen associated with the BDS hardware N. A link to repro
describing the fixed geometry and attributes of the ele-
duce them on a plotter is also available. Many refinements
ment class and executing that routine are planned, including automatic dimensioning, hidden line
2. Binding the values of the attributes and co-ordinates removal and shaded surface (raster scan) displays.
which individually vary for this element, stored at the
location level
SPA TIAL SEA RCH
3. Transforming the derived co-ordinates to their location
within world co-ordinates The retrieval method for any part of the hierarchical data-
4. Linking these co-ordinates to the appropriate topology. structure is through the project file directory. Elements

These computations may be undertaken in three different

Component Project Load m Just prior
stages, when information is: library file core to execution

1. Moved from the parts catalogue to project file

Topology - - -- Tot)olo0v
2. From project file into core
3. Just prior to computation.
fJe~,~~tqy - 1
Information is taken only once from the catalogue; it is
loaded into core many times; while in core it may be
operated on several times. Thus, each later stage change L¢~cation ~

occurs more often than earlier ones and binding done at the FIGURE 9. The sequence o f computations leading to the
later ones must be iterated more often. Conversely, binding definition o f a single element. This sequence resutts in fast
late minimizes the storage of intermediate values. instantiation and small storage requirements

22 COMPUTER AIDED DESIGN

General purpose building description systems

in

. . . .

II
FIGURE I0. (a-l) Views of a small vacation cabin showing the facilities of perspective and ortbographic projections.
(a-c) show perspective views; (d-f) are framing plans and sections; (g-j) are inside perspectives; (k) and (l) are site perspectives

Volume 8 Number 1 January 1976 23

 C Eastman

with identical properties are accessed through the set attri- A------~
butes. A typical requirement for c.a.d, systems, though, is B --'
to access collections of spatially related elements. This D - -

involves finding all elements within the data-structure which, G

when transformed into world co-ordinates, occupy or spa-
dally conflict with a specified volume of space. None of the
structures described thus far collects elements which are
spatially related and an exhaustive search would be
prohibitive.
Accessing element information spatially in an acceptable jF je
amount of time necessitates elimination without inspection
40.35
of as many elements as possible which might prove to be . Ijoo _
completely disjoint from the search volume. A preliminary
search, based on element envelopes, can eliminate all but a
set small enough to be tested exhaustively. By an envelope
is meant the minimal rectangle enclosing an element, with
the rectangle's faces parallel to the co-ordinate axes.
I
x~llO.O
Rather than attempt to superimpose on the hierarchical
data-structure an accessing mechanism which would allow x;,[40.55 A
this search, we instead manage element allocations within
secondary storage on a spatial basis and set up a tree struc- Y;=39.45
ture for accesses (see Figure 1 l(a)). This organization for
making spatial searches was first used in the CEDAR pro- a
ject 12. The organization used in BDS is a modification
which has been optimized in order to involve fewer disc
accesses and envelope tests.
The envelopes of elements are initially located together I START I
within a single area of secondary store, called a bucket. A
bucket stores a fixed number of elements corresponding to
a rectangular envelope enclosing all elements with it. When P+-T;I+-O;J~--O:I/+-O.O;INDEX
<- O; I
a bucket becomes full, the envelope co-ordinates of the
elements within it can be ordered in each dimension. By
applying the algorithm sketched in Figure 11 to the three i

orderings of co-ordinates, the one planar partition of the INDEX ~ INDEX + t" I
rectangular volume can be identified, which produces two ..._1
approximately equal sets of elements and also overlaps with
the most elements. Those elements which do overlap are "-It
allocated to a third bucket. As this partitioning takes place IF (J ;~ 7"/2 + or) THEN EXIT;
the access tree is modified accordingly. Within this structure
a spatial search involves scanning the search tree to identify
½
all those buckets overlapping the volume of interest. It is IF COORD (INDEX, SIDE)
then necessary to test exhaustively the elements within =")°" THEN (/*-- I + 1;J*.-J+ 1)
these buckets for conflicts. We have also found that rather ELSE i + - / - 1;
large buckets are more efficient than small ones. We
achieve this by using multiple adjacent disc sectors for a
single bucket.
The maximum size of an element within a bucket cannot IF (J~> T/2 - or) THEN IF
be larger than the dimensions defining the bucket's spatial I < P THEN (I *- P; II *-
boundaries. Also, all segments in the tree below some node (COORD (INDEX, VALUE) +
must have elements smaller than the node size. This acces- (X)ORD (INDEX + 1, VALUE))/2
sing scheme thus also proves useful in selecting elements by
size for display. This organization and search scheme is fully
described elsewhere 4. b

APPLICA TION PR OGRAMS

F I G U R E 11. The partitioning atgoritbm f o r splitting a disc
As described thus far, any design information system can be sector into multiple sectors as t h e y b e c o m e full, and the
viewed as a large, information system encompassing a data- search tree thus generated. (a) building partition; (b) algo-
base, aset of routines for editing this database, and report- rithm
ing facilities. Designing isthe building-up and editing of C o o r d i n a t e description
the database; drafting is the preparation of a report in a COORD (VALUE, INDEX, SIZE) where
particular graphic format. But design decisions derive from VALUE : : = real n u m b e r
a number of considerations requiring analyses and an effec- I N D E X : : = integer betv~een 0 and T
tive system must deal with the problem of interfacing with T . • = element capacity o f block
analyses programs. SIDE : : = < ( > f o r m i n i m u m and < ) > f o r m a x i m u m

24 COMPUTER AIDED DESIGN

General purpose building description systems

We have found justification for considering application numerical computations involved in database manipulation
and analysis programs as being of two distinct types. Some and the emphasis on high-speed but inexpensive interaction,
applications involve only simple arithmetic to aggregate a minicomputer configuration was chosen (see Figure 12).
data, but must follow precise sequences. Applications of The project file resides on high speed disc memory. In our
this sort include the sizing of most distribution systems and implementation, numerically oriented analyses can be expe-
material and cost take-offs. The major task here is data dited by shipping data to a remote timesharing facility,
organization. Execution of an environment intimately linked which also stores the parts catalogue. BDS is implemented
to the database is likely to be most efficient. Other forms in the BLISS system building language, which produces
of application programs will rely on extensive external data highly optimized code incorporating direct address
and decisions will be based on a large number of variables manipulation 3.
evaluated simultaneously. For this class, computation in Using the storage scheme described, the memory required
an environment with very fast arithmetic capabilities of to store building projects of different sizes depends on the
high accuracy is justified, which may or may not be the project's regularity and the manner in which the user
hardware environment of the database. This second type of chooses to define it. In general, we estimate that about five
application is exampled by structural and thermal transfer million characters of disc space will allow project files
analyses. holding 50 000 elements; 500 000 elements can probably
For both types of applications, we are implementing be described in 40 million characters. Thus even the most
within BDS language facilities for computing new proper- complex custom designed project should adequately reside
ties which are functions of existing ones and routines for on a disc pack.
formatting new or existing data on files. For the type of A preliminary version of BDS is operational. It provides
application relying on large amounts of information in the initial operating speed benchmarks. The necessary computa-
database, the language incorporates mathematical opera- tions for instantiating an element requires three disc accesses.
tions allowing, for example, summation of volumes, the sum With our hardware, we are able to instantiate seven dif-
mation of lengths of a particular class of element or the ferent geometries per second, for example, those elements
number of elements. For the second type of application, based on different forms.
the functions that can be computed include; mass, contact
area between two elements, topological relations over a set
of elements (that is, the mechanical or structural elements), C ONCL USION
or the volume enclosed by a set of elements. The features
of this language are presented in a separate report'( BDS provides a model for general building description sys-
The philosophy of BDS is that all information initially tems capable of dealing with any industrialized building
entered can only concern discrete elements. Properties over system as well as the most custom designed of architecture.
a set of elements, derived by their adjacency, connection or It incorporates features for entering, manipulating, display-
other relationship must be computed. After computing, ing, drafting, and analyzing most building designs. While
these relationships between elements may be stored, either
in one of the record types already defined or on a new file
to be read by an application program. Our analysis has To PDP-IO
shown that the attribute storing facilities provided are ade-
quate for the non-spatial properties of elements or collec-
tions of elements. The problem areas are the computation
of information which are functions of shape, such as pivot
points of joints or contact areas of thermal transfer between
materials, and the derivation of topological structures.
The language features are only now being implemented.
It is too early to determine their strengths or limitations.
Most likely, they will allow the writing of subroutines
capable of interfacing many application programs with a
BDS-type database. In some cases, though, we expect that
the user will need to provide input that corresponds to the
engineering judgment required in the data preparation of
analyses programs.

IMPLEMENTATION

Effective man-machine manipulation of a large database

requires high rates of information transfer, particularly to
achieve effective graphical interaction. In our assessment,
this criterion prohibits the use of voice grade lines anywhere
between the database and the display terminal. Both high
speed time-sharing and satellite minicomputers can provide
the needed computational capabilities. The concepts
developed here rely heavily on information management.
Only the spatial transformations, set operations, and display
routines use real arithmetic; most processing consists of FIGURE 12. Hardware configuration used in the BDS
address manipulation. Because of the limited amount of implementation

Volume 8 Number 1 January 1976 2b

 c Eastman

this paper focuses on database considerations, other facets 5 Eastman, C. 'The use of computers instead of drawmgs in
of a building description system must receive careful scrutiny building design' Amer. Inst. of Arcbitects J., (March 1975 )
pp 4 6 - 5 0
if such systems are ever to receive widespread application.
6 Eastman, C., Lividini, J., Stoker, D, "A database for designing
Current work on BDS focuses on the development of the large physical systems' Proceedings 1975 National Computer
database operations into a convenient and powerful high Conference, Anaheim, California, USA
level language. Hierarchical replacement and other opera- 7 Eastman. C. and Henrion, M. "Language features for a design
tions that directly facilitate the development of a design as information system' Institute of Physical Planning Research
Report, Carnegie-Mellon University, Pittsburgh, Pennsylvania,
it moves through the traditional sequence of schematic, USA (September 1975)
preliminary and detail development are also being explored. 8 Hoskins. E. M 'Computer aids in building', in Computer
BDS is being developed by a team of researchers at the Aided Design, J. J. Vlietstra and R. F. Wielinga (Eds.) Amer-
Institute of Physical Planning at Carnegie-Mellon University. ican Elsevier, New York (1973)
9 Lafue, Gilles, 'Computer recognition of three-dimensional
The team includes Adrian Baer, Marsha Berger, Henry Finch,
objects from orthographic views'. Institute of Physical Plan-
Max Henrion, Gilles Lafue, Joseph Lividini and Douglas ning, Carnegie-Mellon University, Research Report No 56,
Stoker, in addition to the author. This research is supported (September 1975 )
by the National Science Foundation and is part of the 10 Meager. M A. The application of computer aids to hospital
research program in Advanced Building Studies. building Computer Aided Design, J. Vlietstra and R. Wielinga
(Eds.) American Elsevier, New York (1973)
11 Rosen, B. 'The architecture of a high-performance graphic
BIBLIOGRAPHY display terminal' Int. Society for Information Display Digest.
1 Baumgart, B. 'Winged edge polyhedron representation' (May 1973), New York
Stanford A. 1, Project Report AIM-179, (October 1972) 12 Sampson, P. 'The implementation of CEDAR: a computer-
Stanford University aided building design system'. Unpublished report, Design
2 Braid, 1. 'The synthesis of solids bounded by many faces' Group, Royal College of Art, London. (August 1973)
Commun. of the ACM Vol 18, No 4, (April 1974) pp 2 0 9 - 13 Stoker, D., 'The CRIPL-EDGE data-sttucture', Institute of
216 Physical Planning, Carnegie-Mellon University, (May 1974)
3 Digital Equipment Corporation, BLISS-11 Programmers 14 Walter, P. E. 'Computer graphics used in architectural design
Manual Computer Science Department, Carnegie-Mellon and costing' in Computer Gmpbics, R. D. Parslow, Prowse,
University, Pittsburgh, Pennsylvania 15213. and Green (Eds.) Plenum Press, London
4 Eastman, C., and Lividini, J. 'Spatial search', Institute of 15 Paterson, J. W. 'An integrated c.a.d, system for an architects
Physical Planning Research Report, No 55 Carnegie-Mellon department' Comput. Aided. Des. Vol 6 No 1 (January 1974)
University, (September 1974) pp 25-31

the international journal of the Science Polmy Foundation

current awareness for busy people in

SCIENCE & PUBLIC POLICY The information is gathered through a worldwide network of
national correspondents who are intimately involved in research-
provides information on national policies for science and
ing and applying science and public policy in their country.
technology and their effects
Subscription £25,00 (S65.00) per year ( t 2 issues} including post-
examines the roles of science and technology in the opera-
age by fastest route, A special annual rate of £10:00 ($26.00)
t ions of government (local, nat ional and inter national),
is available for the individual who certifies that the copies are
industry and business
for his/her personal use and who is the full-time employee of a
analyses the social and political environments within which current full-price establishment subscriber at the same address.
science and technology operate
assessesappropriate methodologies, information systems
and organisational forms IPCBusinessPressLtd, Oakfield House,Perrymount Road,
explores various types of public participation and their Haywards Heath,Sussex,England
influence on national and international policies
The journal contains short, pithy news items, concise reports, Published monthly by IPC Science and Technology PresSL i d :
comment, commissioned reviews, facts in figures, book reviews publL~her~ of FUTURES. ENERGY POL IC Y and RESOURCES
and extensive bibliographies. POLICY.

26 COMPUTER AIDED DESIGN