\subsection{Mesh traversal routines}%
\label{S:traverse}
\idx{mesh traversal|(}

As described before, the mesh is organized in a binary tree, and
most local information is not stored at leaf element level, but is
generated from hierarchical information and macro element data.  The
generation of such local information is done during tree traversal
routines.

When some work has to be done at each tree element or leaf element,
such a tree traversal is most easily done in a recursive way, calling
some special subroutine at each (leaf) element which implements the
operation that currently has to be done. For some other applications,
it is necessary to operate on the (leaf) elements in another fashion,
where a recursive traversal is not possible.
To provide access for both situations, there exist recursive and
non-recursive mesh traversal routines.

For both styles, selection criteria are available to indicate on which
elements the operation should take place. The following constants are
defined:
\cdx{CALL_EVERY_EL_PREORDER@{\code{CALL\_EVERY\_EL\_PREORDER}}}%
\cdx{CALL_EVERY_EL_INORDER@{\code{CALL\_EVERY\_EL\_INORDER}}}%
\cdx{CALL_EVERY_EL_POSTORDER@{\code{CALL\_EVERY\_EL\_POSTORDER}}}%
\cdx{CALL_LEAF_EL@{\code{CALL\_LEAF\_EL}}}%
\cdx{CALL_LEAF_EL_LEVEL@{\code{CALL\_LEAF\_EL\_LEVEL}}}%
\cdx{CALL_EL_LEVEL@{\code{CALL\_EL\_LEVEL}}}%
\cdx{CALL_MG_LEVEL@{\code{CALL\_MG\_LEVEL}}}%
\bv\begin{lstlisting}
CALL_EVERY_EL_PREORDER  
CALL_EVERY_EL_INORDER   
CALL_EVERY_EL_POSTORDER 
CALL_LEAF_EL            
CALL_LEAF_EL_LEVEL
CALL_EL_LEVEL
CALL_MG_LEVEL
\end{lstlisting}\ev
%
  \code{CALL\_EVERY\_EL\_PREORDER}, \code{CALL\_EVERY\_EL\_INORDER},
  and \code{CALL\_EVERY\_EL\_POSTORDER} all three operate on {\em all}
  hierarchical elements of the mesh. These three differ in the
  sequence of operation on elements: \code{CALL\_EVERY\_EL\_PREORDER}
  operates first on a parent element before operating on both
  children, \code{CALL\_EVERY\_EL\_POSTORDER} operates first on both
  children before operating on their parent, and
  \code{CALL\_EVERY\_EL\_INORDER} first operates on \code{child[0]},
  then on the parent element, and last on \code{child[1]}.

\code{CALL\_LEAF\_EL} operates on {\em all\/} leaf elements of the tree,
whereas \code{CALL\_LEAF\_EL\_LEVEL} operates only on leaf elements
which are exactly at a specified tree depth.
\code{CALL\_EL\_LEVEL} operates on all tree elements at a specified tree 
depth. The option \code{CALL\_MG\_LEVEL} is special for multigrid
operations. It provides the operation on all hierarchy elements on a
specified multigrid level (which is usually \code{el->level/DIM}).

Additional flags are defined that specify which local information in
\hyperref[T:EL_INFO]{\code{EL\_INFO}} has to be generated during the
hierarchical mesh traversal. A bitwise \textsf{OR} of some of these
constants is given as a parameter to the traversal routines. These
flags are more or less self explaining (see also \secref{S:EL_INFO}):
\cdx{FILL_NOTHING@{\code{FILL\_NOTHING}}}%
\cdx{FILL_COORDS@{\code{FILL\_COORDS}}}%
\cdx{FILL_BOUND@{\code{FILL\_BOUND}}}%
\cdx{FILL_NEIGH@{\code{FILL\_NEIGH}}}%
\cdx{FILL_OPP_COORDS@{\code{FILL\_OPP\_COORDS}}}%
\cdx{FILL_ORIENTATION@{\code{FILL\_ORIENTATION}}}%
\cdx{FILL_PROJECTION@{\code{FILL\_PROJECTION}}}%
\cdx{FILL_MACRO_WALLS@{\code{FILL\_MACRO\_WALLS}}}%
\cdx{FILL_NON_PERIODIC@{\code{FILL\_NON\_PERIODIC}}}%
\cdx{FILL_MASTER_INFO@{\code{FILL\_MASTER\_INFO}}}%
\cdx{FILL_MASTER_NEIGH@{\code{FILL\_MASTER\_NEIGH}}}%
\cdx{FILL_ANY@{\code{FILL\_ANY}}}
\begin{descr}
  \kitem{FILL\_NOTHING} no information needed at all.
  %% 
  \kitem{FILL\_COORDS} the vertex coordinates \code{EL\_INFO.coord} are
  filled.
  %% 
  \kitem{FILL\_BOUND} the boundary classification
  \code{EL\_INFO.wall\_bound}, \code{EL\_INFO.vertex\_bound} and
  \code{EL\_INFO.edge\_bound} (in 2d and 3d) are filled. If an
  application only needs the boundary classification of the walls of
  an element, then it is probably more efficient to request the
  \code{FILL\_MACRO\_WALLS} fill-flag and call \code{bndry\_type =
    wall\_bound(el\_info, wall)} to obtain this information.
  %% 
  \kitem{FILL\_NEIGH} neighbour element information
  \code{EL\_INFO.neigh} and \code{EL\_INFO.opp\_vertex} is generated.
  %% 
  \kitem{FILL\_OPP\_COORDS} information about opposite vertex coordinates 
  \code{EL\_INFO.opp\_coords} of neighbours is filled;
  the flag \code{FILL\_OPP\_COORDS} can only be selected 
  in combination with \code{FILL\_COORDS|FILL\_NEIGH}.
  %%
  \kitem{FILL\_ORIENTATION} the element orientation info 
  \code{EL\_INFO.orientation} is generated (3d only).
  %%
  \kitem{FILL\_PROJECTION} information about projection routines for
  new vertices is generated using this flag. The entries
  \code{EL\_INFO.active\_projection} are set.
  %%
  \kitem{FILL\_MACRO\_WALLS} the mapping of the local wall-numbers
  (i.e. faces in 3d, edges in 2d, points in 1d) to the numbering of
  the walls on the ambient macro-element is maintained during
  mesh-traversal. The entries \code{EL\_INFO.macro\_wall} are set.
  %%
 \kitem{FILL\_NON\_PERIODIC} for periodic meshes, ignore the periodic
  structure when computing the neighborhood relations and the boundary
  classification.
  %%
  \kitem{FILL\_MASTER\_INFO} for trace-meshes (AKA
  ``slave-meshes''). During mesh-traversal on the trace-mesh generate
  certain information about the ambient ``master''-element. Certain
  fields of \code{EL\_INFO.master} are valid, depending on which other
  traversal flags are set.
  %%
  \kitem{FILL\_MASTER\_NEIGH} for trace-meshes, implies
    \code{FILL\_MASTER\_INFO} explained above. For trace-meshes
    sliding through an ambient bulk-mesh additionally compute
    information about the neighbour of the ambient master-element
    across the wall forming the element on the trace-mesh. Certain
    fields of \code{EL\_INFO.master} are valid, depending on which
    other traversal flags are set.
  %%
 \kitem{FILL\_ANY} macro definition for a bitwise \textsf{OR} of any
  possible fill flags, used for separating the fill flags from the
  \code{CALL\_...} flags.
\end{descr}

During mesh traversal, such information is generated hierarchically
using the two subroutines
\fdx{fill_macro_info()@{\code{fill\_macro\_info()}}}
\fdx{fill_elinfo()@{\code{fill\_elinfo()}}}
\bv\begin{lstlisting}
void fill_macro_info(MESH *, const MACRO_EL *, EL_INFO *);
void fill_elinfo(int, const EL_INFO *, EL_INFO *);
\end{lstlisting}\ev
Description:
\begin{descr}
  \kitem{fill\_macro\_info(mesh, mel, el\_info)} fills \code{el\_info}
  with macro element information of \code{mel} required by
  \code{el\_info->flag} and sets \code{el\_info->mesh} to \code{mesh}; 
\kitem{fill\_elinfo(ichild, parent\_info, el\_info)} fills \code{el\_info} 
  for the child  \code{ichild} using hierarchy information and parent data
  \code{parent\_info} depending on \code{parent\_info->flag}.
\end{descr}

\subsubsection{Sequence of visited elements}

The sequence of elements which are visited during the traversal is
given by the following rules:
\begin{itemize}
\item All elements in the binary mesh tree of one \code{MACRO\_EL mel}
      are visited prior to any element in the tree of the next macro 
      element in the array \code{mesh->macro\_els}.
\item For every \code{EL el}, all elements in the subtree \code{el->child[0]}
      are visited before any element in the subtree \code{el->child[1]}.
\item The traversal order of an element and its two child trees 
      is determined by the flags \code{CALL\_EVERY\_EL\_PREORDER},
      \code{CALL\_EVERY\_EL\_INORDER}, and
      \code{CALL\_EVERY\_EL\_POSTORDER}, as defined above in
      \secref{S:traverse}.
\end{itemize}
This order can only be changed by explicitly calling the 
\code{traverse\_neighbour()} routine during non-recursive traversal, see below.

\subsubsection{Recursive mesh traversal routines}

Recursive traversal of mesh elements is done by the routine
\fdx{mesh_traverse()@{\code{mesh\_traverse()}}}
\bv\begin{lstlisting}
void mesh_traverse(MESH *,int,FLAGS,void (*)(const EL_INFO *,void *),void *);
\end{lstlisting}\ev
Description:
\begin{descr}
\kitem{mesh\_traverse(mesh, level, fill\_flag, el\_fct, data)} traverses
       the mesh \code{mesh}; the argument \code{level} specifies the
       element level if \code{CALL\_EL\_LEVEL} or
       \code{CALL\_LEAF\_EL\_LEVEL}, or the multigrid level if
       \code{CALL\_MG\_LEVEL} is set in the \code{fill\_flag}; 
       otherwise this variable is ignored; 
       by the argument \code{fill\_flag} the elements to be
       traversed and data to be filled into \code{EL\_INFO} is
       selected, using bitwise \textsf{OR} of one \code{CALL\_...} flag
       and several \code{FILL\_...} flags; the argument \code{el\_fct}
       is a pointer to a function which is called on every element
       selected by the \code{CALL\_...} part of \code{fill\_flag}. The pointer 
       \code{data} is used for opaque user data that should be made available 
       to the \code{el\_fct} routine.

       It is possible to use the recursive mesh traversal recursively,
       by calling \code{mesh\_traverse()} from \code{el\_fct}.
\end{descr}

\begin{example}\label{Ex:measure_omega}
An example of a mesh traversal is the computation of the measure
of the computational domain. On each leaf element, the volume
of the element is computed by the library function \code{el\_volume()}
and added to a global variable \code{measure\_omega}, which finally holds
the measure of the domain after the mesh traversal.
%
\bv\begin{lstlisting}
static void measure_el(const EL_INFO *el_info, void *measure_omega)
{
  *((int *)measure_omega) += el_volume(el_info);
  return;
}

...

measure_omega = 0.0;
mesh_traverse(mesh, -1, CALL_LEAF_EL|FILL_COORDS, measure_el, &measure_omega);
MSG("|Omega| = %e\n", measure_omega);
\end{lstlisting}\ev
%
\code{el\_volume()} computes the element volume and thus needs
information about the elements vertex coordinates.
\end{example}

\begin{example}
We give an implementation of the \code{CALL\_EVERY\_EL\_...}
routines to show the simple structure of all recursive
traversal routines. A data structure \code{TRAVERSE\_INFO}, only used by
the traversal routines, holds the traversal flag and a pointer to
the element function \code{el\_fct()}:
%
\bv\begin{lstlisting}
static void recursive_traverse(EL_INFO *el_info, TRAVERSE_INFO *trinfo)
{
  EL      *el = el_info->el;
  EL_INFO el_info_new;

  if (el->child[0]) 
  {
    if (trinfo->flag & CALL_EVERY_EL_PREORDER)  
      trinfo->el_fct(el_info, trinfo->data);

    fill_elinfo(0, el_info, &el_info_new);
    recursive_traverse(&el_info_new, trinfo);

    if (trinfo->flag & CALL_EVERY_EL_INORDER)
      trinfo->el_fct(el_info, trinfo->data);

    fill_elinfo(1, el_info, &el_info_new);
    recursive_traverse(&el_info_new, trinfo);

    if (trinfo->flag & CALL_EVERY_EL_POSTORDER) 
      trinfo->el_fct(el_info, trinfo->data);
  }
  else
  {
    trinfo->el_fct(el_info, trinfo->data);
  }
  return;
}

static void mesh_traverse_every_el(MESH *mesh, FLAGS fill_flag,
                                   void (*el_fct)(const EL_INFO *, void *),
                                   void *data);
{
  EL_INFO       el_info;
  TRAVERSE_INFO traverse_info;
  int           n;

  el_info.fill_flag = (flag & FILL_ANY);
  el_info.mesh = mesh;

  traverse_info.mesh   = mesh;
  traverse_info.el_fct = el_fct;
  traverse_info.flag   = flag;
  traverse_info.data   = data;

  for(n = 0; n < mesh->n_macro_el; n++) {
    fill_macro_info(mesh->macro_els + n, &el_info);
    recursive_traverse(&el_info, &traverse_info);
  }
  return;
}
\end{lstlisting}\ev
\end{example}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Non--recursive mesh traversal routines}

