Added references to new indexing figures, and rearranged
authorOrion Lawlor <olawlor@acm.org>
Mon, 17 Feb 2003 17:31:01 +0000 (17:31 +0000)
committerOrion Lawlor <olawlor@acm.org>
Mon, 17 Feb 2003 17:31:01 +0000 (17:31 +0000)
and reworked a bit of text.

doc/fem/mesh.tex

index 7e5e74fc763ba526fb4a688a3eadcc1e3b1145a3..4e77a3d9ee3b37493883907ccae7d6d214fc7682 100644 (file)
@@ -38,6 +38,26 @@ can both update---currently, only nodes can be shared.  Shared nodes
 are mixed in with regular nodes, and the framework currently provides
 no way to identify which nodes are shared.
 
+A \term{ghost entity} is a boundary entity that is asymmetrically shared---one
+side provides values for the ghost from one of its real entities, 
+and the other sides accept read-only copies of these values.
+Ghosts are described in more detail in Section~\ref{sec:ghost},
+and can be accessed by adding the constant \kw{FEM\_GHOST} to 
+the corresponding real entity's type.
+
+The different kinds of entities are described in the following sections.
+
+\begin{center}
+\begin{tabular}{|l|l|}\hline
+Real Entity & Ghost Entity \\ \hline
+\kw{FEM\_NODE} & \kw{FEM\_GHOST}+\kw{FEM\_NODE} \\ \hline
+\kw{FEM\_ELEM}+$elType$ & \kw{FEM\_GHOST}+\kw{FEM\_ELEM}+$elType$ \\ \hline
+\kw{FEM\_SPARSE}+$sparseType$ & \kw{FEM\_GHOST}+\kw{FEM\_SPARSE}+$sparseType$ \\ \hline
+\end{tabular}
+\end{center}
+
+
+
 \subsubsection{Nodes}
 \kw{FEM\_NODE} is the entity code for nodes, the simplest kind of entity.  
 A node is a single point in the domain, and elements are defined by their nodes.
@@ -138,6 +158,23 @@ Return the default writing mesh.  This routine is valid:
 \end{itemize}
 
 
