Nektar::FieldUtils::Octree Class Reference

#include <Octree.h>

Classes
class	Octant

Public Member Functions
	Octree ()
	Construct a new octree object. More...
	Octree (const Array< OneD, Array< OneD, NekDouble >> &pts, int maxPts, const Array< OneD, NekDouble > &bounds)
	Construct a new octree object. More...
	Octree (const Array< OneD, Array< OneD, NekDouble >> &pts, int maxPts)
	Construct a new octree object. More...
int	QueryNode (const Array< OneD, NekDouble > &coords, int depth=std::numeric_limits< int >::max())
	Given the coordinates 'coords' of a point, returns the leaf octant that contains it. If 'depth' is specified, returs the node that contains the point such that its depth is lower or equal to the one indicated. If the point lies outside the tree, it returns -1. More...
int	QueryClosest (const Array< OneD, Array< OneD, NekDouble >> &pts, const Array< OneD, NekDouble > &coords, double &distance, int pointInd=-1)
	Finds the ID of the closest point in 'pts' to the one specified by 'coords'. It also returns the distance between both points in 'distance'. More...
std::vector< int >	QueryPoints (int nodeID)
	Returns the indices of the points of the mesh contained in the tree. More...
std::vector< int >	QueryNeighbours (int nodeID)
	Returns the IDs of the octants that surround the queried node. First, it finds the neighbouring nodes with the same or lower depth and, if they are not leaf nodes, return all the leaf octants contained in them. This means that, for octants of depth 2, this function returns all the leaf nodes in the tree except those lying inside the queried octant. More...
int	QueryNpoints (int nodeID)
int	QueryLocation (int nodeID)
int	QueryDepth (int nodeID)
int	QueryDelta (int nodeID)
void	GetStats (int &maxPts, int &nPts, int &nNodes, int &nLeaves, int &depth)
	Returns some characteristic values of the tree. More...

Private Types
using	OctantSharedPtr = std::shared_ptr< Octant >
using	OctantWeakPtr = std::weak_ptr< Octant >

Private Member Functions
void	AdvanceToStats (int nodeID)
	Goes through all the nodes of the octree counting the number of octants and the maximum depth reached. More...
void	SetNeighbours (int nodeID)
	Once the nodes of the octree are created, sets their neighbours as explained in 'Octree::QueryNeighbours'. More...

Private Attributes
int	m_maxPts
	Max points allowed in each octant. More...
int	m_nMshPts
	Number of points in the mesh. More...
int	m_nNodes
	Number of octants in the tree. More...
int	m_nLeaves
	Number of leaf nodes in the tree. More...
int	m_maxDepth
	Maximum depth of the tree. More...
OctantSharedPtr	m_root
	First node of the tree, linked to the rest. More...
std::vector< OctantSharedPtr >	m_nodes
	Vector of pointers to every octant in the tree. More...

Detailed Description

Definition at line 45 of file Octree.h.

Member Typedef Documentation

OctantSharedPtr

using Nektar::FieldUtils::Octree::OctantSharedPtr = std::shared_ptr<Octant>

private

Definition at line 48 of file Octree.h.

OctantWeakPtr

using Nektar::FieldUtils::Octree::OctantWeakPtr = std::weak_ptr<Octant>

private

Definition at line 49 of file Octree.h.

Constructor & Destructor Documentation

Octree() [1/3]

Nektar::FieldUtils::Octree::Octree

(

)

Construct a new octree object.

Definition at line 48 of file Octree.cpp.

    : m_maxPts(0), m_nMshPts(0), m_nNodes(0), m_nLeaves(0), m_maxDepth(0),
      m_root(nullptr)
{
}

Referenced by Octree().

Octree() [2/3]

Nektar::FieldUtils::Octree::Octree	(	const Array< OneD, Array< OneD, NekDouble >> &	pts,
		int	maxPts,
		const Array< OneD, NekDouble > &	bounds
	)

Construct a new octree object.

Parameters

pts
maxPts
bounds

Definition at line 61 of file Octree.cpp.

{
    // Set some values
    m_maxPts  = maxPts;
    m_nMshPts = pts.size();
 
    // Create first (root) node
    std::vector<int> indices(m_nMshPts);
    for (int i = 0; i < m_nMshPts; ++i)
    {
        indices[i] = i;
    }
    m_root = std::make_shared<Octant>(0, 1, 0, bounds);
    m_root->SetIndices(indices);
    m_nodes.push_back(m_root);
 
    // Create the tree
    m_root->Subdivide(m_maxPts, pts, m_nodes);
 
    // Get some data after the tree is computed
    m_maxDepth = 0;
    AdvanceToStats(m_root->GetID());
    m_nNodes = m_nodes.size();
 
    // Set the pointers to the neighbouring nodes
    SetNeighbours(m_root->GetID());
}