Some applications may profit from or actually require a non--recursive
form of mesh traversal, where the element routine gets pointers to
visited elements, one after another. For example, mesh refinement and
coarsening routines (see Sections
\ref{S:refinement_routines} and \ref{S:coarsening_routines}), the
gltools and GRAPE graphic interface (see Sections
\ref{S:graph_gltools} and \ref{S:graph_GRAPE}) are functions which
use a non--recursive access to the mesh elements.

Note that currently non-recursive level-based traversal indicated by
the traversal flags \code{CALL\_EL\_LEVEL},
\code{CALL\_LEAF\_EL\_LEVEL} or \code{CALL\_MG\_LEVEL} is not implemented.

The implementation of the non--recursive mesh traversal routines uses
a stack to save the tree path from a macro element to the current
element. A data structure \code{TRAVERSE\_STACK} holds such
information.  Before calling the non--recursive mesh traversal
routines, such a stack must be allocated (and passed to the traversal
routines). 
\ddx{TRAVERSE_STACK@{\code{TRAVERSE\_STACK}}}
\bv\begin{lstlisting}
typedef struct traverse_stack   TRAVERSE_STACK;
\end{lstlisting}\ev
By allocating a new stack, it is even possible to recursively call the
non--recursive mesh traversal during another mesh traversal without
destroying the stack which is already in use.
For the non--recursive mesh traversal no pointer to an element
function \code{el\_fct()} has to be provided, because all operations are 
done by the routines which call the traversal functions.
A mesh traversal is launched by each call to \code{traverse\_first()}
which also initializes the traverse stack. Advancing to the
next element is done by the function \code{traverse\_next()}.
The following non--recursive routines are provided:
\begin{samepage}
\fdx{get_traverse_stack()@{\code{get\_traverse\_stack()}}}
\fdx{free_traverse_stack()@{\code{free\_traverse\_stack()}}}
\fdx{traverse_first()@{\code{traverse\_first()}}}
\fdx{traverse_next()@{\code{traverse\_next()}}}
\fdx{TRAVERSE_FIRST()@{\code{TRAVERSE\_FIRST()}}}
\mdx{TRAVERSE_FIRST()@{\code{TRAVERSE\_FIRST()}}}
\fdx{TRAVERSE_NEXT()@{\code{TRAVERSE\_NEXT()}}}
\mdx{TRAVERSE_NEXT()@{\code{TRAVERSE\_NEXT()}}}
\bv\begin{lstlisting}
TRAVERSE_STACK *get_traverse_stack(void);
void free_traverse_stack(TRAVERSE_STACK *staci);
const EL_INFO *traverse_first(TRAVERSE_STACK *stack, MESH *, int level, FLAGS fill_flags);
const EL_INFO *traverse_next(TRAVERSE_STACK *stack, const EL_INFO *el_info);
TRAVERSE_FIRST(MESH *mesh, int level, FLAGS fill_flags);
TRAVERSE_NEXT();
const EL_INFO *subtree_traverse_first(TRAVERSE_STACK *stack,
                                      const EL_INFO *local_root,
                                      int level, FLAGS flags);
