Evaluate visibility between points in a set of locations. More...

Functions
bool	HeightCheck (const Node &Node, float height, EmbreeRayTracer &ert)
	Check if Node can be raised by height without clipping into any geometry. More...

vector< int >	HeightCheckAllNodes (const vector< Node > &nodes_to_filter, float height, EmbreeRayTracer &ert)
	Obtain the indexes of all nodes that pass the HeightCheck. More...

bool	IsOcclusionBetween (const Node &node_a, const Node &node_b, EmbreeRayTracer &ert, float height=1.7f, float pre_calculated_distance=0.0f)
	Perform a line of sight check between two nodes. More...

Graph	AllToAll (HF::RayTracer::EmbreeRayTracer &ert, const std::vector< HF::SpatialStructures::Node > &input_nodes, float height=1.7f)
	Generate a Visibility Graph between every node in a set of nodes in parallel. More...

Graph	GroupToGroup (HF::RayTracer::EmbreeRayTracer &ert, const std::vector< HF::SpatialStructures::Node > &from, const std::vector< HF::SpatialStructures::Node > &to, float height=1.7f)
	Generate a Visibility Graph from a set of nodes to another set of nodes. More...

Graph	AllToAllUndirected (HF::RayTracer::EmbreeRayTracer &ert, const std::vector< HF::SpatialStructures::Node > &nodes, float height, int cores=-1)
	Generate a Visibility Graph with every edge stored twice. More...

Detailed Description

Evaluate visibility between points in a set of locations.

A Visibility Graph is a graph of points of space locations that have a clear line of sight to eachother.

Edges in Visibility Graph are bidirectional, since if one node can see another node, the inverse is true. Generating a Visibility Graph from a set of nodes consists of performing a line of sight check between each combination of nodes, and creating an edge if the line of sight check passes.

Remarks: One can quickly summarize the information in a Visibility Graph by summarizing the values of its edges for each node in the graph.

See also: HF::SpatialStructures::Graph for more info on the Graph Datatype that is returned from all functions in the VisibilityGraph namespace.

Function Documentation

◆ AllToAll()

HF::SpatialStructures::Graph HF::VisibilityGraph::AllToAll	(	HF::RayTracer::EmbreeRayTracer &	ert,
		const std::vector< HF::SpatialStructures::Node > &	input_nodes,
		float	height = `1.7f`
	)

Generate a Visibility Graph between every node in a set of nodes in parallel.

Parameters

ert	A Raytracer conatining the geometry to use as obstacles for occlusion checks.
input_nodes	X,Y,Z locations of nodes for the Visibility Graph.
height	Height to offset nodes in the z-direction before generating the VisibilityGraph.

Returns: A VisibilityGraph for generated from every node in input_nodes. The cost of each edge in the graph is equal to the distance between both nodes.

Note: After nodes are offset from the ground, a check is performed to determine if it intersects any geometry. If offsetting the node causes it to intersect any geometry,then the node will not be considered for connections with other nodes and will always have no outgoing or incoming edges.

Every node is offset height meters off the ground, then an occlusion ray is cast between every set of nodes. If this occlusion ray does not intersect any geometry then an edge is created between the set of nodes with a cost equal to the distance between both nodes. The Graph generated by this algorithm is directed, however for each pair of nodes the edge is only stored in the node with the lower ID. This reduces the size of the graph in memory by about 50% and reduces the number of checks since every node will only need to check for edges with nodes that have a higher ID than itself.

Parallelism: Edges are checked on a seperate core for each node. This algorithm will always use every core on a user's machine.

Complexity: The time complexity of this algorithm is O(n^2), performing approximately (n^2+n)/2 operations gauranteed for each execution. The space complexity matches the time complexity, but the actual space used can be less depending on the number of edges created.

See also: AllToAllUndirected for a version of this algorithm that checks for edges between every node in nodes regardless of ID.; GroupToGroup For an algortithm that only calculates a visibility graph for one set of nodes to another set of nodes.

// be sure to #include "objloader.h"
 
// path to OBJ file for a flat plane
std::string plane_path = "plane.obj";
 
