mesh.tex

\label{chap:diving-into-problem}
We begin by walking through an example mesh and examining the properties of the structure found within.

\section{A basic definition of structure}
What we would like is a form of structure which is
\begin{enumerate*}[label=\alph*)]
\item representable as a data structure, and \item efficient in terms of performance.
\end{enumerate*}

Given our semantic knowledge about the mesh model we can ascertain some facts about relation-maps:
\begin{itemize}
\item They are sparse: element arity is very small compared to the number of elements, and is in fact unrelated to it.
\item They have a high clustering coefficient: Relationships tend to be localized, forming tightly connected clusters.
% TODO REFERENCE TO CLUSTERING COEFFICIENTS
\end{itemize}

These properties arise as a consequence of meshes modelling real-world phenomena that exist in a Cartesian space.
On this basis, we consider a spatial embodiment of element relationships, organising the elements in a discrete space such that the uniform relationship is apparent.

Bear in mind that this approach carries no relation to any geometric data associated with elements, such as the coordinates of vertices. To make this distinction clear, as well as to emphasize its discrete nature, we address this Cartesian-like space by rows and columns rather than x and y coordinates.

\subsection{Example: Naca0012 mesh}
Figure~\ref{fig:naca12-plain} shows a small extract from the NACA0012 mesh\footnote{Thanks to Dr. Peter Vincent, George Ntemos and Harry Davis}, showing the cross section of an airfoil mesh and its interaction with surrounding fluid. The mesh is discretized into quadrilateral cells over which computations are performed.