\end{lstlisting}\ev
\end{samepage}
Descriptions:
\begin{descr}
  \kitem{get\_traverse\_stack()} returns a pointer to a 
  data structure \code{TRAVERSE\_STACK}.
  \kitem{free\_traverse\_stack(stack)} frees the traverse stack
  \code{stack} previously accessed by \code{get\_traverse\_stack()}.
  \kitem{traverse\_first(stack, mesh, level, fill\_flag)} launches the
  non--recursive mesh traversal; the return value is a pointer
  to an \code{el\_info} structure of the first element to be visited;

  \code{stack} is a traverse stack previously accessed by
  \code{get\_traverse\_stack()}; 

  \code{mesh} is a pointer to a mesh to
  be traversed, \code{level} specifies the element level if
  \code{CALL\_EL\_LEVEL} or \code{CALL\_LEAF\_EL\_LEVEL}, or the
  multigrid level if \code{CALL\_MG\_LEVEL} is set; otherwise this
  variable is ignored; 

  \code{fill\_flag} specifies the elements to
  be traversed and data to be filled into \code{EL\_INFO} is selected,
  using bitwise \textsf{OR} of one \code{CALL\_...} flag and several
  \code{FILL\_...} flags;

  \kitem{traverse\_next(stack, el\_info)} returns an \code{EL\_INFO}
  structure with data about the next element of the mesh traversal
  or a pointer to \nil, if \code{el\_info->el} is the last 
  element to be visited;

  information which elements are visited and which data has to be 
  filled is accessible via the traverse stack \code{stack}, initialized
  by \code{traverse\_first()}. After
  calling \code{traverse\_next()}, all \code{EL\_INFO} information about
  previous elements is invalid, the structure may be overwritten with
  new data.

  \kitem{TRAVERSE\_FIRST(mesh, level, fill\_flags), TRAVERSE\_NEXT()}
  are convenience macros which internally call the functions
  \code{get\_traverse\_stack()}, \code{traverse\_first()},
  \code{traverse\_next()} and \code{free\_traverse\_stack()}.
  \code{TRAVERSE\_FIRST()} defines a local variable with name
  \code{el\_info} which holds the information about the current element.

  \kitem{subtree\_traverse\_first(stack, local\_root, level, flags)}
  Like \code{traverse\_first()}, but restricts the traversal to the
  sub-tree starting at \code{local\_root}. Note that
  \code{local\_root} is saved on the traverse-\code{stack}, so it is
  possible to initiate a sub-tree traversal from within the recursive
  \code{mesh\_traverse()} routines with this function, or from within
  another non-recursive traversal loop, if that uses another
  \code{TRAVERSE\_STACK}.