References AdvanceToStats(), m_maxDepth, m_maxPts, m_nMshPts, m_nNodes, m_nodes, m_root, and SetNeighbours().

Octree() [3/3]

Nektar::FieldUtils::Octree::Octree	(	const Array< OneD, Array< OneD, NekDouble >> &	pts,
		int	maxPts
	)

Construct a new octree object.

Parameters

pts
maxPts

Definition at line 96 of file Octree.cpp.

{
    // Small margin to avoid rounding errors
    NekDouble margin = 1e-10;
 
    // Find coordinates of the bounding box
    Array<OneD, NekDouble> bounds(6);
    bounds[0] = pts[0][0];
    bounds[1] = pts[0][0];
    bounds[2] = pts[0][1];
    bounds[3] = pts[0][1];
    bounds[4] = pts[0][2];
    bounds[5] = pts[0][2];
    for (int i = 1; i < m_nMshPts; ++i)
    {
        bounds[0] = (bounds[0] < pts[i][0]) ? bounds[0] : pts[i][0];
        bounds[1] = (bounds[1] > pts[i][0]) ? bounds[1] : pts[i][0];
        bounds[2] = (bounds[2] < pts[i][1]) ? bounds[2] : pts[i][1];
        bounds[3] = (bounds[3] > pts[i][1]) ? bounds[3] : pts[i][1];
        bounds[4] = (bounds[4] < pts[i][2]) ? bounds[4] : pts[i][2];
        bounds[5] = (bounds[5] > pts[i][2]) ? bounds[5] : pts[i][2];
    }
 
    // Add the margin
    for (int i = 0; i < 6; ++i)
    {
        bounds[i] -= pow(-1, i) * margin;
    }
 
    // Call the octree constructor
    Octree(pts, maxPts, bounds);
}

References m_nMshPts, and Octree().

Member Function Documentation

AdvanceToStats()

void Nektar::FieldUtils::Octree::AdvanceToStats ( int  nodeID )

private

Goes through all the nodes of the octree counting the number of octants and the maximum depth reached.

Parameters

nodeID

Definition at line 287 of file Octree.cpp.

{
    // Update stats if we reached the end of the branch
    if (m_nodes[nodeID]->IsLeaf())
    {
        m_nLeaves++;
        m_maxDepth = (m_maxDepth > m_nodes[nodeID]->GetDepth())
                         ? m_maxDepth
                         : m_nodes[nodeID]->GetDepth();
    }
    // In any other case, dig into the tree
    else
    {
        Array<OneD, OctantSharedPtr> children = m_nodes[nodeID]->GetChildren();
        for (OctantSharedPtr child : children)
        {
            AdvanceToStats(child->GetID());
        }
    }
}

References m_maxDepth, m_nLeaves, and m_nodes.

Referenced by Octree().

GetStats()

void Nektar::FieldUtils::Octree::GetStats	(	int &	maxPts,
		int &	nPts,
		int &	nNodes,
		int &	nLeaves,
		int &	depth
	)

Returns some characteristic values of the tree.

Parameters

maxPts
nPts
nNodes
nLeaves
depth

Definition at line 271 of file Octree.cpp.

{
    maxPts  = m_maxPts;
    nPts    = m_nMshPts;
    nNodes  = m_nNodes;
    nLeaves = m_nLeaves;
    depth   = m_maxDepth;
}

References m_maxDepth, m_maxPts, m_nLeaves, m_nMshPts, and m_nNodes.

QueryClosest()

int Nektar::FieldUtils::Octree::QueryClosest	(	const Array< OneD, Array< OneD, NekDouble >> &	pts,
		const Array< OneD, NekDouble > &	coords,
		double &	distance,
		int	pointInd = -1
	)

Finds the ID of the closest point in 'pts' to the one specified by 'coords'. It also returns the distance between both points in 'distance'.

Parameters

pts
coords
distance
pointInd

Returns

int

Definition at line 178 of file Octree.cpp.

