HF::GraphGenerator::GraphGenerator Class Reference

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

#include <graph_generator.h>

Collaboration diagram for HF::GraphGenerator::GraphGenerator:

Public Member Functions
	GraphGenerator (HF::RayTracer::EmbreeRayTracer &ray_tracer, const std::vector< int > &obstacle_ids=std::vector< int >(0), const std::vector< int > &walkable_ids=std::vector< int >(0))
	Construct a new graph generator with a specific raytracer. More...
	GraphGenerator (HF::RayTracer::NanoRTRayTracer &ray_tracer, const std::vector< int > &obstacle_ids=std::vector< int >(0), const std::vector< int > &walkable_ids=std::vector< int >(0))
	Construct a new graph generator with a specific raytracer. More...
	GraphGenerator (HF::RayTracer::MultiRT &ray_tracer, const std::vector< int > &obstacle_ids=std::vector< int >(0), const std::vector< int > &walkable_ids=std::vector< int >(0))
	Construct a new graph generator with a specific raytracer. More...
template<typename node_type , typename node2_type , typename up_step_type , typename up_slope_type , typename down_step_type , typename down_slope_type , typename z_precision_type = real_t, typename connect_offset_type = real_t, typename spacing_precision_type = real_t>
SpatialStructures::Graph	BuildNetwork (const node_type &start_point, const node2_type &Spacing, int MaxNodes, up_step_type UpStep, up_slope_type UpSlope, down_step_type DownStep, down_slope_type DownSlope, int max_step_connections, int min_connections=1, int cores=-1, z_precision_type node_z_precision=default_z_precision, connect_offset_type node_spacing_precision=default_spacing_precision, spacing_precision_type ground_offset=default_ground_offset)
	Generate a graph of accessible space. More...
SpatialStructures::Graph	IMPL_BuildNetwork (const real3 &start_point, const real3 &Spacing, int MaxNodes, real_t UpStep, real_t UpSlope, real_t DownStep, real_t DownSlope, int max_step_connections, int min_connections, int cores=-1, real_t node_z_precision=default_z_precision, real_t node_spacing_precision=default_spacing_precision, real_t ground_offset=default_ground_offset)
	Generate a graph of accessible space. More...
SpatialStructures::Graph	CrawlGeom (UniqueQueue &todo)
	Perform breadth first search to populate the graph with with nodes and edges. More...
SpatialStructures::Graph	CrawlGeomParallel (UniqueQueue &todo)
	Perform breadth first search to populate the graph with nodes and edges using multiple cores. More...

Public Attributes
int	max_nodes
	Maximum number of nodes to generate. If less than zero, generate nodes without a limit. More...
int	core_count
	Number of cores to use for graph generation. More...
int	min_connections
	Minimum number of step connections for a node to be valid (minimum out degree of node) More...
int	max_step_connection
	Multiplier for number of children to generate. The higher this is, the more directions there will be. More...
real3	spacing
	Spacing between nodes. New nodes will be generated with atleast this much distance between them. More...
GraphParams	params
	Parameters to run the graph generator. More...
RayTracer	ray_tracer
	A pointer to the raytracer to use for ray intersections. More...

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.

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.

Definition at line 344 of file graph_generator.h.

Constructor & Destructor Documentation

GraphGenerator() [1/3]

HF::GraphGenerator::GraphGenerator::GraphGenerator	(	HF::RayTracer::EmbreeRayTracer &	ray_tracer,
		const std::vector< int > &	obstacle_ids = std::vector<int>(0),
		const std::vector< int > &	walkable_ids = std::vector<int>(0)
	)

Construct a new graph generator with a specific raytracer.

Parameters

ray_tracer	Raytracer to use for performing ray intersctions
walkable_id	IDs of geometry to be considered as obstacles
obstacle_id	IDs of geometry to be considered as walkable surfaces

Stores a pointer to RT. This could be dangerous in the case that the raytracer is destroyed before the graph generator is called again. It's not likely to occur in our codebase since GraphGenerators are mostly disposed of before this has a chance to become a problem.

Definition at line 55 of file graph_generator.cpp.

GraphGenerator() [2/3]

