The Fully Threaded Tree
From Gerris
Contents |
Introduction to Fully Threaded Trees
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 | Name |
| FttCell | guint | flags |
| gpointer | data | |
| FttCellFace | FttCell | cell, neighbor |
| FttDirection | d | |
| FttRootCell | FttCell | cell |
| FttCellNeighbors | neighbors | |
| FttVector | pos | |
| guint | level | |
| gpointer | parent | |
| FttCellNeighbors | FttCell * | c[FTT_CELLS] |
| FttCellChildren | 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
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
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
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_FINEwhen the neighbor is as fine as the cell . -
FTT_FINE_COARSEwhen the neighbor is coarser than the cell -
FTT_BOUNDARYwhen 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.