{
    int index = -1;
    distance  = std::numeric_limits<NekDouble>::max();
 
    if (coords.size())
    {
        // Find the corresponding node to 'coords'
        int nodeInd;
        if (pointInd > 0)
        {
            nodeInd = pointInd;
        }
        else
        {
            nodeInd = QueryNode(coords);
        }
 
        // List the indices of all the candidate points
        std::vector<int> indices(m_nodes[nodeInd]->GetIndices());
        for (OctantWeakPtr neigh : m_nodes[nodeInd]->GetNeighbours())
        {
            for (int i : neigh.lock()->GetIndices())
            {
                indices.push_back(i);
            }
        }
 
        // Check the distances with all the nodes
        for (int i : indices)
        {
            NekDouble sub         = pts[i][0] - coords[0];
            NekDouble tmpDistance = sub * sub;
            for (int j = 1; j < 3; ++j)
            {
                sub = pts[i][j] - coords[j];
                tmpDistance += sub * sub;
            }
            tmpDistance = std::sqrt(tmpDistance);
 
            if (distance > tmpDistance)
            {
                distance = tmpDistance;
                index    = i;
            }
        }
    }
 
    return index;
}

References m_nodes, QueryNode(), and tinysimd::sqrt().

QueryDelta()

int Nektar::FieldUtils::Octree::QueryDelta ( int  nodeID )

inline

Definition at line 85 of file Octree.h.

    {
        return m_nodes[nodeID]->GetDelta();
    }

References m_nodes.

QueryDepth()

int Nektar::FieldUtils::Octree::QueryDepth ( int  nodeID )

inline

Definition at line 81 of file Octree.h.

    {
        return m_nodes[nodeID]->GetDepth();
    }

References m_nodes.

Referenced by Nektar::FieldUtils::ProcessPhiFromFile::FindShortestDist().

QueryLocation()

int Nektar::FieldUtils::Octree::QueryLocation ( int  nodeID )

inline

Definition at line 77 of file Octree.h.

    {
        return m_nodes[nodeID]->GetLoc();
    }

References m_nodes.

QueryNeighbours()

std::vector< int > Nektar::FieldUtils::Octree::QueryNeighbours

(

int

nodeID

)

Returns the IDs of the octants that surround the queried node. First, it finds the neighbouring nodes with the same or lower depth and, if they are not leaf nodes, return all the leaf octants contained in them. This means that, for octants of depth 2, this function returns all the leaf nodes in the tree except those lying inside the queried octant.

Parameters

nodeID

Returns

std::vector<int>

Definition at line 252 of file Octree.cpp.

{
    std::vector<int> indices;
    for (const OctantWeakPtr &node : m_nodes[nodeID]->GetNeighbours())
    {
        indices.push_back(node.lock()->GetID());
    }
    return indices;
}

References m_nodes.

Referenced by Nektar::FieldUtils::ProcessPhiFromFile::FindShortestDist().

QueryNode()

int Nektar::FieldUtils::Octree::QueryNode	(	const Array< OneD, NekDouble > &	coords,
		int	depth = std::numeric_limits<int>::max()
	)

Given the coordinates 'coords' of a point, returns the leaf octant that contains it. If 'depth' is specified, returs the node that contains the point such that its depth is lower or equal to the one indicated. If the point lies outside the tree, it returns -1.

Parameters

coords
depth

Returns

int

Definition at line 139 of file Octree.cpp.

{
    int nodeID = -1;
 
    if (coords.size())
    {
        // First, check if inside the octree
        Array<OneD, NekDouble> bounds = m_root->GetBounds();
        if ((coords[0] >= bounds[0]) && (coords[0] <= bounds[1]) &&
            (coords[1] >= bounds[2]) && (coords[1] <= bounds[3]) &&
            (coords[2] >= bounds[4]) && (coords[2] <= bounds[5]))
        {
            // Initialise 'node'
            OctantSharedPtr node = m_root;
 
            // Keep advancing towards the end of the branch
            while (!node->IsLeaf() && node->GetDepth() < depth)
            {
                int loc = node->GetLocInNode(coords);
                node    = node->GetChildren()[loc - 1];
            }
 
            nodeID = node->GetID();
        }
    }
 
    return nodeID;
}

References CG_Iterations::loc, and m_root.

Referenced by Nektar::FieldUtils::ProcessPhiFromFile::FindShortestDist(), QueryClosest(), and SetNeighbours().

QueryNpoints()

int Nektar::FieldUtils::Octree::QueryNpoints ( int  nodeID )

