HF::GraphGenerator Namespace Reference

Generate a graph of accessible space from a given start point. More...

Classes
struct	GeometryFlagMap
	Manages rules and ids for different types of geometry in the graph generator. More...
class	GraphGenerator
	Generate a graph of accessible space from a given start point. More...
struct	GraphParams
	Holds parameters for the GraphGenerator. More...
struct	optional_real3
	A simple wrapper for real3 that is able to determine whether or not it's defined. More...
struct	Precision
	Various parameters to set the precision of certain parts of the graph generator. More...
class	UniqueQueue
	A queue that remembers every object inserted, and prevents the addition of nodes that have already been inserted even if they've been popped. More...

Typedefs
using	real_t = double
	Internal decimal type of the graph generator. More...
using	real3 = std::array< real_t, 3 >
	Type used for the standard coordinate set of the graph generator. More...
using	graph_edge = HF::SpatialStructures::Edge
	Type of edge for the graph generator to use internally. More...
using	RayTracer = HF::RayTracer::MultiRT
	Type of raytracer to be used internally. More...
using	pair = std::pair< int, int >
	Type for Directions to be stored as. More...
using	hashmap = std::unordered_map< int, HIT_FLAG >
	Hashmap used for assigning and storing hitflags for IDs. More...

Enumerations
enum	HIT_FLAG { NO_FLAG = 0 , FLOORS = 1 , OBSTACLES = 2 , BOTH = 3 }
	Determines which geometry the ray will collide with. More...
enum class	GeometryFilterMode { ALL_INTERSECTIONS = 0 , OBSTACLES_ONLY = 1 , OBSTACLES_AND_FLOORS }
	Different rules for how geometry is filtered by the graph generator. More...

Functions
void	SetupCoreCount (int cores=-1)
	Sets the core count of OpenMP. More...
template<typename raytracer_type >
void	setupRT (GraphGenerator *gg, raytracer_type &rt, const std::vector< int > &obs_ids, const std::vector< int > &walk_ids)
	Converts the raytracer to a multiRT if required, then map geometry ids to hitflags. More...
template<typename real_type >
real_t	CastToReal (real_type t)
	Cast an input value to real_t using static cast. More...
template<typename real_3_type >
real3	CastToReal3 (real_3_type t)
	Cast an array of 3 values to the graph_generator's real_3 type. More...
std::set< std::pair< int, int > >	permutations (int limit)
	Calculate P(n,r) as an array with each unique permutaton of 2 values being a pair. More...
optional_real3	ValidateStartPoint (RayTracer &RT, const real3 &start_point, const GraphParams &Params)
	Determine if the start point of the graph is over valid ground. More...
optional_real3	CheckRay (RayTracer &RT, const real3 &origin, const real3 &direction, real_t node_z_tolerance, HIT_FLAG flag=BOTH, const GeometryFlagMap &geometry_dict=GeometryFlagMap())
	Cast a ray and get the point of intersection if it connects. More...
std::vector< pair >	CreateDirecs (int max_step_connections)
	Create a set of directions based on max_step_connections. More...
std::vector< graph_edge >	GetChildren (const real3 &parent, const std::vector< real3 > &possible_children, RayTracer &rt, const GraphParams &GP)
	Calculate all possible edges between parent and possible_children. More...
std::vector< real3 >	GeneratePotentialChildren (const real3 &parent, const std::vector< pair > &direcs, const real3 &spacing, const GraphParams &gp)
	Populare out_children with a potential child position for every direction in directions. More...
template<typename A , typename D , typename N >
void	MoveNode (const A &dist, const D &direction, N &node)
	Move a node in direction by dist units. More...
std::vector< real3 >	CheckChildren (const real3 &parent, const std::vector< real3 > &possible_children, RayTracer &rt, const GraphParams &params)
	Determine whether children are over valid ground, and and meet upstep/downstep requirements. More...
HF::SpatialStructures::STEP	CheckConnection (const real3 &parent, const real3 &child, RayTracer &rt, const GraphParams &params)
	Determine what kind of step (if any) is between parent and child. More...
bool	OcclusionCheck (const real3 &parent, const real3 &child, RayTracer &RT)
	Determine if there is a valid line of sight between parent and child. More...
bool	CheckSlope (const real3 &parent, const real3 &child, const GraphParams &gp)
	Determine if the slope between parent and child is traversable according to the graph parameters. More...
template<typename point_type >
Node	ToNode (const point_type &ct)
	Convert a point_type to a node. More...
template<typename n1_type , typename n2_type >
real_t	DistanceTo (const n1_type &n1, const n2_type &n2)
	Calculate the distance between two nodes. More...
template<typename vector_type >
void	Normalize (vector_type &v)
	Normalize a vector. More...
template<typename vector_type >
vector_type	DirectionTo (const vector_type &n1, const vector_type &n2)
	Calculate the normalized direction from one node to another. More...
