OctFunctions.C File Reference

A collection of simple functions for manipulating octrees. Examples: Regular Refinements, Linearizing an octree, I/O, Nearest Common Ancestor, adding positive boundaries, marking hanging nodes. More...

#include "TreeNode.h"
#include "parUtils.h"
#include "seqUtils.h"
#include <cstring>

Go to the source code of this file.

Namespaces
namespace	ot
Functions
void	addBoundaryNodesType1 (std::vector< ot::TreeNode > &in, std::vector< ot::TreeNode > &bdy, unsigned int dim, unsigned int maxDepth)
	generates psuedonodes for the positive boundary and inserts them into bdy
void	addBoundaryNodesType2 (std::vector< ot::TreeNode > &in, std::vector< ot::TreeNode > &bdy, unsigned int dim, unsigned int maxDepth)
bool	areComparable (TreeNode first, TreeNode second)
	checks if the dim and maxdepths are the same.
bool	bPartComparator (TreeNode a, TreeNode b)
	criteria for picking blocks inside blockPart
int	createRegularOctree (std::vector< ot::TreeNode > &out, unsigned int lev, unsigned int dim, unsigned int maxDepth, MPI_Comm comm)
	Creates a regular grid octree.
void	discardExtraBoundaryOctants (std::vector< ot::TreeNode > &in, unsigned int dim, unsigned int maxDepth)
void	flagNodesType1 (std::vector< ot::TreeNode > &in, MPI_Comm comm)
	Identifies hanging nodes. Uses two all2allv communications. No overlap of comm and comp.
void	flagNodesType2 (std::vector< ot::TreeNode > &in, MPI_Comm comm)
	Identifies hanging nodes. It just uses 1 communication by sending apriori results. Overlaps comm and comp.
void	flagNodesType3 (std::vector< ot::TreeNode > &in, MPI_Comm comm)
	Identifies hanging nodes. 2 step communication, overlapping comm and comp.
TreeNode	getNCA (TreeNode first, TreeNode second)
unsigned int	getNodeWeight (const TreeNode *t)
char	int2char (int d)
int	int2str (int n, char *s)
bool	lessThanUsingWts (TreeNode const &a, TreeNode const &b)
	A comparator that uses the weights of the octants instead of the Morton ordering.
int	lineariseList (std::vector< ot::TreeNode > &list, MPI_Comm comm)
	Makes the input linear. Removes duplicates and ancestors.
int	lineariseList (std::vector< ot::TreeNode > &list, bool skipLast)
	Makes the input linear. Removes duplicates and ancestors.
void	markBoundaryNodesAtAllLevels (std::vector< ot::TreeNode > &finestOctree, unsigned int nlevels, std::vector< ot::TreeNode > *coarserOctrees, unsigned int maxDepth)
void	markHangingNodesAtAllLevels (std::vector< ot::TreeNode > &finestOctree, unsigned int nlevels, std::vector< ot::TreeNode > *coarserOctrees, MPI_Comm *activeComms, unsigned int dim, unsigned int maxDepth)
int	mergeOctrees (std::vector< TreeNode > &inOct1, std::vector< TreeNode > &inOct2, std::vector< TreeNode > &outOct, MPI_Comm comm)
	Merges the 2 input octrees and linearizes the result.
int	readDataPtsFromFile (char *filename, std::vector< double > &pts, std::vector< double > &ptVals)
	Reads a list of points and corresponding values from a file.
int	readNodesFromFile (char *filename, std::vector< TreeNode > &nodes)
	Reads a list of octants from a file.
int	readPtsFromFile (char *filename, std::vector< double > &pts)
	Reads a list of points from a file.
int	refineAndPartitionOctree (const std::vector< ot::TreeNode > &inp, std::vector< ot::TreeNode > &out, MPI_Comm comm)
	Replaces every octant with its eight children and partitions the result uniformly across the processors.
int	refineOctree (const std::vector< ot::TreeNode > &inp, std::vector< ot::TreeNode > &out)
	Replaces every octant with its eight children.
int	writeDataPtsToFile (char *filename, std::vector< double > &pts, std::vector< double > &data)
	Writes a list of points and corresponding values from a file.
int	writeNodesToFile (char *filename, const std::vector< TreeNode > &nodes)
	Writes a list of octants to a file.
int	writePtsToFile (char *filename, std::vector< double > &pts)
	Writes a list of points to a file.

---

Detailed Description

A collection of simple functions for manipulating octrees. Examples: Regular Refinements, Linearizing an octree, I/O, Nearest Common Ancestor, adding positive boundaries, marking hanging nodes.

Author:

Rahul S. Sampath, rahul.sampath@gmail.com

Hari Sundar, hsundar@gmail.com

Definition in file OctFunctions.C.

---

Function Documentation

