GED: An Interactive Solid Modeling System

For many years the production and modification of target descriptions, no matter what method used, has been a slow, labor-intensive procedure. In an effort to improve the response time of target descriptions, the Ballistic Research Laboratory (BRL) has developed an interactive solid modeling system. This system is called the Graphics Editor (GED) and is designed to replace the traditional manual method of production and modification of target descriptions. GED presently applies to the combinatorial geometry (COMGEOM) solid modeling technique. Using GED, the target descriptions are interactively viewed, modified, and constructed with immediate visual feedback at each step. The GED system virtually eliminates explicit numerical input and opens a new dimension in the target description process.

As the Army’s lead laboratory for vulnerability technology, the Ballistic Research Laboratory (BRL) constantly performs vulnerability analyses for a wide variety of military systems. Vital to these vulnerability studies are three dimensional computer models of the physical characteristics of these systems. These computer models are generally called target descriptions. Since the mid 1960’s, BRL has used a solid modeling technique called combinatorial geometry (COMGEOM) to model targets. The COMGEOM technique uses logic operations to combine basic geometric shapes or primitives to produce the three-dimensional target description. The COMGEOM target descriptions are processed by the Geometric Information For Targets (GIFT [1],[2]) code for use in follow-on vulnerability assessment codes.

Target descriptions are basically large collections of numerical data which traditionally have been handled manually in a batch environment. Hence, the production and modification of target descriptions has been a slow, labor-intensive process. In 1980, BRL initiated an effort to improve the response time of the target description process by applying interactive computer graphics techniques. As a result of this work unit, BRL has developed the Graphics EDitor (GED), an interactive solid modeling system based on the COMGEOM technique. Using GED an analyst can view, build, and modify target descriptions interactively by manipulating the graphical representation, thus providing immediate visual feedback on a vector display device. The GED system is designed to replace the manual method of production and modification of target descriptions.

This report is intended to serve as a user manual for the GED system. The process of viewing and editing a description using GED is covered in detail. The internal data structure is also covered, as it is an important part in the overall design of the GED system.

Since the GED system is presently based on the COMGEOM solid modeling technique, a brief overview of the COMGEOM technique is required to effectively use GED. For more detailed information on the COMGEOM technique see references 1 and 2.

The COMGEOM technique utilizes two basic entities - a solid and a region. A solid is defined as one of fifteen basic geometric shapes or primitives. Table I contains a list of these fifteen solids. The individual parameters of each solid define the solid’s location, size, and orientation. A region is a combination of one or more solids and is defined as the volume occupied by the resulting combination of solids. Solids are combined into regions using any of three logic operations: union(OR), intersection(+), or difference(-). The union of two solids is defined as the volume in either of the solids. The difference of two solids is defined as the volume of the first solid minus the volume of the second solid. The intersection of two solids is defined as the volume common to both solids. Figure 1 presents a graphical representation of these operations. Any number of solids may be combined to produce a region. As far as the COMGEOM technique is concerned, only a region can represent a component of the target. The solids are only building blocks to be combined into regions. Since regions represent the components of the target system, they are further identified by code numbers. These code numbers either identify the region as a target component (nonzero item code) or as air (nonzero air code). Any volume not defined as a region is assumed to be "universal air" and is given an air code of "01". If it is necessary to distinguish between universal "01" air and any other kind of air, then that volume must be defined as a region and given an air code other than "01". Normally, regions cannot occupy the same volume (overlap), but regions identified with air codes can overlap with any region identified as a component (i.e. one that has a nonzero item code). Regions identified with different air codes however, can not overlap.

Computer graphics is one of the fastest growing fields in the computer industry. Computer graphics has applications in many diverse areas, from electronic games to medicine, from cartoons to the space industry. Just what is interactive computer graphics and why is it so versatile? Human visual perception is quite keen and communications with a computer are generally faster and easier with images or displays rather than with numbers. Furthermore, by driving the display image with the computer, one can actually communicate with the computer through the display itself. This technology is called interactive computer graphics. The user converses with the computer through the display using devices such as light pens, data tablets, function switches, and control dials. The response of the computer is immediately reflected on the display. Thus a fast channel of communication is available between person and machine.