// Create a vector of MeshInfo from plane_path, using LoadMeshObjects. Note that
// LoadMeshObjects has two more arguments after plane_path - an enum
// HF::Geometry::GROUP_METHOD (defaults to GROUP_METHOD::ONLY_FILE) a bool
// (defaults to true, used to convert OBJ coordinate system to Rhino coordinates)
std::vector<HF::Geometry::MeshInfo> meshInfo = HF::Geometry::LoadMeshObjects(plane_path);
 
// Create an EmbreeRayTracer.
HF::RayTracer::EmbreeRayTracer tracer(meshInfo);
 
std::vector<HF::SpatialStructures::Node> node_vec;      // container of nodes
const int reserve_count = 100;                          // pre-defined reserve size
node_vec.reserve(reserve_count);                        // reserve reserve_count blocks for node_vec
 
// Construct reserve_count Node and insert each of them into node_vec
for (float i = -5.0; i < 5.0; i++) {
    // runs 10 times
    for (float j = -5; j < 5.0; j++) {
        // runs 10 times
        node_vec.emplace_back(Node(i, j, 0.0f));    // all Node ID default to -1
    }
}
 
// AllToAll constructs and returns a Graph consisting of Node (from node_vec)
// that do not occlude each other
float desired_height = 2.0f;        // Height of graph
HF::SpatialStructures::Graph graph = AllToAll(tracer, node_vec, desired_height);

Definition at line 128 of file visibility_graph.cpp.

References HF::SpatialStructures::Node::distanceTo(), HeightCheckAllNodes(), IsOcclusionBetween(), and HF::SpatialStructures::Graph::size().

Referenced by CreateVisibilityGraphAllToAll().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ AllToAllUndirected()

HF::SpatialStructures::Graph HF::VisibilityGraph::AllToAllUndirected	(	HF::RayTracer::EmbreeRayTracer &	ert,
		const std::vector< HF::SpatialStructures::Node > &	nodes,
		float	height,
		int	cores = `-1`
	)

Generate a Visibility Graph with every edge stored twice.

Parameters

ert	A Raytracer conatining the geometry to use as obstacles for occlusion checks.
from	X,Y,Z locations of nodes to create the visibility graph from.
Height	to offset nodes in the z-direction before generating the VisibilityGraph.
cores	number of cores to use for parallel processing. -1 will use all available cores.

Returns: A VisibilityGraph generated from every node in input_nodes. The cost of each edge in the graph is equal to the distance between both nodes.

Similar to VisibilityGraph::AllToAll, however every edge is stored in both nodes that it connects. For example, An edge betwee node 1 and node 2 would only be stored in node 1 in AllToAll, however here the edge would exist in both node1, and node2, in this algorithm.

Remarks: In most cases it's preferred to use VisibilityGraph::AllToAll since it saves a lot of time and space, however it may be advantageous to have edges stored in both nodes for certain applications.

Parallelism: Edges are checked on a seperate core for each node. This algorithm will use every core on a user's machine if cores is set to -1. Otherwise it will use the number of cores specified in cores.

complexity: O(n^2) in space and time.

// be sure to #include "objloader.h"
 
// path to OBJ file for a flat plane
std::string plane_path = "plane.obj";
 
// Create a vector of MeshInfo from plane_path, using LoadMeshObjects. Note that
// LoadMeshObjects has two more arguments after plane_path - an enum
// HF::Geometry::GROUP_METHOD (defaults to GROUP_METHOD::ONLY_FILE) a bool
// (defaults to true, used to convert OBJ coordinate system to Rhino coordinates)
std::vector<HF::Geometry::MeshInfo> meshInfo = HF::Geometry::LoadMeshObjects(plane_path);
 
// Create an EmbreeRayTracer.
HF::RayTracer::EmbreeRayTracer tracer(meshInfo);
 
std::vector<HF::SpatialStructures::Node> node_vec;      // container of nodes
const int reserve_count = 100;                          // pre-defined reserve size
node_vec.reserve(reserve_count);                        // reserve reserve_count blocks for node_vec
 