void ot::addBoundaryNodesType1 (  std::vector< ot::TreeNode > &  in, std::vector< ot::TreeNode > &  bdy, unsigned int  dim, unsigned int  maxDepth )

generates psuedonodes for the positive boundary and inserts them into bdy Author: Hari Sundar Rahul Sampath Parameters: in  The input octree. This will be modified so that the original octree is embedded into a larger octree. bdy  A list to store the pseudo-octants for the positive boundary Definition at line 626 of file OctFunctions.C. References ot::TreeNode::getLevel(), ot::TreeNode::getX(), ot::TreeNode::getY(), ot::TreeNode::getZ(), PROF_ADD_BDY_BEGIN, and PROF_ADD_BDY_END. Referenced by ot::DA::DA_FactoryPart1(), and ot::DAMGCreateAndSetDA().

void ot::addBoundaryNodesType2 (  std::vector< ot::TreeNode > &  in, std::vector< ot::TreeNode > &  bdy, unsigned int  dim, unsigned int  maxDepth )

Definition at line 473 of file OctFunctions.C. References ot::TreeNode::getLevel(), ot::TreeNode::getX(), ot::TreeNode::getY(), ot::TreeNode::getZ(), PROF_ADD_BDY_BEGIN, and PROF_ADD_BDY_END.

bool ot::areComparable (  TreeNode  first, TreeNode  second )

checks if the dim and maxdepths are the same. Returns: true if first and second are comparable Definition at line 431 of file OctFunctions.C. References ot::TreeNode::getDim(), and ot::TreeNode::getMaxDepth(). Referenced by ot::TreeNode::addBalancingDescendants(), ot::appendCompleteRegion(), ot::balanceBlocks(), ot::balanceOctree(), ot::TreeNode::balanceSubtree(), ot::blockPartStage1(), ot::blockPartStage2(), ot::blockPartStage2_p2o(), ot::comboRipple(), ot::completeOctree(), ot::TreeNode::completeSubtree(), ot::completeSubtree(), ot::finalMergeInBal(), ot::getNCA(), ot::lineariseList(), ot::mergeComboBalAndPickBoundary(), ot::p2oLocal(), ot::parallelRippleType1(), ot::parallelRippleType2(), ot::parallelRippleType3(), ot::TreeNode::pickInternalBoundaryCells(), ot::prepareBalComm2Messages(), ot::prepareWlistInBal(), ot::ripple(), and ot::TreeNode::splitInternalAndBoundaryCells().

bool ot::bPartComparator (  TreeNode  a, TreeNode  b )

criteria for picking blocks inside blockPart Returns: true if a < b according to the criteria Definition at line 267 of file OctFunctions.C. References ot::TreeNode::getLevel(), and ot::TreeNode::getWeight().

int ot::createRegularOctree (  std::vector< ot::TreeNode > &  out, unsigned int  lev, unsigned int  dim, unsigned int  maxDepth, MPI_Comm  comm )

Creates a regular grid octree. Author: Rahul Sampath Parameters: out  the result lev  the level of each octant dim  the dimension of the tree (1 for binary trees, 2 for quadtrees and 3 for octrees) maxDepth  the maximum depth of the octree must be <= _MAX_LEVEL_ Definition at line 153 of file OctFunctions.C. References ot::refineAndPartitionOctree(). Referenced by main().

void ot::discardExtraBoundaryOctants (  std::vector< ot::TreeNode > &  in, unsigned int  dim, unsigned int  maxDepth )

Definition at line 584 of file OctFunctions.C. References ot::TreeNode::getX(), ot::TreeNode::getY(), and ot::TreeNode::getZ().

void ot::flagNodesType1 (  std::vector< ot::TreeNode > &  in, MPI_Comm  comm )

Identifies hanging nodes. Uses two all2allv communications. No overlap of comm and comp. Author: Rahul Sampath Parameters: in  The octree including pseudo-octants for the positive boundaries Definition at line 708 of file OctFunctions.C. References ot::TreeNode::getChildNumber(), ot::TreeNode::getDim(), ot::TreeNode::getLevel(), ot::TreeNode::getMaxDepth(), ot::TreeNode::getParent(), ot::TreeNode::getX(), ot::TreeNode::getY(), ot::TreeNode::getZ(), ot::TreeNode::orFlag(), PROF_FLN_STAGE1_BEGIN, PROF_FLN_STAGE1_END, PROF_FLN_STAGE2_BEGIN, PROF_FLN_STAGE2_END, PROF_FLN_STAGE3_BEGIN, PROF_FLN_STAGE3_END, PROF_FLN_STAGE4_BEGIN, PROF_FLN_STAGE4_END, PROF_FLN_STAGE5_BEGIN, PROF_FLN_STAGE5_END, PROF_MARK_HANGING_BEGIN, and PROF_MARK_HANGING_END.

