QMG logo

Geometric Objects in QMG

The QMG package supports two datatypes: breps and simplicial complexes. Simplicial complexes are also called “meshes.”

Before plunging into the details of geometric representation, consider using some of the simpler ways to create breps. For a simple way to create two-dimensional breps, consider the gm_cpoly routine. For a simple way to create three-dimensional polyhedral breps, consider using OFF format.

Overview of breps

A brep is a geometric object that is specified by its boundary faces (“brep” is short for “boundary representation”). Many people pronounce brep like “bee-rep”. Breps have different internal representations in Matlab versus Tcl/Tk, but the two representation have essentially the same data. Below we describe the details of the internal representations, but first we describe data present in a brep.

The next few paragraphs cover three-dimensional breps whose intrinsic dimension is also three. Below we turn to lower-dimensional breps.

A brep is composed of topological entities which are also sometimes called faces for short. A brep has four types of faces: chambers, surfaces, edges and vertices. These faces have dimensions 3, 2, 1, 0 respectively. The boundary of each face is defined by a list of faces of one lower dimension. In other words, the boundary of a chamber is one or more surfaces, the boundary of a surface is zero or more edges, and the boundary of an edge is zero or more vertices.

The topological hierarchy for a QMG 2.0 object must have the following property: if two faces have a common point, then their intersection must be a common topological subentity. For example, a cube is bounded by six squares. Two adjacent squares must have a common topological edge.

Breps in QMG 2.0 must be finite and must be watertight. Watertight has the following meaning in 3D: for each chamber C, when all the edges that occur as boundaries of surfaces that occur as boundaries of C are enumerated, each edge must occur an even number of times (counting multiplicity). Similarly, for each surface S, when all the vertices that occur as boundaries of edges that occur as boundaries of S are enumerated, each vertex must occur an even number of times in this enumeration. For example, this rule means that for the cube mentioned in the last paragraph, it is not permissible for two surfaces that share a common edge to own separate copies of that edge under two different names.

Each topological entity, except for a chamber, is composed of geometric entities. In particular, a surface is composed of Bezier patches, an edge is composed of Bezier curves, and a vertex has a point associated with it.

Bezier patches of two types are supported: triangular patches and tensor product patches. See G. Farin, Curves and Surfaces for Geometric Design for the definition of the two kinds of Bezier patches. Here are the rules governing Bezier patches and curves.

Rules concerning the relationship between topological entities and geometric entities are as follows:

In QMG, each face is allowed to have property-value pairs. This is a list of pairs of strings. The first string in each pair is the property name, and the second string is the value of that property. For example, surfaces can have a color property that indicates their color to be used by graphics routines. Property names are case-insensitive, e.g., color and CoLOR are not distinguished. The brep itself can have property-value pairs that apply to the whole brep. One important global property is geo_global_id. The corresponding value for this property is intended to be a universally unique ID string for the brep. In QMG 2.0, there is no system for generating these ID strings, but some of the routines like gmchecktri check them.

So far we have discussed breps with intrinsic and embedded dimension equal to 3. The embedded dimension of a brep is the dimension in which it is embedded and is equal to the number of coordinates in each of its control points. QMG 2.0 supports either 2 or 3 for this value. A brep's intrinsic dimension is the highest-dimensional face that it owns. For instance, a brep with topological vertices and edges but no surfaces or chambers would have intrinsic dimension equal to 1. The intrinsic dimension can never exceed the embedded dimension. The mesh generator requires that the intrinsic and embedded dimensions be equal, although other routines in QMG 2.0 allow the intrinsic dimension to be lower.

If the intrinsic and embedded dimension of the brep are both d (where either d=2 or d=3) then the term region is used to denote the topological entities of dimension d. Thus, for a three-dimensional brep, its chambers are its regions. For a two-dimensional brep, its surfaces (subsets of the plane) are its regions. Regions are completely specified by their boundaries, so they do not have any geometric entities associated with them in a brep definition.

Thus, the data items that make up a brep are as follows.

On the difference between geometric and topological entities

The preceding section detailed geometric and topological entities, but the reader may wonder why we bothered with this distinction. Why not have geometric entities only? There are two advantages to this system: For example, consider the following regular 30-gon.

picture of 30-gon
Two possible ways to represent this in QMG would be: In the first case, the topological edge is not G1, but nonetheless QMG permits small divergences from G1 as mentioned earlier. There are also many other options for representing the 30-gon; for example, there could be five edges each made of six linear curves, etc.

Here is the mesh generated by QMG (coarse mesh requested) for the first option:

picture of first mesh of 30-gon

Here is the mesh generated by QMG (coarse mesh requested) for the second option:

picture of second mesh of 30-gon
Notice the two meshes are quite different. Depending on your application, one or the other might be more appropriate.

Internal boundaries in breps

