Package FL.MESH (Femlisp User Manual)

7.12 Package FL.MESH

This module contains the definitions of meshes and routines for mesh management. The meshes allowed in FEMLISP are more general than those of most other software for solving PDEs. In FEMLISP, both mesh, domain and problem definitions are defined over an underlying abstraction, the so-called <skeleton>. A <skeleton> captures the mathematical idea of a "cell complex" which builds a topological space by mapping from standard cells <cell>. Now, a <skeleton> can be seen as mapping the cells of such a cell complex to arbitrary values. Then, a <domain> is a <skeleton> where each cell (which we call "patch" in this case) is mapped to geometric properties, and a <mesh> is a <skeleton> where each cell is mapped to the patch to which it belongs.

The basic entities are the class <cell>, the subclass <simplex> which in turn contains subclasses for arbitrarily dimensional simplices generated on demand, and the subclass <product-cell> containing arbitrary products of simplices, e.g. square or cube.

Meshes can be refined either uniformly or locally using the Freudenthal algorithm as presented in JBey_2000a and generalized to product elements. When local refinement is used, hanging nodes may occur. In contrast to most other finite element software, in FEMLISP the difference of refinement levels of adjacent cells may be arbitrarily large. Up to now, anisotropic refinement of product cells has not yet been implemented.

Variable: *REFERENCE-VERTEX*: The reference vertex.

Class: <BOUNDARY-CELL>

This cell is only fuzzily defined. Its use is mostly for defining domains by their boundary. The slot midpoint can be useful for the graphical output of the cell, the slot holes contains a list of points lying inside holes. This is intended as help for triangulation programs.

Superclasses: <CELL-WITH-BOUNDARY>

Direct slots:

DIMENSION: Self-explanatory.
MIDPOINT: Self-explanatory.
HOLES: Self-explanatory.

Class: <CELL>: The basic cell class.

Class: <DOMAIN>

A <domain> is a special <skeleton>. We call its cells patches, and the properties of a patch carries geometric information. Properties supported up to now are:

IDENTIFIED: list of identified patches
EXTENSION: extender
METRIC: metric tensor function
VOLUME: volume function

Metric and volume should be functions depending on keyword arguments like :LOCAL and :GLOBAL and allowing arbitrary other keys.

Superclasses: <SKELETON> PROPERTY-MIXIN

Direct slots:

CLASSIFIERS: A list of functions of two arguments -patch and classifications so far- which are called from the right to classify the patch.

Class: <HIERARCHICAL-MESH>

Hierarchical-meshes are those meshes which will be used most often, because they remember the refinement history and therefore allow for refinement and coarsening. The slot levels is an array of skeletons containing the cells for different levels.

Superclasses: <MESH>

Direct slots:

LEVELS: Self-explanatory.

Class: <MAPPED-CELL>

A mixin which distinguishes cells which are mapped by a special mapping.

Direct slots:

MAPPING: Self-explanatory.

Class: <MESH>

A <mesh> is a special <skeleton> mapping cells to property lists with properties of the cell. The most important property of a cell is its patch in the domain. Another one could be a list of possibly identified cells. The slot parametric determines which kind of cell mappings are used for approximating the domain. These can be the nonlinear mappings used in the domain definition, but also arbitrary approximations, to those mappings, e.g. isoparametric mappings. The special value NIL means that multilinear mappings are used for all cells outside the boundaries.

Superclasses: <SKELETON>

Direct slots:

DOMAIN: The domain of the mesh.
PARAMETRIC: Self-explanatory.

Class: <PRODUCT-CELL>: A mixin for simplex-product cells.

Class: <SIMPLEX>: A mixin for simplicial cells.

Class: <SKELETON>

A skeleton is a vector of hash-tables containing the cells of a certain dimension as keys. The information stored in the values is different depending on the subclass derived from skeleton.

Superclasses: PROPERTY-MIXIN

Direct slots:

DIMENSION: Self-explanatory.
ETABLES: Self-explanatory.