void ot::flagNodesType2 (  std::vector< ot::TreeNode > &  in, MPI_Comm  comm )

Identifies hanging nodes. It just uses 1 communication by sending apriori results. Overlaps comm and comp. Author: Rahul Sampath Parameters: in  the Octree including pseudo-octants for positive boundaries Definition at line 1062 of file OctFunctions.C. References seq::BinarySearch(), ot::TreeNode::getChildNumber(), ot::TreeNode::getDim(), ot::TreeNode::getLevel(), ot::TreeNode::getMaxDepth(), ot::TreeNode::getX(), ot::TreeNode::getY(), ot::TreeNode::getZ(), par::Mpi_Alltoall(), ot::TreeNode::orFlag(), PROF_FLN_STAGE1_BEGIN, PROF_FLN_STAGE1_END, PROF_FLN_STAGE2_BEGIN, PROF_FLN_STAGE2_END, PROF_FLN_STAGE3_BEGIN, PROF_FLN_STAGE3_END, PROF_FLN_STAGE4_BEGIN, PROF_FLN_STAGE4_END, PROF_FLN_STAGE5_BEGIN, PROF_FLN_STAGE5_END, PROF_FLN_STAGE6_BEGIN, PROF_FLN_STAGE6_END, PROF_FLN_STAGE7_BEGIN, PROF_FLN_STAGE7_END, PROF_MARK_HANGING_BEGIN, and PROF_MARK_HANGING_END.

void ot::flagNodesType3 (  std::vector< ot::TreeNode > &  in, MPI_Comm  comm )

Identifies hanging nodes. 2 step communication, overlapping comm and comp. Author: Rahul Sampath Parameters: in  the Octree including pseudo-octants for positive boundaries Definition at line 1463 of file OctFunctions.C. References ot::TreeNode::getChildNumber(), ot::TreeNode::getDim(), ot::TreeNode::getLevel(), ot::TreeNode::getMaxDepth(), ot::TreeNode::getParent(), ot::TreeNode::getWeight(), ot::TreeNode::getX(), ot::TreeNode::getY(), ot::TreeNode::getZ(), ot::TreeNode::orFlag(), PROF_FLN_STAGE10_BEGIN, PROF_FLN_STAGE10_END, PROF_FLN_STAGE11_BEGIN, PROF_FLN_STAGE11_END, PROF_FLN_STAGE1_BEGIN, PROF_FLN_STAGE1_END, PROF_FLN_STAGE2_BEGIN, PROF_FLN_STAGE2_END, PROF_FLN_STAGE3_BEGIN, PROF_FLN_STAGE3_END, PROF_FLN_STAGE4_BEGIN, PROF_FLN_STAGE4_END, PROF_FLN_STAGE5_BEGIN, PROF_FLN_STAGE5_END, PROF_FLN_STAGE6_BEGIN, PROF_FLN_STAGE6_END, PROF_FLN_STAGE7_BEGIN, PROF_FLN_STAGE7_END, PROF_FLN_STAGE8_BEGIN, PROF_FLN_STAGE8_END, PROF_FLN_STAGE9_BEGIN, PROF_FLN_STAGE9_END, PROF_MARK_HANGING_BEGIN, PROF_MARK_HANGING_END, and ot::TreeNode::setWeight(). Referenced by ot::DA::DA_FactoryPart2(), and ot::markHangingNodesAtAllLevels().

TreeNode ot::getNCA (  TreeNode  first, TreeNode  second )

Author: Rahul Sampath Returns: the nearest common ancestor of first and second. If one of them is the ancestor of the other it is returned. Note: first must be different from second. Definition at line 281 of file OctFunctions.C. References ot::areComparable(), binOp::binLength(), ot::TreeNode::getDim(), ot::TreeNode::getMaxDepth(), ot::TreeNode::getX(), ot::TreeNode::getY(), and ot::TreeNode::getZ(). Referenced by ot::appendCompleteRegion(), ot::comboRipple(), ot::completeOctree(), and ot::completeSubtree().

unsigned int ot::getNodeWeight (  const TreeNode *  t  )

Definition at line 263 of file OctFunctions.C. References ot::TreeNode::getWeight().

char ot::int2char (  int  dec  )

Definition at line 455 of file OctFunctions.C. Referenced by ot::int2str().

int ot::int2str (  int  dec, char *  numStr )

Definition at line 435 of file OctFunctions.C. References ot::int2char(). Referenced by main().

bool ot::lessThanUsingWts (  TreeNode const &  a, TreeNode const &  b )

A comparator that uses the weights of the octants instead of the Morton ordering. Returns: a < b based on their respective weigths. Definition at line 255 of file OctFunctions.C. References ot::TreeNode::getWeight().