To speed up the model description process, a faster more efficient method of manipulating the large masses of data involved in a target description is needed. Interactive computer graphics seems to provide the capability of handling such data in an efficient, relatively fast manner. The key to the whole situation is SOFTWARE - the missing link between the target description problem and a possible solution.

In view of this fact, existing software graphics packages were evaluated with respect to their utility in the target description process. Quite an exhaustive search of commercially available systems was conducted and none were found which completely satisfied our requirements. A study was then initiated to examine the feasibility of producing the required graphics software in-house. The result of this study was a preliminary version of GED which, using existing hardware, quite convincingly demonstrated the feasibility of such an undertaking [3].

It was then decided to develop GED into a full production code and to acquire the hardware necessary for full implementation of the system. The production level GED code has been used since January 1982 to build target descriptions interactively at BRL.

The main function of the GED system is to edit target descriptions with immediate visual feedback. Hence, GED produces images both suitable for editing and capable of being displayed in real time. When an object is displayed, the solids combined to model the object are drawn. No attempt is made to produce edge representations of regions or to remove hidden lines. At the present, such an undertaking would take away from the "real time" displays now enjoyed.

The GED is a modular code written in the C programming language which presently runs under the BRL UNIX Networking System [4].

The workstations presently used are Vector General (VG) 3DI vector refresh systems driven by DEC PDP-11/34 or PDP-11/70 computers. Peripheral devices include a joystick, a pen and data tablet, function switches, and control dials. These peripheral devices and functions of each are discussed in later sections.

Overall control of GED is maintained via the keyboard. The keyboard commands perform general housekeeping functions and allow one to control what is displayed, create/modify combinations, list solid parameters, etc. The keyboard commands are discussed in a later section.

One of the critical aspects of a graphics software package is its internal data structure. Since the target description problem deals with such large volumes of data, the importance of the data structure here is emphasized. Thus it is felt that an introduction to the internal data structure of GED is important for any potential user.

The GED internal data structure is hierarchical in nature with each node or position in the hierarchy being occupied by an OBJECT. An OBJECT is the GED basic data unit and is defined as either a SOLID or a COMBINATION. A SOLID is one of the generalized COMGEOM primitive types while a COMBINATION is a group of objects. Each member object of a combination has a transformation associated with it. Any object not at the top of an hierarchy is referenced by (is a member of) a higher combination and each such reference has an associated transformation. The bottom object of every hierarchy path is a solid. This hierarchical data structure allows actual subsystems of a target to be grouped together and edited as a unit without worrying about individual parts. To display any object, each path in the object’s hierarchy is traveled to its bottom position where a solid is located. The transformations are accumulated for each path traversed and then applied to the solid at the bottom of the path. The solid is then drawn. The hierarchy is traversed recursively until all objects are drawn. Let’s use a high explosive projectile as an example. Figure 2 depicts the hierarchy involved. If one were to display the combination "heround", six solids would be drawn on the screen. Table II lists each solid name, the transformation applied to the solid’s parameters, and the path used to reach the solid.

One very useful type of combination is the INSTANCE. An instance is a referral to an object (solid or combination) without the object itself being duplicated. To produce an instance of an object, a combination is created with the object being instanced as a member object. As with any other combination, this member has an associated transformation, hence it can be edited as a unit. The instance is most useful when an object appears many times in a description. The desired number of instances are made and positioned in the description. Any future changes in the object require that only the original (prototype) be changed. The modifications of the prototype object will then be automatically reflected in all the instances of that object.

To execute GED, one simply types "ged file", where "file" is the data file to be edited. The GED keyboard commands are used to maintain overall control of the system and to perform general housekeeping functions. Each command is invoked by entering a single character followed by other parameters (if necessary) separated by spaces. In most cases, the response on the screen will be the word "done" once the command is completed. This response is not printed for the commands where the results of the command are readily visible on the screen.

In the following pages, the GED keyboard commands will be presented and discussed. Examples will be given in appropriate cases. Table III, at the end of this section, presents a summary of the GED keyboard commands and the function of each.

