Pathfinder
Classes | Typedefs | Enumerations | Functions | Variables
Pathfinder Namespace Reference

Classes

struct  AABB
 This struct models an AABB. More...
 
struct  GraphEdge
 This struct declares all infromation that shall be stored for each edge of a graph. More...
 
struct  GraphVertex
 This struct declares all infroamtion that shall be stored for each vertex of a graph. More...
 
struct  Line2
 This struct represents a vertical 2D line or a line of the form y = mx + b. More...
 
struct  Line3
 This struct represents a 3D line of the form u = v + rw. More...
 
struct  Line3Norm
 This struct represents a line of the form u = v + rw where w is normalized to length 1. More...
 
struct  Line3Unnorm
 This struct represents a line of the form u = v + rw where ||w|| = 1 does not neccessarily hold. More...
 
class  MeshAccessor
 This class is used to simplify the accessing of meshes, their vertices and polygons. More...
 
struct  Octree
 This struct implements the octree data structure. More...
 
struct  Plane
 This struct models a plane of the form ax + by + cz + d = 0. More...
 
struct  Polygon
 A struct that represents a single polygon. More...
 

Typedefs

typedef std::function< void(EScript::Namespace *lib)> EScriptInitFunction_t
 
using Graph = boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, GraphVertex, GraphEdge >
 Shorthand notation for the graph used. More...
 
using Vertex = boost::graph_traits< Graph >::vertex_descriptor
 Shorthand notation for the graph vertices. More...
 
using Edge = boost::graph_traits< Graph >::edge_descriptor
 Shorthand notation for the graph edges. More...
 

Enumerations

enum  relativePosition : short {
  below, online, above, below,
  online, above
}
 Easier description of a point being above, below or on a line. More...
 
enum  relativePosition : short {
  below, online, above, below,
  online, above
}
 
enum  drivable : short {
  person, bicycle, car, truck,
  none
}
 This indicates the passability of edges. More...
 
enum  coordinate : short { x, y, z }
 Easier notation of coordinates. More...
 

Functions

bool AABBintersection (const AABB &a, const AABB &b)
 Check if two AABBs intersect. More...
 
std::string createOutputDirs ()
 Create a directory where all output is written to. More...
 
std::vector< Graph * > sceneAnalysis (const MinSG::ListNode &root)
 Perform the static analysis of the scene. More...
 
boost::optional< VertexnextSuccessor (const Graph *graph, const Vertex &v, const Vertex &goal, const short &agent, const std::vector< Vertex > &considered)
 This function yields the next vertex that shall be processed by A*. More...
 
float cost (const Graph *graph, const Vertex &ni, const Vertex &nj)
 Return the edge weight of the edge {ni, nj} in graph. More...
 
std::vector< Vertexastar (const Graph *graph, const Vertex &start, const Vertex &goal, const short &agent)
 Find a path from start to goal using A*. More...
 
std::vector< MinSG::GeometryNode * > extractGeometryNodes (const MinSG::ListNode &root)
 Build a list of all GeometryNodes in the scene graph. More...
 
std::vector< MeshAccessor * > createMeshAccessors (const std::vector< MinSG::GeometryNode * > &nodes)
 Create MeshAccessor objects for the given GeometryNodes. More...
 
short determineDrivability (const Geometry::Vec3 &v, const Geometry::Vec3 &w)
 Determine which agent is able to traverse the direct connection between the two points. More...
 
std::vector< Graph * > buildGraphList (const std::vector< MinSG::GeometryNode * > &nodes, const std::vector< MeshAccessor * > &meshAccessors)
 Build a graph for every mesh of a scene graph. More...
 
bool allVisited (const std::vector< bool > &boolVec)
 Check whether all entries in boolVec are true. More...
 
size_t getNextUnvisited (const std::vector< bool > &boolVec)
 Search in boolVec for the first value equal to false and return its index. More...
 
std::vector< std::vector< Graph * > > buildGroups (const std::vector< MinSG::GeometryNode * > &nodes, const std::vector< Graph * > &graphList)
 Compute the groups of possibly intersecting meshes. More...
 
bool compareSmallerVec3 (const Geometry::Vec3 &l, const Geometry::Vec3 &r)
 Compare two Vec3 instances for a lexicographic < relation. More...
 
bool compareEqualVec3 (const Geometry::Vec3 &l, const Geometry::Vec3 &r)
 Compare two Vec3 instances for equality. More...
 
bool compareSmallerEqualVec3 (const Geometry::Vec3 &l, const Geometry::Vec3 &r)
 Compare two Vec3 instances for a lexicographic <= relation. More...
 
bool compareSmallerVec3Tuple (const std::tuple< Geometry::Vec3, Geometry::Vec3 > &l, const std::tuple< Geometry::Vec3, Geometry::Vec3 > &r)
 Compare two tuples that contain Vec3 instances, for a lexicographic < relation. More...
 
bool compareEqualVec3Tuple (const std::tuple< Geometry::Vec3, Geometry::Vec3 > &l, const std::tuple< Geometry::Vec3, Geometry::Vec3 > &r)
 Compare two tuples that contain Vec3 instances, for equality. More...
 
bool compareSmallerVec3TupleTuple (const std::tuple< std::tuple< Geometry::Vec3, Geometry::Vec3 >, std::tuple< Geometry::Vec3, Geometry::Vec3 >> &l, const std::tuple< std::tuple< Geometry::Vec3, Geometry::Vec3 >, std::tuple< Geometry::Vec3, Geometry::Vec3 >> &r)
 Compare two tuples which contain tuples, for a lexicographic < relation. More...
 
bool compareEqualVec3TupleTuple (const std::tuple< std::tuple< Geometry::Vec3, Geometry::Vec3 >, std::tuple< Geometry::Vec3, Geometry::Vec3 >> &l, const std::tuple< std::tuple< Geometry::Vec3, Geometry::Vec3 >, std::tuple< Geometry::Vec3, Geometry::Vec3 >> &r)
 Compare two tuples which contain tulpes, for equality. More...
 
bool compareEqualFloat (const float &l, const float &r)
 Compare two float values for equality. More...
 
bool compareSmallerFloat (const float &l, const float &r)
 Compare two float values for a < relation. More...
 
bool registerEScriptInit (const EScriptInitFunction_t &initFn)
 Register the initializer method. More...
 
short coordToDrop (const Polygon *tri)
 Decide which coordinate shall be dropped for flattening this polygon. More...
 
std::tuple< Geometry::Vec2, Geometry::Vec2, Geometry::Vec2 > flattenTri (const Polygon *tri, const short &coord)
 Flatten the given polygon onto the xy/xz/yz plane. More...
 
Geometry::Vec2 flattenVec3 (const Geometry::Vec3 &a, const short &coord)
 Flatten the given vector onto the xy/xz/yz plane. More...
 
std::tuple< short, short, short > determineRelativePos (Geometry::Vec2 point, const std::tuple< Line2, Line2, Line2 > &tri)
 Determine the relative position of a point to three lines. More...
 
std::vector< bool > pointVecInsideTri (const std::vector< Geometry::Vec3 > &pointVec, const std::tuple< Line2, Line2, Line2 > &tri, const short &droppedCoord, const std::tuple< short, short, short > &relPosCenter)
 For a vector of points in three-dimensional space, determine if the inidividual points lie inside or outside a polygon. More...
 
std::vector< bool > pointVecInsideTri (const std::vector< Geometry::Vec2 > &pointVec, const std::tuple< Line2, Line2, Line2 > &tri, const std::tuple< short, short, short > &relPosCenter)
 For a vector of points in two-dimensional space, determine if the individual points lie inside or outside a polygon. More...
 
bool pointInsideTri (const Geometry::Vec3 &point, const std::tuple< Line2, Line2, Line2 > &tri, const short &droppedCoord, const std::tuple< short, short, short > &relPosCenter)
 For a point in three-dimensional space, determine if it lies inside or outside a given polygon. More...
 