HF::GraphGenerator::GraphGenerator::GraphGenerator	(	HF::RayTracer::NanoRTRayTracer &	ray_tracer,
		const std::vector< int > &	obstacle_ids = std::vector<int>(0),
		const std::vector< int > &	walkable_ids = std::vector<int>(0)
	)

Construct a new graph generator with a specific raytracer.

Parameters

ray_tracer	Raytracer to use for performing ray intersctions
walkable_id	IDs of geometry to be considered as obstacles
obstacle_id	IDs of geometry to be considered as walkable surfaces

Stores a pointer to RT. This could be dangerous in the case that the raytracer is destroyed before the graph generator is called again. It's not likely to occur in our codebase since GraphGenerators are mostly disposed of before this has a chance to become a problem.

Definition at line 59 of file graph_generator.cpp.

GraphGenerator() [3/3]

HF::GraphGenerator::GraphGenerator::GraphGenerator	(	HF::RayTracer::MultiRT &	ray_tracer,
		const std::vector< int > &	obstacle_ids = std::vector<int>(0),
		const std::vector< int > &	walkable_ids = std::vector<int>(0)
	)

Construct a new graph generator with a specific raytracer.

Parameters

ray_tracer	Raytracer to use for performing ray intersctions
walkable_id	IDs of geometry to be considered as obstacles
obstacle_id	IDs of geometry to be considered as walkable surfaces

Stores a pointer to RT. This could be dangerous in the case that the raytracer is destroyed before the graph generator is called again. It's not likely to occur in our codebase since GraphGenerators are mostly disposed of before this has a chance to become a problem.

Definition at line 63 of file graph_generator.cpp.

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

Here is the call graph for this function:

Member Function Documentation

BuildNetwork()

template<typename node_type , typename node2_type , typename up_step_type , typename up_slope_type , typename down_step_type , typename down_slope_type , typename z_precision_type = real_t, typename connect_offset_type = real_t, typename spacing_precision_type = real_t>

SpatialStructures::Graph HF::GraphGenerator::GraphGenerator::BuildNetwork ( const node_type &  start_point, const node2_type &  Spacing, int  MaxNodes, up_step_type  UpStep, up_slope_type  UpSlope, down_step_type  DownStep, down_slope_type  DownSlope, int  max_step_connections, int  min_connections = 1, int  cores = -1, z_precision_type  node_z_precision = default_z_precision, connect_offset_type  node_spacing_precision = default_spacing_precision, spacing_precision_type  ground_offset = default_ground_offset  )

inline

Generate a graph of accessible space.

Parameters

start_point	The starting point for the graph generator. If this isn't above solid ground, no nodes will be generated.
Spacing	Space between nodes. Lower values will yield more nodes for a higher resolution graph.
MaxNodes	The maximum amount of nodes to generate.
UpStep	Maximum height of a step the graph can traverse. Any steps higher this will be considered inaccessible.
UpSlope	Maximum upward slope the graph can traverse in degrees. Any slopes steeper than this will be considered inaccessible.
DownStep	Maximum step down the graph can traverse. Any steps steeper than this will be considered inaccessible.
DownSlope	The maximum downward slope the graph can traverse. Any slopes steeper than this will be considered inaccessible.
max_step_connections	Multiplier for number of children to generate for each node. Increasing this value will increase the number of edges in the graph, and as a result the amount of memory the algorithm requires.
min_connections	The required out-degree for a node to be valid and stored. This must be greater than 0 and equal or less than the total connections created from max_step_connections. Default is 1. A value of 8 when max_step_connections=1 would be a grid.
cores	Number of cores to use. -1 will use all available cores, and 0 will run a serialized version of the algorithm.
node_z_precision	Precision to round the z-component of nodes after a raycast is performed
node_spacing_precision	Precision to round nodes after spacing is calculated
ground_offset	Distance to offset nodes from the ground before checking line of sight

Returns

The resulting graph or an empty graph if the start check failed

Note

All parameters relating to distances are in meters, and all angles are in degrees.

Geometry MUST be Z-UP in order for this to work.

Remarks

This exists to provide a softer interface to the graph itself. Without this template, all callers would need to intuitively know the type of real_t or else their code wouldn't compile. The actual implementation of this function is in IMPL_BuildNetwork.