bool	CheckGeometryID (HIT_FLAG goal, int id, const GeometryFlagMap &geom_dict)
	Determine if a hit is against the geometry type specified. More...

Variables
constexpr real_t	default_z_precision = 0.0001
constexpr real_t	default_ground_offset = 0.01
constexpr real_t	default_spacing_precision = 0.00001
static const real3	down = { 0,0,-1 }
	Constant used as a direction for downwards raycasts. More...
static const vector< pair >	init_directs

Detailed Description

Generate a graph of accessible space from a given start point.

The Graph Generator maps out "accessible" space on a model from a given starting point. In graphs created by this algorithm, node represents a point in space that a human can occupy, and each edge between nodes indicates that a human can traverse from one node to another node. The Graph Generator is a powerful tool for analyzing space, since the graph or nodes it outputs can be used as input to all the analysis methods offered by DHARTAPI, allowing for it to be the starting point of other analysis methods within DHARTAPI.

Obstacle Support

The Graph Generator supports marking specific geometry as walkable or obstacles. Obstacle surfaces are surfaces that the graph generator is not allowed to generate nodes on, while walkable surfaces are the only surfaces that the graph generator is permitted to generate nodes on. Depending on what arguments are first passed to the graph generator, it will use different rules for determining which of the inputs are obstacles and which are not. When no geometry ids are specified, all geometry is considered walkable. When only obstacle surfaces are specified, all geometry other than that in the obstacles array are considered walkable. If both an obstacle and walkable array are specified then obstacles will be considered inaccessible, walkable surfaces will be accessible, and all geometry not in either array will be considered not traversable.

Note

All arguments are in meters for distances and degrees for angles unless otherwise specified. For all calculations, the Graph Generator assumes geometry is Z-Up i.e. upstep is how high the step is in the z-direction, ground checks are performed in the -z direction etc.

See also

GraphGenerator for more details.

---

Class Documentation

HF::GraphGenerator::GraphParams

struct HF::GraphGenerator::GraphParams

Holds parameters for the GraphGenerator.

Definition at line 255 of file graph_generator.h.

Collaboration diagram for HF::GraphGenerator::GraphParams:

Class Members
real_t	down_slope	The maximum downward slope the graph can traverse. Any slopes steeper than this will be considered inaccessible.
real_t	down_step	Maximum step down the graph can traverse.Any steps steeper than this will be considered inaccessible.
GeometryFlagMap	geom_ids	Stores a map of geometry IDs to their HIT_FLAGS and the current filter mode of the graph.
Precision	precision	Tolerances for the graph.
real_t	up_slope	Maximum upward slope the graph can traverse in degrees.Any slopes steeper than this will be considered inaccessible.
real_t	up_step	Maximum height of a step the graph can traverse.Any steps higher this will be considered inaccessible.

HF::GraphGenerator::Precision

struct HF::GraphGenerator::Precision

Various parameters to set the precision of certain parts of the graph generator.

Definition at line 111 of file graph_generator.h.

Collaboration diagram for HF::GraphGenerator::Precision:

Class Members
real_t	ground_offset	Distance to offset nodes from the ground before checking line of sight.
real_t	node_spacing	Precision to round nodes after spacing is calculated.
real_t	node_z	Precision to round the z-component of nodes after a raycast is performed.

Typedef Documentation

graph_edge

using HF::GraphGenerator::graph_edge = typedef HF::SpatialStructures::Edge

Type of edge for the graph generator to use internally.

Definition at line 75 of file graph_generator.h.

hashmap

using HF::GraphGenerator::hashmap = typedef std::unordered_map<int, HIT_FLAG>

Hashmap used for assigning and storing hitflags for IDs.

Definition at line 134 of file graph_generator.h.

pair

using HF::GraphGenerator::pair = typedef std::pair<int, int>

Type for Directions to be stored as.

Definition at line 82 of file graph_generator.h.

RayTracer

using HF::GraphGenerator::RayTracer = typedef HF::RayTracer::MultiRT

Type of raytracer to be used internally.

Definition at line 81 of file graph_generator.h.

real3

using HF::GraphGenerator::real3 = typedef std::array<real_t, 3>

Type used for the standard coordinate set of the graph generator.

Definition at line 74 of file graph_generator.h.

real_t

using HF::GraphGenerator::real_t = typedef double

Internal decimal type of the graph generator.

Definition at line 73 of file graph_generator.h.

Enumeration Type Documentation

GeometryFilterMode

enum class HF::GraphGenerator::GeometryFilterMode

strong

Different rules for how geometry is filtered by the graph generator.

Remarks

Each different filter mode was created to allow for different uses of the graph generator depending on how much geometry was specifically specified to be in either group. This allows for users to accept all geometry, Blacklist some geometry, or Blacklist and whitelist some geometry from graph generation.

Enumerator
ALL_INTERSECTIONS	Consider all geometry as walkable surfaces.
OBSTACLES_ONLY	Consider all geometry that isn't an obstacle as walkable.
OBSTACLES_AND_FLOORS	Explicitly tag geometry ids as either obstacle or floor. Any ids outside of these ranges will always fail.

