Functions
C_INTERFACE	GenerateGraph (HF::RayTracer::EmbreeRayTracer ray_tracer, const float start_point, const float spacing, int MaxNodes, float UpStep, float UpSlope, float DownStep, float DownSlope, int max_step_connection, int min_connections, int core_count, HF::SpatialStructures::Graph *out_graph)
	Construct a graph by performing a breadth-first search of accessible space. More...

C_INTERFACE	GenerateGraphObstacles (HF::RayTracer::EmbreeRayTracer ray_tracer, const float start_point, const float spacing, int MaxNodes, float UpStep, float UpSlope, float DownStep, float DownSlope, int max_step_connection, int min_connections, int core_count, const int obstacle_ids, const int walkable_ids, int num_obstacles, int num_walkables, HF::SpatialStructures::Graph *out_graph)
	Construct a graph by performing a breadth-first search of accessible space, seperating obstacles from walkable geometry. More...

Detailed Description

Perform a breadth-first search on a mesh to find accessible space.

Function Documentation

◆ GenerateGraph()

C_INTERFACE GenerateGraph	(	HF::RayTracer::EmbreeRayTracer *	ray_tracer,
		const float *	start_point,
		const float *	spacing,
		int	MaxNodes,
		float	UpStep,
		float	UpSlope,
		float	DownStep,
		float	DownSlope,
		int	max_step_connection,
		int	min_connections,
		int	core_count,
		HF::SpatialStructures::Graph **	out_graph
	)

#include <Cinterface/analysis_C.h>

Construct a graph by performing a breadth-first search of accessible space.

Parameters

ray_tracer	Raytracer containing the geometry to use for graph generation.
start_point	The starting point for the graph generator to begin searching from. If this isn't above solid ground, no nodes will be generated.
spacing	Space between nodes for each step of the search. Lower values will yield more nodes for a higher resolution graph.
MaxNodes	Stop generation after this many nodes. A value of -1 will generate an infinite amount of nodes. Note that the final node count may be greater than this value.
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_connection	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.
core_count	Number of cores to use. -1 will use all available cores, and 0 or 1 will run a serialized version of the algorithm.
out_graph	Address of a (HF::SpatialStructures::Graph *); out_graph will address heap-allocated memory to an initialized HF::SpatialStructures::Graph on success.

Returns: HF_STATUS::OK if graph creation was successful. HF_STATUS::NO_GRAPH if GenerateGraph failed to generate a graph with more than a single node.

See also: Raytracer setup (how to create a BVH), Raytracer teardown (how to destroy a BVH)

You must load an .obj file and create a BVH first.
Begin by reviewing the example at Raytracer setup before proceeding below.

First, determine the start point, spacing of nodes for each axis, and maximum nodes to generate.

        // Define start point.
        // These are Cartesian coordinates.
        std::array<float, 3> start_point { -1.0f, -6.0f, 1623.976928f };
 
        // Define spacing.
        // This is the spacing between nodes, with respect to each axis.
        std::array<float, 3> spacing { 0.5f, 0.5f, 0.5f };
 
        // Set max nodes.
        const int max_nodes = 500;

Then, determine the remainder of the values required by GenerateGraph before calling it.

        // Generate graph.
        // Notice that we pass the address of the graph pointer into GenerateGraph.
        //
        // GenerateGraph will assign the deferenced address to a pointer that points
        // to memory on the free store. We will call DestroyGraph to release the memory resources later on.
 
        float up_step = 1;                      // maximum height of a step the graph can traverse
        float up_slope = 1;                     // maximum upward slope the graph can traverse in degrees
        float down_step = 1;                    // maximum step down that the graph can traverse
        float down_slope = 1;                   // maximum downward slope that the graph can traverse
        int maximum_step_connection = 1;        // multiplier for number of children to generate for each node
        int core_count = -1;                    // CPU core count, -1 uses all available cores on the machine
 
        HF::SpatialStructures::Graph* graph = nullptr;
 
        status = GenerateGraph(bvh,
            start_point.data(), spacing.data(), max_nodes,
            up_step, up_slope,
            down_step, down_slope,
            maximum_step_connection,
            core_count,
            &graph);
 
        if (status != 1) {
            // Error!
            std::cerr << "Error at GenerateGraph, code: " << status << std::endl;
        }

