Discrete Manifolds

Discrete Manifolds capture (at a very abstract level), the notion of a grid. I think that it is safe to say that all grids are what topologists call "cellular complexes". That is, they consist of a set of "cells" (or elements), and the boundary between two cells is a cell of one lower dimension. Thus a regular grid in 3-space is made up of a set of cubes, and the interfaces between adjacent cubes are squares, which are made up of edges, whose ends are points.

This figure shows a 2 dimensional cellular complex in a Target space of dimension 2. The complex consists of: eight vertices (0-cells), labeled in blue, 18 edges (1-cells), labeled in white, and 11 faces (2-cells), labeled in red. In this example face 10 represents the exterior of the polygonal region.

Each cell of dimension greater than 0, has a list of faces. For example, 2-cell number 0 has three faces, which are 1-cells 6, 16, and 17. 1-cell 16 has two "faces", which are vertices 6 and 7.

Each cell of dimension less than the base space dimension has a list of adjacent cells, of which it is a face. For example, 1-cell 8 is the face of 2-cells 6 and 7. 0-cell 5 is a face of 1-cells 5, 6, 8, 10 and 17.

One way of representing the discrete manifold in the figure above is as several lists of cells. Each cell may have a list of cells of one greater dimension to which it is a face, and a list of faces. For the figure:

0-Cells

  Cell      Face of Cells 

  0           0,4,14
  1           0,2,3
  2           1,9,12
  3           8,7,11,12
  4           10,11,13
  5           5,6,8,10,17
  6           2,7,9,16,17
  7           3,4,6,14,15,16

1-Cells

 Cell      Face of Cells            Faces

  0           4,10                   0,1
  1           2,10                   1,2
  2           1,2                    1,6
  3           1,4                    1,7
  4           4,5                    0,7
  5           3,9                    5,8
  6           0,9                    5,7
  7           6,8                    3,6
  8           6,7                    3,5
  9           2,8                    2,6
 10           3,7                    4,5
 11           7,10                   3,4
 12           8,10                   2,3
 13           3,10                   4,8
 14           5,10                   0,8
 15           5,9                    7,8
 16           0,1                    6,7
 17           0,6                    5,6

2-Cells

  Cell                                Faces

  0                                  6,16,17
  1                                  2,3,16
  2                                  1,2,9
  3                                  5,10,13
  4                                  0,3,4
  5                                  4,14,15
  6                                  7,8,17
  7                                  8,10,11
  8                                  7,9,12
  9                                  5,6,15
 10                                  0,1,11,12,13,14

Not all grids actually store all of this information, it may be implicit. For example, a regular grid need only store mesh spacings and counts. The cells of any dimension and their faces can be recovered from the index.

Cells are represented as a list of faces (returned as an array of longs), each of which is a cell of one lower dimension. Each cell is the face of some number of cells of one higher dimension. The following figure illustrates the faces of a 3-cell in three dimensions, which are 2-cells.

Each cell is also potentially the face of another cell. The cells of which a given cell is a face we've called FaceCells (not the best name). The following figure illustrates the face cells of a 2-cell in three dimensions, which are 3-cells.

Manifolds have a member function isitDiscrete() which reports whether a cellular complex exists for the manifold. If it does, the manifold supplies the following member functions

