13472J/1.128J/2158J/16940J COMPUTATIONAL GEOMETRY Lecture 1 Nicholas m. patrikalakis Massachusetts Institute of Technology Cambridge MA 02139-4307. USA Copyright @2003 Massachusetts Institute of Technology Contents 1 Introduction and classification of geometric modeling forms 1.1 Motivation 1.2 Geometric modeling forms 1.2.1 Wireframe modeling 4 1.2.4 Non-two-manifold modeling 4 1.3 Basic classification of solid modeling methods 1.3.1 Decomposition models 1.3.2 Constructive solid geometry(CSG) 1.3.3 Boundary representation(B-Rep 1.4 Alternate classification of geometric modeling forms 1.4.1 Introduction 1. 4.2 Unevaluated sentation systems 1.4.3 Evaluated representation systems Bibliography 21
13.472J/1.128J/2.158J/16.940J COMPUTATIONAL GEOMETRY Lecture 1 Nicholas M. Patrikalakis Massachusetts Institute of Technology Cambridge, MA 02139-4307, USA Copyright �c 2003 Massachusetts Institute of Technology Contents 1 Introduction and classification of geometric modeling forms 2 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Geometric modeling forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 Wireframe modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.2 Surface modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.3 Solid modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.4 Non-two-manifold modeling . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Basic classification of solid modeling methods . . . . . . . . . . . . . . . . . . . 7 1.3.1 Decomposition models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3.2 Constructive solid geometry (CSG) . . . . . . . . . . . . . . . . . . . . . 14 1.3.3 Boundary representation (B-Rep) . . . . . . . . . . . . . . . . . . . . . . 16 1.4 Alternate classification of geometric modeling forms . . . . . . . . . . . . . . . 18 1.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.4.2 Unevaluated representation systems . . . . . . . . . . . . . . . . . . . . 18 1.4.3 Evaluated representation systems . . . . . . . . . . . . . . . . . . . . . . 20 Bibliography 21 1
Lecture 1 Introduction and classification of geometric modeling forms 1.1 Motivation Geometric modeling deals with the mathematical representation of curves, surfaces, and solids necessary in the definition of complex physical or engineering objects. The associated field of computational geometry is concerned with the development, analysis, and computer implemen tation of algorithms encountered in geometric modeling. The objects we are concerned with in engineering range from the simple mechanical parts(machine elements) to complex sculptured bjects such as ships, automobiles, airplanes, turbine and propeller blades, etc. Similarly, for the description of the physical environment we need to represent objects such as the ocean bottom as well as three-dimensional scalar or vector physical properties, such as salinity, tem- perature, velocities, chemical concentrations(possibly as a function of time as well Sculptured objects play a key role in engineering because the shape of such objects(e.g for aircraft, ships and underwater vehicles) is designed in order to reduce drag or increase the thrust(eg. for propeller blades). At the same time these objects need to satisfy other design constraints to permit them to fulfill certain design requirements (e. g. carry a certain payload be stable in perturbations, etc). Similarly, there are objects which have significant aesthetic requirements, eg. cars, yachts, consumer products Typically, engineers deal with the definition of complex shapes such as engines, automobiles aircraft, ships, submarines, underwater robots, offshore platforms, etc. The shape of these objects is usually not fully known in advance(except when a baseline design is available) Consequently, the usual design procedure is iterative, involvin Shape creation based on certain design requirements Analysis to evaluate the performance of the object; and Shape modification to improve the shape, followed by analysis(and so on in an iterativ loop) until a satisfactory (and in simple cases, an optimal) design is reached, which satisfies all the design requirements and minimizes a certain cost function Geometric modeling attempts to provide a complete, flexible, and unambiguous represen- tation of the object, so that the shape of the object can be
Lecture 1 Introduction and classification of geometric modeling forms 1.1 Motivation Geometric modeling deals with the mathematical representation of curves, surfaces, and solids necessary in the definition of complex physical or engineering objects. The associated field of computational geometry is concerned with the development, analysis, and computer implementation of algorithms encountered in geometric modeling. The objects we are concerned with in engineering range from the simple mechanical parts (machine elements) to complex sculptured objects such as ships, automobiles, airplanes, turbine and propeller blades, etc. Similarly, for the description of the physical environment we need to represent objects such as the ocean bottom as well as three-dimensional scalar or vector physical properties, such as salinity, temperature, velocities, chemical concentrations (possibly as a function of time as well). Sculptured objects play a key role in engineering because the shape of such objects (e.g. for aircraft, ships and underwater vehicles) is designed in order to reduce drag or increase the thrust (eg. for propeller blades). At the same time these objects need to satisfy other design constraints to permit them to fulfill certain design requirements (e.g. carry a certain payload, be stable in perturbations, etc). Similarly, there are objects which have significant aesthetic requirements, eg. cars, yachts, consumer products. Typically, engineers deal with the definition of complex shapes such as engines, automobiles, aircraft, ships, submarines, underwater robots, offshore platforms, etc. The shape of these objects is usually not fully known in advance (except when a baseline design is available). Consequently, the usual design procedure is iterative, involving: • Shape creation based on certain design requirements; • Analysis to evaluate the performance of the object; and, • Shape modification to improve the shape, followed by analysis (and so on in an iterative loop) until a satisfactory (and in simple cases, an optimal) design is reached, which satisfies all the design requirements and minimizes a certain cost function. Geometric modeling attempts to provide a complete, flexible, and unambiguous representation of the object, so that the shape of the object can be: 2
Easily visualized (rendered Easily modified(manipulated) Increased in complexity .Converted to a model that can be analyzed computationally Manufactured and tested Computer graphics is an important tool in this process as visualization and visual inspection of the object are fundamental parts of the design iteration. Computer graphics and geometric modeling have evolved into closely linked fields within the last 30 years, especially after the in roduction of high-resolution graphics workstations, which are now pervasive in the engineering environment The remainder of this lecture introduces many of the different approaches to geometric modeling representations that have evolved over the last four decades 1.2 Geometric modeling forms Several different geometric modeling forms have evolved over the last forty years. For the definition of model, we can say that an abstract entity M is a model of an object O if M can be used to answer specific questions about O Different forms of geometric modeling can be distinguished based on exactly what is being represented, the amount and type of information directly available without derivation, and what other information can and cannot be derived 1.2.1 Wireframe modeling Figure 1.1: Wire frame model of a cube Wireframe modeling, developed in the early 1960,'s, is one of the earliest geometric modelin techniques. It represents objects by edge curves and vertices on the surface of the object including the geometric equations of these entities(and also possibly but not always adjacency information), as shown in Figure 1. 1. The traditional drawings of a ship's lines(Figure 1.2 (4) is a form of a wireframe model of a ship hull. It is created by intersecting the hull surface with three sets of orthogonal planes. Usually the hull surface is taken as the molded hull surface hich is the inner side of the hull plating. Intersections of the hull surface with vertical planes (from bow to stern) are called buttock lines. Intersections of the hull surface with horizontal
• Easily visualized (rendered) • Easily modified (manipulated) • Increased in complexity • Converted to a model that can be analyzed computationally • Manufactured and tested Computer graphics is an important tool in this process as visualization and visual inspection of the object are fundamental parts of the design iteration. Computer graphics and geometric modeling have evolved into closely linked fields within the last 30 years, especially after the introduction of high-resolution graphics workstations, which are now pervasive in the engineering environment. The remainder of this lecture introduces many of the different approaches to geometric modeling representations that have evolved over the last four decades. 1.2 Geometric modeling forms Several different geometric modeling forms have evolved over the last forty years. For the definition of model, we can say that an abstract entity M is a model of an object O if M can be used to answer specific questions about O. Different forms of geometric modeling can be distinguished based on exactly what is being represented, the amount and type of information directly available without derivation, and what other information can and cannot be derived. 1.2.1 Wireframe modeling Figure 1.1: Wire frame model of a cube. Wireframe modeling, developed in the early 1960’s, is one of the earliest geometric modeling techniques. It represents objects by edge curves and vertices on the surface of the object, including the geometric equations of these entities (and also possibly but not always adjacency information), as shown in Figure 1.1. The traditional drawings of a ship’s lines (Figure 1.2 [4]) is a form of a wireframe model of a ship hull. It is created by intersecting the hull surface with three sets of orthogonal planes. Usually the hull surface is taken as the molded hull surface which is the inner side of the hull plating. Intersections of the hull surface with vertical planes (from bow to stern) are called buttock lines. Intersections of the hull surface with horizontal 3
planes(parallel to keel) are the waterlines, while intersections with transverse vertical planes are called sections. Wireframes are rather incomplete and possibly ambiguous representations that were superseded by surface models 1.2.2 Surface modeling Surface modeling techniques, developed in the late 1960s, go one step further than wireframe epresentations by also providing mathematical descriptions of the shape of the surfaces of objects, as shown in Figure 1.3 Surface modeling techniques allow graphic display and numerical control machining of care- fully constructed models, but usually offer few integrity checking features(e. g. closed volumes) The surfaces are not necessarily properly connected and there is no explicit connectivity infor- mation stored. These techniques are still used in areas where only the visual display is required e. g. flight simulators 1.2.3 Solid modeling Solid modeling, first introduced in the early 1970,s, explicitly or implicitly contains information about the closure and connectivity of the volumes of solid shapes. Solid modeling offers a number of advantages over previous wireframe and surface modeling techniques. In principle it guarantees closed and bounded objects and provides a fairly complete description of an object modelled as a rigid solid in 3D space [ 7, 6,8 Figure 1. 4 illustrates that for a boundary based solid model of a single homogeneous object very surface boundary is always directly adjacent to one other surface boundary, guaranteeing closed volume. Solid models, unlike surface models, enable a modeling system to distinguish the outside of a volume from the inside. This capability, in turn, allows integral property analysis for the determination of volume, center of volume or gravity, moments of inertia, etc. any An example is Baumgart's winged edge data structure [ 1, 2], where every edge has a start end point, a face on either side, and at least two edges from each vertex bounding the faces. This information can be put in tabular form(perhaps using a relational database) or in a graph like data structure and used to ensure adjacency. Typical solid modeling systems also offer tools for the creation and manipulation of complete solid shapes, while maintaining the integrity of the representations Solid modeling techniques exclude the two previous modeling forms(wireframe and surface modeling). The reason is that the solid modeling forms are traditionally constrained to work only with two-manifold solids In a two-manifold solid representation, every point on the surface has a neighborhood on the surface which is topologically equivalent to a two-dimensional disk. In other words, even though the surface exists in three dimensional space, it is topologically fiat when the surface is examined closely in a small enough area around any given point, as illustrated by the cube in Figure 1.5 1.2.4 Non-two-manifold modeling Non-two-manifold modeling 1, 9, 5, 10 is a new modeling form which removes constraints associated with two-manifold solid modeling forms by embodying all of the capabilities of Figure 1.2: Wire frame model of a ship hull
planes (parallel to keel) are the waterlines, while intersections with transverse vertical planes are called sections. Wireframes are rather incomplete and possibly ambiguous representations that were superseded by surface models. 1.2.2 Surface modeling Surface modeling techniques, developed in the late 1960’s, go one step further than wireframe representations by also providing mathematical descriptions of the shape of the surfaces of objects, as shown in Figure 1.3. Surface modeling techniques allow graphic display and numerical control machining of carefully constructed models, but usually offer few integrity checking features (e.g. closed volumes). The surfaces are not necessarily properly connected and there is no explicit connectivity information stored. These techniques are still used in areas where only the visual display is required, e.g. flight simulators. 1.2.3 Solid modeling Solid modeling, first introduced in the early 1970’s, explicitly or implicitly contains information about the closure and connectivity of the volumes of solid shapes. Solid modeling offers a number of advantages over previous wireframe and surface modeling techniques. In principle, it guarantees closed and bounded objects and provides a fairly complete description of an object modelled as a rigid solid in 3D space [7, 6, 8]. Figure 1.4 illustrates that for a boundary based solid model of a single homogeneous object, every surface boundary is always directly adjacent to one other surface boundary, guaranteeing a closed volume. Solid models, unlike surface models, enable a modeling system to distinguish the outside of a volume from the inside. This capability, in turn, allows integral property analysis for the determination of volume, center of volume or gravity, moments of inertia, etc. An example is Baumgart’s winged edge data structure [1, 2], where every edge has a start and end point, a face on either side, and at least two edges from each vertex bounding the faces. This information can be put in tabular form (perhaps using a relational database) or in a graph like data structure and used to ensure adjacency. Typical solid modeling systems also offer tools for the creation and manipulation of complete solid shapes, while maintaining the integrity of the representations. Solid modeling techniques exclude the two previous modeling forms (wireframe and surface modeling). The reason is that the solid modeling forms are traditionally constrained to work only with two-manifold solids. In a two-manifold solid representation, every point on the surface has a neighborhood on the surface which is topologically equivalent to a two-dimensional disk. In other words, even though the surface exists in three dimensional space, it is topologically flat when the surface is examined closely in a small enough area around any given point, as illustrated by the cube in Figure 1.5. 1.2.4 Non-two-manifold modeling Non-two-manifold modeling [1, 9, 5, 10] is a new modeling form which removes constraints associated with two-manifold solid modeling forms by embodying all of the capabilities of Figure 1.2: Wire frame model of a ship hull
Figure 1.3: Surface model of a cube. 1. 4: Solid model of a cube the previous three modeling forms in a unified representation. The following diagrams (in Figure 1.6) demonstrate non-two-manifold situations In an environment which allows non-two manifold situations, the surface area around a given point on a surface might not be flat in the sense that the neighborhood of the point need not be equivalent to a simple two-dimensional disk. This allows topological conditions such as a cone touching another surface at a single point, more than two faces meeting along a common edge, and wire edges emanating from a point on a surface. A non-two-manifold representation therefore allows a general wire frame mesh with surfaces and enclosed volum embedded in space. Overall, non-two-manifold representations have superior flexibility,can represent a larger variety of objects, and can support a wider variety of applications than two-manifold representations, but at a cost of a larger size and more compler data structure. Applications of the non-two-manifold representation include Distinguish between two different solids, such as a beam welded to a plate(Figure 1.7 Represent a solid volume with a cutout and the volume that was cut out(Figure 1.8) Distinguish between the components of a composite plate(Figure 1. 9) Represent a finite element mesh embedded in a solid object(Figure 1.10) Represent different dimensions simultaneously, such as a volume with a cut plane and an axis of revolution(Figure 1.11)
Figure 1.3: Surface model of a cube. Figure 1.4: Solid model of a cube. the previous three modeling forms in a unified representation. The following diagrams (in Figure 1.6) demonstrate non-two-manifold situations. In an environment which allows non-two manifold situations, the surface area around a given point on a surface might not be flat in the sense that the neighborhood of the point need not be equivalent to a simple two-dimensional disk. This allows topological conditions such as a cone touching another surface at a single point, more than two faces meeting along a common edge, and wire edges emanating from a point on a surface. A non-two-manifold representation therefore allows a general wire frame mesh with surfaces and enclosed volumes embedded in space. Overall, non-two-manifold representations have superior flexibility, can represent a larger variety of objects, and can support a wider variety of applications than two-manifold representations, but at a cost of a larger size and more complex data structure. Applications of the non-two-manifold representation include: • Distinguish between two different solids, such as a beam welded to a plate (Figure 1.7). • Represent a solid volume with a cutout and the volume that was cut out (Figure 1.8). • Distinguish between the components of a composite plate (Figure 1.9). • Represent a finite element mesh embedded in a solid object (Figure 1.10). • Represent different dimensions simultaneously, such as a volume with a cut plane and an axis of revolution (Figure 1.11)