The QMG package supports two datatypes: breps and simplicial complexes.

## Overview of breps

A brep is a geometric object that is specified by its boundary faces (``brep'' is short for ``boundary representation''). I pronounce ``brep'' like ``bee-rep.'' In the current version of the software, all breps must have flat boundaries, in other words, every element of the boundary must be a subset of a linear affine space. Future versions of QMG might support curved objects.

Breps are produced with the modeling routines, and are input to the mesh generator. They can also be exported to and imported from external packages if they are saved in the correct file format.

Abstractly, a brep is an acyclic directed graph. Every node in the graph stands for a face of the brep. The term face refers to a vertex, edge, facet, or higher dimensional bounding face of the brep. In addition, the interior of the brep is also considered a face. Each of these nodes has some information associated to it; for instance, vertices have their space coordinates associated with them. The arcs of the directed graph indicate boundary relationships. For example, an edge that is bounded by two vertices has arcs to those two vertices to indicate the bounding relation. A facet has arcs to the edges that act as its boundary. In general, a face of dimension k has boundary faces of dimension k-1. A face may also have "internal boundary faces" of dimension k-1 or any lower dimension; internal boundaries are discussed below.

A brep has two integers associated with it: its embedded dimension, which is the dimension of the space it lies in, and its intrinsic dimension, which is the dimension of the object itself. For instance, a square sitting in the z-coordinate plane of 3-space would have intrinsic dimension = 2 and embedded dimension = 3. The QMG functions follow the convention that the empty set has intrinsic dimension = -1.

Each face of the brep (node in the graph) has the following items associated with it:

• A system of linear equations defining the affine hull of the face. The coefficient matrix of these equations is (d-k) by d, where d is the embedded dimension and k is the dimension of the face, and the right-hand side is a d-k vector. This system of equations is required to have orthonormal rows. (In other words, if A is the coefficient matrix, then A*A' should be the identity matrix.)
• The coordinates of a point lying in the relative interior of the face.
• Children of the face, that is, pointers to faces of dimension one lower that form the boundary of the face under consideration.
• SL internal boundary elements of the face. See below.
• A list of property-value pairs, which are used by some of routines in QMG. For instance, a face can have a property `color`, which is used by the graphics routines.
In the Ascii input format, the user can omit the linear equations and the coordinate of the point in the face, in which case QMG tries to deduce this information. Other routines, including `gm_poly` and the routine for reading OFF format require as input only a subset of the above information, and they deduce the rest.

The brep for the square displayed above would have four faces of level 0, four faces of level 1, and one face of level 2. Suppose we refer to the vertex as v1,..,v4 in clockwise order, and the edges as e1,....,e4. Then the children of e1 are (v1,v2). The children of e2 are (v2,v3). The children of e3 are (v3,v4), and the children of e4 are (v1,v4). The square itself has (e1,e2,e3,e4) as children.

Internally, the faces of a brep are numbered consecutively 0, 1, 2, etc. on each level. This internal numbering is used by the many functions including `gm_addpropval` and `gmgetf`. In this documentation and in the code, we use the term "facespec" to denote the specification of a face of a brep as an ordered pair (k,i), where k is the dimension of the face and i is this index in the consecutive numbering. Facespecs are used to label vertices simplicial complexes (see below).

Except for the fact that the ordering induces this numbering, the order of the faces in a level is not significant. Similarly, the order of children in the childlist is unimportant. In particular, it is not necessary to list the edges of facets in any kind of sequential order. The order of property-value pairs is unimportant.

## 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. A simplicial complex is specified by three arrays. The first array is the list of vertex coordinates. This array has a number of rows equal to the number of vertices, and a number of columns equal to the embedded dimension of the complex. The entries in this array are floating point numbers.

The second array is a list of simplices. The number of rows in this array is the number of simplices and the number of columns is the intrinsic dimension plus one. The entries of this array are nonnegative integers that refer to the vertices (i.e., to row numbers in the coordinate array). These vertex are numbered starting at 0 so you may have to increment them by 1 if you retrieve them with `gmget(scomplex,'Simplices')` in Matlab, since Matlab numbering always starts with 1.

The third array is a list of facespecs. There is one facespec for each vertex of the simplicial complex. A vertex's facespec is its source specification: it indexes the lowest-dimensional brep face in the brep from which the mesh was generated. These labels are necessary for finite element analysis, because the boundary conditions are stored in the brep faces, and thus the finite element solver must know which face owns each vertex of the mesh.

Notice that this array specifies the brep face but does not actually specify which brep gave rise to the mesh generator. In the current version of QMG it is the user's responsibility to keep track of which brep gave rise to which simplicial complex. This is a known difficulty with the QMG data structures that may be addressed in future versions.

## Representations of objects

The software currently has three different representations for breps and simplicial complexes. The first representation is as internal C++ data structures `Qmg_Brep` and `Qmg_SimpComplex`, which are documented in the source code documentation. The C++ data structures are created while the functions are running, but they are deleted as soon as the functions finish so the user never accesses them directly.

The second representation is called the chunk representation, because in this representation the brep or simplicial complex occupies a contiguous chunk of memory. The chunk representation has been designed so that it can be easily unpacked into a C++ data structure and vice versa. The chunks are stored as Matlab arrays or as Tcl/Tk strings. (In the Tcl/Tk string version, the chunk is first expanded into two printing characters per byte. This is because Tcl/Tk cannot handle strings with embedded bytes equal to 0.) Most QMG functions that take breps or simplicial complexes as arguments expect the arguments in chunk format.

The actual entries of these arrays are meaningless to Matlab and Tcl/Tk, and the user should not attempt to directly access or modify individual entries of a chunk argument. (QMG routines do not verify the correctness of a chunk argument before processing it. Therefore, they may throw a segment-violation/general protection fault if an erroneous chunk argument is processed). Chunk arguments may be saved in files using the Matlab `save` command, but they should not be saved with `save -ascii` command. If chunk arguments are saved in a file, the file should not be shared between different architectures because the encoding and decoding of the chunk arguments is processor and compiler dependent.

The third representation of a brep or simplicial complex is as an Ascii string. QMG1.1 supports several different such formats, but there is one in particular that we refer to as "Ascii" format documented in this page. The other ones are for external interfaces.

The routine for conversion ascii-to-chunk is called `gm_in` and the inverse conversion is called `gm_out`. See below for the details on the Ascii representation.

Other formats for inputing and outputing breps and simplicial complexes include

There are many ways to create breps, access face information, and modify breps; see information about low-level brep constructors, high-level brep constructors, a low-level simplicial complex constructor `gm_simpcomplex` or mesh generation functions for constructing simplicial complex. See also information about `accessors.`

Another method in the current system to construct a brep from scratch is to write a string with an ascii-format brep and then call `gm_in` on the string. See the listing of `gmcone.m/gmcone.tcl` for an example of this technique. The advantage of this technique is that gm_in can deduce information about affine hulls and points in the relative interior if it is not specified in the string.

## Internal boundaries in breps

Brep faces are defined by their children, which act as boundaries. 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.

Note that ``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.

Here is a simple example of an object with an internal boundary:

There are two kinds of internal boundaries supported by the QMG package: MTL internal boundaries and SL internal boundaries. The above figure could be of either kind.

MTL stands for ``multiple top-level.'' This means that the top level of the brep has multiple entries, i.e., the brep has more than one full-dimensional face. (``Top-level'' refers to the top level of the abstract acyclic graph representation described above.) The following graph indicates abstractly how the above double-square could be realized as an MTL domain.

The point is that each of the two top level entries is a valid two-dimensional face (each is a square) but they happen to share a subface.

MTL internal boundaries are constructed with the `gmsplit` routine.

An SL internal boundary corresponds to a ``slit.'' SL internal boundaries are stored separately from the childlist of the object.

If an SL internal boundary of a k-face happens to have dimension k-1, then it behaves in all contexts like a child in the childlist of a face that is repeated twice (and hence acts like a slit). In fact, SL internal boundaries of dimension k-1 can be stored in this fashion (as children that occur twice in the childlist).

Here is how the above double-square object could be represented as an object with an SL internal boundary by repeating entries in the child list.

SL internal boundaries can be created with the `gmsubtract` routine.

From the geometric point of view, SL internal boundaries are more general than MTL internal boundaries, i.e., any internal boundary that can be described as an MTL internal boundary can also be described as an SL internal boundary. SL internal boundaries are more general because they can be used for internal boundaries that cut only partway through the domain.

Even though SL boundaries are more general, MTL internal boundaries are preferable in the case that the internal boundaries represent demarcations between different zones of the domain. In the presence of MTL internal boundaries, the mesh generator will label interior nodes that it generates with the top-level face in which they lie (i.e., the label indicates which ``side'' of the MTL internal boundary the node lies on). See the description of source specifications of simplicial complexes above. The finite element program can take advantage of the labels during matrix assembly because it can use different functions to compute conductivity and source terms for the two sides of the MTL internal boundary.

In the case of an SL boundary, there is no concept of one ``side'' of the internal boundary versus the other since an SL boundary may cut only partway through the domain. Thus, all interior nodes have the same label. The conductivities can still vary as an SL internal boundary is crossed, but in this case the function that computes conductivities will have to use the position of the node in some kind of geometric computation of its own to figure out the conductivity for each mesh element.

The two types of internal boundaries, MTL and SL, can be freely mixed. In addition, an SL internal boundary does not actually have to be inside the face that contains it (although it has to be in the right affine hull). There is generally not much use for internal boundaries exterior to the face, and some routines will behave oddly for such an object, but it is a legal feature of QMG in order to allow the complement operation to take complements of objects with internal boundaries.

The mesh generator will produce a single ``layer'' of nodes along either an SL or MTL internal boundary. In some applications a double-layer of nodes is desirable. It is possible to produce a double layer of nodes along an SL boundary with `gmdoubleib`.

## Correctness of breps

A brep must satisfy certain correctness properties. Here is a partial list. The program `gmcheckbrep` checks all these properties.
• The system of linear equations associated with each face must have orthonormal rows, up to current tolerance.
• If f is a face with subfaces f1,f2,...,fk then the affine sets defined by the linear equations for each fi must lie in the affine set defined the equations of f, accurate to the current tolerance. (Subfaces are children and SL internal boundaries.)
• If f is a face of level k with k>=2, then when we count its grandchildren with multiplicities, each grandchild must occur an even number of times. (For example, in the MTL example above, v1 occurs twice as a grandchild of s1: once as a child of e1 and once as a child of e4.)
• The specified point in the relative interior must be in the affine hull of the face and not lie in any of the subfaces.
• A face of level 0 has no children and no SL internal boundaries.
• The specified point in the relative interior must lie in the specified affine hull of the face.
We can now define the geometric set associated with a face f of dimension >= 1. It is the set of points p such that either p is on a child face of f, or p has the following property. When we draw the segment S from p to the specified point in the relative interior, lying in the affine hull of f, the number of children of f that S meets is even. (Degenerate cases when the ray hits a grandchild face are handled with a different rule.) Notice that this definition is recursive, because we have to already know the geometric set associated with the children.

These definitions allow unbounded breps. For instance, a ray in QMG can be represented as a 1-dimensional object with a single child (the starting point of the ray). An object of dimension 1 or higher with no child faces is an infinite affine hull.

The remaining correctness properties of breps are:

• Two brep faces at level k can intersect only in a common subface.
• Every point of an SL internal boundary of face f must be contained by f or by the complement of f (and must lie in the affine hull as mentioned above).
Again, these properties must be understood recursively; it makes no sense to apply these rules unless we already know the child faces are correct.

For mesh generation, some additional correctness properties are needed.

• If the mesh generator is called for faces of dimension d, then all faces of dimension d must be finite.
• For the quadtree/octree mesh generator, the brep must be full-dimensional (i.e., its intrinsic and embedded dimensions must be equal).
• If face f is a bounding (child) face of face g, then face g must all lie on the same "side" of face f. In general, one expects this property to be true, but it is possible to construct counterexamples involving internal boundaries. Currently the mesh generator does not always detect this error condition.

The correctness properties of a simplicial complex are as follows. The geometric set associated with a simplex is defined to be the convex hull of its vertices.

• The vertices of each simplex must be affinely independent.
• Duplicates are not allowed, i.e., there cannot be two simplices with the same set of vertices.
• If two simplices have a nonempty intersection (that is, there geometric sets have a nonempty intersection), their intersection must be the convex hull of the vertices they have in common.
• Each simplex must have the correct orientation.
The third condition appears difficult to check; the obvious algorithm for testing it requires quadratic time. Since the mesh generator often produces enormous meshes, quadratic time is not acceptable.

If a simplicial complex is specified in conjunction with a brep (i.e., it is a putative triangulation of the brep), it must satisfy the following additional correctness conditions. Suppose it is a triangulation of the k-dimensional faces of the brep.

• The union of the geometric sets associated with the simplices must equal the geometric set defined by the union of the k-dimensional faces of the brep.
• The labeling must correct, i.e., if a simplicial complex vertex is labeled (d,i) then it must lie in face (d,i) of the brep (accurate to double precision) and it must not lie in any proper subface of (d,i).
Paradoxically, it appears to be easier to test correctness of a simplicial complex in conjunction with a brep than to test the correctness of the complex in isolation. In particular, we conjecture that the routine `gmchecktri` tests all of these correctness properties in linear time (that routine assumes correctness of the brep) with its list of tests. We do not have a proof of this conjecture, but we do not know of any counterexamples.

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 is defined as the ratio of the length of the longest edge of the simplex 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.

## Simplex orientation

In QMG 1.1, all simplices are required to have the correct orientation. Let v0,...,vd be the vertices of a simplex. If the simplex is full dimensional, i.e., the embedded space is R^d, then "correct orientation" is defined as follows. Form the d-by-d matrix whose ith row is vi-v0 (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.

If the simplicial complex is not full-dimensional, the rules are as follows. Suppose the simplex lies an a brep face F whose affine hull is given by Ax=b. Note that A is not uniquely determined, so any A is acceptable, but we require that every simplex on a given face must choose the same A matrix.

In the case that the brep face is one lower dimension than d, A has one row. If this face is a bounding (child) face of exactly one d-dimensional brep face of the brep, then we additionally stipulate that the row of A is an outward-pointing normal to the face.

In any case, once A is selected for the brep face, the orientation rule is that the matrix formed by appending to the end of A the rows v1-v0,...,vd-v0 (which now will be a square matrix) must have positive determinant.

## Ascii representation details

The Ascii representation is a string. Some of the entries in the string are user-specified names. These names must avoid the following special characters: <,>,(,),{,},",; and any whitespace character. It is suggested that the user stick to letters, digits and underscores. Colon is also used. Whitespace characters are used as separators for items in crossproducts and lists.

The delimiters for crossproducts are <...>. The delimiters for a list are (...). That is, the sequence of items enclosed in <...> are of possibly different types, and the type of each entry is known in advance from its position in the sequence. The items enclosed in (...) are all of the same type, and the number of items enclosed in (...) is not necessarily determined in advance syntactically.

The idea of representing a brep as recursively nested crossproducts was suggested by S. Allen.

The rules for an Ascii representation may be defined by the following production rules.

• typed_object := < type_name geometric_object >.
Entry type_name may be either `brep` or `simpcomplex`.
• geometric_object := brep_object | simpcomplex_object.
The type_name field determines which type of object should appear.
• brep_object := < intrinsic_dim embedded_dim level_0_spec>.
The intrinsic_dim and embedded_dim entries are integers and their meaning was described above.
• level_k_spec := < (level_k_face1 ... level_k_faceN) level_k+1_spec > | ` nil `.
Thus, the level_k_spec consists of a parenthesized list of face specifications followed by the level k+1 spec. This means the levels are recursively nested inside lower-dimensional levels. The keyword `nil` terminates the recursion; the depth of the nesting before `nil` is encountered must agree with the intrinsic_dim specification above.
• level_k_face := < name property_val_list child_list internal_boundary_list >.
The name is a text string that is used so that the face can be referred to on the next level. The names are not preserved when the Ascii representation is converted to a chunk representation. In other words, if you convert from ascii to chunk back to ascii, the original names of the faces will not appear in the new ascii format.
• property_val_list:= (<property1 value1> ... <propertyN valueN>).
The number of properties N may be zero. Each property is a text string and must obey the above rules. The user is free to define new properties. A value can be a text string or a compound object such as a list or crossproduct.
• There are three distinguished properties that specify the geometry of the brep; they are affine_coef, which defines the coefficient matrix of the affine hull of the face, affine_rhs, which defines the right-hand side of the affine hull of the face, and point, which defines the point in the relative interior.

For common cases, the user never has to specify either the affine_rhs or affine_coef property-value pairs because `gm_in` will deduce them automatically by looking at the vertices of the face. The exception is when the face is infinite, in which case there may not be enough vertices to determine the affine hull. Similarly, the user generally does not have to specify the `point` property either---as long as the face is finite, QMG can automatically deduce the point.

The exception to this latter rule is 0-dimensional faces, which must be accompanied either by a `point` property or a `affine_coef` and `affine_rhs` property, otherwise QMG cannot figure out the position of the vertex.

• The formats for these special property-value pairs are:
• <point (c1 ... cd)> specifies the point in the relative interior of the face (which, in the case of a vertex, is the coordinates of the vertex itself); the number of entries d must be the embedded dimension of the brep.
• <affine_coef (a1 ... ap)> specifies the coefficient matrix of the affine hull of the face. The number of entries p must be equal to (d-k)*d, where d is the embedded dimension and k is the dimension of the face. The entries are in row major order, meaning that a1,...,ad represents the first row of the matrix and so on. The rows must be orthonormal.
• <affine_rhs (r1...rm)> specifies the right-hand side of the affine hull of the face. The number of entries m must be equal to d-k, where d is the embedded dimension and k is the dimension of the face.
• child_list := (child1 ... childN).
This list contains names of faces at the immediately previous level.
• internal_boundary list := (ib1 ... ibN).
This list contains the names of faces from any previous level. These faces are SL internal boundaries.
• simp_complex_object := < intrinsic_dim embedded_dim (coord1 ... coordN) (sourcespec1 ... sourcespecP) (trivtx1 ... trivtxM)>.
Entries intrinsic_dim and embedded_dim are both integers and were described above.
List entries coord1 ... coordN are floating point numbers. The number of entries here N must be equal to embedded_dim multiplied by the number of vertices. Each vertex is defined by embedded_dim consecutive entries in this list.
List entries sourcespec1 ... sourcespecP are the annotations for the vertices that describe which brep face contains the vertex. The sourcespec has the format k:l, where k is the dimension of the face and l is the index. List trivtx1 .. trivtxM contains M nonnegative integers, where M is the product of the number of triangles and (intrinsic_dim + 1). Every consecutive (intrinsic_dim+1) integers of this list specify one simplex; these integers are indices into the vertex table.

If you already have a polyhedral brep that you want to make compatible with QMG, you have to change it to a format readable by QMG. The first question is whether you really need the full-blown Ascii format, or whether you can get by with something simpler. In two dimensions an easier way to create a brep is `gm_poly`. In three dimensions the OFF format is easier to work with. But these other formats do not support internal boundaries or infinite breps, and OFF does not support facets with holes (facets bounded by multiple "loops"). If you do not need any of these features, then you can use one of these simplified formats.

If you need the full power of the Ascii format, then you will need to prepare a list of vertices, edges, and facets of your object. For the vertices you need coordinates; for the edges you need to know endpoints (as specified by the names or indexes of the vertices), and for facets you need to know the bounding edges.

Here is an example of the square at the beginning of this document written in Ascii format. ``` ```

``````< brep
< 2 2
< (
< v1 (< point (0.0 0.0) >) () () >
< v2 (< point (1.0 0.0) >) () () >
< v3 (< point (1.0 1.0) >) () () >
< v4 (< point (0.0 1.0) >) () () >
)
< (
< e1 () (v1 v2) () >
< e2 () (v2 v3) () >
< e3 () (v3 v4) () >
< e4 () (v1 v4) () >
)
< (
< s1 () (e1 e2 e3 e4) () >
) nil >
>
>
>
>
``````
``` ``` The line breaks are not significant. As mentioned above, the names used in this brep, v1, v2, etc. are fairly arbitrary strings and are not stored in the chunk or C++ form of the brep. They are only used by `gm_in` as symbolic tags to link the faces to their children correctly.

The following is the Ascii format of a simplicial complex that is a triangulation of the above brep using two triangles. ``` ```

``````<simpcomplex
< 2 2
(
1.0 0.0
0.0 0.0
0.0 1.0
1.0 1.0
)
( 0:1 0:0 0:3 0:2)
( 0 3 1
1 3 2
)
>
>
``````
``` ```

This documentation is written by Stephen A. Vavasis and is copyright (c) 1996 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