The extensive use of templating on this function is to allow any numeric type to be used for any one of the template arguments. For example node_1_type could be a vector of floats while up_step_type could be an integer, and down_slope_type could be a float, etc.

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 graphgenerator using the raytracer we just created
    HF::GraphGenerator::GraphGenerator GG = GraphGenerator::GraphGenerator(ray_tracer);
 
    // Setup Graph Parameters
    std::array<float, 3> start_point{ 0,0,0.25 };
    std::array<float, 3> spacing{ 1,1,1 };
    int max_nodes = 5;
    int up_step = 1; int down_step = 1;
    int up_slope = 45; int down_slope = 45;
    int max_step_connections = 1;
    int min_connections = 1;
 
    // Generate the graph using our parameters
    HF::SpatialStructures::Graph g = GG.BuildNetwork(
        start_point,
        spacing,
        max_nodes,
        up_step, up_slope,
        down_step, down_slope,
        max_step_connections,
        min_connections
    );
 

    
    // Get nodes from the graph
    auto nodes = g.Nodes();
 
    // Construct Output String
    std::ostringstream out_str;
 
    out_str << "[";
    for (int i = 0; i < nodes.size(); i++)
        out_str << nodes[i] << ((i != nodes.size() - 1) ? "," : "]");
 
    // Print to console.
    std::cout << out_str.str() << std::endl;
    

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

Definition at line 464 of file graph_generator.h.

References HF::GraphGenerator::CastToReal(), HF::GraphGenerator::CastToReal3(), IMPL_BuildNetwork(), and min_connections.

Referenced by GenerateGraph(), and GenerateGraphObstacles().

Here is the call graph for this function:

Here is the caller graph for this function:

CrawlGeom()

Graph HF::GraphGenerator::GraphGenerator::CrawlGeom

(

UniqueQueue &

todo

)

Perform breadth first search to populate the graph with with nodes and edges.

Parameters

todo	Todo list to hold unchecked nodes. Must atleast contain a single start point.

Precondition

todo contains the starting point for the graph.

See also

CrawlGeomParallel for a parallel version.

Returns

The Graph generated by performing the breadth first search.

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 graphgenerator using the raytracer we just created
    HF::GraphGenerator::GraphGenerator GG = GraphGenerator::GraphGenerator(ray_tracer);
 
    // Set parameters for graph generation
    std::array<float, 3> start_point{ 0,1,0 };
    std::array<float, 3> spacing{ 1,1,1 };
    int max_nodes = 5;
    int up_step = 1; int down_step = 1;
    int up_slope = 45; int down_slope = 45;
    int max_step_connections = 1;
    int min_connections = 1;
 
    // Since we're not calling BuildNetwork, we will need to set some parameters
    // in the GraphGenerator in order to use this function standalone
    
    // These parameters need to be set on the graph generator
    GG.core_count = -1;
    GG.max_nodes = 5;
    GG.max_step_connection = 1;
    GG.min_connections = 1;
    
    // Setup its params struct
    GG.params.up_step = up_step; GG.params.down_step = down_step;
    GG.params.up_slope = up_slope; GG.params.down_slope = down_slope;
    GG.params.precision.ground_offset = 0.01; 
    GG.params.precision.node_z = 0.001f;
    GG.params.precision.node_spacing = 0.001;
 
    // Assign it's spacing member, making sure to convert it to real3, the graph generator's
    // internal type for vectors of 3 coordinates.
    GG.spacing = HF::GraphGenerator::CastToReal3(spacing);
 
    // Construct a unique queue, and push back the start point
    HF::GraphGenerator::UniqueQueue queue;
    queue.push(start_point);
    

    
    // Call Crawl Geom with the queue
    auto g = GG.CrawlGeom(queue);
 

    
    // Get nodes from the graph
    auto nodes = g.Nodes();
 
    // Construct Output String
    std::ostringstream out_str;
 
    out_str << "[";
    for (int i = 0; i < nodes.size(); i++)
        out_str << nodes[i] << ((i != nodes.size() - 1) ? "," : "]");
 
    // Print to console.
    std::cout << out_str.str() << std::endl;
    

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

Definition at line 222 of file graph_generator.cpp.

