# Geometric objects and datatypes in QMG

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.

Breps are produced with the modeling routines, and are input to the mesh generator.

Abstractly, a brep is an acyclic directed graph. Every node in the graph stands for a face of the brep, and the arcs connect faces to their subfaces. Each node has some information associated to it. The graph is leveled: in other words, it is a directed graph whose nodes are partitioned into levels, such that all arcs from level k must go to level k-1 only, for each k.

The bottom level (level 0) is a description of the vertices of the object (for instance, a representation of their coordinates). The next level is the edges of the object, along with pointers to their endpoints at level 0. In general, the kth level contains descriptions of the faces of the object of dimension k, and contains pointers to dimension k-1.

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 programs use 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.
• 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 rendering routines.
Above we mentioned that a vertex of the brep has a representation of its coordinates. In fact, for the sake of uniformity, the coordinates are not stored explicitly. Instead, the system of orthogonal linear equation is stored for a vertex. The coordinates are recovered by solving the equations.

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 gm_addpropval and gmgetf commands, and is also used in the source specification field of simplicial complexes (see below). Except for the fact that the ordering is used to refer to faces, the order of the faces in a level is not significant. Similarly, the order of children in the childlist is unimportant; the order of property-value pairs is unimportant.

## Internal representations of a brep

The software currently has three different representations for breps and simplicial complexes. The first representation is as an internal C++ data structure `Geom_Brep` and `Geom_SimpComplex`, which is not documented here. The C++ data structures are created while the routines are running, but they are deleted as soon as the routines finish so the user never accesses them directly. The mesh generator has a C++ data structure for breps `Mg_Brep` different from the rest of the routines.

The second representation is called the chunk representation, because in this representation the brep 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. Most of the QMG routines take chunk arguments as inputs and/or return them as outputs.

The actual entries of these arrays are meaningless to Matlab, and the user should not attempt to directly access or modify individual entries of a chunk argument (the routines may throw a segment-violation if presented with an erroneous chunk argument). Chunk arguments may be saved in files using the Matlab `save` command, but they should not be saved with `save -ascii` command.

It is permissible to append entries at the end of a chunk array---the unpacking routine will ignore these additional entries.

The third representation of a brep or simplicial complex is as an Ascii string. This is the only format that can be directly manipulated by the user. 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.

There is an accessor routine `gmget` to get information from a chunk format brep or simplicial complex. The routine `gmgetf` returns specific information about an individual brep face. The only modification routine for chunk breps is `gm_addpropval`, which adds or modifies a property/value pair for a face of a brep.

There are no low-level constructor routines for chunk breps. (But there are high-level geometric constructors, like constructing a polygon and so on.) The only way 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 `gmmouse.m` for a simple example of this, or `gmcone.m` for a more complex example.

## 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.

There are two kinds of internal boundaries supported by the QMG package: MTL internal boundaries and SL internal boundaries.

MTL stands for ``multiple top-level.'' This means that the top level of the brep has multiple entries. (``Top-level'' refers to the top level of the abstract acyclic graph representation described above.) The opposite of MTL is STL. In the square example of a brep described earlier, we could make a second square at the top level that shares a common edge, say e_3 with the original square. To accomplish this, we need two additional vertices v_5 and v_6, three new edges e_5=(v4,v5), e_6=(v3,v6), and e7=(v5,v6), and one additional top-level brep whose children are (e3,e5,e6,e7). Thus, there are two distinct squares at the top level of the brep which have common descendants. Now e3 acts as an internal boundary for the overall ensemble of breps at the top level. MTL internal boundaries are constructed with the `gmsplit` routine.

An SL internal boundary corresponds to a ``slit.'' An SL internal boundary behaves in most 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 are not stored as double entries in the childlist but are stored as a separate field of the face. SL internal boundaries are 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. The above example of two squares could be represented as follows At the top level would be one six-sided polygon whose children are (e1,e2,e4,e5,e6,e7) and has (e3) listed 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 below. 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 now 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 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, but this is not currently supported.

