Quad/Octrees. More...

Functions
FttCell *	ftt_cell_new (FttCellInitFunc init, gpointer data)
gboolean	ftt_cell_check (const FttCell *cell)
void	ftt_cell_refine_single (FttCell *cell, FttCellInitFunc init, gpointer init_data)
void	ftt_cell_refine (FttCell *root, FttCellRefineFunc refine, gpointer refine_data, FttCellInitFunc init, gpointer init_data)
void	ftt_cell_draw (const FttCell cell, FILE fp)
void	ftt_face_draw (const FttCellFace face, FILE fp)
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_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_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_bbox (const FttCell cell, GtsBBox bb)
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)
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)
FttCell *	ftt_cell_locate (FttCell *root, FttVector target, gint max_depth)
gdouble	ftt_cell_point_distance2_min (FttCell cell, GtsPoint p)
gdouble	ftt_cell_point_distance2 (FttCell root, GtsPoint p, gdouble(distance2)(FttCell , GtsPoint , gpointer), gpointer data, FttCell *closest)
guint	ftt_cell_depth (const FttCell *root)
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)
FttCell *	ftt_cell_read (GtsFile *fp, FttCellReadFunc read, gpointer data)
FttCell *	ftt_cell_read_binary (GtsFile *fp, FttCellReadFunc read, gpointer data)
gboolean	ftt_refine_corner (const FttCell *cell)
FttCell *	ftt_cell_copy (const FttCell *root, FttCellCopyFunc copy, 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)
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)

Detailed Description

Quad/Octrees.

Function Documentation

void ftt_cell_bbox	(	const FttCell *	cell,
		GtsBBox *	bb
	)

Parameters:

cell	a #FttCell.
bb	a #GtsBBox.

Fills bb with the bounding box of cell.

Here is the call graph for this function:

Here is the caller graph for this function:

gboolean ftt_cell_check ( const FttCell * cell )

Parameters:

cell	a #FttCell.

Returns:: TRUE if cell is consistent, FALSE otherwise.

gboolean ftt_cell_coarsen	(	FttCell *	root,
		FttCellCoarsenFunc	coarsen,
		gpointer	coarsen_data,
		FttCellCleanupFunc	cleanup,
		gpointer	cleanup_data
	)

Parameters:

root	a #FttCell root of a cell tree to coarsen.
coarsen	a #FttCellCoarsenFunc.
coarsen_data	user data to pass to coarsen.
cleanup	a #FttCellCleanupFunc to call before destroying a cell or NULL.
cleanup_data	user data to pass to cleanup.

Coarsens the cell tree defined by root according to coarsen.

Returns:: TRUE if root has been coarsened (i.e. root is now a leaf cell), FALSE otherwise.

FttCell* ftt_cell_copy	(	const FttCell *	root,
		FttCellCopyFunc	copy,
		gpointer	data
	)

Parameters:

root	the root of the cell tree to copy.
copy	a #FttCellCopyFunc or NULL.
data	user data to pass to copy.

Returns:: a new #FttCell root of the cell tree copy of root. The attributes of the cells are copied using the user-defined copy function.

Here is the call graph for this function:

guint ftt_cell_depth ( const FttCell * root )

Parameters:

root	a #FttCell.

Returns:: the depth of the tree starting at root, i.e. the maximum level of any cell descendant of root.

Here is the caller graph for this function:

void ftt_cell_destroy	(	FttCell *	cell,
		FttCellCleanupFunc	cleanup,
		gpointer	data
	)

Parameters:

cell	a #FttCell.
cleanup	a #FttCellCleanupFunc to call before destroying cell or NULL.
data	user data to pass to cleanup.

Frees all memory allocated for cell and its descendants.

The user-defined function cleanup is called prior to freeing memory.

Here is the caller graph for this function:

void ftt_cell_destroy_root	(	FttCell *	root,
		FttCellChildren *	children,
		FttCellCleanupFunc	cleanup,
		gpointer	data
	)

Parameters:

root	the root cell of a cell tree.
children	a #FttCellChildren.
cleanup	a #FttCellCleanupFunc to call before destroying a cell.
data	user data to pass to cleanup.

Destroys the root cell of a cell tree but not its children. Each child becomes the root cell of a new cell tree. The new (orphaned) children are returned in children.

Note that the function will fail if root is also a leaf cell.

Here is the call graph for this function:

void ftt_cell_draw	(	const FttCell *	cell,
		FILE *	fp
	)

Parameters:

cell	a #FttCell.
fp	a file pointer.

Outputs in fp an OOGL (geomview) representation of cell.

