All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Similar Documents

Description

Weierstra6-Institut fiir Angewandte Analysis und Stochastik im Forschungsverbund Berlin e. V. Covariant geometry description Ilj a Schmelzer submitted: 7th June 1995 Weierstrass Institute for Applied Analysis

Transcript

Weierstra6-Institut fiir Angewandte Analysis und Stochastik im Forschungsverbund Berlin e. V. Covariant geometry description Ilj a Schmelzer submitted: 7th June 1995 Weierstrass Institute for Applied Analysis and Stochastics MohrenstraBe 39 D Berlin Germany Preprint No. 152 Berlin 1995 Edited by Weierstrafi-Institut fiir Angewandte Analysis und Stochastik (WIAS) Mohrenstrafie 39 D Berlin Germany Fax: (X.400): c=de; a=d 400 ;p=iaas-berlin; s=preprint (Internet): Covariant Geometry Description Ilja Schmelzer June 2, 1995 Contents 1 Introduction 3 2 Definition of a Cogeometry The Continuous Case The Codimension of a Cogeometry Connection to Morse Theory The Implementation in Finite Precision Arithmetics l Affine Simplices Finite Distances Instead of Infinitesimal Directions Rounding Error Handling Subdivision into Two Different Functions Nonorthogonal Flag Directions C++ Interface and OOP Attribute Handling Algorithms for Covariant Geometry Descriptions Simplex Subdivision The Default Function The Induced Cogeometry The Intersection of Geometries Using a Simplicial Grid Using a Boundary Grid Other Possibilities Time Requirements 3.9 Topological Errors and Convexity Results 21,_, 2 1 Introduction A prerequisite for mesh generation is the availability of a geometry description. This description usually defines the boundary of the computational domain. But, this domain often consists of different regions with different material properties. In this case, also inner boundaries have to be defined. These boundaries also often have to be subdivided into different boundary faces with different boundary conditions. These boundary faces, again, have boundaries, and so on. In principle, the geometry description has to define all these regions and boundary parts. The most interesting application of geometry descriptions is the threedimensional space. Often 2D and ld simplifications will be used. But there are also interesting higher dimensional applications: 4D for space-time, 6D for the phase space, 7D for the phase space in. time. Thus, it makes sense to consider the general, n-dimensional problem. The purpose of this paper is to define a new type of geometry description called covariant geometry description or shortly cogeometry. 1 It allows to create and modify even very comple.x geometrical configurations in an easy and natural way, in principle for arbitrary dimension. It was successfully implemented in the 3D geometry description package IBGD which is part of the grid generator IBG. The current situation in 3D geometry modeling was summarized in [3] in the following words: The state-of-the-art in commercial geometric modeling technology is solid modeling. Topologically, a solid model is a two-manifold object. [... ] There is a growing awareness in the 'CAD /CAM/CAE community of the importance of providing systems which can model and represent non-manifold objects. Unfortunately, this functionality is not yet a commercial reality. Here, non-manifold object refers to a geometry with inner boundaries, boundary lines and so on. 1 The notion cogeometry we have formed in analogy to the pair cohomology - homology. Indeed, our cogeometry is a variant of the dual construction of the standard geometry description by a cell complex. From point of view of category theory, it will be more accurate to use the notion contravariant instead of covariant, but outside this theory (f.e. in general relativity) it is widely distributed to use covariant as for covariant, as for contravariant objects, to emphasize that there is a natural transformation behaviour. We also want to emphasize that our geometry description has the natural transformation behaviour of a geometry, in contrast to the cell complex. 3 The geometry description proposed in this (and other like [4]) papers is based on a separate topology description developed by Weiler [5] which lists all regions and boundaries and the neighbourhood relations between them, and geometric entity data which are usually functions from the basic boundary entities into the space. They are usually taken from some special function space, the current favorite seems to be NURBS (non-uniform rational B-splines). See also [8], [10], [9]. From pure mathematical point of view, this may be considered as an implementation of a 3D cell complex. Contrary, our covariant geometry description consists of functionsfk which find intersections of k-dimensional simplices with segments of the related codimensions - one function for each dimension. The first function F 0 is simply a function which defines the region containing a given point, the second allows to find intersections of an edge with boundary faces and so on. The major difference between these two types of geometry description is their functional behaviour. Assume we have a smooth mapping f : X -7 Y and a geometry on Y. In general, this allows to define an induced geometry on X, defining the regions on X as the pre-images of the regions on Y. In the other direction, there is no such natural possibility. A geometry on X in general does not allow to define a natural geometry on Y. Considering the behaviour of the standard geometry description, we see that a cell complex on X defines a natural cell complex on Y. But this is the wrong direction, the cell complex on Y may not be used in general to define a geometry. Our cogemetry has the correct transformation behaviour. A cogeometry on Y allows to define the induced cogeometry on X. There are a lot of interesting possibilities to create or modify geometries which may be considered as special applications of induced geometries: Higher dimensional extension of a lower dimensional geometry. Restriction of a higher-dimensional geometry to a surface. Intersection of different geometries on a given space. Boundary description by an equation f ( x) = 0. See [11], [12] about some problems which occur using standard geometry descriptions. In the cogeometry it becomes much easier to define these operations. We consider algorithms which may be used to define cogeometries: 4 the default for the functions Fk if the related boundary has no nontrivial subdivision into different segments. the geometry induced by a mapping. the intersection of geometries. the geometry described by the standard form - by a cell complex. Thus, there are algorithms for almost every input possibility. These algorithms are fast enough to be used in complex grid generation algorithms. We also have a fast prototyping strategy which allows to implement a complicate geometry step by step. The cogeometry allows also an easy handling of attributes - applicationdependent data which describe the properties of the segments and functions defined on these segments. The functionsfk may be interpreted as methods of the related class cogeometry , that means, the concept is very natural from object-oriented point of view. Some parts of our dual concept have already been used. The idea of the first of our intersection functions F 0 which returns the region containing a given point is very simple, and often this information is the only available. That's why in many applications this function will be used to describe the geometry. If necessary, the boundary position.will be approximated by a simple iteration. But i:o. this way it is not possible to describe the geometry of the boundary itself. Thus, usually such a geometry description will be considered only as a poor substitute of a complete geometry description. To obtain a unique, modular interface for different geometry descriptions which use a lot of different type~ of elementary cells and mappings of these cells (spline types) it is a natural idea to use intersection functions instead of the explicit mapping functions. This idea was also already used for geometry description, for example in [4]. But, for the description of the topological neighbourhood relations, the classical cell-complex concept was used. 5 2 Definition of a Cogeometry There are a lot of different technical realizations of the dual concept. So, a simple dualization leads to a function which returns for a given simplex and a segment of the related codimension their intersection index. Such a realization may be easier to use in theoretical considerations, but not for implementation. We try to find here a variant which allows easy implementation and usage. 2.1 The Continuous Case At first, we introduce the definition of a cogeometry for exact real arithmetics. The notion in general we use to distinguish between the general situation of transverse intersection , which define an open, dense subset in an appropriate topology, and degenerated situations . Related results and techniques you can find in [6]. We consider only the smooth case and don't try to establish the number of derivatives which is necessary. There will be different possibilities to handle the degenerate cases. But this strategy is not relevant for the problems of implementation, because the problem of degenerate cases will be covered by another serious problem - the rounding errors. That's why we simply use the strategy to define the cogeometry only for the general case. Let's now introduce the basic object. The required properties of these objects we define later. A k-simplex is a smooth mapping from the standard k-dimensional reference simplex into X. A side of a k-simplex is a (k-1 )-simplex defined by the mapping of the related side of the reference simplex. To avoid exceptions we define the side of a 0-simplex as the empty object. A k-flag consists of a point p (called position), a sequence of (k+l) segments (So,...,Sk) and k orthogonal directions (v1,...,vk) To avoid exceptions we define the flag also for k == -1 as the empty object. An intersection of a k-simplex may be a k-flag with position in the simplex - an inner intersection - or a (k-1)-flag on a side of the simplex - a boundary intersection. 6 A cogeometry G(X) is a sequence of functions Fk fork;::: 0 so that: The function Fk allows to find intersections of k-simplices. Input is a k-simplex and an inititial intersection of the simplex. The result is another intersection of the same simplex which we call the continuation of the first intersection through the simplex. Before we define the properties required for these objects, let's define them for the case of an n-dimensional geometry described by a smooth cell complex. We consider only smooth simplices and general position. In this case, the position of a k-flag is inside the segmentsk and boundary point for all Si with i k, Si is part of the boundary of S; for i j, the direction Vi is in p tangential to S; for j i, orthogonal to S;. It points into si-1 For an inner intersection, we require not only that the position of the flag is inside the simplex, but also that the projections of the flag directions into the plane of the simplex define a non-degenerate volume. This allows to define an orientation of the intersection. Now let's define the intersection function Fk. The input flag defines a point on some (k-1 )-segment Sk-l Consider the intersection of the k-simplex with this segment, especially the component containing the initial point. In the general situation we obtain a smooth 1-dimensional manifold, and the initial intersection is one of the two ends of this curve. The position of the return value is the second end of this curve. The related flag we obtain using the continuation of the flag along the curve. For degenerate cases we do not define the function. This description may fail, if it is not possible to continue the flag because of a change of the neighbourhood relations in some intermediate point of the curve. To avoid this effect we have to require that such intermediate points must be part of some boundary of codimension k. For an arbitrary geometry, this may be obtained by further subdivision of the related boundaries into parts with identical neighbourhood relations. Let's define now the properties of a cogeometry. The strategy we use to fix these properties is to find properties which are f~lfilled for our example. Let's list at first the most obvious properties: At first, we have a list of transversality and orthogonality conditions 7 - the directions of a flag have to be orthogonal, their projection on the tangential plane of the simplex not degenerated. We have a symmetry in the definition of Fk. The output of a first call may be used as the input with the same simplex. Then the result has to be the input of the fi:rst call. The (k-1 )-part of the list of segments of the two flags is identical. Usually the positions of the two flags are different. Only in the case of inner intersections, the position may be the same. But in this case the directions must be different. The result for a simplex may be derived from the results for smaller simplices obtained by subdivision of the initial simplex. Obviously these properties make sense for every geometry. Especially the last allows to localize the problem: The geometry will be completely defined by the results of Fk for arbitrary small simplices. To complete the definition, we have to add a local regularity condition which describes the local behaviour of the geometry. This may be a condition of the following type: For every point there is a small neighbourhood so that there is a diffeomorphism which allows to transfer the.local situation into the linear reference situation. 2.2 The Codimension of a Cogeometry The codimension of a cogeometry is the highest codimension of a segment of the cogeometry. For a cogeometry of codimension k it is not possible to define input values for Fz with 1 k+l. So, such a cogeometry will be completely defined by the sequence of the Fz between 0 and k+l. Becaus~ of this simplification it is useful to have information about the codimension. We have the following obvious properties of the codimension: The codimension of a cogeometry in an n-dimensional space is :::; n. The codimension of the induced cogeometry is the same as of the original. 8 The codimension of the intersection of two cogeometries is ::; the sum of the codimensions of these cogeometries. 2.3 Connection to Morse Theory There is a natural connection between the cogeometry and Morse functions (see [7]): Lemma 1 A Morse function on a space X defines a cogeometry. Proof: Each segment of this cogeometry will be related to a singularity of the Morse function. The segment may be defined as the set of points so that the limit of the gradient flow is the related singularity. The codimension of the segment is obviously the index of the singularity. qed. This connection shows that a cogeometry is a very natural object from mathematical point of view. It also shows that a cogeometry may he defined also for spaces of infinite dimension and can have infinite codimension. A space which allow to define a Morse function on it, allows also to define a cogeometry. This shows that the class of spaces which allow a cogeometry is greater than the class of spaces which allow a standard geometry description. 2.4 The Implementation in Finite Precision Arithmetics Now let's consider some modifications of the concept for the continuous case which will be necessary or useful for an implementation of the concept Affine Simplices Usually in applications we consider only the n-dimensional Euclidean space, so we have some well-defined global affine structure. To use only affine simplices makes the interface much more simpler to use. Instead of the definition of a mapping we have to define only the coordinates of the corners of the simplex. This seems to be a restriction, but for a manifold without affine structure we can simply use the affine structure of some local coordinates. The usage of other coordinates does not influence the limit of arbitrary small simplices which defines the geometry. 9 2.4.2 Finite Distances Instead of Infinitesimal Directions To define a flag, we have to define a sequence of segments and infinitesimal directions. In finite precision arithmetics, we use instead a sequence of points (Pk, Pk-1,...,po) so that: Each point Pi is inside the segment Si of the fl~g. The direction Vi is defined by the vector from Pi to Pi-1 The distance between the points is small: lvi I The position of the flag is the position of Pk The main reason are the functions which are discontinuous near the boundary. Their value on Pi can be used as boundary limits. Thus, we need no special handling for such discontinuous functions Rounding Error Handling The greatest problem of rounding errors is connected with the degenerate cases which we have not considered in the previous considerations. If we have a degeneration f = 0, it is not the problem what we do - the same as for f 0 or as for f 0. A problem occurs if a value which is really (in exact arithmetics) 0, but in finite precision arithmetics 0, or, much worse, different parts of the program use slightly different formulas which leads to different results. Our way to avoid this is to make a small modification of the result if the exact result is in such a dangerous neighbourhood of a degeneration. The modification must be small enough compared with the required accuracy of boundary computation, but it must be big enough to avoid an incorrect classification if it will be used later as input. Thus, if the required accuracy is big enough compared with the possible rounding errors, this technique allows to avoid fatal errors. It also does not require a special handling for the degenerated situations there the result is not defined in the exact, continuous case, because the input is always not degenerated. Remark that the case of a degenerated simplex is not dangerous, if the side containing the input flag itself is not degenerated. There will be simply 10 a smaller set of possible output - there may be no k-flag inside the simplex and no (k-1)-flag on degenerated sides Subdivision into Two Different Functions For a theoretical consideration it looks very nice if we have only one function for every dimension. But in the real implementation it becomes easier two distinguish two functions: The first variant of /i_'k for the case of a (k-1 )-flag as input. The other variant of Fk for the case of a k-flag as input. The idea of the simplification is that for the first variant we implement only one special case - the flag on the first side of the simplex. This makes the implementation simpler and faster. For the other variant, we can use a default implementation:. Subdivide the simplex into smaller simplices so that the k-flag lies on the border between the sub-simplices. Reinterpret this k-flag as a (k-1)-flag on this border. Use the first variant of Fk to find the continuation. While the continuation was found on the inner border between the two sub-simplices, we have to continue the search in the other sub-simplex N onorthogonal Flag Directions The orthogonality condition for the flag directions require a special consideration. The orthogonality may not be exactly fulfilled in finite precision arithmetics caused by rounding errors. Thus, in reality we will not have exactly orthogonal flag directions. There are algorithms which do not include the computation of the related orthogonal directions. Usually they allow to create only some set of directions with non-degenerated projection on the simplex plane. For a non-smooth boundary, it will not be possible to define the tangential and orthogonal directions required for the definition of a flag. 11 These problems may be solved using the convention that the directions must not be orthogonal, but only. their projections have to be not degenerated. But in this case we o~tain a new problem - the projection of the directions on the simplex plane may lead to an incorrect result for the orientation of the intersection. This problem may be solved by the following convention: The flag directions of the result must defin

Related Search

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks