We saw earlier that the half edge data structure is a very elegant way to create a mesh. However, as I pointed out recently, this approach does have a couple of drawbacks for general CFD applications. Are there other elegant approaches worth considering? One interesting possibility is to use the algebraic relationships between vertices, faces and cells to generate the connections between them. If the mesh is rectangular, and you number the components systematically, you can work out these relationships.
Cells & Vertices
Lets say we number our cells from left to right, starting with the bottom row, as in the figure. Any given cell can be expressed in terms of its column number and row number:
CID = N_cols*i + j
The Cell ID (CID) is found by multiplying the number of columns in the grid (N_cols) by the current row number i, and adding the current column number j. We are following the C convention of starting our numbering from zero. We can number the vertices in the same way, starting in the lower left corner. Without too much trouble, we can see that if you know the ID of the cell, you can work out the ID of the south west vertex of that cell:
VID_SW = CID + i
where VID_SW is the ID number of the southwest vertex. The equation works out this way because any row of N cells has N+1 vertices.
The ID for the southeast vertex is just one more bigger than the southwest:
VID_SE = CID + i + 1
To get the index for the northern vertices, we need to add a row of vertices to the index of the corresponding southern vertex:
VID_NW = CID + i + (N_Cols + 1) VID_NE = CID + i + 1 + (N_Cols + 1)
Faces
The numbering scheme for the faces is a bit trickier. You can just name them sequentially starting from the south west corner, but I think its a bit easier if you create two lists: a list of horizontal faces (i.e., the north and south faces) and a list of vertical faces (i.e., the east and west faces). The figure shows the idea, with the horizontal faces numbered in black and the verticals in blue. With this approach, the southern faces have the same numbering as the cells, thus
FID_S = CID
The northern face ID numbers can be found by taking the southern face ID and adding the number of columns in the grid:
FID_N = CID + N_cols
For the east and west faces, each row has one more face than there are cells. This is the same as the vertex numbering, thus
FID_W = CID + i FID_E = CID + i + 1
In practice, we don’t really want to have two lists of faces. It is more convenient if we can loop through a single list. This can be achieved by appending the east-west list onto the north-south list. Once that is done, the indices for the east and west faces will need to be increased by the number of horizontal faces:
FID_W = N_HFaces + CID + i FID_E = N_HFaces + CID + i + 1
where
.
Implementation
I have written a C program to implement these ideas, but it was a torture. I made heavy use of my generic list structure and in the process hit a bunch snags. C is notorious for giving you the power to shoot yourself in the foot, and I dare say that I don’t have many toes left. I made a ton of memory mistakes and it took me more than 10 hours of debugging to find and correct them all. In the process, I made a number of improvements to the generic list routines (including writing a bunch of documentation), so hopefully this won’t happen again. I’ll discuss the implementation more in the next post.
