Geometric modeling

Geometric modeling, also English Computer Aided Geometric Design ( CAGD ) called, refers to the computer-based description of the shape of geometric objects. It deals both with the description of two-dimensional curves as well as three-dimensional surfaces and bodies. The geometric modeling takes place next to the computer graphics and related fields such as computer -aided design ( CAD) in engineering and scientific fields of application, such as for physical simulations of the behavior of bodies.

• 2.1 Direct representation schemes 2.1.1 Standard cell enumeration scheme
• 2.1.2 Constructive Solid Geometry
• 2.1.3 Generative modeling
• 2.1.4 voxel

• 2.2.1 wireframe
• 2.2.2 Surface representation

• 3.1 polygonisation
• 3.2 Physically based modeling

Free-form curves and surfaces

Free-form curves and surfaces can be made using splines, so here meant piecewise polynomial functions describing. The principle can be extended from the two-dimensional curves on three-dimensional surfaces.

Hermite curves

Cubic Hermite curves are composed of Hermitian polynomials of the third degree. Every polynomial is determined by a start and end point and the corresponding tangents. If the Hermitian polynomials are assembled to form a spline, the tangents of two adjacent polygons are equated. For the choice of the tangents, there are various possibilities. The simplest is to equate a tangent with the line connecting the nearest control points straight, however, other methods have been developed:

• When Cardinal splines, the tangents are determined by a parameter c between 0 and 1 indicating the " power " at the checkpoint.
• Catmull-Rom splines are a special case of Cardinal splines, where c = 0. They are often used in computer animation as animation curves because they run exactly through the control points and its derivative is continuous.
• Kochanek - Bartels splines, also called TCB splines, provide another parametrization of Hermite curves with the three parameters Tension, Continuity and Bias.

Bezier curves

A Bezier curve of degree n is a parametric curve defined by N 1 control points. The polygon which connects the control points to each other is referred to as the control polygon. While a linear Bezier curve, so a first-degree Bezier curve, a simple segment between the two points, a quadratic Bezier curve describes a parabolic part. Many graphics programs use cubic Bezier curves.

A Bezier curve interpolates between the individual control points by means of Bernstein polynomials, which show the influence of the control points depending on the curve parameters. Apart from the start and end points, the curve does not pass through the control points, in general, but is included in the convex hull. For drawing a Bezier curve of the de Casteljau algorithm can be used that approximates a Bezier curve by a polygon.

Bezier curves are invariant under affine transformations. This means that an affine transformation of the control points is the same curve as an affine transformation of the original curve. A problem of Bezier curves is that at a certain position of the control points or contact as colons are possible. Local changes at the control points affect although undesirably to the entire curve, but are only of local importance.

B- splines and NURBS