bool pointInsideTri (const Geometry::Vec2 &point, const std::tuple< Line2, Line2, Line2 > &tri, const std::tuple< short, short, short > &relPosCenter)
 For a point in two-dimensional space, determine if it lies inside or outside a given polygon. More...
 
bool pointInRectangle (Geometry::Vec2 &p, Geometry::Vec2 &lowerLeft, Geometry::Vec2 &upperRight)
 Given a rectangle defined by two points, check if p lies inside it. More...
 
std::tuple< Geometry::Vec2, Geometry::Vec2 > buildRectangle (Geometry::Vec2 &pi, Geometry::Vec2 &pj)
 Given two points, construct a tuple of points that describe the lower left and upper right corner of the rectangle defined by the two points. More...
 
float t (const Plane &p, const Geometry::Vec3 &p1, const Geometry::Vec3 &p2)
 Compute the t value for a plane and two points that form a line. More...
 
std::tuple< std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short > > categorizetValueIndices (const std::tuple< float, float, float, float, float, float > &tValues)
 Sort each computed t into a tuple of vectors where each vector corresponds to one specific interval. More...
 
short determineIntersectionCase (const std::tuple< std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >> &categorizedtValueIndices)
 Determine which intersection case should be considered for the computed t values. More...
 
std::tuple< short, short > tIndex2endpoints (const short &id)
 Translate the index of the tValues vector to the endpoints which were involved in the t value computation. More...
 
short endpoints2tIndex (const std::tuple< short, short > &e)
 Translate a pair of endpoint indices into the corresponding index of the tValue vector. More...
 
short getEquivalenttValueIndex (const short &id)
 For a given index of the tValues tuple, return the index of the tValues tuple which contains the t value that was comuputed by the same vertices but in reverse order. More...
 
std::tuple< bool, bool, bool > intersectionTupleValid (Geometry::Vec2 &pi, Geometry::Vec2 &pj, const std::tuple< boost::optional< float >, boost::optional< float >, boost::optional< float >> &intersections, const std::tuple< Line2, Line2, Line2 > &tri, const std::tuple< short, short, short > &relPosCenter)
 
boost::optional< short > chooseIntersection (const std::tuple< Line2, Line2, Line2 > &tri, const std::tuple< boost::optional< float >, boost::optional< float >, boost::optional< float >> &intersections, const std::tuple< bool, bool, bool > &valid, Geometry::Vec2 &pjFlat)
 When moving a point on an intersection line, determine which intersection to use as a new endpoint. More...
 
float distanceToNewPoint (const Line3Norm &lij, const short &droppedCoord, const float &pointX, const float &pointY)
 
boost::optional< Geometry::Vec3 > cutPointToPolygon (const Geometry::Vec3 &pi, const Geometry::Vec3 &pj, const short &droppedCoord, const std::vector< bool > &inside, const Polygon *tri, const std::tuple< Line2, Line2, Line2 > &triLines, const std::tuple< short, short, short > &relPosCenter)
 
std::vector< std::vector< Geometry::Vec3 > > cutPlaneIntersectionsToPolygon (const Polygon *tri, const std::vector< std::vector< Geometry::Vec3 >> &intersections)
 
std::tuple< float, float, float, float, float, float > computetValues (const Plane &p, const Polygon *tri)
 Given a plane and a polygon, compute the six possible t values. More...
 
std::vector< uint32_t > polygonInAABBIds (MeshAccessor *ma, AABB aabb)
 Compute which polygons of the mesh managed by ma intersect with the AABB aabb. More...
 
std::vector< Geometry::Vec3 > handleIntersectionCase1 (Polygon *tri, const std::tuple< float, float, float, float, float, float > &tValues, const std::tuple< std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >> &categorizedtValueIndices)
 Do the necessary computations to obtain the intersection endpoints for intersection case 1. More...
 
std::vector< Geometry::Vec3 > handleIntersectionCase2 (const Polygon *tri, const std::tuple< float, float, float, float, float, float > &tValues, const std::tuple< std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >> &categorizedtValueIndices)
 Do the necessary computations to obtain the intersection endpoints for intersection case 2. More...
 
Geometry::Vec3 handleIntersectionCase2ii (const Polygon *tri, const short &vertexOnPlane, const std::tuple< float, float, float, float, float, float > &tValues)
 Do the necessary computations to obtain the additional intersection endpoint for intersection case 2ii. More...
 
std::vector< Geometry::Vec3 > handleIntersectionCase3 (Polygon *tri, const std::tuple< std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >> &categorizedtValueIndices)
 Do the necessary computations to obtain the intersection endpoints for intersection case 3. More...
 
std::vector< std::tuple< Graph *, Graph *, std::vector< Geometry::Vec3 > > > intersection (Graph *smaller, Graph *bigger)
 Compute the intersection between the meshes. More...
 
std::tuple< bool, bool, bool > intersectionTupleValid (Geometry::Vec2 &pi, Geometry::Vec2 &pj, const std::tuple< boost::optional< float >, boost::optional< float >, boost::optional< float >> &intersections, const std::tuple< Line2, Line2, Line2 > &tri, const std::tuple< bool, bool, bool > &centerAbove)
 For a given tuple of found intersections, determine if these are valid. More...
 
float distanceToNewPoint (const Line3 &lij, const short &droppedCoord, const float &pointX, const float &pointY)
 When calculating the point on a line that corresponds to a 2D point, determine the distance this new point has from the support vector of the line. More...
 
boost::optional< Geometry::Vec3 > cutPointToPolygon (const Geometry::Vec3 &pi, const Geometry::Vec3 &pj, const short &droppedCoord, const std::vector< bool > &inside, const std::tuple< Line2, Line2, Line2 > &tri)
 For a given polygon and a pair of endpoints, determine a new endpoint for this intersection line which lies inside tri. More...
 
std::vector< std::vector< boost::optional< Geometry::Vec3 > > > cutPlaneIntersectionsToPolygon (const std::vector< Geometry::Vec3 > &tri, const std::vector< std::vector< Geometry::Vec3 >> &intersections)
 For a given polygon and a list of intersections with the plane defined by that polygon, edit these intersections to fit the size of the actual polygon. More...
 
boost::optional< float > line2Intersection (const Line2 &a, const Line2 &b)
 Compute the x value of the intersection of two lines. More...
 
std::vector< std::pair< Vertex, Graph * > > determineMergePoints (const Geometry::Vec3 &p, Graph *graphA, Graph *graphB, const Octree *octree, AABB &aabb)
 Get the points to which a intersection point shall be connected. More...
 
Graphmerge (const std::vector< Graph * > &group, Octree *octree)
 Create one big graph out of the given group. More...
 
bool operator== (const MeshAccessor &l, const MeshAccessor &r)
 Overload operator==. More...
 
std::tuple< size_t, size_t, size_t > getOBJIndices (const std::list< Geometry::Vec3 > &vertices, const Geometry::Vec3 &a, const Geometry::Vec3 &b, const Geometry::Vec3 &c)
 Given three points, get their names for an OBJ file. More...
 
void writeOBJFromMesh (const MinSG::GeometryNode *geoNodePtr, const std::string &path)
 Go through the mesh associated with geoNodePtr and print the appropriate OBJ commands. More...
 
void writeOBJFromGraph (const Graph *graph, const std::string &path)
 Go through graph and output appropriate OBJ commands. More...
 
void appendPointcloudOBJFile (const std::vector< Geometry::Vec3 > &points, const std::string &path)
 Given a list of points, append all of these points onto the file at location path. More...
 
void writeIntersectionOBJFiles (const std::vector< std::tuple< Graph *, Graph *, std::vector< Geometry::Vec3 >> > &intersections, const std::string &path)
 
void writeIntersectionOBJFiles (const std::vector< std::tuple< Graph *, Graph *, std::vector< Geometry::Vec3 >>> &intersections, const std::string &path)
 Given a list of intersections, write all convex hulls of the intersections to OBJ files at the specified path. More...
 
OctreecreateOctree (const std::vector< Graph * > &graphList)
 Given the output of buildGraphList, create an octree containing all polygons and vertices. More...
 