// Construct reserve_count Node and insert each of them into node_vec
for (float i = -5.0; i < 5.0; i++) {
    // runs 10 times
    for (float j = -5; j < 5.0; j++) {
        // runs 10 times
        node_vec.emplace_back(HF::SpatialStructures::Node(i, j, 0.0f)); // all Node ID default to -1
    }
}
 
// AllToAllUndirected constructs and returns a Graph consisting of Node (from
// node_vec) that do not occlude each other
float desired_height = 2.0f;        // Height of graph
int core_count = 4;                 // For omp_set_num_threads(int num_threads), CPU core count
HF::SpatialStructures::Graph graph =
    HF::VisibilityGraph::AllToAllUndirected(tracer, node_vec, desired_height, core_count);

Definition at line 252 of file visibility_graph.cpp.

References HF::SpatialStructures::Node::distanceTo(), HeightCheckAllNodes(), IsOcclusionBetween(), and HF::SpatialStructures::Graph::size().

Referenced by CreateVisibilityGraphAllToAllUndirected().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ GroupToGroup()

HF::SpatialStructures::Graph HF::VisibilityGraph::GroupToGroup	(	HF::RayTracer::EmbreeRayTracer &	ert,
		const std::vector< HF::SpatialStructures::Node > &	from,
		const std::vector< HF::SpatialStructures::Node > &	to,
		float	height = `1.7f`
	)

Generate a Visibility Graph from a set of nodes to another set of nodes.

Parameters

ert	A Raytracer conatining the geometry to use as obstacles for occlusion checks.
from	X,Y,Z locations of nodes to cast rays from.
to	X,Y,Z locations of nodes to cast rays to.
Height	to offset nodes in the z-direction before generating the VisibilityGraph.

Returns: A VisibilityGraph generated from every node in from to every node in to. The cost of each edge in the graph is equal to the distance between both nodes.

Note: The ID of nodes in the new graph wil correspond to the node's location in the from or to arrays. First every node in from will in from be placed in order, then every node in to will be placed in order. This means that the ID of every node in from will be equal to its index in from, and the ID of every node in to will be equal to the number of nodes in from plus its index in to.

The algorithm used here is similar to that of VisibilityGraph::AllToAll, however edges are cast from every node in from to every node in to. All nodes in to will have no outgoing edges.

Remarks: This can be useful for generating the visibility graph for a subset of nodes, such as the visibility from a building to the outside, without needing to calculate the visibility from every node to every other node.

Parallelism: Edges are checked on a seperate core for each node. This algorithm will always use every core on a user's machine.

Complexity: In time: O(ft) where f is the number of nodes in from, and t is the number of nodes in to. In space, O(ft) as well.

// be sure to #include "objloader.h"
 
// path to OBJ file for a flat plane
std::string plane_path = "plane.obj";
 
// Create a vector of MeshInfo from plane_path, using LoadMeshObjects. Note that
// LoadMeshObjects has two more arguments after plane_path - an enum
// HF::Geometry::GROUP_METHOD (defaults to GROUP_METHOD::ONLY_FILE) a bool
// (defaults to true, used to convert OBJ coordinate system to Rhino coordinates)
std::vector<HF::Geometry::MeshInfo> meshInfo = HF::Geometry::LoadMeshObjects(plane_path);
 
// Create an EmbreeRayTracer.
HF::RayTracer::EmbreeRayTracer tracer(meshInfo);
 
std::vector<HF::SpatialStructures::Node> node_vec_0;        // First container of Node
std::vector<HF::SpatialStructures::Node> node_vec_1;        // Second container of Node
 
const int reserve_count = 100;      // Pre-defined reserve size
node_vec_0.reserve(reserve_count);  // Reserve reserve_count blocks for both vectors
node_vec_1.reserve(reserve_count);
 
// 0) Construct reserve_count Node and insert each of them into node_vec_0
for (float i = -5.0; i < 5.0; i++) {
    // runs 10 times
    for (float j = -5.0; j < 5.0; j++) {
        // runs 10 times
        node_vec_0.emplace_back(HF::SpatialStructures::Node(i, j, 0.0f));   // all Node ID default to -1
    }
}
 