int ot::lineariseList (  std::vector< ot::TreeNode > &  list, MPI_Comm  comm )

Makes the input linear. Removes duplicates and ancestors. Parameters: list  the input vector (must be sorted) Author: Rahul Sampath Definition at line 194 of file OctFunctions.C. References par::splitComm2way(). Referenced by ot::mergeOctrees().

int ot::lineariseList (  std::vector< ot::TreeNode > &  list, bool  skipLast = false )

Makes the input linear. Removes duplicates and ancestors. Parameters: list  the input vector (must be sorted) skipLast  Pass 'true' if you do not wish to include the last element in the output and 'false' otherwise Author: Rahul Sampath Definition at line 172 of file OctFunctions.C. References ot::areComparable().

void ot::markBoundaryNodesAtAllLevels (  std::vector< ot::TreeNode > &  finestOctree, unsigned int  nlevels, std::vector< ot::TreeNode > *  coarserOctrees, unsigned int  maxDepth )

Definition at line 554 of file OctFunctions.C. References ot::TreeNode::getX(), ot::TreeNode::getY(), ot::TreeNode::getZ(), and ot::TreeNode::orFlag().

void ot::markHangingNodesAtAllLevels (  std::vector< ot::TreeNode > &  finestOctree, unsigned int  nlevels, std::vector< ot::TreeNode > *  coarserOctrees, MPI_Comm *  activeComms, unsigned int  dim, unsigned int  maxDepth )

Definition at line 607 of file OctFunctions.C. References ot::flagNodesType3(). Referenced by ot::DAMGCreateAndSetDA().

int ot::mergeOctrees (  std::vector< TreeNode > &  inOct1, std::vector< TreeNode > &  inOct2, std::vector< TreeNode > &  outOct, MPI_Comm  comm )

Merges the 2 input octrees and linearizes the result. Author: Rahul Sampath Parameters: inOct1,inOct2  input octrees outOct  output octree Definition at line 31 of file OctFunctions.C. References ot::lineariseList(), PROF_MERGE_OCTREES_BEGIN, and PROF_MERGE_OCTREES_END.

int ot::readDataPtsFromFile (  char *  filename, std::vector< double > &  pts, std::vector< double > &  ptVals )

Reads a list of points and corresponding values from a file. Author: Ilya Lashuk Parameters: filename  the file name pts  the points data  the values Definition at line 333 of file OctFunctions.C.

int ot::readNodesFromFile (  char *  filename, std::vector< TreeNode > &  nodes )

Reads a list of octants from a file. Author: Rahul Sampath Parameters: filename  the file name nodes  the octants Definition at line 393 of file OctFunctions.C. Referenced by main().

int ot::readPtsFromFile (  char *  filename, std::vector< double > &  pts )

Reads a list of points from a file. Author: Rahul Sampath Parameters: filename  the file name pts  the points Definition at line 305 of file OctFunctions.C. Referenced by ComputeFBM_RHS_Part2(), and main().

int ot::refineAndPartitionOctree (  const std::vector< TreeNode > &  in, std::vector< TreeNode > &  out, MPI_Comm  comm )

Replaces every octant with its eight children and partitions the result uniformly across the processors. Author: Rahul Sampath Parameters: in  the input vector out  the output vector See also: refineOctre Definition at line 146 of file OctFunctions.C. References ot::refineOctree(). Referenced by ot::createRegularOctree().

int ot::refineOctree (  const std::vector< TreeNode > &  in, std::vector< TreeNode > &  out )

Replaces every octant with its eight children. Author: Rahul Sampath Parameters: in  the input vector out  the output vector Definition at line 133 of file OctFunctions.C. References ot::TreeNode::addChildren(). Referenced by main(), and ot::refineAndPartitionOctree().

int ot::writeDataPtsToFile (  char *  filename, std::vector< double > &  pts, std::vector< double > &  data )

Writes a list of points and corresponding values from a file. Author: Ilya Lashuk Parameters: filename  the file name pts  the points data  the values Definition at line 377 of file OctFunctions.C.

int ot::writeNodesToFile (  char *  filename, const std::vector< TreeNode > &  nodes )

Writes a list of octants to a file. Author: Rahul Sampath Parameters: filename  the file name nodes  the octants Definition at line 414 of file OctFunctions.C. References ot::TreeNode::getDim(), and ot::TreeNode::getMaxDepth(). Referenced by ot::DAMGCreateAndSetDA(), ot::test::isBalancedInternal(), and main().

int ot::writePtsToFile (  char *  filename, std::vector< double > &  pts )

Writes a list of points to a file. Author: Rahul Sampath Parameters: filename  the file name pts  the points Definition at line 360 of file OctFunctions.C. Referenced by main().

---