Before we discuss the features of GED, we will introduce the hardware devices used to implement them. These devices are the "tools of the trade" for the GED user. We will discuss only basic operational characteristics here. Specific use of these devices will be covered in the later sections on the viewing and editing features of GED.

The JOYSTICK is a mechanical device used to do the rotations in GED. Any movement of the stick left or right rotates the display about the x-axis. Any movement of the stick up or down rotates the display about the y-axis. When the joystick is twisted in a clockwise or counterclockwise direction, the display rotates about the z-axis. Any combination motion of the stick will produce a "combined" rotation about the appropriate axes. All of these motions have a spring return to a null center position.

The FUNCTION SWITCH box contains thirty-two buttons. When any of the buttons is pressed, an action occurs or condition is set. Figure 3 depicts the functions programmed for each button. The buttons in the shaded area are used for editing while the rest are used for viewing the display. The exact functions assigned to these buttons will be discussed in the sections on viewing the display and on editing.

The CONTROL DIALS (knobs) are used to send digital information to the computer. As a knob is turned, a succession of numbers are available for use by the computer. Figure 4 depicts the functions assigned to each of the ten knobs. The exact functions of each of these knobs will be discussed in the angle distance cursor section and in the viewing features section.

The DATA TABLET is a graphics input device containing an X-Y coordinate grid which corresponds to the grid on the screen. Information is entered using a pen-like stylus. The distance this pen is from the tablet is important. If the pen tip is within one half inch of the tablet surface, the cursor location on the screen corresponds to the X,Y location of the pen on the tablet. This condition is called the "near" position. If the pen is more than one half inch from the tablet surface, the cursor remains located in the center of the screen. When the pen is pressed against the tablet surface, the pressure switch is activated and a bit is set which is a signal used by GED. The exact meaning of the pen near and pen press depends on what is being done and will be covered in the appropriate sections of this report.

The angle distance cursor is a construction aid used to measure angles and distances. It should be noted that all measurements are made in the projected space of the screen, so one should measure only in a view normal to the surface where the measurement is to take place. The ADC is placed on (or removed from) the display by pushing the "ADC" function switch button (see Figure 3). The ADC consists of three cursors which cover the entire screen. Figure 5 depicts the ADC as it appears on the screen. All the cursors are centered at the same point and can be moved to any location on the screen. Two of these cursors rotate for angle measuring purposes. Angle cursor 1 is solid while angle cursor 2 is dashed. Angle cursor 1 has movable tic marks for measuring distances on the screen. The two angle cursors move with the horizontal and vertical lines of the main cursor. The resulting effect is the moving of the center point horizontally or vertically. The ADC is controlled by the bottom row of the control dial knobs (see Figure 4) :

Whenever the ADC is on the screen, there is a readout at the bottom of the screen listing pertinent information about the ADC. This information includes the angles that angle cursors 1 and 2 have been rotated (alpha and beta), the distance the tic marks are from the center of the ADC, and the location of the center of the ADC. This information is continually updated on the screen.

The GED viewing features are designed to allow one to examine a target description in close detail. Any of the viewing features can be invoked at any time. It should be noted, that these functions do not change the actual data, only the way these data are displayed.

Six standard views (front, rear, top, bottom, left, and right) and one oblique view (azimuth 35, elevation 25) are each assigned to the function buttons (see Figure 3). Hence, any of these views is immediately available at the press of the appropriate function button. The views available are not limited to these standard views however, as the display can be rotated to any view by using the joystick. By pressing the function button labeled "save view" (see Figure 3), the present viewing aspect angle of the display is saved. At any time, the saved view can be immediately returned to the screen by pressing the "restore view" function button (see Figure 3). The "restore view" button will be lit whenever a view has been saved. The function button labeled "reset" (see Figure 3), restores the display to the default view (front) when pressed.