+\prototype{FEM\_Mesh\_get\_length}  
+\function{int FEM\_Mesh\_get\_length(int mesh,int entity);}
+\function{integer function :: FEM\_Mesh\_get\_length(mesh,entity)}
+  \args{integer, intent(in) :: mesh,entity) }
+
+Return the number of \uw{entity}s that exist in this \uw{mesh}.
+
+This call can be used with any entity.
+For example, to get the number of ghost nodes, 
+  \begin{alltt}
+       nGhostNodes=FEM\_Mesh\_get\_length(\uw{mesh},\kw{FEM\_GHOST}+\kw{FEM\_NODE})
+  \end{alltt}
+To get the number of real elements of type 2,
+  \begin{alltt}
+       nElem=FEM\_Mesh\_get\_length(\uw{mesh},\kw{FEM\_ELEM}+2)
+  \end{alltt}
+
 
 \prototype{FEM\_Mesh\_data}  
 \function{void FEM\_Mesh\_data(int mesh,int entity,int attr,
@@ -219,21 +256,6 @@ user data "tag", for example 13, and:
    CALL FEM\_Mesh\_data(mesh,FEM\_NODE,FEM\_DATA+13, mat, 1,nNodes, FEM\_DOUBLE, 2)
   \end{alltt}
 
-\prototype{FEM\_Mesh\_get\_length}  
-\function{int FEM\_Mesh\_get\_length(int mesh,int entity);}
-\function{integer function :: FEM\_Mesh\_get\_length(mesh,entity)}
-  \args{integer, intent(in) :: mesh,entity) }
-
-Return the number of \uw{entity}s that exist in this \uw{mesh}.
-For example, to get the number of ghost nodes, 
-  \begin{alltt}
-       nGhostNodes=FEM\_Mesh\_get\_length(\uw{mesh},\kw{FEM\_GHOST}+\kw{FEM\_NODE})
-  \end{alltt}
-To get the number of real elements of type 2,
-  \begin{alltt}
-       nElem=FEM\_Mesh\_get\_length(\uw{mesh},\kw{FEM\_ELEM}+2)
-  \end{alltt}
-
 
 \subsection{Advanced Mesh Manipulation Routines}
 
@@ -259,39 +281,40 @@ for details on how to set offsetBytes, distanceBytes, and skewBytes.
 A \term{ghost entity} is a local, read-only copy of a real entity
 on another chunk. Ghosts are typically added to the boundary of a chunk to allow the real (non-ghost) elements at the boundary to access values across the processor boundary.  This makes a chunk ``feel'' as if it was part of a complete unpartitioned mesh; and can be useful with cell-centered methods, and in mesh modification.
 
-
-\begin{figure}[h]
+\begin{figure}
 \begin{center}
-\includegraphics[width=2in]{fig/ghost_pre}
+\includegraphics[width=1.5in]{fig/ghost_pre}
 \end{center}
 \caption{A small mesh partitioned into two pieces.}
 \label{fig:ghostpre}
-\end{figure}
 
-In Figure~\ref{fig:ghostpre}, we begin with a small mesh partitioned
-into pieces on the left and right.  In Figure~\ref{fig:ghostedge},
-we have added ghost elements (dark hashing) that share an edge with
-adjacent real elements (light hatching).  In Figure~\ref{fig:ghostnode},
-we add ghost elements that share at least one node with adjacent 
-real elements.
+% \end{figure} \begin{figure} % Make sure these two figures don't get separated
 
-\begin{figure}[h]
 \begin{center}
-\includegraphics[width=2in]{fig/ghost_edge}
+\includegraphics[width=1.5in]{fig/ghost_edge}
 \end{center}
 \caption{The same mesh with one layer of edge-adjacent ghosts.}
 \label{fig:ghostedge}
-\end{figure}
 
-\begin{figure}[h]
+% \end{figure} \begin{figure}
+
 \begin{center}
-\includegraphics[width=2in]{fig/ghost_node}
+\includegraphics[width=1.5in]{fig/ghost_node}
 \end{center}
 \caption{The same mesh with one layer of node-adjacent ghosts.}
 \label{fig:ghostnode}
 \end{figure}
 
 
+In Figure~\ref{fig:ghostpre}, we begin with a small mesh partitioned
+into pieces on the left and right.  In Figure~\ref{fig:ghostedge},
+we have added ghost elements (dark hashing) that share an edge with
+adjacent real elements (light hatching).  In Figure~\ref{fig:ghostnode},
+we add ghost elements that share at least one node with adjacent 
+real elements.
+
+
+
 \subsection{Ghost Numbering}
 \label{sec:ghost_num}
 Ghosts and real entities are stored by the framework
@@ -301,23 +324,104 @@ lists the ghost elements for \uw{elType} 1.  To get the number
 of ghost nodes, you would call 
 \kw{FEM\_Mesh\_get\_length}(\uw{mesh},\kw{FEM\_GHOST}+\kw{FEM\_NODE}).
 
-The connectivity table for ghost elements may include the invalid 
+\begin{figure}[h]
+\begin{center}
+\includegraphics[width=4in]{fig/conn_indexing}
+\end{center}
+\caption{Node indices used in the element connectivity array.
+There are $n$ real nodes and $m$ ghosts.}
+\label{fig:connindexing}
+\end{figure}
+
+For real elements, the element connectivity always consists of real nodes.
+But for ghost elements, the adjacent nodes may be missing, or may themselves
+be ghosts.
+Thus ghost element connectivity lists may include the invalid 
 value -1 (in C) or 0 (in Fortran) to indicate that the corresponding 
-node is not present.  Ghost element connectivities may also include values
+node is not present; or may include values
 less than this, which indicate the corresponding node is a ghost.
-That is, in C, ghost node $i$ is indicated by the value $-1-i$, while
-in fortran, ghost node $i$ is indicated by the value $-i$.  Since the 
-C versions are more complex (because 0 is a valid index in C), the
-C version includes the macros \kw{FEM\_Is\_ghost\_index}(i), which
-returns true if $i$ represents a ghost node; and \kw{FEM\_From\_ghost\_index}(i),
-which returns the ghost node's index given its connectivity entry.
-In Fortran, these macros are equivalent to the test $i$ .lt. $0$ and 
-the expression $-i$.
-
-For example, a quadrilateral ghost element adjacent to two real 
-nodes 23 and 17, one ghost node 10, and one not-present node might have a 
+In C, ghost node $i$ is indicated by the value $-2-i$, while
+in Fortran, ghost node $i$ is indicated by the value $-i$.  
+This node indexing system is illustrated in Figure~\ref{fig:connindexing}, 
+This indexing system is bizarre, but it allows us to keep
+the real and ghost nodes clearly separate, while still
+allowing real and ghost nodes to be added in increasing order
+at both ends.
+
+Since the C tests are complicated, in C we recommend using these macros:
+
+\begin{itemize}
+\item \kw{FEM\_Is\_ghost\_index}(i) returns true if $i$ represents a ghost node.
+In Fortran, use the test $i$ .lt. $0$
+
+\item \kw{FEM\_From\_ghost\_index}(i) returns the ghost node's index given its connectivity entry.
+In Fortran, use the expression $-i$.
+
+\item \kw{FEM\_To\_ghost\_index}(i) returns the connectivity entry for a given ghost node index.
+In Fortran, again use the expression $-i$.
+\end{itemize}
+
+For example, a quadrilateral ghost element that is adjacent to, respectively, two real 
+nodes 23 and 17, the tenth local ghost node, and one not-present node might have a 
 connectivity entry of {23,17,-11,-1} (in C) or {23,17,-10,0} (in Fortran).
 
+Applications may wish to use some other numbering,
+such as by storing all the ghost nodes after all the real nodes.
+The code to extract and renumber the connectivity of some 3-node triangles 
+stored in FEM\_ELEM+2 would be:
+
+\begin{alltt}
+/* C version */
+  int nReal=FEM_Mesh_get_length(mesh,FEM_ELEM+2);
+  int nGhost=FEM_Mesh_get_length(mesh,FEM_GHOST+FEM_ELEM+2);
+  typedef int intTriplet[3];
+  intTriplet *conn=new intTriplet[nReal+nGhost];
+  /* Extract real triangles into conn[0..nReal-1] */
+  FEM_Mesh_data(mesh,FEM_ELEM+2,FEM_CONN, &conn[0][0], 0,nReal, 3,FEM_INDEX_0);
+  /* Extract ghost triangles into conn[nReal..nReal+nGhost-1] */
+  FEM_Mesh_data(mesh,FEM_GHOST+FEM_ELEM+2,FEM_CONN, &conn[nReal][0], 0,nGhost, 3,FEM_INDEX_0);
+  
+  /* Renumber the ghost triangle connectivity */
+  for (int t=nReal;t<nReal+nGhost;t++)
+    for (int i=0;i<3;i++) \{
+      int in=conn[t][i]; /* uses FEM ghost node numbering */
+      int out; /* uses application's ghost numbering */
+      if (in==-1) \{ 
+        out=some_value_for_missing_nodes; 
+      \} else if (FEM_Is_ghost_index(in)) \{
+        out=first_application_ghost+FEM_From_ghost_index(in);
+      \} else /*regular real node*/ \{
+        out=in;
+      \}
+      conn[t][i]=out;
+    \}
+
+! F90 version
+  INTEGER, ALLOCATABLE :: conn(3,:)
+  INTEGER :: nReal,nGhost,t,i,in,out
+  nReal=FEM_Mesh_get_length(mesh,FEM_ELEM+2)
+  nGhost=FEM_Mesh_get_length(mesh,FEM_GHOST+FEM_ELEM+2)
+  ALLOCATE(conn(3,nReal+nGhost))
+  ! Extract real triangles into conn[1..nReal] 
+  CALL FEM_Mesh_data(mesh,FEM_ELEM+2,FEM_CONN, conn, 1,nReal, 3,FEM_INDEX_1)
+  ! Extract ghost triangles into conn[nReal+1..nReal+nGhost] 
+  CALL FEM_Mesh_data(mesh,FEM_GHOST+FEM_ELEM+2,FEM_CONN, conn(1,nReal+1), 1,nGhost, 3,FEM_INDEX_1)
+  
+  ! Renumber the ghost triangle connectivity 
+  DO t=nReal+1,nReal+nGhost
+    DO i=1,3
+      in=conn(i,t) 
+      IF (in .EQ. 0) out=some_value_for_missing_nodes
+      IF (in .LT. 0) out=first_application_ghost-1+(-in)
+      IF (in .GT. 0) out=in
+      conn(i,t)=out
+    END DO
+  END DO
+  
+  
+\end{alltt}
+
+
 
 \subsection{Setting up the ghost layer}
 The framework's ghost handling is element-centric. You specify which kinds of elements should be ghosts and how they connect by listing their faces before partitioning.  
@@ -662,14 +766,27 @@ details).  The row-major form is preferred.
 
 \subsection{Old Ghost Numbering}
 
+
+
 In this older version of the framework, FEM\_Get\_node and FEM\_Get\_elem return the 
 \textbf{total} number of nodes and elements, including ghosts. The routines below
 return the index of the first ghost node or element, where ghosts are numbered
 after all the real elements.  This old ghost numbering scheme does not work
-well when adding elements, which is why the new ghost numbering scheme
+well when adding new ghosts, which is why the new ghost numbering scheme
 describes in Section~\ref{sec:ghost_num} is used in the new API.
 
 
+\begin{figure}[h]
+\begin{center}
+\includegraphics[width=4in]{fig/conn_indexing_old}
+\end{center}
+\caption{Old ghost element and node numbering.  \kw{FEM\_Get\_ghost\_*} returns $g$,
+\kw{FEM\_Get\_*} returns $n$.}
+\label{fig:connold}
+\end{figure}
+
+
+
 \prototype{FEM\_Get\_ghost}
 \function{int FEM\_Get\_node\_ghost(void);}
 \function{int FEM\_Get\_elem\_ghost(int elemType);}