Very important! Compress the graph after generating a graph or adding edges.

        // Always compress the graph after generating a graph/adding new edges
        status = Compress(graph);
 
        if (status != 1) {
            // Error!
            std::cerr << "Error at Compress, code: " << status << std::endl;
        }

To output the graph to the console, we must retrieve its nodes.

        // Get all nodes from graph first (the container of nodes)
        // The address of the local variable node_vector will be passed to GetAllNodesFromGraph;
        // it will be dereferenced inside that function and assigned memory via operator new.
        //
        // We will have to call DestroyNodes on node_vector to properly release this memory.
        // node_vector_data points to the internal buffer that resides within *(node_vector).
        //
        // When we call DestroyNodes, node_vector_data's memory will also be released.
        std::vector<HF::SpatialStructures::Node>* node_vector = nullptr;
        HF::SpatialStructures::Node* node_vector_data = nullptr;
 
        status = GetAllNodesFromGraph(graph, &node_vector, &node_vector_data);
 
        if (status != 1) {
            // Error!
            std::cerr << "Error at GetAllNodesFromGraph, code: " << status << std::endl;
        }
 
        // Get size of node vector
        int node_vector_size = -1;
        status = GetSizeOfNodeVector(node_vector, &node_vector_size);
 
        if (status != 1) {
            // Error!
            std::cerr << "Error at GetSizeOfNodeVector, code: " << status << std::endl;
        }
 
        // Print number of nodes in the graph
        std::cout << "Node count: " << node_vector_size << std::endl;

We are now ready to output the generated graph to the console.

        // Output 3 of the nodes within *node_vector.
        std::cout << "[";
        for (int i = 0; i < 3; i++) {
            auto n = (*node_vector)[i];
            std::cout << "("
                << n.x << ", " << n.y << ", " << n.z << ", "
                << n.id << ")";
 
            if (i < 2) {
                std::cout << " ";
            }
        }
        std::cout << "]" << std::endl;

When we are finished, we must destroy node_vector and graph.

 
 
        // destroy vector<Node>
        status = DestroyNodes(node_vector);
 
        if (status != 1) {
            // Error!
            std::cerr << "Error at DestroyNodes, code: " << status << std::endl;
        }
 
        // destroy graph
        status = DestroyGraph(graph);
 
        if (status != 1) {
            std::cerr << "Error at DestroyGraph, code: " << status << std::endl;
        }

From here, please review the example at Raytracer teardown for instructions
on how to free the remainder of the resources used by the graph –
which are the (vector<HF::Geometry::MeshInfo> *) and (HF::Raytracer::EmbreeRayTracer *) instances.

>>> LoadOBJ loaded mesh successfully into loaded_obj at address 000002468EEBBEB0, code: 1
>>> CreateRaytracer created EmbreeRayTracer successfully into bvh at address 00000246849C59B0, code: 1
>>> Node count: 594
>>> [(-1, -6, 0, 0) (-1.5, -6.5, -0, 1) (-1.5, -6, -0, 2)]

Definition at line 22 of file analysis_C.cpp.

References HF::GraphGenerator::GraphGenerator::BuildNetwork(), HF::SpatialStructures::Graph::Nodes(), and HF::Exceptions::OK.

Here is the call graph for this function:

◆ GenerateGraphObstacles()

C_INTERFACE GenerateGraphObstacles	(	HF::RayTracer::EmbreeRayTracer *	ray_tracer,
		const float *	start_point,
		const float *	spacing,
		int	MaxNodes,
		float	UpStep,
		float	UpSlope,
		float	DownStep,
		float	DownSlope,
		int	max_step_connection,
		int	min_connections,
		int	core_count,
		const int *	obstacle_ids,
		const int *	walkable_ids,
		int	num_obstacles,
		int	num_walkables,
		HF::SpatialStructures::Graph **	out_graph
	)