void printOctree (const Octree *octree, const std::string &indent)
 Output a graphical representation of an octree to the console. More...
 
void disableOutput ()
 Prevents any output from being printed onto the terminal. More...
 
void enableOutput ()
 Permits all output to be printed onto the terminal. More...
 
void disableLogging ()
 Prevents the creation of log files. More...
 
void enableLogging ()
 Permits the creation of log files. More...
 
void createLoggers (const std::string &dir)
 Create all logger objects used throughout the code. More...
 
void disableOBJ ()
 Prevent any OBJ files from being created. More...
 
boost::optional< std::pair< Vertex, Vertex > > findStartGoal (const Geometry::Vec3 &start, const Geometry::Vec3 &goal, const Graph *graph)
 Given 2 points in 3D space, approximate these points by nodes in the graph while adhering to a maximum distance threshold. More...
 
EScript::Array * findPath (const MinSG::ListNode &root, const Geometry::Vec3 &start, const Geometry::Vec3 &goal, const short &agent)
 Do the scene analysis and pathfinding. More...
 
void sortSizeTTuple (std::tuple< size_t, size_t, size_t > &t)
 TODO. More...
 
void sortVec3Tuple (std::tuple< Geometry::Vec3, Geometry::Vec3 > &t)
 TODO. More...
 
void sortVec3TupleTuple (std::tuple< std::tuple< Geometry::Vec3, Geometry::Vec3 >, std::tuple< Geometry::Vec3, Geometry::Vec3 > > &t)
 
void sortVec3TupleTuple (std::tuple< std::tuple< Geometry::Vec3, Geometry::Vec3 >, std::tuple< Geometry::Vec3, Geometry::Vec3 >> &t)
 TODO. More...
 
float gettValue (const std::tuple< float, float, float, float, float, float > &tValues, const short &idx)
 Access the element at index idx. More...
 
std::vector< short > gettValueIndexCategoryVector (const std::tuple< std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >> &categorizedtValueIndices, const short &idx)
 Access the element at index idx. More...
 
Line2 getLine2 (const std::tuple< Line2, Line2, Line2 > &lines, const short &idx)
 Access the element at index idx. More...
 
bool * getBoolPtr (std::tuple< bool, bool, bool > &boolTuple, const short &idx)
 Access the element at index idx and return a pointer to it. More...
 
short * getShortPtr (std::tuple< short, short, short > &shortTuple, const short &idx)
 Access the element at index idx and return a pointer to it. More...
 
boost::optional< float > getOptionalFloat (const std::tuple< boost::optional< float >, boost::optional< float >, boost::optional< float >> &optionalFloatTuple, const short &idx)
 Access the element at index idx. More...
 
bool getBool (const std::tuple< bool, bool, bool > &boolTuple, const short &idx)
 Access the element at index idx. More...
 
Geometry::Vec3 getTriVertex (const std::tuple< Geometry::Vec3, Geometry::Vec3, Geometry::Vec3 > &tri, const short &idx)
 Access the vertex at index idx. More...
 
Geometry::Vec2 getFlatTriVertex (const std::tuple< Geometry::Vec2, Geometry::Vec2, Geometry::Vec2 > &tri, const short &idx)
 Access the vertex at index idx. More...
 
const std::string red ("\3[0;31m")
 Color definition for prettier console output. More...
 
const std::string green ("\3[1;32m")
 Color definition for prettier console output. More...
 
const std::string yellow ("\3[1;33m")
 Color definition for prettier console output. More...
 
const std::string cyan ("\3[0;36m")
 Color definition for prettier console output. More...
 
const std::string magenta ("\3[0;35m")
 Color definition for prettier console output. More...
 
const std::string reset ("\3[0m")
 Color definition for prettier console output. More...
 
Geometry::Vec3 crossProduct (const Geometry::Vec3 &a, const Geometry::Vec3 &b)
 Compute the cross product of two vectors. More...
 
float dotProduct (const Geometry::Vec3 &a, const Geometry::Vec3 &b)
 Compute the dot product of two vectors. More...
 
Geometry::Vec3 scalarMultiplication (const float &a, const Geometry::Vec3 &b)
 Scale a vector by a scalar. More...
 
bool operator< (const Geometry::Vec3 &l, const Geometry::Vec3 &r)
 Overload operator<. More...
 
float distance2 (Geometry::Vec2 &p1, Geometry::Vec2 &p2)
 Compute the euclidean distance between two points in 2D. More...
 
float distance3 (const Geometry::Vec3 &v1, const Geometry::Vec3 &v2)
 Compute the euclidean distance between two nodes. More...
 

Variables

const short threshold = 10
 If this threshold is reached, stop octree recursion. More...
 
bool objOutput = true
 Indicate whether OBJ files shall be created. More...
 
const float allowedStartEndDistance = 5
 

Typedef Documentation

◆ Edge

using Pathfinder::Edge = typedef boost::graph_traits<Graph>::edge_descriptor

Shorthand notation for the graph edges.

◆ EScriptInitFunction_t

typedef std::function<void (EScript::Namespace* lib)> Pathfinder::EScriptInitFunction_t

◆ Graph

using Pathfinder::Graph = typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, GraphVertex, GraphEdge>

Shorthand notation for the graph used.

◆ Vertex

using Pathfinder::Vertex = typedef boost::graph_traits<Graph>::vertex_descriptor

Shorthand notation for the graph vertices.

Enumeration Type Documentation

◆ coordinate

enum Pathfinder::coordinate : short

Easier notation of coordinates.

Enumerator

◆ drivable

enum Pathfinder::drivable : short

This indicates the passability of edges.

Enumerator
person 
bicycle 
car 
truck 
none 

◆ relativePosition [1/2]

Easier description of a point being above, below or on a line.

Enumerator
below 
online 
above 
below 
online 
above 

◆ relativePosition [2/2]

Enumerator
below 
online 
above 
below 
online 
above 

Function Documentation

◆ AABBintersection()

bool Pathfinder::AABBintersection ( const AABB a,
const AABB b 
)

Check if two AABBs intersect.

The involved check is presented in the thesis.

Parameters
aThe first AABB.
bThe second AABB.
Returns
Return true if the AABBs intersect, false otherwise.

◆ allVisited()

bool Pathfinder::allVisited ( const std::vector< bool > &  boolVec)

Check whether all entries in boolVec are true.

Parameters
boolVecA vector of boolean values.
Returns
Return true if all entries in boolVec are true, false otherwise.

◆ appendPointcloudOBJFile()

void Pathfinder::appendPointcloudOBJFile ( const std::vector< Geometry::Vec3 > &  points,
const std::string &  path 
)

Given a list of points, append all of these points onto the file at location path.

Parameters
pointsA vector which contains the points that shall be written to a file.
pathThe path to OBJ file.

◆ astar()

std::vector< Vertex > Pathfinder::astar ( const Graph graph,
const Vertex start,
const Vertex goal,
const short &  agent 
)

Find a path from start to goal using A*.

This path must be passable by agent.

This is the IDA* algorithm presented in 4.4.

Parameters
graphA pointer to the graph that is worked on.
startThe vertex description of the starting point.
goalThe vertex description of the goal point.
agentThe agent that shall traverse the graph.
Returns
Returns a vector contaning all vertices on the shortest path from start to goal that is passable by agent.

◆ buildGraphList()

std::vector< Graph * > Pathfinder::buildGraphList ( const std::vector< MinSG::GeometryNode * > &  nodes,
const std::vector< MeshAccessor * > &  meshAccessors 
)

Build a graph for every mesh of a scene graph.

Given a list of GeometryNodes, get the meshes stored in them and convert these meshes into graphs. This is done by taking the vertices of the mesh and translating them into the vertices of a graph. The edges of the graph correspond to the connections of the mesh's vertices that form the polygons.

Parameters
nodesA vector of pointers to the GeometryNodes of the scene graph.
meshAccessorsA vector of pointers to the MeshAccessors created for the GeometryNodes of nodes.
Returns
Return a vector of pointers to graphs.