## Correctness of breps

A brep must satisfy certain correctness properties. Here is a partial list. There is currently no program to verify the correctness of a brep.
• The system of linear equations associated with each face must have orthonormal rows, up to double-precision accuracy.
• 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 (this must hold to double-precision accuracy). (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 square brep above, v1 occurs twice as a grandchild of square, once as a child of e1 and once as a child of e4.)
• If f is a face of level 1, then it must have an even number of children.
• A face of level 0 has no children and no SL internal boundaries.
• A face of level 1 or higher has at least two children.
• Coincident faces are not allowed.
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 shoot a randomly-chosen ray R from p to infinity lying in the affine hull of f, the number of children of f that R meets is odd. Notice that this definition is recursive, because we have to already know the geometric set associated with the children.

This definition implies that the brep faces are always bounded, which is the case for the current system. There is no way to represent unbounded sets.

For example, in the case of a one-dimensional face, the above properties imply that it has an even number of boundary vertices, and all its boundary vertices are colinear. The ray-shooting definition of its geometric set is equivalent to the following simpler definition. The geometric set is the union of the line segments marked off by consecutive pairs of points along the line. Most commonly a one-dimensional face has exactly two children, in which case its geometric set is a single segment. There is no way to represent rays or infinite lines in the current version of QMG.

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.
Again, these properties must be understood recursively; it makes no sense to apply these rules unless we already know the child faces are correct.

The mesh generator requires certain additional properties of the breps it triangulates.

• The brep must be full-dimensional meaning that its embedded dimension and intrinsic dimension are equal.
• There must not be a vertex whose deletion would locally disconnect the brep (visualize an hourglass shape); this confuses the current version of connected-component testing routine.
• A child can appear at most once in the childlist of a face. Therefore, SL internal boundaries cannot actually be represented as repeated children.
• Every face must have a path to a top-level face. In other words, there cannot be a vertex in the brep that does not occur in any 1-dimensional face; there cannot be a 1-dimensional face that does not occur in any 2-dimensional face, and so on.
The current modeling routines cannot generate a brep that violates the third or fourth points on this list.

## 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 the current version of 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.

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 the array are double-precision 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 indices start at 0 so you may have to increment them by 1 if you retrieve them with `gmget(scomplex,'Simplices')` in Matlab.

The geometric set associated with a simplex is defined to be the convex hull of its vertices.

The third array is a list of specifications of a brep face in the in the brep from which the complex was generated (the ``source specification''). This specification consists of two integers; the first integer is the level of the face and the second integer is the position within the level (numbered 0,1,2, etc.)

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.

The correctness properties of a simplicial complex are:

• 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.
• Each vertex in the simplicial complex must appear in at least one simplex.
• 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.
The last 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.

• The union of the geometric sets associated with the simplices must equal the geometric set defined by the union of the top-level 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.

## 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. 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 all of 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 linear_equations property_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.
• linear_equations := < numrows numcols (entry1 ... entryN) >.
The field numrows is an integer and must be equal to d-k where d is the embedded dimension and k is the face dimension. The value of numcols must be equal to d+1. The number of entries N must be (d-k)(d+1). The entries of the linear equations are in row-major order, and the the last entry of each row is the right-hand side entry for that row.
• property_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.
• child_list := (child1 ... childN).
This list contains names of faces at the previous level.
• internal_boundary list := (ib1 ... ibN).
This list contains the names of faces at the previous level. These faces are SL internal boundaries.
• simp_complex_object := < intrinsic_dim embedded_dim (coord1 ... coordN) (annot1 ... annotP) (trivtx1 ... trivtxM)>.
Entries intrinsic_dim and embedded_dim are both integers and were described above.
List entries coord1 ... coordN are double-precision 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 annot1 ... annotP are annotations for the vertices. Currently only one annotation format is supported, namely an annotation of the form d/k where (d,k) specifies the face of the brep in which the vertex is contained. 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.

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

geom.html,v 1.1.1.1 1995/05/05 01:15:54 vavasis Exp

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