\end{descr}

Usually, the interface to a graphical environment
uses the non--recursive mesh traversal, compare the gltools
(\secref{S:graph_gltools})
and GRAPE interfaces (\secref{S:graph_GRAPE}).

\begin{example}
\fdx{get_traverse_stack()@{\code{get\_traverse\_stack()}}}
\fdx{free_traverse_stack()@{\code{free\_traverse\_stack()}}}
\fdx{traverse_first()@{\code{traverse\_first()}}}
\fdx{traverse_next()@{\code{traverse\_next()}}}
  The computation of the measure of the computational domain with the
  non--recursive mesh traversal routines is shown in the following
  code segment.
%
\bv\begin{lstlisting}[label=E:nrtraversal]
REAL measure_omega(MESH *mesh)
{
  TRAVERSE_STACK *stack = get_traverse_stack();
  const EL_INFO  *el_info;
  FLAGS          fill_flag;
  REAL           measure_omega = 0.0;

  el_info = traverse_first(stack, mesh, -1, CALL_LEAF_EL|FILL_COORDS);
  while (el_info)
  {
    measure_omega += el_volume(el_info);
    el_info = traverse_next(stack, el_info);
  }
  free_traverse_stack(stack);

  return(measure_omega);
}
\end{lstlisting}\ev
\end{example}

