DHARTAPI.VisibilityGraph.VisibilityGraph Class Reference

Contains all methods for generating Visibility Graphs. More...

Static Public Member Functions
static Graph	GenerateAllToAll (EmbreeBVH bvh, IEnumerable< Vector3D > nodes, float height=1.7f, bool directed=true)
	Create a visibility graph from every node to every node in nodes. More...
static Graph	GenerateGroupToGroup (EmbreeBVH bvh, IEnumerable< Vector3D > group_a, IEnumerable< Vector3D > group_b, float height=1.7f)
	Generate a directed visibility graph from nodes in group_a to the nodes in group_b. More...

Detailed Description

Contains all methods for generating Visibility Graphs.

Member Function Documentation

GenerateAllToAll()

static Graph DHARTAPI.VisibilityGraph.VisibilityGraph.GenerateAllToAll ( EmbreeBVH  bvh, IEnumerable< Vector3D >  nodes, float  height = 1.7f, bool  directed = true  )

static

Create a visibility graph from every node to every node in nodes.

Parameters

bvh	The BVH to intersect with.
nodes	The nodes to use in the visibility graph.
height	The height to offset each node from the ground.
directed	if set to true generate a directed graph, otherwise generate an undirected graph.

Returns

A Graph where each node is a node in nodes, and each edge represents a clear line of sight between the parent and child node. Any nodes that clip into geometry when offset by height will not be considered for any edge connections and will always have no outgoing or incoming edges.

Attention

When directed is true. Edges between nodes will only be stored in the edges of the node with the lower ID. To store the edge in the edge array of both nodes use false but be warned, it will take longer to execute and take up more memory. Read the following section for more info.

Directed vs Undirected

For the sake of this function, an undirected visibility graph describes a graph where edge is only stored in the graph for the node with the lowest ID. For example, The first node will check for edges from itself to every node in the set, node 2 will check for edges from itself to every other node except for the first node, node 3 will check every node except for the first and second. In contrast, a directed graph will check every node against every other node in the graph regardless of ID. In most cases you will want to use the undirected algorithm, as it only performs n(n+1)/2 operations vs the directed's n^2 operations.

Warning

Graphs output by this function CANNOT be modified.

See also

SpatialStructures.Graph.AggregateEdgeCosts for a way to easily summarize the results of a visibility graph.

Example

            // Load the example plane and convert it to z-up
            MeshInfo MI = (OBJLoader.LoadOBJ("ExampleModels/plane.obj", CommonRotations.Yup_To_Zup));
 
            // Construct a BVH from this mesh
            EmbreeBVH bvh = new EmbreeBVH(MI);
 
            // Define all nodes and put them into an array,
            Vector3D Point1 = new Vector3D(0, 0, 0);
            Vector3D Point2 = new Vector3D(0, 1, 0);
            Vector3D Point3 = new Vector3D(1, 0, 0);
            Vector3D Point4 = new Vector3D(1, 0, -4); // Node 4 is beneath the plane so it should have no connections
            Vector3D[] nodes = { Point1, Point2, Point3, Point4 };

            
            // Create a visibility from every node to every other node
            Graph G = DHARTAPI.VisibilityGraph.VisibilityGraph.GenerateAllToAll(bvh, nodes);
 
            // Aggregate the graph's edges to get the total distance from this node to all of its edges
            var results = G.AggregateEdgeCosts(GraphEdgeAggregation.SUM);
 
            // Print output
            Debug.WriteLine(results);
 

[2, 2.414214, 2.414214, 0]

GenerateGroupToGroup()

static Graph DHARTAPI.VisibilityGraph.VisibilityGraph.GenerateGroupToGroup ( EmbreeBVH  bvh, IEnumerable< Vector3D >  group_a, IEnumerable< Vector3D >  group_b, float  height = 1.7f  )

static

Generate a directed visibility graph from nodes in group_a to the nodes in group_b.

Parameters

bvh	The geometry to use for generating the visibility graph.
group_a	The nodes to cast rays from.
group_b	The nodes to cast rays to.
height	The height to offset nodes from the ground.

Returns

A graph contanining the visibility graph. Since a new graph is created, all nodes will be assigned ids for access within it. First every node in group_a will be assigned ids in order, then all nodes in group_b will be assigned ids in order. Nodes in group_a will be assigned IDs before those in group_b. All edges will be from nodes in group_a to nodes in group_b. Any nodes that clip into geometry when offset by height will not be considered for any edge connections and will always have no outgoing or incoming edges.

Precondition

No nodes in group_a also exist in group_b and vice versa.

Attention

Any nodes that clip into geometry when offset by height will not be considered for any edge connections.

See also

GenerateAllToAll to generate a graph from every node to every other node.

Example

            // Load the example plane and convert it to z-up
            MeshInfo MI = (OBJLoader.LoadOBJ("ExampleModels/plane.obj", CommonRotations.Yup_To_Zup));
 
            // Construct a BVH from this mesh
            EmbreeBVH bvh = new EmbreeBVH(MI);
 
            // Define all nodes and put them into an array,
            Vector3D Point1 = new Vector3D(0, 0, 0);
            Vector3D Point2 = new Vector3D(0, 1, 0);
            Vector3D Point3 = new Vector3D(1, 0, 0);
            Vector3D Point4 = new Vector3D(1, 0, -4); // Node 4 is beneath the plane so it should have no connections
            Vector3D[] nodes = { Point1, Point2, Point3, Point4 };

 
            // Define two groups of nodes
            Vector3D[] group_a = { Point1, Point2 };
            Vector3D[] group_b = { Point3, Point4 };
 
            // Generate a visibility graph from group A to group B
            Graph G = DHARTAPI.VisibilityGraph.VisibilityGraph.GenerateGroupToGroup(bvh, group_a, group_b);
 
            // Print the results
            var results = G.AggregateEdgeCosts(GraphEdgeAggregation.SUM);
 
            Debug.WriteLine("[{0}, {1}, {2}, {3}]", results[0], results[1], results[2], results[3]);
 

1, 1.414214, 0, 0

Note how the nodes in group B have scores of 0. This is because edges are only calculated from group a to group B and by default AggredgateEdgeCosts only considers outgoing costs with it's default parameters. Since group to group graphs only store the edges for a node in one of the two nodes, you should use Graph.AggregateEdgeCosts(GraphEdgeAggregation.SUM, directed:false) to get the accurate score for every node, since the edges of a visibility graph are bidirectional.

 
            // Print the undirected results
            results = G.AggregateEdgeCosts(GraphEdgeAggregation.SUM, directed:false);
 
            Debug.WriteLine("[{0}, {1}, {2}, {3}]", results[0], results[1], results[2], results[3]);
 

[1, 1.414214, 2.414214, 0]

As you can see here, node 3 has a score of 0 since it doesn't have a clear line of sight to either of the nodes in group a. Node 2 has a score equal to that of 0 and 1 combined since it has a clear line of sight to both of them.

---

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

• src/Csharp/packages/visibilitygraph/src/VisibilityGraph.cs