Notes on the QMG Source Code

Much of the QMG package is written in C++. The purpose of this page is to give a brief overview of the source code in case the user wishes to modify it. This page assumes familiarity with C++. The source code is in subdirectories of $QMG_ROOT/src. The subdirectories are as follows: Some commands span several directories and files. The most complicated example is probably gmviz. Invoking gmviz first executes gmviz.m or gmviz.tcl depending on the scripting language. These in turn invoke invoke gm_viz, a C++ routine whose source file is in $QMG_ROOT/src/model. This routine calls the constructor for Qmg_Graphic_Engine, a class declared in $QMG_ROOT/src/common/render.h. This in turn may create a class Qmg_Graphic_Engine_Local, which is defined by render_local.h either in the $QMG_ROOT/src/tcl or $QMG_ROOT/src/matlab subdirectory. Finally, the local graphics engine routines in render_local.cpp in the same directory invoke an mfile or a tcl file to actually carry out the plotting.

General naming conventions used in the source code are as follows. Almost all names with global scope are prefixed as follows. Global constants are in all-caps and prefixed with QMG. Global type names (include class names) are capitalized word by word and are prefixed with Qmg. Finally, global functions and global static variables are in lowercase and are prefixed with "qmg."

The main exception to the prefix convention are global macros, which are not prefixed. Global macros can be discerned because their first word is in all-caps and their remaining words are in lower case. For instace, FOR_each_child_of_face is a global macro for looping over the child faces of a face of a brep.

The C++ source files that are invoked directly by the scripting language (Matlab or Tcl/Tk) all begin with the letters "gm" and are all in the meshgen and model subdirectories. These are C++ programs that can be linked to either Matlab or Tcl/Tk. Because Matlab and Tcl/Tk use somewhat different linking conventions, these files are full of macros. The macros are defined by wrapper.h, which is a source file in the matlab and tcl source directories. Depending on your choice of scripting language, the Makefile will cause one of these two versions of wrapper.h to be included with your gm files. In this way the same C++ source file can link to either scripting language.

For example, one macro used in many of these gm routines is VERIFY_num_in_arg_min, which takes a single integer argument. The purpose this macro is to verify that the number of input arguments to the gm function is at least as large as the specified integer. In matlab, this expands to a comparison with nrhs, an argument to a mexFunction. In Tcl/Tk this expands to a comparison to argc-1, which is an argument to a Tcl/Tk user-written routine. Other macros convert input arguments to internal C++ formats (these macros all begin with PARSE), and finally there are macros for setting the return values passed back to the scripting language such as RETURNvalue_brep, which passes a brep back to the scripting language.

Perhaps the most important C++ class in the package is Qmg_Brep, which is the class for breps. This is class is an interface class, i.e., it has no data in it. It defines many low-level accessor functions for breps, like face_children, which takes a facespec and returns the children for that facespec as an array of integers. These low-level accessors are pure virtual functions. There are no member functions for modifying breps in this base class. The class Qmg_Brep also includes some non-virtual functions like "face_contains_point_retry", which is a routine to determine whether a face of a brep contains a given point (specified by its coordinates). The "retry" part means to retry the test (which involves some randomization) until it succeeds. This routine gets information about the brep through the lower-level pure-virtual accessor functions like face_childlist, face_eq (the affine hull coefficient matrix), face_rhs (the right-hand side of affine equations), face_coord (the point in the relative interior of the face).

There are three concrete classes derived from Qmg_Brep, namely, Qmg_Brep_Unpacked_1, Qmg_Brep_Unpacked_2, and Qmg_Brep_Packed_2. (I had originally also planned on a Qmg_Brep_Packed_1, but this turned out to be unneeded). The suffix 1 means that the brep has all its relevant information stored in its data structure. Most breps occurring in QMG are of this type. There is a base class for type 1 breps which is Qmg_Brep_1.

Type 2 breps are used only in the quadtree/octree mesh generator for storing content breps. In the quadtree/octree mesh generator, each active box b has a brep called its "content" which is the intersection of the original input brep with ex(b), a slightly expanded version of the box. In fact, the content does not store the true intersection; it stores only those faces of the intersection that pass through the interior of the box. The base class is Qmg_Brep_2. In a type 2 brep, there is no system of equations or right-hand side. Instead, each face stores a "sourcespec", which is a face spec of a face in the input brep. The system of equations can be looked up there, since each face of the content is some portion of a face of the input brep. There are additional tables of data stored with sourcespecs so that intersection problems and least-squares problems can be solved more quickly.

The words "packed" and "unpacked" indicate how the brep is layed out in memory. There are two intermediate base classes, Qmg_Brep_Packed and Qmg_Brep_Unpacked. A packed brep occupies a contiguous block of storage. (Packed breps are not the same as chunk format breps because packed breps are C++ data structures with pointers and are derived from Qmg_Brep, whereas chunk-format breps are encoded data structures that must be unpacked to realign all the pointers. But the routine for making packed breps shares some common subroutines with the routine for making chunk format breps.) The reason for having packed breps is that they lead to an improvement in the performance of the quadtree/octree mesh generator: there are fewer calls to "new" and "delete", and also fewer page faults. The contiguous memory allocation is accomplished with some pointer-casting tricks that are not "standard" C++.

An unpacked brep can be modified with non-constant member functions like add_face (to add a new face) and face_coord_nonconst (to access the coordinate entries of the point in the relative interior of the face in a non-constant fashion).

Most of the breps occurring in routines are Qmg_Brep_Unpacked_1. However, many routines take as an argument const Qmg_Brep&, since most routines do not need to modify the breps passed to them as arguments.

The brep classes use multiple inheritance; for instance, Qmg_Brep_Unpacked_1 has Qmg_Brep as a virtual base class, and then Qmg_Brep_Unpacked and Qmg_Brep_1 as intermediate base classes.

Another major class is Qmg_SimpComplex. This is also an interface class with no data. It provides low-level accessor functions to simplicial complexes such as a routine to get a vertex coordinate. There is one concrete class derived from Qmg_SimpComplex, which is Qmg_SimpComplex_Unpacked, which has member functions to update a simplicial complex.

The two classes Qmg_SimpComplex and Qmg_Brep are both derived from Qmg_Obj, which provides some basic functionality like determining the intrinsic dimension, embedded dimension, and converting in and out of chunk format.

There are many low-level classes important to QMG. For instance, there is are several array classes all derived from the base array class Qmg_Const_Array<T>, where T is a datatype. This base class allows read-only access to the arrays entries via operator[]. Derived from this is Qmg_Array<T>, which allows both read and write access via operator[]. From Qmg_Array<T> we have more classes derived, like Qmg_Growing_Array<T>, which is an array with a "resize" member function that allows it to be resized dynamically. There is also a Qmg_Resizable_Array<T> that can be resized. Class Qmg_Resizable_Array requires the maximum size to be specified at construction time, whereas Qmg_Growing_Array<T> occupies more memory as needed.

There is also a stack class, Qmg_Stack<T> and several classes derived from this class. There is a association-list class, built on top of Tcl's hash tables. There is an indexed-list data structure Qmg_IndexedList<D,K> which takes two types, a data type and a key type. The user inserts items in this data structure, then calls a member "sort". After "sort" is called, the user can then look up the items in the object (but can no longer do any insertions). This data structure uses merge-sort for sorting, and the merge-sort routine will actually merge together (user a user-provided member function of the data-type called "merge") two data items with the same key.

The quadtree/octree mesh generator defines many additional classes like a class for boxes, Qmg_Box, which has derived from it Qmg_ActiveBox, which in turn is specialized to Qmg_SeparationBox and Qmg_AlignmentBox.

Some other conventions used in the source code are as follows. Variable di often stands for the embedded dimension, and gdim for the intrinsic dimension. Variables called fspec, new_fspec, subfspec, etc are usually face-specs, that is, ordered pairs of integers (facedim, faceind) that index a face of a brep. Variable tol is always the current absolute tolerance ("absolute" means that the tolerance lies between 0 and 1), scfac is usually the scale factor of the brep under consideration, and scaled_tol is the product of tol and scfac and is the tolerance relative to the size of the current brep. The variable names in this paragraph are all used in local scopes only.

The routine qmg_error is called when there is an error, and the routine qmg_user_error is called when there is an error that is probably caused by an incorrect argument to a routine. These routines do not throw exceptions because we do not use the exception mechanism in C++. However, the QMG code tries to check for exceptional conditions by frequently calling qmg_error_status() to see if an error has occurred, and if so, returning to the caller.

The makefiles are organized as follows. There is one makefile for each four-tuple of platform, operating system, compiler, scripting language. These makefiles have some basic definitions, but most of the makefiles actual content is located in the various src subdirectories. For instance, in the src/meshgen subdirectory, there are four files called make_pre_o, make_post_o, make_pre_e, make_post_e. The files make_pre_o and make_post_o are for making .o/.obj files; "pre" means that this file should be included before the first main target of the makefile (and hence the file consists of all definitions and declarations but no targets), and "post" means that the file has targets and hence should be included after the first main target. The files make_pre_e and make_post_e are for making executables (Matlab only).

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.

Back to the QMG1.1 home page.

Stephen A. Vavasis, Computer Science Department, Cornell University, Ithaca, NY 14853,