References HF::SpatialStructures::Graph::addEdge(), HF::GraphGenerator::CastToReal3(), HF::GraphGenerator::CreateDirecs(), HF::GraphGenerator::UniqueQueue::empty(), HF::GraphGenerator::GeneratePotentialChildren(), HF::GraphGenerator::GetChildren(), max_nodes, max_step_connection, params, HF::GraphGenerator::UniqueQueue::pop(), HF::GraphGenerator::UniqueQueue::PushAny(), ray_tracer, and spacing.

Referenced by IMPL_BuildNetwork().

Here is the call graph for this function:

Here is the caller graph for this function:

CrawlGeomParallel()

Graph HF::GraphGenerator::GraphGenerator::CrawlGeomParallel

(

UniqueQueue &

todo

)

Perform breadth first search to populate the graph with nodes and edges using multiple cores.

Parameters

todo	Todo list to hold unchecked nodes. Must atleast contain a single start point.

Precondition

todo contains the starting point for the graph.

Returns

The Graph generated by performing the breadth first search.

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 graphgenerator using the raytracer we just created
    HF::GraphGenerator::GraphGenerator GG = GraphGenerator::GraphGenerator(ray_tracer);
 
    // Set parameters for graph generation
    std::array<float, 3> start_point{ 0,1,0 };
    std::array<float, 3> spacing{ 1,1,1 };
    int max_nodes = 5;
    int up_step = 1; int down_step = 1;
    int up_slope = 45; int down_slope = 45;
    int max_step_connections = 1;
    int min_connections = 1;
 
    // Since we're not calling BuildNetwork, we will need to set some parameters
    // in the GraphGenerator in order to use this function standalone
    
    // These parameters need to be set on the graph generator
    GG.core_count = -1;
    GG.max_nodes = 5;
    GG.max_step_connection = 1;
    GG.min_connections = 1;
    
    // Setup its params struct
    GG.params.up_step = up_step; GG.params.down_step = down_step;
    GG.params.up_slope = up_slope; GG.params.down_slope = down_slope;
    GG.params.precision.ground_offset = 0.01; 
    GG.params.precision.node_z = 0.001f;
    GG.params.precision.node_spacing = 0.001;
 
    // Assign it's spacing member, making sure to convert it to real3, the graph generator's
    // internal type for vectors of 3 coordinates.
    GG.spacing = HF::GraphGenerator::CastToReal3(spacing);
 
    // Construct a unique queue, and push back the start point
    HF::GraphGenerator::UniqueQueue queue;
    queue.push(start_point);
    

    
    // Call crawl geom parallel
    g = GG.CrawlGeomParallel(queue);
    

    
    // Get nodes from the graph
    auto nodes = g.Nodes();
 
    // Construct Output String
    std::ostringstream out_str;
 
    out_str << "[";
    for (int i = 0; i < nodes.size(); i++)
        out_str << nodes[i] << ((i != nodes.size() - 1) ? "," : "]");
 
    // Print to console.
    std::cout << out_str.str() << std::endl;
    

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

Definition at line 141 of file graph_generator.cpp.

References HF::SpatialStructures::Graph::addEdge(), HF::GraphGenerator::CastToReal3(), HF::GraphGenerator::CreateDirecs(), HF::GraphGenerator::UniqueQueue::empty(), HF::GraphGenerator::GeneratePotentialChildren(), HF::GraphGenerator::GetChildren(), max_nodes, max_step_connection, min_connections, params, HF::GraphGenerator::UniqueQueue::popMany(), HF::GraphGenerator::UniqueQueue::push(), ray_tracer, HF::GraphGenerator::UniqueQueue::size(), and spacing.

Referenced by IMPL_BuildNetwork().

Here is the call graph for this function:

Here is the caller graph for this function:

IMPL_BuildNetwork()

SpatialStructures::Graph HF::GraphGenerator::GraphGenerator::IMPL_BuildNetwork	(	const real3 &	start_point,
		const real3 &	Spacing,
		int	MaxNodes,
		real_t	UpStep,
		real_t	UpSlope,
		real_t	DownStep,
		real_t	DownSlope,
		int	max_step_connections,
		int	min_connections,
		int	cores = -1,
		real_t	node_z_precision = default_z_precision,
		real_t	node_spacing_precision = default_spacing_precision,
		real_t	ground_offset = default_ground_offset
	)

Generate a graph of accessible space.