◆ buildGroups()

std::vector< std::vector< Graph * > > Pathfinder::buildGroups ( const std::vector< MinSG::GeometryNode * > &  nodes,
const std::vector< Graph * > &  graphList 
)

Compute the groups of possibly intersecting meshes.

Two meshes have the possibility of intersection of their AABBs intersect. If the AABBs of A and B and the AABBs of B and C intersect, A, B, and C all end up in the same group.

Parameters
nodesA vector of pointers to GeometryNodes.
graphListA vector of pointers to graphs.
Returns
Return a vector of groups of possibly intersecting meshes. Each group is a vector of pointers to graphs.

◆ buildRectangle()

std::tuple< Geometry::Vec2, Geometry::Vec2 > Pathfinder::buildRectangle ( Geometry::Vec2 &  pi,
Geometry::Vec2 &  pj 
)

Given two points, construct a tuple of points that describe the lower left and upper right corner of the rectangle defined by the two points.

A rectangle can be defined by any two points. This function computes two points that define the same rectangle but are the lower left and upper right corner of the rectangle.

Parameters
piThe first point.
pjThe second point.
Returns
Return a tuple containing the lower left and upper right corner of the rectangle defined by pi and pj.

◆ categorizetValueIndices()

std::tuple< std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short > > Pathfinder::categorizetValueIndices ( const std::tuple< float, float, float, float, float, float > &  tValues)

Sort each computed t into a tuple of vectors where each vector corresponds to one specific interval.

Each vector stores the indices of those values in tValues which fall into the interval represented by that vector. The intervals are: 0 = (-infinity,0), 1 = [0,0], 2 = (0,1), 3 = [1,1], 4 = (1,infinity).

Parameters
tValuesA vector of 6 elements which contains the computed t values for one poylgon.
Returns
Return a tuple containing 5 vectors that in turn contain short values.

◆ chooseIntersection()

boost::optional< short > Pathfinder::chooseIntersection ( const std::tuple< Line2, Line2, Line2 > &  tri,
const std::tuple< boost::optional< float >, boost::optional< float >, boost::optional< float >> &  intersections,
const std::tuple< bool, bool, bool > &  valid,
Geometry::Vec2 &  pjFlat 
)

When moving a point on an intersection line, determine which intersection to use as a new endpoint.

This point should be the intersection which is valid and the closest to the point which shall be moved.

Parameters
triThe current polygon described by a tuple of bounding lines.
intersectionsA tuple that contains the computed intersections of an intersection line with tri.
validA tuple that indicates which of the intersections in intersections are valid.
pjFlatThe flattened version of the point that is to be moved.
Returns
Return the index of the intersection which is closest to the point that is to be moved. If no such intersection exists, boost::none is returned.

◆ compareEqualFloat()

bool Pathfinder::compareEqualFloat ( const float &  l,
const float &  r 
)

Compare two float values for equality.

The given values are not compared by the use of ==. This function computes the distance of l and r and checks if this lies within some epsilon. If so, the two values are considered equal.

Parameters
lThe first float value.
rThe second float value.
Returns
Return true if l == r, false otherwise.

◆ compareEqualVec3()

bool Pathfinder::compareEqualVec3 ( const Geometry::Vec3 &  l,
const Geometry::Vec3 &  r 
)

Compare two Vec3 instances for equality.

Two Vec3s are equal if their contents are the same.

Parameters
lThe first Vec3.
rThe second Vec3.
Returns
Return true if l == r, false otherwise.

◆ compareEqualVec3Tuple()

bool Pathfinder::compareEqualVec3Tuple ( const std::tuple< Geometry::Vec3, Geometry::Vec3 > &  l,
const std::tuple< Geometry::Vec3, Geometry::Vec3 > &  r 
)

Compare two tuples that contain Vec3 instances, for equality.

Two such tuples are equal if their contents are the same.

Parameters
lThe first tuple.
rThe second tuple.
Returns
Return true if l == r, false otherwise.

◆ compareEqualVec3TupleTuple()

bool Pathfinder::compareEqualVec3TupleTuple ( const std::tuple< std::tuple< Geometry::Vec3, Geometry::Vec3 >, std::tuple< Geometry::Vec3, Geometry::Vec3 >> &  l,
const std::tuple< std::tuple< Geometry::Vec3, Geometry::Vec3 >, std::tuple< Geometry::Vec3, Geometry::Vec3 >> &  r 
)

Compare two tuples which contain tulpes, for equality.

Two such tuples are equal if their contents are the same.

Parameters
lThe first tuple.
rThe second tuple.
Returns
Return true if l == r, false otherwise.

◆ compareSmallerEqualVec3()

bool Pathfinder::compareSmallerEqualVec3 ( const Geometry::Vec3 &  l,
const Geometry::Vec3 &  r 
)

Compare two Vec3 instances for a lexicographic <= relation.

Parameters
lThe first Vec3.
rThe second Vec3.
Returns
Return true if l <= r, false otherwise.

◆ compareSmallerFloat()

bool Pathfinder::compareSmallerFloat ( const float &  l,
const float &  r 
)

Compare two float values for a < relation.

This function first checks if l and r are the same by the use of compareEqualFloat. If so, this function returns false. Otherwise it returns what is returned by l < r.

Warning
If this returns false, l <= r does not hold!
Parameters
lThe first float value.
rThe second float value.
Returns
Return true if l < r, false otherwise.

◆ compareSmallerVec3()

bool Pathfinder::compareSmallerVec3 ( const Geometry::Vec3 &  l,
const Geometry::Vec3 &  r 
)

Compare two Vec3 instances for a lexicographic < relation.

Parameters
lThe first Vec3.
rThe second Vec3.
Returns
Return true if l < r, false otherwise.

◆ compareSmallerVec3Tuple()

bool Pathfinder::compareSmallerVec3Tuple ( const std::tuple< Geometry::Vec3, Geometry::Vec3 > &  l,
const std::tuple< Geometry::Vec3, Geometry::Vec3 > &  r 
)

Compare two tuples that contain Vec3 instances, for a lexicographic < relation.

Parameters
lThe first tuple.
rThe second tuple.
Returns
Return true if l < r, false otherwise.

◆ compareSmallerVec3TupleTuple()

bool Pathfinder::compareSmallerVec3TupleTuple ( const std::tuple< std::tuple< Geometry::Vec3, Geometry::Vec3 >, std::tuple< Geometry::Vec3, Geometry::Vec3 >> &  l,
const std::tuple< std::tuple< Geometry::Vec3, Geometry::Vec3 >, std::tuple< Geometry::Vec3, Geometry::Vec3 >> &  r 
)

Compare two tuples which contain tuples, for a lexicographic < relation.

Parameters
lThe first tuple.
rThe second tuple.
Returns
Return true if l < r, false otherwise.

◆ computetValues()

std::tuple< float, float, float, float, float, float > Pathfinder::computetValues ( const Plane p,
const Polygon tri 
)

Given a plane and a polygon, compute the six possible t values.

Parameters
pThe plane.
triThe polygon.
Returns
Return a tuple containing all 6 possible t values. The mapping of tuple position and vertex pairing is the following: 0 – 0, 1 1 – 0, 2 2 – 1, 0 3 – 1, 2 4 – 2, 0 5 – 2, 1

◆ coordToDrop()

short Pathfinder::coordToDrop ( const Polygon tri)

Decide which coordinate shall be dropped for flattening this polygon.

The component that shall be dropped is the component that has the greatest absolut value in the normal vector of the polygon.

Parameters
triThe polygon.
Returns
The component (x, y or z) which shall be dropped.

◆ cost()

float Pathfinder::cost ( const Graph graph,
const Vertex ni,
const Vertex nj 
)

Return the edge weight of the edge {ni, nj} in graph.

Parameters
graphA pointer to the graph that is worked on.
niThe first endpoint of the edge.
njThe second endpoint of the edge.
Returns
Returns the weight associated to the edge {ni, nj}.

◆ createLoggers()