Class: <VERTEX>

The vertex class.

Superclasses: <CELL>

Direct slots:

CELL-CLASS-INFORMATION: Self-explanatory.
POSITION: Self-explanatory.

Function: BOUNDARY OBJECT: Returns the boundary of an object (usually a cell in a mesh).

Function: BOUNDARY-IDENTIFICATIONS IDENTIFICATIONS: Returns an identification list for the boundaries of the cells in identifications.

Function: BOX-DOMAIN DIMENSIONS: Generates a box domain for the given dimensions. Here, dimensions is expected to be a list of 2-element lists denoting the interval along the respective axis. The algorithm works by copying the unit cube and modifying the coordinates of the vertices of the copy.

Function: CARTESIAN-PRODUCT OBJ1 OBJ2 &KEY PROPERTY-COMBINER &ALLOW-OTHER-KEYS: Computes the cartesian product of two skeletons.

Function: CELL->CUBE CELL: Transforms a product-cell into a degenerated cube with the same vertices.

Function: CELL-IDENTIFICATION CELL SKEL: Returns cell’s identification in skel or NIL.

Function: CELL-MAPPING CELL: Return the mapping for mapped cells.

Function: CELLS-OF-DIM SKEL DIM: Returns the cells of skel of dimension dim in form of a list.

Function: CELLS-OF-HIGHEST-DIM SKEL: Returns the cells of skel of highest dimension in form of a list.

Function: CHECK OBJ &KEY &ALLOW-OTHER-KEYS: Checks the data structure of obj.

Function: COMBINE-IDENTIFICATIONS SETS: Reduces identifications to maximally connected sets.

Function: COMPARE-LEXICOGRAPHICALLY &KEY (FUZZY 1.0e-12) DIRECTION: Returns a function which compares two vectors lexicographically.

Function: COPY-MESH MESH: Copies a mesh. Properties copied are only patch and identification. If necessary, one might add further properties to be copied as a keyword argument.

Function: COPY-SKELETON SKEL &KEY PROPERTIES TRANSFORMATION: Copies a skeleton. Properties is a list of properties to be copied.

Function: CORNERS CELL: Returns a list of corners of the cell, i.e. the global positions of the cell’s vertices.

Function: CUBE-EXTENDER DOMAIN-CUBE DIRECTION: Makes domain-cube —which should be a cube in a domain— extensible in the given direction.

Function: CUBE-P CELL: Returns T iff CELL is a cube.

Function: DEALII-N-BALL-DOMAIN DIM &KEY (RADIUS 1.0): An alternative version of the n-ball defined by using cubic patches. This is precisely what the well-known FE library deal.ii does.

Function: DIAMETER CELL: Returns the diameter of a cell.

Function: DIMENSION CELL: Returns the dimension of the cell.

Function: DIMENSION-OF-PART SKEL PART: Parts of a skeleton can be named with the property :part.

Function: DISSECTION-COMPARE H-MESH &KEY (KEY (FUNCTION IDENTITY)): Compares two cells wrt their level and their dimension. The predicate is true if level1>level2 or the levels are equal and dim1>dim2.

Function: DOMAIN-BOUNDARY DOMAIN: The boundary of the domain as a skeleton.

Function: DOMAIN-CHARACTERISTICS DOMAIN: Returns a property list of characteristics. The property curved means that curved patches exist. The property exact is set to t if the domain mappings are exact. Otherwise, only the boundary of the domain should be assumed to be provided in an exact form.

Macro: DOSKEL (LOOPING-VAR SKEL &KEY (DIRECTION) WHERE DIMENSION) &BODY BODY: Loop through a skeleton. If looping-var is an atom, it loops through all cells, otherwise it loops through cells and properties.

Function: EMBEDDED-DIMENSION OBJECT: Dimension of the embedding space for object. If check is T, a test is performed if the dimension is well-defined for all parts of object. If not, NIL is returned.

