Michael John Muuss and Lee A. Butler

Published in
*State of the Art in Computer Graphics: Visualization and Modeling*
D. F. Rogers, R. A. Earnshaw editors,
Springer-Verlag, New York, 1991, pages 185-223.

Please read the Postscript Version, this page is just to provide the text to the search engines.

% $Header: /vld/mike/talks/90nmg/RCS/joined.html,v 1.1 1998/05/01 06:53:13 mike Exp $ \titlepage \baselineskip=20pt \vbox to 40pt{} \leftline{\hyphenpenalty=10000 \raggedright% {\chaptertitlefont \noindent Combinatorial Solid Geometry,} } \leftline{\hyphenpenalty=10000 \raggedright% {\chaptertitlefont \noindent Boundary Representations,} } \leftline{\hyphenpenalty=10000 \raggedright% {\chaptertitlefont \noindent and Non-Manifold Geometry} } \author {Michael John Muuss and Lee A. Butler} \makeheadline % --------------------------------------------------------------------------- % $Header: /vld/mike/talks/90nmg/RCS/joined.html,v 1.1 1998/05/01 06:53:13 mike Exp $ \footline={}% Turn off stupid Springer copyright \beginabstract The history of solid modeling is reviewed. Both traditional combinatorial solid geometry (CSG) systems and traditional boundary representation (B-rep) solid modeling systems are considered. CSG models are formed by the boolean combination of ``primitive'' solids. Only the unevaluated CSG tree is stored, rather than an explicit representation of the final surfaces. Many applications would like an {\it approximation} of these complex CSG shapes expressed as a collection of planar N-gons. This paper focuses on a technique for computing approximate three dimensional surface tessellations. So far, B-rep solid modelers have used variations on the winged-edge data structure. The winged-edge data structure can only describe manifold shapes, limiting these systems to manifold geometry. While not restricting the set of manufacturable parts, this has made implementing boolean operations on these B-rep models more difficult. Boolean operations and other useful modeling operations can be much more easily implemented using a representation that permits non-manifold topology to be expressed directly. A detailed look is taken at the radial-edge data structure and how it represents non-manifold conditions. While several previous publications describe the general nature of algorithms required to perform boolean operations on non-manifold geometry, details are sparse. This report describes the necessary algorithms in detail. Some of the systems analysis issues that can result from integrating non-manifold B-rep geometry into a hybrid CSG solid modeling system are discussed. Of particular note are the specification of tessellation tolerancing, the implementation of robust tessellation, the difficulties of carrying dual representations of objects, ray-tracing non-manifold B-rep solids, using the B-rep for driving high-performance polygon rendering hardware, and interfacing to facet-based analysis codes. \endabstract { \eightpoint \narrower \hrule \medsmallskip \noindent To appear in {\bf Advanced Computer Graphics Techniques}, ed. Rogers and Earnshaw, Springer-Verlag. } \vfill\eject % % Do these after setting up the title, to avoid a header on title page. \def\rhead{Combinatorial Solid Geometry, B-Reps, and Non-Manifold Geometry} \def\lhead{Michael John Muuss and Lee A. Butler} \sectionhead{A History of Solid Modeling} The digital computer provides the opportunity for nearly infinite variety in the representation of information within it. 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 -- the drafting process. Thus, initial CAD systems replicated traditional two-dimensional drafting techniques. Only modest gains in efficiency were possible in creating the first version of a design, but tremendous gains were realized when design modifications were needed, because the computer can retain and redraw the unchanged portions of the drawing. 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 simple 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 not designed for this sort of interrogation. 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, it is easy to define objects which cannot be physically realized due to non-closed faces and dangling lines. Third, it is possible to construct a wireframe which has ambiguous interpretations from different views. Finally, wireframe models may include view-specific lines representing false edges such as profile lines and silhouettes [REQU82]. Engineering drawings are suitable only for interpretation by human beings, not for automatic computerized analysis. As a new product is being designed, there are generally two or more different kinds of engineering analyses that need to be performed, such as structural analysis, thermal analysis, computational fluid dynamics (CFD), and vulnerability analysis, as well as the calculation of predictive optical, radar, infra-red (IR), and X-ray images or ``signatures''. Therefore, computerized drawings cannot be used to provide the geometric input required for these analysis codes. These requirements have focused attention on the evolution of an entirely different approach to representing objects: solid models. \sectionheadtwo{What is a solid model?} A solid model [MUUS87a] 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 [DEIT83]. 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 of them as well. 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. A solid model is always amenable to further modification by boolean combination with other shapes. 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 at any time. Therefore, solid modeling technology is particularly suited to the automation of many manufacturing and analysis tasks. %% was 4.5 by 3.25 \captionfig 3.5in by 2.5in, design-loop, Figure 1 -- The Design Loop. \eject \sectionheadtwo{The Design Loop} Solid models are very useful for generating drawings or pictures of the modeled object from any viewpoint. 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. The model can be subjected to numerous engineering analyses, allowing the effects of varying many parameters to be studied in a controlled and automatic way. This iterative process is termed the ``design loop'', and is illustrated in Figure 1. 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 {\it early in the design process}. 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 [DEIT85]. 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 an existing component already in inventory is entirely suitable for use in a new design, significant manufacturing and inventory savings will be realized. 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 [DEIT82]. Thus, the real payoff from building a solid geometric model comes when it is time to analyze it. This capability is so powerful that it ordinarily justifies any extra time or equipment investments needed to support the construction of the three dimensional solid model. 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. \sectionheadtwo{Model representations} Two major families of solid model representations exist, each with several unique advantages. The first representation, developed by MAGI under contract to the Ballistic Research Lab (BRL) in the early 1960s [MAGI67], 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 simplest solid that can be used is the halfspace [REQU82], 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 [LANI79] and TIPS-1 [OKIN78]. While this choice of representation limits these systems to modeling convex 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 [KEDE85a, KEDE85b]. Most CSG-rep systems in use today offer quite a variety of primitive solids, ranging from various types of spheres and ellipsoids, boxes and cones, and solids defined by swept or extruded curves. The alternative to describing solids with primitives is to adopt a boundary representation (B-rep), of which there are two sub-types: the {\it explicit} and {\it implicit} 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 [COON67], Bezier patches [BEZI74], splines [deBO78], etc. 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 only the traditional CSG primitives, it can be exceedingly difficult and non-intuitive to attempt to describe sculptured, free-form surfaces as a boolean combination of primitives. But similarly, implementing powerful modeling operations like boolean intersection and boolean differences {\it on the fundamental representation itself} can be difficult with pure boundary representations. Many current B-rep modelers implement boolean operations as an external post-processing operation, because current schemes to evaluate Boolean operations are not closed. As an example of this, B-spline $\cap$ B-spline might result in polygons rather than another B-spline. In a boundary representation closed under the set of boolean operations, B-rep $\cap$ B-rep $\rightarrow$ 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 [THOM84]. Even though existing systems are often considered as being purely CSG-rep or B-rep, the reality is that many production CAD 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. % $Header: /vld/mike/talks/90nmg/RCS/joined.html,v 1.1 1998/05/01 06:53:13 mike Exp $ \sectionhead{Interrogating a Solid Model} For more than thirty years, solid geometric modeling methods have been used to support engineering design and analyses [MAGI67, DEIT82, \break DEIT84a]. In such item-level studies geometry and material information are passed to various application codes to derive certain measures-of-performance. This is commonly done in structural analysis, thermal analysis, computational fluid dynamics (CFD), and vulnerability analysis. Building on the general paradigm, the techniqsues have been extended to support many predictive signature models [DEIT84b] including optical, millimeter wave (MMW), infra-red (IR), magnetic and X-ray signature generation tools. It is important to note that this type of predictive analysis must generally be supported by a solid geometric model. 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, a representation of just the {\it edges} of the objects in a model would be suitable for a program attempting to construct a wire-frame display of the model. There exists another family of applications which must be able to find the intersection of small object paths (e.g., 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. \captionfig 4.5in by 3in, appl-interf, Figure 2 -- The Applications Interface. Unfortunately, it is not often the case that building only {\it one} three dimensional model of the product is enough. Each of the different engineering analysis software packages needed to perform the analyses usually requires a different form of input. As a result, more than one kind of geometric model may have to be constructed. However, rarely do these application codes read the three-dimensional geometry and material data base directly. Rather, each application has a specific interrogation method that is invoked to obtain geometric and material attributes from a source or reference file. The physical simulation techniques used in the application software are therefore constrained by the available techniques for extracting geometric information from the model. Each analysis package often requires a unique form of input. Without a central geometry database that can drive all the analysis packages, the designer can be forced into having to create many different representations of each design, one for each distinctly different type of analysis code. This can be very costly and time consuming. The time needed to create a single model ranges between one man-week and several man-years, depending on the complexity of the design. Having to spend the effort to manually create the same design in different formats to drive several analysis codes is an unfortunate and expensive necessity. The philosophy adopted in the BRL-CAD Package [MUUS87c, \break MUUS88a] has been to develop a broad set of analysis codes which access the same geometry database [DEIT84b]. These analyses cover the spectrum from engineering decision aids, to design validators, to signature prediction codes, to the generation of wireframe drawings, to high-resolution image generation for management comprehension and sales advantage. Key analysis capabilities have been developed to assess the strength, weight, protection, and performance 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 designs constructed with a philosophy of {\it system optimization} right from the start [DEIT88]. This facilitates the rapid development of products with the desired levels of performance at the best attainable price. To accomplish all these goals, the BRL-CAD Package provides a variety of procedural interfaces so that the diverse collection of analysis codes can be driven from a single, central geometric model [MUUS90b]. These procedural interfaces follow the natural object-oriented programming interface. An application program retrieves one or more objects from the model database, and then requests those objects to either interrogate themselves in the desired way, or to convert themselves into the desired representation. This applications interface is depicted in Figure 2. The software is designed to be highly portable to different hardware architectures, platforms and environments, and is implemented using the C programming language [RITC78b] running on the ${\rm UNIX^{tm}}$ operating system [RITC78a]. \sectionheadtwo{Wireframe Representation} The interactive model editor {\bf mged} program employs three dimensional wireframe outlines of the various solid objects in order to maintain the highest possible speed of user interaction. In addition to the primary use in supporting interactive geometry viewing and modification, wireframes are also useful for visualizing complex analysis results. A particularly powerful form of this is to create a color display of the output of an analysis code (for example, temperature distribution across the surface of an object), and then overlay the analysis data with a wireframe drawing of the geometry. Wireframes are also very useful for the previewing of animation sequences. The conversion of database objects into wireframe drawings is the simplest of the application interfaces, and is very easy for the application program to utilize. After the user specifies which objects from the model database should be displayed, {\bf mged} retrieves the necessary database records and invokes the {\bf ft_plot()} interface provided by {\bf librt}. {\bf ft_plot()} passes the database object to the appropriate object-specific wireframe converter, which generates a wireframe outline of that object. The wireframe is composed of a collection of three dimensional virtual pen-plotter {\it move} and {\it draw} operations, returned to the application as a linked list of {\bf vlist} structures attached to the application provided {\bf vlhead} structure. Each {\bf vlist} structure has three elements, vl_pnt, the XYZ coordinates of a point in space, vl_draw, a flag which indicates whether the virtual pen should be moved invisibly from the current position to vl_pnt (vl_draw= VL_CMD_LINE_MOVE) or moved visibly, drawing a line from the current position to vl_pnt (vl_draw= VL_CMD_LINE_DRAW). \sectionheadtwo{Ray Tracing} Many phenomena that are ordinarily difficult to model can be handled simply and elegantly with ray-tracing. For example, an illumination model based on ray-tracing first fires a ray from the eye plane into the model geometry. To approximate the total amount of light at that point in the model, the algorithm simply fires a ray at each light source and sums the contributions from visible light sources. 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 [COOK84], motion-blur, shadow penumbra, depth-of-field, translucency, and other effects are easily achieved. The power of the lighting model can be further extended by making a provision to record the paths of all the rays followed when computing the light intensity for each pixel in an auxiliary file. This capability allows one to follow the path of the light rays passing through lenses reflecting from mirrors while performing image rendering, with no additional computation. 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 modeling, 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. Rays begin at a point $ \vec P $, and proceed infinitely in a given direction $ \vec D $. The {\it direction vector} or {\it direction cosines} for the ray $( \vec D_x , \vec D_y , \vec D_z )$ are the cosines of the angle between the ray and each of the Cartesian axes. This vector $\vec D$ is of unit length, i.e. $| \vec D | = 1 $. Any point $ \vec A $ on a ray may be expressed as a linear combination of $ \vec P $ and $ \vec D $ by the formula $ \vec A ~=~ \vec P ~+~ t ~*~ \vec D $ where valid values for $t$ are in the range $[ ~0,~ \infty )$. The traditional approach to ray-tracing has been batch-oriented, with the user defining a set of ``viewing angles'', initiating a large 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. 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 provide the ray-tracing capability through a general-purpose library, and make the functionality available to any application as needed. For example, the decision of when a ray should be reflected, transmitted, or absorbed should be entirely under the control of the application program. \sectionheadthree{LIBRT Library Interface} The third generation ray-tracing capability in the BRL-CAD Package is a set of library routines in {\bf librt} 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. {\bf rt_dirbuild()} opens the database file, and builds the in-core database table of contents. {\bf rt_gettree()} adds a database sub-tree to the active model space, and can be called multiple times to join different parts of the database together. To compute the intersection of a ray with the geometry in the active model space, the application must call {\bf rt_shootray()} once for each ray. Ray behaviors such as perspective, reflection, refraction, etc, are entirely determined by the applications program logic, and not by the ray-tracing library. The ray-path specification determined by the applications program is passed as a parameter to {\bf rt_shootray()} in the {\bf application} structure, which contains five major elements: the vector a_ray.r_pt ($\vec P$) which is the starting point of the ray, the vector a_ray.r_dir ($\vec D$) which is the unit-length direction vector, the pointer *a_hit() to an application-provided routine to be called when some geometry is hit by the ray, the pointer *a_miss() to an application-provided routine to be called when the ray does not hit any geometry, and the variable a_onehit. In addition, there are various locations for applications to store state information such as recursion level, intermediate color values, and cumulative ray distance. When the a_onehit variable is set to zero, the ray is traced through the entire model. Applications such as lighting models may often only be interested in the first object hit; in this case, a_onehit may be set to the value one to stop ray-tracing as soon as the ray has intersected at least one piece of geometry. Similarly, if only the first three hits are required (such as in the routine that refracts light through glass), then a_onehit may be given the value of three. Then, at most three hit points will be returned, an in-hit, an out-hit, and a subsequent in-hit. When only a limited number of intersections are required, the use of this flag can provide a significant savings in run-time. The {\bf rt_shootray()} function is designed for full recursion so that the application provided a_hit()/a_miss() routines can themselves fire additional rays by recursively calling {\bf rt_shootray()} before deciding their own return value. In addition, the function {\bf rt_shootray()} is fully capable of 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. 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 {\bf librt}. \vbox{\beginverbatim struct application ap; struct rt_i *rtip; main() { rtip = rt_dirbuild(``model.g''); rt_gettree(rtip, ``car''); rt_prep(rtip); VSET( ap.a_point, 100, 0, 0 ); VSET( ap.a_dir, -1, 0, 0 ); ap.a_hit = &hit_geom; ap.a_miss = &miss_geom; ap.a_rt_i = rtip; rt_shootray( &ap ); } \endverbatim } \vbox{\beginverbatim hit_geom(app, pp) struct application *app; struct partition *pp; { printf(``Hit %s'', pp->pt_forw->pt_regionp->reg_name); } miss_geom(){ printf(``Missed''); } \endverbatim } \sectionheadthree{Ray Intersection Data} If a given ray hits something, the a_hit() routine is called, and is provided a pointer to the head of a doubly-linked list of {\bf partition} structures. Each {\bf partition} structure contains information about a line segment along the ray; the partition has both an ``in'' ({\bf pt_inhit}) and an ``out'' ({\bf pt_outhit}) hit point. Each hit point is characterized by the hit distance {\bf hit_dist}, which is the distance $t$ from the starting point {\bf r_pt} along the ray to the hit point. The linked list of {\bf partition} structures is sorted by ascending values of {\bf hit_dist}. As a result of this definition, the ``line-of-sight'' distance between any two hit points can be determined simply by subtracting the two {\bf hit_dist} values. This will give the distance between the hit points, in millimeters. If the variable {\bf a_onehit} was set non-zero, then only the first {\bf a_onehit} hit points along the partition list are guaranteed to be correct; any additional hit points provided should be ignored. This is usually important only when {\bf a_onehit} was set to an odd number; the value of {\bf pt_outhit} in the last {\bf partition} structure may not be accurate, and should be ignored. If the actual three-space coordinates of the hit point are required, they can be computed into the {\bf hit_point} element with the C-language version of $ \vec A = \vec P + t * \vec D $: \beginverbatim VJOIN1(hp->hit_point, rayp->r_pt, hp->hit_dist, rayp->r_dir); \endverbatim \sectionheadthree{Surface Normals} As an efficiency measure, only the hit distances are computed when a ray is intersected with the model geometry. The surface normal at any hit point can be easily acquired by executing a C macro. In addition to providing the unit-length outward-pointing surface normal in struct {\bf hit} element {\bf hit_normal}, this macro also computes the three-space coordinates of the hit point in struct {\bf hit} element {\bf hit_point}: \beginverbatim RT_HIT_NORM( hitp, stp, rayp ); \endverbatim \sectionheadthree{Gaussian Curvature} For any hit point, after the surface normal has been computed, the Gaussian surface curvature [STOK69] at that hit point can be acquired by executing the C macro: \beginverbatim RT_CURVE( curvp, hitp, stp ); \endverbatim At the hit point, there exists exactly one pair of orthogonal directions also orthogonal to the surface normal $\vec N$ for which the values of $c$ take on the minimum and maximum values $c_1$ and $c_2$. $c_1$ and $c_2$ are the inverse radii of curvature, and $ |c_1| \le |c_2| $, i.e. $c_1$ is the most nearly flat principle curvature. A positive curvature indicates that the surface bends toward the (outward pointing) normal vector $\vec N$ at the hit point. A {\bf curvature} structure has three elements, the unit vector {\bf crv_pdir} (or $\vec A$) pointing in the direction of the first principle curvature, the scalor {\bf crv_c1} (or $c_1$) giving the curvature in the first principle direction, and the scalor {\bf crv_c2} (or $c_2$) giving the curvature in the second principle direction $\vec B$. The second principle direction $\vec B$ is implied and can be found by taking the cross product of the normal with {\bf crv_pdir}, i.e., $ \vec B = \vec N \times \vec A $. \sectionheadthree{U-V Mapping} Each primitive solid can be considered to be bounded by one or more {\em regular surfaces}. Each regular surface is defined as the locus of points $\vec S ( u, v )$ depending on two real parameters $u$ and $v$ which range from 0.0 to 1.0 inclusive. These parameters form the coordinates of a two-dimensional Cartesian $u,v$-plane. A given $(u,v)$ coordinate will appear only once on each regular surface, but in objects with more than one surface that same $(u,v)$ pair may appear at more than one place on the object. The $(u,v)$ coordinate of the hit point is returned in {\bf uvcoord} structure elements {\bf uv_u} and {\bf uv_v}. For any hit point, after the value of {\bf hit_point} has been computed, the $(u,v)$ coordinates of that point can be acquired by executing the C macro: \beginverbatim RT_HIT_UVCOORD( ap, stp, hitp, uvp ); \endverbatim For some simple lighting-model applications, it is sometimes desirable to create a mapping between the coordinate system on the surface of an object to coordinates on a plane. This is generally used to drive simple, two dimensional {\it texture mapping} algorithms. The most common application is to extract a ``paint'' color from a rectangular image file at coordinates $(u,v)$, and apply this color to the surface of an object. These parameters can also be used to simulate the effect of minor surface roughness using the {\it bump mapping} technique. Here, the $u$ and $v$ coordinates index into a rectangular file of perturbation angles; the surface normal returned by RT_HIT_NORM() is then modified by up to $\pm 90$ degrees each in both the $u$ and $v$ directions, according to the stored perturbation. In addition, the approximate ``beam coverage'' of the ray in terms of the parameters $(u,v)$ is returned in the structure elements {\bf uv_du} and {\bf uv_dv}. These approximate values are based upon the ray's initial beam radius ({\bf a_rbeam}) and beam divergence per millimeter ({\bf a_diverge}) as specified in the application structure. These delta-$u$ and delta-$v$ values can be helpful for anti-aliasing or filtering areas of the original texture map to produce an ``area sample'' value for the hit point. \sectionheadtwo{Three Dimensional Surface Mesh} Combinatorial Solid Geometric (CSG) models are formed by the boolean combination of ``primitive'' solids [MUUS87a]. For example, a plate with a hole is most easily modeled as a plate primitive minus a cylinder primitive. It is important to note that in CSG models, there is no explicit representation of the surfaces of the solids stored; indeed, for complex boolean combinations of complex primitives, some of the resultant shapes may have very convoluted topology and surfaces that may be at best high degree polynomials. There are many applications that would benefit from being able to express an {\it approximation} of the complex shapes created using CSG modeling as a collection of planar N-gons which together enclose roughly the same volume of space as the original CSG solid. The most obvious such application is to drive polygon-based rendering routines (lighting modules) for predictive optical signatures. On many modern workstations there is direct hardware or firmware support for high-speed rendering of polygons [MOLN87]. In addition, there are whole collections of polygon-based predictive infra-red and radar signature programs. The very best predictive radar signatures can be calculated using the Method of Moments, which requires having a three dimensional surface tessellation to sub-wavelength resolution of the entire model. A technique for computing this approximate three dimensional surface tessellation is the focus of the majority of this paper. \sectionheadtwo{Topological Representation} Some predictive radar signature codes, such as the TRACK code of GTRI [PELF86], do not operate directly on a geometric representation of an object. Instead, they rely on the fact that large radar returns occur primarily due to the existence of dihedral and trihedral structures in the object. Rather than describing a vehicle simply as a collection of these topological structures, it is possible to analyze a three dimensional solid model to locate all instances of the topological features of interest. For example, the software could locate planar face elements; edges where two locally planar elements join to make a dihedral, edges where three locally planar elements join to make a trihedral, etc. Then this list of topological features is used as input to the feature-based analysis code. % $Header: /vld/mike/talks/90nmg/RCS/joined.html,v 1.1 1998/05/01 06:53:13 mike Exp $ \sectionhead{System-Level Issues} It should be abundantly clear that it is highly desirable to have a single, central geometric database which can be interrogated by a full suite of analysis codes. Many fundamentally different kinds of model interrogation need to be supported in order to meet this goal. If a CAD system was being designed afresh, without {\it any} ties to the past, then any underlying representation could be chosen and used. In this section, the design considerations for expanding the kinds of model interrogation available to the BRL-CAD Package will be explored. While the BRL-CAD Package comprises a large amount of finished computer software, the main investment is in the existing library of geometric models. The amount of effort required to replicate these models can be conservatively estimated in the hundreds of man-years. In addition, the experience of the large number of trained model designers and design analysts is quite significant. Clearly, any design intended to expand the kinds of model interrogation available within the system must protect these investments. The BRL-CAD Package as it stood in 1989 could be considered to be one of the very few production CAD systems which was based purely on the combinatorial solid geometry (CSG) technique. The final shapes of all objects were created by boolean combinations of primitive solids. No attempt was made to represent in explicit form either the topology or the surface geometry of any object. The exact nature of the final form of an object was discovered only on a point by point basis, by sampling the object with ray-tracing. At the same time, the assortment of primitive solids available to designers was definitely a hybrid combination of traditional CSG primitives and more recent boundary-representation (B-rep) primitives. The primitive solids described by their boundaries included a variety of faceted solids, as well as solids defined by a closed collection of non-rational B-spline surfaces. This rich collection of primitive solids could be combined by the designer using any number of boolean operations. However, complex combinations of primitives could be difficult to visualize except through careful study of the three dimensional wireframe approximation rotating in real time, coupled with the judicious use of ray-traced renderings. Given that modern computer workstations [MOLN87] are now commonly available with integral polygon rendering hardware, and that hardware rendering speeds can exceed one million polygons per second, it seems highly desirable to be able to take advantage of this hardware. Also, as discussed earlier, there is a burgeoning supply of analysis software that simply can not make do with a geometry interrogation interface that supports only the ray-tracing paradigm. What was missing from the BRL-CAD Package was a way of obtaining an {\it explicit} description of the final shape of modeled objects. Our quest then is for a technique suitable for obtaining an explicit description of geometric objects. \sectionheadtwo{Boolean Operations} There are several classes of modeling operations that are very conveniently expressed in terms of boolean operations. For example, holes can be bored in objects by subtracting a ``drill bit'' solid from the original work piece, and the primary shape of an injection mold can be created by subtracting the desired final product from one or more blocks of mold material. Designers who have experienced the conceptual power of using boolean operations to construct complex shapes are unlikely to want to switch to a system that does not permit the use of boolean operations. Given that the existing investment in geometric models depends heavily on the use of boolean operations, it was concluded that adding the capability for obtaining an explicit description of modeled objects must provide full support for the use of boolean operations. This conclusion immediately places several rather severe requirements on the design. Most importantly, it requires that the underlying representation used to hold the explicit description of the modeled objects must be {\it closed} under boolean operations. That is, given the explicit description of objects A and B, then any boolean combination of A and B must be representable as an explicit description expressed in terms of the same underlying representation. Several available choices of representation will be considered. \eject \sectionheadtwo{The Underlying Representation} A strictly polygonal representation could be selected. While performing boolean operations on solids described as collections of polygons is not easy, the representation can (with certain special definitions) be considered to be closed under boolean operations, and algorithms to accomplish the boolean evaluation have been published for several years [LAID86]. A representation comprised exclusively of rectangular parametric surfaces, such as B-splines or similar tensor-product surface patches could be used. However, research to date has shown that while B-spline surfaces can be combined using boolean operations, the resulting object can not be expressed strictly in terms of B-splines [THOM84]. Instead, a mixed representation of B-splines and polygons is produced, and this mixture becomes ungainly when subjected to repeated boolean operations. This occurs because the boolean combination of rectangular parametric surfaces is not necessarily bounded by rectangular parametric surfaces; i.e., the representation is not closed. Recent work has suggested that a representation comprised of trimmed B-splines and shared-edge polylines might be closed under boolean operations [COBB84], but a full implementation is not yet known to exist. No other good choices for an underlying representation could be found. Because the B-spline representation does not have closure under the set of boolean operations, it regrettably could not be used. Therefore, there was no choice; the explicit representation of modeled objects would have to be expressed in terms of collections of polygons. This certainly met the requirements of the polygon based application codes, but it posed a whole host of new questions. \sectionheadtwo{Topology} Given that the explicit geometric representation of surfaces will be approximated using polygons, there still remains the question of how to deal with the representation of the topology. The simplest strategy would be to simply ignore topology, and store solid objects as collections of polygons. This has several drawbacks because these objects are intended to represent enclosed volumes of space. It could be quite difficult to verify that a given collection of polygons is in fact a valid solid, without any cracks, dangling faces, or missing faces. Also, implementing boolean operations without any explicit topology would be nearly impossible. Traditionally, solid modeling systems based on boundary representations such as PADL [REQU82] have employed the {\it winged edge} data structure for storing topology, as discussed earlier. The disadvantage of the winged edge data structure is that it is simply unable to represent many of the non-manifold conditions that arise in the construction of complex shapes (such as finite element meshes), and the non-manifold conditions that arise from the use of the intersection operator ($\cap$) on two objects that share only a single face, edge, or vertex. Those systems employing the winged edge data structure that also support boolean operations (such as PADL) have had to resort to the use of {\it regularized boolean operators} which are defined in such a way as not to produce any non-manifold results. These regularized boolean operators are denoted by a superscript asterisk, i.e., regularized union is $\cup ^ *$, regularized intersection is $\cap ^ *$, and regularized subtraction is ${-} ^ *$. It seems unfortunate to have to restrict boolean operations on the polygonal representation to not include any non-manifold results. Some applications might desire them, and others might not; unwanted non-manifold results are easy to discard, but there is no easy way to re-infer the existance of non-manifold results if the representation can not express them. This is akin to the ``language limits thought'' concept from cognitive psychology. Non-manifold results can be useful in a variety of ways. One example is in interference or overlap checking. The intersection of two objects can be computed. If the intersection is the null set, then the two objects are disjoint, and there is space between them. If the intersection is a solid object, then the two objects overlap in the given volume, which generally signals a modeling error. If the intersection is a lone face, edge, or vertex, then the two objects exactly touch, but do not overlap. The inability of the ``winged-edge'' data structure to represent non-3-manifold conditions prompted Weiler to evaluate existing edge-based data structures [WEIL85]. This resulted in the development of a new data structure suitable for representing all the Non-3-Manifold Geometric (NMG) and topological configurations that boolean operations might produce [WEIL87]. This new data structure has been dubbed alternately the ``radial-edge'', or ``NMG'' data structure. Because of this structure's ability to handle 3-manifolds (solids), 2-manifolds (faces), 1-manifolds (edges), and 0-manifolds (points), NMG objects are closed under boolean operations. The NMG data structures have the advantages of complete generality and closure under boolean operations, plus they encode the full topological structure of an object, as well as the geometric information. The representation contains full topology information, so that the relationships between vertices, edges, loops, faces, and shells are continuously available. Geometry is associated with each topological element. For example, the geometry information associated with a planar face is the plane equation which includes the outward-pointing surface normal; the plane equation does not have to be re-derived from the vertices. This generality does come at a significant price in increased memory use compared to the winged-edge data structure. However, because of the anticipated frequency of occurance of non-3-manifold conditions in CSG modeling, both intentionally and as part of various analysis operations, the NMG data structures were selected to contain the approximate surface representation. \eject \sectionheadtwo{Conversion versus Post-Processing} Several of the existing and planned primitive solids have very complex curved shapes. Some examples include the torus, the truncated generalized cone, the hyperboloid of two sheets, the general polynomial solid, and the B-spline solid. In general, these solids have few or no sub-sections which are flat. Thus, these solids can not be represented by a collection of polygons without loosing essential information about the very nature of the solids. Yet, the desire to have a homogeneous representation suggests that all existing solids should be converted to a single new underlying representation, so as to take advantage of the boolean closure property, and to enable applications to access the explicit surface representation. The two options to consider are either (a) making a one-time conversion of all existing models to a polygonal form, and then performing all subsequent editing and processing on a polygonal database; or (b) retaining the existing, implicit combinatorial solid geometry database, and providing some form of post-processing capability to convert the implicit CSG shapes into an explicit, polygonal form. Many existing application codes that use the ray-tracing paradigm depend on being able to obtain very accurate surface normal and Gaussian curvature information at any point on an object. While surface normal interpolation [GOUR71] can be used with a polygonal representation, many artifacts can be introduced, including surface normal discontinuities across polygon boundaries and inconsistencies between the apparent and actual location and shape of profile edges. While these artifacts may be entirely tolerable in simple rendering applications, they are entirely inappropriate in a CAD system targeted for high-resolution engineering analysis. Finally, it would be extremely distasteful to have to {\it reduce} the quality of the ray-tracing style of interrogation in order to accomodate the ability to obtain explicit object surfaces. Therefore, the conclusion was that the existing combinatorial solid geometry database would remain unchanged, and that any application that required an explicit representation of the modeled shapes would obtain that explicit representation through some form of conversion of the underlying CSG database. While this capability needs to be available to any application at any time, it can still be thought of as being a ``post-processing'' operation. This choice of strategy has a number of fortunate implications. Because a polygonal representation of a fundamentally curved shape could never be more than an approximation of that shape, it is impossible to choose a single resolution approximation that would satisfy all applications. Using a coarse approximation would quickly produce complaints about a lack of accuracy in the modeling system. For example, few engineering applications could tolerate octagonal pipes being substituted for genuine round pipe. On the other hand, using a very fine approximation would consume gargantuan amounts of memory, which would impede simple operations such as model editing and display. With this strategy, the polygonal representation can be considered just an {\it approximation} of a much more accurate underlying geometric model. Furthermore, because this approximation can be created dynamically, each application has the opportunity to control the resolution of the approximation being created. This permits each application to obtain exactly the degree of resolution required, without having to worry about the approximation being too coarse or too bulky. \sectionheadtwo{Implementation Tactics} The strategy that has been adopted has several key points. Whenever an application requires an explicit description of the surface of an object, it will access the {\it Application Interface} to obtain an approximation created to meet accuracy requirements of this particular application. The explicit representation of the object will be returned as a collection of planar faces embedded in the NMG data structures. The existing Application Interface to the geometry database already has a nice simple programming interface. Thus, it seems appropriate to have a high-level interface similar to {\bf rt_gettree()}. The application would indicate what objects or object heirarchies are to be retrieved from the database, and what the accuracy requirements are, and would be given in return a collection of NMG data structures that would contain the surface approximation of the indicated objects. \captionfig 4.5in by 3in, nmg-schematic, Figure 3 -- Schematic NMG Wiring Diagram. %\figspace {3in} {4.5in} {X-3} {Schematic NMG Wiring Diagram.} The actual implementation of the application interface can be further broken into several pieces. The existing routine {\bf db_walk_tree()} is used to retrieve the indicated objects from the database. Each solid retrieved from the database needs to be converted to an approximate faceted form stored in NMG data structures. This operation is referred to as {\it tessellation}. As each boolean operation is encountered in the database, the appropriate tessellated solids will have that boolean operation performed by the routine {\bf nmg_do_bool()}. This routine will take the two tessellated objects and combine them according to the boolean operation back into a consistent set of solid tessellated objects. Until very recently, it has been this step that has proven the most difficult [LAID86]. Once all the objects have been retrieved from the database and combined with their boolean formulas, the resultant collection of NMG objects is returned to the application. (More precisely, the application is returned a {\bf struct model} which contains pointers to the requested objects, stored as one or more {\bf struct nmgregion}s). This architecture gives rise to the schematic diagram in Figure 3. In the existing ray-tracing implementation, {\bf librt} makes heavy use of an object-oriented style of procedural interfaces to geometry support routines. This object-oriented programming interface already defined a standardized set of operations that could be performed on geometric objects. The operations include having a geometric object read itself into memory, describe itself, produce a wireframe representation of itself, and intersect a ray with itself. This interface was extended to define a new operation to require an object to tessellate itself into an NMG data structure. This has the highly desirable property that all the processing related to a given primitive solid remains centralized in a single solid-specific geometry module. Thus, adding a new primitive solid requires only the addition of a single module to the library; none of the analysis codes ever need to be modified when designers begin using a new kind of primitive. \sectionheadtwo{Interface to Applications} From the schematic diagram it should be clear that the final evaluated NMG solid object can be employed in a variety of ways. The primary use will be for input to visualization and analysis software that needs an approximate three dimensional surface mesh of the solid model. However, a very powerful additional use will be to create new faceted shapes which are then stored back in the database as new geometric objects, suitable for future editing or analysis. As will be explained in more detail in subsequent chapters, each face of an NMG object will be composed of one or more planar N-gons, each potentially non-convex and with embedded internal loops. Applications that are prepared to deal with this topological richness may operate on the NMG representation directly. However, for those applications that require a simpler face topology, a simplification routine exists that will reduce each face to a collection of planar N-gons. These simplified N-gons may be non-convex but will have no embedded internal loops. Finally, for applications that prefer faces to be collections of simple triangles, a {\it triangulator} routine will be provided that convertes the NMG faces into well-behaved triangles [GOOD89]. \sectionhead{Non-Manifold Geometry} One of the keys to the NMG approach lies with the concept of the radial-edge representation as opposed to the classical winged-edge. Within the winged-edge representation, an edge represents the boundary between exactly two faces. The drawback to this is that an infinite number of planes or faces can intersect in a single line in three dimensional space. The winged edge representation only allows for a pairwise topological connection between these faces. The radial-edge representation topologically links all faces which share the edge as a line of intersection. The implementation described in this paper is heavily patterned after a description of the radial-edge data structures and operations written by Weiler [WEIL87]. \captionfig 3.0in by 2.5in, hierarchy, Figure 4 -- NMG Structure Hierarchy. \sectionheadtwo{Separation of Topology and Geometry} The basic topological elements are the vertex, edge, loop, face, shell, region, and model. The relationship between these elements of the hierarchy is depicted in Figure 4. Note that for any element within the hierarchy, there is a direct path from that element to the element which is one level higher, and also to the element which is one level lower. The {\it vertex} represents a unique topological point. The {\it edge} is a line or curve in space terminated by either one vertex, or two distinct vertices. The {\it loop} is either a single vertex, or a circuit of one or more edges. A loop defines a circuit or a boundary of a space. The {\it face} consists of one or more loops, and represents an actual surface area. The use of a loop within a face may define either an exterior loop or an interior loop. Exterior loops include an area in the face. Interior loops exclude an area from the face surface, thereby causing a hole in the face. The {\it shell} is either a single vertex, or a collection of faces, loops, and edges. The collection of faces in a shell may enclose a volume, thereby creating closed objects, or may represent arbitrary surfaces. Loops and edges of a shell are refered to as ``wire loops'' and ``wire edges.'' They may be used in creating wireframe aspects of the model. The {\it region} is a collection of shells, and the {\it model} is a collection of regions. For the elements vertex, edge, loop, and face, there is a distinction between the existence of the element and instances of the use of the element. This allows multiple topological elements to share the same underlying form and geometry. The {\it vertexuse} is an instance or a use of a vertex. The {\it edgeuse} is a directed instance of an edge. The {\it loopuse} is an instance of a loop. The {\it faceuse} is an instance or a use of a face. Each side of the face is uniquely represented by a faceuse, i.e., every face is referenced by exactly two faceuses. Finally, note that each topological element makes reference to a separate geometric element. As a result of this separation of topology and geometry, the kinds of geometric support in the modeling system may evolve into richer and richer forms, while continuing to enjoy a common set of topological elements with a stable interface. For example, the system described in this paper is based upon manipulation of planar facets. However, in the future the geometry support of the system will be expanded to support curved facets or B-splines, while retaining the same interface to the topology. \sectionheadtwo{The Data Structures in Detail} \vskip -22pt % \sectionheadthree{Magic Numbers and Memory Descriptors} The first {\bf long} (longword of memory) in any of the NMG structures is dedicated to a {\it magic number}. It will be found either listed explicitly as the first entry in the structure definition, or it will be hidden, obtained implicitly from the {\bf struct nmg_list} sub-structure (described below) which is the first entry in the structure definition. Thus, it is always located at an offset of zero bytes from the start of the structure. This magic number serves a dual purpose. First, every subroutine that is passed a pointer as a parameter can dereference that pointer to obtain the magic number. If the magic number obtained does not match the magic number assigned for use with that kind of data structure, then either memory has become corrupted, or a defective pointer has been provided as a parameter. Given that some NMG operations may have to dereference pointers through seven connected data structures, it is advantageous to detect invalid pointers as early in the process as possible. Second, some data structures employ {\it generic} pointers which may refer to one of several different kinds of structures. Rather than using an extra word of memory to store a type indicator, the generic pointer can be dereferenced to obtain the magic number, and thus the identity, of the referred-to structure. \sectionheadthree{Structure Indices} A count of the number of structures within a model is kept. Each structure type contains an integer ``index'' member which uniquely identifies the instance of a structure type within the model. This assists algorithms which must temporarily associate some flag or bit of information with structures. In these instances, an array can be allocated with the appropriate size so that there exists one array element for each structure in the model. As the model hierarchy is walked, the index elements can be used to quickly access the temporary information appropriate for this particular structure. Applications for this include copying the model between memory and disk, and flags to help assure that every structure is visited or operated upon exactly once. \sectionheadthree{Linked lists} %\label{linkedlists} The NMG data structures make frequent use of doubly linked lists. With one exception, they are all implemented using the same strategy and list manipulation macros. (It is the radial-edge linked list which does not follow this form.) All linked lists are made up of ``nmg_list'' structures: \vbox{ \beginverbatim struct nmg_list { long magic; /* magic number */ struct nmg_list *forw; /* ``forward'', ``next'' */ struct nmg_list *back; /* ``back'', ``last'' */ }; \endverbatim } The magic number field of this structure identifies the node as either a list head or as a structural element. The two pointers are to the successor and predecessor of the node in the list. Every list has one structure which is dedicated to functioning as the ``head'' node. An empty list consists of a ``head'' node whose ``forw'' and ``back'' members are pointers to the ``head'' node. Defining the doubly linked list as having an explicit ``head'' means that the enqueue and dequeue operations can operate on any member of the list, and they do not need to refer to the head. Consider the task of making a linked list of {\bf edgeuse} structures. The first element of the {\bf edgeuse} structure is an {\bf nmg_list} structure named {\bf l}. Thus, the address of {\bf l} is a {\it pun} (or homonym) for the address of the {\bf edgeuse} structure. By adding {\bf l} to a linked list, in reality the whole {\bf edgeuse} structure has been added to the linked list. This allows the list manipulation functions to be generalized to handle lists of any kind of structures. The manipulation routines merely operate on {\bf nmg_list} objects and need not know details about what structure types are in the list. The only requirement is that the {\bf nmg_list} structure must appear as the first element in the containing structure. A rich set of macros exist for insulating the programmer from all the details of inserting and deleting elements from a list, walking a linked list, and various initialization and clean-up operations. \sectionheadthree{Naming Conventions} When creating variable names and structure member names, the implementation makes heavy use of abbreviations. As a result, it was important to regularize the abbreviation strategy. The suffix ``_p'' is appended to the end of all pointer variables in the structures. The first characters of the variable indicate the type of object the pointer references. For example, a pointer to a vertex structure would be ``v_p'', and ``vu_p'' would be a pointer to a vertexuse structure. Some structures types may have a variety of different structure types as ``parent'' or ``child'' structures. Since each structure maintains a pointer to its parent and children, a method for maintaining a syntactically correct handle for such objects is required. Such pointers are stored as unions of pointers to each possible type of structure required, plus a pointer to a magic number. For example, Figure 4 demonstrates that a vertexuse may have either a shell, a loopuse or an edgeuse for a parent. As a result, the vertexuse structure will contain something similar to the following: \vbox{ \beginverbatim union { struct shell *s_p; struct loopuse *lu_p; struct edgeuse *eu_p; long *magic_p; } parent; \endverbatim } This union provides a handle for each possible type of parent for the vertexuse structure. In addition, it contains a ``pointer to magic number'' handle. This allows the type and validity of the parent to be identified as a particular structure type, {\em before} the parent structure is referenced. This union owes its existence to the Pascal origins of the implementation by Weiler. In the C language, a simple ``pointer to long integer'' and the language's ability to {\it coerce} one type of pointer into another type of pointer using type-casting would have been sufficient. It is debatable whether type-casting or the union-name-handle approach produces more readable source code. The names for linked list ``head nodes'' use the ``_hd'' suffix, and the first letters indicate the type of object in the list. For example, the head of a list of vertexuse structures would be called ``vu_hd''. When a structure is to be a part of a linked list, the first element of the structure will be an element ``{\tt l}'', the list node which becomes a member of a linked list. As described in the section on linked list implementation, by keeping this item as the first element in the list, the list manipulation interface can be made fully general for lists of all types of elements. % was 3.75 by 3.5 \captionfig 2.5in by 2.35in, vertex, Figure 5 -- Vertex and Vertex Uses. \sectionheadthree{Vertex and Vertexuse} The simplest element in the system is the {\it Vertex}. A vertex represents a single point within the topological space of the object being modeled. It also serves as a linkage point for connecting the topological model with the geometrical data. The structures ``vertex'' and ``vertexuse'' can be conceptually viewed as in Figure 5. The magic number is stored directly as the first element of the structure. The second item is an ``nmg_list'' substructure. This substructure forms the head of a doubly-linked list of all the {\it uses} of this vertex. The member ``vg_p'' is a pointer to the geometry. The index element keeps the structure index for the particular vertex instance. The vertex structure is referenced through a vertexuse structure. \setbox0=\vbox{ \beginverbatim struct vertex { long magic; struct nmg_list vu_hd; struct vertex_g *vg_p; long index; }; struct vertexuse { struct nmg_list l; union { struct shell *s_p; struct loopuse *lu_p; struct edgeuse *eu_p; long *magic_p; } up; struct vertex *v_p; struct vertexuse_a *vua_p; long index; }; typedef double point_t[3]; struct vertex_g { long magic; point_t coord; long index; }; \endverbatim } \addfigure0 The ``l'' element of the vertexuse structure is entered on the vertex structure's ``vu_hd'' list, which is a list of all uses of the vertex. This linked list node also contains the magic number for the vertexuse structure. A vertexuse may be needed by any of the higher level objects: shell, loopuse, or edgeuse. The union ``up'' contains a pointer to each of these three structure types. It also contains a pointer to a magic number, which can be used as a handle for getting the magic number of the parent. The element v_p is a pointer to the vertex being {\it used} by this vertexuse. The vertexuse may have an associated vertexuse attribute structure. This structure is referenced through the ``vua_p'' pointer. One example of such information might be to store a surface normal for each vertexuse, suitable for intensity interpolation shading algorithms used in Gouraud shading [GOUR71], or for normal-vector interpolation shading algorithms. The vertex geometry structure is very simple and straightforward. It consists of a magic number, the coordinates of the vertex, and a structure index. The coordinates are stored in a variable of type point_t, which is an array of three double-precision floating point numbers. % Was 5in by 2.25in; page is only 4.5in wide! \captionfig 4in by 1.75in, edge, Figure 6 -- Edge and Edgeuse. \sectionheadthree{Edge and Edgeuse} The next topological element is the {\it edge}. The edge represents a line or curve between a pair of vertices. The unique members of this structure are ``eu_p'' which is a pointer to one of the uses of the edge, and ``eg_p'' which is a pointer to the edge geometry. The edge geometry structure is reserved for future curved-edge support. Note that the edge structure itself does not reference the endpoints of the edge. The endpoints are accessed through the edgeuse structure because almost all references to the edge endpoints occur while processing the edgeuse structures [WEIL87]. Within the edgeuse structure, the edge struct pointer ``e_p'' ties the edgeuse to the appropriate edge. \setbox0=\vbox{ \beginverbatim struct edge { long magic; struct edgeuse *eu_p; struct edge_g *eg_p; long index; }; struct edgeuse { struct nmg_list l; union { struct loopuse *lu_p; struct shell *s_p; long *magic_p; } up; struct edgeuse *eumate_p; struct edgeuse *radial_p; struct edge *e_p; struct vertexuse *vu_p; long index; }; \endverbatim } \addfigure0 % was 4.75in by 3.9in, page is only 4.5! \captionfig 4.5in by 3.75in, radialedge, Figure 7 -- Radial Edge Structure. Each edgeuse references one vertex via the vertexuse structure pointer ``vu_p''. The other end of the edge/edgeuse is referenced through the first edgeuse's {\it mate} edgeuse. The pointer ``eumate_p'' connects an edgeuse to it's edgeuse mate. The eumate_p edgeuse is conceptually the use of the edge on the opposite side (interior/exterior wise) of the face from the existing edgeuse. The ``eumate_p'' and ``radial_p'' pointers form a linked list of the ``radial uses'' of an edge. The edgeuse referenced by ``eumate_p'' is on the opposite loopuse/faceuse of the same loop/face. The edgeuse ``l'' list node is used to form loops of edges, or to keep lists of all of the ``wire edges'' which are a part of a shell. Like the vertexuse, the edgeuse can be referenced by one of two different types of structures higher in the hierarchy. The same technique is used for providing handles for these ``parent'' structures as was used for the vertexuse. % was 4 by 5. \captionfig 2.75in by 3.5in, looptypes, Figure 8 -- Variations of the Loop. \sectionheadthree{Loop and Loopuse} A loop defines a boundary or circuit. Conceptually, a loop consists of either a single vertex, or a series of one or more edges in a circuit. Like the edge, most of this information is stored in the use structure. The loop structure member ``lu_g'' is a pointer to the geometry support for the loop. The member ``lu_p'' connects the loop structure to one of the loopuses of the loop. From that loopuse, the other use of the loop is reached through the ``lumate_p'' structure pointer. The geometry structure continas a bounding box for the loop. \setbox0=\vbox{ \beginverbatim struct loop { long magic; struct loopuse *lu_p; /* Ptr to one use of this loop */ struct loop_g *lg_p; /* Geometry */ long index; }; struct loopuse { struct nmg_list l; union { struct faceuse *fu_p; struct shell *s_p; long *magic_p; } up; struct loopuse *lumate_p; char orientation; struct loop *l_p; struct nmg_list down_hd; long index; }; \endverbatim } \addfigure0 The loopuse structure is where most of the loop details are handled. The first element is a linked list node, so that faces and shells may keep track of collections of loopuses. The union ``up'' provides a handle for all possible parents of the loopuse. The ``lumate_p'' member provides a pointer to the other use of the same loop as this loopuse. Often the other loopuse will be the use of this loop on the opposite surface of a face. The ``orientation'' member is used to define whether this loopuse is being used to enclose space, or exclude space within a face. The loopuse is associated with a particular loop through the pointer ``lu_p.'' The structure member ``down_hd'' is a list head which is used to access the component elements which form the loop. In the case where the loop is made up of one or more edges, this list will consist of a series of edgeuses. When the loop is formed on a single vertex, the first and only item in the list will be the vertexuse associated with the loopuse. \captionfig 3in by 3in, loopedges, Figure 9 -- Orientation of Edgeuses within a Loopuse. Figure 8A depicts a use of a loop (a loopuse) where the boundary formed by the loop consists of a single vertex. Figure 8B depicts a loop which is formed of one edge, and Figure 8C depicts a loop which is formed of four edges. When the loopuse is made up of edgeuses, they will be arranged to form a circuit. The mates to these edges will form a circuit for the loopuse mate. If the loopuses are a part of a faceuse, the edgeuses are arranged in a special orientation. When the cross product of the vector of the edgeuse and the normal vector for the faceuse is taken, the resultant vector should point into and along the surface of the face. See Figure 9. %\clearpage \sectionheadthree{Face and Faceuse} The face represents a planar or curvilinear two-dimensional boundary or surface. The pointer ``fu_p'' is a pointer to one of the two faceuses of the face, the other being reached through that faceuse's ``fumate_p'' pointer. The pointer ``fg_p'' references the geometry structure for the face. The face geometry structure keeps a bounding box, and the plane equation of the face. The equation is stored as a 4-tuple of double precision floating point numbers. A point $\vec A$ which lies on the plane will satisfy the following relation: $$ N_x * A_x + N_y * A_y + N_z * A_z - N_3 = 0 $$ \vbox{ \beginverbatim struct face { long magic; struct faceuse *fu_p; struct face_g *fg_p; long index; }; \endverbatim } \vbox{ \beginverbatim typedef double plane_t[4]; struct face_g { long magic; plane_t N; point_t min_pt; point_t max_pt; long index; }; \endverbatim } Faceuses represent a side of the surface of a face. Each face will therefore have exactly two faceuses associated with it. The first element in the faceuse structure is a linked list node. This is here so that the shell may keep a list of all the faceuses which are in the shell. The pointer ``s_p'' is a pointer to the parent shell of the faceuse. The other use of the same face is indicated by the faceuse pointer ``fumate_p''. The ``orientation'' member indicates which side of the face is represented by the faceuse. It actually indicates whether the surface normal of the faceuse is the same as the normal stored in the face geometry structure, or whether the normal is reversed. The faceuse is associated with a particular face through the ``f_p'' pointer. ``lu_hd'' keeps track of all loops in the face. \vbox{ \beginverbatim struct faceuse { struct nmg_list l; struct shell *s_p; struct faceuse *fumate_p; char orientation; struct face *f_p; struct nmg_list lu_hd; long index; }; \endverbatim } \sectionheadthree{Shell} The shell represents a set of collected, inter-related (and probably connected) items. The first element is a linked list node to allow groups of shells to be collected into a list. The member ``r_p'' is a pointer to the parent nmgregion for the shell. The attribute or geometry structure for the shell as a whole are refered to through the pointer ``sa_p''. The lists ``fu_hd'', ``lu_hd'', ``eu_hd'' are used to keep track of the faceuses, wire loopuses, and wire edgeuses which make up the shell. The pointer ``vu_p'' points to a single vertexuse when the shell consits of a single vertex. The shell attribute structure ``sa_p'' is used to store a bounding box for the entire shell. \vbox{ \beginverbatim struct shell { struct nmg_list l; struct nmgregion *r_p; struct shell_a *sa_p; struct nmg_list fu_hd; struct nmg_list lu_hd; struct nmg_list eu_hd; struct vertexuse *vu_p; long index; }; \endverbatim } \eject \sectionheadthree{Region} Regions are used to keep collections of associated shells within the model space. The nmgregion is included in the model's list of regions through the linked list node at the head of the region structure Because the structure name ``region'' was already in extensive use through out the BRL-CAD Package when the development of the NMG capability was begun, the structure has been called ``nmgregion'' instead of simply ``region''. At some point in the future, the implementation will probably be altered so that all NMG structures begin with the prefix ``nmg''. The ``nmgregion'' structure consists of a linked list node ``l'', a pointer to the parent model ``m_p'' and a list of shells which make up the region ``s_hd''. The region attributes structure is used to store a bounding box for the entire region. \vbox{ \beginverbatim struct nmgregion { struct nmg_list l; struct model *m_p; struct nmgregion_a *ra_p; struct nmg_list s_hd; long index; }; \endverbatim } \sectionheadthree{Model} The model represents the top of the hierarchy for the NMG structures. The list ``r_hd'' keeps track of all regions or ``nmgregions'' in the model space. The long integer ``maxindex'' contains the number of structures which have been allocated in the model. It exists so that arrays can be allocated with one element for each structure in the model. \vbox{ \beginverbatim struct model { long magic; struct nmg_list r_hd; long index; long maxindex; }; \endverbatim } \sectionheadtwo{Variations} There are several differences between this implementation of the radial edge data structures and Weilers implementation [WEIL87]. Some of the differences are a result of the different programming languages used, while others are a result of the different goals of the implementations. While Weiler was implementing an entire modeling system based exclusively upon the NMG structures, within the BRL-CAD Package NMG objects are just one representation of many. The differences are outlined as follows: \beginitemlist \listitem Wire loops are permitted as members of the shell to simplify the creation and manipulation of loops and faces within the system. This also permits a shell to be comprised of a ``point cloud'' made up of loops on individual vertex points. \listitem Each of the structures faceuse, loopuse, and edgeuse as described by Weiler had attribute substructures which were used for storing information unique to a particular use of the object. This has not proven necessary in this implementation. \listitem The shell keeps a list of all wire edges within the shell. Under the system described by Weiler, some wire edges were ``discovered'' by looking at vertices (vertexes) used in the shell, to find other uses of the same vertex(es) which were children of edgeuses whose parent is the same shell. \listitem The linked lists in the Pascal language structures described by Weiler were maintained by directly manipulating ``next'' and ``last'' pointers within the structures. In this implementation, all structures which are kept in lists contain a generic ``list node''; manipluation of the linked lists is via a standardized set of macros. \listitem In this implementation, generic pointers which may reference more than one type of structure are disambiguated by dereferencing the pointer and inspecting resulting ``magic number''. Because Pascal is a ``strongly typed'' programming language, Weiler's implementation required that a structure pointer be disambiguated before it was dereferenced. Hence an additional variable in the structure containing the pointer was used to indicate the appropriate interpretation for the generic pointer. \listitem All uses of a face must belong to one shell. \enditemlist \sectionhead{NMG Library Interface} The applications programmer is insulated from the details of the NMG radial-edge data structures by a library of functions which perform all of the basic tasks. Each of the routines accepts a valid NMG model or a part of one, and performs an operation, returning a valid model upon completion. The routines within the library can be classified as constructive, destructive, or manipulative. This chapter provides a basic description of the routines in these categories. Within the library, all routines which are intended for use by the applications programmer or user begin with the ``nmg_'' prefix. \sectionheadtwo{Construction Routines} The basic constructive routines all have the letter ``m'' (which stands for ``make'') immediately after the ``nmg_'' prefix. \beginitemlist \listitem struct model *nmg_mm() {\it ``Make Model''} creates a new NMG model structure and fills in the appropriate fields. The result is an empty model. \listitem struct model *nmg_mmr() {\it ``Make Model, Region''} creates a new model with a call to ``nmg_mm'' and creates a region within the model. The region is empty. \listitem struct shell *nmg_msv(struct nmgregion *r_p) {\it ``Make Shell, Vertex''} creates a new shell consisting of a single vertex in the parameter region. A new vertex is created for the shell. \listitem struct nmgregion *nmg_mrsv(struct model *m) {\it ``Make Region, Shell, Vertex''} creates a new region within the existing model, and creates a shell of a single vertex within the region. \listitem struct vertexuse *nmg_mvvu(long *upptr) {\it ``Make Vertex, Vertexuse''} exists so that shells, loops and edges can be created on a new vertex. ``upptr'' points to the parent structure for which the vertex and vertex use are being created. The new vertexuse will reference this structure as its parent. \listitem struct vertexuse *nmg_mvu(struct vertex *v, long *upptr) {\it ``Make Vertexuse''} allocates a new vertexuse for an existing vertex. The vertexuse becomes a child of the structure indicated by ``upptr''. \listitem struct edgeuse *nmg_me(struct vertex *v1, struct vertex *v2, struct shell *s) {\it ``Make Edge''} creates a new wire edge in the shell specified. The vertex pointer parameters may either indicate vertexes for the endpoints of the new wire edge, or may be NULL pointers. New vertex structures will be generated for each NULL vertex parameter. \listitem struct edgeuse *nmg_meonvu(struct vertexuse *vu) {\it ``Make Edge on existing Vertexuse''} is used to create an edge on a vertex in a loop or shell. The resultant edge has the same vertex at each endpoint. \listitem struct edgeuse *nmg_eusplit(struct vertex *v, struct edgeuse *eu) \break {\it ``Edgeuse Split''} splits an existing edgeuse pair of a wire or ``dangling'' face-edge by inserting a new vertex. \listitem struct edge *nmg_esplit(struct vertex *v, struct edge *e) {\it ``Edge Split''} causes a new vertex to be inserted along an existing edge. If the parameter vertex pointer is NULL, an new vertex is created. The vertex inserted need not lie along the existing edge. See Figure 10. \listitem struct edgeuse *nmg_eins(struct edgeuse *eu) {\it ``Edge Insert''} inserts a new, zero length edge between the edge associated with the parameter edgeuse and the edge associated with the edgeuse ``previous'' to the parameter edgeuse. See Figure 10. \captionfig 4.75in by 1.8in, edgefunc, Figure 10 -- Edge Operators. \listitem struct loopuse *nmg_ml(struct shell *s) {\it ``Make Loop''} takes the largest possible number of contiguous wire edges which form a circuit from the parameter shell and uses them to create a wire loop in the shell. \listitem struct loopuse *nmg_mlv(long *magic, struct vertex *v, int orientation) {\it ``Make Loop, Vertex''} creates a new vertex-loop. The loop will be a child of the structure indicated by the magic number pointer parameter, and will have the specified orientation. If the vertex pointer is NULL, a new vertex is created for the loop. \listitem struct faceuse *nmg_mf(struct loopuse *lu1) {\it ``Make Face''} generates a new face from the parameter wire loop and its mate. \enditemlist \sectionheadthree{Convenience Routines} In order to simplify the creation of manifold and non-manifold faces, The following two routines are provided for the application developer. \beginitemlist \listitem struct faceuse *nmg_cface(struct shell *s, struct vertex **vt, int n) {\it ``Create Face''} creates a (non-manifold) face from a list of vertex structure pointers. The face will be a child of the shell indicated in the parameter list. The parameter ``vt'' is an array of pointers to vertex structures. The length of the array is indicated by the parameter ``n''. If ``vt'' is a null pointer, then the face will be created as a polygon on ``n'' new vertex structures. If ``vt'' is non-null, a null entry in the list will cause a new vertex to be allocated for that position. The vertexes in the list should be ordered in a clockwise manner for a viewer looking backwards along the normal vector of the desired face. \listitem struct faceuse *nmg_cmface(struct shell *s, struct vertex **vt[~], int n) {\it ``Create Manifold Face''} generates a manifold face in the indicated shell. The parameter ``vt'' is an array of ``n'' pointers to pointers to vertex structures. If a pointer in vt is a pointer to a null vertex pointer, a new vertex is created for that position. In this way, new vertices can be created conveniently within a user's list of known vertices. The vertices should be listed in ``clockwise'' order for a viewer looking backwards along the normal of the desired face. In addition to creating the face, the routine will join edges of the new face with dangling edges of other faces in the same shell. This makes it easier for the applications code to generate topologically correct, closed, manifold objects. \enditemlist \eject \sectionheadthree{Creating Faces} The usual technique for creating a model is to first allocate a model with a call to the ``Make Model'' routine ``nmg_mm''. The resultant model does not have any regions within it. Next, a region, and shell consisting of a single vertex are created with a call to ``Make Region, Shell, Vertex'' or ``nmg_mrsv''. This lone vertex will be consumed when the first edge or loop is created in the shell. At this point, there are many separate paths to creating the first face. If a manifold object is the desired goal, then one of the routines ``nmg_cface'' or ``nmg_cmface'' should probably be employed. Alternatively, a loop consisting of a single vertex can be created with a call to ``nmg_mlv'' (Make Loop, Vertex). Then a face can be made with the loop via a call to ``nmg_mf''. The loop may then be expanded to an edge-loop with calls to ``nmg_meonvu'' and new vertex points inserted with ``nmg_esplit''. % was 4.5 by 2 \captionfig 3.5in by 1.75in, cmface1, Figure 11 -- Conceptual View of Arguments to nmg_cmface. \sectionheadthree{Creating a Closed Object} Ordinarily, the applications programmer will be interested in creating simple closed objects. The final topology of the object is already well understood at the time of creation. That is to say, the number of vertices is known, as well as their relationships to various edges and faces. In order to simplify the creation of such objects, the library provides the routine {\it nmg_cmface} or {\it "Create Manifold Face."} In addition to providing a simple interface for creating complex faces, the routine also takes care of meshing the edgeuses of the new face with the radial edge structure of pre-existing edges. This is important for the creation of topologically closed objects. To build a face using {\it nmg_cmface}, the application programmer must provide a pointer to the parent shell for the face, an array of pointers to pointers to struct vertex, and the length of the array. The reason for the complexity of the array is actually to simplify the job of the applications programmer when making faces for which vertices do not yet exist. The application keeps an array of pointers to struct vertex (the array {\it verts} in the example below). This array contains pointers to the vertex structures used in the object being built. A null pointer in this list indicates a vertex structure which does not exist prior to the creation of the face or object. When these pointers are encountered by the nmg_cmface routine, a new vertex will automatically be allocated and a pointer to the new vertex inserted in the list. The mechanism for this will become clear later. Another array ({\it vertp} in the example below) is used as the argument to {\it nmg_cmface}. This second array will contain pointers to elements in the first array. For example, take as given an array of pointers to struct vertex called {\it verts[~]}, and an array of pointers to pointers to struct vertex called {\it vertp[~]}. Now suppose a triangular face is desired, and verts[0], verts[2], and verts[3] are pointers to the vertices at the corners of the face. The result can be conceptually viewed as in Figure 11. The elements of {\it vertp} should be ordered so that when the new face is viewed from the outside or normal-ward direction, the vertices will be listed in clockwise order. The face can then be created in the shell indicated by the pointer {\it shell_p} with the following call to nmg_cmface: \vbox{ \beginverbatim struct vertex *verts[4], **vertp[3]; vertp[0] = verts[0]; vertp[1] = verts[2]; vertp[2] = verts[3]; nmg_cmface(shell_p, vertp, 3); \endverbatim } Thus to create an NMG object (as is done in the tesselation process), the application first builds the list of vertex structures needed. This consists of pointers to pre-existing vertex structures, and null pointers for new vertex structures. Then each face is constructed in turn. \sectionheadtwo{Destruction Routines} When the model or some part of the model is no longer needed, the structures involved must be deleted. Each of the functions described below ``kills'' or deletes a structure type, and all its children. Normally, the only destruction routine called directly by the application is ``nmg_km'', which is called when the model is no longer needed. \beginitemlist \listitem void nmg_km(struct model *m) {\it ``Kill Model''} deletes an entire NMG model. \listitem void nmg_kr(struct nmgregion *r) {\it ``Kill Region''} deletes an nmgregion and all of its children. \listitem void nmg_ks(struct shell *s) {\it ``Kill Shell''} removes a shell and all of its children. \listitem void nmg_kfu(struct faceuse *fu1) {\it ``Kill Faceuse''} deletes a faceuse, its mate and the face which they share, as well as all components which made up the faceuses and face. \listitem void nmg_klu(struct loopuse *lu1) {\it ``Kill Loopuse''} removes a loopuse, it's mate, and all children. \listitem void nmg_keu(struct edgeuse *eu) {\it ``Kill Edgeuse''} removes an edgeuse, and its mate from a radial edge, and deletes them. If these were the last radial uses of the edge, then the edge structure and children are deleted as well. \listitem void nmg_kvu(struct vertexuse *vu) {\it ``Kill Vertexuse''} removes a vertexuse from the list of uses of the vertex and deletes the vertexuse structure. If this was the last use of that vertex, the vertex structure and children are deleted as well. \enditemlist \sectionheadtwo{Manipulation Routines} These routines mold and manipulate the NMG structures. \beginitemlist \listitem void nmg_face_g(struct faceuse *fu, plane_t p) {\it ``Face Geometry construction''} assigns a plane equation to the face of the given faceuse. \listitem void nmg_face_bb(struct face *f) {\it ``Construct Bounding Box for Face''} by looking at (and computing) the bounding boxes for all the constituent loops. \listitem void nmg_vertex_gv(struct vertex *v, pointp_t pt) {\it ``Assign vertex Geometry''} to a vertex. \listitem void nmg_loop_g(struct loop *l) {\it ``Compute Geometry} (bounding box) {\it for loop''}. \listitem void nmg_shell_a(struct shell *s) {\it ``Compute Shell Attributes''} (bounding box) for a shell. \listitem void nmg_region_a(struct nmgregion *r) {\it ``Compute Region Attributes''} computes the bounding box for the nmgregion from all constituent shells. \listitem void nmg_movevu(struct vertexuse *vu, struct vertex *v) {\it ``Move Vertexuse''} causes a vertexuse to be moved to a new vertex. \listitem void nmg_unglueedge(struct edgeuse *eu) {\it ``Un-Glue Edge''} removes an edgeuse and its mate from a shared radial edge, and creates a new edge for them to share. \listitem void nmg_moveeu(struct edgeuse *eudst, struct edgeuse *eusrc) {\it ``Move Edgeuse''} causes an edgeuse ``eusrc'' and its mate to become uses of a new edge. In the new edge, ``eusrc'' will be immediately radial to ``eudst'' in the radial edge list of that edge. If ``eusrc'' and its mate were the last uses of the old edge, then the old edge structure and it's children are deleted. \listitem void nmg_moveltof(struct faceuse *fu, struct shell *s) {\it ``Move first wire Loop in shell to an existing Face''}. Not normally called by applications programmer. The first wire loop (loopuse pair) of the specified shell is moved to the given faceuse (and faceuse mate). \listitem void nmg_jv(struct vertex *v1, struct vertex *v2) {\it ``JoinVertexes''} causes all uses of vertex ``v2'' to become uses of ``v1''. Vertex ``v2'' is deleted. \listitem void nmg_isect_faces(struct faceuse *fu1, struct faceuse *fu2) {\it ``Intersect Faces''} causes two faces to be intersected and the line of intersection to be identified and inserted. \listitem void nmg_mesh_faces(struct faceuse *fu1, struct faceuse *fu2) {\it ``Mesh Faces''} performs the topological and geometrical meshing of two faces which share one or more edges of intersection. When complete, opportunities for edge sharing between the two faces will be taken advantage of, and radial edge orientations of the two faces will be appropriate for all shared edges. \listitem struct model *nmg_find_model(long *magic_p) {\it ``Find Model''} returns the parent model for a given structure. The structure is identified by a pointer to its ``magic number''. \listitem struct vertexuse *nmg_find_vu_in_face(point_t pt, struct faceuse *fu, \break fastf_t tol) searches for a vertex with geometry coordinates within tolerance in a particular face. \listitem struct nmgregion *nmg_do_bool(struct nmgregion *s1, struct nmgregion *s2, int oper, fastf_t tol) performs a specified boolean operation using the indicated regions as inputs. Produces a region as output. \listitem int nmg_ck_closed_surf(struct shell *s) {\it ``Check for Closed Surface''} tries to determine if the parameter shell represents a closed object. \listitem int nmg_manifold_face(struct faceuse *fu) returns a non-zero value if the parameter face represents a part of a closed surface. \listitem int nmg_demote_eu(struct edgeuse *eu) turns an edgeuse into a pair of loopuses. Each loopuse consists of a single vertexuse. The edgeuse and its mate are deleted, and if they were the last use of their edge, the edge and its children are delete. \listitem int nmg_demote_lu(struct loopuse *lu) turns a loop into a collection of wire edges. The loopuses of this loop are deleted, as is the loop and its children. \listitem void nmg_simplify_loop(struct loopuse *lu) \\ void nmg_simplify_face(struct faceuse *fu) \\ void nmg_simplify_shell(struct shell *s) all serve to simplify the topology of the faces in a shell. Unnecessary edges within a face are deleted, and the adjacent loops are joined together. This service is primarily required to simplify the topology generated as a result of boolean operations. \listitem void nmg_jl(struct loopuse *lu, struct edgeuse *eu) {\it ``Join Loops''} combines loops which share a common edge. Useful primarily as a support routine for the ``Simplify'' routines. \listitem char *nmg_identify_magic(long magic) returns a string that describes the name of the structure type associated with the given magic number. This is most useful in program diagnostics associated with error detection and recovery. \enditemlist % $Header: /vld/mike/talks/90nmg/RCS/joined.html,v 1.1 1998/05/01 06:53:13 mike Exp $ \sectionhead{The Tessellators} The job of a tessellator is to convert a given solid primitive into a faceted approximation stored in NMG data structures. There are two aspects to this conversion: establishing the topology of the approximation, and then generating the geometry to associate with the approximate topology. Conversion of a faceted primitive solid will be exact, with each face, edge, and vertex of the NMG representation one-to-one with a topological element in the original representation. In general, effecting the conversion of a faceted primitive to the NMG representation is direct. Difficulties usually arise only when the original representation did not contain enough topology information to permit direct generation of the NMG topology. For example, the {\bf PolySolid} ``bag of polygons'' solid contains a collection of faces which together are known to enclose one or more volumes, yet there is absolutely no explicit topology. For this solid, the tessellator routines must rediscover the topology of the original object. This is done by a geometric comparison of each vertex against all the vertices previously encountered in this solid. If the vertex has been previously seen, then a new {\em use} of the existing vertex is made. If the vertex is unique, then a null pointer is added to the parameter list for {\bf nmg_cmface()} so a new topology vertex can be created. When all the vertices of a face have been processed in this manner, the list of vertices are passed to the routine {\bf nmg_cmface()}, which connects all the vertices together with edges. If an edge existed between two vertices in the new face, then a new use of the existing edge is created, otherwise an entirely new edge is created. Finally, these edges are formed into a loop, and the loop is embedded in a new face. \sectionheadtwo{Error Tolerances} Conversion of curved, implicitly defined primitive solids to a faceted representation will necessarily be inexact. To provide control over the nature and magnitude of the errors that may be introduced by the faceted approximation used in the tessellation, three types of tolerances are passed to the tessellator. The {\em absolute} tolerance, which limits the maximum permissible difference between any point on the tessellation and the corresponding point on the original solid, is expressed as an absolute distance. In the subroutine interface, this absolute distance is passed as a double precision floating point value, given in millimeters. In the {\bf mged} user interface, this absolute distance is specified in terms of the current working units (millimeters, inches, etc). The absolute tolerance permits users to make absolute statements about the maximum distance error contained in any tessellation. For example, using this mechanism it is possible to ensure that no face deviates from the true surface by more than 2 mm. The {\em relative} tolerance also limits the maximum error of any point, but is expressed as a fraction between 0.0 and 1.0 of the diameter of the bounding sphere which encloses the original solid. This relative tolerance permits users to make statements about the relative error contained in any tessellation. For example, this could ensure that no face deviates from the true surface by more than five percent of the size of the solid. The {\em normal} tolerance limits the maximum angular error of the surface normal. This normal tolerance permits users to make statements about the accuracy of the surface normals. For example, this could ensure that the surface normal of all faces do not deviate from the exact surface normals of the corresponding points on the original solid by more than 5 degrees. The tolerances can be set singly or in any combination. If no tolerances are set, each tessellator module establishes a default minimum tessellation; for example, most tessellators will not approximate a circle with fewer than 6 line segments. If more than one tolerance is specified, then on a solid by solid basis, the most restrictive tolerance is applied. If both an absolute and a relative tolerance are given, then large solids would most likely be tessellated to satisfy the absolute tolerance, while small solids would most likely be tessellated to satisfy the relative tolerance. For example, if an abs=10mm and rel=1\%, a large sphere of diameter 1000mm would be subjected to the absolute tolerance, while a small sphere of diameter 10mm would be subjected to the relative tolerance. \sectionheadtwo{Tessellating the Torus} \captionfig 3in by 3in, torus, Figure 12 -- Calculating Arc/Chord Error. The topology of the torus is a rectangular mesh where the ``edges'' of the mesh are connected together, side to side, and top to bottom. This can be visualized as follows: if the torus is cut once and straightened, it becomes a right circular cylinder. If the cylinder is cut longitudinaly and uncurled, it becomes a rectangle. The ``length'' of this rectangle is the distance around the rim of the torus and is traversed as the angle $\alpha$ varies from $0$ to $2\pi$. The ``width'' is the distance around one cross-section of the torus and is traversed as the angle $\beta$ varies from $0$ to $2\pi$. The torus can also be constructed by constructing a circle in $\alpha$ with radius $r_2$, and then sweeping that circle out around $\beta$ with radius $r_1$. The torus tessellator must determine the minimum number of facets that can be used to represent the torus while still satisfying the given error tolerances. Fortunately, the two parts of the torus are separable, and both parts are circles, so this problem reduces to determining the fewest number of line segments that can be used to approximate a circle while still meeting the error tolerances. Consider a triangle inscribed inside a circle of radius $r$. One vertex of the triangle is at the center of the circle $O$; the other two touch the circle at points $A$ and $B$, as shown in Figure 12. The line segment $AB$ subtends an angle $$ \angle AOB = \theta $$ The point of maximum error is $C$, the midpoint of $AB$: $$ C = {{A + B} \over 2} $$ $$ \angle AOC = {\theta \over 2} = \gamma $$ Extending the line $OC$ until it hits the circle results in the point $D$. Satisfying the surface normal tolerance is the easiest. If the circle is divided into line segments, the surface normal is exact at the line segment midpoint $C$, and has the largest error at the endpoints of the line segment: $A$ and $B$. The surface normal error at the endpoints is $\theta \over 2$. The relationship between the number of line segments $n$ and the angle $\theta$ that each line segment subtends is $$ n = {2\pi \over \theta} $$ Thus, to satisfy a surface normal error tolerance of $ntol$, the error at the endpoints $$ {\theta \over 2} \leq ntol $$ Therefore the minimum number of line segments that can be used is $$ nseg = { {2\pi} \over {2 ntol} } = { \pi \over ntol } $$ The face distance error inherent in the linear approximation of the circle is $$ e = | D - C | = r (1 - cos { \theta \over 2 } ) $$ Thus, to meet the face distance error tolerance, a choice of $\theta$ must be made so that $e$ satisfies the relation $$ e \leq dtol $$ The maximum value of $\theta$ which can be used is $$ \theta = 2 cos^{-1} ( 1 - { dtol \over r} ) $$ and the minimum number of line segments that must be used is: $$ nseg = {{2 \pi} \over \theta} = { {\pi} \over { cos^{-1} ( 1 - { dtol \over r} ) } } $$ To efficiently satisfy the maximum surface error tolerance, it is necessary to find the minimum number of line segments that must be used in each of the ``length'' and ``width'' directions. The appropriate radius is substituted into the formula for $nseg$ to determine $nlen$ (the number of segments needed in the length direction), and to determine $nw$ (the number of segments needed in the width direction). The largest of either of $nlen$ or $nw$ or the number of segments required to satisfy the surface normal tolerance is used. All the vertices on the surface of the torus can be generated by varying $len$ from 0 to $nlen$ while also varying $w$ from 0 to $nw$, and computing: $$ \alpha = w { { 2 \pi } \over nw } $$ $$ \beta = len { { 2 \pi } \over nlen } $$ $$ R = A cos(\beta) + B sin(\beta) $$ $$ P = V + R + r_2 {R \over |R|} cos(\alpha) + H sin(\alpha) $$ where \bigskip \centerline{\vbox{ \halign{\hfil#\ & #\hfil\cr V & vertex point at the center of the torus \cr A, B & perp. vectors, lie in the plane of the torus, define ``length'' \cr G, H & perp. vectors, define ``width'' direction \cr H & normal to plane of the torus \cr P & surface point \cr $r_2$ & radius of torus around the rim \cr }}} \setbox0=\vbox{ {\tt \beginverbatim E /\ / \ G/____\H /\ /\ / \ / \ /____\/____\ D I F \endverbatim } \centerline{Figure 13 -- Initial Octahedron Face} } \addfigure0 \sectionheadtwo{Tessellating the Ellipsoid} An ellipsoid is defined by a vertex point $V$ at the center and three mutually perpendicular vectors $A$, $B$, and $C$ which define the eccentricities. Through an affine transformation, the ellipsoid can be mapped to a unit sphere located at the origin. The algorithm begins by approximating the sphere by an octahedron, with the six vertices at $V \pm A$, $V \pm B$, and $V \pm C$. Each face of the octahedron is a triangle $\triangle DEF$, as in Figure 13. Points DEF line on the surface of the unit sphere. Pick the points GHI as the midpoints of the three edges of ABC. If each of these points GHI are viewed as vectors from the origin in the direction of the surface of the unit sphere, then re-normalizing the vectors to have unit length will cause the points to lie on the surface of the unit sphere. Consider each of the four new triangles $\triangle DGI$, $\triangle GHI$, $\triangle IHF$, and $\triangle GEH$ recursively until the tolerance is satisfied. \setbox0=\vbox{ {\tt \beginverbatim E /\ / \ J/____\K /\ /\ / \ / \ G/____\/____\H /\ L /\ / \ / \ / \ / \ / \ / \ / \ / \ /__________\/__________\ D I F \endverbatim } \centerline{Figure 14 -- Partially Subdivided Octahedron Face} } \addfigure0 It is tempting to consider an adaptive subdivision algorithm, so that when the magnitudes of A, B, and C are not equal, the areas of higher curvature could be tessellated more finely. Unfortunately, it is not possible to use different levels of subdivision without introducing ``cracks'' into the tessellation. Consider the case where triangle $\triangle GEH$ needs further subdivision, but triangles $\triangle DGI$, $\triangle GHI$, and $\triangle IHF$ do not, as in Figure 14. The problem here arises because the edge $GH$ in $\triangle GHI$ will no longer match up with edge $GL$ in $\triangle GJL$ and edge $LH$ in $\triangle LKH$, because point $L$ will have been normalized out to meet the unit sphere. While cracks could be prevented with by splitting $\triangle GHI$ into $\triangle GLI$ and $\triangle LHI$, this would produce an irregularity in the topology of the tessellation that would make a non-recursive formulation significantly more difficult. Let $$ r = max( |A|, |B|, |C| ) $$ Then, the distance tolerance $dtol$ can be expressed as a maximum angular (normal) tolerance as before: $$ \theta = 2 cos^{-1} ( 1 - { dtol \over r} ) $$ The final tolerance to use is the more strict of the surface normal tolerance $ntol$ and the distance tolerance: $$ tol = min( ntol, \theta ) $$ Thus, the number of triangles to be used around any one circumference of the ellipsoid will be $$ nseg = { \pi \over ntol } $$ However, because the initial approximation to the ellipsoid is an octahedron, the number of segments must be a multiple of four. The coordinates of all the vertices of the tessellation of a unit sphere with $nseg$ triangles are computed. Each of these coordinates is then transformed back into the coordinate system of the ellipsoid. \sectionhead{Evaluating Booleans} To evaluate a boolean combination of two tessellated solids, three distinct sub-operations must be performed. First, all elements of the two shells must be intersected. Second, every element in the two shells must be classified as {\bf in}, {\bf on}, or {\bf out}. Finally, all undesired elements are eliminated. \eject \sectionheadtwo{Intersection Operations} The first step in the boolean operation process is the intersection and cutting of the two shells with respect to each other. This process is summarized in Figure 15. \setbox0=\vbox{ {\tt\beginverbatim if bounding boxes of shell A and shell B overlap for each face in shell A, if bounding box of face A overlaps bound box of shell B for each face in shell B if bounding boxes of face A and face B overlap intersect edges of face A with plane of face B intersect edges of face B with plane of face A insert new topology & perform meshing for each wire edge in shell A, if wire edge A overlaps bounding box of shell B for each face in shell B if edge A intersects face B if necessary split edge at plane, insert vertex at plane intersection into face for each wire edge in shell B if wire edges intersect create any needed verticies in both wire edges \endverbatim} \centerline{Figure 15 -- Shell Intersection Procedure.} } \addfigure0 % Add figure from box0 to floating figure list. The process of comparing the face bounding boxes involves a check to see if the bounding boxes overlap along the line of intersection, not just whether they overlap at all. This is important for reducing the number of face intersections performed. When the bounding boxes of two faces overlap, they must be intersected with each other. The plane equations of the two faces are compared for equality. If the two faces are coplanar, they must have their loops intersected using a two dimensional polygon clipping approach. If the two faces are not coplanar, they must be intersected so that the faces will share an edge at the intersection. A list of all vertexuses or points which are on the line of intersection between the two planes is first generated. To do this, each edge of face A is intersected with the plane of face B and each edge of face B is intersected with the plane of face A. This intersection process takes the following form: If an endpoint of the edge is either topologically or geometrically in the plane of the other face, that vertex is registered in the list of points on the line of intersection. If the span of the edge crosses the plane of the other face, then the edge is divided into two edges. The new vertex which divides the edge lies on the line of intersection and is added to the list of points along the line of intersection. \captionfig 3in by 3in, seginsert1, Figure 16 -- Segment Insertion: Both Points in Face. After each face has been intersected with the plane of the other face, the resulting list of points of intersection is sorted geometrically along the line of intersection. The list is then used to determine which segments of the line of intersection are shared between both faces. Such segments must be added to each face. For each face, a segment to be added will fall into one of three categories: (1) both endpoints are in the face, (2) one endpoint is in the face, or (3) no endpoints are in the face. In the first case, a check is made to make certain that the edge does not already exist. If it does not, then each of the two endpoints are examined. If they are part of the same loop of the face, then that loop is divided into two separate loops, which share a common (new) edge. If the vertices belong to different loops, then an edge which connects the two loops is created, and the two loops are joined into a single loop. Examples of each of these cases can be seen in Figure 16. %Was 4.75 by 2.25 \captionfig 3in by 1.5in, seginsert2, Figure 17 -- Segment Insertion: One Point in Face. % Was 4.75 by 2.0 \captionfig 3in by 1.2in, seginsert3, Figure 18 -- Segment Insertion: No Points in Face. When only one of the endpoints exists in the face, the loop which contains the existing vertex is extended to include the new point. This can be seen in Figure 17. Finally, when neither of the segment endpoints exists in the face, a new interior loop must be created in the face as in Figure 18. When all of the appropriate topology has been inserted into the faces, the topology of the two faces is connected so that edges and vertices which can be shared between the faces are indeed shared. This process consists mainly of combining vertexuses onto a common vertex, and arranging the radial-edge orientation of edgeuses about a shared edge. Wire edges of the shell must also be intersected with the other shell. Wire edges exist either as part of a wire loop, or as an individual wire edge. Both types are processed in the same manner. Each edge is compared to the bounding box of the other shell. Where there is overlap, the edge is intersected with each face and wire of the other shell. If the edge intersects any of these, the edge is split if necessary, and the point of intersection is topologically linked to the other face or wire. \sectionheadtwo{Object Classification} When all of the intersections have been performed, every object in each shell must be classified with respect to the other shell. Each face, loop, edge, and vertex must be classified as being inside, on the surface of (referred to here as ``on''), or outside of the other shell. Here the topology becomes helpful. This process is easier if each shell is classified in turn against the other shell. For notational clarity, we refer to the classification of an object in shell A with respect to shell B. The classification of all structures is stored in a single table. The ``index'' fields in the NMG structures serve as offsets into the table. Once the classification is complete, an individual structure's classification can be quickly gotten by using the ``index'' field from the structure as the offset into the table of classifications. \sectionheadthree{Vertex Classification} If by, referring to the topology, it can be determined that the vertex has previously been classified against shell B, then obviously any vertexuse of that vertex which is in shell A shares the same classification. If it has not previously been classified, it is classified now. By looking at the other vertexuses of a vertex, it is possible to determine if there is a use of the vertex in the topology of shell B. If such a use exists, then the vertex, and the current vertexuse are classed as being ``on'' shell B. If the topology does not indicate that the vertex is ``on'' shell B, the geometry must be used to determine if the vertex is ``inside'' or ``outside'' of shell B. First of all it should be obvious that all vertices which lie outside of the bounding box of shell B are easily classified as being outside of shell B. Should this fail to classify the vertex, a raytracing approach is employed. A single ray is ``fired'' from the vertex along an arbitrary line and is intersected with all of the faces in shell B. Typically, this line will be along one of the major axis directions, although it may be useful to send the ray in some other, non-aligned direction to reduce the probability of hitting the edge of a face or hitting the plane of a face edge-on. The number of {\em Manifold} faces which the ray encounters before leaving the bounding box of shell B is counted. If the number of crossings is odd, then the vertex is classified as ``inside'' of shell B. While this appears simple at first glance, there are several problems involved in the raytracing approach which are worth noting: (1) identifying a face as either manifold or non-manifold, (2) recognizing an actual hit on a face, and (3) coping with a ray hit on an edge or a vertex. \sectionheadfour{Manifold Faces} If a face has any dangling edges, it can be quickly classed as being non-manifold. This is a relatively quick check. If for each edge of the face, there exists an odd number of other face-loops of manifold faces of the same shell adjacent to the same edge, then the face is manifold. This is a tedious check which requires an exhaustive analysis of most, if not all of the faces of the shell to determine if one face is manifold. While this is important for some cases, most of the time it is not necessary to perform a full manifold check of the radial faces. A check for dangling edges of radial faces is sufficient. \captionfig 3in by 3in, rayisects, Figure 19 -- Raytracing Hit-Points. \sectionheadfour{Intersecting a Ray and Face} Since faces consist of both interior loops (holes in the face) and exterior loops, it is important to be sure that a ray which hits the plane of a face actually hits inside the surface area of the face as well. The in/out status for the hit-point is determined by the loop which has the sub-element (edge or vertex) closest to the hit-point. If the hit-point is closest to an exterior loop of the face, then (a) the ray hits the face if the point is inside the loop, as in hit-point 1 in Figure 19A, and (b) the ray misses the face if the point is outside the loop. Likewise, if the hit-point is closest to an interior loop, then (c) the ray misses the face if the hit-point is inside the loop, as in hit-point 3 in Figure 19A, and (d) the ray hits the face if the hit-point is outside the loop, as in hit-point 2 in Figure 19A. \sectionheadfour{Intersecting a Ray and Edge Or Vertex} When the hit-point of the ray lies on an edge or vertex of a face, further logic must be used to determine whether or not a hit actually occurs. If the ray hits an edge of a loop in a face, and there is another loop of the face of the same type (interior/exterior) adjacent on the edge, the hit is registered as if the ray had intersected the interior of the loop. For example, hit-point 4 in Figure 19A is not a hit on the face because the edge is shared between two interior loops of the same face. On the other hand hit-point 5 in Figure 19A is a hit on the face because the edge being hit is shared between two exterior loops of the face. If the edge is actually a boundary of the face, then the ray must be compared to the surface normals of the faces involved. For example, the ray V1 in Figure 19B scores a single hit as it encounters the edge between the two faces. Ray V2 does not score a hit. It is important to note that only one hit may occur for the pair of faces, since it was the edge between them which was encountered. The situation becomes slightly more complex when there are more than two faces of the shell sharing the edge. In this case, the hit/miss status for each pair of faces is determined at the time the edge is first encountered, and all faces are marked as having been processed. \sectionheadthree{Edge Classification} Once all the vertex structures in shell A have been classified against shell B, it is possible to classify the edges. First cut classification of edges is done by referring to the classification of the endpoints. If one or more of the endpoints is not ``on'' shell B, the edge takes it's classification from that vertex. If both endpoints are classified as ``on'' shell B, the mid-point of the line segment is computed, and classified using the raytracing technique described in the previous section. An edge with endpoints inside and outside shell B indicates an error in the intersection process. Table 1 summarizes the classification of edges. \vbox{ \vskip 10pt \centerline { \vbox{ \offinterlineskip \hrule \halign{\vrule\strut\ \hfil#\hfil\ \vrule& \ \hfil#\hfil\ \vrule\cr Endpoint& Edge\cr classifications&classification \cr \noalign{\hrule} both out& out \cr \noalign{\hrule} out/on& out \cr \noalign{\hrule} both on& use mid-point ray \cr \noalign{\hrule} in/on& in \cr \noalign{\hrule} both in& in \cr \noalign{\hrule} in/out& intersection error \cr } \hrule } % vbox end } % centerline end \vskip 22pt \centerline {Table 1 -- Edge Classification by Endpoint Classification} } \sectionheadthree{Loop Classification} A loop of a single vertex inherits the vertex's classification. A loop of edges which contains an edge which is not ``on'' shell B inherits that classification. For example, if a loop contains an edge classified ``inside'' shell B, then the loop is classified ``inside'' shell B. A loop with edges both inside and outside shell B indicates an error in the intersection process. If all edges of a wire loop are classified as ``on'' shell B, the loop is classified as ``on'' shell B. There are other conditions required for a face loop to be classified as being ``on'' shell B. First, there must exist a loop in the topology of shell B which has exactly the same set of edges. Secondly, the loop must be classified as being either ``shared'' or ``anti-shared''. A ``shared'' face loop not only has a counterpart in the other shell, but the normals of the faces of which the loops are a part of are pointing in the same direction. A loop is ``anti-shared'' when the surface normals of the parent faces point in opposite directions. \sectionheadthree{Face Classification} Faces are not classified except to the extent to which the loops which make up the face are classified. % $Header: /vld/mike/talks/90nmg/RCS/joined.html,v 1.1 1998/05/01 06:53:13 mike Exp $ \captionfig 3.75in by 1.75in, op-intro, Figure 20 -- Classification of Example Objects. \sectionheadtwo{Boolean Evaluation} After all the topological elements in objects A and B have been classified, the boolean evaluation simply becomes a task of deciding which elements to retain, and which to destroy. Every element has been classified with respect to both objects A and B, and was assigned one of eight combined classifications. The object from which the element originally came from is always given an {\bf on} classification. Elements from A are classified as one of {\bf onAinB, onAonBshared, onAonBanti-shared, onAoutB,} while elements from B are classified as one of {\bf inAonB, onAonBshared, onAonBanti-shared,} or {\bf outAonB}. All of these possibilities occur in the two example object pairs (four blocks viewed end-on) in Figure 20; the important face-loop classifications are appropriately labeled. For the two blocks on the left of Figure 20, the bottom center face-loop exists in both objects A and B, and the orientation (outward surface normal) of the face-loop in both objects is the same (pointing towards the bottom of the page), so the face-loop is classified {\bf onAonBshared}. For the two blocks on the right of Figure 20, the middle face-loop also exists in both objects A and B, but the orientation of the two face-loops are opposite, so this face-loop is classified {\bf onAonBanti-shared}. \vbox{ \vskip 10pt \centerline { \vbox{ \offinterlineskip \hrule \halign{& \vrule#& \strut\ #\ \hfil\vrule& \ #\ \hfil& \vrule#\ \vrule& \ #\ \hfil\vrule& \ #\ \hfil\vrule& \ #\ \hfil& \vrule#\cr &A& B&& A -- B& A $\cup$ B& A $\cap$ B& \cr \noalign{\hrule} &on& in&& kill& kill& retain& \cr &on& on shared&& kill& retain& retain& \cr &on& on anti-shared&& retain& kill& retain& \cr &on& out&& retain& retain& kill& \cr \noalign{\hrule} &in& on&& retain+flip& kill& retain& \cr &on shared& on&& kill& kill& kill& \cr &on anti-shared& on&& kill& kill& kill& \cr &out& on&& kill& retain& kill& \cr } \hrule \vskip 3pt } %vbox end } %centerline end \centerline{Table 2 -- Boolean Evaluation Decision Table} \vskip 10pt } % was 3.75 by 1.5 \captionfig 3.5in by 1.5in, op-sub, Figure 21 -- Subtraction Performed on Example Objects. Because there are only eight possible classifications, the appropriate action for the boolean evaluation algorithm can be easily tabulated. These actions are found in Table 2. Indeed, this exact same table exists in the source code for the boolean evaluator in file {\bf nmg_eval.c}. Placing these actions into a table permits a complete separation of {\em policy} and {\em mechanism} in the implementation. The policy is encoded in the entries of the table, and the mechanism is embodied in the code of the subroutine. This has two main benefits. First, code to perform any one action exists in only one place, ensuring consistent treatment of all cases. Second, this offers the potential for adding more boolean operations at a later date, simply by supplementing the table with another column. Consider first the case of the subtraction operation, A minus B. The intent is to retain every part of A that is {\bf in} only A, to kill every part of A that is also {\bf in} B, and to kill every part of B. The policy just stated is implemented by the tabulated rules for processing all the topological elements. The entry for an element which has classification {\bf on} A and {\bf out} B has a table entry of ``retain'' (denoted more suscinctly as {\bf onAoutB}=retain). This rule preserves the main body of A. {\bf onAinB}=kill and {\bf onAonBshared}=kill because these elements are {\bf in} B, and therefore represent a portion to be subtracted out. {\bf outAonB}=kill to eliminate unused parts of B. {\bf onAonBanti-shared} elements are retained, because they are on the surface of A and on the surface of B, where the two surfaces touch. To implement subtraction, this case has to be defined as either (a) shaving an infinitesimally thin layer off of the surface of A, or (b) a no-op, where the A surface is retained unmodified, and the B surface is killed. Because choice (a) would modify the volume of the resulting solid, it can not be used; instead, choice (b) has been selected. This policy is implemented in these three table entries: {\bf onAonBanti-shared}=retain, {\bf onBonAshared}=kill, and {\bf onBonAanti-shared}=kill. Finally, elements which have been classified as {\bf inAonB} are listed in the table as ``retain+flip''. The surface has to be retained because it will become part of the new boundary between A and the outside world. However, the existing surface normal points {\em into} solid A, reflecting the fact that this surface was originally part of the exterior of solid B, so the surface normal must be flipped. The results of performing a subtraction on the two sample objects is illustrated in Figure~21. While the discussion of the table entries has been made in terms of surfaces defined by face-loops, the same reasoning and actions apply to the inferior topological elements: wire-loops, loop-edges, wire-edges, edge-vertices, and lone-vertices. The overall strategy is to process all the topological elements of object A, and then to process all the elements of object B. The meat of the algorithm exists in internal subroutine {\bf nmg_eval_shell()}, which starts by processing the loops in each face. Any loopuse which has a classification that maps to an action of ``kill'' is demoted into a collection of wire edges using {\bf nmg_demote_lu()}. The loop is demoted rather than killed so that edges and vertices that are shared in common with both objects can be properly considered later in the subroutine. If none of the loops in the face are retained, then the faceuse is killed using {\bf nmg_kfu()}. If some loops in the face are retained, then the faceuse is retained; if the faceuse came from object B then it is moved to object A, the faceuse's mate is also moved to object A, and the face normal is flipped. The algorithm then proceeds down from faces to processing wire-loops. If the loopuse has a classification that maps to an action of ``kill'' then it is demoted into a collection of wire edges, otherwise it is retained, and moved into object A if necessary. Next, wire-edges are processed. If the edge is marked `kill'' it is demoted into vertices using {\bf nmg_demote_eu()}, otherwise it is retained, and moved into object A if necessary. Finally, lone-vertices are processed. Vertices marked ``kill'' are disposed of using {\bf nmg_kvu()}. Because vertices are 0-manifolds there is no lower topological element to demote them to. \captionfig 3.75in by 1.5in, op-union, Figure 22 -- Union Performed on Example Objects. Consider next the case of the union operation, A $\cup$ B. The intent here is to retain all elements that are on the exterior of either A or B, while eliminating any interior structure or redundant elements. More precisely, for solid modeling, the formula for union is interpreted as $$ A \cup B ~ := ~ (A - B) + (B - A) $$ where the $+$ operation is a simple combination, or sum, operation. The elements that are on the exterior of exactly one of either A or B are classified as {\bf onAoutB} and {\bf outAonB} and are retained. Elements that are on the exterior of both A and B appear twice, first as {\bf onAonBshared} which is retained, and again as {\bf onBonAshared}, which is killed (to avoid having the element become duplicated in the result). Interior structure is found in all elements classified as {\bf onAinB}, {\bf inAonB}, plus any anti-shared faces {\bf onAonBanti-shared} and {\bf onBonAanti-shared}. All elements with these classifications are killed. The result of performing the union operation on the two example objects is shown in Figure 22. \captionfig 2.5in by 0.75in, op-inter, Figure 23 -- Intersection Performed on Example Objects. Finally, consider the case of the intersection operation, A $\cap$ B, as shown in Figure 23. The intersection operation retains all elements that are simultaneously part of both A and B, while discarding the excess. Clearly, elements classified {\bf onAonBshared} and {\bf onAonBanti-shared} are elements common to the two objects and should be retained; elements classified {\bf onBonAshared} and {\bf onBonAanti-shared} need to be killed to prevent duplication. The elements exterior to one of the objects are classified {\bf onAoutB} and {\bf outAonB} and should also be killed. Previously interior structure {\bf onAinB} and {\bf inAonB} should also be retained, as these elements will form the new boundary when the non-common elements have been removed. The technique just described for evaluating a boolean formula is simple to program and debug, works reliably, and is easy to understand. Storing all the policy decisions in a table makes the algorithm very straightforward. % $Header: /vld/mike/talks/90nmg/RCS/joined.html,v 1.1 1998/05/01 06:53:13 mike Exp $ \sectionhead{User Interface} The majority of a BRL-CAD user's contact with the new non-manifold geometry capability will be through the Multi-Device Graphics Editor ({\bf mged}) [APPL88]. This is the program that is used to rapidly view existing geometry in wireframe form, to create new geometry and update existing shapes, to select viewpoints for ray-tracing runs, to select keyframes for animation sequences, and to preview animation sequences in wireframe form. At any time in an {\bf mged} session, the user may add one or more objects to the active model space, using the command \beginprose mged> {\em e object} \endprose If the viewing cube is suitably positioned, the newly added subtrees become visible on the display. 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. 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. The evaluation of the approximation is performed by tessellating each of the primitive solids into an NMG object meeting the current tolerance, and combining them according to the indicated boolean operations. Each edge and vertex in the resulting NMG object are placed in a {\bf struct vlist} chain (by subroutine {\bf nmg_r_to_vlist()}) and drawn on the {\bf mged} display. This operation is invoked with the command \beginprose mged> {\em E object} \endprose or \beginprose mged> {\em ev -w object} \endprose Evaluating the surface takes somewhat longer than creating wireframes of the unevaluated primitive solids, so it is not used by default for viewing large assemblies. However, it is quite reasonable to evaluate the surface whenever the design has reached a new plateau, or when a detailed examination of a complex part is required. When viewing objects of modest complexity at loose tolerances, the evaluation process is quite rapid. Note that the evaluated boundary wireframes are not stored in the database, and are primarily intended as a visualization aid for the designer. % Figure \ref{crod} 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. \sectionheadtwo{Polygons} On those hardware platforms where polygon drawing capabilities exist, it is possible to have a flat-shaded polygonal rendering of database objects drawn. This operation is invoked with the {\em evaluate} command \beginprose mged> {\em ev object} \endprose Once the polygonal rendering of the object is on the screen, it can be rotated in real time. This capability gives the designer the opportunity to more fully appreciate the complex shape which has been created, and to judge whether the evaluated shape matches the intended design. On hardware platforms which have hardware support for rendering lit and shaded polygons with multiple light sources (such as the Silicon Graphics 4D workstations), it is possible to activate the hardware lighting model. This provides a much more realistic rendition of the evaluated objects, and also gives clues about face normals. When further used in conjunction with hardware clipping planes, the evaluated solids can provide significant new insight for the designer. \sectionheadtwo{Surface Normals} As an aid to the user, an option to the {\em ev} command exists to add surface normal vectors to the evaluated surface polygon display. The outward pointing surface normals are drawn as single vectors from the centroid of each polygon. They resemble ``whiskers'' on the polygons. This option is invoked with the command \beginprose mged> {\em ev -n object} \endprose If the polygon rendering of the object shows all the faces, but no surface normal vectors can be seen, then this suggests that either an error exists in the database entry for this object, or an internal software error in {\bf librt} has been encountered. In either of these cases, the vectors should be pointing inside the solid object. This can be easily verified by using the hardware clipping planes to permit the inside of the solid to be seen. If the vectors are on the inside, then the surface normals have become reversed. \sectionheadtwo{Tolerances} As discussed the in section on tessellation, there are three types of tolerances that are user selectable. The absolute tolerance ensures that no point on the polygonal approximation will be further away from the true surface than the tolerance value. The relative tolerance ensures that no point on the polygonal approximation will have a distance from the true surface which is greater than the given fraction of the primitive object's size. The surface normal tolerance ensures that no face normal at any point on the polygonal approximation will differ from the true surface normal at the corresponding point on the true surface by more than the indicated angular error. If multiple tolerances are given, the tesselator is required to satisfy all of the tolerances. This enables the user of the approximation to make firm statements about the upper bound on the tessellation error produced. When {\bf mged} is first started, a relative tolerance of one percent is the default tolerance. At any time the tolerance settings can be examined, using the {\em tol} command. Thus, immediately after starting {\bf mged}, the {\em tol} command would show: \beginprose mged> {\em tol} Current tolerance settings are: abs None rel 0.01 (1\%) norm None \endprose The absolute tolerance specification is given in the current working units, and is converted internally into millimeters. For example, adding an absolute tolerance of three millimeters might be done like this: \beginprose mged> {\em tol abs 3} mged> {\em tol} Current tolerance settings are: abs 3 MILLIMETERS rel 0.01 (1\%) norm None mged> {\em units inches} mged> {\em tol} Current tolerance settings are: abs 0.11811 INCHES rel 0.01 (1\%) norm None \endprose The absolute tolerance can be disabled by setting the tolerance to zero (or a negative number). Providing a tessellation with zero error is impossible; in general, to create a tessellation of a curved object with zero error would require an infinite number of planar faces. Therefore, zero tolerance can be used as a flag to turn off the absolute tolerance requirement. The relative tolerance specification is given as a fraction between zero and one. \beginprose mged> {\em tol rel .001} mged> {\em tol} Current tolerance settings are: abs 3 MILLIMETERS rel 0.001 (0.1\%) norm None mged> {\em tol rel 0} mged> {\em tol} Current tolerance settings are: abs 3 MILLIMETERS rel None norm None \endprose The surface normal tolerance is given as a positive angle in degrees between zero and 90. Specifying a normal tolerance of zero is used to disable the normal tolerance requirement. The angular tolerance is echoed back both in fractional degrees, and as degrees minutes and seconds of arc, as can be seen in the second example below. \beginprose mged> {\em tol norm 2} mged> {\em tol} Current tolerance settings are: abs 3 MILLIMETERS rel 0.01 (1\%) norm 2 degrees (2 deg 0 min 0 sec) mged> {\em tol norm 0.5} mged> {\em tol} Current tolerance settings are: abs 3 MILLIMETERS rel 0.01 (1\%) norm 0.5 degrees (0 deg 30 min 0 sec) \endprose If a model included parts that had been created from the boolean combination of both very large and very small primitives, where the small primitives have a size within a few orders of magnitude of the desired absolute tolerance, it may be desirable to specify both an absolute and a relative tolerance. For the large objects, the absolute tolerance would ensure that the tessellation produced enough facets to represent the surface to the desired degree of accuracy, whereas the relative tolerance would probably have generated significantly fewer facets. For the small objects, the absolute tolerance would probably not generate very many facets, but the presence of a relative tolerance would ensure that the tessellation produced a reasonable rendition of the desired shape. The surface normal tolerance will also limit the error in the tessellation. However, the number of faces in the tessellation can grow rapidly as the tolerance is tightened. For example, consider tessellating a single torus. If no normal tolerance is given, the torus is approximated by 36 ($6 \times 6$) facets, and a normal tolerance of one degree yields 32400 facets. Other values are listed in Table 3. While specifying a tight tolerance on the surface normal will produce tessellations with a pleasingly smooth surface, the large number of facets that result can consume substantial amount of memory. If all tolerances are disabled (including the default one percent relative tolerance), then each tessellator will choose an object-specific minimum number of facets needed to produce a reconizable rendition of the primitive solid. \vbox{ \vskip 5pt \centerline { \vbox{ \offinterlineskip \hrule \halign{&\vrule#&\strut\hfil#\hfil& \hfil#&\vrule#\cr &Tolerance &Facets &\cr\noalign{\hrule} & none & 36 &\cr & 10 & 326 &\cr & 5 & 1296 &\cr & 2 & 8100 &\cr & 1 & 32400 &\cr & 0.5 & 129600 &\cr} \hrule \vskip 5pt } %vbox end } % centerline end \centerline{Table 3 -- Relationship Between Normal Tolerance and Facets for Torus} } \sectionheadtwo{Visualizing Boolean Evaluation} During the development of the boolean evaluation software, several graphical displays were created to assist in the debugging process. By default, this feature is not active, but setting a run-time debugging flag allows any user to enable it. The first display shows the process of intersecting two faces together. The outline of all the loops in the first face are drawn. Performing the intersection operation can result in the addition of new edges. Adding new edges may also result in the cutting or joining of loops in the face. After the intersection is complete, the outline of all the loops in the face are drawn again so that the changes are visible. The display is updated each time. The second display shows the process of evaluating the boolean formula on the fully intersected and cut objects. First all the faces are evaluated. Faces to be retained do not change, but faces that are not part of the result are demoted to wire loops. This is indicated by the color of the edges changing to yellow. Wire loops that are not retained are demoted to wire edges. Wire edges that are not retained are demoted to lone vertices and disappear from the display. Lone vertices that are not retained are killed, and vanish from the display. Even for the boolean combination of two relatively simple overlapping solids, quite a few face intersections can be computed. However, on typical workstations it is not uncommon to see ten intersections computed and the diagnostic wireframes drawn to the screen each second. This high speed animated review of the intersection and boolean evaluation operations is very valuable for teaching users how the boolean operations work. It can also be beneficial when a user wants to understand the exact process that created a final NMG shape. This capability also served as a very valuable debugging tool, often permitting an intuitive grasp of programming errors to be rapidly acquired -- pouring through formatted dumps of thousands of NMG data structures was so difficult that it was reserved as the technique of last resort. \eject \sectionheadtwo{Creating an NMG Database Object} So far, the primary motivation for computing an approximate surface representation for an object has been to drive some ``post processing'' application. For example, the {\em ev} command computes an approximate surface representation for the purpose of creating wireframes and shaded polygon renderings for the user to view inside the {\bf mged} editor. Approximate surface representations are also used to provide appropriate kinds of input files for existing analysis applications. But, the facetization and boolean combination mechanism that has been constructed is completely general, and can be used for other purposes also. There may be circumstances when a designer may wish to take a collection of primitive solids, tessellate and combine them into some faceted shape, and then store that faceted shape as the finished design. If the object of the design task is to create a faceted object, then this can be a powerful way of accomplishing that task. It can be accomplished with the {\em facetize} command: \beginprose mged> {\em facetize newsol oldsol} mged> {\em facetize newreg oldreg} \endprose The {\em facetize} command takes either a single pre-existing solid, or a single pre-existing combination of solids (such as a group or region), tessellates them according to the current tolerance settings, and creates a new solid in the database that is the facetized result, represented using the NMG data structures. This newly created solid has exactly the same standing as any other primitive solid: it can be ray-traced, instanced, or combined with other solids to create new shapes. However, it is important to note that no record is made of how this new solid was formed. Thus, when the parameters of one of the original solids inside the original region {\em oldreg} is modified, this does {\em not} result in any changes being propagated to the facetized version {\em newreg}. If this effect is desired, it is necessary to delete {\em newreg} and re-execute the {\em facetize} command, e.g.: \beginprose mged> {\em kill newreg} mged> {\em facetize newreg oldreg} \endprose The same procedure must be followed if a different tolerance for the facetization is desired. % $Header: /vld/mike/talks/90nmg/RCS/joined.html,v 1.1 1998/05/01 06:53:13 mike Exp $ \sectionhead{Applications} The capability to produce an explicit approximate representation of the surface of any object stored in the geometry database exists as a general capability. Any application program that links to the library {\bf librt} can make use of this capability, at any time in the analysis process. Furthermore, use of this capability can be simultaneously intermixed with other forms of interrogation supported by the library, so that an application might perform some operations using the approximate surface description, and other operations using ray-tracing. The application will have no knowledge of the underlying primitives used to describe the objects in the database, nor will the application be aware that the library creates the surface description by extracting the objects from the geometry database, tessellating them into NMG solids, and then combining them via boolean formulas. \sectionheadtwo{Image Rendering} Prior to the existence of this polygon rendering capability, all renderings of the geometry databases had to be performed using an optical simulation program based on ray-tracing. While ray-tracing can produce some very beautiful images, it can require a non-trivial amount of processing time to create the images. For the purpose of visualizing the shape of an object, an image with much lower quality than those produced by ray-tracing would be entirely acceptable, if they could be produced in significantly less time. The most immediate application of the explicit surface representation is for visualization purposes: making an optical image or {\em rendering} of objects in the geometric database. These images can be useful for a variety of applications. Within the geometry editor {\bf mged}, a high-speed rendering of a polygonal approximation of a shape is very useful for inspecting the model. This permits the user to verify that the design is as it should be. It is also a very powerful technique for conveying information about the design to others. If the display hardware is fast enough, this capability could provide an improved interface for many geometry editing operations. Presently, modifications to solids are performed using the wireframe display. The modifications are entered either numerically (by entering specific parameters), or interactively (by modifying key parameters through cursor manipulations on the screen). In both cases, it can occasionally be difficult to judge by eye whether the shape created is the desired one. Being able to edit the object in a (seemingly) solid, rendered form would greatly assist in this task. Along the spectrum of rendering quality, there is a point midway between the low quality of simple hardware polygon rendering, and the high quality of ray-traced images. This intermediate level of quality can be obtained using software-based polygon rendering algorithms. These algorithms tend to run faster than rendering algorithms based on ray-tracing. Especially when creating animation sequences that require the rendering of hundreds or thousands of images, having the ability to make this quality {\em vs.} speed tradeoff can be a real boon. This opportunity now exists. An approximate surface description, tessellated with appropriate tolerances, can be converted into polygonal form and passed to existing polygonal rendering software. \sectionheadtwo{Thermal Predictions} In the design of vehicles, it is very useful to be able to make predictions about the thermal behavior of the vehicle before the prototype is constructed. This is important for ensuring passenger comfort and proper cooling of temperature sensitive components. In military applications, the patterns of heat radiation are also quite important. If simulation of the thermal behavior of the vehicle reveals heat distribution that is not consistent with the design criteria, it is a simple matter to modify the vehicle geometry or substitute different construction materials in an attempt to improve the situation. Re-running the thermal simulation will assess the effect of these changes. To simulate the thermal behavior of the vehicle, it is necessary to calculate a complete heat budget for the entire vehicle, in addition to obtaining the geometry and material property information. The heat budget must account for all the internal sources of heat such as engines, bearings, and road wheels, and radiators of heat such as cooling fins, air vents, and surface area ``skin'' in contact with the open air. The simulation must also take into account external thermal loading due to such factors as solar radiation and contact with the surface of the earth. Accurate predictive thermal modeling is possible based on solid modeling, using three dimensional finite element mesh (FEM) techniques. The geometry is subdivided into small isomorphic solid volumes or {\em nodes}, and the thermal properties of the material of each node are recorded. Heat flow is calculated between all node pairs, where the links between mesh elements pairs are characterized by thermal coupling coefficients. %%[Reference?] However, a full three dimensional thermal model requires that a great deal of material property information be known to a reasonable degree of accuracy. In many cases it is possible to compute a reasonable approximation to the thermal behavior of a vehicle using a description of the surfaces of the the vehicle, and some ``lump parameters'' for the thermal mass of the various components, and for the primary heat sources. This approach, based on a geometry of flat plates, is taken by the Physically Reasonable Infra-red Signature Model (PRISM) developed at the Keweenaw Research Center [REYN89]. Having the capability for generating an approximate surface description of a BRL-CAD model will permit vehicle designs stored in a BRL-CAD geometry database to be converted to a form suitable for analysis by the PRISM application program. Once the thermal behavior of the vehicle is predicted, passenger comfort considerations can be directly assessed, and no further processing is required. For predicting a thermal signature, such as might be seen on an imaging infra-red sensor, it is necessary to take the simulated patterns of thermal energy radiation and convolve them with the transfer function of the atmosphere that lies between the vehicle and the sensor to determine the patterns of energy presented to the sensor. That pattern in turn must be convolved with the transfer function of the sensor itself, in order to predict the signal measured by the sensor. In the design of sensor systems, it is important to know the nature of vehicle signatures over a range of detection bands and for a variety of signal-processing schemes [RAPP76, RAPP83]. Linking BRL-CAD with PRISM provides a method for computing this information as part of the design loop. This linkage provides opportunities for vehicle designers to retain control over the thermal signatures of their vehicles, as well as giving sensor designers an environment for testing and refining improved sensors. \sectionheadtwo{Radar Predictions} When a metallic vehicle is illuminated with radar energy, that energy is partly absorbed, and partly dispersed back into the surroundings. Some of the illumination energy returns to the transmission position, and it does so carrying an electronic ``signature'' of the vehicle [TOOM82]. Depending on the applications envisioned, a vehicle designer is usually interested in either maximizing the strength of the radar signature (for example, to make boats and commercial aircraft easier to locate in foul weather), or minimizing the strength and recognizability of the radar signature, such as in the design of low-observable (``stealth'') aircraft. A variety of different techniques exist to calculate the predicted radar signature of a given vehicle. The algorithms based on ray-tracing tend to handle multi-bounce effects very well but are unable to simulate edge diffraction and creeping wave phenomena. However, algorithms based on feature-based descriptions of the the vehicle or coarse polygonalizations tend to handle diffraction and creeping waves acceptably, but are unable to handle multiple bounce effects. The best known technique for the simulation of radar signatures is the Method-of-Moments technique [HARR82, MOOR84], which requires a polygonalization of the surface of the vehicle as input. The nature of the calculation is much like that employed for predicting heat flow, as outlined earlier. However, in order to achieve high accuracy, the Method-of-Moment technique requires that each surface polygon be no wider than one fifth of one wavelength of the radar signal. The relationship between frequency $f$ and wavelength $\lambda$ is given by $$ \lambda = { c \over f } = { { 3 \times 10^8 ~~ m/s } \over { f ~~ Hz } } $$ Radar frequencies begin in the UHF range with P-band radars transmitting from 225 MHz to 390 MHz, at a wavelength of about one meter [IEEE76]. A millimeter wave (W-band) radar transmitting at 94 GHz emits a signal with a wavelength of 3{.}2 millimeters. A radar transmitting at a higher frequency would have a very short wavelength indeed. The relationship between frequency $f$, wavelength $\lambda$, and the maximum facet size is given in Table 4. Thus, the method of moments technique requires exceptionally fine surface tessellations to be used. Tessellating full size vehicles this finely produces a gargantuan number of facets. Computing a solution to problems of such size is barely within the reach of present-day supercomputers. \vbox{ \vskip 5pt \centerline { \vbox{ \offinterlineskip \hrule \halign{&\vrule#&\strut\hfil#\hfil& \hfil#& \hfil#& \hfil#&\vrule#\cr &Band & Frequency & Wavelength & Facet Size &\cr\noalign{\hrule} & P & 300 MHz & 1000 mm & 600mm &\cr & L & 1 GHz & 300 mm & 60mm & \cr & X & 10 GHz & 30 mm & 6mm &\cr & W & 94 GHz & 3.2 mm & \ 0.64mm &\cr} \hrule \vskip 5pt} %vbox end } % centerline end \centerline{Table 4 -- Relationship Between Frequency and Facet Size} } \sectionheadtwo{Interfacing to Other CAD Systems} There are many reasons why the geometric database for a given design might need to be transferred from the CAD system which originated it to a completely different kind of CAD system. This might be done because two different organizations use different software packages and they need to exchange design files. Similarly, as part of a comparison of the advantages of different CAD systems, or of different analysis codes, it would be necessary to import a reference design. Or, some aspects of a design might be best handled using software uniquely suited to a particular specialized task, such as numerically-controlled (NC) machinery toolpath generation, or ISO-compliant blueprint generation. Having NMG objects as ``first class citizens'' in the geometry database makes the task of importing faceted geometry from other CAD systems very straightforward. Existing faceted objects either with no explicit topology, or including explicit topology (most commonly using a winged edge representation), can be easily converted into an NMG object with full generality and no loss of topological information. There are a great many systems that employ faceted representations, so this is a significant capability. Being able to convert models described using boolean combinations of the rich set of primitive solids into explicit surface descriptions also enables transfer of geometry in the outward direction as well. Shapes that are originally modeled using the existing CSG database can be exported to other CAD systems for additional processing. % $Header: /vld/mike/talks/90nmg/RCS/joined.html,v 1.1 1998/05/01 06:53:13 mike Exp $ \sectionhead{Future Directions} \vskip -22pt % \sectionheadtwo{Editing an NMG object} At present, the only way to create an NMG object is via the procedural interface of {\bf librt}, either from the {\bf mged} {\em facetize} command, or from an outboard database converter or procedural database generator that uses {\bf libwdb}, the library for writing databases. Just as it is possible to edit all the other primitive solids, it seems reasonable to permit users to edit NMG solids. In principle, a basic NMG editing capability should not be much different than the existing ARB editing capability, which includes the ability to move vertices, move edges, and move faces. In addition to these familiar editing features, some kind of interface to the Euller operators will need to be created, so that new topological elements can be created, existing elements can be killed, and sets of existing elements can be joined together or split apart. \sectionheadthree{Editing Under Constraints} If the NMG editing capability is implemented in a very general way, it should be possible to replace most of the existing faceted object editing capabilities in {\bf mged} with interfaces to a subroutine that implements editing of NMG objects under a set of general constraints. For example, when editing an ARB, if an edge is split, all faces sharing that edge need to be split as well. When moving a vertex, it must satisfy the constraint of keeping planar all the faces that contain it. A simple primitive shape like an ARB4 could be modified and expanded into a much more complicated topological arrangement, without forcing the user to destroy the original solid, and re-create the shape using a more general primitive. Editing B-spline control meshes could also be implemented using this general NMG editing capability. In this case, if an existing edge was to be split, in order to create an extra control point, a whole row or column of extra control points would have to be inserted, to maintain the logically rectangular topology of the B-spline control mesh. When an NMG editing operation would complete, a series of simple checks would see if the topology of the new shape qualified as an existing primitive shape, such as an ARB8 or an ARBN. If so, the new shape would be stored as the simpler and less general primitive, so as to take advantage of the more efficient data storage and faster analysis processing speeds inherrent in the less general primitive shapes. This capability should replace a large portion of the existing geometry editing interface, and should provide geometry builders with unparalleled flexibility and power in creating new shapes. \sectionheadtwo{NMG with Trimmed NURBS Faces} One of the most exciting current research projects at BRL is the extension of the NMG framework to permit faces either to be planar N-gons, or trimmed non-uniform rational B-splines (``trimmed NURBS''). This will permit many of the tessellation operations to be implemented exactly, rather than as approximations. This will also permit solids to enjoy the economy of having most faces be represented as planar N-gons, which are very compact and efficient to process, while those few faces that require sculptured surface shape control can be represented as trimmed NURBS. This combination provides both efficiency and full shape control in the rich non-Manifold topological framework: a combination that does not exist in any current commercial CAD system. \sectionheadtwo{Interrogation Extensions} To date, most BRL-CAD applications programs have been implemented using the ray-tracing paradigm, because of ray-tracing having a lengthy head start. By choosing the ray sampling density within the Nyquist limit for a given spatial resolution, many applications based on ray-tracing are well satisfied by extracting ray/geometry intersection information. 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 will always lead to some sampling inaccuracies. Applications which simulate particles or small rocks approaching the model might benefit from having a direct 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 [AMAN84, KIRK86]. 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. While recent research has begun to explore techniques for intersecting cylinders, cones, and planes with geometry [KAJI83], ray-tracing and polygon-based techniques are by far the most well developed approaches. However, there are several additional types of interface to the model geometry that are likely to be of general applicability. \sectionheadthree{3-D Finite-Element Volume Mesh} Many forms of energy flow analysis, such as heat flow, vibrational analysis (acoustic energy flow), and stress analysis require the use of 3-D Finite-Element Mesh (FEM) techniques. While there has been some work on using the ray-tracing paradigm to construct finite element and finite difference meshes [LAGU89], it has been difficult to deal with high spatial frequency (fine detail) portions of the model. In particular, meshing small diameter pipes is problematic, since undersampling can cause the pipe to incorrectly be separated into multiple pieces. In order to improve on the current state of affairs, it seems necessary to provide support for the generation of volume meshes directly as part of the application interface. This would provide the meshing algorithm to have unrestricted access to the underlying geometry, the space partitioning tree, and other internal data in order to perform a better job. Even more promising still would be a strategy that takes advantage of the NMG support. A first pass might tessellate the model and evaluate the booleans to produce a surface mesh. The second pass would then take the surface mesh and fill the interior (or exterior) volumes with appropriately chosen volume elements. A very good fit could probably be achieved using only parallelepiped (``brick'') elements and 20-node ``superelements''. The brick elements would be used to fill interior volume that does not border on a face, and the superelements would be used for volume that contacts a face. Recourse could be made back to the underlying geometry (perhaps via firing a few well chosen rays) to get the curvature of the superelement faces to match the curvature of the underlying primitive, rather than having to rely strictly on the NMG planar-face approximation. \sectionheadthree{Homogeneous Trimmed B-Splines} When support for trimmed NURBS faces has been added to the NMG capability, it will be possible to represent all existing primitives either with exact rational B-spline versions, or with very good rational B-spline approximations. This could be done even for faces that were completely planar. This offers the hope that it might be possible (albeit memory intensive) to convert an entire CSG solid model into a homogeneous collection of non-uniform rational B-spline faces organized in a non-manifold topological data structure. In addition to the conceptual simplicity afforded by having a uniform representation for shape, this affords the opportunity to create new analysis codes that can process curved surfaces, yet at least initially only have to deal with one kind of shape. This would also provide a very direct and natural interface to spline based [ROGE90] and Bezier-patch [BEZI74] based modeling systems. \sectionheadthree{Analytic Analysis} Given a homogeneous geometric representation such as the Trimmed B-Splines just discussed which also has an analytic representation, a further processing capability arises. Rather than interrogating the data base by means sampling or subdivision techniques, the direct mathematical manipulation of the source geometry through its parametric representation becomes possible. Calculations of physical properties requiring integration over a surface can often be evaluated with greater accuracy using an explicit analytic calculation than would be provided by numerical evaluation. While this may be difficult in general due to the complexity of the parametric expression, some classes of surface representations good candidates. Splines, for example, are piecewise-polynomial functions which have relatively simple Fourier transform representations. Since 2-D spatial Fourier transforms arise frequently in far-field electromagnetic scattering calculations, exploitation of the parametric spline representation is of interest in predictive scattering calculations. With the rapidly developing potential of symbolic calculation, treatment of seemingly impossible formulas resulting from the geometry/physics interaction may become tenable. This could help to reduce the trend towards employing numerical methods at the onset of a problem and avoid some of the accompanying instabilities and errors. \sectionhead{Summary} In this paper, a brief history of solid modeling has been presented, with special emphasis placed on the central role that the solid model plays in the design and analysis cycle. A detailed look was taken at how different analysis applications can interrogate the solid model to extract relevant information. For CSG-Rep solid modeling system, the lack of an explicit representation for the final, developed shapes was identified as a critical lack. The systems engineering issues associated with creating an explicit representation for CSG solid models without loosing the fidelity of existing geometric databases were considered, and a strategy using Non-Manifold Geometry data structures was adopted. The implementation of the NMG data structures and algorithms were presented in significant detail. To convert existing primitive shapes into NMG objects, the details of several tessellation algorithms were examined, with particular attention being paid to the topic of rigorous user-controlled error bounds on the algorithms. Evaluating boolean combinations of tessellated objects has only recently become tractable, since the use of the NMG data structures makes these operations much more straightforward. The details of a three-stage algorithm for boolean evaluation were presented in sufficient detail to permit the average reader to be able to implement this technique. Finally, the existing user interface was presented, as well as an overview of a whole gamut of new applications that will now be able to process existing CSG geometry databases. This represents a major and important capability, the true significance of which will only become apparent over the next few years. \sectionhead{Acknowledgements} The authors would like to thank Dr. Paul Deitz for providing unflagging support and encouragement for this effort. He has established a research atmosphere that breeds good work, and is fun to work in. The authors would also like to thank Prof. Dave Rogers for once again persuading us to take the time to write all this down. Finally, the clarity of the paper was greatly improved thanks to numerous suggestions by Susanne Muuss and Christopher Johnson. % WARNING: This bibliography was created by hand from TROFF/REFER output. % Don't just casually blow it away, edit it! % (All the TeX standard bibliography packages are rotten). % % $Header: /vld/mike/talks/90nmg/RCS/joined.html,v 1.1 1998/05/01 06:53:13 mike Exp $ % \sectionheadtwo{References} \beginitemlist \item [AMAN84] J. Amanatides, ``Ray Tracing with Cones,'' {\em Computer Graphics (Proceedings of Siggraph '84)}, vol. 18, no. 3, July 1984. \item [APPL88] K. A. Applin, M. J. Muuss, R. J. Reschly, M. Gigante, and I. Overend, {\em Users Manual for BRL-CAD Graphics Editor MGED}, BRL Internal Publication, October 1988. \item [BEZI74] P. E. Bezier, {\em Mathematical and Practical Possibilities of \break UNISURF}, Academic Press, New York, 1974. \item [COBB84] E. S. Cobb, {\em Design of Sculptured Surfaces using the B-spline Representation}, PhD dissertation, University of Utah, June 1984. \item [COOK84] R. Cook and Porter, L. Carpenter, ``Distributed Ray Tracing,'' {\em Computer Graphics (Proceedings of Siggraph '84)}, vol. 18, no. 3, pp. 137-145, July 1984. \item [COON67] S. A. Coons, {\em Surfaces for Computer-Aided Design of Space Forms}, Tech. report MAC-TR-41, Project MAC, MIT, NTIS AD No. 663-504, Cambridge MA, June 1967. \item [deBO78] C. deBoor, {\em A Practical Guide to Splines}, Applied Mathematical Sciences 27, Springer-Verlag, New York, 1978. \item [DEIT82] P. H. Deitz, {\em Solid Modeling at the US Army Ballistic Research Laboratory}, 2, pp. 949-960, Proceedings of the 3rd NCGA Conference, 13-16 June 1982. \item [DEIT83] P. H. Deitz, {\em Solid Geometric Modeling -- The Key to Improved Materiel Acquisition from Concept to Deployment}, Defense Computer Graphics 83, Washington DC, 10-14 October 1983. \item [DEIT84a] P. H. Deitz, {\em Modern Computer-Aided Tools for High- \break Resolution Weapons System Engineering}, DoD Manufacturing Technology Advisory Group MTAG-84 Conference, Seattle WA, 25-29 November 1984. \item [DEIT84b] P. H. Deitz, {\em Predictive Signature Modeling via Solid Geometry at the BRL}, Sixth KRC Symposium on Ground Vehicle Signatures, Houghton MI, 21-22 August 1984. \item [DEIT85] P. H. Deitz, {\em The Future of Army Item-Level Modeling}, Army Operations Research Symposium XXIV, Ft. Lee VA, 8-10 October 1985. \item [DEIT88] P. Deitz, W. Mermagen Jr, and P. Stay, ``An Integrated Environment for Army, Navy, and Air Force Target Description Support,'' {\em Proceedings of the Tenth Annual Symposium on Survivability and Vulnerability}, April 1988. \item [GOOD89] Michael T. Goodrich, ``Triangulating a Polygon in Parallel,'' {\em Journal of Algorithms}, vol. 10, 1989. \item [GOUR71] H. Gouraud, ``Continuous Shading of Curved Surfaces,'' {\em IEEE Transactions on Computers}, vol. C-20, no. 6, pp. 623-628, June 1971. \item [HARR82] R. F. Harrington, {\em Field Computation by Moment Methods}, Krieger, Malabar, Florida, 1982. \item [IEEE76] IEEE, {\em IEEE Standard 521}, Institute of Electrical and Electronic Egnineers, Piscataway NJ, November 30, 1976. \item [KAJI83] J. T. Kajiya, ``New Techniques for Ray Tracing Procedurally Defined Objects,'' {\em Transactions on Graphics}, vol. 2, no. 3, pp. 161-181, July 1983. \item [KEDE85a] G. Kedem, {\em Computer Structures and VLSI Design for Curve-Solid Classification}, Siggraph '85 Tutorial ``VLSI for Computer Graphics'', San Francisco CA, July 23, 1985. \item [KEDE85b] G. Kedem and J. L. Ellis, {\em Computer Structures for Curve-Solid Classification in Geometric Modeling}, Siggraph '85 Tutorial ``VLSI for Computer Graphics'', San Francisco CA, July 23, 1985. \item [KIRK86] D. B. Kirk, ``The Simulation of Natural Features Using Cone Tracing,'' in {\em Advanced Computer Graphics}, ed. T. L. Kunii, pp. 129-144, Springer-Verlag, 1986. \item [LAGU89] G. Laguna, {\em Recent Advances in 3D Finite Difference Mesh Generation Using the BRL-CAD Package}, pp. 21-35, BRL-CAD Symposium '89, Aberdeen Proving Ground, MD, 24-25 October, 1989. \item [LAID86] David H. Laidlaw, W. Benjamin Trumbore, and John F. \break Hughes, ``Constructive Solid Geometry for Polyhedral Objects,'' {\em Computer Graphics}, vol. 120, no. 4, Proceedings of SIGGRAPH 86, Dallas, Texas, August 1986. \item [LANI79] J. H. Laning and S. J. Madden, ``Capabilities of the SHAPES System for Computer Aided Mechanical Design,'' {\em Proc. First Annual Conference on Computer Graphics in CAD/CAM Systems}, pp. 223-231, Cambridge MA, April 9-11, 1979. \item [MAGI67] MAGI, {\em A Geometric Description Technique Suitable for Computer Analysis of Both Nuclear and Conventional Vulnerability of Armored Military Vehicles}, MAGI Report 6701, AD847576, August 1967. \item [MOLN87] Zsuzsanna Molnar, ``Advanced Engineering/Scientific Graphic Workstations,'' in {\em Techniques for Computer Graphics}, ed. D. F. Rogers, R. A. Earnshaw, Springer-Verlag, 1987. \item [MOOR84] J. Moore and R. Pizer (eds), {\em Moment Methods in Electromagnetics}, Wiley, New York, 1984. \item [MUUS87a] M. J. Muuss, ``Understanding the Preparation and Analysis of Solid Models,'' in {\em Techniques for Computer Graphics}, ed. D. F. Rogers, R. A. Earnshaw, Springer-Verlag, 1987. \item [MUUS87c] M. J. Muuss and P. Dykstra, K. Applin, G. Moss, E. Davisson, P. Stay, C. Kennedy, {\em Ballistic Research Laboratory CAD Package, Release 1.21}, BRL Internal Publication, June 1987. \item [MUUS88a] M. J. Muuss and P. Dykstra, K. Applin, G. Moss, P. Stay, C. Kennedy, {\em Ballistic Research Laboratory CAD Package, Release 3.0 -- A Solid Modeling System and Ray-Tracing Benchmark}, BRL Internal Publication, October 1988. \item [MUUS90b] M. J. Muuss, {\em Multiple Families of Engineering Analyses Interrogating a Single Geometric Model}, Proceedings of the 8th Army Math Conference, Ithaca NY, 19-22 June 1990. \item [OKIN78] N. Okino and et al., {\em TIPS-1, '77 Version}, Institute of Precision Engineering, Hokkaido University, Sapporo Japan, March 1978. \item [PELF86] John Pelfer, {\em Georgia Tech Research Institute Radar Cross Section Modeling Software}, Modeling and Analysis Division, Georgia Tech Research Institute, October 1986. \item [RAPP76] J. R. Rapp, {\em A Computer Model for Predicting Infrared Emission Signatures of An M60A1 Tank}, BRL Report No. 1916, NTIS AD No. B013411L, August 1976. \item [RAPP83] J. R. Rapp, {\em A Computer Model for Estimating Infrared Sensor Response to Target and Background Thermal Emission Signatures}, BRL Memorandum Report ARBRL-MR-03292, August 1983. \item [REQU82] A. A. G. Requicha and H. B. Voelcker, ``Solid Modeling: A Historical Summary and Contemporary Assessment,'' {\em IEEE Computer Graphics and Applications}, vol. 2, no. 2, pp. 9-24, March 1982. \item [REYN89] William R. Reynolds, {\em PRISM User's Manual Version 2.0}, Keweenaw Research Center, Michigan Technological University, Houghton, MI 49931, October 1989. \item [RITC78a] D. M. Ritchie and K. Thompson, ``The UNIX Time-Sharing System,'' {\em Bell System Technical Journal}, vol. 57, no. 6, pp. 1905-1929, 1978. \item [RITC78b] D. M. Ritchie, S. C. Johnson, M. E. Lesk, and B. W. \break Kernighan, ``The C Programming Language,'' {\em Bell System Technical Journal}, vol. 57, no. 6, pp. 1991-2019, 1978. \item [ROGE90] D. F. Rogers and J. A. Adams, {\em Mathematical Elements for Computer Graphics, 2nd ed.}, McGraw-Hill, New York, 1990. \item [THOM84] S. W. Thomas, {\em Modelling Volumes Bounded by B-spline Surfaces}, PhD dissertation, University of Utah, June 1984. \item [TOOM82] J. C. Toomay, {\em Radar Principles for the Non-Specialist}, Lifetime Learning Publications, London, 1982. \item [WEIL85] Kevin J. Weiler, ``Edge-based Data Structures for Solid Modeling in Curved-Surface Environments,'' {\em IEEE Computer Graphics and Applications}, vol. 5, no. 1, pp. 21-40, January 1985. \item [WEIL87] Kevin J. Weiler, ``The Radial Edge Structure: a Topological Representation for Non-Manifold Geometric Modeling,'' in {\em Geometric Modeling for CAD Applications}, ed. M. Wozny, H. McLaughlin, and J. Encarnacao, Springer Verlag, December 1987. \enditemlist