void Pathfinder::createLoggers ( const std::string &  dir)

Create all logger objects used throughout the code.

Parameters
dirThe directory where the log files shall be written to.

◆ createMeshAccessors()

std::vector< MeshAccessor * > Pathfinder::createMeshAccessors ( const std::vector< MinSG::GeometryNode * > &  nodes)

Create MeshAccessor objects for the given GeometryNodes.

Go through the list of GeometryNodes and create one MeshAccessor object per node.

Parameters
nodesA vector of pointers to GeometryNodes.
Returns
Return a vector of pointers to MeshAccessor objects.

◆ createOctree()

Octree * Pathfinder::createOctree ( const std::vector< Graph * > &  graphList)

Given the output of buildGraphList, create an octree containing all polygons and vertices.

Parameters
graphListThe output of the builGraphList function.
Returns
Return a pointer to the octree that was constructed.

◆ createOutputDirs()

std::string Pathfinder::createOutputDirs ( )

Create a directory where all output is written to.

This function will create a directory in ../Output. The directory will be named after the current timestamp.

Returns
Returns a string that contains the relative path to the created output directory.

◆ crossProduct()

Geometry::Vec3 Pathfinder::crossProduct ( const Geometry::Vec3 &  a,
const Geometry::Vec3 &  b 
)

Compute the cross product of two vectors.

Parameters
aThe first vector.
bThe second vector.
Returns
The cross product of a and b.

◆ cutPlaneIntersectionsToPolygon() [1/2]

std::vector<std::vector<boost::optional<Geometry::Vec3> > > Pathfinder::cutPlaneIntersectionsToPolygon ( const std::vector< Geometry::Vec3 > &  tri,
const std::vector< std::vector< Geometry::Vec3 >> &  intersections 
)

For a given polygon and a list of intersections with the plane defined by that polygon, edit these intersections to fit the size of the actual polygon.

This might involve discarding intersections or cutting them to the appropriate size.

Parameters
triA polygon defined by three vertices.
intersectionsA vector of vectors which contain the endpoints of the intersections with plane defined by tri.
Returns
Return a vector of vectors containing the endpoints of the edited intersections. If some intersection points needed to be discarded, they are returned as boost::none. The indices are unchanged from intersections.

◆ cutPlaneIntersectionsToPolygon() [2/2]

std::vector<std::vector<Geometry::Vec3> > Pathfinder::cutPlaneIntersectionsToPolygon ( const Polygon tri,
const std::vector< std::vector< Geometry::Vec3 >> &  intersections 
)

◆ cutPointToPolygon() [1/2]

boost::optional<Geometry::Vec3> Pathfinder::cutPointToPolygon ( const Geometry::Vec3 &  pi,
const Geometry::Vec3 &  pj,
const short &  droppedCoord,
const std::vector< bool > &  inside,
const std::tuple< Line2, Line2, Line2 > &  tri 
)

For a given polygon and a pair of endpoints, determine a new endpoint for this intersection line which lies inside tri.

Parameters
piThe first endpoint of the intersection line.
pjThe second endpoint of the intersection line.
droppedCoordThe coordinate that was dropped while flattening the tri.
insideThe vector which holds the information on which points lie inside tri.
triThe current flattened polygon described by three bounding lines.
Returns
Return the new endpoint for the intersection. If no such point could be found, boost::none is returned.

◆ cutPointToPolygon() [2/2]

boost::optional<Geometry::Vec3> Pathfinder::cutPointToPolygon ( const Geometry::Vec3 &  pi,
const Geometry::Vec3 &  pj,
const short &  droppedCoord,
const std::vector< bool > &  inside,
const Polygon tri,
const std::tuple< Line2, Line2, Line2 > &  triLines,
const std::tuple< short, short, short > &  relPosCenter 
)

◆ cyan()

const std::string Pathfinder::cyan ( "\0;36m"  )

Color definition for prettier console output.

◆ determineDrivability()

short Pathfinder::determineDrivability ( const Geometry::Vec3 &  v,
const Geometry::Vec3 &  w 
)

Determine which agent is able to traverse the direct connection between the two points.

Determine the slope of the direct connecton between the two points. Which agent corresponds to which slope is mentioned in the thesis.

Parameters
vThe first point.
wThe second point.
Returns
Returns a number that corresponds to the agents that can traverse an edge.

◆ determineIntersectionCase()

short Pathfinder::determineIntersectionCase ( const std::tuple< std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >> &  categorizedtValueIndices)

Determine which intersection case should be considered for the computed t values.

Given the computed t values for an intersection, a case distinction can be made. The details are provided in the thesis.

Parameters
categorizedtValueIndicesA tuple of 5 vectors which shows how many t values fall into which interval.
Returns
Return a number representing the found intersection case. 0 = no intersection, 1 = (1), ..., 4 = (4).

◆ determineMergePoints()

std::vector< std::pair< Vertex, Graph * > > Pathfinder::determineMergePoints ( const Geometry::Vec3 &  p,
Graph graphA,
Graph graphB,
const Octree octree,
AABB aabb 
)

Get the points to which a intersection point shall be connected.

The point p shall be connected to the two nearest points in either graph that are outside the given AABB.

Parameters
pThe point that shall be connected.
graphAThe first graph.
graphBThe second graph.
octreeAn octree that encompasses the whole scene.
aabbAn AABB that defines a volume where no connections shall be made.
Returns
Returns the two points that shall be used for the new connections.

◆ determineRelativePos()

std::tuple< short, short, short > Pathfinder::determineRelativePos ( Geometry::Vec2  point,
const std::tuple< Line2, Line2, Line2 > &  tri 
)

Determine the relative position of a point to three lines.

For a given point and a triangle described by three lines in two-dimensional space, compute a tuple which contains the information on whether the given point lies above, on or below the individual bounding lines of the triangle. If a bounding line is vertical, above means that point is right of the line. If the value is set to below, this means that point is left of the line.

Parameters
pointThe point for which it shall be evaluated if it lies above, on or below the individual lines.
triA triangle described by a tuple of three Line2 objects.
Returns
Return a tulpe of three short values which tell if the point lies above, on or below the corresponding line in tri.

◆ disableLogging()

void Pathfinder::disableLogging ( )

Prevents the creation of log files.

◆ disableOBJ()

void Pathfinder::disableOBJ ( )

Prevent any OBJ files from being created.

◆ disableOutput()

void Pathfinder::disableOutput ( )

Prevents any output from being printed onto the terminal.

◆ distance2()

float Pathfinder::distance2 ( Geometry::Vec2 &  p1,
Geometry::Vec2 &  p2 
)

Compute the euclidean distance between two points in 2D.

Parameters
p1The first point.
p2The second point.
Returns
The euclidean distance between p1 and p2.

◆ distance3()

float Pathfinder::distance3 ( const Geometry::Vec3 &  v1,
const Geometry::Vec3 &  v2 
)

Compute the euclidean distance between two nodes.

Given three points in 3D, compute the length of the straight line between the two points.

Parameters
v1The position of the first node.
v2The position of the second node.
Returns
The euclidean distance between the two nodes.

◆ distanceToNewPoint() [1/2]

float Pathfinder::distanceToNewPoint ( const Line3 lij,
const short &  droppedCoord,
const float &  pointX,
const float &  pointY 
)

When calculating the point on a line that corresponds to a 2D point, determine the distance this new point has from the support vector of the line.

Parameters
lijThe 3D line for which a distance from the support vector to a point shall be calculated.
droppedCoordThe component that was dropped while flattening in the current step.
pointXThe x position of the 2D point.
pointYThe y position of the 2D point.
Returns
Return the distance from the new point on the line to the support vector of the line.

◆ distanceToNewPoint() [2/2]

float Pathfinder::distanceToNewPoint ( const Line3Norm lij,
const short &  droppedCoord,
const float &  pointX,
const float &  pointY 
)

◆ dotProduct()

float Pathfinder::dotProduct ( const Geometry::Vec3 &  a,
const Geometry::Vec3 &  b 
)

Compute the dot product of two vectors.

