################################################ # # # ## ## ###### ####### ## ## ## ## ## # # ## ## ## ## ## ### ## ## ## ## # # ## ## ## ## #### ## ## ## ## # # ## ## ###### ###### ## ## ## ## ### # # ## ## ## ## ## #### ## ## ## # # ## ## ## ## ## ## ### ## ## ## # # ####### ###### ####### ## ## ## ## ## # # # ################################################ The following paper was originally published in the Proceedings of the USENIX 1996 Conference on Object-Oriented Technologies (COOTS) Toronto, Ontario, Canada, June 1996. For more information about USENIX Association contact: 1. Phone: 510 528-8649 2. FAX: 510 548-5738 3. Email: office@usenix.org 4. WWW URL: http://www.usenix.org Class Relationships and User Extensibility in Solid Geometric Modeling James R. Miller University of Kansas miller@eecs.ukans.edu Abstract Solid Geometric Modeling is an important enabling technology in Computer-Aided Design and Manufacturing. Open, extensible architectures which foster efficient construction and manipulation of models are important to design engineers. We describe the architecture of the cryph Solid Modeler, focusing on aspects of the design which maximize flexibility and enable user-extensibility of primitive modeling shapes. 1.0 Introduction Geometric Modeling and Computer Graphics are important tools in modern industrial design and manufacture. Computer models are replacing physical models. They are cheaper to construct, easier to change, and simpler to analyze. They enable a broad range of automated technologies including finite element analysis, process planning, robotics, and computer-controlled manufacturing. Computer simulations save industry both time and money, and computer analyses of geometric models lead to better and cheaper products. Geometric Modeling is concerned with efficient and robust computer-based representation and analysis of geometric information describing a product to be manufactured. An important sub-discipline of Geometric Modeling is Solid Modeling in which one creates a complete volumetric representation of an object [Requicha 80]. Geometric Modelers provide the capability to create and manipulate curves and surfaces. Solid Modelers build on top of this curve and surface functionality by establishing a framework in which the curve and surface elements are guaranteed to describe a valid, physically-realizable solid. We describe our system from a programming language point of view, including its goals and architecture and some of our ongoing research efforts related to user extensibility of modeling primitives. No specialized knowledge of curve and surface representations is required to read this paper, however we do need to introduce a few basic concepts related to Solid Modeling. While several different solid representations have been studied over the years [Requicha 80], two schemes predominate in systems today: Constructive Solid Geometry (CSG) and Boundary Representations (B-Rep). CSG representations define a solid as a general Boolean combination of half-spaces. Loosely speaking, a half-space boundary is a surface which divides space into two distinct regions: an "inside" and an "outside". Each region is called a half-space. For example, a plane is a half-space boundary which determines a half-space containing the points on one side of the plane and another half-space containing those points on the other side. Similarly, the half-spaces associated with a sphere are those points inside the sphere and those that are outside. In CSG Solid Modeling, the designer rarely, if ever, thinks of the boundary of a desired half-space as distinct from the half-space itself. For example, a designer would not care to distinguish between creating a spherical surface and a spherical half-space. This distinction is one that is significant only to certain internal algorithms, and even at that, it is merely a matter of how the basic data defining the sphere is used. That is, the geometric definitions for the boundary and for the half-space are identical. We mention these issues here since they affected the design of our class hierarchy. At issue were the sometimes conflicting demands of "specification purity" and "naturalness" of the user interfaces. We shall examine these issues in section 5. B-Reps characterize a solid by an explicit description of its boundary (i.e., its "skin"). That is, they consist of a hierarchical collection of trimmed boundary elements (vertices, edges, and faces) which, when taken together, completely describe the exterior boundary of a solid. B-Rep data structures are typically designed to draw a sharp distinction between topological information (i.e., adjacency relationships which are independent of shape) and geometric information (i.e., the actual points, curves, and surfaces which determine shape). Both CSG and B-Reps are prevalent because they can be effectively used to create a wide range of models, and because algorithms are known for most commonly desired analysis applications. In addition, these two representations have largely complementary advantages and disadvantages. Some systems -- called dual representation systems [Requicha 80, Miller 89] -- maintain both in a redundant fashion. Today, Solid Modeling systems are growing in use, due largely to slow but steady progress in terms of numerical stability, geometric coverage, and application algorithms. Nevertheless, a great many technological challenges remain. Here we focus on two such issues related to programming language support: „ controlled reuse and refinement of geometric software Many operations applied to curves and surfaces depend only on the generic type of the entity. For example, the method for applying rigid transformations to conics is independent of the type of conic involved. On the other hand, simple robust intersection algorithms for intersecting two circles are preferred over more general curve-curve (or even conic-conic) intersection algorithms. Observations such as these have led many to the conclusion that object-oriented techniques including the application of inheritance with overriding can provide appropriate, natural, and powerful tools for the construction of Geometric Modeling systems. „ user extensibility of modeling primitives The designer of a modeling system must supply basic modeling and analytical tools supporting basic curve and surface definition as well as intersections and other algorithms. For creating solid models, a set of component solids is normally provided which a designer can use to construct a model. Loosely speaking, one either "cuts" with the component solid or "glues it onto" the evolving model. At the lowest level, these component solids are half-spaces, but specific common shapes (blocks, bounded portions of cylinders and cones, etc.) are often provided in addition to facilitate the engineer's work. This set of common shapes is unavoidably incomplete. There are inevitably application-specific "common shapes" which are not sufficiently general-purpose to warrant being a part of the standard product, yet they are of considerable value to specific groups of engineers. These engineers need to be able to tailor the standard system by adding such specialized component solids. Havi! ng done so, these specialized components must appear and behave exactly as those in the standard product. The remainder of the paper is organized as follows. In the next section we discuss the relevant evolution of the cryph modeler which is being used as a testbed for techniques applicable to these problems, and we relate it to other possible approaches. The remaining sections discuss relevant portions of the cryph architecture from a programming language support point of view. In particular we discuss how and why various concepts were modeled as they were in C++. Finally we summarize in section 7. 2.0 The cryph Modeler and Other Engines Cryph is a dual representation Solid Modeler developed at the University of Kansas based in part on curve and surface intersection utilities developed over the past five to ten years in ANSI C (e.g., [Miller 87, Miller & Goldman 95]). The original cryph modeler was written purely in ANSI C and used an implementation of a subset of PHIGS [ISO 89, Howard, et. al. 91] for display. The version of cryph described here employs the same low-level curve and surface intersection utilities and boundary evaluator. However, development moved to C++ to enable a more flexible representation for the geometry1. In particular, the CSG representation was explicitly designed to enable the user extensibility features discussed in section 4 which were the focus of much of the original effort. In fact, the original structure of the boundary evaluator [Miller 93] was designed specifically to provide low-level support for such extensibility. The current version also uses OpenGL [Neider, et. al. 93] and the object-oriented OpenInventor [Wernecke 94] for graphics display and interaction. From a solid modeling point of view, the primary type of user-definable extension we wanted to provide was the ability to create application-specific "macro solids" which would appear exactly like system-supplied instantiable solids. These are fairly straightforward to create with the architecture we now have, yet they are surprisingly powerful and useful. Another type of extension would be to allow users to add new surface types (and hence also new curve types). While possible in principle, this remains an extraordinarily complex task. Adding macro solids requires only a packaging of a suitably parameterized CSG sub-tree; adding new surface types, on the other hand, minimally requires that new surface-surface and curve-surface intersection algorithms be provided by the person wishing to add these new geometric forms. Not only does this involve considerably more sophisticated software development, but also we have not yet addressed the issue of documenting to such a developer all the issues involved in adding such new forms. Indeed, there are research issues lurking there which need to be addressed [Lamping 93]2. The current (C++) version of the cryph modeler views the older cryph utilities as a solid modeling engine. This concept is not unique. In recent years, much effort has been expended in the specification and prototyping of such potential engine interfaces. Computer-Aided Manufacturing, International (CAM-I) was an early leader in this effort [CAM-I 90]. More recently, Spatial Technology's ACIS modeler and toolkit [ACIS 95] has emerged as a popular engine for a variety of modeling systems. While ACIS supports Boolean operations between solids, it is basically a pure B-Rep system. A major thrust of our overall research agenda revolves around the potential of dual CSG/B-Rep modeling, and we needed an engine with support for such dual models at the core. This was a major reason we continued to use the older cryph utilities as opposed to the commercial ACIS product. Other differences of interest between the two engines relate to the use of Nonuniform Rational B-Splines (NURBS). In cryph, NURBS curves and surfaces are used only for the interface to OpenGL and OpenInventor. That is, NURBS objects are created on the fly from the cryph B-Rep when needed for display. In ACIS, NURBS curves and surfaces are a basic modeling form. A detailed discussion of the related implications is beyond the scope of this paper. 3.0 Substratum Curve and Surface Issues Lines, planes, conics, and quadrics are currently the core geometric forms in cryph. The relationships between these classes are depicted in Figure 1. (a) Curves (b) Surfaces and Solids Figure 1: The cryph Curve, Surface, and Solid Class Hierarchies These portions of the class hierarchy reflect the usual goals of factoring code for common operations while providing for specialization of operations in particular cases. As implied earlier, however, the situation is different for Bezier and NURBS curves and surfaces since they are only generated as alternate representations of parabolas (Bezier) and other conics and quadrics (NURBS) to facilitate the graphical display interface. The subclasses of these freeform shapes are used to record how instances were created so that subsequent modification and query operations can be facilitated. Sample class definitions for a vertical slice of the c_Curve hierarchy (in particular, the c_CurveȚc_ConicȚc_Ellipse classes) are presented in Figure 2 (a-c). The data type "real" is platform-dependent, but is typically defined to be double precision. The classes "aPoint" and "aVector" encapsulate the notions of points and vectors in three-dimensional affine space. class c_Curve { public: c_Curve(); c_Curve(const c_Curve& c); virtual ~c_Curve(); // instance methods virtual void ASCIIdisplay(ostream& os) const = 0; virtual real getParameterOf(const aPoint& p) const = 0; virtual void getPointAt(real parameter, aPoint& p) const = 0; virtual int pwlApproximation(real errorHint, aPoint outputBuffer[], int outputBufferLength, orientation o=UNSPECIFIEDorientation, endPointSpec* endPt = NULL) { return 0; } virtual const char* const typeName() const = 0; // operators c_Curve& operator=(const c_Curve& rhs); }; Figure 2(a): The c_Curve class To support fundamental solid modeling operations, it is necessary to compute intersections (i.e., find the set of points common to) various combinations of instances of curves and surfaces. Most generally we require pairwise intersections; occasionally it is desirable to find the set of points common to three surfaces simultaneously. The result of a general intersection operation (maintained in an instance of class c_IntersectionResult) is either empty (i.e., the operands share no points), or it consists of some collection of discrete points and (portions of) curves and surfaces. class c_Conic : public c_Curve { public: c_Conic(); c_Conic(const c_Conic& C); c_Conic(const aPoint& O , const aVector& U, const aVector& W); c_Conic(const aPoint& O , const aVector& W); virtual ~c_Conic(); void getLocalCoordinates(const aPoint& p, real& x, real& y) const; aPoint getOrigin() const; aVector getU() const; aVector getV() const; aVector getW() const; // Class Methods static void putThetaInStandardRange( real& theta); // OPERATORS virtual c_Conic& operator=(const c_Conic&); protected: // All conics have a local coordinate system: aPoint mOrigin; aVector mU; aVector mV; aVector mW; private: void validateData(); }; Figure 2(b): The c_Conic sub-class It is our practice to invoke specialized algorithms based on the type of curves and surfaces given to these utilities. The lack of reasonable support in C++ to support such double (and occasionally triple) dispatch was an early disappointment. We were at least able to hide the awkwardness of the actual dispatch from the programmer by modeling requests for intersections as constructors for class c_IntersectionResult: c_IntersectionResult(const c_Curve& c1, const c_Curve& c2); c_IntersectionResult(const c_Curve& c1, const c_Surface& s2); c_IntersectionResult(const c_Surface& s1, const c_Surface& s2); c_IntersectionResult(const c_Surface& s1, const c_Surface& s2, const c_Surface& s3); The basic idea is that when the system needs to compute the intersection of some combination of curves and surfaces, the programmer declares an instance of c_IntersectionResult, specifying the required curves and surfaces as implied above. Depending on the dynamic classes of the curves and surfaces, specialized algorithms are invoked to compute the various pieces of the intersection and store them in instances of class c_IntersectionItem. The resulting collection of these items is then associated with the c_IntersectionResult. This approach allowed us to minimize the size and complexity of the class interfaces for both the curves and surfaces as well as for the intersection result itself. 4.0 Basic Solid Modeling and User Extensibility We define two fundamental subclasses of solids: "simple" and "structured". (See Figure 1(b).) Simple solids are half-spaces, the base objects to which the CSG Boolean operations are applied. Structured solids are general Boolean combinations of half-spaces. They are the only types of solids for which it is useful to keep an associated B-Rep. In our system, B-Reps can be associated with each instance of a structured solid in a CSG graph. However in practice B-Reps are normally maintained only at the top one or two levels due to storage considerations. Simple and structured solids differ also in how they are generated by the designer and validated by the system. Simple solids (half-spaces) can be instantiated via numerical parameters which are simple and orthogonal. That is, each parameter can be tested for validity independent of all others. If an invalid parameter is detected, it is easy to substitute a reasonable default value which will yield a valid instance. Structured solids, on the other hand, are generated by specifying Boolean operations between simple or other structured solids. It is impossible to generate an "invalid" structured solid using the standard operators. class c_Ellipse : public c_Conic { public: c_Ellipse(); c_Ellipse(const c_Ellipse& E); c_Ellipse(const c_Circle& C); c_Ellipse(const aPoint& C , const aVector& U, const aVector& W, real Rmajor, real Rminor); virtual ~c_Ellipse(); // OPERATORS friend ostream& operator<<(ostream& os, const c_Ellipse& obj); virtual c_Ellipse& operator=( const c_Ellipse&); // GENERAL METHODS virtual void ASCIIdisplay(ostream& os) const; aPoint getCenter() const; real getMajorRadius() const; real getMinorRadius() const; real getParameterOf( const aPoint& p) const; void getPointAt(real parameter, aPoint& p) const; virtual int pwlApproximation(real errorHint, aPoint outputBuffer[], int outputBufferLength, orientation o=UNSPECIFIEDorientation, endPointSpec* endPt = NULL); virtual const char* const typeName() const; // CLASS METHODS static const char* const className(); private: static const char* const TypeName; void validateData(); real mMajorRadius; real mMinorRadius; }; Figure 2(c): The c_Ellipse sub-class 4.1 User Extensibility via "Macro Solids" A subclass of structured solids -- c_MacroSolid in Figure 1(b) -- re-introduces instantiation via numerical parameters. It is here where users extend the set of modeling primitives as mentioned in the Introduction. To recap, the motivation was based on simplifying the work required of the design engineer. That is, the set of half-spaces coupled with the Boolean operators is sufficient to generate desired models. However many geometric features appear with great regularity, and it becomes horribly inefficient to recreate each instance with appropriate instantiations and combinations of half-spaces. Of course this has been known for almost as long as solid modelers have been in existence; hence since the 1970s most developers of solid modelers have provided an additional set of such shapes which can be directly instantiated. Typical simple examples include a bounded cylinder (the portion of a cylindrical half-space between two given planar half-space boundaries), and a parallelepiped (the intersection of six planar half-spaces). The fact that these common shapes are really just "macros" for certain common construction sequences is not apparent in most systems, however. In many instances this is due to how the boundary evaluation algorithms work. Many need to be bootstrapped from simple bounded objects whose boundary topology is known a priori. In addition, system designers typically implemented these shapes as specific built-in objects in closed systems, and that meant that it was not viable for end-users to augment the system-supplied set with some of their own favorites. When such extensions were allowed by the system, the resulting CSG tree would typically have a large number of duplicate half-spaces. The boundary evaluator in cryph was specifically designed to work directly from half-spaces for exactly this reason [Miller 95], and we have provided a standard interface in the class hierarchy where users can add their own set of specialized shapes, created with minimally-sized CSG trees. Such shapes are added by defining an appropriate subclass of c_MacroSolid in which a particular set of methods is defined and implemented. We used this facility ourselves to implement the pseudo-standard set of such shapes: bounded cone, block (parallelepiped), bounded cylinder, and wedge (half of a parallelepiped). These are illustrated in Figure 1(b). In addition, students in our Geometric Modeling class have defined and used their own as part of class projects using this system. A necessary evil associated with macro solids is that the actual instantiation and validation of instances of these specialized modeling shapes can be more complex than that for half-spaces. This is due largely to the fact that, unlike half-spaces, the instantiation parameters for macro solids are typically not orthogonal, and hence the validity of a given parameter cannot in general be decided in isolation from others. For example, the parallelepiped primitive takes three vectors specifying the directions of the edges, and the validity condition is that these three vectors be linearly independent. When instantiation errors are detected, it is therefore often more difficult to determine how the situation can best be corrected. 5.0 On Multiple Inheritance As illustrated in Figure 1(b), class c_Halfspace inherits multiply from c_Surface and c_SimpleSolid, modeling the idea that half-spaces can be used for surface operations such as intersections as well as for solid operations such as deciding whether a point lies in the interior of a solid. Modeling the classes in this way contradicts what we described in the Introduction, namely that half-space boundaries are surfaces which separate the points in two distinct half-spaces. Thus in the interests of specification purity, one should define a class "half-space-boundary" which would inherit from c_Surface, and then model "half-space" as a subclass of c_SimpleSolid. The relationship between these two would then be "half-space has-a half-space-boundary". While more accurate from a mathematical point of view, there seemed to be a danger that the user interface could be complicated. As a quick example, if the designer wants to create a sphere, we would need to determine (i.e., the designer would have to tell us) whether a spherical skin or a spherical solid were actually desired. This would require first that we explain to the design engineer that there is a difference between half-spaces and half-space boundaries, a tenuous proposition. Moreover, like us, the designer often wants to create such an object once and use it both ways. For example, he may create two spheres, ask whether some point is inside both, and then ask for their circle of intersection. The designer typically asks such questions without thinking about whether it is a question asked of a solid or of a surface. Since the defining data is identical for both, forcing such a seemingly arbitrary distinction would most likely be met with disdain. We chose to define c_Halfspace using multiple inheritance since the difference between half-spaces and half-space boundaries is of no interest to engineers, and since there is never any internal ambiguity. That is, it is always clear whether surface properties or solid properties are of interest when a given method is invoked. Furthermore, there is no overhead in terms of instance variables since the defining data for both is identical. 6.0 Rendering In contrast to the distinctions considered in the previous section, it is vitally important to distinguish between a geometric model and an image of the model. While the concept of a model is independent of any display device or graphics system, images are intimately tied to these. In addition, images often involve various geometric approximations and/or re-representations, as well as other intentional visual distortions. We often also wish to support multiple simultaneous visual representations of an object. All these goals dictate that view-independent geometric descriptions be maintained which know nothing about graphical display. One or more separate class hierarchies can then be developed which support particular display approaches. Instances of these "renderers" are created for individual entities to be displayed. The renderer knows what is required of a particular visualization medium, and it knows how to ask appropriate questions of the geometry in order to obtain data to drive the graphics engine. An example of a "renderer" class hierarchy used in cryph is illustrated in Figure 3. Instances of these renderers interface to the object-oriented OpenInventor engine on Silicon Graphics workstations (and occasionally directly to OpenGL in addition) to produce interactive visualizations of the cryph B-Rep (Figure 4). Notice that the renderer hierarchy does not match the application class hierarchy. This should not be surprising. Consider the following: „ Different characteristics are important in the geometric model hierarchy than are important in the renderer hierarchy. An obvious example is the fact that the renderers care first about whether the object to be rendered is bounded or unbounded. „ The geometric model hierarchy is also much deeper. This is in part to factor common analysis code and to facilitate simple, yet flexible interface specifications (for example, the c_CurveȚc_ConicȚc_Ellipse relationships), and in part to record how certain instances of an object were created in order to facilitate construction, modification, and other query operations (e.g., the c_NURBSCurve Ț c_NURBSConic Ț c_NURBSEllipse relationships). Generally speaking, there is an i_Renderer subclass for every leaf class in the c_Curve, c_Surface, and c_Solid hierarchies. The exceptions are where subclasses are employed only to record how certain instances of an object were created (i.e., NURBS curves and surfaces and c_StructuredSolid). The renderer is only concerned with the object, not how it was created. „ Multiple inheritance was not needed on the renderer side, but recall it was used on the application side to model certain application-specific and image-independent relationships involving half-spaces. In our work to date, we have only required visualizations of the boundaries of objects, hence the fact that a half-space can also be interpreted as a solid has been irrelevant to the renderer. In fact, the current solid renderer in effect simply extracts the outer skin of the solid piece by piece, passing each piece to individual surface renderers. Techniques for volumetric visualization through direct volume rendering are well-known [Watt & Watt 92]. They are extremely useful when attempting to visualize certain types of internal structure and/or the distribution of functional properties (heat, stress, etc.) which vary continuously throughout the interior of an object. As our work progresses, it is very likely that we will require such volumetric visualization capabilities. However, it is unlikely that multiple inheritance will be employed at that time since the rendering techniques for surfaces and volumes are radically different. Thus no argument can be made that volumetric renderers have sufficient common functionality with surface renderers to warrant an inheritance relationship. Unlike the arguments we made when discussing the definition of classes for half-spaces, no awkwardness would be foisted upon either the designer or the programmer since the class to be created depends only on the type of visualization desired (something which obviously must be specified anyway) and such a renderer would never be expected to play a "dual role". That is, we would never expect such a renderer to generate a more traditional surface display. Figure 3 A Renderer Class Hierarchy We have additional visualization interfaces which output text files for use by other visualization programs. For example, we generate POV-Ray input files [POV 93] to generate ray traced images like those in Figure 5. These interfaces are currently implemented as methods in the geometric classes. They add negligible overhead and do not compromise the integrity of the model in any way. That is, they simply dump textual data describing the model to an fstream. Figure 4 An OpenInventor Display of a B-Rep Solid 7.0 Summary We have described the history and basic architecture of the cryph solid geometric modeling system, focusing on how the class hierarchies were designed in order to satisfy various important design criteria related to user extensibility and graphics system portability. We have also presented our rationale for the use of multiple inheritance in the surface and solid portions of the hierarchy, observing that our use of multiple inheritance was driven by user interface considerations and internal expediency, but was not immune to criticism. Finally we described the use of separate class hierarchies to support visualization of and interaction with the model in a way that keeps the notion of model distinct from image of a model. To date we have focused on the construction of the infrastructure of the solid modeler. We are currently pursuing projects which use this engine in a number of ways. We are working on an interactive modeler which, among other things, will allow the designer to create new macro solids interactively. For example, the modeler would be used to construct the shape and to specify relevant parametric relationships. The system would then automatically generate C++ definitions and code for an appropriate c_MacroSolid subclass. We are also investigating ways to construct more sophisticated metaclasses which would allow new macro solids to be created on the fly without the need for generation of actual new C++ subclasses. Figure 5: A Ray Traced Image of a CSG Solid A generalization of these efforts is being studied which focuses on the use of the engine to support variational classes of models [Shapiro & Vossler 95]. A number of additional issues arise in that context, not the least significant of which is the need for a mechanism to record and subsequently solve sets of quite general constraint equations which describe the geometric relationships of importance in a variational family of parts. Acknowledgments Much of the work described here was performed in DesignLab, a multidisciplinary research laboratory funded in part by NSF Grant CDA-94-01021. References [ACIS 95] Spatial Technology, ACIS, http://www.spatial.com/ spatial. [CAM-I 90] Computer-Aided Manufacturing, International, Application Interface Specification (AIS) 2.0, CAM-I, Arlington, Texas. [Howard, et. al. 91] T. Howard, W. Hewitt, R. Hubbold, and K. Wyrwas, A Practical Introduction to PHIGS and PHIGS PLUS, Addison-Wesley, 1991. [ISO 89] International Organization for Standardization, ISO 9592: Programmer's Hierarchical Interactive Graphics System (PHIGS), 1989. [Lamping 93] J. Lamping, Typing the Specialization Interface, ACM SIGPlan Notices (Proceedings OOPSLA '93), Vol. 28, No. 10, October 1993, pp. 201-214. [Miller 87] J. R. Miller, Geometric Approaches to Nonplanar Quadric Surface Intersection Curves, ACM Transactions on Graphics, Vol. 6, No. 4, October 1987, pp. 274-307. [Miller 89] J. R. Miller, Architectural Issues in Solid Modeling, IEEE Computer Graphics and Applications, Vol. 9, No. 5, September 1989, pp. 72-87. [Miller 93] J. R. Miller, Incremental Boundary Evaluation Using Inference of Edge Classifications, IEEE Computer Graphics and Applications, Vol. 13, No. 1, January 1993, pp. 71-78. [Miller 95] J. R. Miller, Incremental Boundary Evaluation For Nonmanifold Partially Bounded Solids, Graphics Interface '95, QuŽbec City, 15-19 May 1995, pp. 187-195. [Miller & Goldman 95] J. R. Miller and R. N. Goldman, Geometric Algorithms for Detecting and Calculating All Conic Sections in the Intersection of Any Two Natural Quadric Surfaces, Computer Vision, Graphics, and Image Processing, Vol. 57, No. 1, January 1995, pp. 55-66. [Neider, et. al. 93] J. Neider, T. Davis, and M. Woo, OpenGL Programming Guide, Addison-Wesley, 1993. [POV 93] POV-Ray Team, Persistence of Vision Ray Tracer (POV-Ray), Version 2.0, User's Documentation, 1993. [Requicha 80] Representations for Rigid Solids: Theory, Methods, and Systems, ACM Computing Surveys, Vol. 12, No. 4, December 1980, pp. 437-464. [Shapiro & Vossler 95] V. Shapiro and D. Vossler, What is a Parametric Family of Solids?, Proceedings, Third Symposium on Solid Modeling and Applications, Salt Lake City, ACM Press, May 1995, pp. 43-54. [Watt & Watt 92] A. Watt and M. Watt, Advanced Animation and Rendering Techniques: Theory and Practice, Addison-Wesley, 1992. [Wernecke 94] J. Wernecke, The Inventor Mentor, Addison-Wesley, 1994. 1 Interesting issues arose while determining how to marry the old utilities with the new class definitions, but a complete discussion of this history is beyond the scope of the current presentation. 2 In our case, this is also complicated in no small part by the ANSI C heritage of the curve and surface intersection utilities. -- ------------------------------------------+---------------------------------- Jim Miller | Associate Professor Department of Electrical Engineering | miller@eecs.ukans.edu and Computer Science | (913) 864-7384 (office) 415 Snow Hall +---------------------------------- University of Kansas | (913) 864-3226 (FAX) Lawrence, KS 66045 | (913) 864-4620 (department) ------------------------------------------+----------------------------------