source: trunk/anuga_core/documentation/old_pyvolution_documentation/pyvolution_structure.tex @ 7935

\documentclass[12pt]{article}
\usepackage{graphicx}


\begin{document}


\section{Abstract view of a basic triangle}

The fundamental geometric structure in the finite-volume 
or finite-element method is the \textbf{triangle}.
Several triangles can be joined along their edges to 
form \textbf{meshes} thus providing the ability to discretise complex and 
general domains. Figure \ref{fig:mesh_example} shows a mesh composed of a
number of triangles.

\begin{figure}
\begin{center} 
  \includegraphics[width=0.8\textwidth]{mesh_example}  
\end{center}
\label{fig:mesh_example}
\caption{FIXME: Should be replaced by a pmesh generated mesh}
\end{figure}



Triangles are fully described by the location of their three \textbf{vertices}
always required to be given in \emph{counter-clockwise} order and they are
enumerated as 0, 1, 2.
Other properties are derived automatically and each triangle is given a 
unique non-negative integer id. The derived 
properties are:
\begin{itemize}
  \item \textbf{centroid:} location of center of gravity
  \item \textbf{faces:} Triangle edges are called \emph{faces} in 
  pyvolution and each is enumerated like the vertex it opposes.       
  \item \textbf{edgelengths:} Length of each face.  
  \item \textbf{normals:} Outward pointing normal vectors. 
  Enumerated as faces. 
  \item \textbf{midpoints:} Points bisecting each face. 
  Enumerated as faces.    
  \item \textbf{area:} The triangle area
  \item \textbf{radius:} The distance from the centroid to the 
  nearest midpoint 
\end{itemize}  


In addition, each triangle has information about adjacent triangles 
(neighbours):
 
\begin{itemize}
  \item \textbf{neighbours:} Indices of adjacent triangles if present, 
  otherwise a negative number identifying a boundary 
  (see Section \ref{sec:boundaries}). Neighbours are enumerated as faces.
  \item \textbf{neighbour\_faces:} For each face, this is the index of 
  the closest face in the neighbour. If no neighbour is present this 
  index is undefined.     
  \item \textbf{number\_of\_boundaries:} Defined as $3$ less the number of 
  adjacent triangles.
\end{itemize}  

The conceptual structure of a triangle and it's relation to edges and 
adjacent triangles are shown in Figure \ref{fig:triangle}. 
Some quantities are omitted for simplicity.
 
\begin{figure} 
  \begin{center}
    \includegraphics[width=0.8\textwidth]{triangle}
  \end{center}
  \caption{Conceptual structure of triangles and their relationships.}
  \label{fig:triangle}  
\end{figure} 


\section{Mesh Data Structure}

Each triangle, each point and each vector could be implemented 
as an object containing the above mentioned attributes. 
However, for performance issues, all information is kept in 
consecutive memory blocks implemented as standard 2d arrays 
and each triangle object pertain to all conceptual instances of 
triangle, point and vector.

In addition, not all information listed above need to be 
stored permanently. 
The midpoints, for example, are only needed once when computing the 
triangle-radii, and are discarded after all other attributes 
have been computed.

Figure \ref{fig:mesh} shows the objects constituting a mesh, the
arrays that contain the attributes and their relationships.
Let $M$ be the total number of triangles and $P$ be the total 
number of points.
Class Points contains an $P \times 2$ floating point array 
representing $x, y$ coordinates of all points entering the 
structure. These are all vertices and centroids. 
Derived midpoints need not be stored.
Class Vectors contains the same kind of data, 
a $3 M \times 2$ floating point array representing $x,y$ coordinates
of normal vectors. Class Vectors can be derived from Class Points.
Class Triangles contains the following arrays
\begin{itemize}
  \item \textbf{vertices:} An $M \times 3$ integer array representing 
  indices into the points array for vertex 0, 1 and 2.
  \item \textbf{centroids:} An $M \times 1$ integer array representing 
  indices into the points array for the centroids.
  \item \textbf{normals:} An $M \times 3$ integer array representing  
  indices into the Vectors array for normal 0, 1 and 2.    
  \item \textbf{neighbours:} An $M \times 3$ integer array representing
  ids of neighbouring triangles. If no neighbouring triangle is present, 
  the corresponding neighbour index will be negative 
  representing a boundary object. See Section \ref{sec:boundaries}.     
  \item \textbf{neighbour\_faces:} An $M \times 3$ integer array representing
  enumerations (0, 1, or 2) of adjacent faces of neighbouring triangles.
  \item \textbf{areas:} An $M \times 1$ floating point 
  array representing the derived geometric property area for each triangle.
  \item \textbf{radii:} An $M \times 1$ floating point 
  array representing the derived geometric property radius for each triangle.  
  \item \textbf{edgelengths:} An $M \times 3$ floating point 
  array representing the derived geometric edgelenghts 0, 1 and 2.
  \item \textbf{number\_of\_boundaries:} Number of absent adjacent triangles.
\end{itemize} 
(FIXME: A proper diagram with both data and methods 
should go in somewhere in this document)



\begin{figure}
\begin{center} 
  \includegraphics[width=0.8\textwidth]{mesh}  
\end{center}
\label{fig:mesh}
\caption{The data structure for a basic mesh (without boundary info).}
\end{figure}


\section{Vertex data structure}

It is convenient to keep a mapping from each point in the mesh to
the triangles and vertex ids occupying them.

.........

Mapping:\\
  Point id: list of (triangle id, vertex id) 




\section{Boundaries}
\label{sec:boundaries}

Tags, boundary objects and more

\end{document}