Parameters
aThe first vector.
bThe second vector.
Returns
The dot product of a and b.

◆ enableLogging()

void Pathfinder::enableLogging ( )

Permits the creation of log files.

◆ enableOutput()

void Pathfinder::enableOutput ( )

Permits all output to be printed onto the terminal.

◆ endpoints2tIndex()

short Pathfinder::endpoints2tIndex ( const std::tuple< short, short > &  e)

Translate a pair of endpoint indices into the corresponding index of the tValue vector.

Every possible combination of two different vertices of a polygon has a certain index in the t values tuple. This function provides a convenient way to obtain the t value tuple index computed from the two given endpoints.

Parameters
eAn edge represented by a vector of two endpoint indices.
Returns
Return the index of the computed t value in the tuple tValues.

◆ extractGeometryNodes()

std::vector< MinSG::GeometryNode * > Pathfinder::extractGeometryNodes ( const MinSG::ListNode &  root)

Build a list of all GeometryNodes in the scene graph.

Given the root node of a scene graph, traverse the scene graph and store all GeometryNodes that have been found in a vector.

Parameters
rootThe root node of the scene graph.
Returns
Return a vector containing pointers to all GeometryNodes of the scene graph.

◆ findPath()

EScript::Array * Pathfinder::findPath ( const MinSG::ListNode &  root,
const Geometry::Vec3 &  start,
const Geometry::Vec3 &  goal,
const short &  agent 
)

Do the scene analysis and pathfinding.

Parameters
rootThe root node of the scene graph.
startThe start point of the pathfinding.
goalThe goal point of the pathfinding.
agentThe agent that shall be used for pathfinding.
Returns
Return an EScript array which contains all nodes of the found path.

◆ findStartGoal()

boost::optional< std::pair< Vertex, Vertex > > Pathfinder::findStartGoal ( const Geometry::Vec3 &  start,
const Geometry::Vec3 &  goal,
const Graph graph 
)

Given 2 points in 3D space, approximate these points by nodes in the graph while adhering to a maximum distance threshold.

Parameters
startThe start point.
goalThe goal point.
graphThe graph in which adequate start and goal vertices shall be searched.
Returns
Return a pair of vertices that approximate start and goal. If no such vertices exist, return boost::none.

◆ flattenTri()

std::tuple< Geometry::Vec2, Geometry::Vec2, Geometry::Vec2 > Pathfinder::flattenTri ( const Polygon tri,
const short &  coord 
)

Flatten the given polygon onto the xy/xz/yz plane.

This is done by deleting all coord elements from the polygon's vertices.

Parameters
triThe polygon.
coordThe coordinate which shall be dropped.
Returns
A tuple of flattened coordinates in 2D space.

◆ flattenVec3()

Geometry::Vec2 Pathfinder::flattenVec3 ( const Geometry::Vec3 &  a,
const short &  coord 
)

Flatten the given vector onto the xy/xz/yz plane.

This is done by deleting the coord element from a.

Parameters
aThe vector to flatten.
coordThe coordinate which shall be dropped.
Returns
The vector flattened to a coordinate in 2D space.

◆ getBool()

bool Pathfinder::getBool ( const std::tuple< bool, bool, bool > &  boolTuple,
const short &  idx 
)

Access the element at index idx.

Parameters
boolTupleThe tuple containing tree bool values.
idxThe index on which access shall be performed.
Returns
The value of the tuple at the desired index.

◆ getBoolPtr()

bool * Pathfinder::getBoolPtr ( std::tuple< bool, bool, bool > &  boolTuple,
const short &  idx 
)

Access the element at index idx and return a pointer to it.

Parameters
boolTupleThe tuple containing three bool values.
idxThe index on which access shall be performed.
Returns
A pointer to the desired position in boolTuple.

◆ getEquivalenttValueIndex()

short Pathfinder::getEquivalenttValueIndex ( const short &  id)

For a given index of the tValues tuple, return the index of the tValues tuple which contains the t value that was comuputed by the same vertices but in reverse order.

Example: t value 0 and 2 are computed by the same two vertices of a given poylgon. However, the order of vertices is switched in the computations of the two t values.

Parameters
idThe index of the tValues tuple.
Returns
Return the index of the element in the tValues tuple which contains a value computed with the same endpoints in reverse order.

◆ getFlatTriVertex()

Geometry::Vec2 Pathfinder::getFlatTriVertex ( const std::tuple< Geometry::Vec2, Geometry::Vec2, Geometry::Vec2 > &  tri,
const short &  idx 
)

Access the vertex at index idx.

Parameters
triA tuple describing a flattened polygon.
idxThe index on which access shall be performed.
Returns
The flattened vertex stored at position idx.

◆ getLine2()

Line2 Pathfinder::getLine2 ( const std::tuple< Line2, Line2, Line2 > &  lines,
const short &  idx 
)

Access the element at index idx.

Parameters
linesThe tuple containing three Line2 objects.
idxThe index on which access shall be performed.
Returns
The Line2 object stored at position idx.

◆ getNextUnvisited()

size_t Pathfinder::getNextUnvisited ( const std::vector< bool > &  boolVec)

Search in boolVec for the first value equal to false and return its index.

Parameters
boolVecA vector of boolean values.
Returns
Return the first index of an entry in boolVec which is set to false. Return boolVec.size() if all entries were true.

◆ getOBJIndices()

std::tuple< size_t, size_t, size_t > Pathfinder::getOBJIndices ( const std::list< Geometry::Vec3 > &  vertices,
const Geometry::Vec3 &  a,
const Geometry::Vec3 &  b,
const Geometry::Vec3 &  c 
)

Given three points, get their names for an OBJ file.

Search through the vertex list and return the indices of the

Parameters
verticesA list of all vertices.
aThe first point.
bThe second point.
cThe third point.
Returns
Returns a tuple that contains the names of the three points.

◆ getOptionalFloat()

boost::optional< float > Pathfinder::getOptionalFloat ( const std::tuple< boost::optional< float >, boost::optional< float >, boost::optional< float >> &  optionalFloatTuple,
const short &  idx 
)

Access the element at index idx.

Parameters
optionalFloatTupleThe tuple containing boost::optional<float> values.
idxThe index on which access shall be performed.
Returns
The value of the tuple at the desired index.

◆ getShortPtr()

short * Pathfinder::getShortPtr ( std::tuple< short, short, short > &  shortTuple,
const short &  idx 
)

Access the element at index idx and return a pointer to it.

Parameters
shortTupleThe tuple containing three short values.
idxThe index on which access shall be performed.
Returns
A pointer to the desired position in shortTuple.

◆ getTriVertex()

Geometry::Vec3 Pathfinder::getTriVertex ( const std::tuple< Geometry::Vec3, Geometry::Vec3, Geometry::Vec3 > &  tri,
const short &  idx 
)

Access the vertex at index idx.

Parameters
triA tuple describing a polygon.
idxThe index on which access shall be performed.
Returns
The vertex stored at position idx.

◆ gettValue()

float Pathfinder::gettValue ( const std::tuple< float, float, float, float, float, float > &  tValues,
const short &  idx 
)

Access the element at index idx.

Parameters
tValuesThe tValues tuple containing 6 float values.
idxThe index on which access shall be performed.
Returns
The t value stored at position idx.

◆ gettValueIndexCategoryVector()

std::vector< short > Pathfinder::gettValueIndexCategoryVector ( const std::tuple< std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >> &  categorizedtValueIndices,
const short &  idx 
)

Access the element at index idx.

Parameters
categorizedtValueIndicesThe tuple containing 5 vectors which represent the intervals used for case distinction.
idxThe index on which access shall be performed.
Returns
The vector stored at position idx.

◆ green()

const std::string Pathfinder::green ( "\1;32m"  )

Color definition for prettier console output.

◆ handleIntersectionCase1()

std::vector< Geometry::Vec3 > Pathfinder::handleIntersectionCase1 ( Polygon tri,
const std::tuple< float, float, float, float, float, float > &  tValues,
const std::tuple< std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >> &  categorizedtValueIndices 
)