Definition at line 144 of file graph_generator.h.

HIT_FLAG

enum HF::GraphGenerator::HIT_FLAG

Determines which geometry the ray will collide with.

Remarks

Used internally by the GraphGenerator to determine which type of geometry to collide with when casting a ray.

Enumerator
NO_FLAG	No flag set.
FLOORS	Floors only.
OBSTACLES	Obstacles only.
BOTH	Collide with floors and obstacles.

Definition at line 123 of file graph_generator.h.

Function Documentation

CastToReal()

template<typename real_type >

real_t HF::GraphGenerator::CastToReal ( real_type  t )

inline

Cast an input value to real_t using static cast.

Remarks

Just a convience function. Same as static_cast<real_t>(t)

Returns

static_cast<real_t>(t)

Definition at line 91 of file graph_generator.h.

Referenced by HF::GraphGenerator::GraphGenerator::BuildNetwork(), and CastToReal3().

Here is the caller graph for this function:

CastToReal3()

template<typename real_3_type >

real3 HF::GraphGenerator::CastToReal3 ( real_3_type  t )

inline

Cast an array of 3 values to the graph_generator's real_3 type.

Template Parameters

real_3_type

A vector type that is indexable with square brackets for up to 3 elements (pointlike concept)

Parameters

t	X,Y,Z coordinates to convert to a real3

Returns

A real3 containing the x,y,z coordinates of t

Definition at line 104 of file graph_generator.h.

References CastToReal().

Referenced by HF::GraphGenerator::GraphGenerator::BuildNetwork(), HF::GraphGenerator::GraphGenerator::CrawlGeom(), and HF::GraphGenerator::GraphGenerator::CrawlGeomParallel().

Here is the call graph for this function:

Here is the caller graph for this function:

CheckChildren()

std::vector< real3 > HF::GraphGenerator::CheckChildren	(	const real3 &	parent,
		const std::vector< real3 > &	possible_children,
		RayTracer &	rt,
		const GraphParams &	params
	)

Determine whether children are over valid ground, and and meet upstep/downstep requirements.

Parameters

parent	Parent of all children in possible_children
possible_children	Children of parent that may or may not be over valid ground
rt	Raytracer to use for all ray intersections
params	Parameters to use for upstep/downstep limits and rounding

Returns

An array of children from possible_children that are over valid ground and meet the upstep/downstep requirements in params. Any child that didn't meet these requirements will not have been included. Each child in the return will have been moved to be directly over the valid ground they're above.

Example

    
    // Load an OBJ containing a simple plane
    auto mesh = HF::Geometry::LoadMeshObjects("plane.obj", HF::Geometry::ONLY_FILE, true);
    
    // Create a raytracer using this obj
    EmbreeRayTracer ray_tracer = HF::RayTracer::EmbreeRayTracer(mesh);
    

 
    // Create a parent node
    HF::GraphGenerator::real3 parent{ 0,0,1 };
 
    // Create a vector of possible children
    std::vector<HF::GraphGenerator::real3> possible_children{
        HF::GraphGenerator::real3{0,2,1}, HF::GraphGenerator::real3{1,0,1},
        HF::GraphGenerator::real3{0,1,1}, HF::GraphGenerator::real3{2,0,1}
    };
 
    // Create graph parameters
    HF::GraphGenerator::GraphParams params;
    params.up_step = 2; params.down_step = 2;
    params.up_slope = 45; params.down_slope = 45;
    params.precision.node_z = 0.01f;
    params.precision.ground_offset = 0.01f;
 
    // Call CheckChildren 
    auto valid_children = HF::GraphGenerator::CheckChildren(parent, possible_children, HF::RayTracer::MultiRT(&ray_tracer), params);
 
    // Print children
    std::ostringstream out_str;
    out_str << "[";
    for (int i = 0; i < valid_children.size(); i++)
        out_str << "(" << valid_children[i][0] << ", " << valid_children[i][1] << ", " << valid_children[i][2] << ")" << ((i != valid_children.size() - 1) ? "," : "]");
 
    std::cout << out_str.str() << std::endl;
 

[(0, 2, 0),(1, 0, -0),(0, 1, 0),(2, 0, -0)]

Definition at line 248 of file graph_utils.cpp.

References CheckRay(), down, HF::GraphGenerator::GraphParams::down_step, FLOORS, HF::GraphGenerator::GraphParams::geom_ids, HF::GraphGenerator::Precision::node_z, HF::GraphGenerator::GraphParams::precision, HF::GraphGenerator::optional_real3::pt, and HF::GraphGenerator::GraphParams::up_step.

Referenced by GetChildren().

Here is the call graph for this function:

Here is the caller graph for this function:

CheckConnection()

