basicnumerics.com Blog

When I created the mesh generator for BFlow, I used a straightforward but unimaginative set of data structures for storage. A mesh is made up of cells, faces, edges and vertices. Unstructured meshes have arbitrary relationships between these (unlike a structured mesh), and thus those relationships must be stored.

In a 2d, a mesh looks like this:

My BFlow data structures to hold the information for a mesh look like this:

TYPE CellType
    node(4) AS LONG   '1=SW,2=SE,3=NE,4=NW (1st 4 are the corners)
    Face(4) AS LONG   '1=East, 2=west, 3=North, 4=South
    nb(4) AS LONG     'Neighbor cells. 1=East, 2=west, 3=North, 4=South
END TYPE

TYPE FaceType
    node(2) AS LONG  'ptrs to two nodes of face
    cell(2) AS LONG  'ptrs to neighbor cells
END TYPE

TYPE VertType
    face(4) AS LONG  'pointer to touching faces, 1=East,2-West,3=North,4=South
    cell(4) AS LONG  'pointer to touching cells, 1=SW,2=SE,3=NE,4=NW
END TYPE

(These are Basic declarations, but they would look very similar in C.) You can see that everything is stored. A cell can have four faces and four nodes. Pointers to them are stored in that cell structure. A vertex can be touched by four faces. Pointers to all those faces are stored for each vertex.

There is a very elegant alternative storage scheme called the Half Edge Mesh. Amazingly little information is stored, but it provides everything you need! The key idea is that rather than store edges (or faces in 2d), you store half edges (half faces). While an ordinary face is defined by its two end points, a half face is directed and defined by just a single point. The picture shows the idea.

This probably looks like a step in the wrong direction, if we are trying to simplify things. Yet, this change is really helpful. The data structure for a half face looks like:

struct face_type {
    VERT_TYPE *vert;  //vertex at the end of the half-face
    FACE_TYPE *pair;  //Oppositely oriented adjacent half-face
    CELL_TYPE *cell;  //cell that this face belongs to
    FACE_TYPE *nextF;  //next half-face around the cell
};

The vertex and cell structures are given below:

struct vert_type {
    double x;
    double y;
    FACE_TYPE *face;  //Ptr to a touching face
};

struct cell_type {
	FACE_TYPE *face;   //south face of cell
};

The cell structure seems especially spartan, at least compared with what I started with. How do you access the faces of the cell? Or its vertices? It turns out to be very easy:

FACE_TYPE* face = cell->face;
do
{
    // ...some face calcs...
    face = face->nextF;
} while (face != cell->face);

The cell faces are effectively organized into a circular linked list. Thus the above code works equally well for a quad mesh as a polyhedral mesh.

Accessing all of the vertices around the cell is nearly as easy:

VERT_TYPE *vert;
FACE_TYPE *face = cell->face;
do
{
    vert = face->vert;
    // ...some vert calcs...
    face = face->next;
} while (face != cell->face);

Now lets try something trickier. Say you needed to loop over all of the cells surrounding a vertex? This could come up in a CFD model, for instance, when interpolating a field value from the cell centers to the vertices. Here is the code:

CELL_TYPE *cell;
FACE_TYPE* face = vert->face;
do
{
    cell = face->cell;
    // ...cell calcs...
    face = face->nextF->pair;
} while (face != vert->face);

This takes advantage of the fact that pairs of faces are oriented in opposite directions. In the figure below, face F1 is pointed upward. Its pair face, F2, is pointed downward. Each face stores a pointer to the vertex that it is pointing to. F1 stores a pointer to V1, while F2 stores a pointer to V2.

You can trace out logic by picking one of the faces pointing toward vertex V2, then following the steps. It is very elegant.

Compared to my original scheme, the Half Edge approach is both more efficient (in terms of memory use) and more flexible (since its not limited to quad meshes). In my next entry, I will explore this in more detail.

This entry was posted on Saturday, January 26th, 2008 at 4:13 pm and is filed under BFlow, Data Structures. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.