B -spline curves provide improved compared to Bezier curves locality and controllability: Changes affect only locally, and only a portion of the curve has to be recalculated. Similar to Hermite curves B -spline curves are piecewise composed of individual polynomials. The seams are called nodes. Unwanted oscillations ( Runge's phenomenon ) in a large number of nodes are avoided. B- splines are a linearly weighted combination of basis functions, called B-splines. The basis functions are piecewise polynomials with a small carrier. Changes outside of the carrier does not affect the B- spline curve.

Uniform basis functions are shifted, each centered on a node copies of each other. In uniform, linear basis functions are triangular functions that are centered on a particular node and have a support which extends over three nodes. Quadratic and cubic basis functions are composed of correspondingly higher polynomials, but always centered on a node. In contrast, non-uniform basis functions have different forms. B -spline curves can be converted into a polygon with the de Boor algorithm.

An extension are rational B-spline curves, or in general non- uniform rational B-splines ( NURBS ), the parametric representation is a mathematical breakage. NURBS are general enough to describe all the usual curves and surfaces. Some recent modeling tools they use as the sole internal representation method.

Representation schemes

Various methods for representing objects (display schemes ) are designed to be able to be converted by their storage requirements, numerical accuracy, complexity, and capability to other presentation schemes differ. Another property of a representation scheme is the ability to check whether a model is correct, so a "real " physically possible object defined.

A distinction is made between direct representation schemes that describe the volume itself, and indirect schemes in which the description of edges and surfaces are. In addition, hybrid schemes are conceivable, which combine both methods.

Direct representation schemes

Standard cell enumeration scheme

For standard cell enumeration scheme of the space is divided into a grid of evenly split cells ( voxels). A body is represented by a set of cells. The smaller the voxel, the more the body is approximated. The enumeration scheme consumes a lot of memory.

Constructive Solid Geometry

In Constructive Solid Geometry (CSG ) objects using primitives such as sphere, cube or cylinder, and operators such as intersection, union or difference be modeled. A CSG body can be based on a formula that applies the operators on the base body, describe and illustrate a tree.

CSG is common especially in the CAD field. An investigation concluded that allows 63% of all mechanical components with a CSG system that uses only square and straight circular cylinder model. If more body be allowed, so as much as 90 % of all components in traditional mechanical engineering (primarily drilling, milling, turning the components or their molds ) describe in a natural way by CSG.

A big advantage of CSG over other representation schemes is that their correctness is guaranteed if only certain body be allowed. For example, if R- sets are used as the main body, thus guarantee the properties that a corresponding CSG tree is correct. In addition, CSG bodies are very compact and easy to produce. Many rendering methods can not deal directly with CSG and demand that CSG bodies are first converted into B- reps, which is a relatively difficult task.

Until the 1980s, most based modeling tools either on Boundary Representations or CSG.

Generative modeling

A generative model is a shape that has been called by a continuous transformation of a shape generator which generates. The dimension of the model is irrelevant. The modeling takes place at a high level and is expandable. Using a programming language such as the Generative Modeling Language, the user can quite easily build a library of useful forms.

Shifting geometries, also called sweeps, are a special case of generative models. They are produced by a curve or a volume guided along a curve.

A special case of sweeps are surfaces of revolution generated by a certain amount is rotated about an arbitrary axis.

Voxel

Voxel are spatially arranged in grid form and values ​​that describe the " density " of an object and can be represented by the means of volume graphics. Voxel allow parts of objects " cut away " and see inside. Also, CSG operations can be easily implemented. However, voxel require a lot of space, and they tend to unwanted aliasing effects. The modeling using voxel is used mainly in medicine, fluid dynamics and in the representation of natural objects such as clouds application.

Indirect representation schemes

Wireframe

A wireframe model defines a body exclusively through its edges. This model offers speed advantages, since the representation is very efficient. A problem with this scheme is its ambiguity. A wireframe model can represent several different bodies, since it is not clear where the surfaces run. A masking calculating like surfaces is not possible, but the Haloed -line algorithm may be used.

Surface representation

A display surface, also called the boundary representation, or B -rep, the description of a body by means of its surface; B- reps are so " hollow". B- reps are rendering scheme, probably most commonly used in computer graphics. Meshes are used frequently in particular.

B- reps are well suited for efficient rendering general surfaces and allow it to make local changes to the model. Disadvantages of B- reps are their high memory requirements and the difficulty of checking the correctness.

On the so-called Euler operations based representation schemes are used to guarantee the correctness for the modeling of objects as a B- rep at least partially. The idea is to allow only so-called Euler operations that maintain the Euler characteristic or alter them in some way.

Modeling techniques

Polygonisation

Many algorithms in computer graphics, including some rendering methods only work with meshes. Also, finite element methods are based on this form of representation. Numerous Polygonisierungsalgorithmen have been developed which provide the results of varying quality. In general, to a Polygonisierungsmethode achieve a good approximation to the shape of the original object, with respect polygons balanced, not to produce a narrow form, and the local topology of the original object, so do not leave any gaps or breaks occur. Examples of Polygonisierungsalgorithmen are

• The cutting cube algorithm by M. Schmidt and
• The tracking algorithm of E. Hartmann. see

Torus: cutting cube method

Physically based modeling

Modeling methods that take into account in addition to the static and the dynamic properties of objects, is called based physically. Objects can in this case be not only rigid but also flexible. An example is a piece of cloth that is placed over other objects and its drape is automatically calculated.