Here is the call graph for this function:

void ftt_cell_flatten	(	FttCell *	root,
		FttDirection	d,
		FttCellCleanupFunc	cleanup,
		gpointer	data
	)

Parameters:

root	the root of the cell tree to flatten.
d	the direction in which to flatten.
cleanup	a #FttCellCleanupFunc to call before destroying a cell.
data	user data to pass to cleanup.

Recursively destroys all the cells of the tree defined by root which do not form the boundary in direction d. The resulting cell tree is in effect a domain "flattened" in direction d.

The resulting domain is always one-cell thick in direction d.

Here is the call graph for this function:

FttCell* ftt_cell_locate	(	FttCell *	root,
		FttVector	target,
		gint	max_depth
	)

Parameters:

root	a #FttCell.
target	position of the point to look for.
max_depth	maximum depth to consider (-1 means no restriction, see below for -2).

Locates the cell of the tree defined by root containing target. This is done efficiently in log(n) operations by using the topology of the tree.

If max_depth is set to -2, the finest cell containing target is returned. This cell is not necessarily a leaf-cell in contrast to the case where max_depth is set to -1.

Returns:: a #FttCell of the tree defined by root and containing (boundary included) the point defined by target or NULL if target is not contained in any cell of root.

Here is the call graph for this function:

Here is the caller graph for this function:

FttCell* ftt_cell_new	(	FttCellInitFunc	init,
		gpointer	data
	)

Parameters:

init	a #FttCellInitFunc or NULL.
data	user data to pass to init.

Returns:: a new root #FttCell, initialized by calling init (if not NULL).

Here is the caller graph for this function:

gdouble ftt_cell_point_distance2	(	FttCell *	root,
		GtsPoint *	p,
		gdouble()(FttCell , GtsPoint *, gpointer)	distance2,
		gpointer	data,
		FttCell **	closest
	)

Parameters:

root	a #FttCell.
p	a #GtsPoint.
distance2	the squared distance function.
data	user data to pass to distance2.
closest	where to return the closest cell or NULL.

For non-leafs cells distance2 must return a lower-bound for the minimum distance (using for example ftt_cell_point_distance2_min()).

Returns:: the square of the minimum distance measured according to distance2 between p and a leaf cell of root.

gdouble ftt_cell_point_distance2_min	(	FttCell *	cell,
		GtsPoint *	p
	)

Parameters:

cell	a #FttCell.
p	a #GtsPoint.

Returns:: the square of the minimum distance between cell and p.

Here is the call graph for this function:

void ftt_cell_pos	(	const FttCell *	cell,
		FttVector *	pos
	)

Parameters:

cell	a #FttCell.
pos	a #FttVector.

Fills pos with the coordinates of the center of cell.

Here is the caller graph for this function:

FttCell* ftt_cell_read	(	GtsFile *	fp,
		FttCellReadFunc	read,
		gpointer	data
	)

Parameters:

fp	a #GtsFile.
read	a #FttCellReadFunc function or NULL.
data	user data to pass to read.

If an error occurs (i.e. corrupted file or file format incorrect), the error field of fp is set. A possibly incomplete tree is then returned.

Returns:: the root cell of the tree contained in the file pointed to by fp. If not NULL, the user-defined function read is used to read the extra user data associated with each cell.

Here is the call graph for this function:

FttCell* ftt_cell_read_binary	(	GtsFile *	fp,
		FttCellReadFunc	read,
		gpointer	data
	)

Parameters:

fp	a #GtsFile.
read	a #FttCellReadFunc function or NULL.
data	user data to pass to read.

If an error occurs (i.e. corrupted file or file format incorrect), the error field of fp is set. A possibly incomplete tree is then returned.

Returns:: the root cell of the tree contained in the file pointed to by fp. If not NULL, the user-defined function read is used to read the extra user data associated with each cell.

Here is the call graph for this function:

void ftt_cell_refine	(	FttCell *	root,
		FttCellRefineFunc	refine,
		gpointer	refine_data,
		FttCellInitFunc	init,
		gpointer	init_data
	)

Parameters:

root	a #FttCell.
refine	a #FttCellRefineFunc.
refine_data	user data to pass to refine.
init	a #FttCellInitFunc or NULL.
init_data	user data to pass to init.

Recursively refines the tree starting from root. Each leaf of the tree is tested for refinement using the refine function. The new refined cells created are initialized using init (if not NULL) and are themselves recursively refined.

void ftt_cell_refine_single	(	FttCell *	cell,
		FttCellInitFunc	init,
		gpointer	init_data
	)

Parameters:

cell	a #FttCell.
init	a #FttCellInitFunc or NULL.
init_data	user data to pass to init.

Refines cell and eventually its neighbors to ensure that the neighborhood properties are preserved. The new refined cells created are initialized using init (if not NULL).

void ftt_cell_relative_pos	(	const FttCell *	cell,
		FttVector *	pos
	)

Parameters:

cell	a #FttCell (not a root cell).
pos	a #FttVector.

Fills pos with the coordinates of the center of cell relative to the center of its parent cell. The length unit is the size of the parent cell.

Here is the caller graph for this function:

void ftt_cell_set_level	(	FttCell *	root,
		guint	level
	)

Parameters:

root	a #FttCell, root of a cell tree.
level	the new level.

Sets the level of the root cell of a cell tree to level. Updates the levels of its children recursively.

void ftt_cell_set_neighbor	(	FttCell *	root,
		FttCell *	neighbor,
		FttDirection	d,
		FttCellInitFunc	init,
		gpointer	init_data
	)

Parameters:

root	a #FttCell, root of a cell tree.
neighbor	a #FttCell, root of a cell tree.
d	a direction.
init	a #FttCellInitFunc or NULL.
init_data	user data to pass to init.

Sets the cell tree defined by neighbor as the neighbor in direction d of the cell tree defined by root.

Any new cell created during the process is initialized using the user-defined function init.

Both root and neighbor must be the roots of their respective cell trees.

Here is the caller graph for this function:

void ftt_cell_set_neighbor_match	(	FttCell *	root,
		FttCell *	neighbor,
		FttDirection	d,
		FttCellInitFunc	init,
		gpointer	init_data
	)

Parameters:

root	a #FttCell, root of a cell tree.
neighbor	a #FttCell, root of a cell tree.
d	a direction.
init	a #FttCellInitFunc or NULL.
init_data	user data to pass to init.

Sets the cell tree defined by neighbor as the neighbor in direction d of the cell tree defined by root.

The boundary between both trees is matched i.e. the type of the face between any pair of cells belonging to each tree is always FTT_FINE_FINE. Any new cell created during the process is initialized using the user-defined function init.

Both root and neighbor must be the roots of their respective cell trees.

void ftt_cell_set_pos	(	FttCell *	root,
		const FttVector *	pos
	)

Parameters:

root	a #FttCell, root of a cell tree.
pos	a #FttVector.

Sets the position of the center of the root cell of a cell tree to pos. Updates the positions of its children recursively.

void ftt_cell_traverse	(	FttCell *	root,
		FttTraverseType	order,
		FttTraverseFlags	flags,
		gint	max_depth,
		FttCellTraverseFunc	func,
		gpointer	data
	)

Parameters:

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.

Here is the caller graph for this function:

void ftt_cell_traverse_boundary	(	FttCell *	root,
		FttDirection	d,
		FttTraverseType	order,
		FttTraverseFlags	flags,
		gint	max_depth,
		FttCellTraverseFunc	func,
		gpointer	data
	)

Parameters:

root	the root #FttCell of the tree to traverse.
d	the direction of the boundary 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 the boundary of a cell tree in direction d starting at the given root #FttCell. Calls the given function for each node visited.

Here is the caller graph for this function:

void ftt_cell_traverse_box	(	FttCell *	root,
		GtsBBox *	box,
		FttTraverseType	order,
		FttTraverseFlags	flags,
		gint	max_depth,
		FttCellTraverseFunc	func,
		gpointer	data
	)

Parameters:

root	the root #FttCell of the tree to traverse.
box	a #GtsBBox.
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. Only the cells partly or totally contained within box are visited.

Here is the call graph for this function:

void ftt_cell_traverse_condition	(	FttCell *	root,
		FttTraverseType	order,
		FttTraverseFlags	flags,
		gint	max_depth,
		FttCellTraverseFunc	func,
		gpointer	data,
		gboolean()(FttCell , gpointer)	condition,
		gpointer	cdata
	)

Parameters:

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.
condition	the condition.
cdata	user data to pass to condition.

Traverses a cell tree starting at the given root #FttCell. Calls the given function for each cell visited.

Traversal of any branch of the tree is stopped whenever condition is not verified.

Here is the caller graph for this function:

void ftt_cell_traverse_destroy ( FttCellTraverse * t )

Parameters:

t	a #FttCellTraverse.

Frees all the memory associated with t.

FttCellTraverse* ftt_cell_traverse_new	(	FttCell *	root,
		FttTraverseType	order,
		FttTraverseFlags	flags,
		gint	max_depth
	)

Parameters:

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.