Parameters

start_point	The starting point for the graph generator. If this isn't above solid ground, no nodes will be generated.
Spacing	Space between nodes. Lower values will yield more nodes for a higher resolution graph.
MaxNodes	The maximum amount of nodes to generate.
UpStep	Maximum height of a step the graph can traverse. Any steps higher this will be considered inaccessible.
UpSlope	Maximum upward slope the graph can traverse in degrees. Any slopes steeper than this will be considered inaccessible.
DownStep	Maximum step down the graph can traverse. Any steps steeper than this will be considered inaccessible.
DownSlope	The maximum downward slope the graph can traverse. Any slopes steeper than this will be considered inaccessible.
max_step_connections	Multiplier for number of children to generate for each node. Increasing this value will increase the number of edges in the graph, and as a result the amount of memory the algorithm requires.
min_connections	The required out-degree for a node to be valid and stored. This must be greater than 0 and equal or less than the total connections created from max_step_connections. Default is 1. A value of 8 when max_step_connections=1 would be a grid.
cores	Number of cores to use. -1 will use all available cores, and 0 will run a serialized version of the algorithm.
node_z_precision	Precision to round the z-component of nodes after a raycast is performed
node_spacing_precision	Precision to round nodes after spacing is calculated
ground_offset	Distance to offset nodes from the ground before checking line of sight

Returns

The resulting graph or an empty graph if the start check failed.

Note

All parameters relating to distances are in meters, and all angles are in degrees.

Geometry MUST be Z-UP in order for this to work.

Definition at line 69 of file graph_generator.cpp.

References core_count, CrawlGeom(), CrawlGeomParallel(), HF::GraphGenerator::GraphParams::down_slope, HF::GraphGenerator::GraphParams::down_step, HF::GraphGenerator::Precision::ground_offset, max_nodes, max_step_connection, min_connections, HF::GraphGenerator::Precision::node_spacing, HF::GraphGenerator::Precision::node_z, params, HF::GraphGenerator::GraphParams::precision, HF::GraphGenerator::UniqueQueue::PushAny(), ray_tracer, HF::GraphGenerator::SetupCoreCount(), spacing, HF::GraphGenerator::GraphParams::up_slope, HF::GraphGenerator::GraphParams::up_step, and HF::GraphGenerator::ValidateStartPoint().

Referenced by BuildNetwork().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

core_count

int HF::GraphGenerator::GraphGenerator::core_count

Number of cores to use for graph generation.

Definition at line 348 of file graph_generator.h.

Referenced by IMPL_BuildNetwork().

max_nodes

int HF::GraphGenerator::GraphGenerator::max_nodes

Maximum number of nodes to generate. If less than zero, generate nodes without a limit.

Definition at line 347 of file graph_generator.h.

Referenced by CrawlGeom(), CrawlGeomParallel(), and IMPL_BuildNetwork().

max_step_connection

int HF::GraphGenerator::GraphGenerator::max_step_connection

Multiplier for number of children to generate. The higher this is, the more directions there will be.

Definition at line 351 of file graph_generator.h.

Referenced by CrawlGeom(), CrawlGeomParallel(), and IMPL_BuildNetwork().

min_connections

int HF::GraphGenerator::GraphGenerator::min_connections

Minimum number of step connections for a node to be valid (minimum out degree of node)

Definition at line 350 of file graph_generator.h.

Referenced by BuildNetwork(), CrawlGeomParallel(), and IMPL_BuildNetwork().

params

GraphParams HF::GraphGenerator::GraphGenerator::params

Parameters to run the graph generator.

Definition at line 354 of file graph_generator.h.

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

ray_tracer

RayTracer HF::GraphGenerator::GraphGenerator::ray_tracer

A pointer to the raytracer to use for ray intersections.

Definition at line 356 of file graph_generator.h.

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

spacing

real3 HF::GraphGenerator::GraphGenerator::spacing

Spacing between nodes. New nodes will be generated with atleast this much distance between them.

Definition at line 352 of file graph_generator.h.

Referenced by CrawlGeom(), CrawlGeomParallel(), and IMPL_BuildNetwork().

---

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

• Cpp/analysismethods/src/graph_generator.h
• Cpp/analysismethods/src/graph_generator.cpp