Pathfinder
Public Member Functions | Public Attributes | List of all members
Pathfinder::Octree Struct Reference

This struct implements the octree data structure. More...

#include <Octree.h>

Collaboration diagram for Pathfinder::Octree:

Public Member Functions

 Octree (const Geometry::Vec3 &AABBmin, const Geometry::Vec3 &AABBmax)
 A basic constructor that initializes all data members with dummy data. More...
 
 Octree (const float &size, const std::vector< Polygon *> &polygons, const std::vector< std::pair< Vertex, Graph *>> &graphVertices)
 A constructor that creates an octree and fills it with data. More...
 
void deleteOctree (const bool &root)
 Free all memory allocated to this octree and polygons. More...
 
void buildOctree (const std::vector< Polygon *> &polygons, const std::vector< std::pair< Vertex, Graph *>> &graphVertices, const std::string &indent)
 For two lists of Polygons and vertices, sort them into an empty octree. More...
 
bool polygonInOctree (const Polygon *polygon, const std::string &indent)
 Check if a poylgon lies inside an octree. More...
 
bool pointInOctree (const Geometry::Vec3 &p, const std::string &indent)
 Check if a point lies inside an octree. More...
 
std::vector< std::pair< Vertex, Graph * > > getNeighbours (const Geometry::Vec3 &p, const std::string &indent)
 Given a point p in 3D space, return all vertices associated to the smallest existing octree that has p in it. More...
 

Public Attributes

Geometry::Vec3 min
 The AABBmin of the current cube. More...
 
Geometry::Vec3 max
 The AABBmax of the current cube. More...
 
std::vector< Octree * > child
 Store pointers to the eight children of the octree. More...
 
std::vector< Polygon * > polygons
 Store pointers to Polygons that lie in this octree. More...
 
std::vector< std::pair< Vertex, Graph * > > graphVertices
 Store graph vertices that lie in this octree together with a reference to their graph. More...
 

Detailed Description

This struct implements the octree data structure.

Each octree stores a list of polygons and a list of vertices and is subdivided as follows:

6 7 y x 2 3 4 5 |/ 0 1 o–z

Constructor & Destructor Documentation

◆ Octree() [1/2]

Pathfinder::Octree::Octree ( const Geometry::Vec3 &  AABBmin,
const Geometry::Vec3 &  AABBmax 
)

A basic constructor that initializes all data members with dummy data.

Parameters
AABBminThe smallest point of the octree.
AABBmaxThe biggest point of the octree.

◆ Octree() [2/2]

Pathfinder::Octree::Octree ( const float &  size,
const std::vector< Polygon *> &  polygons,
const std::vector< std::pair< Vertex, Graph *>> &  graphVertices 
)

A constructor that creates an octree and fills it with data.

Creates the root node and calls buildOctree.

Parameters
sizeThe octree will span (-size, -size, -size) to (size, size, size).
polygonsA list of references to polygons that shall be inserted into the octree.
graphVerticesA list of references to vertices that shall be inserted into the octree.

Member Function Documentation

◆ buildOctree()

void Pathfinder::Octree::buildOctree ( const std::vector< Polygon *> &  polygons,
const std::vector< std::pair< Vertex, Graph *>> &  graphVertices,
const std::string &  indent 
)

For two lists of Polygons and vertices, sort them into an empty octree.

Create new child octrees as long as the number of poylgons for the current octree is greater than the defined threshold.

Parameters
polygonsA list of pointers to Polygons that shall be inserted into the octree.
graphVerticesA list of vertex-graph pairs that shall be inserted into the octree.
indentThe indentation used for output.

◆ deleteOctree()

void Pathfinder::Octree::deleteOctree ( const bool &  root)

Free all memory allocated to this octree and polygons.

Parameters
rootA flag that tells the function if it is invoked on the root of an octree. This is used to avoid a double free() on the polygons.

◆ getNeighbours()

std::vector< std::pair< Vertex, Graph * > > Pathfinder::Octree::getNeighbours ( const Geometry::Vec3 &  p,
const std::string &  indent 
)

Given a point p in 3D space, return all vertices associated to the smallest existing octree that has p in it.

Parameters
pThe point for which all vertices in its proximity shall be returned.
indentThe indentation used for output.
Returns
Return a list of vertices that are near p.

◆ pointInOctree()

bool Pathfinder::Octree::pointInOctree ( const Geometry::Vec3 &  p,
const std::string &  indent 
)

Check if a point lies inside an octree.

Parameters
pThe point that is to be checked.
indentThe indentation used for output.
Returns
Return true if node lies inside octree, false otherwise.

◆ polygonInOctree()

bool Pathfinder::Octree::polygonInOctree ( const Polygon polygon,
const std::string &  indent 
)

Check if a poylgon lies inside an octree.

Uses a variant of the AABB intersection detection.

Parameters
polygonThe poylgon that is to be checked.
indentThe indentation used for output.
Returns
Return true if polygon lies inside octree, false otherwise.

Member Data Documentation

◆ child

std::vector<Octree*> Pathfinder::Octree::child

Store pointers to the eight children of the octree.

◆ graphVertices

std::vector<std::pair<Vertex, Graph*> > Pathfinder::Octree::graphVertices

Store graph vertices that lie in this octree together with a reference to their graph.

◆ max

Geometry::Vec3 Pathfinder::Octree::max

The AABBmax of the current cube.

◆ min

Geometry::Vec3 Pathfinder::Octree::min

The AABBmin of the current cube.

◆ polygons

std::vector<Polygon*> Pathfinder::Octree::polygons

Store pointers to Polygons that lie in this octree.


The documentation for this struct was generated from the following files: