1 Topology
1.1 Unstructured topology
The base data structures used to represent topology are derived from combinatorial maps in order to provide the necessary generality of operations. More structured topologies are required to conform to this interface. The two base topological interfaces are for unoriented combinatorial maps and oriented combinatorial maps.
The most basic element of each combinatorial map is the dart. From an implementation perspective a dart is just a reference to the underlying combinatorial map and a numeric identifier.
1.1.1 Unoriented topology
An unoriented combinatorial map of dimension can represent any topology of dimension without kissing corners. In an unoriented combinatorial map, there is one dart for each -tuple containing one cell of each dimension from 0 (vertex) up to the highest-dimensional element of the topology (face in two dimensions and volume in three). Each dart can be viewed as part of one of the cells that make up the corresponding tuple. Conversely, with an appropriate set of connections between darts, labeling or enumerating the cells explicitly can be avoided and instead we can refer to cells in the topology in terms of the darts that make them up. Given an unoriented combinatorial map , let the set of all darts that make up the topology be represented by . The core connections for an unoriented topology of dimension are the involutions . Each function takes a dart and maps it to another dart that is part of all the same cells except the cell of dimension or to the empty set if there is no other dart satisfying the definition.
In order to form the set of all darts associated with a single cell, we must define an orbit. Let be a set of darts associated with the topology . Given a set of functions , we say that is a fixed point set with respect to if for any and , . The orbit of a dart is a fixed point set of darts with respect to a set of functions. We denote the orbit of a dart with respect to a set of operations by or if we wish to be explicit about the functions that make up the defining set of operations. The set of darts that make up a cell of dimension can be found by constructing the orbit of a single dart in the cell using the set of operations except the operation . For example, the darts associated with the vertex of which is a member in a three-dimensional unoriented topology is given by .
1.1.2 Oriented topology
If we know that we are representing an orientable manifold then the unoriented combinatorial map data structure contains exactly twice as many darts as necessary. It is often advantageous to use only half of the darts to represent the topology. We accomplish this by introducing an oriented combinatorial map . We initially view the oriented combinatorial map as being derived from an unoriented combinatorial map: . We define a new set of operations in terms of the operations: where . We note that each of the operations for is an involution, that is (unless lies on the boundary). It is convenient to introduce the inverse of , . The set of darts that make up the oriented combinatorial map is given by . The darts that make up cells of dimension are given by the orbits . The orbit associated with a vertex is . In practice, we will not use operations on an unoriented combinatorial map to define the oriented combinatorial map but instead we will store the relations directly.
1.1.3 Combinatorial maps as an interface
From the perspective of implementation, we can view the or functions as interface functions that must be implemented. Any structure that consistently implements these functions can be treated as a combinatorial map. The simplest implementation is a collection of integer arrays arranged so that the th array provides the dart identifier associated with that relation. If we use the symbol to represent the th array then We can use the interface view of combinatorial maps to provide a rich collection of derived topological constructions.
1.1.4 Unoriented map derived from oriented map
The first example we give of a derived construction is the operation of building an unoriented map from an oriented map. Certain types of iteration are simpler on an unoriented combinatorial map and so it is advantageous to have a lightweight structure that is capable of generating an unoriented combinatorial map from an oriented combinatorial map. We accomplish this by embedding the indices of the oriented combinatorial map in an index space of twice the size. The index of a dart in the unoriented combinatorial map, , derived from the oriented map is given in terms of the index of the dart as The relation is easily defined using the bitwise operator The remaining relations for a dart are defined in terms of the relations and the bitwise , , and operations on the dart index: Here we use to represent the relation of the dart with index in the combinatorial map .
1.1.5 Tensor product topology
Large computations often contain regions that can be produced by tensor products of lower dimensional regions or the computational domain can be decomposed into multiple regions that can be constructed from tensor products. Significant computational and storage savings can be realized by leveraging this structure. We consider the construction of tensor product topologies through products of combinatorial maps. For our purposes, we are most interested in the construction of oriented maps. For now, we restrict our attention to products of one- and two-dimensional maps with one-dimensional maps to produce two- or three-dimensional maps.
We begin with an oriented map that serves as the base topology. We represent the line topology as an unoriented map, , constructed from an oriented one-dimensional map: . Combinatorial maps explicitly represent the boundary of their elements and so every dart in the resultant oriented map can be viewed as being associated with a boundary cell produced by a tensor product of a cell from with a cell from . We must consider all possible combinations such that . If is two-dimensional then there are only two options: with and with . In the case of a three-dimensional map, , there are two obvious options for the product : with and with . We must also consider the product with and . Thus for the three-dimensional map, there are three products that must be considered. From these observations, we deduce that the every dart in can be reduced to a an identifier for the type of product with which the dart was defined, a dart from , and a dart from . There are of these identifiers. This decomposition is represented as: where is the product identifier. We observe that these tuples are generated by the Cartesian product of the integer sets: This observation allows us to embed the constitutive elements of each dart into a single index space in a structured fashion:
where is an integer (we assume zero-based indexing). This embedding can easily be reversed by the standard approach for determining the colexicographical ordering of tuples.
All operations can be determined by decomposing the dart and then forming a new tuple using an appropriate transformation of , and the or operations on the darts and . The embedding of the new tuple into the integer space then provides the index . We do not give the explicit forms for these operations at this time. This approach provides minimal restrictions on the structure of and other than requiring that the dart indices be contiguous and zero-based. It is possible to adapt this construction to noncontiguous indexing with slight modifications, but the notational burden obfuscates the simple construction and so we do not present the modifications here.
1.1.6 Composite topological data structures
The two previous examples, constructing an unoriented map from an unoriented map and constructing the tensor product topology from two combinatorial maps, lead us to define the notion of a composite structure. Every dart in a composite combinatorial map can be separated into a token for the type of combination employed, and one or more darts.
Every dart in the unoriented map can be separated into a value indicating the parity of the index and the dart from whose index satisfies .
Every dart in the oriented map can be separated into an integer corresponding to the type of product that produced the dart and two darts, one from and one from .
This concept of decomposing darts and topological data structures is a powerful enabling technique for leveraging the intrinsic structure of data.
1.1.7 Semi-structured topology
We now consider the construction of semi-structured or unstructured maps through combinations of structured maps. This enables the efficient representation of complex unstructured computational domains through use of structured domain data structures. Given an ordered set of structured combinatorial maps we can construct the index space for the combined map by appending shifted versions of the index spaces for the constituent maps. The transformations are defined using the relationship
Any darts from for which are termed boundary darts, and those for which are called internal darts. All operations for darts in which correspond to internal darts from one of the , as well as all operations with are performed as
The remaining operations, for darts which are on the boundary of the constituent map, are instead performed by mapping to the boundary of the structured region, transferring to the boundary of the neighboring structured region, and then mapping to the interior of the neighboring structured region.
1.1.8 Refinement
Many important types of refinement can be viewed as embedding a mesh into each cell of a base mesh. For simplicity, we consider a conforming mesh of box-like elements as our prototypical mesh. This mesh is defined by a combinatorial map . Each box-like cell admits an natural parameterization based on the tensor product of the unit interval. We assume that the refinement mesh is given along with a function that maps each vertex to a coordinate in the unit box. The refinement is also defined by a combinatorial map . We further assume that the embedding of the refinement mesh respects octahedral symmetry on all boundaries. We define the combined mesh with combinatorial map to be defined by embedding the refinement mesh in each cell of We do this by assigning a copy of the refinement mesh and its associated topological data structure to each cell in the base mesh. This is most easily accomplished by enumerating the cells in the base mesh and then assigning each dart in the refined map an index
where represents the contiguous index assigned to a single cell in the base mesh.
This convention provides a unique identifier for each dart in the map . All that remains is to determine the relationships between the darts in the combined map . Any darts from that have are termed boundary darts. All operations on darts in for that correspond to internal darts of or for for boundary darts of are accomplished by decomposing the dart into the base dart and refinement dart, performing the required operation on the refinement dart, and then constructing the index for the refined dart using equation . In these cases the cell index of the base cell will not change. The of refined darts that correspond to boundary darts in the refinement map require the determination of the adjacent base cell that defines the adjacent refined darts in order to compute. This is accomplished by determining the parametric coordinates of the -cell corresponding to the refinement dart and then finding the corresponding boundary -cell in the base cell and a constitutive dart . The dart given by provides a dart from the adjacent base cell (if it exists). It is then necessary to determine the correct refinement dart embedded within the adjacent base cell. This is accomplished by again using the embedding of the refinement mesh into the parameterization of the base cell. The relationships between all possible orientations of two adjacent cells can be computed and stored so that this operation can be completed efficiently. Using this correspondence, the procedure for the operation is to decompose the input dart, determine the adjacent base cell and use the relative orientation of the two base cells to determine the appropriate correspondence between the refinement darts in the adjacent meshes. Once the correct adjacent refinement dart is determined, the index of the adjacent dart and the adjacent refinement dart are used to compute the index of the adjacent refined dart using equation .
1.1.9 Example application
We conclude with an example of applying the tensor product and refinement operations to combinatorial maps in order to optimize a computation. Suppose that we wish to carry out a simulation on a mesh with repeating substructure. The base mesh is also known to be formed from a tensor product of an unstructured two-dimensional topology with a line and the repeating substructure can be represented by a tensor product of three lines. We form the base mesh and the refinement meshes and . We use the following notation to denote the embedding operation on meshes: . We also form the refined meshes and . The final computational mesh is given by . All available structure is at our disposal during computations. The darts of the computational mesh can be decomposed at any point in time to determine the topological contributions of any of the base meshes or the associated refined meshes.