The display can be panned or slewed on the screen in two ways - using the data tablet and pen or by using the control knobs. When one is editing, the tablet and pen are not available for slewing, hence one must use the control knobs to slew the display. If one is NOT editing, then whenever the pen is pressed, the display moves in the direction of an imaginary vector drawn from the center of the screen to the cursor location on the screen. Recall that there is a one-to-one correspondence between the pen location and the cursor location. The longer this vector, the faster the display will move. To slew the display using the control knobs, one uses the knobs labeled "slew x" or "slew y" (see Figure 4). The null positions on these knobs is in the center or straight up. If the "slew x" knob is turned clockwise of center, the display will move to the right. If it is turned counterclockwise, the display will move to the left. For the "slew y" control knob, clockwise of the center moves the display up and counterclockwise moves the display down. The further these knobs are turned from center, the faster the display moves.

One can zoom the display by using the control knob labeled "zoom" (see Figure 4). Again the null position of this knob is center or straight up. Turning this knob clockwise of center causes the display to increase in size producing a zoom-in effect. Turning this knob counterclockwise of center causes the display to decrease in size or zoom-out. Again, the further the "zoom" knob is turned from center, the faster the zooming will occur.

The viewing features of GED also include a slice mode. To invoke the slice feature, one presses the "slice mode" function button (see Figure 3). An imaginary slicing plane, parallel to the screen, can then be moved about by turning the first control knob (see Figure 4). Turning this knob clockwise moves the imaginary plane into the screen and counterclockwise moves the plane out of the screen. All portions of the display in front of the plane are eliminated from the display. The result of moving this plane into the screen is a slicing effect with the parts of the display closest disappearing first. To leave the slice mode, just press the "slice mode" button again.

Before we discuss the editing features of GED, we will discuss how one selects objects for editing. To be edited, an object must be displayed on the screen. Since the object to be edited may be only a small portion of the display, a procedure is needed to select an object from the many objects being displayed. This procedure relies on the hierarchical structure of the GED data base. As stated before, when objects are displayed, every path of every object is traversed and the bottom object, which is always a solid, is drawn. Hence one can think of each solid drawn not as one solid, but as the unique path used to reach that solid. As an example, the six paths (solids) for the sample object "heround" were presented in Table II.

To select an object for editing, one first must enter the illuminate mode by pressing the function button labeled "illuminate" (see Figure 3). The data tablet and pen are then used to select the object. The surface of the data tablet is divided into imaginary horizontal strips. Each of these strips corresponds to a path (solid) drawn on the screen. For example, if the sample "heround" were displayed, the tablet surface would be divided into six horizontal strips. The pen is used in the "near" mode (within one half inch of tablet surface) to illuminate the paths. The path corresponding to the pen location is written in the upper right hand corner of the screen. The solid at the bottom of this path is illuminated (drawn brighter) on the screen. In this manner one can "scan" the complete display by simply moving the pen up and down the tablet in the near mode. Hence, the illuminate mode is also quite useful just to identify objects in a description. However, the primary purpose of the illumination mode is to select objects for editing.

The actual selecting of an object for editing is a two-step process. First, one selects the path desired, then one selects the particular object of interest from that path. One "selects" by pressing the pen on the tablet surface. When a path is selected, the word PATH followed by the members of that path is written in the upper right of the screen. At that point, one is ready to select a specific member (object) from that path for editing. Again, the tablet is used for this selection. The tablet surface is now divided into as many rows (zones) as there are members in the selected path. When the pen, in the near mode, is in a path member’s assigned zone on the tablet, that member’s name will be illuminated in the path listing. When the specific member to be edited is illuminated, it is selected by pressing the pen. The word EDIT will now appear in the upper right of the screen ahead of the path listing. One is now ready to edit this selected object.

The only way out of the EDIT mode is to accept or reject any editing performed. This is done by pressing the function buttons labeled "accept" or "reject" (see Figure 3). If at any time in the selection process an incorrect object is selected, just press the "reject" button and begin the selection process again.

The heart of the GED system is its editing features. The editing features are divided into two classes: object editing and solid editing. Object editing is designed to allow one to change the location, size, and orientation of an object. Recall that an object is defined as the basic data unit of the GED system and includes both combinations and solids. In the case of a solid, one needs to change not only its location, size, and orientation, but also its "shape". Changing the shape of a solid means changing any of its individual parameters. Hence, solid editing is handled separately.