\begin{example}
\fdx{TRAVERSE_FIRST()@{\code{TRAVERSE\_FIRST()}}}
\mdx{TRAVERSE_FIRST()@{\code{TRAVERSE\_FIRST()}}}
\fdx{TRAVERSE_NEXT()@{\code{TRAVERSE\_NEXT()}}}
\mdx{TRAVERSE_NEXT()@{\code{TRAVERSE\_NEXT()}}}
  The same example as above, but implemented with the convenience
  macros \code{TRAVERSE\_FIRST()}, \code{TRAVERSE\_NEXT()}:
%
  \bv\begin{lstlisting}[label=E:simplenrtraversal]
REAL measure_omega(MESH *mesh)
{
  REAL measure_omega = 0.0;

  TRAVERSE_FIRST(mesh, -1, CALL_LEAF_EL|FILL_COORDS) {
    measure_omega += el_volume(el_info);
  } TRAVERSE_NEXT();
  return measure_omega;
}
\end{lstlisting}\ev
\end{example}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Neighbour traversal}

Some applications, like the recursive refinement algorithm, need the
possibility to jump from one element to another element using
neighbour relations. Such a traversal can not be performed by the
recursive traversal routines and thus needs the non--recursive mesh
traversal.
The traversal routine for going from one element to a neighbour is
\fdx{traverse_neighbour()@{\code{traverse\_neighbour()}}}%
\bv\begin{lstlisting}
EL_INFO *traverse_neighbour(TRAVERSE_STACK *, EL_INFO *, int);
\end{lstlisting}\ev
Description:
\begin{descr}
\kitem{traverse\_neighbour(stack, el\_info, i)} returns 
a pointer to an \code{EL\_INFO} structure with information about the
\code{i}-th neighbour opposite the \code{i}-th
vertex  of \code{el\_info->el};