Function: ENSURE-DOMAIN DOMAIN: If domain is an integer, return the corresponding n-cube-domain, if domain is a domain return it unchanged, otherwise signal an error.

Function: ENSURE-SIMPLEX-PRODUCT FACTOR-DIMS: Returns the reference product-cell for the given factor dimensions.

Function: ETABLE SKEL DIM: A table for cells of dimension dim in skel.

Function: EXTEND MESH &KEY (TEST (CONSTANTLY T)): Extends a mesh on all extensible cells for which test —if provided— yields T.

Function: FACTOR-SIMPLICES CELL: Returns the factor-simplices.

Function: FIND-CELL-FROM-POSITION SKEL POS: Finds a cell from skel which contains the global position pos.

Function: FIND-CELLS TEST SKEL &KEY DIMENSION WITH-PROPERTIES WHERE: Returns a list of cells contained in skel and satisfying test.

Function: FIND-PATCH DOMAIN CLASSIFIERS &KEY MIDPOINT: Searches for a patch of domain having the given list classifiers.

Function: FOR-EACH-CELL-OF-HIGHEST-DIMENSION-ON-SURFACE FUNC H-MESH: Calls func for each cell on the hierarchical-mesh surface.

Function: G2L CELL GLOBAL-POS: Computes the local position inside the cell for the given global position. This function is not really used at the moment, in contrast to global->local.

Function: GET-CELL-PROPERTY CELL SKEL PROPERTY: Returns the value of the property.