long getNumberOfVertices() -- returns the number of verticies (i.e. points).
int getNumberOfCoordinatesPerVertex() -- returns the number of coordinates per vertex. Vertices may be either in the base or target space.
getVertex(long i,NAPointOnManifold *) -- returns vertex i.
long getVertexNumber(NAPointOnManifold *) -- returns the number of a vertex.
long getNumberOfCells(int dimension) -- returns the number of cells of dimension dimension. For a three dimensional mesh:
- dimension=3 returns the number of volume cells.
- dimension=2 returns the number of faces.
- dimension=1 returns the number of edges.
- dimension=0 returns the number of vertices.
int getMaxNumberOfCellFaces(int dimension) -- returns the maximum number of faces of a cell of dimension dimension. For a three dimensional mesh:
- dimension=3 returns the maximum number of faces around any volume cell.
- dimension=2 returns the maximum number of edges around any face.
- dimension=1 returns the maximum number of points about any edge (always should be two).
int getMinNumberOfCellFaces(int dimension) -- returns the minimum number of faces of a cell of dimension dimension. For a three dimensional mesh:
- dimension=3 returns the minimum number of faces around any volume cell.
- dimension=2 returns the minimum number of edges around any face.
- dimension=1 returns the minimum number of points about any edge (always should be two).
int getNumberOfCellFaces(long i,int dimension) -- returns the number of faces of cell i of dimension dimension. For a three dimensional mesh:
- dimension=3 returns the number of faces around volume cell i.
- dimension=2 returns the number of edges around face i.
- dimension=1 returns the number of points about edge i (always should be two).
getCellFaces(int i, int dimension,int *faces) -- returns the faces of cell i of dimension dimension. For a three dimensional mesh:
- dimension=3 returns a list of the faces around volume cell i.
- dimension=2 returns a list of the edges around face i.
- dimension=1 returns a list of the end points of edge i.
long getCellFace(long i, int dimension, int face) -- returns a face of cell i of dimension dimension. For a three dimensional mesh:
- dimension=3 returns a particular face of volume cell i.
- dimension=2 returns a particular edge of face i.
- dimension=1 returns a particular end point of edge i.
int getMaxNumberOfFaceCells(int dimension) -- returns the maximum number of cells of dimension dimension attached to any face. For a three dimensional mesh:
- dimension=2 returns the maximum number of volume cells sharing any given face (should always be two).
- dimension=1 returns the maximum number of faces sharing any given edge.
- dimension=0 returns the maximum number of edges with any given endpoint.
int getMinNumberOfFaceCells(int dimension) -- returns the minimum number of cells of dimension dimension attached to any face. For a three dimensional mesh:
- dimension=2 returns the minimum number of volume cells sharing any given face (should always be two).
- dimension=1 returns the minimum number of faces sharing any given edge.
- dimension=0 returns the minimum number of edges with any given endpoint.
getNumberOfFaceCells(long i,int dimension) -- returns the number of faces of cell i of dimension dimension. For a three dimensional mesh:
- dimension=2 returns the number of volume cells sharing face i (should always be two).
- dimension=1 returns the number of faces sharing edge i.
- dimension=0 returns the number of edges with endpoint i.
getFaceCells(long face, int dimension, int *cells) -- returns the cells of which face is a face. For a three dimensional mesh:
- dimension=2 returns a list of the volume cells sharing face i.
- dimension=1 returns a list of the faces sharing edge i.
- dimension=0 returns a list of the edges with endpoint i.
long getFaceCell(long face, int dimension, int cell) -- returns a cell of which face is a face. For a three dimensional mesh:
- dimension=2 returns a particular volume cell sharing face i.
- dimension=1 returns a particular face sharing edge i.
- dimension=0 returns a particular edge with endpoint i.

Note: The 1 and n-1 cells of a mesh are somewhat special. A 1-cell has two endpoints (faces), and each n-1 cell has two n-cells that it is a face of. There is therefore an orientation associated with the edges and n-1 cells. For edges, we speak of an origin and destination, and in three dimensions faces have left and right volume cells. In two dimensions n-1=1, and edges have left and right faces.

Orientation becomes important when you try to generate a list of the vertices around a face, or all the neighbors of an n-cell. If the 1 and n-1 cells are not oriented, each vertex or n-cell is generated twice. If they are oriented, the first endpoint of each edge, and the first face cell of each n-1 cell will generate the required list.

We therefore strongly recommend that the following convention be observed: that routines which return 1-cells return a number that is between zero and twice the number of 1-cells. Each 1-cell has a mirror twin, with opposite orientation, which is refered to by the number that is greater than the total number of 1-cells. Similarly with the n-1 cells. (This must be implemented in the getCellFace() routines.)

For example, mesh with 200 1-cell's and 300 n-1 cells

1-cell #105 has endpoints 1 and 400

1-cell #305=(105+200) has endpoints 400 and 1

n-1-cell #49 has face cells 55 and 69

n-1-cell #349=(49+300) has face cells 69 and 55

[Comments | NAO Home Page] [Research home page]

[ IBM home page | Order | Privacy | ContactIBM | Legal ]