Any object in the data file may be selected for object editing. The object is picked using the object selection procedure discussed earlier. Recall that in the GED data structure, all members of combinations have transformation matrices associated with them, allowing assemblies to be edited as units. Object editing is the vehicle for performing such tasks. All object editing is done using homogeneous transformation matrices. When the editing is accepted, new transformation matrices are created in all appropriate member locations. If the object happens to be a single-member path (solid) then the matrix is applied to the solid’s parameters. Otherwise, all object editing is stored in transformation matrices in the data base.

Once an object is selected for editing, the second row of function buttons (see Figure 3) is used to select the editing to be done. Then either the data tablet and pen or the joystick are used to perform the actual editing.

To SCALE a selected object, one first presses the function button labeled "scale object". The data tablet and pen are then used to scale the object. The object is scaled about the target origin, thus unless the object is centered at the origin, some translation of the object will occur. The location of the pen on the tablet when pressed determines the scale factor used. If the pen is above the center of the screen, the scale factor will be greater than one. The further the pen is located above the center, the larger the scale factor. Likewise, if the pen is located below the vertical center, the scale factor will be less than one and the further below the center, the smaller the scale factor. As long as the pen is pressed, the object will continue to increase or decrease in size.

To ROTATE a selected object, one first presses the function button labeled "rotate object". The joystick is then used to rotate the object. The object is rotated about the center of the view (screen). If one wishes to rotate the object about another point of interest, the entire display can be slewed until the desired point is positioned at the center of the screen.

To TRANSLATE a selected object, one has three function buttons from which to select (see Figure 3). The data tablet and pen are then used to translate the object. The center of the object "follows" the pen (cursor) location whenever the pen is pressed. The three function buttons define the direction allowed for movement of the object. The button labeled with a horizontal arrow (←→), allows the object to follow only the horizontal location of the pen. The vertical location of the object does not change. The function button labeled with a vertical arrow ( ), allows the object to follow only the vertical location of the pen. The horizontal location of the object does not change. The function labeled with crossed arrows (←→) allows the object to follow the X,Y location of the pen.

The object editing features can be invoked in any order and at any time once an object has been selected for editing. During object editing, any of the viewing features, such as changing views, zooming, and slewing, can be used and in fact are usually quite useful. Again, the only way to exit the object editing mode is to accept or reject the editing. If the "reject" button is pressed, the object will return to its pre-edit state. If the "accept" button is pressed, the data base will be changed to reflect the object editing performed.

The solid editing feature allows the user to interactively translate, rotate, scale, and modify individual parameters of a solid. Whenever one is in the solid edit mode, the parameters of the solid being edited are listed and continually updated at the bottom of the screen. Certain parameters are also labeled on the solid being edited. Solid editing is generally used to "build" objects by producing solids of the desired shape and size in the correct orientation and position. Once the object is built, object editing is used to scale, orient, and position the object in the description. The general philosophy of solid editing is to first create a copy of a prototype solid with the desired name and then to edit this solid. The prototype solids should not be edited. As an example, suppose one were to build the sample object "heround" mentioned earlier. To produce the base of the shell, one would need a cylindrical shaped solid. The prototype solid is the TGC (see Table I), so one would type: c tgc shellcase.s

A new solid record called shellcase.s would be created and displayed on the screen. This shellcase.s solid would then be edited using solid editing to produce the exact solid parameters desired. The solid record tgc would be unchanged and available for copying the next time a cylindrical solid is needed.

The procedure for solid editing is quite similar to that for object editing. First, the solid must be selected for editing. A solid is selected for editing using the illuminate mode, just as in object editing, except a solid must be selected. Recall that the bottom object in every hierarchy path is a solid. Second, one must push the function button labeled "solid edit" (see Figure 3). This button sets up the solid edit mode: the solid parameters are listed at the bottom of the screen, pertinent solid parameters are labeled on the display, the solid editing function buttons are activated, and a menu header depending on the solid type is written on the right side of the screen. The meaning of the menu will be discussed shortly. Third, one selects (by pressing the appropriate function buttons) and performs the editing desired. Finally, one exits the solid editing mode by accepting or rejecting the editing performed, just as in object editing.

