Understanding the Preparation and Analysis of Solid Models

Published in Techniques for Computer Graphics D. F. Rogers, R. A. Earnshaw editors, Springer-Verlag, 1987

Please read the Postscript Version which contains all the figures.

.\" groff -X -tepRs -ms solid-models
.\" groff -tepRs -ms solid-models | print-postscript
.\"
.\" Commands for grefer style selection
.\" label "A1.n.u D.y-2"
.R1
accumulate
sort
database ../bib
label-in-text
move-punctuation
bracket-label " [" ] ", "
label K
.R2
.\" Actual text
.EQ
delim $$
.EN
.\"gsize 24
.RP
.TL
UNDERSTANDING
.br
THE PREPARATION AND ANALYSIS OF
.br
SOLID MODELS
.AU
Michael John Muuss
.AI
Leader, Advanced Computer Systems Team
U. S. Army Ballistic Research Laboratory
Aberdeen Proving Ground
Maryland 21005-5066 USA
.AB
.LP
The origins and basic principles of solid modeling
will be reviewed.
Topics to be covered include a detailed look at the
primitive solids and their mathematical descriptions, a review of
boolean mathematics for solids combination, and the use of homogeneous
coordinates for object positioning.
References to various existing solid
modeling systems will be given.
.LP
As a case study of a modern solid modeling system,
the U. S. Army Ballistic Research
Laboratory's (BRL) solid modeling system will be described.
In addition to an
overview of the constructive solid modeling based geometric design
editor's (MGED) features and operations, examples of constructing objects
using MGED will be presented.
MGED's capabilities, command interface,
code organization and internal editing states will be discussed.
Important considerations in preparing and organizing large models
will be presented.
.LP
A detailed investigation of the algorithms needed to
ray-trace a solids model will be presented.
The mathematics of ray-solid
intersection will be shown for three primitive solids.
Bounding
volumes will be discussed, along with boolean expression tree evaluation.
The general data structures, code organization, and space partitioning
algorithms of BRL's ray tracing package (RT) will be reviewed, and a sample
application will be given.
.LP
An overview of how ray-tracing of solids
models can be applied to compute information about the
properties of the structure being modeled will be given.
Image rendering, property calculations, and
specific engineering assessments will be examined.
.AE
.RT
.NH 1
Origins and Principles of Solid Modeling
.NH 2
Brief history of design
.PP
When prehistoric man began fashioning tools and adapting his
surroundings to suit him, the history of design began.
Driven by his desires, prehistoric man made plans in the form of
ideas and mental images.
Whether the implementation of these plans was successful or unsuccessful,
the plan and goal remained as private mental images, locked within
the mind of the individual.
.PP
The limitations of this elegant and simple design process
were reached when prehistoric man encountered
a stone or tree too massive to be dealt with by a single individual.
A new dimension was introduced as he attempted to
share his ideas and goals with his peers, and organize their aid.
Most likely he communicated his ideas by arranging small stones and sticks
to form a miniature representation of the initial state of things,
and then to manually manipulate his model step by step
(no doubt accompanied by grunts, wild gestures, and significant glances)
until the desired final configuration was achieved.
Then the group went off to implement the plan in full scale.
Variations of this design metholodogy persist into the present.
.PP
As evolution progressed and the fashionings of man became more
and more complex, the necessity for constructing a physical model
to communicate ideas grew cumbersome.  Detailed models could require
substantial effort to construct, and could be difficult to transport.
The time required to construct a model might be a substantial fraction
of the time to construct the actual object.
Furthermore, insight into the construction process could be
difficult without disassembling and reassembling the model.
Considerations such as these motivated the next level of abstraction:
the drawing.  The first drawings were probably simple
scratchings in earth or sand, depicting the outlines of the
objects involved:  a two-dimensional wireframe.
.PP
With the passage of time, drawings evolved beyond simple engineering
representations into recordings of significant events, and art.
Drawings were enhanced with color and shading in an attempt to
more accurately convey the three dimensional nature of reality.
As the field of engineering progressed further, draftsmen
began explicitly providing indications of the three dimensional
nature of their subjects by representing hidden and false edges
as light or broken lines,
.[
Requicha Historical Summary
.]
such as in Figure 1.1.
Subsequent to this development,
drafting advanced very little, and has persisted nearly unchanged
up to the present.
.KF
.PS
scale=250
box invis ht 340 wid 656 with .sw at 0,0
line  from 240,142 to 648,142
arc from 240,336 to 144,240 at 240,240
arc from 144,236 to 240,144 at 240,240
line  from 240,336 to 648,336
line  from 648,336 to 544,232
line  from 648,336 to 648,144
line  from 544,40 to 648,144
line  from 544,232 to 544,40
line  from 136,232 to 544,232
arc from 136,40 to 232,136 at 136,136
arc from 232,136 to 136,232 at 136,136
line  from 136,40 to 544,40
line  from 164,28 to 204,68 dotted
line  from 28,164 to 172,308 dotted
circle rad 96 at 96,96
.PE
.ce
\fBFigure 1.1 \(em Wireframe Ambiguity\fR
.KE
.PP
The digital computer provides the opportunity for nearly infinite
variety in the representation of information within it.
Improving the design of complex, expensive objects
is always an area ripe for technological improvements,
and with the emergence of graphics displays, computer aided
design (CAD) packages began to appear.
Designers of early CAD packages focused their efforts on the most
tedious, time-consuming, and unrewarding aspect of conventional design:
the process of converting a designer's sketches and notes into
finished engineering drawings suitable for use by a manufacturing
facility \(em the drafting proces.
Thus, while computers offered the ability to create arbitrarily
powerful
mathematical representations for objects, initial CAD systems
replicated traditional two-dimensional drafting techniques.
Only modest gains in efficiency were made in creating
the first version of a design,
but tremendous gains were made when design modifications were needed,
because the computer retains and redraws the unchanged portions of
the drawing.
.PP
Once a computer aided drafting system has been used to create a
computer representation of a design,
the designer (and his management)
is often tempted to expect more out of the computer
system than simply drawings.  One would expect that a representation
that depicted the boundaries of an object from several views
would provide sufficient information for computing a whole
variety of useful facts about the model, such as center of mass,
volume, cross-sectional area, etc.
Two-dimensional drafting systems were poorly prepared for this
sort of interrogation.  With the addition of appropriate connectivity
and material property information, these capabilities
became possible, giving rise to 2.5-dimensional drafting systems,
which are frequently called 3-dimensional wireframe systems.
For limited analysis, 2.5-dimensional models may provide all the
required information.
.PP
Four major types of difficulties have plagued wireframe systems.
First, the user is required to supply a large amount of information,
often at a very low level.
Because of the drafting heritage, some of
this information may be ``construction lines'' that do not actually
contribute to the ultimate shape of any object.
Second, because the user is providing such low-level information,
objects can easily be defined
which can not be physically realized due to
non-closed faces and dangling lines.
Third, it is possible to construct a wireframe which might represent
several different solid objects;  additional information is needed to
disambiguate the description.
Finally, wireframe models may include
lines representing false edges such as profile lines and silhouettes,
leading to ambiguous interpretations.
.[
Requicha historical summary
.]
These issues have driven the refinement of drafting-type systems,
but have also focused attention on the quiet evolution
of an entirely different approach
to representing objects:  solid models.
.NH 2
What is a solid model?
.PP
A solid model is
a computer description of closed, solid, three-dimensional shapes
represented by  an analytical framework within which the three-dimensional
material can be completely and unambiguously defined.
.[
Deitz improved acquisition
.]
Solid models differ from drafting-type systems in several
important ways:
objects are composed of combinations of primitive objects (some quite
complex), each of which is complete, unambiguous,
physically realizable, and modifiable.
Because these properties hold for the primitive objects, they hold
for any boolean combinations as well.
.PP
Completeness is assured because the
representation contains a full description of a piece of solid matter;
there is no view-specific information.
Because the solid matter is completely described, there
is no possibility for ambiguity.
For primitive solids defined by specifying parameters to an analytic
function, there is no possibility of having missing faces, loose edges, or
other similar defects.
Systems which offer boundary representations as primitive solids
must carefully validate each such solid when it is created.
Because solid modeling systems generally do not attempt to compute
an exact analytic representation of the surfaces of all the objects,
but instead derive the actual surfaces by evaluating the boolean combination
expressions in the model interrogation
process (such as by ray-tracing), a solid model is
always amenable to further modification by boolean combination with
other shapes.
.PP
These properties guarantee that
all the spatial information necessary for any
subsequent analysis is directly available from the model representation.
Object structure and material properties can be computed
at any arbitrary point in the model
or along all points of an arbitrary directed ray
at any time.
Therefore, solid modeling technology is particularly suited to the
automation of many manufacturing and analysis tasks.
.NH 2
The Design Loop
.PP
Solid models are very useful for generating drawings or pictures of
the modeled object, from any viewpoint.
The power of this capability alone usually pays for the cost of
developing the model.
However, the solid model has a much larger role in the design process
than simply automating the production of pictures and engineering
drawings.
Properly utilized, the solid model becomes the central element in the
iterative process of taking a design from idea to prototype design
to working design to optimized design.
This iterative process is termed the ``design loop'', and is illustrated
in Figure 1.2.
.KF
.PS
scale=200
define m0 |
[ box invis ht 121 wid 176 with .sw at 0,0
"\f1\s12\&M O D E L\f1\s0" at 87,53
ellipse ht 24 wid 176 at 88,12
ellipse ht 24 wid 176 at 88,109
line  from 1,106 to 1,16 
line  from 176,109 to 176,15 
] |

box invis ht 510 wid 529 with .sw at 0,0
line -> from 526,11 to 438,11 
line  from 526,283 to 526,11 
line  from 494,283 to 494,91 
line  from 422,283 to 526,283 
line -> from 494,91 to 414,91 
m0 with .nw at 261,465
spline -> from 242,401\
to 201,384\
to 137,384\
to 102,399
spline -> from 103,435\
to 144,452\
to 208,452\
to 243,437
line -> from 258,89 to 122,89 
line -> from 266,177 to 122,113 
line  from 342,331 to 342,315 
line  from 64,228 to 54,220 
line  from 64,228 to 75,220 
line  from 64,103 to 64,228 
line  from 70,384 to 65,392 
line  from 60,381 to 65,392 
line  from 65,277 to 65,392 
"\f1\s12\&Manufacturing\f1\s0" at 333,13
"\f1\s12\&Analysis 1\f1\s0" at 338,181
"\f1\s12\&Analysis N\f1\s0" at 338,85
line  from 462,283 to 462,187 
line -> from 462,187 to 406,187 
"\f1\s12\&Interrogate\f1\s0" at 332,277
box ht 44 wid 169 with .nw at 248,301 
"\f1\s12\&& Images\f1\s0" at 48,62
"\f1\s12\&Reports\f1\s0" at 43,85
"\f1\s12\&User\f1\s0" at 57,253
"\f1\s12\&Edit\f1\s0" at 63,410
.PE
.ce 1
\fBFigure 1.2 \(em The Design Loop\fR
.KE
.PP
In a full scale solid modeling system, there is no need for initial
drawings;  the designer expresses the initial structures directly
into the modeling system's editor,
just as a modern author creates his ``rough draft''
directly into a word processor.
At the completion of each version of the design, the model is
subjected to a battery of analyses appropriate to the function of the
object being designed.
Strength, volume, weight, level of protection, and other similar evaluations
can be reported, along with the
production of a variety of images and/or drawings.
These automated analyses help identify weaknesses or deficiencies in
a design \fIearly in the design process\fR.
By detecting flaws early, the designer has the
opportunity to correct his plans before having invested too much time
in a bad design, or the designer can
switch to an entirely different approach which may seem more promising
than the original one.
In this way, the solid modeling system allows the designer to
concentrate on the important, creative aspects of the design process.
Freeing the designer of routine analysis permits designs to be
finished in less time than previously required, or allows much more
rigorously optimized designs to be delivered in comparable
timeframes and at the same cost as unoptimized designs created using
older techniques.
.[
Deitz item-level modeling
.]
.PP
A highly interactive modeling system can allow full designs to be
completed in a matter of days, where weeks or months may have
previously been required.
.[
Deitz ncga
.]
Furthermore, the modeling system allows sweeping design changes to be
made quickly and cheaply, allowing great flexibility in the face of
ever changing requirements and markets.
The time needed to create a new product can be further decreased by
re-utilizing elements of earlier models and then modifying them as
appropriate.  If such an existing component is entirely suitable
for use in a new design, manufacturing and inventory
savings should also be realized.
.PP
Yet another benefit of developing a solids model is the opportunity
to exploit computer aided manufacturing (CAM).
In the design evaluation process, numerically controlled (NC) milling
machines can be used to produce small quantities of prototype parts
with a limited amount of human planning or supervision.
When the design is ready for full scale production, optimization of
the automatically produced NC programs
can result in maximum production rates from
factory automation equipment with minimum waste.
.PP
In summary, allowing the designer the opportunity to explore and
analyze more design options will allow the development of the
highest quality product, while also improving the work environment of
the designer by eliminating boring, repetitive tasks.
.NH 2
Model representations
.PP
Two major families of solid model representations exist,
each with several unique advantages.
The first representation, developed by MAGI under contract to BRL
.[
MAGI geometric description technique
.]
in the mid 1960s,
is the combinatorial solid geometry representation (CSG-rep).
Solid models of this type are expressed as boolean combinations of
primitive solids.
Each primitive solid is a geometric entity described by some set of
parameters that occupies a fixed volume in space;
the choice of primitive solid types available varies from system to
system.
The simplest solid that can be used is the halfspace,
.[
Requicha historical summary
.]
defined by the infinite plane $ a x + b y + c z + d = 0$
plus all points on one side of that plane.
Systems which defined all objects in terms of
Boolean combinations of halfspaces
include SHAPES
.[
Laning SHAPES user manual
.]
.[
Laning Capabilities of SHAPES
.]
from Draper Laboratories and TIPS-1
.[
Okino Kakazu Kubo TIPS-1 Technical Information Processing System
.]
.[
Okino TIPS 77 version
.]
.[
Okino TIPS practical approaches for an integrated CAD/CAM system
.]
.[
Okino TIPS graphics processor
.]
.[
Okino Kubo Kakazu TIPS-2 integrated CAD/CAM system prolomat
.]
from Hokkaido University.
While this choice of representation
limits these systems to modeling objects with
planar faces, and excludes smooth objects (or forces them to be
approximated), the simplicity of this representation lends itself to
very natural processing by VLSI hardware.
.[
Kedem computer structures vlsi design for classification
.]
.[
Kedem Ellis computer structures curve-solid classification geometric modeling
.]
Most CSG-rep systems in use today
offer quite a variety of primitive solids, ranging from various types
of spheres and ellipses, boxes and cones,
and solids defined by swept or extruded curves.
Some examples of CSG-rep systems which use primitive solids include
GDP/GRIN (IBM),
.[
Fitzgerald GRIN
.]
PADL-1,
.[
Voelcker PADL introduction
.]
.[
Voelcker PADL system for defining solid objects
.]
PADL-2,
.[
Brown PADL-2
.]
Series 7000 SMS (Auto-Trol),
GMSolid,
.[
Boyse GMSolid
.]
.[
Roth ray casting solid modeling
.]
SynthaVision (MAGI)
.[
Goldstein 3-D visual simulation
.]
.[
Goldstein modelling with the synthavision system
.]
(SynthaVision is also marketed as ICEM by CDC,
and Solids Modeling II by Applicon),
MGED (BRL),
.[
Weaver Muuss interactive construction
.]
.[
Muuss GED interactive solid modeling
.]
and ProSolid (CAEtec).
.PP
The alternative to describing solids with primitives is to adopt a
boundary representation (B-rep),
of which there are two sub-types,
the \fIexplicit\fR and \fIimplicit\fR boundary representations.
In an explicit boundary representation, each solid is described
by an explicit specification of all the points on the surface of the
solid, typically by exhaustively listing the vertices of many planar
facets.
Alternatively, there are implicit boundary representations,
where the surface of the solid is described by an analytic function
such as Coons patches,
.[
Coons surfaces space forms
.]
Bezier patches,
.[
Bezier unisurf
.]
splines,
.[
deBoor practical guide splines
.]
etc.
Some examples of B-rep systems (not all of which qualify as solid modelers)
are:
Alpha_1 (U. Utah),
.[
Cohen mathematical tools for modelers workbench
.]
Build-2 (U. Cambridge),
.[
Braid new generations
.]
.[
Braid stepwise construction
.]
.[
Hillyard build group
.]
CADD (McAuto),
CATIA (Dassault/IBM),
Compac (Technical U. Berlin),
.[
COMPAC integrated design and production
.]
.[
COMPAC workpiece design manufacturing
.]
.[
COMPAC integration design manufacturing planning
.]
.[
COMPAC producing engineering drawings
.]
.[
Spur COMPAC further development geometric modelling system
.]
Euclid (Matra Datavision),
.[
Bernascon euclid
.]
Euklid (Fides Co.),
.[
EUKLID language for 30 applications
.]
.[
EUKLID eine einfuhrung
.]
Glide (CMU),
.[
Eastman glide language for design
.]
.[
Eastman glide modelling using euler operators
.]
Medusa (Cambridge Interactive Systems, Ltd.),
PATRAN (PDA Engineering),
Romulus (Shape Data Ltd, Evans&Sutherland),
.[
ROMULUS
.]
and Solidesign (Computervision).
.NH 2
Representation Issues
.PP
Boundary representations offer the advantage of being able to
naturally model solid objects with arbitrarily shaped surfaces, but
can require a large amount of information to achieve acceptable
results.
Both CSG-reps and B-reps have certain advantages.  With pure CSG
representation, it can be exceedingly difficult and non-intuitive to
attempt to describe sculptured, free-form surfaces.
But similarly, implementing operations like boolean intersection and
boolean differences \fIon the fundamental representation itself\fR
can be difficult with pure Boundary representations.
Many current B-rep modelers implement boolean operations as an
external procedure, because current brute-force schemes to
evaluate Boolean operations are not closed.
As an example of this,
B-spline $inter$ B-spline results in polygons
rather than another B-spline.
In a boundary representation closed under the set of boolean operations,
B-rep $inter$ B-rep $->$ B-rep.
Thus, pure B-rep systems may be difficult to use for some types of
objects, especially those with sculptured surfaces pierced by sharp
rectangular gouges.
.[
Thomas volumes bounded by b-spline surfaces
.]
.PP
Even though existing systems were listed earlier as being either
CSG-rep or B-rep, the reality is that many
of these systems are actually hybrids of the two approaches,
offering the designer the choice of primitive solids or boundary
representations, as appropriate for each task.
In practice, the implementation of the
CSG-rep and B-rep portions of
the software may be quite different, but at the highest level of abstraction
each representation is just a different way of viewing the other.
Faceted primitives such as boxes and wedges can be thought of as
explicit B-reps, and smooth primitives such as spheres and cones can
be thought of as implicit B-reps defined by analytic
functions.
Until one uniform representation can be found, hybrid systems seem
both inevitable and desirable.
.NH 2
Mathematical descriptions of the primitive solids
.PP
There are differences between the primitive solids offered by any given
modeling system.  However, common primitives which are likely to be offered
by most systems include the half-space, ellipsoid,
truncated general cone, torus,
convex polyhedra with small numbers of vertices (typically four to eight),
faceted polyhedra,
sets of closed B-spline surfaces which taken together
define the bounds of a solid object,
and curves swept through space.
Examples of many of these types of primitives are shown
hovering over a mirror in plate 1.1.
.KF
.PS
scale=300
box invis ht 400 wid 553 with .sw at 0,0
"\f1\s12\&inside\f1\s0" at 184,347
"\f1\s12\&Origin\f1\s0" at 152,211
spline  from 361,289\
to 362,266\
to 344,255\
to 315,269\
to 295,264\
to 291,251\
to 286,236
spline  from 194,242\
to 202,220\
to 217,215\
to 242,220\
to 258,253\
to 278,251\
to 294,236
"\f1\s12\&d\f1\s0" at 306,202
"\f1\s12\&N\f1\s0" at 464,371
spline  from 273,561\
to 221,567\
to 195,528\
to 104,518\
to 83,462\
to 15,448\
to 41,375\
to 0,326\
to 43,298\
to 34,238\
to 64,227\
to 62,164\
to 131,151\
to 167,114\
to 205,102\
to 223,81\
to 278,107\
to 315,95\
to 349,99\
to 350,131\
to 375,145\
to 381,157
line  from 273,561 to 417,129 
line -> from 337,369 to 553,441 
line  from 361,377 to 353,401 
line  from 353,401 to 329,393 
line  from 194,242 to 361,297 
circle rad 8 at 361,297
circle rad 8 at 193,241
line -> from 417,130 to 352,0 
line -> from 273,561 to 208,431 
"\f1\s12\&outside\f1\s0" at 424,515
.PE
.ce 1
\fBFigure 1.3 \(em Definition of a Halfspace\fR
.KE
.NH 3
Halfspace (HALF)
.PP
The simplest solid that can be used is the halfspace,
defined by the infinite plane $ a x + b y + c z + d = 0$
plus all points on one side of that plane.
Referring to figure 1.3,
another way to define a halfspace is to specify a vector
$bold N vec$ normal to the surface of the plane
with unit length
(i.e. $| bold N vec | = 1$)
and to specify
the minimum distance $d$ from the origin to the plane.
If $d >= 0$ then the origin is inside the halfspace, otherwise
the origin is outside.
More rigorously, any point $bold X vec$ is contained within the halfspace
if $bold N vec cdot bold X vec <= d$.
Points lying on the surface of the plane
are considered to be inside the halfspace.
.KF
.PS
scale=300
define m0 |
[ box invis ht 238 wid 356 with .sw at 0,0
line -> from 178,119 to 138,63 
line -> from 178,119 to 178,0 
line -> from 178,119 to 356,119 
ellipse ht 236 wid 90 at 178,119
ellipse ht 114 wid 356 at 178,119
ellipse ht 238 wid 356 at 178,119
circle rad 7 at 178,119
] |

box invis ht 324 wid 700 with .sw at 0,0
"\f1\s12\&V\f1\s0" at 92,224
"\f1\s12\&A\f1\s0" at 62,160
"\f1\s12\&C\f1\s0" at 107,76
"\f1\s12\&B\f1\s0" at 229,202
ellipse ht 208 wid 68 at 106,205
line -> from 106,205 to 212,205 
line -> from 106,205 to 76,164 
line -> from 106,205 to 106,100 
"\f1\s12\&SPHERE\f1\s0" at 106,26
"\f1\s12\&ELLIPSE\f1\s0" at 455,13
circle rad 7 at 106,205
circle rad 105 at 106,205
ellipse ht 82 wid 212 at 106,205
m0 with .nw at 274,324
"\f1\s12\&B\f1\s0" at 650,200
"\f1\s12\&V\f1\s0" at 441,226
"\f1\s12\&A\f1\s0" at 404,134
"\f1\s12\&C\f1\s0" at 453,58
.PE
.ce 1
\fBFigure 1.4 \(em Ellipsoid\fR
.KE
.NH 3
Ellipsoid (ELL)
.PP
Referring to figure 1.4,
an ellipsoid can be defined by specifying a vector
$bold V vec$ from the origin to the center of the ellipsoid,
and by specifying three vectors
$bold A vec , bold B vec , bold C vec$
which are mutually perpendicular, and whose magnitudes define the
eccentricity of the ellipse.
Thus, $ | bold A vec |=| bold B vec |=| bold C vec | $ defines a sphere.
.KF
.PS
scale=300
box invis ht 494 wid 463 with .sw at 0,0
"\f1\s12\&D\f1\s0" at 325,463
line -> from 231,95 to 463,95 
line  from 231,190 to 239,183 
line  from 223,183 to 231,190 
line  from 231,95 to 231,190 
line -> from 343,431 to 447,431 
line  from 343,494 to 351,487 
line  from 335,487 to 343,494 
line  from 343,431 to 343,494 
line  from 447,431 to 463,95 
line  from 239,431 to 0,95 
ellipse ht 126 wid 208 at 343,431
ellipse ht 190 wid 462 at 231,95
circle rad 8 at 231,95
line -> from 231,95 to 343,431 dashed
"\f1\s12\&V\f1\s0" at 208,68
"\f1\s12\&A\f1\s0" at 423,70
"\f1\s12\&B\f1\s0" at 209,158
"\f1\s12\&H\f1\s0" at 323,287
"\f1\s12\&C\f1\s0" at 404,403
.PE
.ce 1
\fBFigure 1.5 \(em Truncated General Cone\fR
.KE
.NH 3
Truncated General Cone (TGC)
.PP
Referring to figure 1.5, a truncated general cone can be defined by specifying
a vector $bold V vec$ from the origin to the center of the ``lower'' ellipse,
two perpendicular vectors $bold A vec$ and $bold B vec$
which define the orientation and eccentricity of the lower ellipse,
a vector $bold H vec$ which defines the height and slant of the cone,
and two more perpendicular vectors $bold C vec$ and $bold D vec$
which define the orientation and eccentricity of the upper ellipse.
.KF
.PS
scale=300
box invis ht 448 wid 616 with .sw at 0,0
circle rad 31 at 560,352
line  from 560,448 to 560,0 dashed
line -> from 560,224 to 592,224 
line  from 8,64 to 616,64 dashed
line  from 8,96 to 616,96 dashed
line  from 8,128 to 616,128 dashed
circle rad 160 at 160,224
line  from 176,232 to 176,232 
line  from 176,256 to 152,248 
line  from 184,232 to 176,256 
line -> from 160,224 to 280,264 
line  from 136,224 to 616,224 dashed
line  from 8,320 to 616,320 dashed
line  from 8,352 to 616,352 dashed
line  from 8,384 to 616,384 dashed
line -> from 159,224 to 120,344 
circle rad 128 at 160,224
circle rad 97 at 159,224
circle rad 8 at 160,224
line  from 528,352 to 528,96 
line  from 594,352 to 594,96 
"\f1\s12\&R2\f1\s0" at 504,368
"\f1\s12\&H\f1\s0" at 578,254
"\f1\s12\&V\f1\s0" at 544,191
"\f1\s12\&V\f1\s0" at 137,197
line  from 160,384 to 168,376 
line  from 152,376 to 160,384 
line  from 160,352 to 160,384 
"\f1\s12\&R2\f1\s0" at 194,362
"\f1\s12\&A\f1\s0" at 271,235
"\f1\s12\&R1\f1\s0" at 212,257
"\f1\s12\&B\f1\s0" at 144,331
circle rad 7 at 560,224
"\f1\s12\&R1\f1\s0" at 579,145
line  from 560,96 to 568,104 
line  from 568,104 to 568,104 
line  from 568,104 to 568,104 
line  from 552,104 to 560,96 
line  from 560,224 to 560,96 
line -> from 560,352 to 538,373 
circle rad 31 at 560,96
.PE
.ce 1
\fBFigure 1.6 \(em Torus\fR
.KE
.NH 3
Torus (TOR)
.PP
Referring to figure 1.6, a torus can be defined by specifying a vector
$bold V vec$ from the origin to the center of the torus,
three mutually  perpendicular vectors
$bold A vec$ and $bold B vec$ and $bold H vec$
which specify the plane containing the torus and the normal to the plane,
plus two radii, $R sub 1$ which specifies the overall radius of the torus,
and $R sub 2$ which specifies the radius of the swept circular section of
the torus.
Some systems may allow the torus to have non-circular shape and cross-section,
in which case more parameters would be required.
.KF
.PS
scale=300
box invis ht 312 wid 631 with .sw at 0,0
line  from 146,32 to 18,128 
line  from 146,32 to 226,104 
line  from 146,256 to 146,32 
line  from 18,128 to 226,104 dashed
line  from 474,64 to 474,64 
line  from 338,136 to 346,128 
line  from 330,128 to 338,136 
line  from 338,136 to 338,64 
line  from 474,136 to 338,136 
line  from 458,200 to 610,192 dashed
line  from 458,200 to 458,256 dashed
line  from 338,64 to 458,200 dashed
line -> from 338,64 to 474,136 
"\f1\s12\&8\f1\s0" at 440,272
"\f1\s12\&7\f1\s0" at 607,300
"\f1\s12\&6\f1\s0" at 626,184
"\f1\s12\&5\f1\s0" at 474,213
"\f1\s12\&4\f1\s0" at 319,134
"\f1\s12\&3\f1\s0" at 493,132
"\f1\s12\&2\f1\s0" at 486,44
"\f1\s12\&1\f1\s0" at 324,53
line  from 594,296 to 610,192 
line  from 458,256 to 594,296 
line  from 338,136 to 458,256 
line  from 474,136 to 594,296 
line  from 474,64 to 610,192 
line  from 474,64 to 474,136 
line -> from 338,64 to 474,64 
"\f1\s12\&4, 5, 6, 7, 8\f1\s0" at 148,274
"\f1\s12\&3\f1\s0" at 243,101
"\f1\s12\&2\f1\s0" at 154,13
"\f1\s12\&1\f1\s0" at 4,128
line  from 226,104 to 146,256 
line  from 18,128 to 146,256 
.PE
.ce 1
\fBFigure 1.7 \(em Convex Polyhedron (ARB8)\fR
.KE
.NH 3
Convex Polyhedron with 4 to 8 vertices (ARB8)
.PP
Referring to figure 1.7, a convex polyhedron can be defined
in absolute form by specifying
the points which represent the vertices of the faces, or
in relative form by
specifying a vector $bold V vec$ from the origin to the first vertex
and seven additional vectors ${ bold R vec sub { i } | } sub { i=1..7 }$
from $bold V vec$
to the other vertices.
Vectors $bold R vec sub i$ may coincide or have length=0,
${ | bold R vec sub i | } sub i=1..7 >= 0$.
Examples of this type of solid are the wedge, box, pyramid, etc.
.KF
.PS
scale=300
box invis ht 256 wid 740 with .sw at 0,0
"\f1\s8\&5\f1\s0" at 108,184
"\f1\s8\&6\f1\s0" at 136,72
"\f1\s8\&7\f1\s0" at 80,80
"\f1\s8\&8\f1\s0" at 16,96
"\f1\s8\&9\f1\s0" at 46,138
"\f1\s8\&10\f1\s0" at 8,8
line  from 70,96 to 130,96 
line  from 120,166 to 185,166 
line  from 120,166 to 160,236 
line  from 50,206 to 160,236 
line  from 50,126 to 130,96 dashed
line  from 50,206 to 100,206 dashed
line  from 0,126 to 70,96 
line  from 50,126 to 10,26 dashed
line  from 185,166 to 160,236 
line  from 70,96 to 120,166 
line  from 70,96 to 10,26 
line  from 10,26 to 0,126 
line  from 100,206 to 160,236 dashed
line  from 50,206 to 120,166 
"\f1\s8\&Curve 4\f1\s0" at 342,28
line  from 430,164 to 406,164 
line  from 430,28 to 406,28 
"\f1\s8\&Curve 3\f1\s0" at 342,92
line  from 406,236 to 430,236 
"\f1\s8\&Curve 2\f1\s0" at 342,164
line  from 430,92 to 406,92 
"\f1\s8\&Curve 1\f1\s0" at 342,236
line  from 678,92 to 718,92 
line  from 678,28 to 718,28 
line  from 678,116 to 718,148 
line  from 678,236 to 718,236 
line  from 678,188 to 718,220 
line  from 678,164 to 718,164 
line  from 678,44 to 718,76 
line  from 606,164 to 646,164 
line  from 606,44 to 646,76 
line  from 606,116 to 646,148 
line  from 662,220 to 662,187 
"\f1\s8\&5\f1\s0" at 662,164
"\f1\s8\&1\f1\s0" at 662,236
"\f1\s8\&9\f1\s0" at 662,92
"\f1\s8\&10\f1\s0" at 662,28
line  from 662,148 to 662,116 
line  from 662,76 to 662,44 
line  from 734,217 to 734,188 
line  from 734,148 to 734,116 
"\f1\s8\&2\f1\s0" at 734,164
"\f1\s8\&10\f1\s0" at 734,28
line  from 734,77 to 734,44 
"\f1\s8\&1\f1\s0" at 734,236
"\f1\s8\&6\f1\s0" at 734,92
line  from 534,92 to 574,92 
line  from 534,28 to 574,28 
line  from 534,164 to 574,164 
"\f1\s8\&7\f1\s0" at 518,92
line  from 518,76 to 518,44 
"\f1\s8\&10\f1\s0" at 518,28
line  from 518,220 to 518,188 
line  from 462,28 to 502,28 
line  from 462,236 to 502,236 
line  from 462,92 to 502,92 
line  from 446,76 to 446,44 
"\f1\s8\&10\f1\s0" at 446,28
"\f1\s8\&6\f1\s0" at 446,92
line  from 446,116 to 446,148 
line  from 590,76 to 590,44 
"\f1\s8\&10\f1\s0" at 590,28
"\f1\s8\&4\f1\s0" at 590,164
line  from 534,236 to 574,236 
line  from 534,188 to 574,220 
"\f1\s8\&3\f1\s0" at 518,164
line  from 518,147 to 518,116 
line  from 462,44 to 502,76 
line  from 462,116 to 502,148 
"\f1\s8\&2\f1\s0" at 446,164
"\f1\s8\&8\f1\s0" at 590,92
"\f1\s8\&1\f1\s0" at 590,236
line  from 534,116 to 574,148 
"\f1\s8\&1\f1\s0" at 518,236
line  from 502,220 to 462,188 
"\f1\s8\&1\f1\s0" at 446,236
line  from 590,148 to 590,116 
line  from 462,164 to 502,164 
line  from 590,220 to 590,188 
line  from 446,188 to 446,220 
line  from 534,44 to 574,76 
line  from 606,28 to 646,28 
line  from 606,236 to 646,236 
line  from 606,188 to 646,220 
line  from 606,92 to 646,92 
line  from 0,126 to 50,126 dashed
line  from 130,96 to 185,166 
line  from 50,126 to 100,206 dashed
line  from 100,206 to 185,166 dashed
line  from 0,126 to 50,206 
line  from 10,26 to 130,96 
"\f1\s8\&1\f1\s0" at 168,248
"\f1\s8\&2\f1\s0" at 200,144
"\f1\s8\&3\f1\s0" at 128,144
line  from 192,236 to 288,236 
line  from 216,164 to 288,164 
line  from 160,92 to 288,92 
line  from 48,28 to 288,28 
"\f1\s8\&4\f1\s0" at 40,216
.PE
.ce 1
\fBFigure 1.8 \(em Faceted Polyhedron (ARS)\fR
.KE
.NH 3
Faceted Polyhedron (ARS)
.PP
Referring to figure 1.8,
any faceted polyhedron with logically rectangular structure can
be defined by listing N points on each of M curves.
In order to make this type of solid more useful, points may overlap,
and points are taken in triples to form planar facets.  Degenerate
facets (lines and points) are discarded.
.PP
One can think of this type of polyhedron as representing data obtained
by measuring ``waterlines'', i.e. by placing the object into a basin,
adding some water, and measuring N points where the water touches the object.
This procedure would be repeated M times to define the whole object.
This type of solid is really an explicit boundary representation.
.NH 3
B-spline Solids (SPLINE)
.PP
A spline solid is composed of one or more spline surfaces
(also called spline patches), which in combination completely enclose
some region in space.
This type of solid is really an implicit boundary representation.
It is important that the model editor ensures that there are no gaps
between the spline surfaces so that the primitive is actually solid.
An example of one spline surface that might make up a spline solid
is shown in plate 1.2.
.PP
A clear explanation of the fundamentals of spline surfaces can
be had from deBoor,
.[
deBoor calculating with splines
.]
.[
deBoor Practical Guide
.]
while a basis for good computer implementations can be found in Riesenfeld
.[
Riesenfeld Discrete B-splines and Subdivision
.]
and Forrest,
.[
Forrest unified approach to modelling
.]
so they will not be described further.
Details of implementations to design sculptured surfaces using
the B-spline representation can be found in Cobb
.[
Cobb design sculptured surfaces
.]
and Stay.
.[
Stay rounded edge primitives design
.]
.NH 2
The Boolean Math of Combination
.PP
Boolean set operations are a natural way to combine shapes.
The union operator gives the combined volume of two input shapes, while
the intersection operator gives the common volume of two input shapes, and
the difference (subtraction) operator acts like a ``cookie cutter'',
giving the volume of the
first input shape with the common volume of the two subtracted out.
These familiar concepts are illustrated in 4 pairs of plates generated
from three primitive solids: a box $A$, a cylinder $B$, and a wedge $C$.
The wireframe and shaded image of $A union B union C$ are plates 1.3 and 1.4,
the wireframe and shaded image of $A - B - C$ are plates 1.5 and 1.6,
the wireframe and shaded image of $(A - B) inter C$ are plates 1.7 and 1.8,
and the wireframe and shaded image of $C - A - B$ are plates 1.9 and 1.10.
Note that the wireframe approximations are for visualization purposes only;
while the wireframe outlines are only approximate,
the actual solids (e.g., the cylinder) are smooth.
For a rigorous treatment of boolean operations in CSG systems,
consult Tilove.
.[
Tilove boolean operations
.]
.NH 2
Model Structure
.PP
Most projects have a natural organization.
Similarly, geometric models which are constructed
need to have a good, logical structure which
is easy to work with and
reflects the natural structure of the project.
Larger structures should be formed from sub-elements,
facilitating top-down design of the overall structure, and
bottom-up design of highly detailed subassemblies.
This dual strategy allows
detail to be added to sub-elements only when needed.
Replicated components should not have to be re-described,
but instead should be modeled as translated \fIinstances\fR
of the prototype assembly.
Finally, there needs to be a mechanism to easily utilize
``model parts bins''.  This allows elements of other models to be
incorporated into the current model, either as an exact duplicate,
or as a point of departure for further editing.
.KF
.PS
scale=300
box invis ht 480 wid 415 with .sw at 0,0
spline   from 296,182\
to 96,140\
to 54,109\
to 33,49
"\f1\s12\&a\f1\s0" at 299,87
"\f1\s12\&M\f1\s0" at 282,97
spline   from 346,159\
to 343,112\
to 332,80\
to 303,25
"\f1\s12\&R\f1\s0" at 196,87
"\f1\s12\&M\f1\s0" at 177,98
"\f1\s12\&L\f1\s0" at 113,80
"\f1\s12\&M\f1\s0" at 96,94
"\f1\s12\&R\f1\s0" at 343,275
"\f1\s12\&M\f1\s0" at 328,292
"\f1\s12\&F\f1\s0" at 241,273
"\f1\s12\&M\f1\s0" at 224,289
"\f1\s12\&s\f1\s0" at 148,277
"\f1\s12\&M\f1\s0" at 135,288
"\f1\s12\&e\f1\s0" at 37,274
"\f1\s12\&M\f1\s0" at 22,284
"\f1\s12\&Axle-rod\f1\s0" at 303,13
"\f1\s12\&Wheel\f1\s0" at 30,27
"\f1\s12\&Engine\f1\s0" at 32,196
spline   from 281,380\
to 349,319\
to 369,276\
to 369,228
spline   from 233,353\
to 245,293\
to 270,235\
to 295,211
spline   from 187,355\
to 169,315\
to 169,274\
to 175,211
spline   from 157,387\
to 97,350\
to 58,312\
to 44,218
"\f1\s12\&Shaft\f1\s0" at 191,195
"\f1\s12\&Axle\f1\s0" at 350,195
ellipse ht 58 wid 120 at 355,194
ellipse ht 58 wid 120 at 217,387
"\f1\s12\&Car\f1\s0" at 217,385
spline   from 312,171\
to 212,84\
to 162,54\
to 73,34
.PE
.ce 1
\fBFigure 1.9 \(em Directed Acyclic Graph for Simple Car\fR
.KE
.PP
A directed acyclic graph (DAG) is a good structure to choose
to represent this type of structure in a model.
A directed acyclic graph is composed of
a collection of \fInodes\fR connected by
directed \fIarcs\fR without cycles (loops).
Each node in the directed acyclic graph has a name.
\fILeaf nodes\fR contain a single piece of geometry
(a single primitive solid), and
\fINon-terminal nodes\fR have one or more
departing \fIarcs\fR, each \fIarc\fR referring to some other node by name.
In addition to the referenced name, each
\fIarc\fR contains a boolean operator and
a 4-by-4 transformation matrix.
Refer to figure 1.9 for an example of a directed acyclic graph used to
express the relationships between various parts of a car.
.PP
As the directed acyclic graph is traversed from top to bottom,
the total effect is accumulated by multiplying the matrices together.
If $bold v vec$ is some vector in a solid at a leaf node, and it is
transformed by the matrix in a single arc, the transformed vector is
.EQ
bold v vec ~prime ~=~ bold v vec ~*~ bold M vec .
.EN
When traversing the graph from top to bottom, the matrix on the first arc
is considered $bold M vec sub 1$, and the matrix on the final arc is
$bold M vec sub n$.  Thus, the final value of a vector is found by
.EQ
bold v vec ~prime ~=~ bold v vec ~*~ bold M vec sub n ~*~ ... ~*~ bold M vec sub 1
.EN
In the example of the car in figure 1.9, a vector in the left wheel on
the front axle would be
.EQ
{ bold v vec ~prime } sub wheel ~=~ { bold v vec } sub wheel
 ~*~ bold M vec sub L ~*~ bold M vec sub F .
.EN
Each matrix is a 4-by-4 Homogeneous Transform Matrix,
which may represent any combination of
rotation,
scaling (uniform or affine), or translation.
.EQ
bold v vec mark =~ left [ x ~ y ~ z ~ w right ]
.EN
.EQ
bold v vec prime lineup =~
left [ x prime y prime z prime w prime right ]
= left [
{ x prime } over { w prime }
{ y prime } over { w prime }
{ z prime } over { w prime }
1  right ]
.EN
.EQ
bold v vec prime lineup =~ bold v vec ~*~ bold M vec
~=~ left [  x ~ y ~ z ~ w  right ]
* left [ matrix {
col { alpha r above r above r above DELTA x }
col { r above beta r above r above DELTA y }
col { r above r above gamma r above DELTA z }
col { 0 above 0 above 0 above { 1 over s } }
} right ]
.EN
Here, the nine $r$ elements specify the rotation,
$alpha$, $beta$, and $gamma$ specify the single-axis scaling factors
(affine transformation),
$s$ specifies the uniform scaling factor, and
$DELTA x$, $DELTA y$, and $DELTA z$ specify the translation distances.
Note that the three elements usually used for perspective transformations
are zero.  Perspective transformations are used for viewing only,
and should not be part of a model matrix.
For more details on homogeneous coordinates
and homogeneous transform matrices, consult
pp. 491-501 in Newman and Sproul,
.[
Newman Sproul principles
.]
and also see pp. 46-88 in Rogers and Adams.
.[
Rogers Adams mathematical elements
.]
.NH 2
References
.PP
For reviews of the solid modeling field in general, see
Requicha,
.[
Requicha Historical Summary
.]
Johnson,
.[
Johnson capabilities of solid modeling
.]
and Baer.
.[
Baer geometric modelling survey
.]
For more information on current solid modelers, the interested reader is
referred to
Wyvil,
.[
Wyvil Kunii functional model for constructive solid geometry
.]
Boyse,
.[
Boyse GMSolid
.]
Muuss,
.[
Muuss GED Interactive solid modeling system
.]
and Brown.
.[
Brown PADL-2
.]
.NH 2
History of Solid Modeling at BRL
.PP
The Ballistic Research Laboratory has a long history of
innovation in computer science, starting with the world's first electronic
digital computer, ENIAC, built for BRL by the Moore School of Engineering.
In the early 1960s, BRL retained
the Mathematical Applications Group, Inc. (MAGI)
to develop a geometric description technique suitable for computer
analysis of the survivability of armored military vehicles.
This culminated in the development of the MAGIC solid modeling
system and shotline (ray-tracing) code in 1966,
.[
MAGI geometric description technique
.]
which was adopted and documented by a tri-service Joint Technical
Coordinating Group for Munitions Effectiveness
.[
MAGIC User Manual
.]
.[
MAGIC Analyst Manual
.]
and also resulted in a number of other papers being published.
.[
Goldstein visual simulation
.]
Further development at BRL evolved the MAGIC ray-tracing code into
the GIFT (Geometric Information from Targets) ray-tracing code,
.[
GIFT input requirements
.]
.[
GIFT output options
.]
while MAGI pursued in-house developments which eventually resulted in
the commercial Synthavision system.
.[
Goldstein modelling with synthavision system
.]
.[
Goldstein bounding edges of synthavision model
.]
.PP
At BRL, the original GIFT
models were prepared laboriously by hand.
Each solid was described by dozens of parameters entered on punched cards.
In GIFT descriptions, only one level of model structure is available,
so good model structure was difficult to achieve.
These difficulties notwithstanding, BRL built approximately 150 models
for the GIFT system over a span of 14 years.
With the exception of simple line drawings of the models,
none of these models had ever been seen, and no graphical tools
for viewing or manipulating them existed.
.PP
In late 1979, the author
began an independent, unfunded research effort to investigate
the use of three-dimensional graphics display hardware to assist in
the development of combinatorial solid geometry descriptions of
military vehicles.  The success of this effort
prompted the development in early 1980 of a special database to describe the
hierarchical relationships between the
sub-systems of the vehicles being modeled.
Geometry so described could be viewed and modified using a
special graphics editor called GED,
.[
Weaver Muuss interactive construction
.]
documented in a monochrome movie
which demonstrated the capabilities of the GED software.
.PP
In 1981, BRL initiated an industry-wide search for
computer aided design systems capable of meeting BRL's expanding
requirements.  Many systems were evaluated, but none met BRL's complex
needs, and the decision was made to enhance the in-house software.
The result was a state-of-the-art software package
capable of meeting BRL's needs for vehicle assessment.
In early 1982, the first dedicated DEC PDP-11/70 and associated
graphics displays were installed, creating BRL's
first production interactive CAD facility.
.[
Muuss GED interactive solid modeling
.]
An early rendering produced by this system is shown in plate 1.11.
Later, GED was extended to have multi-display capability;
the new version, MGED, went into production in 1984.
.PP
In April 1984, a ``fast prototype'' for a new ray-tracing
code was designed and implemented in one week;  the team effort to
develop the full implementation continued through 1984.
In July 1985, the results of recent research in techniques
for decreasing the computational expense of ray-tracing
.[
Kaplan
.]
were extended
in several simple but significant ways, resulting in substantially
higher performance for the RT library.
In summer 1985, RT reached production status.
.PP
The RT library has permitted other BRL
researchers to implement capabilities that were not possible
using earlier software, including bi-static lighting models, and models of
laser illumination.  A project to redesign all
of BRL's applications codes around the power of the RT library was begun.
.PP
In mid 1985, the RT code was extended for fully parallel operation
developed for execution on the BRL HEP Supercomputer.
In late 1985, BRL began to experiment with ray-tracing
fractal clouds and frequency-controlled random terrain, and
began experiments in motion control and animation.
Coupling this animation capability with the fully parallel HEP
version of the RT code
culminated in a 3 minute medium-resolution computer
generated animation titled:  \fI``A Quick Run Through The M-2 Bradley''\fR.
.PP
Since the adoption of GED, BRL has been building
models of 15 to 20 vehicles annually, usually
producing between 3 and 12 variations of each.
Most of these models have more than 2000 components, with
the larger models often having in excess of 5000 components.
.NH 1
BRL's Solid Modeling Editor MGED:  A Case Study
.PP
There are a significant number of solid modeling systems,
each developed for different purposes by different groups.
In this paper, details of the design of BRL's solid modeling system
.[
Muuss Applin BRL GED interactive solid modeling system for vulnerability
.]
will be presented.
This presentation both documents some of the specific capabilities
of the BRL system, and also serves as a good case study of
the features and functionality that should be present in every solid
modeling system.
Most features are comparable to those found in commercial systems.
.NH 2
Philosophy
.PP
The role of CAD models at BRL differs somewhat from
that of CAD models being built in the automobile and aerospace industries,
resulting in some different design choices
being made in the BRL CAD software.
Because BRL's main use for these models is to conduct detailed
performance and survivability analyses of large complex vehicles,
it is required that the model of an entire vehicle be completely contained
in a single database, suitable for interrogation by the application codes.
This places especially heavy demands on the database software.
At the same time, a somewhat more modest level of detail is required
for these analysis codes than if direct NC machining was the primary goal.
.PP
At BRL, there are only a small number of primary designers responsible
for the design of a vehicle, and for the construction of the corresponding
solid model.  Together they decide upon and construct the
overall structure of the model,
then they perform the work of building substructures in parallel,
constantly combining intermediate results into the full model database.
Because of the need to produce rapid prototypes (often creating a full design
within a few weeks), there is no time for a separate integration stage;
subsystem integration must be an ongoing part of the design process.
.PP
Once an initial vehicle design is completed, there is usually the
need for exploring many alternatives.  Typically, between 3 and 12
variations of each design need to be produced, analyzed, and optimized
before recommendations for the final design can be made.
Also, there is a constantly changing definition of performance;
based on new developments it may be necessary to rapidly re-evaluate
all the designs of the past several years for trouble spots.
.PP
The user interface is designed to be powerful and ``expert friendly'' rather
than foolproof for a novice to use, much like UNIX.
However, it only takes about two days for new users to start doing useful
design work with MGED.
True proficiency comes with a few months practice.
.PP
Finally, it is vitally important that the software offer the same capabilities
and user interface across a wide variety of display and processor hardware.
Government procurement regulations make single-vendor solutions difficult.
The best way to combat this is with highly portable software.
.NH 2
Displays Supported
.PP
It is important for a CAD system to have a certain degree of independence
from any single display device in order to provide longevity of the
software and freedom from a single equipment supplier.
The MGED editor supports serial use of multiple displays by way of
an object-oriented programmatic
interface between the editor proper and the display-specific code.
All display-specific code for each type of hardware is thus isolated
in a separate \fIdisplay manager\fR module.
High performance of the display manager was an important design goal.
Existing graphics libraries
were considered, but no well established standard existed with the necessary
performance and 3-dimensional constructs.
By having the display manager modules incorporated as a direct part of
the MGED editor, the high rates of display update necessary to deliver
true interactive response are possible, even when using CPUs of modest power.
.PP
An arbitrary number of
display managers may be included in a copy of MGED, allowing the user
to rapidly and conveniently move his editing session from display to display.
This is useful for switching between several displays, each of
which may have unique benefits:  one might have color capability,
and another might have depth cueing.
The ``release'' command closes out MGED's use of the current
display, and does an implicit attach to the ``null'' display manager.
This can be useful to allow another user to briefly examine an image
on the same display hardware without having to lose the state of
the MGED editing session.  The ``attach'' command is used to
attach to a new display via it's appropriate display manager routines.
If another display is already attached, it is released first.
The null display manager also allows the MGED editor to be run from a normal
alphanumeric terminal with no graphic display at all.  This can be useful
when the only tasks at hand involve viewing or changing
database structures, or entering or adjusting geometry parameters
in numerical form.
.PP
Creation of a new display manager module in the ``\fBC\fR'' language
.[
ritchie johnson lesk kernighan the C programming language
.]
generally takes an experienced
programmer from one to three days.
The uniform interface to the display manager provides two levels
of interactive support.
The first level of display support includes
the Tektronix 4014, 4016, and compatible displays,
including the Teletype 5620 bit-mapped displays.
However, while storage-tube style display devices allow MGED to
deliver the correct functionality, they lack the
rate of screen refresh needed for productive interaction.
The second level of support, including real-time interaction,
is provided by
the Vector General 3300 displays,
the Megatek 7250 and 7255 displays,
the Raster Technologies Model One/180 display,
the Evans and Sutherland PS300 displays
with either serial, parallel, or Ethernet attachment,
and the Silicon Graphics IRIS 2400 workstation family.
.NH 2
Portability
.PP
Today, the half-life of computer technology is
approximately two to three years.
To realize proper longevity of the modeling software, it needs to be written
in a portable language to allow the software to be moved readily from
processor to processor without requiring the modeling software or users
to change.
Then, when it is desirable to
take advantage of the constantly increasing 
processor capabilities and similarly increasing memory capacity by replacing
the installed hardware base, there are a minimum of ancillary costs.
Also, it may be desirable to connect together processors from a variety
of vendors, with the workload judiciously allocated to
the types of hardware that best support the requirements of each particular
application program.
This distribution of processing when coupled with the fact that
users are spread out over multiple locations makes networking a vital
ingredient as well.
.PP
BRL's strategy for achieving this high level of portability was to target
all the software for the UNIX operating system,
.[
Ritchie Thompson time-sharing system
.]
with all the software written in the ``\fBC\fR''
programming language.
.[
kern78 the C programming language
.]
All communications software is based upon the TCP/IP protocol suite
developed by DARPA
.[
Feinler ddn protocol handbook
.]
and now formally designated MIL-STD-1777 and MIL-STD-1778.
The CAD software is currently running on all UNIX machines at BRL,
under several versions of the UNIX operating system, including
Berkeley 4.3 BSD UNIX, Berkeley 4.2 BSD UNIX, and AT&T System V UNIX.
In addition, there has been a limited subset of the software
ported to the Digital Equipment Corporation VAX/VMS operating system,
using the VMS C compiler.
.PP
The list of manufacturers and models of CPUs that support the UNIX
operating system
.[
Deitz modern tools system engineering
.]
is much too lengthy to include here.  However, BRL
has experience using this software on
DEC VAX 11/750, 11/780, 11/785 processors,
Gould PN6000 and PN9000 processors,
Alliant FX/8 processors (including systems with 8 CPUs),
Silicon Graphics IRIS 2400, 2400 Turbo, and 3030 workstations,
and the ill-fated Denelcor HEP H-1000 parallel supercomputer.
.KF
.PS
scale=300
box invis ht 570 wid 400 with .sw at 0,0
"\f1\s8\&Display\d1\f1\s0" at 100,30
line -> from 150,104 to 100,42 
"\f1\s8\&Display\dN\f1\s0" at 300,30
line -> from 250,104 to 300,42
"\f1\s18\&...\f1\s0" at 200,67
"\f1\s8\&Display Managers 1..N\f1\s0" at 200,135
box ht 52 wid 300 with .nw at 50,160
spline -> from 280,307\
to 317,299\
to 380,252\
to 384,160\
to 350,135
"\f1\s8\&Geometry Routines\f1\s0" at 200,204
box ht 44 wid 280 with .nw at 60,224
spline -> from 120,305\
to 40,280\
to 5,260\
to 5,230\
to 60,200
"\f1\s14\&MGED\f1\s0" at 200,305
box ht 65 wid 160 with .nw at 120,340
"\f1\s12\&Database\ \ Interface\f1\s0" at 200,401
line -> from 200,465 to 200,341 
"\f1\s14\&Database\f1\s0" at 200,500
line  from 100,535 to 300,535
line  from 100,465 to 300,465
ellipse ht 70 wid 18 at 100,500
ellipse ht 70 wid 18 at 300,500
.PE
.ce 1
\fBFigure 2.1 \(em Object-Oriented Design\fR
.KE
.NH 2
Object-Oriented Design
.PP
The central editor code has four sets of object-oriented interfaces
to various subsystems, including database access, geometry processing,
display management, and command parser/human interface,
as depicted in figure 2.1.
In each case, a common interface has been defined for the set of
functions that implement the overall function;
multiple instances of these function sets exist when a multiplicity
of support exists.
The routines in each instance of a function set are completely independent
of all the routines in other functions sets, making it easy to add new
instances of the function set.  A new type of primitive geometry,
a new display manager, a new database interface, or a new command
processor can each be added simply by writing all the routines
to implement a new function set.
This approach greatly simplifies software maintenance, and allows
different groups to have responsibility for the
creation and enhancement of features within each of the function sets.
.KF
.PS
scale=300
box invis ht 390 wid 605 with .sw at 0,0
line  from 477,100 to 526,70
line  from 359,100 to 415,70
line  from 335,100 to 303,70 
line  from 234,100 to 274,70
line  from 198,100 to 165,70 
line  from 95,100 to 149,70
line  from 95,100 to 58,70
line  from 132,169 to 84,150
line  from 167,169 to 217,150
line  from 276,172 to 217,150 
line  from 289,172 to 344,150 
line  from 415,172 to 464,150 
line  from 370,252 to 415,223
line  from 346,252 to 308,223 
line  from 247,252 to 289,223 
line  from 210,252 to 171,223 
ellipse ht 62 wid 116 at 547,35
ellipse ht 62 wid 116 at 423,35
ellipse ht 62 wid 116 at 303,35
ellipse ht 62 wid 116 at 180,35
ellipse ht 62 wid 116 at 58,35
box ht 50 wid 96 with .nw at 429,150
box ht 50 wid 96 with .nw at 169,150 
box ht 50 wid 96 with .nw at 296,150 
box ht 50 wid 96 with .nw at 36,150
box ht 50 wid 96 with .nw at 367,220 
box ht 50 wid 96 with .nw at 241,220
box ht 50 wid 96 with .nw at 108,220
box ht 50 wid 96 with .nw at 310,305 
box ht 50 wid 96 with .nw at 174,305
.PE
.ce 1
\fBFigure 2.2 \(em Hierarchy\fR
.KE
.NH 2
Directed Acyclic Graph and Database Details
.PP
The database is stored as a single,
binary, direct-access
UNIX file for efficiency and cohesion,
with fixed length records called database \fIgranules\fR.
Each object occupies one or more granules of storage.
The user sees and manipulates the directed acyclic graphs
like UNIX paths (e.g., car/chassis/door),
but in a global namespace.
There can be many independent or semi-independent
directed acyclic graphs within the same database,
each defining different models, as depicted in figure 2.2.
The figure also makes heavy use of the \fIinstancing\fR capability.
As mentioned earlier, the
\fIleaves\fR of the graph are the primitive solids.
.PP
Commands exist to import sub-trees from other databases and libraries,
and to export sub-trees to other databases.
Also, converters exist to dump databases in printable form for
non-binary interchange.
Within the database,
all points are stored as floating point numbers, in millimeters.
However, it is important to note that the 
user edits in his choice of arbitrary working units.
.NH 2
Interaction Forms
.PP
Textual and numeric interaction with the MGED editor is the most
precise editing paradigm because it allows exact
manipulation of known configurations.
This works well when the user is designing the model
from an existing drawing, or when all dimensions are known (or are computable)
in advance.
.PP
The use of a
tablet or mouse, knob-box or dial-box, buttons, and a joystick
are all simultaneously supported by MGED for analog inputs.
Direct graphic interaction via a ``point-push-pull'' editing paradigm
tends to be better for
prototyping, developing arbitrary geometry, and fitting
together poorly specified configurations.
Having both types of interaction capability available at all times
allows the user to select the style of interaction that best
meets his immediate requirements.
.NH 2
The Faceplate
.PP
When the MGED program has a display device attached, it
displays a border around the region of the screen being used
along with some ancillary status information.  Together, this
information is termed the editor ``faceplate''.
In the upper left corner of the display is a small enclosed area
which is used to display the current editor state;
this is discussed further in the Editor States section, below.
.PP
Underneath the state display is a zone in which three ``pop-up'' menus
may appear.  The top menu is termed the ``button menu'' as it
contains menu items which duplicate many of the functions assigned to
the button box.  Having these frequently used
functions available on a pop-up menu
can greatly decrease the number of times that the user needs to remove
his hand from the pointing device (either mouse or tablet puck)
to reach for the buttons.
An example of the faceplate and first level menu is shown in plate 2.1.
The second menu is used primarily for the various editing states,
at which time it contains all the editing operations which are generic
across all objects (scaling, rotation, and translation).
The third menu contains selections for object-specific editing operations.
The choices on these menus are detailed below.
It is important to note that while some display hardware that MGED runs on
has inherent support for pop-up menus included, MGED does not
presently take advantage of that support, preferring to depend
on the portable menu system within MGED instead.
It is not clear whether the slight increase in functionality that might
accrue from using display-specific menu capabilities would offset the
slight nuisance of a non-uniform user interface.
.PP
Running across the entire bottom of the faceplate is a thin rectangular
display area which holds two lines of text.
The first line always contains a numeric display of the model-space
coordinates of the center of the view and the current size of
the viewing cube, both in the currently selected editing units.
The first line also contains the current rotation rates.
The second line has several uses, depending on editor mode.
Normally it displays the formal name of the database that is being
edited, but in various editing states this second line will instead
contain certain path selection information.
When the angle/distance cursor function is activated, the second
line will be used to display the current settings of the cursor.
.PP
It is important to mention that while the database records all
positions in terms of millimeters, all numeric interaction between
the user and the editor are in terms of user-selected display units.
The user may select from millimeters, centimeters, meters, inches, and
feet, and the currently active display units are noted in the first
display line.
.PP
The concept of the ``viewing cube'' is an important one.
Objects drawn on the screen are clipped in X, Y, and Z, to the size
indicated on the first status line.
This feature allows extraneous wireframes which are positioned within view
in X and Y, but quite far away in the Z direction to not be seen,
keeping the display free from irrelevant objects when zooming in
very close to a particular part of the model.
.NH 2
Changing the View
.PP
At any time in an editing session, the user may add one or more
subtrees to the active model space.  If the viewing cube is
suitably positioned, the newly added subtrees are drawn on the display.
(The ``reset'' function can always be activated to get the entire active
model space into view).
The normal mode of operation is for users to work with wireframe
displays of the unevaluated primitive solids.  These wireframes can be
created from the database very rapidly.
.PP
On demand, the user can request the calculation of
approximate boundary wireframes that account for
all of the boolean operations specified along the arcs of the
directed acyclic graph in the database.
This is a somewhat time consuming process, so it is not used
by default, but it is quite reasonable to use whenever the
design has reached a plateau.
Note that these boundary wireframes are not stored in the database,
and are generally used as a visualization aid for the designer.
Plate 2.2 shows an engine connecting rod.
On the left side is the wireframe of the unevaluated primitives
that the part is modeled with, and on the right side is the approximate
boundary wireframe that results from evaluating the boolean expressions.
.PP
Also, at any time the user can cause any part of the active model space
to be dropped from view.
This is most useful when joining two complicated subsystems
together;  the first would be called up into the active model space,
manipulated until ready, and then the second subsystem would also be
called up as well.  When any necessary adjustments had been made
(perhaps to eliminate overlaps or to change positioning tolerances),
one of the subassemblies could be dropped from view,
and editing could proceed.
.PP
The position, size, and orientation of the viewing cube can be
arbitrarily changed during an editing session.
The simplest way to change the view is by selecting one of nine
built in preset views, which can be accomplished by a simple keyboard
command, or by way of a button press or first level menu selection.
The user is given the ability to execute a ``save view'' button/menu
function that attaches the current view to a ``restore view'' button/menu
function.
The rate of rotation around each of the X, Y, and Z axes
can be selected by knob, joystick, or keyboard command.
Because the rotation is specified as a rate, the view
will continue to rotate about the view center until the rotation
rate is returned to zero.
Similarly, the zoom rate (in or out) can be set by keyboard
command or by rotating a control dial.
Also, displays with three or more mouse buttons have binary (2x) zoom
functions assigned to two of the buttons.
Finally, it is possible to set a slew rate to translate the view
center along X and/or Y in the current viewing space, selectable
either by keyboard command or control dial.
In VIEW state, the main mouse button translates the
view center;  the button is defined to cause the indicated point to become
the center of the view.
.PP
This assignment of zoom and slew functions to the mouse buttons tends to
make wandering around in a large model very straightforward.
The user uses the binary zoom-out button to get an overall view, then
moves the new area for inspection to the center of the view and uses
the binary zoom-in button to obtain a ``close up'' view.
Plate 2.3 show such a close up view of the engine connecting rod.
Notice how the wireframe is clipped in the Z viewing direction
to fit within the viewing cube.
.NH 2
Model Navigation
.PP
In order to assist the user in creating and manipulating a complicated
hierarchical model structure, there is a whole family of editor commands
for examining and searching the database.
In addition, on all keyboard commands, UNIX-style regular-expression
pattern matching, such as ``*axle*'' or ``wheel[abcd]'', can be used.
The simplest editor command (``t'') prints a table of contents, or directory,
of the node names used in the model.  If no parameters are specified,
all names in the model are printed,
otherwise only those specified are printed.
The names of solids are printed unadorned, while the names of combination
(non-terminal) nodes are printed with a slash (``/'') appended to them.
.PP
If the user is interested in obtaining detailed information about the
contents of a node, the list (``l'') command will provide it.
For combination (non-terminal) nodes, the information about all departing
arcs is printed, including the names of the nodes referenced, the boolean
expressions being used, and an indication of any translations and rotations
being applied.
For leaf nodes, the primitive solid-specific ``describe yourself''
function is invoked, which provides a formatted display of the parameters
of that solid.
.PP
The ``tops'' command is used to find the names of all nodes which are
not referenced by any non-terminal nodes;  such nodes are either
unattached leaf nodes, or tree tops.
To help visualize the tree structure of the database,
the ``tree'' command exists to
print an approximate representation of the database subtree below the
named nodes.
The ``find'' command can be used to find the names of all non-terminal
nodes which reference the indicated node name(s).  This can be very helpful
when trying to decide how to modify an existing model.
A related command (``paths'') finds the full tree path specifications
which contain a specified graph fragment, such as ``car/axle/wheel''.
In addition to these commands, several more commands exist
to support specialized types of searching through the model database.
.KF
.PS
scale=250
box invis ht 290 wid 380 with .sw at 0,0
"\f1\s18\&Viewing\f1\s0" at 170,281
line -> from 121,267 to 45,215
"\f1\s12\&Obj EDIT\f1\s0" at 45,58
line -> from 45,167 to 45,133 
"\f1\s12\&Obj Path\f1\s0" at 45,118
line -> from 45,104 to 45,77 
"\f1\s12\&Obj Pick\f1\s0" at 45,186
line -> from 102,122 to 145,230 dotted
line -> from 97,192 to 143,230 dotted
spline -> from 40,27\
to 40,17\
to 54,0\
to 112,0\
to 150,29\
to 159,231
line -> from 320,177 to 320,147 
"\f1\s12\&Solid Pick\f1\s0" at 320,192
line -> from 256,204 to 210,230 dotted
line -> from 222,275 to 320,215 
"\f1\s12\&Solid EDIT\f1\s0" at 320,126
spline -> from 320,111\
to 320,90\
to 310,60\
to 290,40\
to 200,40\
to 180,230
.PE
.ce 1
\fBFigure 2.3 \(em Editor State Transitions\fR
.KE
.NH 2
Editor States
.PP
The MGED editor operates in one of six states, with a state transition
diagram as shown in figure 2.3.
Either of the two PICK states can be entered by button press,
menu selection, or keyboard command.  The selection of the desired
object can be made either by using \fIilluminate mode\fR, or by
keyboard entry of the name of the object.
.PP
Illuminate mode is arranged such that if there are $n$ objects visible on
the screen, then the screen is divided into $n$ vertical bands.
By moving the cursor (via mouse or tablet) up and down through these bands,
the user will cause each solid in turn to be highlighted on the screen,
with the solid's name displayed in the faceplate.
The center mouse button is pressed when the desired solid is located, causing
a transition to the next state (Object Path, or Solid Edit).
.PP
Illuminate mode offers significant advantages over more conventional pointing
methods when the desired object lies in a densely populated region of the
screen.  In such cases, pointing methods have a high chance of making an
incorrect selection.
However, in sparsely populated regions of the screen, a pointing paradigm
would be more convenient, and future versions of MGED will support this.
.NH 2
Add Primitive
.PP
Another family of commands exists to allow the user to
add more actual solids (leaf nodes) to the model database.
To obtain a precise duplicate of an existing solid (presumably to be
changed by a subsequent editing command), the copy (``cp'') command
can be used.  It is important to note that the copy operation is
different from creating an \fIinstance\fR of an existing solid;
there are occasions to use both operations.
If the precise configuration of the solid desired is not important, the
``make'' command can be used to create a stock prototype solid of the
desired type with the given name, which can then be edited to suit.
The ``mirror'' command makes a
duplicate of an existing solid reflected about
one of the coordinate axes.
.PP
If the actual numeric parameters of a solid are known, then the ``in''
command can be used.  In addition to prompting for the descriptions of
the full generic primitive solids, this command also accepts
abbreviated input formats.  For example, a wedge or an RPP can be entered
with a minimum of parameters, even though a database ARB8 is created.
Similarly, the parameters for a right circular cylinder can be given,
resulting in a truncated general cone (TGC) being stored.
This is not a very sophisticated way to build solids, but it receives
a surprising amount of use.
.PP
A number of commands also exist to create new solids with some
higher level description.  For example, the ``inside'' command
creates a new solid inside an existing solid, separated from the
existing solid by specified tolerances.  This is quite useful for
creating hollow objects such as fuel tanks.
It is possible to create a piece of metal plate with a specified
azimuthal orientation and fallback angle, or to create an ARB8 (plate)
by specifying three points and a thickness, or to create an ARB8
given one point, an azimuthal orientation, and a fallback angle.
.NH 2
Edit Primitive
.PP
There are two classes of editing operations that can be performed on
leaf nodes, the primitive solids.
The first class of operations are generic operations which can be applied to
any type of solid, and the second class of operations are those operations
which are specific to a particular type of solid.
Generic operations which can be applied to all primitive solids are all
those transformations that can be specified by a 4-by-4 homogeneous
transformation matrix;  each type of transformation can be performed
through several types of user direction.
Primitives can be rotated around the center of the viewing cube;
this rotation can be specified in degrees via keyboard command, or can
be controlled by the rotation of a set of control dials or the motions of
a three-axis joystick.
Translation of a primitive can be specified in terms of a precise new location
via keyboard command, or by adjustment of a set of control dials.
The primitive can also be moved to a designated position by pointing and
clicking with the mouse or tablet.
Uniform and single-axis (affine) scaling of a primitive can be controlled
by a numeric scale factor via keyboard command, or through repeated
analog scaling by pointing and clicking with the mouse or tablet.
.PP
Finally, the numeric parameters which define the actual primitive solid
can be edited using the user's choice of UNIX text editor (specified by
the EDITOR environment variable).
The ``tedit'' command
forms a printed representation of the solid's numeric parameters in a
temporary file and forks a sub-process to allow the user to edit that file.
When the text editor exits, MGED regains control, parses the file back into
the internal representation of the primitive, and remains in the SOLID EDIT
state to allow further modifications.
.PP
Each primitive solid also has a variety of editing operations available that
are specific to the definition of that solid.  Many of these operations are
detailed below, but all fall into one of two classes.
First, simple scalar parameters such as a radius can be entered numerically
via a single parameter keyboard command (``p''),
or they can be adjusted in analog
form by pointing and clicking with the mouse or tablet.
Secondly, defining vectors can be made to pass through a specified point,
or changed to terminate at a given point.  The particular point can be
specified by entering three parameters to the ``p'' command,
or by pointing and clicking with the mouse or tablet to ``drag'' the vector.
.NH 2
Ellipsoid Parameter Edit
.PP
Refer to figure 1.4 for an example of the parameters that control
the ellipsoid.
Most interesting transformations on an ellipsoid can be accomplished
by changing it's orientation in space using the generic operations
such as rotation and translation.
The shape (eccentricity) of the ellipsoid is controlled by varying
the relative lengths of the A, B, and C vectors;  these modifications
are controlled by this solid-specific menu:
.ne 2i
.TS
center box;
l.
ELLIPSOID MENU
=
Scale A
_
Scale B
_
Scale C
_
Scale A,B,C
.TE
.NH 2
Truncated General Cone Parameter Edit
.LP
Refer to figure 1.5 for an example of the parameters that control
the truncated general cone.
It is possible to change the length of the H, A, B, C, or D
vectors, resulting in a change in height or eccentricity of the
end plates.  The overall size of the A,B or C,D end plates can
be adjusted, or the size of both can be changed together, leaving
only the H vector constant.
The H vector can be rotated in space, either with the end plates
remaining in the same plane, or with the end plates reorienting to be
perpendicular to the H vector as it changes.
These functions are selected from this menu:
.ne 4i
.TS
center box;
l.
TGC MENU
=
scale H
_
scale A
_
scale B
_
scale c
_
scale d
_
scale A,B
_
scale C,D
_
scale A,B,C,D
_
rotate H
_
rotate A $times$ B
_
move end H (rot)
_
move end H
.TE
.NH 2
Torus Parameter Edit
.PP
Refer to figure 1.6 for an example of the parameters that control
the torus.
While the internal representation of the torus allows for elliptical
cross-sections and an elliptical overall shape, those sorts of tori
are rarely needed, and this editing menu only permits changing the
two radii of a torus with circular cross-section
and circular overall shape.
.ne 2i
.TS
center box;
l.
TORUS MENU
=
scale r1
_
scale r2
.TE
.NH 2
ARB8 Parameter Edit
.PP
Refer to figure 1.8 for examples of an ARB4 and ARB8.
ARBs are defined by their vertices, but the placements of the vertices
are not entirely free, as each face must be planar.
When an ARB is being edited, the user must specify which
\fIedge\fR is to be moved.  Then the user specifies a point in space
through which the line containing the edge must pass;  this is done
either by numerically specifying the parameters with the ``p'' command,
or by pointing and clicking with the mouse or tablet.
When editing an ARB with 8 distinct vertices, here is the
solid-specific menu that the user would see:
.ne 4i
.TS
center box;
l.
ARB8 MENU
=
move edge 12
_
move edge 23
_
move edge 34
_
move edge 14
_
move edge 15
_
move edge 26
_
move edge 56
_
move edge 67
_
move edge 78
_
move edge 58
_
move edge 37
_
move edge 48
.TE
.PP
Plate 2.4 shows the wireframe of a box modeled as an ARB8,
just after entering SOLID EDIT state but before any editing
has taken place.
Plate 2.5 shows the solid after edge ``1-4'' has been moved to
a new location.
.PP
As the number of distinct vertices in the ARB decreases, the number of
menu choices decreases as well, with more and more edge motion choices
turning into point motion choices.
Consider the ARB4 as an example of this;  an example of one is provided
in figure 1.7.
When editing an ARB with only 4 distinct vertices, here is the
solid-specific menu that the user would see:
.TS
center box;
l.
ARB4 MENU
=
move face 123
_
move face 124
_
move face 234
_
move face 134
_
move point 1
_
move point 2
_
move point 3
_
move point 4
.TE
.PP
There are several keyboard commands that apply only to ARB solids which are
being edited in SOLID EDIT state.
Once such command is ``mirface'', which replaces a designated
face of the ARB with a copy of an original face mirrored about
the indicated axis.
Another such command is ``extrude'', which projects a designated face
a given amount in the indicated direction.
.NH 2
Creating Non-Terminal Nodes
.PP
Non-terminal nodes in the directed acyclic graph stored in the database
are also called \fIcombinations\fR.
It is possible to extend the definition of a non-terminal node by
adding an instance of an existing node to the non-terminal node
with an associated boolean
operation of union;  this is done by the ``i''
(instance) command.  To start with, such an instance has an identity
matrix stored in the arc;  the user needs to separately edit the
arc to move the instance to some other location.
If the non-terminal node being extended does not exist, it is created first.
.PP
The instance command provides the simplest way to create a reference to
a another node.  Instances of a whole list of nodes can be added to a
non-terminal node by way of the group ``g'' command.
If instances of a list of nodes with non-union boolean operations
is to be added to a non-terminal node, the region ``r'' command
accepts a list of (operation, name) pairs, where the single lower case
character ``u'' indicates union, ``\(em'' indicates subtraction, and
``+'' indicates intersection.  The first operation specified
is not significant.  An example of this command might be:
.ce 1
r non-terminal u node1 \(em node2 + node3
For historical reasons,
there is no explicit grouping possible, occasionally forcing
the user to create intermediate non-terminal nodes to allow the
realization of the desired boolean formula.
It is also important to note that for the same reasons
there is an \fIimplicit\fR grouping between union terms, ie
.ce 1
u n1 \(em n2 + n3 u n4 \(em n5
is evaluated as
.ce 1
(n1 \(em n2 + n3) union (n4 \(em n5)
rather than
.ce 1
((((n1 \(em n2) + n3) union n4) \(em n5)
.PP
MGED contains a few high-level operations implemented as built-in
commands;  the most interesting one of these makes an articulated
track for a vehicle given the locations of the drive, idler, and road
wheels.
It is straightforward to create similar domain-specific built-in
capabilities as desired, merely by adding another function to the
command processor.
.NH 2
Edit Non-Terminal
.PP
Before being able to enter the OBJECT EDIT state
(i.e. edit non-terminal),
it is necessary to pass through two intermediate states
in which the full path of an object to be edited is specified,
and the location of one arc along that path is designated for editing.
It is possible to create a transformation matrix to be applied
above the root of the tree, affecting everything in the path,
or to apply the matrix between any pair of nodes.
For example, if the full path /car/chassis/door is specified,
the matrix could be applied above the node ``car'', between
``car/chassis'', or between ``chassis/door''.
.PP
The transformation matrix to be applied at the
designated location can be created by the concatenation of
operations, each specified through several types of user direction.
Trees can be rotated around the center of the viewing cube;
this rotation can be specified in degrees via keyboard command, or can
be controlled by the rotation of a set of control dials or motions on
a three-axis joystick.
Translation of trees can be specified in terms of a precise new location
via keyboard command, or by adjusting a set of control dials.
Tree translation can also be accomplished by pointing and
clicking with the mouse or tablet.
Uniform and single-axis (affine) scaling of a tree can be controlled
by a numeric scale factor via keyboard command, or by way of repeated
analog scaling by pointing and clicking with the mouse or tablet.
.NH 2
Miscellany
.PP
MGED has a substantial number of commands which defy easy categorization;
some of these commands will be described in this section.
The ``analyze'' command is used to obtain a simple analysis
about a single primitive object, including the
plane equations, surface area, azimuth and fallback angles of each face,
plus the lengths of each edge and the volume of the enclosed space,
both in terms of cubic user units, and also in terms of fluid capacity.
.PP
Given that the current view is of the evaluated boundaries of the
solids, one can obtain a reasonable estimate of the presented area
of the components from the current viewing direction by using
the ``area'' command.
.PP
It is possible to view, specify, and text-edit
information pertaining to the material type and color of various
parts of the model tree.  This is an interim capability
intended to provide enough material properties information for
current rendering and analysis purposes until the design of a
full material properties database can be finalized.
.PP
In addition to a variety of usual database manipulation
and status commands, there are commands to
compare the current database for name overlap (conflicts)
with another database, as well as commands to import and export
subtrees to/from the current database.
If name conflicts between the two databases
do exist, there are commands to rename an individual node without
changing any of the references to it (``mv''), or to rename
a node and change all the references to it (``mvall'').
Another command which is useful for preparing to move subtrees between
databases is the ``push'' command,
which adjusts the transformation matrices from the indicated point
down to the leaves of the directed acyclic graph, leaving the higher
level arcs with identity matrices.
.NH 2
Output Features
.PP
The ``plot'' command can store an exact image of the current
(non-faceplate) display on the screen, either using the
System V standard 2-D monochrome UNIX-Plot (\fIplot(4)\fR) format,
or the BRL 3-D color extended-UNIX-Plot format.
These plots can be sent to a disk file,
or ``piped'' directly to a filter process.
This can be useful for making hard copies of the current MGED view
for showing to others,
using a local pen plotter or laser printer.
.PP
An important capability even beyond the ability to generate an
evaluated boundary wireframe is the ability of MGED to initiate a
quick ray-trace rendering of the current view on any nearby framebuffer!
This is implemented by using the MGED ``rt'' command to fork off
an instance of the RT program, and sending the RT program
a description of the current view
with any user-specified options.
This allows the designer to
use the power of MGED to select the desired view, and then to
quickly verify the geometry and light source placement.
A 50 by 50 pixel rendering of the current view can usually be done
in less than a minute (on a DEC VAX-780 class processor), and allows
for general verification before the designer uses the ``saveview''
command to submit a batch job for a high resolution ray-trace of
the same view.
.NH 2
Animation
.PP
The MGED editor includes a number of features which are useful
for developing animation tools and scripts.
The full description of the current viewing transformation and eye position
can be saved in a file,
and such a previously saved view can be read back at any time,
immediately changing the editor's view.
In addition, the current viewing transformation and eye position can be
appended to a file containing a collection of keyframes.
Most importantly, a file full of keyframe information, either raw keyframe
positions or smoothly interpolated keyframe sequences, can 
by ``played'' in real time using MGED,
providing a powerful and fast animation preview capability.
.PP
As a separate animation capability intended
for developing demonstrations and instructional material relating to the
use of the MGED editor,
all user interactions with the editor can be recorded in a file,
along with an indication of the time elapsed between user actions.
This file can be  adjusted using a normal text editor to remove any errors,
or to eliminate dead time where the user stopped to think.
Once created, this session script can be replayed through the editor
at any time, either to provide a smooth ``canned'' demonstration
before a live audience, or to create a film or videotape.
.NH 2
Model Building Philosophy
.PP
The power of a full directed acyclic graph structure for representing
the organization of the database gives a designer a great deal of
flexibility in structuring a model.
In order to prevent chaos, most designers at BRL choose to
design the overall structure of their model in a top-down manner,
selecting meaningful names for the major structures and sub-structures
within the model.
Actual construction of the details of the 
model generally proceeds in a bottom-up
manner, where each sub-system is fabricated from component primitives.
.PP
The first sub-systems to be constructed are the chassis and skin of the
vehicle, after which a set of analyses are run to validate the geometry,
checking for unintentional gaps in the skin or for solids which overlap.
The second stage of model construction is to build the features of the
main compartments of the vehicle.  If necessary for the analysis
codes that will be used, the different types of air compartments within
the model also need to be described.
The final stage of model construction is to build the internal
objects to the desired level of detail.
This might include modeling engines, transmissions, radios
people, seats, etc.
In this stage of modeling, the experienced designer will draw heavily on the
parts-bin of model components and on pieces extracted from earlier
models, modifying those existing structures to meet his particular
requirements.
.PP
Throughout the model building process it is important for the model builder
to choose part names carefully, as the MGED database currently has a
global name space, with individual node names limited to 16 characters.
In addition, BRL has defined conventions for naming the elements in the
top three levels of database structure so that people will be able to
easily navigate within models prepared at
different times and by different designers,
facilitating the integration of design changes into old models with
a minimum of difficulty.
.NH 1
Interrogating the Model:  Ray-tracing
.NH 2
What Applications Want and Need
.PP
The objective of a given application will to a large degree determine the
most ``natural'' form in which the model might be presented.
For example, extracting just the \fIedges\fR of the objects in a model
would be suitable for a program attempting to construct a wire-frame display
of the model.
Another family of applications exists which needs to be able to find
the intersection of small object paths (eg, photons) with the
model.
Generally, these alternatives are motivated by the representation of
a physical process being simulated, and each alternative
is useful for a whole family of applications.
By choosing the ray sampling density
within the Nyquist limit, these applications are well satisfied by
extracting ray/geometry intersection information,
the well known ``ray-tracing'' algorithm.
However, a mathematical ray has as its cross section a point,
while physical objects have significant cross-sectional area.
This lack of cross-sectional area can result in sampling inaccuracies, and
has lead some applications developers to try to
minimize these difficulties.  Applications which simulate
particles or small rocks approaching the model might benefit
from cylinder/geometry intersection
capability, and applications which shine beams of light on the model
such as spotlights or
even highly collimated light such as laser light might benefit from
cone/geometry intersection capabilities.
.[
Amanatides ray tracing cones
.]
.[
Kirk simulation natural features using cone tracing
.]
Applications which are attempting to simulate wave effects might
be well expressed in terms of plane/geometry intersection curves,
and structural analysis routines would probably prefer to obtain
the geometry as a collection of connected hyperpatches.
.PP
While very recent research has begun to explore techniques for
intersecting cylinders, cones, and planes with geometry,
.[
Kajiya ray tracing procedurally defined objects
.]
ray-tracing is by far the most well developed approach.
Fortunately, most applications can function well with approximate,
sampled data about the model, rather than needing a precise
representation.
Data with statistical validity
can be obtained by sampling the model with
an adequate number of rays and computing the ray/geometry intersections.
This approach is also by far the easiest one to implement,
as the one-dimensional nature of a mathematical ray makes the
intersection equations relatively straightforward.
.PP
Given that one has decided to force all applications to interrogate
the model strictly by computing ray/geometry intersections,
there are still several implementation strategies that could be
adopted.  The most traditional approach has been batch-oriented,
with the user defining a set of ``viewing angles'',
turning loose a big batch job to compute all the ray intersections,
and then post-processing all the ray data into some meaningful form.
However, the major drawback of this approach is that the application
has no immediate control over ray paths, making another batch run
necessary for each level of reflection, etc.
.PP
In order to be successful, applications need: (1) interactive control of ray
paths, to naturally implement reflection, refraction, and fragmenting into
multiple subsidiary rays, and (2) the ability to fire rays in arbitrary
directions from arbitrary points.
Nearly all non-batch implementations have closely
coupled a specific application (typically a model of illumination) with the
ray-tracing code, allowing efficient and effective control of the ray paths.
The most flexible approach of all is to implement the ray-tracing
capability as a general-purpose library, and make the functionality
available as needed to any application.
.NH 2
References
.PP
The origins of modern ray-tracing come from work at MAGI
under contract to BRL, initiated in the early 1960s.
The initial results were reported by MAGI
.[
geometric description technique MAGI
.]
in 1967.
Extensions to the early developments were undertaken by a
DoD Joint Technical Coordinating Group effort, resulting in
publications in 1970
.[
MAGIC User Manual
.]
and 1971.
.[
MAGIC Analyst Manual
.]
The detailed presentation of the
fundamental analysis and implementations of the ray-tracing algorithm
found in these two documents forms an excellent and thorough
review of the principles of solid modeling.
.PP
More recently, interest in ray-tracing developed in the academic
community, with Kay's
.[
Kay Ray Tracing 1979
.]
thesis in 1979
being a notable early work.
One of the central papers in the ray-tracing literature is
the work of Whitted.
.[
Whitted Improved Illumination Model
.]
Model sampling techniques can be improved to provide substantially
more realistic images by using the ``Distributed Ray Tracing'' strategy.
.[
Cook Carpenter Distributed Ray Tracing
.]
For an excellent, concise discussion of ray-tracing,
consult pages 363-381 of Rogers.
.[
Rogers Procedural Elements
.]
.NH 2
Ray -vs- Geometry
.PP
The process of intersecting one ray with the model geometry
can be decomposed into two distinct tasks.
First, the ray must be intersected with each and every primitive
solid in the model.  Each successful intersection will result in
a set of line segments being returned.
Secondly, the boolean combinations expressed in the
model's directed acyclic graph must be evaluated over this
collection of line segments.
.PP
We will examine the details of intersecting a
ray with a halfspace, a generalized ARB, and an ellipsoid.
These three analyses provide all the information necessary to
enable one to intersect a ray with any solid possessing
a quadratic surface.  For example, a truncated general cone
can be dealt with as an infinite cylinder (a quadratic)
bounded by two planes.  The extension to surfaces of higher
order is straightforward, and depends only on having a
reliable root-finding algorithm.
Information about ray-tracing of spline objects can be found in a recent
paper by Sweeny.
.[
Sweeny Ray Tracing
.]
.PP
Rays begin at a point $bold P vec$,
and proceed infinitely in a given direction $bold D vec$.
Any point $bold A vec$ on a ray may be expressed as a linear
combination of $bold P vec$ and $bold D vec$:
.EQ C
bold A vec ~=~ bold P vec ~+~ k ~*~ bold D vec
.EN
where valid solutions for $k$ are in the range $[ 0, inf )$.
$( bold D sub x , bold D sub y , bold D sub z )$ are the
\fIdirection cosines\fR for the ray, being the cosine of
the angle between the ray and the appropriate axis.
While not necessary, in this analysis it is assumed that
$bold D vec$ is of unit length, i.e. $| bold D vec | = 1$.
.NH 2
Ray/Halfspace Intersection
.PP
Consider a plane with arbitrary orientation.  This plane
partitions space into two half-spaces.  Define 
$bold N vec$ to be an outward-pointing unit-length vector
which is normal to the plane.
Let point $bold A vec$ lie anywhere on the plane.
Let the ray in question be defined such that any point $bold X vec$
on the ray may be expressed as
$bold X vec = bold P vec + k bold D vec$.
.PP
Determine if the ray is parallel to the surface of the plane, and
if not, determine if the ray is entering or exiting the half-space
by comparing the direction of the ray with the direction of the
normal $bold N vec$:
.EQ
bold N vec cdot bold D vec ~=~ left {
lpile { 0 above >0 above <0 }
~~ roman lpile {
parallel,~no~solution above
exiting~half-space,~segment~t=[ 0 , k ] above
entering~half-space,~segment~t=[ k , inf ) }
.EN
.PP
If a solution exists, i.e. $bold N vec cdot bold D vec != 0$,
find parameter $k$ for intersection of ray and plane.
To accomplish this, a useful form for the equation of the plane is
$bold N vec cdot ( bold X vec - bold A vec ) = 0$,
where the vector from any point on the plane ($bold A vec$)
is tested for perpendicularity with the normal $bold N vec$.
To find $k$, we substitute the parametric version of $bold X vec$, giving:
.EQ
bold N vec cdot ( bold P vec + k * bold D vec - bold A vec ) = 0
.EN
.EQ
bold N vec cdot bold P vec + k ( bold N vec cdot bold D vec ) -
bold N vec cdot bold A vec = 0
.EN
.br
.EQ
k = { bold N vec cdot bold A vec - bold N vec cdot bold P vec }
over { bold N vec cdot bold D vec }
.EN
.KF
.PS
scale=300
box invis ht 201 wid 526 with .sw at 0,0
circle rad 8 at 496,41
circle rad 8 at 88,65
line -> from 88,65 to 24,129 
line  from 16,41 to 24,25 
line  from 40,49 to 48,33 
line  from 64,57 to 72,41 
line  from 112,73 to 120,57 
line  from 136,81 to 144,65 
line  from 160,89 to 168,73 
line  from 184,97 to 192,81 
line  from 208,105 to 216,89 
line  from 232,113 to 240,97 
line  from 280,129 to 288,113 
line  from 304,137 to 312,121 
line  from 328,145 to 336,129 
line  from 352,153 to 360,137 
line  from 16,41 to 352,153 
line -> from 496,41 to 16,201 
spline  from 256,121\
to 248,82\
to 313,82\
to 341,79\
to 352,65\
to 352,41
"\f1\s12\&N\f1\s0" at 8,133
"\f1\s12\&A\f1\s0" at 112,29
"\f1\s12\&k\f1\s0" at 344,13
"\f1\s12\&P\f1\s0" at 520,61
"\f1\s12\&D\f1\s0" at 400,93
spline  from 496,41\
to 474,16\
to 450,16\
to 400,57\
to 376,57\
to 352,41
circle rad 8 at 256,121
.PE
.ce 1
\fBFigure 3.1 \(em Ray/Halfspace Intersection\fR
.KE
.NH 2
Ray/ARB Intersection
.PP
An ARB is a convex volume bounded by
4 (pyramid), 5 (wedge), or 6 (box) planes.
This analysis depends on the properties of objects with convex hulls.
Let the ray in question be defined such that any point $bold X vec$
on the ray may be expressed as
$bold X vec = bold P vec + k bold D vec$.
Intersect the ray with each of the
planes bounding the ARB as discussed above,
and record the values of the
parametric distance $k$ along the ray.
With outward pointing normal vectors, note that the
ray \fIenters\fR the half-space defined by a plane when
$bold D vec cdot bold N vec < 0$,
is \fIparallel\fR to the plane when $bold D vec cdot bold N vec = 0$,
and \fIexits\fR otherwise.
Find the \fIentry\fR point farthest away from the starting point $bold P vec$,
i.e. it has the largest value of $k$ among the entry points.
The ray enters the solid at this point.
Similarly, find the \fIexit\fR point closest to point
$bold P vec$, i.e. it has the smallest value of $k$ among the exit points.
The ray exits the solid here.
.KF
.PS
scale=300
box invis ht 319 wid 574 with .sw at 0,0
line  from 261,18 to 436,311 
line  from 384,226 to 376,232 
line  from 375,210 to 367,216 
line  from 367,195 to 359,200 
line  from 356,179 to 348,185 
line  from 346,163 to 338,169 
line  from 337,148 to 329,154 
line  from 327,131 to 319,137 
line  from 318,115 to 310,121 
line -> from 355,17 to 29,302 
"\f1\s12\&P\f1\s0" at 383,13
"\f1\s12\&D\f1\s0" at 337,66
spline  from 262,99\
to 268,121\
to 257,134\
to 232,138\
to 223,144\
to 219,161\
to 224,168
line  from 192,92 to 189,102 
line  from 208,94 to 205,104 
line  from 224,96 to 221,106 
line  from 240,97 to 237,107 
line  from 303,103 to 300,113 
line  from 287,101 to 284,111 
line  from 383,249 to 383,241 
line  from 367,249 to 367,241 
line  from 351,249 to 351,241 
line  from 335,249 to 335,241 
line  from 319,249 to 319,241 
line  from 303,249 to 303,241 
line  from 287,249 to 287,241 
line  from 272,249 to 272,241 
line  from 256,249 to 256,241 
line  from 240,249 to 240,241 
line  from 224,249 to 224,241 
line  from 208,249 to 208,241 
line  from 192,249 to 192,241 
circle rad 8 at 291,71
circle rad 8 at 262,99
circle rad 8 at 175,174
circle rad 8 at 89,249
circle rad 8 at 355,17
line  from 0,249 to 534,249 
line  from 8,74 to 574,130 
spline  from 175,174\
to 189,185\
to 202,176\
to 202,167\
to 211,154\
to 218,157\
to 226,160
line  from 177,234 to 188,234 
line  from 177,219 to 188,219 
line  from 176,201 to 187,201 
line  from 175,187 to 186,187 
line  from 174,155 to 185,155 
line  from 173,139 to 184,139 
line  from 173,123 to 184,123 
line  from 172,107 to 183,107 
line  from 178,319 to 168,11 
.PE
.ce 1
\fBFigure 3.2 \(em Ray/ARB Intersection\fR
.KE
.NH 2
Ray/Ellipse Intersection
.PP
Let the point $W$ belong to the set of points
on the surface of an ellipsoid which is defined by
$bold V vec , bold A vec , bold B vec , bold C vec$, where $bold V vec$
is the center of the ellipsoid, and $bold A vec$, $bold B vec$,
and $bold C vec$ are mutually perpendicular and define the orientation
and shape of the ellipsoid.
By affine transformations, map the points on the
original ellipsoid into the set of points $W hat$ in the ``hat'' space
which lie on the surface of a unit sphere, located at the origin.
For any point $X$, the corresponding point in the ``hat'' space is
$X hat = S(R( X - V ))$,
where
.EQ
R( X ) = left [ pile {
{ A vec / ( | A vec |) }
 above { B vec / ( | B vec | ) }
 above { C vec / ( | C vec | ) }
} right ] ~*~ X
.EN
and
.EQ
S(X) =	 left [ matrix {
col { 1 / | A vec | above 0 above 0 }
col { 0 above 1 / | B vec | above  0 }
col { 0 above 0 above  1 / | C vec | }
} right ] ~*~ X
.EN
Intersect this ellipse with a ray;
points on the ray $L$ are of the form $P + k * D$.
This can be be expressed as the intersection of
the ray in ``hat'' space with the unit sphere, where
points on the ray $L hat$ are of the form $P hat + k hat * D hat$.
The mapping between regular and ``hat'' space for vectors is:
.EQ
D hat = S( R( D ) )
.EN
and for points is:
.EQ
P hat = S( R( P - V ) )
.EN
With $W$ defined to be the point where ray $L$ intersects the ellipsoid,
and $W hat$ is the point where $L hat$ intersects the unit sphere, then
.EQ
W hat = P hat + k hat * D hat
.EN
and
.EQ
W hat = S ( R ( W - V ) )
.EN
.LP
In order to find the point $W hat$, we refer to the definition for
a sphere with unit radius located at the origin
.EQ
x sup 2 + y sup 2 + z sup 2 ~=~ 1
.EN
and substitute in the parametric definition of $W hat$, giving
.EQ
( P hat sub x + k hat * D hat sub x ) sup 2 ~+~
( P hat sub y + k hat * D hat sub y ) sup 2 ~+~
( P hat sub z + k hat * D hat sub z ) sup 2 ~=~ 1
.EN
Regrouping terms as a polynomial in $k hat$ gives
.EQ
( D hat sub x sup 2 + D hat sub y sup 2 + D hat sub z sup 2 )
 k hat sup 2 ~+~
2 * ( D hat sub x P hat sub x +
     D hat sub y P hat sub y +
     D hat sub z P hat sub z ) k hat
~+~ P hat sub x sup 2 + P hat sub y sup 2 + P hat sub z sup 2 - 1 ~=~ 0
.EN
.br
.EQ
( D hat cdot D hat ) k hat sup 2 ~+~ 2 ( D hat cdot P hat ) k hat ~+~
[ ( P hat cdot P hat ) - 1 ] ~=~ 0
.EN
Solving the quadratic equation for $k hat$ yields 0, 1, or 2 roots
.EQ
k hat = {
  -2 ( D hat cdot P hat ) +- sqrt {
    [ 2 ( D hat cdot P hat ) ] sup 2
      - 4 ( D hat cdot D hat ) [ ( P hat cdot P hat ) - 1 ]
    }
} over {
    2 ( D hat cdot D hat )
}
.EN
.br
.EQ
k hat = {
     - ( D hat cdot P hat ) +- sqrt {
        ( D hat cdot P hat ) sup 2
           - ( D hat cdot D hat ) [ ( P hat cdot P hat ) - 1 ]
    }
} over {
    ( D hat cdot D hat )
}
.EN
.LP
If a solution for $k hat$ exists, these values of $k hat$
define the intersection point(s) $W hat$.  In order to determine
$W$, the relationship between $k hat$ and $k$ needs to be found.
.EQ
W hat mark = P hat + k hat * D hat
.EN
.br
.EQ
W hat lineup = S ( R ( W - V ) )
.EN
can be rearranged in terms of $W$
.EQ
W lineup = V + R sup -1 ( S sup -1 ( W hat ) ) 
.EN
Then, substituting in the parametric form of $W hat$
.EQ
lineup = V + R sup -1 ( S sup -1 [ P hat + k hat * D hat ] ) 
.EN
.br
.EQ
lineup = V + R sup -1 ( S sup -1 [ S( R( P - V ) ) + k hat * S( R( D ) ) ] )
.EN
.br
.EQ
lineup = V + R sup -1 ( R( P - V ) + k hat * R( D ) )
.EN
.br
.EQ
lineup = V + ( P - V ) + k hat * D
.EN
.br
.EQ
W lineup = P + k hat * D
.EN
but,
.EQ
W lineup = P + k * D
.EN
so $k = k hat$.
This useful result is not surprising because
affine transformations
applied to straight lines yield straight lines, and
$R$ and $S$ are both affine transformation matrices.
The fact that $k$ is constant for both $W$ and $W hat$ means that
the solution for $k hat$ can be determined from $D hat$ and $P hat$
without needing to transform the results out of the ``hat'' space.
.LP
Given that we can find the point $W hat$
where ray $L hat$ intersects the unit sphere and
the point $W$ where ray $L$ intersects the ellipsoid, what is the vector
normal to the tangent plane at that point?
The tangent plane on the unit sphere at $W hat$ has
normal vector $N hat ~=~ W hat$.
(The vector from the origin to any point on the surface of the sphere
is pointing in the direction of the tangent at that point).
.EQ
N hat mark = W hat = S ( R ( W - V ) )
.EN
The tangent plane at $W hat$ transforms back to the tangent plane at $W$,
with normal vector $N vec$:
.EQ
N vec lineup = { [ { ( R sup -1  *  S sup -1 ) } sup T ] } sup -1 ( N hat )
.EN
because if $H vec$ is perpendicular to plane $Q$, and matrix $M$ maps
from $Q$ to $Q hat$,
then ${ [ { M } sup T ] } sup -1 ( H vec )$ is perpendicular to $Q hat$.
.EQ
N vec lineup = { [ { ( S sup -1 ) } sup T * { ( R sup -1 ) } sup T ] } sup -1
  ( N hat )
.EN
Because $( R sup -1 ) sup T = R$ and $S sup T = S$,
.EQ
N vec lineup = { [ S sup -1 * R ] } sup -1 ( N hat )
.EN
.EQ
lineup = R sup -1  * S ( N hat )
.EN
.EQ
lineup =  R sup -1 ( S( S( R( W - V ) ) ) )
.EN
Note that $| N vec | != 1$.
.NH 2
Boolean Evaluation
.PP
In the context of the three dimensional model, each ray passes
through zero or more objects, but the objects are
defined in terms of a boolean combination of primitive solids.
The first part of the task is to intersect the ray with
each and every primitive solid in the model.
For each solid,
either the ray will miss, in which case nothing further need be done,
or the ray will intersect the solid in one or more line segments.
When all of the primitive solids have been intersected, the
segments have to be sorted, and ``woven'' together into
intervals.  The original ray is broken into a new interval
at each point where a primitive solid was entered or exited;
the list of primitive solids intersected is constant within each interval.
Note that the correct entry and exit normals must be selected
each time a segment is broken into an additional interval.
.PP
After all the segments are woven together into intervals, each
interval needs to be applied to the boolean expression tree.
For all primitive solids in the expression tree,
if a segment is present within an interval,
the expression tree sees a TRUE input, otherwise a FALSE input is presented.
For all intervals in which the expression tree returns a TRUE output,
the ray has passed through an actual solid object, and that interval
is added to the solution list for this ray/model intersection.
Note that by keeping the interval list sorted front-to-back
in increasing $k$, and by
incrementally weaving new segments into the interval list as they
are computed, applications such as lighting models which are
only interested in the first intersection with a solid object
can be processed much more efficiently by stopping the intersection
process after the first hit.
.KF
.PS
scale=300
box invis ht 700 wid 719 with .sw at 0,0
box ht 8 wid 248 with .nw at 371,82 
box ht 8 wid 304 with .nw at 315,114 
line  from 467,536 to 467,0 
line  from 619,538 to 619,2 
box ht 89 wid 200 with .nw at 267,407 
box ht 2 wid 697 with .nw at 1,370 
line -> from 697,369 to 719,369 
ellipse ht 162 wid 300 at 467,363
circle rad 184 at 187,376
line  from 3,536 to 3,0 
line  from 267,536 to 267,0 
line  from 315,536 to 315,0 
line  from 371,536 to 371,0 
box ht 8 wid 368 with .nw at 3,176 
box ht 8 wid 200 with .nw at 267,144 
.PE
.ce 1
\fBFigure 3.3 \(em Boolean Evaluation\fR
.KE
.NH 2
Bounding Volumes & Space Partitioning
.PP
Part of the computational expense of ray-tracing derives from the
statement that ``the first part of the task is to intersect the ray with
each and every primitive solid in the model'' results in a
an enormous amount of computation.
Much of the recent research in ray-tracing techniques has focused
on strategies for reducing the the amount of computation required.
Overall, the goal is to develop methods to avoid computing the
actual ray/solid intersections when the ray does not pass near the solid.
.PP
The first method for eliminating unnecessary ray/solid intersections
involves enclosing the solid within a \fIbounding solid\fR.
Before computing the intersection of a ray with the actual primitive
solid, the ray is first intersected with the bounding solid
to reject obvious misses.  This is only effective if the cost of
computing the intersection with the bounding solid is significantly
less than the cost of intersecting the ray with the primitive solid.
Spheres, axis-aligned right-parallelpipeds (RPPs), and boxes
are the three most popularly used bounding volumes.
An important issue is the measure of the quality of
a bounding volume.  The desire is to minimize
$VOL sub bound ~-~ VOL sub geom$, but
each bounding volume is a poor fit for some objects.
The sphere is a poor bound for any object which is long and thin.
Axis-aligned RPPs are poor bounds for any object where the
greatest width is not axis aligned.  The torus represents
a solid that is very hard to bound well at all.
.PP
The best bounding sphere has it's center located at the centroid
of the primitive solid, with the radius $r$ set to the smallest
possible value that encloses the entire primitive solid.
Then, to determine if a ray needs to be intersected with the
primitive solid, it is merely necessary to determine if
the distance from the sphere center $bold V vec$
to line $bold P vec ~+~ k * bold D vec ~<= r$, i.e.
.EQ
left | {
( bold V vec - bold P vec ) times
{ bold D vec } over { | bold D vec | }
} right |
~<=~ r
.EN
When $| bold D vec | = 1$, this can be quite fast to compute.
Another way to speed the calculation of this would be to
compare the magnitude squared to the radius squared,
eliminating the necessity for taking a square root in finding
the distance.
.KF
.PS
scale=300
box invis ht 458 wid 614 with .sw at 0,0
spline  from 303,255\
to 303,287\
to 271,311\
to 223,287\
to 196,321
"\f1\s12\&D\f1\s0" at 174,20
"\f1\s12\&P\f1\s0" at 6,20
"\f1\s12\&dist\f1\s0" at 366,204
"\f1\s12\&V\f1\s0" at 334,292
"\f1\s12\&r\f1\s0" at 198,340
circle rad 8 at 38,8
line  from 302,256 to 100,256 
circle rad 8 at 302,256
line -> from 38,8 to 614,200 
line  from 366,144 to 374,120 
line  from 342,136 to 366,144 
line  from 302,256 to 350,112 
circle rad 202 at 302,256
spline  from 100,256\
to 100,288\
to 132,312\
to 180,288\
to 204,321
.PE
.ce 1
\fBFigure 3.4 \(em Bounding Sphere\fR
.KE
.PP
A bounding RPP
is defined by six numbers giving the extent of the RPP along each of
the three axes, i.e. $MIN sub { x,y,z }$ and $MAX sub { x,y,z }$.
Cyrus and Beck
.[
Cyrus Beck clipping
.]
provide an efficient algorithm for intersecting
the ray with the six planes of the RPP.  By taking advantage of
the fact that all six planes are axis-aligned, the plane intersection
equations are greatly simplified, and the following algorithm
(written in pseudo-\fBC\fR) provides the fastest possible
ray/RPP intersection, with a computational cost very close
to the cost of computing the distance from a bounding sphere.
(Assuming that the division by $D sub i$ is replaced with a multiplication
by the inverse, which is calculated once per ray).
.br
.nf
for( i = x, y, z )  {
    if( $D sub i$ == 0 )  {
        if( $MIN sub i$ > $P sub i$ )  return(MISS);
        if( $MAX sub i$ < $P sub i$ )  return(MISS);
    } else if( $D sub i$ > 0 )  {
        /* Heading toward larger numbers */
        if( $MAX sub i$ < $P sub i$ )  return(MISS);
        k = $(MAX sub i - P sub i ) / D sub i$;
        if( maxK > k )  maxK = k;
        k = $(MIN sub i - P sub i ) / D sub i$;
        if( minK < k )  minK = k;
    } else {
        /* $D sub i$ < 0, heading to smaller numbers */
        if( $MIN sub i > P sub i$ )  return(MISS);
        k = $(MIN sub i - P sub i ) / D sub i$;
        if( maxK > k )  maxK = k;
        k = $(MAX sub i - P sub i ) / D sub i$;
        if( minK < k )  minK = k;
    }
}
if( minK > maxK )  return(MISS);
.fi
If the ray intersects the RPP at all, it does so in the range (minK, maxK).
.PP
Space partitioning is an efficiency strategy which
only intersects rays with bounding volumes that are "near" the path of
the ray, and avoids finding intersections in irrelevant areas of the model.
.[
Glassner space subdivision
.]
.[
Fujimoto accelerated ray tracing
.]
.[
Fujimoto fast elaboration geometry
.]
.PP
Bin-trees
enclose all of model space with 6 axis-aligned planes (an RPP), and
split the RPP with a single plane carefully chosen to reduce complexity
of at least one side of the tree by one solid.
Lists of the contents of both new RPPs are made, and then
both new RPPs are recursed into until the list of contents is ``small''.
When a ray is to be fired,
find the first RPP the ray enters by walking the tree,
making binary decisions at each node.
When a leaf node is found in the space partitioning tree,
fire rays at solids listed (or their bounding volumes).
.PP
Oct-Trees operate similarly, except that at each node space is
uniformly split by planes in X, Y, and Z.
.NH 2
RT Library Interface
.PP
In order to give all applications interactive control over
the ray paths, and to allow the rays to be fired in arbitrary directions
from arbitrary points, BRL has implemented its second generation
ray-tracing capability as a set of library routines.
The RT library exists to allow application programs to
intersect rays with model geometry.  There are two parts to the
interface: preparation routines and the actual ray-tracing routine.
Three "preparation" routines exist;  the first routine which must be called is
dir_build(), which opens the database file, and builds the
in-core database table of contents.
The second routine to be called is get_tree(), which
adds a database sub-tree to the active model space.
get_tree() can be called multiple times
to load different parts of the database
into the active model space.
The third routine is rt_prep(), which
computes the space partitioning data structures, and does other
initialization chores, prior to actual ray-tracing.
Calling this routine is optional,
as it will be called by shootray() if needed.
rt_prep() is provided as a separate routine to
facilitate more accurate timing of the preparation and ray-tracing phases of
applications.
.PP
To compute the intersection of a ray with the geometry in the
active model space, the application must call shootray() once for each
ray.
Ray-path selection for perspective, reflection, refraction, etc,
is entirely determined by the applications program, and passed as a parameter
to shootray() in the RT ``application'' structure, which contains five
major elements:
the vector a_ray.r_pt ($bold P vec$) which is
the starting point of the ray to be fired,
the vector a_ray.r_dir ($bold D vec$) which is
the unit-length direction vector of the ray,
the pointer *a_hit() which is the address of an application-provided
routine to call on those rays where some geometry is hit by the ray,
the pointer *a_miss() which is the address of an application-provided
routine to call on those rays where the ray does not hit any geometry,
the flag a_onehit which is set non-zero to stop ray-tracing
as soon as the ray has intersected at least one piece of geometry
(useful for lighting models),
plus various locations for applications to store state
(recursion level, colors, etc).
Note that
the return from the application provided a_hit()/a_miss() routine
is the formal return of the function shootray().
The shootray() function is prepared for full recursion so that
the application provided a_hit()/a_miss() routines can themselves
fire additional rays by calling shootray() recursively before deciding their
own return value.
In addition, the function shootray() is fully prepared to be operating
in parallel with other instances of itself in the same address space,
allowing the application to take advantage of parallel hardware capabilities
where such exist.  This has actually been successfully demonstrated on
the Denelcor HEP H-1000 machine and on the Alliant FX/8.
.NH 2
Sample RT Application
.PP
A simple application program that fires one ray at a model and prints
the result is included below, to demonstrate the simplicity of the
interface to the RT library.
.LP
.nf
struct application ap;
main() {
      dir_build("model.g");
      get_tree("car");
      rt_prep();
      ap.a_point = [ 100, 0, 0 ];
      ap.a_dir = [ -1, 0, 0 ];
      ap.a_hit = &hit_geom;
      ap.a_miss = &miss_geom;
      ap.a_onehit = 1;
      shootray( &ap );
}
hit_geom(app, part)
struct application *app;
struct partition *part;
{
      printf("Hit %s", part->pt_forw->pt_regionp->reg_name);
}
miss_geom(){
      printf("Missed");
}
.fi
.NH 2
RT Shootray
.PP
To show the simplicity of the overall ray-tracing algorithm, and
to provide the reader with enough information to be able to implement
a full ray-tracing package, the RT shootray() function is
presented.
.LP
.nf
shootray(app)
struct application *app;
{
      if( ray outside model RPP )  return( a_miss() );
      do "push" from box to box  {
            for all solids in box {
                  check bounding RPP
                  invoke SHOOT on solid, collect segment list
            }
            bool_weave():  add segs to interval list
            if( app->a_onehit > 0 )  {
                  bool_final()
                  if( any geometry hit )  break;
            }
      }
      bool_final();
      if( any geometry hit )
            call a_hit();
      else
            call a_miss();
}
.fi
.PP
The overall strategy here is simple, and only the addition of the space
partitioning ``box'' (voxel) notion adds any complexity.  If the ray
does not even intersect the model RPP, then call a_miss().
Otherwise, examine every box (voxel) that the ray pierces, in increasing
distance from the starting point $bold P vec$.  For every solid inside
each voxel, call the SHOOT routine appropriate for that type of solid,
and collect the resultant lists of intersection segments.  After
processing all the solids in the voxel, call bool_weave() to sort
the segments into the interval list, creating additional intervals
where segments overlap.  If the a_onehit flag is set, call bool_final()
to evaluate the boolean expressions on the sorted interval list;  if
any interval evaluates as TRUE, then break the loop and call a_hit().
When all voxels have been examined, call bool_final(), and call a_hit()
or a_miss() as appropriate.
.PP
It is important to note that the BRL MGED and RT software is available
from BRL at no cost
by writing to the author.  In this way, the author hopes to prevent
the implementation of more ray-tracers, and focus attention onto
more fruitful areas of research, such as developing more sophisticated
algorithms for the analysis of solid models.
.NH 1
Analysis of the Model
.PP
At any stage of the design,
the model can be used to make
realistic images and engineering drawings.
This capability is so powerful that it ordinarily justifies the
construction of the model.
However, the real payoff from building a geometric model
comes when it is time to analyze it.
The model can be subjected to
numerous engineering analyses, allowing
the effects of varying many parameters
to be studied in a controlled way.
.NH 2
Image Rendering
.PP
Many phenomena that are difficult to model with the more traditional
scan-line-order rendering of faceted objects
can be handled simply and elegantly with ray-tracing,
although with a much greater cost in processing time.
For example,
in most conventional rendering packages, shadows are implemented
by way of a subterfuge:
computing the \fIshadow volumes\fR cast from the light source by each object
as a set of ``neutral density''
polygons, and using them to influence the shading
decisions for the actual surfaces underneath them.
On the other hand, an illumination model
based on ray-tracing merely needs to fire a ray at each light source
to determine the total light energy at each point.
While the computational requirements of this strategy can be explosive
in a model with multiple light sources and many reflective objects,
the ease and accuracy of using ray-tracing to
model the laws of optics to
create very realistic renderings
has not yet been surpassed by other techniques.
.PP
By dithering the location of the light sources, this can also give
a statistically good rendition of shadow penumbra effects.
Unlike conventional rendering packages, ray-tracing also makes it
easy to deal with objects that are partly or entirely reflective,
and with transparent objects that have varying refractive indices.
Furthermore, by applying the proper sorts of dither,
.[
Cook distributed ray tracing
.]
motion-blur, depth-of-field, translucency, and other effects are
easily achieved.
The ease and flexibility
of modeling point-sampled optics with the ray-tracing paradigm
is demonstrated by the lighting model code supplied with RT, which implements
all of the features listed above
(reflection, refraction, perspective views, penumbras, texture maps
translucency, etc.)
in less than 400 lines of heavily-commented ``\fBC\fR'' code.
.PP
An example of these features is shown in plate 4.1.
Plate 4.2 shows the outside and inside (skin removed) views of
a BMP vehicle, and plate 4.3 depicts an M109 with glass armor.
Using simple techniques such as making selected parts of the model
invisible or transparent, a designer can create powerful images
for communicating the design.
.NH 2
Animation
.PP
Given that lighting model code exists for making static images,
it is a relatively straightforward matter to develop code which
can animate the position of the ``eye'' (camera) and light sources
within the model, and only a modest additional effort to develop
the capability of articulating the model geometry itself.
Using animation can be very beneficial when trying to gain
comprehension of complex geometry, especially when the object
being modeled has never actually been physically built before.
There is nothing that communicates complex structures
more clearly than observing them passing by smoothly.
In addition to assisting the design engineers understanding
the geometry that they are developing, an animation capability
is also very useful as a sales tool, both for aiding management
understanding of the design project, and also to convey
a strong message to potential customers.
.PP
In addition to being a valuable visualization tool,
animation capabilities can be used to experimentally
verify that moving assemblies do not interfere with each
other, and that adequate clearances exist.
This can be extended still further by explicitly modeling
the presence of humans as part of the geometry,
allowing pre-prototype testing and evaluation of
the ``human factors'' portions of the design.
Verification that the design provides
adequate space to move around in, easily accessible
operating controls, proper provisions for seating,
and doorways that are convenient for non-contortionists
can be achieved through animation studies.
.NH 2
Lens Design
.PP
The power of the lighting model code
can further extended by making a provision to record the paths of all
the rays followed when computing the light intensity for each pixel,
and recording them in an auxiliary file.
In addition to being a fantastic debugging tool, this capability
allows one to follow the path of the light rays passing through lenses
and being reflected by mirrors while performing image rendering.
All these calculations are necessary simply to obtain a rendering
of the scene, but if one is actually attempting to use the solid modeling
system to study optics, the effects on the actual light ray paths
can be obtained with no additional computation.
.PP
Studying the paths of light rays as they are repeatedly bent
by passing from air to glass and back again has traditionally
been a painstaking manual procedure for lens designers.
By developing a solid model of some set of optics under consideration,
it becomes possible to predict lens behavior, including making a
determination of the exact focal length, finding the precise influence of
spherical distortions and edge effects, determining the amount of
image distortion due to internal reflection and scattering,
and finding the level of reflections from the lens mounting hardware.
Furthermore, experiments can be conducted to
determine the effects of adding or removing
baffles, irises, special lens coatings, etc.
This is an unusual but highly profitable coupling of solid models and
analysis codes.
.NH 2
Property Calculations
.PP
In the design of vehicles,
moments and products of inertia play a central role.
Particularly when designing aircraft, weights,
the center of gravity,
and parameters related to inertia are vital aspects of
creating a stable design with high performance.
For ground vehicles and fixed structures these figures are
quite significant, providing a good first estimate of structural
loading, and allowing transportation costs to be assessed.
Moments of inertia are important in determining what conditions
a vehicle may be overturned by maneuvering or impact, and can also
help predict the vehicle's handling when maneuvering over rough terrain.
.[
Deitz improved materiel acquisition
.]
.PP
By applying the Fundamental Theorem of integral calculus and
performing spatial integration of the geometry as sampled by
the ray tracing process,
it is possible to compute
the presented areas and profile shapes from a given viewpoint,
important information to have both for styling and functional design.
.[
Lee Requicha algorithms for computing volume properties solid objects
.]
By combining this spatial integration procedure
with a knowledge of the properties of the various
materials involved (density, etc),
it becomes possible to compute
the mass, center of gravity, moments of inertia,
overturning moments, and other similar engineering assessments.
.[
Thomas calculus
.]
Plate 4.4 shows one planar set of material property samples
from the ray-tracing analysis of an M48 tank.
Such material samples comprise the input information
for the codes which make the property calculations.
.PP
The mass of an object distributed over a region $V$ and having
a density $delta (x, y, z)$ at the point $(x, y, z)$ of $V$
is given by the integral
.EQ
M ~=~ int int int ~ delta (x, y, z) ~ dV ~.
.EN
In the case of sampled geometry, this can be expressed as
.EQ
M ~=~ sum from x sum from y sum from z ~ delta (x, y, z) ~.
.EN
Similarly, the center of gravity is
.EQ
( { int int int ~ x ~ delta (x, y, z) ~ dV } over M ,~
{ int int int ~ y ~ delta (x, y, z) ~ dV } over M ,~
{ int int int ~ z ~ delta (x, y, z) ~ dV } over M ),
.EN
or for sampled geometry
.EQ
( { sum from x sum from y sum from z ~x~ delta (x, y, z) } over M ,~
{ sum from x sum from y sum from z ~y~ delta (x, y, z) } over M ,~
{ sum from x sum from y sum from z ~z~ delta (x, y, z) } over M ).
.EN
The moments of inertia $I$ can be found as
.EQ
I ~=~ (~
{ int int int ~ ( y sup 2 + z sup 2 )~ delta (x, y, z) ~ dV },~
{ int int int ~ ( x sup 2 + z sup 2 )~ delta (x, y, z) ~ dV },~
{ int int int ~ ( x sup 2 + y sup 2 )~ delta (x, y, z) ~ dV } ~ ) ~.
.EN
.PP
These computational techniques can be extended
.[
Blass theoretical physics
.]
to provide the principle second moments and cross products of inertia.
Due to the computational complexity of evaluating these
mechanical design parameters, they have typically
been unavailable to engineers using traditional design approaches.
.NH 2
Drafting
.PP
When a design created on a CAD system is to be produced in
traditional manufacturing facilities
rather than using a fully automated NC plant,
clear and  detailed drawings are a necessity.
Thus, the production of engineering drawings, including
orthogonal views, orthographic projections, and ``exploded views''
from the solid models is an important, if unglamorous, capability.
.[
Lamit teaching descriptive geometry
.]
Once the model is constructed, the designer may define drawings containing an
unlimited number of views,
either standard orthogonal views or views from an arbitrary azimuth and
elevation.
While tolerance specification, 
fully automatic dimensioning, and tolerance indication is a difficult area,
.[
Requicha historical summary
.]
recent research is beginning to provide strategies for implementing them,
.[
Hashimoto automatic dimensioning
.]
and future CAD systems should demand less human intervention
than current ones.
BRL does not have a well developed capability in this area
because of its heavy reliance on color shaded images to communicate
final designs.
.NH 2
Numerical Controlled Milling
.PP
Direct numerical control (NC) of a milling machine provides
the ultimate in ``hard copy'' output.
.[
Voelcker Hunt role solid machining NC verification
.]
NC milling can be
very useful for generating prototypes for initial testing,
where the goal is to produce correct
toolpath computation in a short amount of elapsed time, but
requiring minimal human intervention.
.PP
However, NC milling is
also very important in the mass production of final versions of the design.
In this case, the objective is to compute
toolpaths which result in maximum efficiency of the milling machine.
A man/machine team effort
with human-directed optimization of
the automatically produced NC programs
can result in maximum production rates from
factory automation equipment with minimum waste.
.PP
Automatic toolpath generation is still difficult
due to the complexity of tool/block interference testing,
but various researchers are currently investigating using
a ray-tracing paradigm for toolpath planning.
.NH 2
Structural Analysis
.PP
Currently, most structural analysis and hydrodynamics
analysis is done using finite element mesh (FEM) techniques.
FEM data is normally pre-processed by packages like PATRAN
to develop inputs for NASTRAN, EPIC, ANSYS and other similar programs to
to actually process the mesh data,
including stress testing, computing loading factors, etc.
.PP
An automatic interface from the modeling system to a finite element
representation is a very important capability.
G. Moss at BRL is currently developing a post-processor program which converts
CSG-rep solid models into a boundary form suitable for input to PATRAN-G,
but this is still an active research effort.
.NH 2
Vulnerability Assessments
.PP
An important extension to simple static and dynamic loading of
structures is to consider unexpected dynamic stress caused by
a high-energy source impacting the object being designed.
This could be as ordinary as a rock striking a car traveling at
80 kilometers per hour, hailstones falling from the sky, or
a collision with another vehicle.
On the other hand, if the object being designed is intended for
use in a military setting, the range of threats which must be considered
is greatly enlarged.
Not only designers have to worry about airplanes impacting with large birds,
hail, and rain, they also need to design airplanes to withstand the
buffeting from nearby explosions, flying shrapnel, and various projectiles.
.[
Weaver Deitz solid modeling aircraft survivability
.]
When designing tanks and other ground vehicles,
the designer needs to consider the effects of small arms fire, land mines,
projectiles, and missiles.
Similarly, designers of ocean-going vessels need to concern themselves
with the effects of torpedoes, projectiles, and missiles;
spacecraft designers need to contend with high-velocity particles,
laser beams, and other similar challenges.
For all designs, nuclear effects need to be considered.
.PP
To conduct a ballistic analysis of point burst effects,
BRL has developed a model for lethality and vulnerability estimation
which is used to evaluate the effects of antiarmor weapons used against
ground vehicles, based upon a ray-tracing approach.
.[
Brown slave user manual
.]
.[
Ringers slave analyst guide
.]
Following perforation of a vehicle armor shell by a penetrator, this code
evaluates behind-armor spall cloud effects, described by a cone of debris
extending from the point of armor penetration.
This process is illustrated in plate 4.5, where the red rods depict
the path of the main penetrator, and the blue cone represents the
extent of the debris.
Soft components located within the spall cone are considered to be destroyed
by the debris, while hard components survive unless they are impacted by the
main penetrator.
This code runs interactively and generates a color display to provide
immediate feedback into the design process,
.[
Ozolins islave interactive
.]
an example of which is shown in plate 4.6.
.NH 2
Nuclear Survivability
.PP
When a nuclear weapon is detonated, blast effects, thermal radiation,
electro-magnetic pulse, initial nuclear radiation, and fallout all
pose threats to
equipment and personnel.
The initial nuclear radiation has three main components:
prompt neutrons, neutron-induced secondary gamma particles,
and prompt gamma particles.
.[
Deitz materiel acquisition
.]
The Vehicle Code System (VCS)
.[
Rhodes VCS user manual
.]
.[
Rhodes radiation protection vehicles
.]
considers total dose effects by first deterministically calculating
the transport of radiation to an envelope that surrounds the vehicle, and
then making a stochastic relationship between the radiation at the
source envelope and at the detection point inside
by using ray-tracing to track each particle through the vehicle.
Plate 4.7 shows a rendering of a Tank Test Bed (TTB) concept vehicle,
and a version displayed with a false coloring scheme, depicting the
proportions of radiation leakage that reached the detection point inside.
A surprising result of this test was the unexpectedly high proportion of
radiation that entered the vehicle through the narrow front plate;
examination of the model did not suggest that it was inadequate.
The ability to find and correct this type of deficiency early in the
design process is extremely important, and can result in huge cost savings.
.NH 2
Signatures by ``Geometric Sampling''
.PP
In the next several sections the topic of predictive signature
analysis will be examined for a variety of wavelengths using
several slightly different approaches.
The development of predictive
signature analysis is like a double-edged sword;  it can be
useful both for developing techniques for reducing the
signatures of existing vehicles by guiding product improvement plans,
as well as ensuring that new vehicles being designed have an acceptably low
signature for frequency ranges of interest, but this kind of analysis
can also be used to guide testing and 
optimize designs for new or improved sensing systems.
.PP
It is very important to note that
point-sampled geometric optics
only bears a statistical relationship to the
effects actually obtained from a wave optics analysis (or experiment),
and that accounting for phase-related effects is difficult at best.
Thus, developing predictive models does not relieve the designer of
the responsibility for conducting tests with scale and full size physical
models of the prototype, but having these predictive models should
make the possibility of unexpected behaviors
in the prototypes quite small.
.NH 2
Vision Assessments
.PP
An interesting application for inside-out ray-tracing is to determine
the view from within a vehicle through the vision ports or windows.
This gives the designers the opportunity to adjust the shape, orientation,
and placement of the vision elements of each vehicle so as to optimize the
exterior field of view for the vehicle occupants.
.PP
Some modern weapons utilize a forward observer to designate
a target by laser illumination, with a missile-borne sensor
homing in on the reflected beam.
This scenario is illustrated in plate 4.8.
In order to determine how such
a sensor might perform, it is necessary to calculate the
laser energy reflected from a variety of candidate targets.
.[
Deitz high resolution weapons
.]
A related assessment is to determine the amount of optical radiation
that might enter a vehicle through each vision port when irradiated
with the light from a laser designator.  The result of this type of
study is usually a cardioid shaped plot showing the energy transmitted as
a function of azimuth angle.
.[
Deitz improved materiel acquisition
.]
.NH 2
Infrared Modeling
.PP
In the design of smart munitions, it is important to know the
nature of vehicle signatures over a range of detection bands
and for a variety of signal-processing schemes.
.[
Rapp estimating Infrared sensor response
.]
Actual predictive infrared modeling is possible based on solid modeling,
using finite element techniques.
To make predictions about the patterns of heat radiation,
it is necessary to calculate a complete internal heat
budget for the entire vehicle which accounts for all the sources and
radiators of heat, such as engines and cooling fins,
and then to take into account external thermal loading due to such factors as
the surface of the earth and solar radiation.
Heat flow is calculated from node to node in the model, with links between
mesh elements characterized by thermal coupling coefficients.
The methodology for performing this type of predictive modeling
was developed at BRL,
.[
Rapp predicting infrared emission signatures m60a1 tank
.]
but has never been implemented.
.NH 2
Millimeter Wave Signatures
.PP
Dihedral and trihedral metal elements act as particularly efficient
reflectors for millimeter wavelength radio transmissions,
to the extent that the return from such elements represents the great majority
of the return from vehicles.
.[
Deitz predictive signature modeling
.]
BRL has developed a predictive millimeter wave signature model
.[
Lacetera deterministic targets mmw radar systems
.]
which concerns itself strictly with processing the dihedral and trihedral
elements that compose a vehicle.  G. Moss at BRL has developed
a post-processor program which extracts these features,
regardless of size and orientation, from the existing
CSG-rep solid models to drive this analysis.
An example of the result of this type of processing is shown in Plate 4.9
.PP
Because there is a strong correlation between the quantity of
dihedral vehicle surface topology and the intensity of the millimeter wave
reflection, this feature extraction program can be used by itself
without running the full deterministic millimeter wave reflection model
to obtain initial estimates of the magnitudes of
the millimeter wave signature of a given structure.
.NH 2
Synthetic Aperture Radar
.PP
Synthetic aperture radar (SAR) is a technique with which a variety of
image information about a distant object can be obtained by correlating
multiple radar samples taken from various positions.
.[
Toomay radar principles
.]
While standard radars only report target backscatter and range information,
SAR techniques can resolve distinct scattering regions of a target.
.[
Deitz signature modeling
.]
In 1984, BRL merged the
Simulated Radar Image Modeling (SRIM)
predictive SAR model from
the Environmental Research Institute of Michigan (ERIM)
with BRL's raytracing capability.
The choice of ray density is based on the frequency of the radar being
simulated and the cross-range resolution of the process.
Any ray can reflect up to some preset number of times or until it leaves
the vicinity of the target.  An example of the ray paths for
the first and subsequent reflections is shown in plate 4.10.
The actual results of the SAR calculation with an M48 vehicle
using a single transmit/receive polarization is shown in plate 4.11
These calculations were made in a high-resolution mode
unconstrained by practical frequency or coherence considerations of
realizable radar systems.  The radar signal is propagating from left to right.
.NH 2
Tradeoff Analysis
.PP
The philosophy adopted at BRL has been to develop a broad set of
analyses which are supported from the same geometry database.
.[
Deitz predictive signature modeling
.]
These analyses cover the spectrum from engineering decision aids,
to design validators, to drafting and milling interfaces, to
the generation of manufacturing drawings,
to image generation for management comprehension and sales advantage.
Key analysis capabilities have been developed to assess the 
strength, weight, and ``protection'' levels offered by
the structures represented by a solid model.
Using this analysis information and additional domain-specific
applications tools makes it possible to produce highly detailed
vehicle designs
constructed with a philosophy of \fIsystem optimization\fR
right from the start.
This should allow the rapid
development of vehicles with the desired levels
of performance at the best attainable price.
.SH
Thanks
.PP
The author would like to thank
Bob Reschly for his assistance with creating the drawings using PIC and CIP,
his supervisors Dr. Stephen Wolff and Dr. Paul Deitz 
for their unflagging support,
Harry Reed for providing an environment that makes good research possible,
and Dr. Dave Rogers for persuading me to write it all down.
.[
$LIST$
.]
.bp
.SH
Plate Captions
.LP
.nf
1.1	ComGeom Primitive Solids
1.2	Rendered Spline Surface
1.3	AuBuC Wireframe
1.4	AuBuC Rendering
1.5	A-B-C Wireframe
1.6	A-B-C Rendering
1.7	(A-B)+C Wireframe
1.8	(A-B)+C Rendering
1.9	C-A-B Wireframe
1.10	C-A-B Rendering
1.11	Early Rendering of Vehicle

2.1	MGED Faceplate with First-level Menu
2.2	Engine Connecting Rod.  Unevaluated and Evaluated Wireframes
2.3	Close-up of Connecting Rod Joint
2.4	ARB8 Before Editing
2.5	ARB8 After Editing Edge 1-4

4.1	Ray-Tracing Features
4.2	Inside and Outside Views of BMP
4.3	M109 with Transparent Armor
4.4	M48 Ray-Tracing Sample, w/Materials Colored
4.5	Main Penetrator and Spall Cone
4.6	Output of Vulnerability Evaluation
4.7	Neutron Study of Testbed Vehicle
4.8	Optical Signature Modeling
4.9	Dihedral and Trihedral Plates
4.10	Ray Paths of Radar Bounces
4.11	Ultra-high Resolution M48 SAR Image
plate	slide	hi-res & what			where
-----	-----	-------------				-----
1.1	27	N  comgeom primitives		/demo/tanks/allsolids.rle
1.2	26	Y  rendered spline		talks/86tokyo/g/a43.rle
1.3	30	Y  AuBuC			talks/86tokyo/g/all1.rle
1.4	32	Y  AuBuC			talks/86tokyo/g/all2.rle
1.5	33	Y  A-B-C			talks/86tokyo/g/a-b-c1.rle
1.6	34	Y  A-B-C			talks/86tokyo/g/a-b-c2.rle
1.7	35	Y  A-B+C			talks/86tokyo/g/a-b+c1.rle
1.8	36	Y  A-B+C			talks/86tokyo/g/a-b+c2.rle
1.9	37	Y  C-A-B			talks/86tokyo/g/c-a-b1.rle
1.10	38	Y  C-A-B			talks/86tokyo/g/c-a-b2.rle
1.11	122	N  example of early rendering	/demo/gift/york.rle

2.1	72	Y  faceplate, first menu	talks/86tokyo/g/p2.1.rle
2.2	65	Y  two crods			talks/86tokyo/g/p2.2.rle
2.3	66	Y  close-up crod		talks/86tokyo/g/p2.3.rle
2.4	73	Y  arb8 before editing		talks/86tokyo/g/p2.4.rle
2.5	74	Y  arb8 after moving edge	talks/86tokyo/g/p2.5.rle

4.1	91	Y  ray-tracing features		/demo/lgt/raytrace-features.rle
4.2	123	N  inside/outside views of BMP	/demo/tanks/bmpei.rle
4.3	124	Y  transparent armor M109	/demo/lgt/m109,trans,front.rle
4.4	134	N  m48 side slice		/demo/tanks/m48linesZ.rle
4.5	125	Y  spall cone			/demo/lgt/m1a1_spall.rle
4.6	137	N  vulnerability evaluation (pkh)	/demo/tanks/icav.rle
4.7	138	N  testbed, neutron study	/demo/tanks/testbed.rle
4.8	142	N  optical signature modeling	/demo/lgt/osm.rle
4.9	143	dihedral and trihedral plates	~moss/plot/bmp_flat.plot
4.10	144	N  radar bounces		/demo/sar_images/m48corners.rle
4.11	145	N  m48 sar hi-res		/demo/sar_images/m48sarHR.rle