Pathfinder
|
This struct implements the octree data structure. More...
#include <Octree.h>
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... | |
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
Pathfinder::Octree::Octree | ( | const Geometry::Vec3 & | AABBmin, |
const Geometry::Vec3 & | AABBmax | ||
) |
A basic constructor that initializes all data members with dummy data.
AABBmin | The smallest point of the octree. |
AABBmax | The biggest point of the octree. |
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.
size | The octree will span (-size, -size, -size) to (size, size, size). |
polygons | A list of references to polygons that shall be inserted into the octree. |
graphVertices | A list of references to vertices that shall be inserted into the octree. |
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.
polygons | A list of pointers to Polygons that shall be inserted into the octree. |
graphVertices | A list of vertex-graph pairs that shall be inserted into the octree. |
indent | The indentation used for output. |
void Pathfinder::Octree::deleteOctree | ( | const bool & | root | ) |
Free all memory allocated to this octree and polygons.
root | A 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. |
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.
p | The point for which all vertices in its proximity shall be returned. |
indent | The indentation used for output. |
bool Pathfinder::Octree::pointInOctree | ( | const Geometry::Vec3 & | p, |
const std::string & | indent | ||
) |
Check if a point lies inside an octree.
p | The point that is to be checked. |
indent | The indentation used for output. |
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.
polygon | The poylgon that is to be checked. |
indent | The indentation used for output. |
std::vector<Octree*> Pathfinder::Octree::child |
Store pointers to the eight children of the octree.
Store graph vertices that lie in this octree together with a reference to their graph.
Geometry::Vec3 Pathfinder::Octree::max |
The AABBmax of the current cube.
Geometry::Vec3 Pathfinder::Octree::min |
The AABBmin of the current cube.
std::vector<Polygon*> Pathfinder::Octree::polygons |
Store pointers to Polygons that lie in this octree.