(Difference between revisions)
 Revision as of 15:12, 14 August 2012GeordieMcBain (Talk | contribs) (→FTT_OPPOSITE_DIRECTION(direction) - set snippets of code in tags)← Previous diff Current revisionGeordieMcBain (Talk | contribs) (→Fast location - decorated navigation in footer; put a code snippet in a tag) Line 410: Line 410: === Fast location === === Fast location === - Have a look at the source of ''ftt_cell_locate()'' and find out how it manages to find the cell position efficiently in log(''n'') operations by using the topology of the tree. + Have a look at the source of ftt_cell_locate() and find out how it manages to find the cell position efficiently in log(''n'') operations by using the topology of the tree. ---- ---- - Go to [[ Gerris Flow Solver Programming Course for Dummies | course top level]]. Go to [[The Fluid Domain | next Session]]. + ⇐ '''previous''': [[Introduction to Gerris Programming]], ⇑ '''up''': [[Gerris Flow Solver Programming Course for Dummies]], ⇒ '''next''': [[The Fluid Domain]].

## Introduction to Fully Threaded Trees

Figure 1

An octree is a data structure in which each cell may have up to eight children cell, corresponding to eight cubic subcells in three dimensions. The corresponding two-dimensional structure is a quadtree. The cells and tree structure of the quadtree are illustrated on Figure 1.

In the fully threaded tree implementation of the octree by Khokhlov the data structure contains, in each cell, a reference to the neighbors of the cell. This speeds up considerably the computation of the addresses of neighbor cells; since otherwise in the worst case scenario finding a neighbor cell implies going all the way up the tree to the root cell and then down again.

## FTT library

The files ftt.c and ftt.h form a kind of "ftt library" that is completely independent from the rest of Gerris. The "data" member in FttCell is used so that the logical structure of the quadtree is entirely abstracted from its use in Gerris; i.e. the FTT implementation could be used as-is for an entirely different application requiring an octree.

## Description of the FTT interface

At this stage it is important to recall the distinction we made in the previous session between the public parts of the code and the private parts. The file ftt.h provides the interfaces for a number of public functions, macros, and structures which are meant to be used elsewhere in the code. At this stage of the analysis of Gerris, we only need to know about the public aspects.

The description should logically involve three or four aspects. The prerequisite is a knowledge of the idea of the Fully Threaded Tree with oriented faces as shown above. The three other aspects are the descriptions of structures, macros and functions.

This description is available from the Reference Manual. Notice that the manual respects the `/*< public >*/` and `/*< private >*/` tags: as in our table below, it will only show the public members of the structures.

However, not all the structures and macros have descriptions and other descriptions may not cure the bafflement of us dummies. In the previous section we have given some definitions and comments for some of the functions and macros. Now we try a more systematic approach.

## Description of the Public Members of the Basic Structures

These are the most important public structures.

 Public members Structure Type guint flags gpointer data FttCell cell, neighbor FttDirection d FttCell cell FttCellNeighbors neighbors FttVector pos guint level gpointer parent FttCell * c[FTT_CELLS] FttCell * c[FTT_NEIGHBORS]

## Basic concepts

### FttDirection

`typedef enum{  FTT_RIGHT = 0,  FTT_LEFT,  FTT_TOP,  FTT_BOTTOM,#if (!FTT_2D)  FTT_FRONT,  FTT_BACK,#endif /* FTT_3D */  FTT_NEIGHBORS} FttDirection;`

An orientation is defined in Gerris by the `FttDirection` enum. As shown just above, the different directions (`FTT_RIGHT`, `FTT_LEFT`,…) are associated with an integer: `FTT_RIGHT` with 0, `FTT_LEFT` with 1 and so on. The number of neighbors `FTT_NEIGHBORS` is thus associated with 4 in 2D and 6 in 3D.

### FttCellFace

Figure 2
`struct _FttCellFace {  FttCell * cell, * neighbor;  FttDirection d;};`

A face is oriented: it belongs to one `FttCell` (pointed to by) `cell` and has another as `neighbor` in `FttDirection d`. In other words, a face has an interior and an exterior. There is a corresponding reversed face. As a result the right face of Cell A is not the same object in the program as the left face of Cell B (Figure 2). This is useful for instance when programming the advection scheme when two states (the left and the right state) are present on the same boundary between cells.

### _FttOct

This is the structure tag (it is not a type, only a tag) associated with the private members of the struct `_FttCell`. There is no type `FttOct` associated to `_FttOct`. Both facts indicate that the structure `FttOct` is not meant to be used outside of the ftt library: it is a private part. Other implementations of the library could be possible, not using the `_FttOct`.

Of course the particular implementation here is important as it allows to find neighbors rapidly. But we need not know how it is done to use it, we can use it as a black box.

## Numbering of FttCellChildren when refining

### 2D case

Figure 3: 2D numbering

When the 2D tree is traversed, the `FttCellChildren` are numbered in Z-order, from left to right and then from top to bottom (see Figure 3).

This order is of course the one followed by Gerris to search the tree or apply a function to some cells at levels higher than 0 (root level).

### 3D case

Figure 4: 3D numbering

When the 3D tree is traversed, the `FttCellChildren` are numbered from left to right, then from top to bottom and finally from front to back (see Figure 4).

## Introduction to public functions and macros

Here we give some examples of often used functions and their description. Some of the descriptions may be found in the Reference Manual, but at present some other definitions are not there. As we show below in the case of FTT_OPPOSITE_DIRECTION the meaning is however often easy to guess.

### FTT_FACE_DIRECT (face)

This says how a face is oriented. It returns true if the face orientation is direct. Direct is RIGHT (towards positive x), TOP (towards positive y) or FRONT (towards positive z).

### ftt_face_type(face)

There are three types :

• `FTT_FINE_FINE` when the neighbor is as fine as the cell .
• `FTT_FINE_COARSE` when the neighbor is coarser than the cell
• `FTT_BOUNDARY` when there is no neighbor.

The situation where the neighbor is finer than the cell cannot occur; if there are finer children cells across the face, the neighbor is defined as the contiguous cell at the same level. For instance if a leaf cell A has four neighboring finer leaf cells B, C, D, E the parent B+C+D+E of these four leaf cells is the neighbor of cell A .

The function gfs_face_upwinded_value fails if the face is of type `FTT_BOUNDARY`. (Look at the source code).

### FTT_OPPOSITE_DIRECTION(direction)

If you had to guess what `FTT_OPPOSITE_DIRECTION` does, what would you say? Well if you know that `face->d` is a direction and you guess that it takes a direction as argument and returns the opposite: left for right, bottom for top etc.… And you are right!

### Traversing the tree

An important operation is the traversal of the tree. It allows to perform a sequence of calls of a given function, one call for each cell of a tree.

`/** * ftt_cell_traverse: * @root: the root #FttCell of the tree to traverse. * @order: the order in which the cells are visited - %FTT_PRE_ORDER, * %FTT_POST_ORDER.  * @flags: which types of children are to be visited. * @max_depth: the maximum depth of the traversal. Cells below this * depth will not be traversed. If @max_depth is -1 all cells in the * tree are visited. * @func: the function to call for each visited #FttCell. * @data: user data to pass to @func. * * Traverses a cell tree starting at the given root #FttCell. Calls * the given function for each cell visited.   */void ftt_cell_traverse (FttCell * root,			FttTraverseType order,			FttTraverseFlags flags,			gint max_depth,			FttCellTraverseFunc func,			gpointer data)`

The comments above the function definition explain what it does.

## The whole FTT "library"

By now you should be getting and idea of the meaning of the various macros and modules of the FTT. Listed below are all the "public" functions and macros of FTT. You should now do the following exercise. For each item in the list below, either look up its meaning in the Reference Manual , or find the meaning by looking at the source code. In some cases it would be helpful to supplement the comments in the Reference Manual by some additional considerations, add them where necessary.

Not all the comments in Reference Manual can be found in the source code. Some were added by hand. Conversely, not all macros and functions are referenced in the Reference Manual, although some functions that I have not found in the Reference Manual have comment headers in the source code.

The list is rather long. Things can be accelerated by considering that some functions have obvious definitions. If you have a doubt on the operation of a function, you can always return to it later when you encounter it in other parts the code. Moreover, most of the functions not referenced in the Reference Manual are at the beginning of the list.