Do the necessary computations to obtain the intersection endpoints for intersection case 1.

Parameters
triThe polygon that intersects the current plane.
tValuesThe computed t values for the intersection of tri and the current plane.
categorizedtValueIndicesThe tuple containing the assignment of the indices in the tValues vector to the different value intervals.
Returns
Return a vector containing the endpoints of the intersection.

◆ handleIntersectionCase2()

std::vector< Geometry::Vec3 > Pathfinder::handleIntersectionCase2 ( const Polygon tri,
const std::tuple< float, float, float, float, float, float > &  tValues,
const std::tuple< std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >> &  categorizedtValueIndices 
)

Do the necessary computations to obtain the intersection endpoints for intersection case 2.

This includes the computation of the endpoint that lies on the current plane as well as deciding if case 2i. or 2ii. is present.

Parameters
triThe polygon that intersects the current plane.
tValuesThe computed t values for the intersection of tri and the current plane.
categorizedtValueIndicesThe tuple containing the assignment of the indices in the tValues vector to the different value intervals.
Returns
Returns a vector containing the endpoints of the intersection.

◆ handleIntersectionCase2ii()

Geometry::Vec3 Pathfinder::handleIntersectionCase2ii ( const Polygon tri,
const short &  vertexOnPlane,
const std::tuple< float, float, float, float, float, float > &  tValues 
)

Do the necessary computations to obtain the additional intersection endpoint for intersection case 2ii.

Parameters
triThe polygon that intersects the current plane.
vertexOnPlaneThe index of the vertex which lies on the current plane.
tValuesThe computed t values for the intersection of tri and the current plane.
Returns
Return the computed additional intersection endpoint.

◆ handleIntersectionCase3()

std::vector< Geometry::Vec3 > Pathfinder::handleIntersectionCase3 ( Polygon tri,
const std::tuple< std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >, std::vector< short >> &  categorizedtValueIndices 
)

Do the necessary computations to obtain the intersection endpoints for intersection case 3.

Parameters
triThe polygon that intersects the current plane.
categorizedtValueIndicesThe tuple containing the assignment of the indices in the tValues vector to the different value intervals.
Returns
Return a vector containing the endpoints of the intersection.

◆ intersection()

std::vector< std::tuple< Graph *, Graph *, std::vector< Geometry::Vec3 > > > Pathfinder::intersection ( Graph smaller,
Graph bigger 
)

Compute the intersection between the meshes.

Parameters
smallerThe smaller mesh.
biggerThe bigger mesh.
Returns
Return a vector with all found intersections.

◆ intersectionTupleValid() [1/2]

std::tuple<bool, bool, bool> Pathfinder::intersectionTupleValid ( Geometry::Vec2 &  pi,
Geometry::Vec2 &  pj,
const std::tuple< boost::optional< float >, boost::optional< float >, boost::optional< float >> &  intersections,
const std::tuple< Line2, Line2, Line2 > &  tri,
const std::tuple< short, short, short > &  relPosCenter 
)

◆ intersectionTupleValid() [2/2]

std::tuple<bool, bool, bool> Pathfinder::intersectionTupleValid ( Geometry::Vec2 &  pi,
Geometry::Vec2 &  pj,
const std::tuple< boost::optional< float >, boost::optional< float >, boost::optional< float >> &  intersections,
const std::tuple< Line2, Line2, Line2 > &  tri,
const std::tuple< bool, bool, bool > &  centerAbove 
)

For a given tuple of found intersections, determine if these are valid.

An intersection is valid if its x position lies between the x positions of the two points pi and pj.

Parameters
piThe first endpoint of the common intersection line.
pjThe second endpoint of the common intersection line.
intersectionsA tuple of three optional values representing the x positions of the intersections of the line through pi and pj and the three bounding lines of the polygon. If an intersection was found, a float value will reside at the corresponding position. If two lines were found to be parallel, a boost::none value will be placed at the corresponding index.
triThe triangle with which the intersections were computed.
centerAboveA tulpe describing the relative position of the center point of tri to its bounding lines.
Returns
Return a tuple of bool values. If a value is set to true, this means that the corresponding intersection in intersections is valid. If the value reads false, the intersection is invalid.

◆ line2Intersection()

boost::optional< float > Pathfinder::line2Intersection ( const Line2 a,
const Line2 b 
)

Compute the x value of the intersection of two lines.

Parameters
aThe first line.
bThe second line.
Returns
Return the x value of the intersection point of a and b if Return boost::none is a and b are parallel.

◆ magenta()

const std::string Pathfinder::magenta ( "\0;35m"  )

Color definition for prettier console output.

◆ merge()

Graph * Pathfinder::merge ( const std::vector< Graph * > &  group,
Octree octree 
)

Create one big graph out of the given group.

Parameters
groupThe group whose graphs shall be merged.
octreeA pointer to the octree that stores all information of the scene.
Returns
Return the merged graph.

◆ nextSuccessor()

boost::optional< Vertex > Pathfinder::nextSuccessor ( const Graph graph,
const Vertex v,
const Vertex goal,
const short &  agent,
const std::vector< Vertex > &  considered 
)

This function yields the next vertex that shall be processed by A*.

The function looks at all incident edges of v. Only those edges that are passable by agent are considered. The function then selects a candidate vertex that was not considered before.

Parameters
graphA pointer to the graph that is worked on.
vThe vertex whose successors shall be found.
goalThe goal node of the search.
agentOnly edges that are passable by agent shall be considered.
consideredA vector containing all already considered vertices.
Returns
Returns a possible successor of v that is reachable by agent. If such a successor does not exist, boost::none is returned.

◆ operator<()

bool Pathfinder::operator< ( const Geometry::Vec3 &  l,
const Geometry::Vec3 &  r 
)

Overload operator<.

Parameters
lThe left operand.
rThe right operand.
Returns
True if l is lexicographically smaller than r.

◆ operator==()

bool Pathfinder::operator== ( const MeshAccessor l,
const MeshAccessor r 
)

Overload operator==.

Two MeshAccessor objects are considered the same if both objects describe the same GeometryNode.

Parameters
lThe left operand.
rThe right operand.
Returns
Return true if the the geoNodePtr member variables of both operands are the same. Return false otherwise.

◆ pointInRectangle()

bool Pathfinder::pointInRectangle ( Geometry::Vec2 &  p,
Geometry::Vec2 &  lowerLeft,
Geometry::Vec2 &  upperRight 
)

Given a rectangle defined by two points, check if p lies inside it.

The point p lies inside the rectangle if its components are greater or equal to the lower left corner of the rectangle and smaller or equal to the upper right corner of the rectangle.

Parameters
pThe point which shall be checked.
lowerLeftThe lower left corner of the rectangle.
upperRightThe lower left corner of the rectangle.
Returns
Return true if p lies inside the rectangle, false otherwise.

◆ pointInsideTri() [1/2]

bool Pathfinder::pointInsideTri ( const Geometry::Vec3 &  point,
const std::tuple< Line2, Line2, Line2 > &  tri,
const short &  droppedCoord,
const std::tuple< short, short, short > &  relPosCenter 
)

For a point in three-dimensional space, determine if it lies inside or outside a given polygon.

A point lies inside a poylgon, if its relative positions to the polygon's bounding lines are the same as the relative positions of the polygon's center point to the polygon's bounding lines. If a point lies on a bounding line, it can be interpreted either way: as being above or below.

Parameters
pointThe point which is to be checked.
triA polygon described by a tuple of three 2D lines.
droppedCoordThe component which was dropped in the flattening of tri.
relPosCenterA tuple which describes the relative position of the center point of tri to the three bounding lines of tri.
Returns
Return true if the point lies inside tri, false otherwise.

◆ pointInsideTri() [2/2]

bool Pathfinder::pointInsideTri ( const Geometry::Vec2 &  point,
const std::tuple< Line2, Line2, Line2 > &  tri,
const std::tuple< short, short, short > &  relPosCenter 
)

