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