`#define  FTT_ROOT_CELL(c)        #define  FTT_CELL_ID(c)          #define  FTT_CELL_IS_LEAF(c)     #define  FTT_CELL_IS_ROOT(c)     #define  FTT_CELL_IS_DESTROYED(c)#define  FTT_FACE_DIRECT(f)     #define  FTT_FACE_REVERSE(dst, src)#define FTT_OPPOSITE_DIRECTION(d)   #define FTT_ORTHOGONAL_COMPONENT(c) FttCell * ftt_cell_new(FttCellInitFunc init,gpointer data);#define ftt_cell_level(c)  #define ftt_cell_parent(c) #define ftt_cell_dz(c)      gdouble ftt_level_size (guint level)gdouble ftt_cell_volume (const FttCell * cell)void ftt_cell_children (const FttCell * cell,			FttCellChildren * children)guint ftt_cell_children_direction (const FttCell * cell,				   FttDirection d,				   FttCellChildren * children)FttCell * ftt_cell_child_corner (const FttCell * cell,				 FttDirection d[FTT_DIMENSION])void ftt_cell_neighbors_not_cached (const FttCell * cell,				    FttCellNeighbors * neighbors)FttCell * ftt_cell_neighbor_not_cached (const FttCell * cell,					FttDirection d)void ftt_cell_neighbors (const FttCell * cell,			 FttCellNeighbors * neighbors)FttCell * ftt_cell_neighbor (const FttCell * cell,			     FttDirection d)FttCell * ftt_cell_neighbor_not_cached (const FttCell * cell,					FttDirection d)FttCellFace ftt_cell_face (FttCell * cell,			   FttDirection d)FttFaceType ftt_face_type (const FttCellFace * face)gboolean ftt_cell_neighbor_is_brother (FttCell * cell, 				       FttDirection d)guint                ftt_cell_depth                  (const FttCell * root);void                 ftt_cell_set_neighbor           (FttCell * root,						      FttCell * neighbor,						      FttDirection d,						      FttCellInitFunc init,						      gpointer init_data);void                 ftt_cell_set_neighbor_match     (FttCell * root,						      FttCell * neighbor,						      FttDirection d,						      FttCellInitFunc init,						      gpointer init_data);void                 ftt_cell_relative_pos           (const FttCell * cell,						      FttVector * pos);void                 ftt_cell_pos                    (const FttCell * cell,						      FttVector * pos);void                 ftt_corner_relative_pos         (const FttCell * cell,						      FttDirection d[FTT_DIMENSION],						      FttVector * pos);void                 ftt_corner_pos                  (const FttCell * cell,						      FttDirection d[FTT_DIMENSION],						      FttVector * pos);void                 ftt_face_pos                    (const FttCellFace * face,						      FttVector * pos);void                 ftt_cell_set_pos                (FttCell * root,						      const FttVector * pos);void                 ftt_cell_set_level              (FttCell * root,						      guint level);void                 ftt_cell_draw                   (const FttCell * cell,						      FILE * fp);void                 ftt_face_draw                   (const FttCellFace * face,						      FILE * fp);gboolean             ftt_cell_check                  (const FttCell * cell);typedef gboolean  (* FttCellRefineFunc)              (FttCell * cell,						      gpointer data);void                 ftt_cell_refine                 (FttCell * root,						      FttCellRefineFunc refine,						      gpointer refine_data,						      FttCellInitFunc init,						      gpointer init_data);void                 ftt_cell_refine_single          (FttCell * cell,						      FttCellInitFunc init,						      gpointer init_data);gboolean             ftt_refine_corner               (const FttCell * cell);void                 ftt_cell_traverse               (FttCell * root,						      FttTraverseType order,						      FttTraverseFlags flags,						      gint max_depth,						      FttCellTraverseFunc func,						      gpointer data);void                 ftt_cell_traverse_condition     (FttCell * root,						      FttTraverseType order,						      FttTraverseFlags flags,						      gint max_depth,						      FttCellTraverseFunc func,						      gpointer data,						      gboolean (* condition) (FttCell *, 									      gpointer),						      gpointer cdata);void                 ftt_cell_traverse_box           (FttCell * root,						      GtsBBox * box,						      FttTraverseType order,						      FttTraverseFlags flags,						      gint max_depth,						      FttCellTraverseFunc func,						      gpointer data);void                 ftt_cell_traverse_boundary      (FttCell * root,						      FttDirection d,						      FttTraverseType order,						      FttTraverseFlags flags,						      gint max_depth,						      FttCellTraverseFunc func,						      gpointer data);typedef void      (* FttFaceTraverseFunc)            (FttCellFace * face, 						      gpointer data);void                 ftt_face_traverse               (FttCell * root,						      FttComponent c,						      FttTraverseType order,						      FttTraverseFlags flags,						      gint max_depth,						      FttFaceTraverseFunc func,						      gpointer data);void                 ftt_face_traverse_boundary      (FttCell * root,						      FttDirection d,						      FttTraverseType order,						      FttTraverseFlags flags,						      gint max_depth,						      FttFaceTraverseFunc func,						      gpointer data);FttCell *            ftt_cell_locate                 (FttCell * root,						      FttVector target,						      gint max_depth);gdouble              ftt_cell_point_distance2_min    (FttCell * cell, 						      GtsPoint * p);void                 ftt_cell_point_distance2_internal (FttCell * root,							GtsPoint * p,							gdouble d,							gdouble (* distance2) (FttCell *, 									       GtsPoint *, 									       gpointer),							gpointer data,							FttCell ** closest,							gdouble * dmin);gdouble              ftt_cell_point_distance2        (FttCell * root,						      GtsPoint * p,						      gdouble (* distance2) (FttCell *, 									     GtsPoint *, 									     gpointer),						      gpointer data,						      FttCell ** closest);void                 ftt_cell_bbox                   (const FttCell * cell, 						      GtsBBox * bb);typedef void      (* FttCellCopyFunc)                (const FttCell * from,						      FttCell * to,						      gpointer data);FttCell *            ftt_cell_copy                   (const FttCell * root,						      FttCellCopyFunc copy,						      gpointer data);typedef void      (* FttCellWriteFunc)               (const FttCell * cell,						      FILE * fp,						      gpointer data);void                 ftt_cell_write                  (const FttCell * root,						      gint max_depth,						      FILE * fp,						      FttCellWriteFunc write,						      gpointer data);void                 ftt_cell_write_binary           (const FttCell * root,						      gint max_depth,						      FILE * fp,						      FttCellWriteFunc write,						      gpointer data);typedef void      (* FttCellReadFunc)                (FttCell * cell,						      GtsFile * fp,						      gpointer data);FttCell *            ftt_cell_read                   (GtsFile * fp,						      FttCellReadFunc read,						      gpointer data);FttCell *            ftt_cell_read_binary            (GtsFile * fp,						      FttCellReadFunc read,						      gpointer data);typedef void      (* FttCellCleanupFunc)             (FttCell * cell,						      gpointer data);void                 ftt_cell_destroy           (FttCell * cell,						 FttCellCleanupFunc cleanup,						 gpointer data);void                 ftt_cell_destroy_root      (FttCell * root,						 FttCellChildren * children,						 FttCellCleanupFunc cleanup,						 gpointer data);void                 ftt_cell_flatten           (FttCell * root, 						 FttDirection d, 						 FttCellCleanupFunc cleanup,						 gpointer data);typedef gboolean  (* FttCellCoarsenFunc)        (FttCell * cell,						 gpointer data);gboolean             ftt_cell_coarsen           (FttCell * root,						 FttCellCoarsenFunc coarsen,						 gpointer coarsen_data,						 FttCellCleanupFunc cleanup,						 gpointer cleanup_data);FttDirection         ftt_direction_from_name    (const gchar * name);FttCellTraverse *    ftt_cell_traverse_new      (FttCell * root,						 FttTraverseType order,						 FttTraverseFlags flags,						 gint max_depth);void                 ftt_cell_traverse_rewind   (FttCellTraverse * t);void                 ftt_cell_traverse_destroy  (FttCellTraverse * t);FttCell * ftt_cell_traverse_next (FttCellTraverse * t)`

## Exercises

• Some of these exercises can be done by using some functions already defined in Gerris.
• Other exercises require you to write some code while using some gerris functions.
• Other exercises require you to write entirely new functions.

From the point of view of this course, the "best" answers are those that reuse a maximum of already defined functions.

### Conditional traversal

Write a function that traverses all the cells of a tree that are inside a sphere centered on FttVector x_0 and of radius R.

### Finding the neighbors

Consider a leaf cell C. What is the maximum number of leaf cells that may be adjacent to C in 3D ? Write a function that returns a list of the leaf cells adjacent to C in a given direction d.

### Fast location

Have a look at the source of `ftt_cell_locate()` and find out how it manages to find the cell position efficiently in log(n) operations by using the topology of the tree.

previous: Introduction to Gerris Programming, ⇑ up: Gerris Flow Solver Programming Course for Dummies, ⇒ next: The Fluid Domain.