Function: GET-REFINEMENT-RULE CELL ID: Finds the refinement rule for cell defined by the id. This id can be a number (position of the rule, T (meaning 0), or some symbol which is contained in the names of some rule, or even the rule itself. Two values are returned: the rule and its position in the refinement-rule vector.

Function: GLOBAL->EMBEDDED-LOCAL CELL GLOBAL-POS: This computes a local coordinate which solves the Ausgleichsproblem of mapping to a point as near as possible to global-pos. It involves more computational work than global->local. As a second value, the distance to global-pos is returned.

Function: GLOBAL->LOCAL CELL GLOBAL-POS: Mainly useful for finite element evaluation: from the local position, the value of a fe function can be obtained by interpolation. This is done by a Newton iteration, which converges in one step for linear mappings. The result is NIL, if no local point could be determined.

Function: HIERARCHICALLY-ORDERED-CELLS H-MESH &KEY (WHERE SURFACE)

Deprecated. If you need this function, please contact me on the mailing list. NN.

Sorts the cells up to the given level (defaulting to the last level) hierarchically for use in something similar to the nested disection method. Returns a list of the sorted cells.

Function: IDENTIFIED-CELLS CELL SKEL: Returns a list of cells in skel which are identified with cell.

Function: IDENTIFIED-P CELL SKEL: Returns cell’s identification in skel or NIL.

Function: IDENTIFY IDENTIFIED-CELLS SKEL: Identifies all cells in identified-cells within skel.

Function: IDENTIFY-UNIT-CELL-FACES SKEL &KEY (INDICES ALL): This routines identifies boundary cells in skel which correspond to boundary cells in the unit cube. Warning: exact arithmetic is used to recognize identified cells. This should work for skeletons derived from the unit cell, but may create problems in other situations.

Function: INNER-REFCELL-CHILDREN REFCELL RULE: Returns the children of refcell.

Function: INSERT-CELL! SKEL CELL &OPTIONAL PROPERTIES: Inserts cell and if necessary also its boundary into skel. If properties are given those are used for cell.

Function: INSERT-CELL-FROM-CORNERS MESH CORNERS->CELL CELL-CLASS CORNERS PROPERTIES &KEY (CREATE-SUBCELLS T): Creates a cell of type cell-class with corners given by corners. corners->cell has to be an equalp hash-table mapping corners to the corresponding cell. It is updated by this function.

Function: INSERT-CELLS! SKEL CELLS: Inserts a list of cells into a skeleton.

Function: INSIDE-CELL? CELL GLOBAL-POS &OPTIONAL THRESHOLD: Checks if global-pos is inside the interior of the cell. It calls global->local to obtain local coordinates and then coordinates-inside? to check if those are inside the cell. If threshold is a non-negative number, an additional check is performed, if the local coordinates map to global-pos with accuracy threshold.

Function: ITERATE-IDENTIFICATIONS INITIAL-IDENTIFICATIONS: Generates all identifications of the skeleton from the identifications of some higher-dimensional cells.

Function: KEY-IS-SUBCELL-P KEY1 KEY2: Checks if key1 occurs as subcell of key2. The keys can be either cells or identifications.

Function: L-DOMAIN DIM: Creates an L-domain by cutting out cubes from the uniform refinement of the unit cube.

Function: L2DG CELL LOCAL-POS: Computes the gradient for a multilinear interpolation from the vertices.

Function: L2G CELL LOCAL-POS: Computes the global position by interpolation from the vertices.

Function: LEVEL-OF-CELL CELL H-MESH: Returns the level of cell in the hirearchical mesh h-mesh.

Function: LINEARLY-TRANSFORMED-SKELETON SKEL &KEY A B PROPERTIES: Transforms skel by transforming the vertex positions.

Function: LOCAL->DGLOBAL CELL LOCAL-POS: local->Dglobal checks if a mapping is given for the cell. If yes, then the gradient of this mapping is evaluated (if available). If no, then the function l2Dg is called which gives the gradient for a multilinear interpolation from the cell’s corners.

Function: LOCAL->GLOBAL CELL LOCAL-POS: local->global checks if a mapping is given for the cell. If yes, then this mapping is evaluated. If no, then the function l2g is called which should do a multilinear interpolation from the cell’s corners.

Function: LOCAL-COORDINATES-OF-MIDPOINT CELL: Returns the local coordinates of the cell midpoint.

Function: MAKE-CELL-FROM-CORNERS CELL-CLASS CORNERS: Creates a cell of class CELL-CLASS having the given CORNERS.

Function: MAKE-CELL-FROM-VERTICES CELL-CLASS VERTICES: Creates a cell of class CELL-CLASS having the given VERTICES.

Function: MAKE-CLASSIFIER TEST CLASSIFICATION: Returns a classifier for patches.

Function: MAKE-DOMAIN SKEL &REST ARGS: Changes a skeleton into a domain.

Function: MAKE-HIERARCHICAL-MESH-FROM &REST ARGS: Creates a hierarchical-mesh from the given arguments. See MAKE-MESH-FROM.

Function: MAKE-HIERARCHICAL-MESH-FROM-DOMAIN DOMAIN &KEY &ALLOW-OTHER-KEYS: Construct a hierarchical-mesh from a domain.

Function: MAKE-LINE FROM-VTX TO-VTX &KEY (CHECK T) MAPPING: Creates a line given its endpoints.

Function: MAKE-MESH-FROM OBJECT &KEY PARAMETRIC INITIAL-MESH-REFINEMENTS &ALLOW-OTHER-KEYS: Makes a mesh from or for the given object.

Function: MAKE-SIMPLEX BOUNDARY &KEY CHECK MAPPING: Short form of creating a simplex given its boundary. An alternative is creating it from its vertices, see the functions MAKE-CELL-FROM-VERTICES and INSERT-CELL-FROM-CORNERS.

Function: MAKE-VERTEX POSITION &OPTIONAL MAPPING: General vertex constructor.

Function: MAPPED-CELL-CLASS CLASS &OPTIONAL DISTORTED: Constructs a cell class with <mapped-cell> mixin.

Function: MARK-SKELETON SKEL PROP VALUE: Marks all cells of skel with the given prop/value pair.

Function: MEMBER-OF-SKELETON? CELL SKEL: Returns T if cell is in skel, NIL otherwise.

Function: MESHSIZE MESH: Computes a meshsize. Please refer to the method documentations for the exact definition.

Function: MIDPOINT CELL: Returns cell midpoint in global coordinates.

Function: MULTIPLE-LOCAL->DGLOBAL CELL LOCAL-POS: Applies LOCAL->DGLOBAL for several positions at once.

Function: MULTIPLE-LOCAL->GLOBAL CELL LOCAL-POS: Applies LOCAL->GLOBAL for several positions at once.

Function: N-BALL-DOMAIN DIM: Generates an n-dimensional ball domain with 2^n simplex patches.

Function: N-CELL-DOMAIN DIM: Generates an n-dimensional cell domain which is a n-dimensional unit cube with its opposite sides identified.

Function: N-CUBE DIM: Returns the reference cube of dimension dim.

Function: N-SIMPLEX DIM: Returns the reference simplex of the given dimension.

Function: NR-OF-CELLS SKEL &OPTIONAL DIMENSION: Returns number of cells in a skeleton.

Function: NR-OF-SIDES CELL: Returns the number of boundary faces.

Function: NR-OF-SUBCELLS CELL: Returns the number of subcells.

Function: NR-OF-VERTICES CELL: Returns the number of vertices.

Function: ORIGIN CELL: Returns cell origin in global coordinates.

Function: PATCH-CLASSIFICATION PATCH DOMAIN: Returns a list of classifications for patch in domain.

Function: PERIODIC-POLYGONAL POSITIONS: Constructs a periodic polygon from positions. The result is a <skeleton>.

Function: REFCELL-CHILDREN REFCELL RULE: Returns the children for refcell and subcells.

Function: REFCELL-REFINEMENT-SKELETON REFCELL &OPTIONAL (LEVEL 1) (RULE 0) REINIT: Returns an LEVEL times refined skeleton of REFCELL. It is partially memoized, see the documentation of *REFCELL-REFINEMENT-MEMOIZE-DEPTH*.

Function: REFERENCE-CELL CELL-OR-CLASS: Returns the cell’s or cell-classes reference-cell.

Function: REFERENCE-CELL-P CELL: Tests if a cell is a reference cell.

Function: REFINE SKEL &KEY INDICATOR HIGHEST DECOUPLE &ALLOW-OTHER-KEYS: Refines skel either locally or globally depending on the indicator.

Function: REFINE-INFO CELL: Returns refinement information for the cell.

Function: REFINEMENT CELL SKELETON: Returns the refinement of cell in skeleton as two values: the rule and the children.

Function: REFINEMENT-INTERFACE H-MESH &KEY LEVEL: Returns the refined boundary subcells of unrefined cells in a skeleton. Those cells are found as all refined cells which are not part of the domain boundary. At the moment, this is a global operation. Later on, it should probably be localized.

Function: REFINEMENT-RULE CELL SKEL: Returns the refinement rule of cell in skel.

Class: REFINEMENT-RULE

Rule for refining reference cells. Those rules are stored in the refine-info slot of the cell class.

Direct slots:

NAMES: Names identifying the rule.
REFCELL: Reference cell for this refinement rule.
BOUNDARY-REFINEMENT-RULES: Refinement rules for the sides required by this rule.
REFINEMENT-INFO: Vector of refinement information for the children.

Function: REPRESENTATIVE OBJ: Returns a representative for this object.

Function: SHIFT-SKELETON SKEL SHIFT &KEY PROPERTIES: Shifts skel by vec. vec has to be a vector of dimension (embedded-dimension skel).

Function: SIMPLEX-CLASS DIM &OPTIONAL MAPPED DISTORTED: Returns the n-simplex class.

Function: SIMPLEX-PRODUCT-DOMAIN DIMS: Generates a product-cell domain for the given factor dimensions.

Function: SKEL-ADD! SKEL-1 SKEL-2 &KEY (OVERRIDE NIL) THRESHOLD ACTIVE-SKEL-1: Adds skel-2 to skel-1 destructively for skel-1. Overlaying cells are identified. override is a list of properties which are copied from skel-2 on the overlap. active-skel-1 is used for hierarchical-meshes for selecting a level to which skel-2 is added. This function returns three values: the first is skel-1, the second is skel-2, the third is a hash-table mapping overlapping cells from skel-2 to their counterpart in skel-1.

Function: SKEL-FOR-EACH FUNC SKEL &KEY (DIRECTION UP) DIMENSION WHERE WITH-PROPERTIES: Loops through a skeleton applying func. When direction is :down then loops with dimension of the cells decreasing, otherwise increasing.

Function: SKEL-MAP FUNC SKEL: Maps a skeleton with func to another skeleton having the same keys and mapped values. May be configured later on.

Function: SKEL-REF SKEL CELL: Returns the properties of cell in skel.

Function: SKELETON CELL-OR-CELLS: Returns a skeleton for the given cell or the given cells.

Function: SKELETON-BOUNDARY SKEL: Returns a skeleton consisting of cells of skel of dimension n-1 which have only one neighbor.

Function: SKELETON-DISJOINT-UNION &REST SKELS: Builds a disjoint union skeleton of all skeletons.

Function: SKELETON-WITHOUT-CELL SKEL CELL-TO-REMOVE: Removes a cell from a skeleton such that the rest remains a skeleton. Warning: does not handle identifications yet.

Function: SORT-LEXICOGRAPHICALLY ELIST &KEY (FUZZY 1.0e-12): Sorts a cell list lexicographically by the coordinates of their midpoint.

Function: SPECIAL-MESH-ON-BOX-DOMAIN DOMAIN PATCH->MESH-SIZES: Creates a uniform mesh consisting of N_1 x ... x N_dim cells on a box domain.

Function: STANDARD-EXTENDER ORIGINAL-CELL REPLACEMENT: Extension function replacing an original-cell with a replacement.

Function: STRUCTURED-MESH-ON-BOX-DOMAIN DOMAIN N: Creates a uniform mesh consisting of N_1 x ... x N_dim cells on a box domain lying parallel to the coordinate axis. Instead of N_i being an integer, it can also be a vector N_i=[x0,...,xN] with numbers x0,...,xN satisfying 0=x0<...<xN=1.

Function: STRUCTURED-SKELETON N H &KEY CORNERS->CELL: Create a uniform box skeleton consisting of N_1 x ... x N_dim cubes of dimensions h_1 x ... x h_dim.

Function: SUBCELL-CHILDREN CELL SKELETON: Returns a vector of all children of the subcells of cell in skeleton.

Function: SUBCELLS CELL: Returns a vector containing all subcells of a given cell. The code is special to each class and often automatically generated by generate-subcell-access-code.

Function: SUBSKELETON SKEL TEST: Returns a minimal skeleton containing the cells satisfying the test.

Function: SURFACE-CELLS-OF-DIM H-MESH DIM: This function returns the surface cells of a locally refined hierarchical-mesh structure.

Function: SURFACE-CELLS-OF-HIGHEST-DIM H-MESH: This function returns the surface cells of highest dimension of a locally refined hierarchical-mesh structure.

Function: TEST-CONDITION CONDITION CLASSIFICATIONS: Test if condition holds for classifications. condition should be a logical combination of the keyword symbols in the list classification.

Function: TOP-LEVEL MH: Top-level of a mesh hierarchy.

Function: TRANSFORMED-SKELETON SKEL &KEY TRANSFORMATION PROPERTIES: Transforms skel by transforming the cell mappings resp. vertex positions.

Function: TRIANGULATE DOMAIN &REST ARGS &KEY PARAMETRIC (CHECK-P T) &ALLOW-OTHER-KEYS: Triangulate domain by successively building a mesh on the domain skeleton starting from the 0-dimensional patches.

Function: TRIANGULIZE MESH: Transforms a product-cell mesh into a simplex mesh.

Function: UNIFORMLY-REFINED-MESH DOMAIN N &KEY PARAMETRIC: Generates a mesh by refining the domain partition uniformly.

Function: VERTICES CELL: Returns a list of all vertices of the cell.