HF::SpatialStructures::STEP HF::GraphGenerator::CheckConnection	(	const real3 &	parent,
		const real3 &	child,
		RayTracer &	rt,
		const GraphParams &	params
	)

Determine what kind of step (if any) is between parent and child.

Parameters

parent	Node being traversed from
child	Node being traversed to
rt	Raytracer to use for all ray intersections
params	Parameters to use for upstep/downstep and upslope/downslope

Returns

The type of step between parent/child or NO_CONNECTION if no connection could be found between them.

Example

    
    // Load an OBJ containing a simple plane
    auto mesh = HF::Geometry::LoadMeshObjects("plane.obj", HF::Geometry::ONLY_FILE, true);
    
    // Create a raytracer using this obj
    EmbreeRayTracer ray_tracer = HF::RayTracer::EmbreeRayTracer(mesh);
    

 
    // Create a parent node
    HF::GraphGenerator::real3 parent{ 0,0,1 };
 
    // Create a vector of possible children
    std::vector<HF::GraphGenerator::real3> possible_children{
        HF::GraphGenerator::real3{0,2,0}, HF::GraphGenerator::real3{1,0,0},
        HF::GraphGenerator::real3{0,1,0}, HF::GraphGenerator::real3{2,0,0}
    };
 
    // Create graph parameters
    HF::GraphGenerator::GraphParams params;
    params.up_step = 2; params.down_step = 2;
    params.up_slope = 45; params.down_slope = 45;
    params.precision.node_z = 0.01f;
    params.precision.ground_offset = 0.01f;
 
    // Loop through potential children call each one with check connection
    std::vector<HF::SpatialStructures::STEP> connections;
    for (const auto& child : possible_children)
        connections.push_back(HF::GraphGenerator::CheckConnection(parent, child, HF::RayTracer::MultiRT(&ray_tracer), params));
        
 
    // Print children
    std::ostringstream out_str;
    out_str << "[";
    for (int i = 0; i < connections.size(); i++)
        out_str << connections[i] << ((i != connections.size() - 1) ? "," : "]");
 
    // In the output, 0s indicate no connection, while 1s indicate that nodes are on a flat plane
    // with no step between them. 
    std::cout << out_str.str() << std::endl;
 

[1,0,0,1]

Definition at line 303 of file graph_utils.cpp.

References CheckSlope(), HF::GraphGenerator::GraphParams::down_step, HF::GraphGenerator::Precision::ground_offset, OcclusionCheck(), HF::GraphGenerator::GraphParams::precision, and HF::GraphGenerator::GraphParams::up_step.

Referenced by GetChildren().

Here is the call graph for this function:

Here is the caller graph for this function:

CheckGeometryID()

bool HF::GraphGenerator::CheckGeometryID ( HIT_FLAG  goal, int  id, const GeometryFlagMap &  geom_dict  )

inline

Determine if a hit is against the geometry type specified.

Parameters

goal	Hitflag that the intersection is being cheecked against
ID	id of the mesh that was intesected
geom_dict	Rules to use for determining if the intersection was successful

Returns

True if the intersection abides by the rules in geom_dict, false otherwise

Remarks

This function serves as the sole place for intersection mesh ids to be checked using the ifnormation in geom_dict.

Definition at line 126 of file graph_utils.cpp.

References ALL_INTERSECTIONS, BOTH, HF::GraphGenerator::GeometryFlagMap::Mode, OBSTACLES, OBSTACLES_AND_FLOORS, and OBSTACLES_ONLY.

Referenced by CheckRay().

Here is the caller graph for this function:

CheckRay()

optional_real3 HF::GraphGenerator::CheckRay	(	RayTracer &	RT,
		const real3 &	origin,
		const real3 &	direction,
		real_t	node_z_tolerance,
		HIT_FLAG	flag = BOTH,
		const GeometryFlagMap &	geometry_dict = GeometryFlagMap()
	)

Cast a ray and get the point of intersection if it connects.

Parameters

RT	Raytracer to use for intersection.
origin	Origin point of the ray.
direction	direction to cast the ray in.
node_z_tolerance	Precision to round the point of intersection's z-component to
flag	Which category of geometry will be intersected with. In general, any intersections with geometry other than this type will be discarded unless the type is BOTH, NONE, or the geometry dictionary is empty.
geometry_dict	Dictionary containing rules for filtering ray intersections. If not specified, this will not filter any intersections.

Returns

An invalid optional_real3 if the ray did not intersect any geometry, or a valid optional_real3 containing the point of intesection if an intersection was found.