\newcommand{\drawnaca}[4]{
	\begin{figure}
	\includesvg[svgpath=#1]{#2}
	\caption{#3}
	\label{#4}
	\end{figure}
}
\drawnaca{images/defining-structure/}{naca0012-plain}{Extract of the NACA0012 mesh.}{fig:naca12-plain}

The vertices in the highlighted region of figure~\ref{fig:naca12-vertices} seem like good candidates for a \emph{``structured region''}, forming a two-dimensional lattice in a discrete Cartesian space. This \emph{``structured region''} has the properties outlined below.

\drawnaca{images/defining-structure/}{naca0012-node-structure}{Highlighted vertices which exhibit a form of \emph{``structured region''}.}{fig:naca12-vertices}

\subsection{Desired properties of a structured region}
\label{sec:structured-region-properties}
\begin{enumerate}
\item All vertices have a uniform arity of four.
\item Every vertex has a consistent discrete direction (for example the cardinal directions: north east, south, west) with respect to the other vertices. In other words, the direction is transitive: if vertex $a$ is above vertex $b$, and vertex $b$ is above vertex $c$, then vertex $a$ is above vertex $c$. For a non-example see figure~\ref{fig:non-consistent-direction}.
\end{enumerate}

\begin{figure}
\includesvg[width=\imagewidth, svgpath=images/defining-structure/]{non-consistent-direction}
\caption{An example of inconsistent direction. We can traverse cells in \emph{``one direction''} by following the edge parallel to the one we entered from. If we start from $A$ and traverse the cells in one direction (the blue path) we reach $Z$. If we start from $A$ and traverse the cells in an orthogonal direction (the red path) to the first path, we also reach $Z$! Is $Z$ then \emph{``above''} $A$ or \emph{``to the side of it''}?}
\label{fig:non-consistent-direction}
\end{figure}


%% TODO Maybe not introduce data structure yet????
We can propagate this inherent structure from the mesh model to the underlying data structure, representing this two-dimensional lattice using a two-dimensional array. Vertices may be assigned Cartesian coordinates, but in spirit of the space's discreteness we shall use rows and columns instead. See figure~\ref{fig:naca12-structure-grid}.\label{sentence:2d-array}

\drawnaca{images/defining-structure/}{naca0012-node-grid}{The overlaid grid shows the lattice structure more clearly.}{fig:naca12-structure-grid}


\newcommand{\strV}{V_{str}}
\newcommand{\adjstrV}{V_{adjstr}}
\newcommand{\AdjVVstr}{Adj_{\adjstrV\strV}}

Let us call $\VertexSet$ the set of all vertices, and $\strV \subseteq \VertexSet$ the set of vertices in the \emph{``structured region''}.

\subsection{Representing the vertex-vertex adjacency}

Now consider the vertex-vertex adjacency relation $\AdjVV: \VertexSet \mapsto \VertexSet$ in context of the \emph{``structured region''} $\strV$. We can directly locate a particular neighbour of any vertex, for example its north neighbour, so long as that neighbour is also within the structured region. This restricts the set of vertices with fully-accessible neighbours to those which are not on the borders or the fringe of the \emph{``structured region''}. This is the subset of vertices $\adjstrV \subseteq \strV$ which are structured \emph{with respect to} $\AdjVV$. This induces a new relation which operates purely within the structured region:
$$\AdjVVstr: \adjstrV \mapsto \strV$$

Figures~\ref{fig:naca12-structured-highlighted} and~\ref{fig:structure-as-graph} illustrate these two sets.
\drawnaca{images/defining-structure/}{naca0012-node-neighbours}{The interior structured vertices (those not on the fringe) are highlighted in dark blue.}{fig:naca12-structured-highlighted}


\begin{figure}
% Draw structured node region
\begin{tikzpicture}[scale=0.7]
	\newcommand{\stylewithfill}[1]{\tikzstyle{every node}=[draw, shape=circle, minimum size=0.8cm, fill=#1];}
	\stylewithfill{none}

	% ROW 0
	\drawgrid{rows=1, cols=3, rowoffset=0, coloffset=4, labeler=\plainlabelnode, labelerA=0, labelerB=2,
		southborder=structured}

	% ROW 1
	\drawgrid{rows=1, cols=2, rowoffset=-2, coloffset=0, labeler=\plainlabelnode, labelerA=1, labelerB=0,
		eastborder=structured}

	{
	\stylewithfill{neighbourstructurecolor}
	\drawgrid{rows=1, cols=2, rowoffset=-2, coloffset=4, labeler=\plainlabelnode, labelerA=1, labelerB=2,
		northborder=structured, southborder=structured, westborder=structured, eastborder=structured}
	}

	\drawgrid{rows=1, cols=1, rowoffset=-2, coloffset=8, labeler=\plainlabelnode, labelerA=1, labelerB=4,
		northborder=structured, southborder=structured, westborder=structured}


	\drawgrid{rows=1, cols=1, rowoffset=-2, coloffset=12, labeler=\plainlabelnode, labelerA=1, labelerB=6,
		southborder=structured, eastborder=structured}

	\drawgrid{rows=1, cols=1, rowoffset=-2, coloffset=14, labeler=\plainlabelnode, labelerA=1, labelerB=7,
		westborder=structured}

	% ROW 2
	\drawgrid{rows=1, cols=1, rowoffset=-4, coloffset=4, labeler=\plainlabelnode, labelerA=2, labelerB=2,
		northborder=structured, southborder=structured, eastborder=structured}

	{
	\stylewithfill{neighbourstructurecolor}
	\drawgrid{rows=1, cols=2, rowoffset=-4, coloffset=6, labeler=\plainlabelnode, labelerA=2, labelerB=3,
		northborder=structured, southborder=structured, eastborder=structured, westborder=structured}
	}

	\drawgrid{rows=1, cols=1, rowoffset=-4, coloffset=10, labeler=\plainlabelnode, labelerA=2, labelerB=5,
		southborder=structured, westborder=structured, eastborder=structured}

	\drawgrid{rows=1, cols=1, rowoffset=-4, coloffset=12, labeler=\plainlabelnode, labelerA=2, labelerB=6,
		northborder=structured, westborder=structured}

	% ROW 3
	\drawgrid{rows=1, cols=1, rowoffset=-6, coloffset=4, labeler=\plainlabelnode, labelerA=3, labelerB=2,
		northborder=structured, southborder=structured, eastborder=structured}

	{
	\stylewithfill{neighbourstructurecolor}
	\drawgrid{rows=1, cols=2, rowoffset=-6, coloffset=6, labeler=\plainlabelnode, labelerA=3, labelerB=3,
		northborder=structured, southborder=structured, eastborder=structured, westborder=structured}
	}

	\drawgrid{rows=1, cols=1, rowoffset=-6, coloffset=10, labeler=\plainlabelnode, labelerA=3, labelerB=5,
		northborder=structured, westborder=structured}

	% ROW 4
	\drawgrid{rows=1, cols=1, rowoffset=-8, coloffset=2, labeler=\plainlabelnode, labelerA=4, labelerB=1, eastborder=structured}

	{
	\stylewithfill{neighbourstructurecolor}
	\drawgrid{rows=1, cols=2, rowoffset=-8, coloffset=4, labeler=\plainlabelnode, labelerA=4, labelerB=2,
		northborder=structured, southborder=structured, eastborder=structured, westborder=structured}
	}

	\drawgrid{rows=1, cols=1, rowoffset=-8, coloffset=8, labeler=\plainlabelnode, labelerA=4, labelerB=4,
		northborder=structured, westborder=structured}

	% ROW 5
	\drawgrid{rows=1, cols=2, rowoffset=-10, coloffset=4, labeler=\plainlabelnode, labelerA=5, labelerB=2,
		northborder=structured}
\end{tikzpicture}
\caption{The vertices in figure~\ref{fig:naca12-structured-highlighted} represented as a graph.}
\label{fig:structure-as-graph}
\end{figure}

The key insight we make is that for structured regions in a mesh we need not represent set relationship maps explicitly; the uniformity of set relations allows us to deduce the relationships. We can encode the relation $\AdjVVstr$ very simply. Given a vertex $n_{r,c} \in \adjstrV$, located at row $r$ and column $c$, its four vertex neighbours are $n_{r,c-1}$, $n_{r,c+1}$, $n_{r-1,c}$, and $n_{r+1,c}$. This is illustrated in figure~\ref{fig:single-vertex-neighbours}.



\begin{figure}
% Draw structured node region
\begin{tikzpicture}[scale=1]
	\newcommand{\stylewithfill}[1]{\tikzstyle{every node}=[draw, shape=circle, minimum size=1.3cm, fill=#1];}
	\stylewithfill{none}

	% ROW 0
	\drawgrid{rows=1, cols=1, rowoffset=0, coloffset=2,
		labeler=\varlabelnode, labelerA=-1, labelerB=0, labelerC=r, labelerD=c,
		southborder=structured}

	% ROW 1
	\drawgrid{rows=1, cols=1, rowoffset=-2, coloffset=0,
		labeler=\varlabelnode, labelerA=0, labelerB=-1, labelerC=r, labelerD=c,
		eastborder=structured}

	{
		\stylewithfill{neighbourstructurecolor}
		\drawgrid{rows=1, cols=1, rowoffset=-2, coloffset=2,
			labeler=\varlabelnode, labelerA=0, labelerB=0, labelerC=r, labelerD=c,
			eastborder=structured, westborder=structured, northborder=structured, southborder=structured}
	}

	\drawgrid{rows=1, cols=1, rowoffset=-2, coloffset=4,
		labeler=\varlabelnode, labelerA=0, labelerB=1, labelerC=r, labelerD=c,
		westborder=structured}

	% ROW 2
	\drawgrid{rows=1, cols=1, rowoffset=-4, coloffset=2,
		labeler=\varlabelnode, labelerA=1, labelerB=0, labelerC=r, labelerD=c,
		northborder=structured}

\end{tikzpicture}
\caption{The neighbours of a structured vertex.}
\label{fig:single-vertex-neighbours}
\end{figure}


\section{Mesh structure as a data structure}
The choice of data structure to represent the structured region is a key one, touching on various aspects:
\begin{itemize}
\item Scope of structure representation: what level of structure can be represented.
\item Implementation complexity of structure detection: how complex a detection algorithm is required.
\item Runtime performance of structure detection: the time and space complexity of the detection algorithm.
\item Storage requirements for detected structure.
\item Runtime performance of computation over the structured region.
\end{itemize}

We analyse several possible data structure representations.

\subsection{Structure bit-mask}
\label{subsec:structure-bitmap}

\newcommand{\drawbitmap}[2]{
	% trim left bottom right top
	\includesvg[svgpath=#1]{#2}
}

Represent the bounding box around the structured region as a two-dimensional bit-mask, with each bit representing a vertex position in the superimposed grid. An \emph{on} bit indicates that the corresponding vertex is part of the structured region, an \emph{off} bit otherwise.

A bit-mask can represent \emph{any} structured region which adheres to the properties listed in section~\ref{sec:structured-region-properties}. They are very flexible, capable of representing complex formations as well as handling small anomalies in structure.

Let us define the \emph{efficiency} $\epsilon$ of a bit-mask as the percentage of its bits which are \emph{on}, as the \emph{off} bits represent wasted vertices. Bit-masks with high $\epsilon$ are favourable for several reasons:
\begin{itemize}
\item \emph{Off} bits increase the storage space of the structured region, up to $O(\card{\VertexSet})$ in the worst case, as opposed to $O(\card{\strV})$.
\item \emph{Off} bits similarly worsen the runtime performance, again up to $O(\card{\VertexSet})$ due to wasted execution.
\end{itemize}

Figure~\ref{fig:example-bitmask} shows an example of a good bit-mask candidate.

\begin{figure}
\pgfplotstableread{
	1 1 1 1 1 1
	1 2 2 1 1 1
	1 1 2 1 1 2
	1 1 1 1 1 1
	1 1 1 1 1 2
	2 1 1 1 1 1
}{\bitmapmatrix}
\drawmatrix[cell wd=0.8, cell ht=0.8]{\bitmapmatrix}
\caption{An example of a structured region which can be bit-mask defined. The dotted regions indicate unstructured cells. The blue cells are structured cells. Its efficiency $\epsilon$ is $\frac{30}{36} \approx 83\%$.}
\label{fig:example-bitmask}
\end{figure}

A detection algorithm would likely be implemented using a variant of a general graph search algorithm such as breadth-first search or depth-first search. Further consolidation work may be needed to compact disconnected structured components in order to maximize $\epsilon$. The potential benefits of compaction are illustrated in figure~\ref{fig:disjoint-matrix}.

\begin{figure}
\pgfplotstableread{
	2 2 2 2 2 1
	1 2 2 2 2 1
	1 1 2 2 2 2
	2 1 2 2 2 2
	2 1 2 1 2 2
	2 1 1 1 2 2
}{\disjointAmatrix}
\pgfplotstableread{
	1 2 2 1
	1 1 2 1
	2 1 2 2
	2 1 2 1
	2 1 1 1
}{\disjointBmatrix}

\sidebyside
{
\drawmatrix[cell wd=0.8, cell ht=0.8]{\disjointAmatrix}
\caption{Originally detected structured components.}
\label{subfig:original-components}
}
{
\drawmatrix[cell wd=0.8, cell ht=0.8]{\disjointBmatrix}
\caption{Compacted structured components.}
\label{subfig:compacted-components}
}
\caption{A demonstration of the benefits of disconnected structured components compaction. The detected structured cell components in~\ref{subfig:original-components} are unnecessarily sparse and occupy more space than necessary. After compaction in~\ref{subfig:compacted-components} the space is used is reduced by over 40\%.}
\label{fig:disjoint-matrix}
\end{figure}


\subsection{Row-specific boundaries}

Represent the structured region as a sequence of consecutive fixed-length rows, permitting vertices outside the structured region to cluster at the beginning and ends of each row. A structured region is then represented by the row-length, as well as individual begin and end offsets for each row. This is exemplified in figure~\ref{fig:row-specific}.

\begin{figure}
\pgfplotstableread{
	0 2 1 1 1 1
	2 2 1 1 1 2
	1 1 1 1 2 0
	2 1 1 1 1 1
	1 1 1 1 1 1
	2 2 1 1 2 2
}{\bitmapmatrix}
\drawmatrix[cell wd=0.8, cell ht=0.8]{\bitmapmatrix}
\caption{An example of a structured region which can be represented using row-specific boundaries. Note the white cells, which represent unused structured regions near the boundaries, which cannot be included as part of the structured region due to the constraints imposed.}
\label{fig:row-specific}
\end{figure}

Storing row-specific boundaries reduces the storage requirement by the order of row-length times.
No executions are wasted as the loop iterations are constrained to vertices in the structured region.
A detection algorithm can be implemented as a simple row-by-row traversal in linear time and space.


On the downside, this scheme trades some of the flexibility offered by the bit-mask representation, in particularly anomalies in structure which do not occur at the boundaries.


\subsection{Full rectangle}

Represent the structured region as a rectangle of given length and width, with all elements corresponding strictly to vertices within the structured region. The structured region is thus simply represented by the length and the width: the number of rows and the number of columns. Figure~\ref{fig:rectangle} shows an example of a rectangle-representable structured region.

The storage requirement is now constant with respect to the size of the structured region.
Loop iterations are fixed for each region, enabling further optimisation opportunities.
A detection algorithm, as above, can be implemented as a simple row-by-row traversal.

On the downside, the scope of structure representable is limited, being only capable of representing rectangles proper. Nonetheless, we stick with detecting rectangular structured regions for the remainder of this work as it seems to be the most promising choice.

\begin{figure}
\pgfplotstableread{
	0 2 2 0 2 0
	2 2 1 1 2 2
	2 0 1 1 2 2
	2 2 1 1 0 0
	0 2 1 1 2 2
	2 2 1 1 2 2
}{\bitmapmatrix}
\drawmatrix[cell wd=0.8, cell ht=0.8]{\bitmapmatrix}
\caption{An example of a rectangular structured region. Note the abundance of unused structured cells.}
\label{fig:rectangle}
\end{figure}

\section{Chapter summary}
In this chapter we derived intuitive definitions structure in a mesh in light of an excerpt from an airfoil mesh. We also discussed different representations in which they can be manifested, and the advantages and disadvantages of each.