Mesh

Standard mesh

(See also: mesh, Working with the mesh class)

The mesh class is robust and feature rich, supporting arbitrary, mixed-element meshes, with a variety of methods and on-demand properties. It’s based around two data structures:

1. NodeCoords - an array containing the coordinates of the nodes, and

2. NodeConn - an array (or list of lists) containing indices of the nodes that connect to form elements (or the ‘node connectivity’)

Dictionaries NodeData and ElemData can be used to store scalar or vector data alongside the nodes and elements.

Dynamic mesh

(See also: dmesh)

dmesh is a specialized mesh data structure for rapid modifications to a mesh’s connectivity, such as during coarsening (Contract()) or delaunay triangulation. It has three key features that enables rapid modifications: amortized \(\mathcal{O}(1)\) insertion by doubling, swap removal, and a doubly-linked list to track node-element connectivity.

Note

dmesh only supports single element type meshes, and has only been fully tested on purely triangular and purely tetrahedral meshes.

Amortized \(\mathcal{O}(1)\) insertion

In dynamically changing meshes, nodes and/or elements may be repeatedly added and/or removed. When performing many such operations, the cost of resizing the arrays storing node and element information becomes significant. To more efficiently handle insertions into arrays, the arrays are maintained with buffer space at the end, and a pointer (e.g. NNode, NElem) that tracks where the end of the meaningful data is. Inserting a value into the next available space is a simple and \(\mathcal{O}(1)\) operation. Whenever that buffer space runs out, the arrays will still need to be resized. Since we don’t know how big the array needs to be, we can just double the length of the arrays to create plenty of space relative to the size of the existing arrays.

Swap Removal

Similar to insertion, removal changes the size of the data, but resizing the arrays whenever an entry is removed would slow things down a lot. Instead, the item that’s to be deleted can just be swapped with the last entry of meaningful data in the array, and the pointers can be moved accordingly. In addition eliminating the need to resize the arrays when an item is deleted, it adds more buffer space that can be utilized by future insertion operations.

While elements are removed the NodeConn array by swap removal, nodes are removed from the mesh by simply removing the elements that reference them. While that can cause orphaned nodes that take up space, it prevents the need to modify all connected elements with updated node numbers.

Doubly-linked list for element connectivity

It’s often useful to keep track of all the elements that are connected to a node, however, that number can vary from node to node, meaning the ElemConn data structure becomes a “ragged” array (or list of lists), which can be difficult and inefficient to work with.

The doubly linked list structure involves five arrays: head, next, prev, tail, and elem. For node i, head[i] contains an index j for elem that points to the first element connected to node i (elem[head[i]]). To get to the next connected element, next[j] gives the index k that points to the next element in elem, next[k] gives the next, and so on until next contains the end flag (in this case, -1). Thus, by traversing the arrays head, elem, and next we can collect all of the element indices that are connected to a node. tail and prev work just liked head and next but in reverse. The value of maintaining tail and prev in addition to head and next is that they make it easy (and efficient) to insert and remove new entries. For example, if a new element is connected to node i, we can insert an entry into elem at the next available index m, change prev[tail[i]] from end to m, and set prev[m] to end. The addition of a new connection thus does not depend on how many elements are already connected to the node, as it would if we need to first use next to traverse from head[i] to tail[i]

The same insertion method used for the node and element information is used to maintain these arrays.

ElemConn = [[0, 2],
            [0, 1],
            [1],
            [0, 1, 2],
            [2]]