The function can be called at any time during the non--recursive 
mesh traversal after initializing the first element by 
\code{traverse\_first()}.

Calling \code{traverse\_neighbour()}, all
\code{EL\_INFO} information about a previous element is invalid, and
can only be regenerated by calling \code{traverse\_neighbour()} again
with the \emph{old\/} \code{OPP\_VERTEX} value. If called at the
boundary, when no adjacent element is available, then the routine
returns \nil; nevertheless, information from the old \code{EL\_INFO}
may be overwritten and lost. To avoid such behavior, one should check
for boundary vertices/edges/faces (1d/2d/3d) before calling 
\code{traverse\_neighbour()}.
\end{descr}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Access to an element at world coordinates $x$}

Some applications need the access to elements at a special location in
world coordinates. Examples are characteristic methods for convection
problems, or the implementation of a special right hand side like point
evaluations or curve integrals. 
In a characteristic method, the point $x$ is usually given by 
$x = x_0 - \vec{V} \tau$, where $x_0$ is the starting point,
$\vec{V}$ the advection and $\tau$ the time step size. For
points $x_0$ close to the boundary it may happen that
$x$ does not belong to the computational domain. In this situation
it is convenient to know the point on the domain's boundary which lies on
the line segment between the old point $x_0$ and the new point
$x$. This point is uniquely determined by the scalar value
$s$ such that $x_0 + s \, (x - x_0) \in \partial\text{Domain}$.

The following function accesses an element at world coordinates $x$:
\fdx{find_el_at_pt()@{\code{find\_el\_at\_pt()}}}
\bv\begin{lstlisting}
int find_el_at_pt(MESH *, const REAL_D, EL_INFO **, FLAGS, REAL [N_LAMBDA],
                  const MACRO_EL *, const REAL_D, REAL *);
\end{lstlisting}\ev
Description:
\begin{descr}
\kitem{find\_el\_at\_pt(mesh, x, el\_info\_p, fill\_flag, bary, start\_mel, x0, sp)}
fills element information in an \code{EL\_INFO} structure and 
corresponding barycentric coordinates
of the element where the point \code{x} is located; the return value is 
\code{true} if \code{x} is inside the domain, or \code{false} otherwise.
Arguments of the function are:

\code{mesh} is the mesh to be traversed;

\code{x} are the world coordinates of the point (should be in the domain
         occupied by \code{mesh});

\code{el\_info\_p} is the return address for a pointer to the
             \code{EL\_INFO} for the element at \code{x} (or when \code{x} is
             outside the domain but \code{x0} was given, of the element
             containing the point
             $x_0 + s \, (x - x_0) \in \partial\text{Domain}$);

\code{fill\_flag} are the flags which specify which information should be
             filled in the \code{EL\_INFO} structure,
             coordinates are included in any case as they are needed
             by the routine itself;

\code{bary} pointer where to return the barycentric coordinates of \code{x} on 
            \code{*el\_info\_p->el} (or, when \code{x} is
             outside the domain but \code{x0} was given, of the point
             $x_0 + s \, (x - x_0) \in \partial\text{Domain}$);

\code{start\_mel} an initial guess for the macro element containing \code{x},
             or \nil;

\code{x0}   starting point of a characteristic method, see above, or \nil;

\code{sp}   return address for the relative distance to domain boundary in a 
             characteristic method if \code{x0 != nil}, see above, or \nil.
\end{descr}

The implementation of \code{find\_el\_at\_pt()} is based on the
transformation from world to local coordinates, available via the
routine \code{world\_to\_coord()}, compare Section
\ref{S:bary_routines}.  At the moment, \code{find\_el\_at\_pt()} works
correctly only for domains with non--curved boundary. This is due to
the fact that the implementation first looks for the macro--element
containing \code{x} and then finds its path through the corresponding
element tree based on the macro barycentric coordinates. For domains
with curved boundary, it is possible that in some cases a point inside
the domain is considered as external.
\idx{mesh traversal|)}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "alberta-man"
%%% End: