Model Geometry and Topology

The role of the model in the presented mesh generator is a passive one. The model serves only for the geometrical description of individual model entities and representation of their topological relationships. There is no need to account for general topological operations (which is actually the job of a geometric modeller) and therefore the implementation of an advanced topological representation as [29] is unnecessary. A simple internal data structure was designed and implemented to store the topology of non-manifold models.

The model is described by a boundary representation and consists of the following model entities - vertices, curves, surfaces, patches, shells, and regions. Topologically, each region is formed by a set of not self-intersecting boundary surfaces, patches, and shells, each of which is bounded by a set of curves. Each curve is given by two end vertices. Moreover, each boundary surface, patch, and shell points out to the regions on the side of its outer and inner normal. While a curve keeps list of surfaces, patches, and shells sharing that curve, a vertex stores only the list of curves sharing that vertex. This basic topology is further restricted by the geometry of model entities. Both curves and surfaces are based on free-form representation in terms of tensor-product polynomial entities. This limits the number of curves bounding a surface to four. While the patch is a planar model entity, shell must be constrained to a background surface. To enhance the modelling capability an entity-to-entity fixation concept has been introduced. Generally, each model entity may be fixed to another model entity of the same or higher dimension. However, the fixed entity is not allowed to coincide with the boundary of the parent entity. Each model entity keeps the list of entities fixed to it. No further topological information is required for the description of a valid non-manifold domain of almost arbitrary complexity.

There are several ways to represent geometry of free-form curves and surfaces - Coons entities, Bezier entities, rational Bezier entities, splines, B-splines, non-uniform rational B-splines, and others. In the presented work, the rational Bezier entities have been employed. This allows to exactly represent conics and quadrics by entities starting with the order of three (quadratic curves and biquadratic surfaces). It should be noted, however, that the meshing approach presented in this work is generally applicable to all tensor-product polynomial entities of an arbitrary degree.

The rational Bezier curve has the form

where is the positional vector of a point on the curve, are Bezier control points,  are weights of Bezier control points, stand for Bernstein polynomials,  denotes a curve parameter varying in the range from to , is the curve degree, and represents the rational Bernstein polynomial of the form

The curve order is equal to . and correspond to model vertices while the remaining points form the control polygon of the curve dictating its bow (Fig. 2.2a). The first and last segments of the control polygon coincide with the curve tangent at the starting and ending vertices, respectively. A curve may be degenerated into a single point (a collapsed curve) if all its control points including the end vertices are merged at this point. This allows to model ``triangular'' surfaces.

The rational Bezier surface can be written in a similar form

where is the positional vector of a point on the surface, are Bezier control points, are weights of Bezier control points, and stand for Bernstein polynomials, and denote curvilinear coordinates of the surface ranging from to , and are surface degrees (orders are greater by ) in and parametric directions, respectively, and stands for the rational Bernstein polynomial of the form

If the control points are arranged in the matrix of type then the corner points correspond to model vertices, the side points correspond to control polygons of model curves bounding the surface and the remaining points form the control polygon of the surface (Fig. 2.2b). Since the degeneration of a surface into a curve or point is not supported, no two adjacent curves are allowed to be degenerated into a single point and no two opposite or adjacent curves are allowed to be the same.

Bernstein polynomials can be expressed as

or recursively as

where . Note that the ordinary Bezier entities can be derived from the rational Bezier entities when all weights are set to .

The hierarchy of the topological data structure and geometrical representation of individual model entities used in the current implementation of the sequential mesh generator is schematically outlined in Table 2.1. The capability of the presented topological and geometrical representation is demonstrated by an example of a non-manifold domain (Fig. 2.1). It consists of a combination of wireframe, surface, and solid data with non-manifold features as touching at a single point or along a single curve.