For a point in two-dimensional space, determine if it lies inside or outside a given polygon.

A point lies inside a poylgon, if its relative positions to the polygon's bounding lines are the same as the relative positions of the polygon's center point to the polygon's bounding lines. If a point lies on a bounding line, it can be interpreted either way: as being above or below.

Parameters
pointThe point which is to be checked.
triA polygon described by a tuple of three 2D lines.
relPosCenterA tuple which describes the relative position of the center point of tri to the three bounding lines of tri.
Returns
Return true if the point lies inside tri, false otherwise.

◆ pointVecInsideTri() [1/2]

std::vector< bool > Pathfinder::pointVecInsideTri ( const std::vector< Geometry::Vec3 > &  pointVec,
const std::tuple< Line2, Line2, Line2 > &  tri,
const short &  droppedCoord,
const std::tuple< short, short, short > &  relPosCenter 
)

For a vector of points in three-dimensional space, determine if the inidividual points lie inside or outside a polygon.

A point lies inside a poylgon, if its relative positions to the polygon's bounding lines are the same as the relative positions of the polygon's center point to the polygon's bounding lines. If a point lies on a bounding line, it can be interpreted either way: as being above or below.

Parameters
pointVecA vector of points where each point shall be cheked for its position.
triA polygon described ba a tuple of three 2D lines.
droppedCoordThe component which was dropped in the flattening of tri.
relPosCenterA tuple which describes the relative position of the center point of tri to the three bounding lines of tri.
Returns
Return a vector of boolean values which indicate if the corresponding point in pointVec lies inside tri (true) or not (false).

◆ pointVecInsideTri() [2/2]

std::vector< bool > Pathfinder::pointVecInsideTri ( const std::vector< Geometry::Vec2 > &  pointVec,
const std::tuple< Line2, Line2, Line2 > &  tri,
const std::tuple< short, short, short > &  relPosCenter 
)

For a vector of points in two-dimensional space, determine if the individual points lie inside or outside a polygon.

A point lies inside a poylgon, if its relative positions to the polygon's bounding lines are the same as the relative positions of the polygon's center point to the polygon's bounding lines. If a point lies on a bounding line, it can be interpreted either way: as being above or below.

Parameters
pointVecA vector of points where each point shall be cheked for its position.
triA polygon described ba a tuple of three 2D lines.
relPosCenterA tuple which describes the relative position of the center point of tri to the three bounding lines of tri.
Returns
Return a vector of boolean values which indicate if the corresponding point in pointVec lies inside tri (true) or not (false).

◆ polygonInAABBIds()

std::vector< uint32_t > Pathfinder::polygonInAABBIds ( MeshAccessor ma,
AABB  aabb 
)

Compute which polygons of the mesh managed by ma intersect with the AABB aabb.

Parameters
maThe MeshAccessor of the mesh whose polygons shall be checked for intersection.
aabbThe AABB that shall be used for checking intersection.
Returns
Return a vector containing all indices of those polygons of the mesh managed by ma which intersect with the AABB aabb.

◆ printOctree()

void Pathfinder::printOctree ( const Octree octree,
const std::string &  indent 
)

Output a graphical representation of an octree to the console.

Parameters
octreeThe octree that shall be printed.
indentThe indentation that is prepended to every output to signal depth.

◆ red()

const std::string Pathfinder::red ( "\0;31m"  )

Color definition for prettier console output.

◆ registerEScriptInit()

bool Pathfinder::registerEScriptInit ( const EScriptInitFunction_t initFn)

Register the initializer method.

Implementation of the 'registerEScriptInit' function declared in 'EScriptHelper.h'.

◆ reset()

const std::string Pathfinder::reset ( "\0m"  )

Color definition for prettier console output.

◆ scalarMultiplication()

Geometry::Vec3 Pathfinder::scalarMultiplication ( const float &  a,
const Geometry::Vec3 &  b 
)

Scale a vector by a scalar.

Parameters
aThe scaling factor.
bThe vector.
Returns
Vector b scaled by a.

◆ sceneAnalysis()

std::vector< Graph * > Pathfinder::sceneAnalysis ( const MinSG::ListNode &  root)

Perform the static analysis of the scene.

Given the root node of a scene graph, get all GeometryNodes, build groups and the graphs of each group.

Parameters
rootThe root node of the scene.
Returns
Returns a vector of pointers to the graphs that were computed in the analysis.

◆ sortSizeTTuple()

void Pathfinder::sortSizeTTuple ( std::tuple< size_t, size_t, size_t > &  t)

TODO.

TODO

◆ sortVec3Tuple()

void Pathfinder::sortVec3Tuple ( std::tuple< Geometry::Vec3, Geometry::Vec3 > &  t)

TODO.

TODO

◆ sortVec3TupleTuple() [1/2]

void Pathfinder::sortVec3TupleTuple ( std::tuple< std::tuple< Geometry::Vec3, Geometry::Vec3 >, std::tuple< Geometry::Vec3, Geometry::Vec3 >> &  t)

TODO.

TODO

◆ sortVec3TupleTuple() [2/2]

void Pathfinder::sortVec3TupleTuple ( std::tuple< std::tuple< Geometry::Vec3, Geometry::Vec3 >, std::tuple< Geometry::Vec3, Geometry::Vec3 > > &  t)

◆ t()

float Pathfinder::t ( const Plane p,
const Geometry::Vec3 &  p1,
const Geometry::Vec3 &  p2 
)

Compute the t value for a plane and two points that form a line.

The computation of the t value is decribed in the thesis. It describes the distance of the intersection point of the plane with the line formed by p1 and p2, from one of the endpoints.

Parameters
pThe plane.
p1The first endpoint of the line.
p2The second endpoint of the line.
Returns
Return t according to the formula in the thesis.

◆ tIndex2endpoints()

std::tuple< short, short > Pathfinder::tIndex2endpoints ( const short &  id)

Translate the index of the tValues vector to the endpoints which were involved in the t value computation.

Every possible combination of two different vertices of a polygon has a certain index in the t values tuple. This function provides a convenient way to obtain the two endpoints involved in the computation of a certain t value.

Parameters
idThe index of the tValues vector.
Returns
Return a tuple of two numbers. These numbers represent the endpoints used for computing the t value with the index id in the tvalues tuple.

◆ writeIntersectionOBJFiles() [1/2]

void Pathfinder::writeIntersectionOBJFiles ( const std::vector< std::tuple< Graph *, Graph *, std::vector< Geometry::Vec3 >>> &  intersections,
const std::string &  path 
)

Given a list of intersections, write all convex hulls of the intersections to OBJ files at the specified path.

Parameters
intersectionsA vector containing all intersections for a group.
pathThe path to the directory where the OBJ files shall be written to.

◆ writeIntersectionOBJFiles() [2/2]

void Pathfinder::writeIntersectionOBJFiles ( const std::vector< std::tuple< Graph *, Graph *, std::vector< Geometry::Vec3 >> > &  intersections,
const std::string &  path 
)

◆ writeOBJFromGraph()

void Pathfinder::writeOBJFromGraph ( const Graph graph,
const std::string &  path 
)

Go through graph and output appropriate OBJ commands.

Parameters
graphThe graph which shall be transformed.
pathThe path to the file where the data shall be written to.

◆ writeOBJFromMesh()

void Pathfinder::writeOBJFromMesh ( const MinSG::GeometryNode *  geoNodePtr,
const std::string &  path 
)

Go through the mesh associated with geoNodePtr and print the appropriate OBJ commands.

Parameters
geoNodePtrA pointer to the GeometryNode.
pathThe path to the file where the data shall be written to.

◆ yellow()

const std::string Pathfinder::yellow ( "\1;33m"  )

Color definition for prettier console output.

Variable Documentation

◆ allowedStartEndDistance

const float Pathfinder::allowedStartEndDistance = 5

◆ objOutput

bool Pathfinder::objOutput = true

Indicate whether OBJ files shall be created.

◆ threshold

const short Pathfinder::threshold = 10

If this threshold is reached, stop octree recursion.