As mentioned early, a brep face can have bounding faces of one lower dimension. A brep face can also have internal boundaries, which are subfaces of lower dimension that are inside the face itself, i.e., they have the interior of the face on both sides of them.

Internal boundaries usually serve one of two purposes in a scientific computation: they act as demarcations between separate regions of the domain (for instance, the domain may represent an object that is a composite of several materials) or they act as singular boundaries, for example, in modeling a region with a slit or crack. Holes in a domain are not internal boundaries—they are classified as ordinary boundaries.

Internal boundaries are useful because the mesh generator will respect them in its mesh (i.e. mesh elements will not cross through them). They can also be the site of boundary conditions for the finite element package.

There are three kinds of internal boundaries supported by the QMG package, multi-region, repeated boundary, and low-dimensional boundary.

A multi-region brep means that there are multiple regions in the brep. (Recall that region means a topological entity of dimension equal to the embedded dimension.) The boundary between two regions is a type of internal boundary. The region on either side sees it as an ordinary boundary.

A repeated boundary means that a region has a boundary face listed twice in its list of boundaries. For example, suppose a 3D chamber lists a topological surface twice in its list of bounding faces. This makes the surface act like a crack or fissure inside the chamber. Lower-dimensional faces can also have repeated boundaries. This is sometimes necessary to attach a region's repeated boundary to an exterior boundary. For instance, to represent a cube with a crack, such that the crack meets an exterior boundary, the crack itself would be a repeated boundary of the region, and then its edge where it meets the exterior boundary would be a repeated boundary of the exterior boundary.

Finally, a face can have one or more low-dimensional boundaries, which act like low dimensional cracks. In particular, a chamber can have edges or vertices as low-dimensional boundaries, and a surface can have vertices as a low-dimensional boundaries.

Multi-region breps are generally used for the case of internal boundaries that demarcate the brep into several zones. The mesh generator lists the elements that it generates according to the region in which they lie. See the description of meshes below. The finite element program can take advantage of these labels during matrix assembly. For example, it can use different functions to compute conductivity and source terms for the two sides of the internal boundary corresponding to different materials.

In the case of a single-region brep with repeated boundaries, there is no concept of one side of the internal boundary versus the other since the fissure may cut only partway through the domain. Thus, all elements have the same label.

The various types of internal boundaries can be freely mixed in the same brep.

The mesh generator will produce a single layer of nodes along either an repeated boundary or an internal boundary in a multi-region domain. In some applications a double layer of nodes is desirable. It is possible to produce a double layer of nodes along a repeated boundary with the gmdouble function.

Overview of simplicial complexes

A simplicial complex is a collection of simplices of one specific dimension embedded in a space of the same or higher dimension. (Thus, simplicial complexes in QMG cannot contain simplices of several different dimensions in the same complex). Simplicial complexes are the output of the mesh generator and are an input to the finite-element program and to the graphics programs.

As with a brep, a simplicial complex has two integers associated with it, the embedded dimension and the intrinsic dimension. Also like a brep, a simplicial complex can have property-value pairs. For example, one possible property name is geo_global_id. The mesh generator stores the brep's ID in this field during mesh generation. The field is omitted in a mesh generated for a brep without a global ID. The rest of the data is lists of vertices and elements.

The first list is the vertex real-space coordinates. Each vertex has a global ID number, which must be a nonnegative integer. Global ID numbers must be unique within the mesh but do not have consecutive or in order. With each global ID is a tuple of two or three real-space coordinates of the node. (The number of real-space coordinates per node equals the embedded dimension.)

Next are lists of vertices and simplicial faces associated with brep topological entities. Let d be the embedded dimension of the mesh. Let B be the brep that gave rise to the mesh. Then each brep topological entity F of dimension 0 to d−1 has a list of vertices lying on it. For each vertex on F, the following information is stored: its global ID number, the curve or patch index of the geometric entity containing the vertex (omitted when d=0) and the parametric coordinates on that entity (omitted when d=0). Mesh vertices lying on lower-dimensional subfaces of F are also listed as lying on F since they will have a different patch-index and parametric coordinates with respect to F. Thus, the same mesh vertex may appear in many different lists associated with various brep faces.

Each brep topological entity of dimension 1 to d has a list of simplex faces lying on it. This list is made of tuples. A brep entity of dimension k contains tuples made up of k+1 vertices. These vertices are listed via their global ID numbers. For faces of dimension 1 to d−1, all vertices listed in any of these tuples must also be listed as a vertex of the face as in the previous paragraph. The full-dimensional simplex faces (i.e., the case k=d) are the actual simplices of the mesh.

Two geometric properties of meshes

An important property of a simplex is its aspect ratio. The aspect ratio of a simplex can be defined in several ways, which are all equivalent up to constant multiples. In the QMG package, aspect ratio of a simplex is defined as the ratio of the length of its longest edge divided by its shortest altitude.