Example

    
    // Load an OBJ containing a simple plane
    auto mesh = HF::Geometry::LoadMeshObjects("plane.obj", HF::Geometry::ONLY_FILE, true);
    
    // Create a raytracer using this obj
    EmbreeRayTracer ray_tracer = HF::RayTracer::EmbreeRayTracer(mesh);
    

 
    // Define z tolerance
    HF::GraphGenerator::real_t node_z = 0.01;
 
    // Create a start  point 10 units above the mesh, and
    // a direction vector facing straight down.
    HF::GraphGenerator::real3 start_point{ 1,1,1 };
    HF::GraphGenerator::real3 direction{0,0,-1};
 
    // Call CheckRay and capture the result
    HF::GraphGenerator::optional_real3 result = HF::GraphGenerator::CheckRay(
        HF::RayTracer::MultiRT(&ray_tracer), start_point, direction, node_z);
 
    // If the ray intersected, print it
    if (result)
    {
        auto result_point = *result;
        printf("(%0.000f, %0.000f, %0.000f)\n", result_point[0], result_point[1], result_point[2]);
    }
 
    // If it didn't print a message
    else
        printf("No intersection found\n");
 

(1, 1, 0)

Definition at line 146 of file graph_utils.cpp.

References CheckGeometryID(), HF::RayTracer::HitStruct< numeric_type >::DidHit(), HF::RayTracer::HitStruct< numeric_type >::distance, HF::RayTracer::MultiRT::Intersect(), HF::RayTracer::HitStruct< numeric_type >::meshid, MoveNode(), and HF::GraphGenerator::optional_real3::pt.

Referenced by CheckChildren(), and ValidateStartPoint().

Here is the call graph for this function:

Here is the caller graph for this function:

CheckSlope()

bool HF::GraphGenerator::CheckSlope	(	const real3 &	parent,
		const real3 &	child,
		const GraphParams &	gp
	)

Determine if the slope between parent and child is traversable according to the graph parameters.

Parameters

parent	Node being traversed from
child	Node being traversed to
GP	Parameters to use for up_slope/down_slope

Returns

true if the slope from parent to child meets upstep/downstep requirements in graph_params. false otherwise.

Example

    
    // Setup graph parameters so the slope limits are 30 degrees in both directions.
    HF::GraphGenerator::GraphParams gp;
    gp.up_slope = 30; gp.down_slope = 30;
 
    // Create a parent, a child that's traversble, and a child that's too steep
    // to pass the slope check
    HF::GraphGenerator::real3 parent { 0,0,0 };
    HF::GraphGenerator::real3 child_1 { 0,1,0.5 };
    HF::GraphGenerator::real3 child_2 { 0,1,1};
 
    // Perform slope checks
    bool slope_check_child_1 = HF::GraphGenerator::CheckSlope(parent, child_1, gp);
    bool slope_check_child_2 = HF::GraphGenerator::CheckSlope(parent, child_2, gp);
    
    std::cout << "Slope Check For Child 1 = " << (slope_check_child_1 ? "True" : "False") << std::endl;
    std::cout << "Slope Check For Child 2 = " << (slope_check_child_2 ? "True" : "False") << std::endl;
 

Slope Check For Child 1 = True
Slope Check For Child 2 = False

Definition at line 290 of file graph_utils.cpp.

References HF::GraphGenerator::GraphParams::down_slope, and HF::GraphGenerator::GraphParams::up_slope.

Referenced by CheckConnection().

Here is the caller graph for this function:

CreateDirecs()

vector< pair > HF::GraphGenerator::CreateDirecs

(

int

max_step_connections

)

Create a set of directions based on max_step_connections.

Parameters

max_step_conenctions

Multiplier for directions to generate.

Returns

A set of all directions generated for max_step_connections.

See also

permutations for more information on how max_step_connections influences generated directions

Example

 
    // Call create direcs with a max_step_conections of 2
    auto directions = HF::GraphGenerator::CreateDirecs(2);
 
    // Construct Output String
    std::ostringstream out_str;
 
    out_str << "[";
    for (int i = 0; i < directions.size(); i++)
        out_str << "(" << directions[i].first << ", " << directions[i].second << ")" << ((i != directions.size() - 1) ? "," : "]");
 
    // Print to console.
    std::cout << out_str.str() << std::endl;
    

[(-1, -1),(-1, 0),(-1, 1),(0, -1),(0, 1),(1, -1),(1, 0),(1, 1),(-2, -1),(-2, 1),(-1, -2),(-1, 2),(1, -2),(1, 2),(2, -1),(2, 1)]

Definition at line 201 of file graph_utils.cpp.

References init_directs, and permutations().

Referenced by HF::GraphGenerator::GraphGenerator::CrawlGeom(), and HF::GraphGenerator::GraphGenerator::CrawlGeomParallel().

Here is the call graph for this function:

Here is the caller graph for this function:

DirectionTo()

template<typename vector_type >

vector_type HF::GraphGenerator::DirectionTo ( const vector_type &  n1, const vector_type &  n2  )

inline

Calculate the normalized direction from one node to another.

Template Parameters

vector_type