Recall, in the section on object editing it was mentioned that since a solid is indeed an object, a solid can be edited (translated, rotated, and scaled) as an object. Hence, the solid editing mode is really only necessary to perform parameter modifications. However, much of the object editing is done about the target or screen center, which can be annoying when editing a solid. Also, precise parameter modifications are possible (using the "p" keyboard command) in solid editing. Thus it was deemed desirable to include translation, rotation, and scaling in solid editing also.

Solid TRANSLATION allows the user to place the solid being edited anywhere in the description. To invoke this option, one presses the function button labeled "solid trans" (see Figure 3). To move the solid, use the data tablet and pen. Whenever the pen is pressed, the VERTEX of the solid moves to that location on the screen. One can read the actual coordinates of the vertex on the bottom of the screen, along with the other parameters. If the actual desired coordinates of the vertex are known, one can place the solid exactly using the "p" keyboard command. For example, to place a solid’s vertex at the coordinates (x, y, z) one would type p x y z The solid would then jump to this location.

The solid SCALE feature allows the user to scale the solid being edited to any desirable size. The scaling is done about the vertex of the solid, hence NO translation of the solid occurs. The scaling is performed using the data tablet and pen, just as in object scaling. One can input an exact scale factor using the "p" keyboard command. For example, typing p factor will scale the solid by an amount equal to "factor". The value of "factor" is absolute - the original solid is scaled. The size of the original solid is defined when the "solid scale" function button is pressed. By setting "factor" equal to one, the original size solid will be displayed on the screen.

Solid ROTATION allows the user to rotate the solid being edited to any desired orientation. The rotation is performed about the vertex of the solid. To select this option, one presses the function button labeled "solid rotate" (see Figure 3). The actual rotation is done using the joystick. One can input exact angles to rotate the solid by using the "p" keyboard command. For example, typing p alpha beta gamma will rotate the solid "alpha" degrees about the x-axis, "beta" degrees about the y-axis, and "gamma" degrees about the z-axis. Alpha, beta, and gamma are measured from the original "zero" orientation of the solid, defined when the "solid edit" function button was pressed. Hence, typing p 0 0 0 will always return the solid to its original position (its position when the current solid editing session began).

The PARAMETER editing feature allows the user to modify any of the parameters which comprise the selected solid. To invoke this feature, one presses the function button labeled "menu" (see Figure 3). A menu (listing) of parameters to edit will then appear on the right side of the screen under the menu header. The contents of this menu of course depend on the type of solid being edited. To select an item (parameter) from this menu, one uses the data tablet and pen. The immediate region (strip) surrounding each item of the menu "belongs" to that item. Whenever the pen is in one of these regions, that menu item will get brighter in the menu listing on the screen. A menu item is picked by pressing the pen when that item name is illuminated. It should be noted that whenever the pen is in the "menu area", the code assumes the user is attempting to pick a menu item. Hence, the menu area of the screen (the far right edge) can NOT be used by the pen for editing while the menu is on the screen.

For parameter editing, the solid type determines the menu items. The GED code recognizes four general solid types for parameter editing. All the specific solid types which fall into one of these general classes are treated as the general type. For example, all the cylindrical solid types are treated as the general type - the TGC. In the following paragraphs, we will discuss parameter editing for each of these general types of solids.

BRL has developed the Army’s first interactive solid modeling system, called GED. GED performs two basic functions: viewing and editing. The standard viewing capabilities of zooming, slewing, slicing, and rotation are available. Likewise, all the standard editing features are also available. The user easily traverses the hierarchical data structure, applying the editing functions of rotation, translation, and scaling to any position in the hierarchy. The hierarchical structure can be modified and regrouped and regions created and modified. Specific parameter editing can also be applied to the solids to produce any shape solid desired. GED has made great gains in reducing the bottleneck the target description process has been creating in the vulnerability process at BRL.