// 1) Construct reserve_count Node and insert each of them into node_vec_1
for (float i = 0.0; i < 10.0; i++) {
    for (float j = 0.0; j < 10.0; j++) {
        node_vec_1.emplace_back(HF::SpatialStructures::Node(i, j, 0.0f));   // all Node ID default to -1
    }
}
 
// GroupToGroup constructs and returns a Graph consisting of Node (between
// node_vec_0 and node_vec_1) such that the nodes do not occlude each other
float desired_height = 2.0f;        // Height of graph
HF::SpatialStructures::Graph graph = HF::VisibilityGraph::GroupToGroup(tracer, node_vec_0, node_vec_1, desired_height);

Definition at line 189 of file visibility_graph.cpp.

References HF::SpatialStructures::Node::distanceTo(), HeightCheckAllNodes(), IsOcclusionBetween(), and HF::SpatialStructures::Graph::size().

Referenced by CreateVisibilityGraphGroupToGroup().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ HeightCheck()

bool HF::VisibilityGraph::HeightCheck	(	const Node &	Node,
		float	height,
		EmbreeRayTracer &	ert
	)

inline

Check if Node can be raised by height without clipping into any geometry.

Parameters

Node	Node to perform height check on.
height	Distance to check above the node in meters. Default = 1.7m.
ert	Raytracer containing geometry to intersect with.

Returns: true if Node can be raised by height without intersecting with any geometry. False otherwise.

Cast an occlusion ray straight up with a distance of height to determine if it will intersect with any geometry.

Remarks: This is useful to prevent nodes from going through ceilings or other geometry when comparing the scores of all nodes in a model.

Definition at line 47 of file visibility_graph.cpp.

References HF::RayTracer::EmbreeRayTracer::Occluded(), and HF::SpatialStructures::ROUNDING_PRECISION.

Referenced by HeightCheckAllNodes().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ HeightCheckAllNodes()

vector< int > HF::VisibilityGraph::HeightCheckAllNodes	(	const vector< Node > &	nodes_to_filter,
		float	height,
		EmbreeRayTracer &	ert
	)

Obtain the indexes of all nodes that pass the HeightCheck.

Parameters

nodes_to_filter	Nodes to perform the height check on
height	Height to check above the nodes
ert	Raytracer containing the geometry to use as obstacles

Returns: The indexes in nodes_to_filter of all nodes that pass the height check.

See also: HeightCheck

Definition at line 69 of file visibility_graph.cpp.

References HeightCheck().

Referenced by AllToAll(), AllToAllUndirected(), and GroupToGroup().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ IsOcclusionBetween()

bool HF::VisibilityGraph::IsOcclusionBetween	(	const Node &	node_a,
		const Node &	node_b,
		EmbreeRayTracer &	ert,
		float	height = `1.7f`,
		float	pre_calculated_distance = `0.0f`
	)

inline

Perform a line of sight check between two nodes.

Parameters

node_a	Node to check occlusion from.
node_b	Node to check occlusion to.
ert	Raytracer containing the geometry to use as obstacles.
height	Distance to offset a node in the z-direction before performing the check.
pre_calculated_distance	Distance from node_a to node_b. If set to zero then this will be calculated automatically.

Returns: True if there is an obstacle blocking line of sight between node_a and node_b when raised to height.

Calculate the distance between node_a and node_b if required, then calculate the direction between them. Cast an occlusion ray in the direction between node_a and node_b with a maximum distance equal to the distance between them. If the ray intersects anything then the nodes don't have a line of sight.

Definition at line 103 of file visibility_graph.cpp.

References HF::SpatialStructures::Node::directionTo(), HF::SpatialStructures::Node::distanceTo(), and HF::RayTracer::EmbreeRayTracer::Occluded().

Referenced by AllToAll(), AllToAllUndirected(), and GroupToGroup().

Here is the call graph for this function:

Here is the caller graph for this function:

Functions

Detailed Description

Function Documentation

◆ AllToAll()

◆ AllToAllUndirected()

◆ GroupToGroup()

◆ HeightCheck()

◆ HeightCheckAllNodes()

◆ IsOcclusionBetween()