Small aspect ratios are desirable because large aspect ratios cause a loss of accuracy in the finite element approximation, and can also lead to condition number problems for the assembled stiffness matrix.

All full-dimensional simplices should to have the correct orientation. Let v0, ..., vd be the vertices of a simplex. The correct orientation is defined as follows. Form the d×d matrix whose ith row is viv0 (a d-vector). The determinant of this matrix must be positive. In two dimensions, this means that the vertices are listed in counterclockwise order. In three dimensions this means that if you curl your right-hand around v0, v1,v2, then your thumb is pointing toward v3.

Ascii format for objects

Both Matlab and Tcl/Tk versions of QMG support Ascii format. In particular, the gm_read and gm_write functions use this format. Furthermore, in Tcl/Tk, conversion to Ascii format is automatic for any operation that causes string format to be released. (See below for more information.)

Ascii format consists of free-form plain text with parentheses as delimiters. Free-form means that linebreaks are usually not significant, except that they act like spaces. Comments are marked with a '#' sign. A comment may start at any position in the line, and is in effect until the end of the current line.

The Ascii format for a brep follows the following grammar. In this grammar, normal-weight text denotes field names and boldface denotes literals. The symbol := indicates substitution for a field name. The vertical bar symbol | means either/or, and curly braces {} indicate optional data. Parentheses when indicated are literals (i.e., parentheses occur in the corresponding place in the actual brep).

The Ascii format for a mesh is:

Matlab internal representation of objects

The Matlab internal representation of objects uses zero-based array addressing. This implemented via a Matlab class called "zba". In a zero-based array, rows and column numbering starts with 0 instead of 1. Many array operations with which you are familiar have been reimplemented for zba's. You can extend the operations available for zba's by adding new routines to the @zba subdirectory. To convert an array to a zba, use the zba function. To convert back, use the double function.

>> z = zba([3,5,7]);
>> z(0)

ans =


>> y = double(z);
>> y(1)

ans =


The user can directly access entries of these objects to examine and modify a brep or mesh. Breps or meshes can also be created directly by the user or with m-files. (This is in contrast to QMG 1.0 and 1.1, in which the object was stored in 'chunk' format and was accessible and modifiable only by using certain accessor functions.)

The zba's in QMG are usually nested, with the outer level being a cell array. Every level of indexing in a nested zba is zero-based.

A brep is represented by a zero-based cell column vector with 6+i entries, where i is the intrinsic dimension of the brep. (This documentation assumes that you are already familiar with subscripting of vectors, matrices, and cell arrays in Matlab.) Say the brep is b. The entries of b are as follows.

The matlab format for a mesh is as follows. A mesh m is a zba cell-vector with 6+i entries, where i is the embedded dimension. The entries as follows.

Two file-formats for meshes and breps can be used in Matlab/QMG. The first is Ascii format: to read a brep or mesh from a file in Ascii format, use gm_read. To write it out to a file, use gm_write. Breps and meshes can also be saved in Matlab's native mat-file format using the save and load commands.

Tcl representation of objects

In Tcl/Tk, breps and meshes are represented internally using C data structures. This data structure is not documented here; refer to the source-code files GeoFmt.h and MshFmt2.h in the QMGROOT/src/tcl directory and the comments in those files.

Breps and meshes are Tcl dual-ported objects, which means that they stay in the C data structures until a command is executed on the object that is unable to directly handle breps or meshes, for instance, the concat function. Then the object is converted to its string representation, which is the Ascii format described above. Converting a large object to Ascii can be very expensive, so you should avoid Tcl operations that cause a conversion unless you need them.

To make it easier to manipulate geometric objects in Tcl, there are also the two functions gm_obj2list and its inverse gm_list2obj. The former is roughly equivalent to converting the object to Ascii format and then replacing all parentheses that occur at outer levels with curly braces so that entries can be indexed and modified using the lindex and lreplace functions of Tcl. (The gm_obj2list function does not actually convert to a string on an intermediate step. Instead, it converts directly to Tcl's internal list representation, which is more efficient.) The gm_list2obj operation inverts this procedure.

Two file-formats for meshes and breps are available in Tcl/QMG. The first is Ascii format. To read a brep or mesh from a file in Ascii format, use gm_read. To write it out to a file, use gm_write. Breps and meshes can also be saved in a binary file format based on the XDR standards. The functions for this purpose are gmxdr_read and gmxdr_write. This XDR format is platform independent because the XDR routines handle byte-order issues.

This documentation is written by Stephen A. Vavasis and is copyright ©1999 by Cornell University. Permission to reproduce this documentation is granted provided this notice remains attached. There is no warranty of any kind on this software or its documentation. See the accompanying file 'copyright' for a full statement of the copyright.

Stephen A. Vavasis, Computer Science Department, Cornell University, Ithaca, NY 14853, vavasis@cs.cornell.edu