inline

Definition at line 73 of file Octree.h.

    {
        return m_nodes[nodeID]->GetNpoints();
    }

References m_nodes.

QueryPoints()

std::vector< int > Nektar::FieldUtils::Octree::QueryPoints

(

int

nodeID

)

Returns the indices of the points of the mesh contained in the tree.

Parameters

nodeID

Returns

std::vector<int>

Definition at line 237 of file Octree.cpp.

{
    return m_nodes[nodeID]->GetIndices();
}

References m_nodes.

Referenced by Nektar::FieldUtils::ProcessPhiFromFile::FindShortestDist().

SetNeighbours()

void Nektar::FieldUtils::Octree::SetNeighbours ( int  nodeID )

private

Once the nodes of the octree are created, sets their neighbours as explained in 'Octree::QueryNeighbours'.

Parameters

nodeID

Definition at line 314 of file Octree.cpp.

{
    // Array with the different steps
    static int steps[26][3] = {
        {-1, -1, -1}, {1, 0, 0},  {1, 0, 0},  {0, 1, 0},  {0, 1, 0},
        {-1, 0, 0},   {-1, 0, 0}, {0, -1, 0}, {1, 0, 0},  {-1, -1, 1},
        {1, 0, 0},    {1, 0, 0},  {0, 1, 0},  {0, 1, 0},  {-1, 0, 0},
        {-1, 0, 0},   {0, -1, 0}, {0, -1, 1}, {1, 0, 0},  {1, 0, 0},
        {0, 1, 0},    {0, 1, 0},  {-1, 0, 0}, {-1, 0, 0}, {0, -1, 0},
        {1, 0, 0}};
 
    // Advance to the leaves of the octree
    if (!m_nodes[nodeID]->IsLeaf())
    {
        for (OctantSharedPtr child : m_nodes[nodeID]->GetChildren())
        {
            SetNeighbours(child->GetID());
        }
    }
    else
    {
        // delta * steps
        Array<OneD, NekDouble> probeCoords(m_nodes[nodeID]->GetCentre());
        for (int step = 0; step < 26; ++step)
        {
            for (int i = 0; i < 3; ++i)
            {
                probeCoords[i] += m_nodes[nodeID]->GetDelta() * steps[step][i];
            }
 
            // For each neighbour, find the leaves and add them
            int neighInd = QueryNode(probeCoords, m_nodes[nodeID]->GetDepth());
            if (neighInd > -1)
            {
                std::vector<OctantSharedPtr> leaves;
                m_nodes[neighInd]->GetLeaves(leaves);
                m_nodes[nodeID]->AddNeighbours(leaves);
            }
        }
    }
}

References m_nodes, and QueryNode().

Referenced by Octree().

Member Data Documentation

m_maxDepth

int Nektar::FieldUtils::Octree::m_maxDepth

private

Maximum depth of the tree.

Definition at line 201 of file Octree.h.

Referenced by AdvanceToStats(), GetStats(), and Octree().

m_maxPts

int Nektar::FieldUtils::Octree::m_maxPts

private

Max points allowed in each octant.

Definition at line 193 of file Octree.h.

Referenced by GetStats(), and Octree().

m_nLeaves

int Nektar::FieldUtils::Octree::m_nLeaves

private

Number of leaf nodes in the tree.

Definition at line 199 of file Octree.h.

Referenced by AdvanceToStats(), and GetStats().

m_nMshPts

int Nektar::FieldUtils::Octree::m_nMshPts

private

Number of points in the mesh.

Definition at line 195 of file Octree.h.

Referenced by GetStats(), and Octree().

m_nNodes

int Nektar::FieldUtils::Octree::m_nNodes

private

Number of octants in the tree.

Definition at line 197 of file Octree.h.

Referenced by GetStats(), and Octree().

m_nodes

std::vector<OctantSharedPtr> Nektar::FieldUtils::Octree::m_nodes

private

Vector of pointers to every octant in the tree.

Definition at line 206 of file Octree.h.

Referenced by AdvanceToStats(), Octree(), QueryClosest(), QueryDelta(), QueryDepth(), QueryLocation(), QueryNeighbours(), QueryNpoints(), QueryPoints(), and SetNeighbours().

m_root

OctantSharedPtr Nektar::FieldUtils::Octree::m_root

private

First node of the tree, linked to the rest.

Definition at line 204 of file Octree.h.

Referenced by Octree(), and QueryNode().