Returns:: a new #FttCellTraverse.

Here is the call graph for this function:

void ftt_cell_traverse_rewind ( FttCellTraverse * t )

Parameters:

t	a #FttCellTraverse.

Sets t at the begining of the traversal.

void ftt_cell_write	(	const FttCell *	root,
		gint	max_depth,
		FILE *	fp,
		FttCellWriteFunc	write,
		gpointer	data
	)

Parameters:

root	a #FttCell.
max_depth	the maximum depth at which to stop writing (-1 means no limit).
fp	a file pointer.
write	a #FttCellWriteFunc function or NULL.
data	user data to pass to write.

Writes in the file pointed to by fp a text representation of the cell tree starting at root. If not NULL, the user-defined function write is used to write the extra user data associated with each cell.

void ftt_cell_write_binary	(	const FttCell *	root,
		gint	max_depth,
		FILE *	fp,
		FttCellWriteFunc	write,
		gpointer	data
	)

Parameters:

root	a #FttCell.
max_depth	the maximum depth at which to stop writing (-1 means no limit).
fp	a file pointer.
write	a #FttCellWriteFunc function or NULL.
data	user data to pass to write.

Writes in the file pointed to by fp a binary representation of the cell tree starting at root. If not NULL, the user-defined function write is used to write the extra user data associated with each cell.

void ftt_corner_pos	(	const FttCell *	cell,
		FttDirection	d[FTT_DIMENSION],
		FttVector *	pos
	)

Parameters:

cell	a #FttCell.
d	a set of perpendicular directions.
pos	a #FttVector.

Fills pos with the coordinates of the corner of cell defined by d.

Here is the call graph for this function:

Here is the caller graph for this function:

void ftt_corner_relative_pos	(	const FttCell *	cell,
		FttDirection	d[FTT_DIMENSION],
		FttVector *	pos
	)

Parameters:

cell	a #FttCell.
d	a set of perpendicular directions.
pos	a #FttVector.

Fills pos with the coordinates (normalised by the size of cell) of the corner of cell defined by d relative to the position of the center of cell.

Here is the caller graph for this function:

FttDirection ftt_direction_from_name ( const gchar * name )

Parameters:

name	a direction name.

Returns:: the index of the direction name or FTT_NEIGHBORS if name is not a valid direction name.

void ftt_face_draw	(	const FttCellFace *	face,
		FILE *	fp
	)

Parameters:

face	a #FttCellFace.
fp	a file pointer.

Outputs in fp an OOGL (geomview) representation of face.

Here is the call graph for this function:

void ftt_face_pos	(	const FttCellFace *	face,
		FttVector *	pos
	)

Parameters:

face	a #FttCellFace.
pos	a #FttVector.

Fills pos with the coordinates of the center of face.

Here is the call graph for this function:

Here is the caller graph for this function:

void ftt_face_traverse	(	FttCell *	root,
		FttComponent	c,
		FttTraverseType	order,
		FttTraverseFlags	flags,
		gint	max_depth,
		FttFaceTraverseFunc	func,
		gpointer	data
	)

Parameters:

root	the root #FttCell of the tree to traverse.
c	only the faces orthogonal to this component will be traversed - one of FTT_X, FTT_Y, (FTT_Z), FTT_XYZ.
order	the order in which the cells are visited - FTT_PRE_ORDER, FTT_POST_ORDER.
flags	which types of children and faces 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 #FttCellFace.
data	user data to pass to func.

Traverses a cell tree starting at the given root #FttCell. Calls the given function for each face of the cells of the tree.

If FTT_TRAVERSE_BOUNDARY_FACES is not set in flags, only "double-sided" faces are traversed i.e. the neighbor field of the face is never NULL.

Here is the call graph for this function:

void ftt_face_traverse_boundary	(	FttCell *	root,
		FttDirection	d,
		FttTraverseType	order,
		FttTraverseFlags	flags,
		gint	max_depth,
		FttFaceTraverseFunc	func,
		gpointer	data
	)

Parameters:

root	the root #FttCell of the tree to traverse.
d	the direction of the boundary to visit.
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 #FttCellFace.
data	user data to pass to func.

Traverses a cell tree starting at the given root #FttCell. Calls the given function for each face of the cell tree forming the boundary of the domain in direction d.

Here is the call graph for this function:

gboolean ftt_refine_corner ( const FttCell * cell )

Parameters:

cell	a #FttCell.

Returns:: TRUE if any "corner" neighbors of cell are more than one level more refined, FALSE otherwise (see figure topology.fig).

ftt.c File Reference

Functions

Detailed Description

Function Documentation