The type of vectors used to hold the coordinates of n1 and `n2. Each element should be indexable with square brackets up to 3 values.

Parameters

n1	Node to calcualte direction from
n2	Node to calculate direction to

Returns

A vector_type containing the normalized direction n1 to n2. Directions that are used always used by the graph generator.

Definition at line 88 of file graph_utils.cpp.

References Normalize().

Referenced by OcclusionCheck().

Here is the call graph for this function:

Here is the caller graph for this function:

DistanceTo()

template<typename n1_type , typename n2_type >

real_t HF::GraphGenerator::DistanceTo ( const n1_type &  n1, const n2_type &  n2  )

inline

Calculate the distance between two nodes.

Template Parameters

n1_type	A vector type that is indexable with square brackets for up to 3 elements (pointlike concept)
n2_type	n1_type A vector type that is indexable with square brackets for up to 3 elements (pointlike concept)

Parameters

n1	Location to calculate distance from
n2	Location to calculate distance to

Returns

The distance from n1 to n2.

Definition at line 54 of file graph_utils.cpp.

Referenced by GetChildren(), and OcclusionCheck().

Here is the caller graph for this function:

GeneratePotentialChildren()

std::vector< real3 > HF::GraphGenerator::GeneratePotentialChildren	(	const real3 &	parent,
		const std::vector< pair > &	direcs,
		const real3 &	spacing,
		const GraphParams &	gp
	)

Populare out_children with a potential child position for every direction in directions.

Parameters

parent	Parent to generate children from.
directions	X,Y pairs to use for generating children. I.E. A pair of {1,2}would create a child at {parent.x + 1*spacing.x, parent.y + 2*spacing.y, parent.z + spacing.z}.
spacing	Magnitude to offset children in the x,y,z direction for each direction in directions
gp	Parameters to use for rounding offset nodes.

Returns

An array of children offset from parent by spacing and directions.

Example

Example

 
    // Create a parent node and set the spacing for these offsets
    HF::GraphGenerator::real3 parent = { 0,0,1 };
    HF::GraphGenerator::real3 spacing = { 1,2,3 };
 
    // Create a vector of directions to offset it
    std::vector<HF::GraphGenerator::pair> directions = { {0,1}, {0,2}, {1,0}, {2,0}, {1,1}, {2,1} };
 
    // Construct a GraphParams with the spacing filled out
    HF::GraphGenerator::GraphParams gp;
    gp.precision.node_spacing = 0.001f;
    gp.precision.node_z = 0.001f;
 
    // Call CreateDirecs
    auto children = HF::GraphGenerator::GeneratePotentialChildren(parent, directions, spacing, gp);
 
    // Create Output
    std::ostringstream out_str;
    
    out_str << "[";
    for (int i = 0; i < directions.size(); i++)
        out_str << "(" << children[i][0] << ", " << children[i][1] << ", " 
        << children[i][2] << ")" << ((i != directions.size() - 1) ? "," : "]");
 
    // Print to console
    std::cout << out_str.str() << std::endl;
 

[(0, 2, 4),(0, 4, 4),(1, 0, 4),(2, 0, 4),(1, 2, 4),(2, 2, 4)]

Definition at line 381 of file graph_utils.cpp.

References HF::GraphGenerator::Precision::node_spacing, HF::GraphGenerator::Precision::node_z, and HF::GraphGenerator::GraphParams::precision.

Referenced by HF::GraphGenerator::GraphGenerator::CrawlGeom(), and HF::GraphGenerator::GraphGenerator::CrawlGeomParallel().

Here is the caller graph for this function:

GetChildren()

vector< graph_edge > HF::GraphGenerator::GetChildren	(	const real3 &	parent,
		const std::vector< real3 > &	possible_children,
		RayTracer &	rt,
		const GraphParams &	GP
	)

Calculate all possible edges between parent and possible_children.

Parameters

parent	Parent of all children in possible_children
possible_children	Children that may have an edge with Parent
rt	Raytracer to use for ray intersections
GP	parameters to use for rounding and discarding nodes

Rules

An edge is considered valid if: 1) Both parent and child the potential child are over valid walkable ground 2) After the child is moved to be directly on top of the ground it is over The slope between parent and child is within upslope/downslope limits OR the path between parent/child involves a step that is within upstep/downstep limits

Returns

An array of all edges that could be created between parent and possible_children that meet the requirements of GraphParameter. For every edge, the child will be moved downwards to ensure it's over valid ground.

Example

    
    // Load an OBJ containing a simple plane
    auto mesh = HF::Geometry::LoadMeshObjects("plane.obj", HF::Geometry::ONLY_FILE, true);
    
    // Create a raytracer using this obj
    EmbreeRayTracer ray_tracer = HF::RayTracer::EmbreeRayTracer(mesh);
    

 
    // Create a parent node
    HF::GraphGenerator::real3 parent{ 0,0,1 };
    
    // Create a vector of possible children
    std::vector<HF::GraphGenerator::real3> possible_children{
        HF::GraphGenerator::real3{0,2,1}, HF::GraphGenerator::real3{1,0,1},
        HF::GraphGenerator::real3{0,1,1}, HF::GraphGenerator::real3{2,0,1}
    };
    
    // Create graph parameters
    HF::GraphGenerator::GraphParams params;
    params.up_step = 2; params.down_step = 2;
    params.up_slope = 45; params.down_slope = 45;
    params.precision.node_z = 0.01f;
    params.precision.ground_offset = 0.01f;
 
    // Call GetChildren
    auto edges = HF::GraphGenerator::GetChildren(parent, possible_children, HF::RayTracer::MultiRT(&ray_tracer), params);
 
    // Print children
    std::ostringstream out_str;
    out_str << "[";
    for (int i = 0; i < edges.size(); i++)
        out_str << "(" << edges[i].child << ", " << edges[i].score << ", " << edges[i].step_type << ")" << ((i != edges.size() - 1) ? "," : "]");
    
    std::cout << out_str.str() << std::endl;
        

[((0, 2, 0), 2.23607, 1),((2, 0, -0), 2.23607, 1)]

Definition at line 218 of file graph_utils.cpp.

References CheckChildren(), CheckConnection(), DistanceTo(), and ToNode().

Referenced by HF::GraphGenerator::GraphGenerator::CrawlGeom(), and HF::GraphGenerator::GraphGenerator::CrawlGeomParallel().

Here is the call graph for this function:

Here is the caller graph for this function:

MoveNode()

template<typename A , typename D , typename N >

void HF::GraphGenerator::MoveNode ( const A &  dist, const D &  direction, N &  node  )

inline

Move a node in direction by dist units.

Template Parameters

D	Must have [0], [1], [2] defined.
N	Must have [0], [1], [2] defined.

Parameters

dist	Distance to move the node.
direction	Direction to move the node in.
node	Node to move

Postcondition

Node's members at [0], [1], [2] been moved in direction by dist units.

Definition at line 731 of file graph_generator.h.

Referenced by CheckRay().

Here is the caller graph for this function:

Normalize()

template<typename vector_type >

void HF::GraphGenerator::Normalize ( vector_type &  v )

inline

Normalize a vector.

Template Parameters

vector_type

Must be indexable with square brackets for up to 3 elements. (pointlike concept)

Parameters

v	The vector to normalize

Postcondition

v will be normalized to have a magnitude of 1.

Definition at line 68 of file graph_utils.cpp.

Referenced by DirectionTo().

Here is the caller graph for this function:

OcclusionCheck()

bool HF::GraphGenerator::OcclusionCheck	(	const real3 &	parent,
		const real3 &	child,
		RayTracer &	RT
	)

Determine if there is a valid line of sight between parent and child.

Parameters

parent	Node to perform the line of sight check from
child	Node to perform the line of sight check to
RT	raytracer to use for the line of sight check

Returns

True The line of sight between parent and child is obstructed

False There is a clear line of sight between parent and child

Example

    
    // Load an OBJ containing a simple plane
    auto mesh = HF::Geometry::LoadMeshObjects("plane.obj", HF::Geometry::ONLY_FILE, true);
    
    // Create a raytracer using this obj
    EmbreeRayTracer ray_tracer = HF::RayTracer::EmbreeRayTracer(mesh);
    

 
    // Create a parent node, a child that has a clear line of sight, then
    // a child that is underneath the plane
    HF::GraphGenerator::real3 parent{ 0,0,1 };
    HF::GraphGenerator::real3 child_1{ 0,0,-3 };
    HF::GraphGenerator::real3 child_2{ 0,0,1 };
 
    // Perform slope checks
    bool occlusion_check_child_1 = HF::GraphGenerator::OcclusionCheck(parent, child_1, HF::RayTracer::MultiRT(&ray_tracer));
    bool occlusion_check_child_2= HF::GraphGenerator::OcclusionCheck(parent, child_2, HF::RayTracer::MultiRT(&ray_tracer));
 
    std::cout << "Occlusion Check For Child 1 = " << (occlusion_check_child_1 ? "True" : "False") << std::endl;
    std::cout << "Occlusion Check For Child 2 = " << (occlusion_check_child_2 ? "True" : "False") << std::endl;
    

Occlusion Check For Child 1 = True
Occlusion Check For Child 2 = False

Definition at line 283 of file graph_utils.cpp.

References DirectionTo(), DistanceTo(), and HF::RayTracer::MultiRT::Occluded().

Referenced by CheckConnection().

Here is the call graph for this function:

Here is the caller graph for this function:

permutations()

std::set< std::pair< int, int > > HF::GraphGenerator::permutations

(

int

limit

)

Calculate P(n,r) as an array with each unique permutaton of 2 values being a pair.

Parameters

limit

Highest number in the set

Returns

a list of all permutations for integers from 0 to limit

Definition at line 180 of file graph_utils.cpp.

Referenced by CreateDirecs().

Here is the caller graph for this function:

SetupCoreCount()

void HF::GraphGenerator::SetupCoreCount ( int  cores = -1 )

inline

Sets the core count of OpenMP.

Parameters

cores

Number of cores to use. If -1, use every as many cores as possible

Definition at line 35 of file graph_generator.cpp.

Referenced by HF::GraphGenerator::GraphGenerator::IMPL_BuildNetwork().

Here is the caller graph for this function:

setupRT()

template<typename raytracer_type >

void HF::GraphGenerator::setupRT ( GraphGenerator *  gg, raytracer_type &  rt, const std::vector< int > &  obs_ids, const std::vector< int > &  walk_ids  )

inline

Converts the raytracer to a multiRT if required, then map geometry ids to hitflags.

Parameters

gg	Pointer to the graph generator to update
obs_ids	array of geometry ids to set as obstacles
walk_ids	Array of geometry ids to set as walkable

Postcondition

gg will have it's geometry map populated with the passed geometry ids and it's raytracer set to a MultiRT containing gg

Definition at line 50 of file graph_generator.cpp.

References HF::GraphGenerator::GraphParams::geom_ids, HF::GraphGenerator::GraphGenerator::params, HF::GraphGenerator::GraphGenerator::ray_tracer, and HF::GraphGenerator::GeometryFlagMap::SetGeometryIds().

Here is the call graph for this function:

ToNode()

template<typename point_type >

Node HF::GraphGenerator::ToNode ( const point_type &  ct )

inline

Convert a point_type to a node.

Template Parameters

point_type

An array-like type that meets the pointlike concept

Parameters

ct	x,y,z coordinates to create the new node with.

Returns

A node containing the x,y,z components of ct

Definition at line 36 of file graph_utils.cpp.

Referenced by GetChildren().

Here is the caller graph for this function:

ValidateStartPoint()

optional_real3 HF::GraphGenerator::ValidateStartPoint	(	RayTracer &	RT,
		const real3 &	start_point,
		const GraphParams &	Params
	)

Determine if the start point of the graph is over valid ground.

Parameters

RT	Raytracer to use for ray intersection
start_point	the x,y,z coordinates of the starting point
Params	parameters to use for precision.

Returns

An invalid optional_real3 if the check failed, or a valid optional_real3 containing the x,y,z coordinates of the start point moved to be directly ontop of the intersected ground if the check succeeded.

Example

    
    // Load an OBJ containing a simple plane
    auto mesh = HF::Geometry::LoadMeshObjects("plane.obj", HF::Geometry::ONLY_FILE, true);
    
    // Create a raytracer using this obj
    EmbreeRayTracer ray_tracer = HF::RayTracer::EmbreeRayTracer(mesh);
    

 
    // Define tolerances
    HF::GraphGenerator::Precision precision;
    precision.node_z = 0.01f;
    precision.node_spacing = 0.001f;
    precision.ground_offset = 0.001f;
 
    // Create graphParameters to hold tolerances
    HF::GraphGenerator::GraphParams params;
    params.precision = precision;
 
    // Setup start_point
    HF::GraphGenerator::real3 start_point{ 0,0,10 };
 
    // Call ValidateStartPoint
    HF::GraphGenerator::optional_real3 result = HF::GraphGenerator::ValidateStartPoint(
        HF::RayTracer::MultiRT(&ray_tracer), start_point, params
    );
 
    // If the ray intersected, print the result
    if (result)
    {
        auto result_point = *result;
        printf("(%0.000f, %0.000f, %0.000f)\n", result_point[0], result_point[1], result_point[2]);
    }
 
    // If it didn't print a message
    else
        printf("No intersection found\n");
 

(0, 0, 0)

Definition at line 107 of file graph_utils.cpp.

References CheckRay(), down, FLOORS, HF::GraphGenerator::GraphParams::geom_ids, HF::GraphGenerator::Precision::node_z, and HF::GraphGenerator::GraphParams::precision.

Referenced by HF::GraphGenerator::GraphGenerator::IMPL_BuildNetwork().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

default_ground_offset

constexpr real_t HF::GraphGenerator::default_ground_offset = 0.01

constexpr

Definition at line 78 of file graph_generator.h.

default_spacing_precision

constexpr real_t HF::GraphGenerator::default_spacing_precision = 0.00001

constexpr

Definition at line 79 of file graph_generator.h.

default_z_precision

constexpr real_t HF::GraphGenerator::default_z_precision = 0.0001

constexpr

Definition at line 77 of file graph_generator.h.

down

const real3 HF::GraphGenerator::down = { 0,0,-1 }

static

Constant used as a direction for downwards raycasts.

Definition at line 13 of file graph_utils.cpp.

Referenced by CheckChildren(), and ValidateStartPoint().

init_directs

const vector<pair> HF::GraphGenerator::init_directs

static

Initial value:

= {
        pair(-1, -1), pair(-1, 0), pair(-1, 1),
        pair(0, -1), pair(0, 1), pair(1, -1),
        pair(1, 0), pair(1, 1)
    }

Definition at line 101 of file graph_utils.cpp.

Referenced by CreateDirecs().