Generating path candidates#
When performing deterministic, or exact, Ray Tracing, we aim at exactly finding all possibles paths between two nodes (e.g., BS and UE) that undergo up to a fixed number of interactions.
To this end, a possible approach, as described in [EOJ23], is to first
generate a set of path candidates. Each path candidate represent an ordered list of interactions
with the environment. Then, a coordinates path will be computed for every path candidate using,
e.g., the image_method,
see Advanced Path Tracing.
Listing those path candidates is equivalent to finding all the paths from BS to UE in a graph that connects nodes and objects together.
Scene with known visibility matrix#
Let’s take the 2D example from [EOJ23, fig. 3]:
2-D scenario with triangular-shaped objects on which reflection or diffraction can occur. Surfaces are colored in red and edges in black.#
Depending on the visibility between the various objects in the scene, we can construct an adjacency graph, also referred to as visibility matrix [EOJ23, fig. 4]:
Each row of this 14 × 14 matrix refers to the visible objects as seen from the corresponding object. For readability purposes, zeros are discarded. The black coefficients describe reflection, while the red ones are describing diffraction.#
In the above matrix, the ones are indicating a visibility between pairs of nodes (i.e., objects) in the graph. That means that there exists a line segment that connects the two corresponding objects without intersecting any other object in the scene. If we omit the start and end nodes, usually denoting transmitters and receivers, respectively, the matrix should be symmetric.
We can construct a directed graph [Wikipediacontributors23b] (DiGraph) from this matrix
and iterate through all possible paths between BS and UE.
import numpy as np
from differt_core.rt.graph import DiGraph
adjacency_matrix = np.array(
[
[0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1],
[0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
]
).astype(bool)
We can test that our adjacency matrix, without BS and UE, is indeed symmetric.
sub_adjacency_matrix = adjacency_matrix[1:-1, 1:-1]
assert np.all(sub_adjacency_matrix == sub_adjacency_matrix.T)
di_graph = DiGraph.from_adjacency_matrix(adjacency_matrix)
from_ = 0 # BS
to = 13 # UE
for i, path in enumerate(di_graph.all_paths(from_, to, depth=4)):
print(f"#{i + 1:03d}: {path}") # noqa: T201
#001: [ 0 1 6 13]
#002: [ 0 1 10 13]
#003: [ 0 6 2 13]
#004: [ 0 6 8 13]
#005: [ 0 6 9 13]
#006: [ 0 7 6 13]
#007: [ 0 7 10 13]
#008: [ 0 8 6 13]
#009: [ 0 8 10 13]
#010: [ 0 8 12 13]
#011: [ 0 10 2 13]
#012: [ 0 10 8 13]
#013: [ 0 10 9 13]
#014: [ 0 12 2 13]
#015: [ 0 12 8 13]
#016: [ 0 12 9 13]
Scene with unknown visibility matrix#
In practice, computing the visibility for a 2D scene is quite complex, and almost impossible for 3D scene[1]. As a result, this is sometimes interesting to just assume that every object can potentially connect to every other object in the scene. In graph theory, such a configuration is called a complete graph [Wikipediacontributors23a].
Even though such a graph could be represented using DiGraph,
we provide the CompleteGraph class that generates
paths an order of magnitude faster than with an equivalent directed graph.
However, we usually don’t want to have BS and UE nodes to be appear multiple times in a path: we want BS to be connected to every other nodes, but no node should be connected to BS. Every node should be connected to UE, but UE should not be connected to any node.
To allow this with CompleteGraph, you must:
create a complete graph without BS and UE;
and then generate
all_paths*withfrom_andtoare that not part of the graph.
Because the implementation is for complete paths, it will assume that from_ to connected
to all the nodes in the graph. Then, I will also assume that any node can connect to node to.
See the example below for the same scene as above, but where we don’t know much about its visibility matrix.
from differt_core.rt.graph import CompleteGraph
complete_graph = CompleteGraph(12) # 12 objects
from_ = 12 # Can be anything >= 12
to = 13 # Can be anything >= 12 and != from_
for i, path in enumerate(complete_graph.all_paths(from_, to, depth=4)):
print(f"#{i + 1:03d}: {path}") # noqa: T201
#001: [12 0 1 13]
#002: [12 0 2 13]
#003: [12 0 3 13]
#004: [12 0 4 13]
#005: [12 0 5 13]
#006: [12 0 6 13]
#007: [12 0 7 13]
#008: [12 0 8 13]
#009: [12 0 9 13]
#010: [12 0 10 13]
#011: [12 0 11 13]
#012: [12 1 0 13]
#013: [12 1 2 13]
#014: [12 1 3 13]
#015: [12 1 4 13]
#016: [12 1 5 13]
#017: [12 1 6 13]
#018: [12 1 7 13]
#019: [12 1 8 13]
#020: [12 1 9 13]
#021: [12 1 10 13]
#022: [12 1 11 13]
#023: [12 2 0 13]
#024: [12 2 1 13]
#025: [12 2 3 13]
#026: [12 2 4 13]
#027: [12 2 5 13]
#028: [12 2 6 13]
#029: [12 2 7 13]
#030: [12 2 8 13]
#031: [12 2 9 13]
#032: [12 2 10 13]
#033: [12 2 11 13]
#034: [12 3 0 13]
#035: [12 3 1 13]
#036: [12 3 2 13]
#037: [12 3 4 13]
#038: [12 3 5 13]
#039: [12 3 6 13]
#040: [12 3 7 13]
#041: [12 3 8 13]
#042: [12 3 9 13]
#043: [12 3 10 13]
#044: [12 3 11 13]
#045: [12 4 0 13]
#046: [12 4 1 13]
#047: [12 4 2 13]
#048: [12 4 3 13]
#049: [12 4 5 13]
#050: [12 4 6 13]
#051: [12 4 7 13]
#052: [12 4 8 13]
#053: [12 4 9 13]
#054: [12 4 10 13]
#055: [12 4 11 13]
#056: [12 5 0 13]
#057: [12 5 1 13]
#058: [12 5 2 13]
#059: [12 5 3 13]
#060: [12 5 4 13]
#061: [12 5 6 13]
#062: [12 5 7 13]
#063: [12 5 8 13]
#064: [12 5 9 13]
#065: [12 5 10 13]
#066: [12 5 11 13]
#067: [12 6 0 13]
#068: [12 6 1 13]
#069: [12 6 2 13]
#070: [12 6 3 13]
#071: [12 6 4 13]
#072: [12 6 5 13]
#073: [12 6 7 13]
#074: [12 6 8 13]
#075: [12 6 9 13]
#076: [12 6 10 13]
#077: [12 6 11 13]
#078: [12 7 0 13]
#079: [12 7 1 13]
#080: [12 7 2 13]
#081: [12 7 3 13]
#082: [12 7 4 13]
#083: [12 7 5 13]
#084: [12 7 6 13]
#085: [12 7 8 13]
#086: [12 7 9 13]
#087: [12 7 10 13]
#088: [12 7 11 13]
#089: [12 8 0 13]
#090: [12 8 1 13]
#091: [12 8 2 13]
#092: [12 8 3 13]
#093: [12 8 4 13]
#094: [12 8 5 13]
#095: [12 8 6 13]
#096: [12 8 7 13]
#097: [12 8 9 13]
#098: [12 8 10 13]
#099: [12 8 11 13]
#100: [12 9 0 13]
#101: [12 9 1 13]
#102: [12 9 2 13]
#103: [12 9 3 13]
#104: [12 9 4 13]
#105: [12 9 5 13]
#106: [12 9 6 13]
#107: [12 9 7 13]
#108: [12 9 8 13]
#109: [12 9 10 13]
#110: [12 9 11 13]
#111: [12 10 0 13]
#112: [12 10 1 13]
#113: [12 10 2 13]
#114: [12 10 3 13]
#115: [12 10 4 13]
#116: [12 10 5 13]
#117: [12 10 6 13]
#118: [12 10 7 13]
#119: [12 10 8 13]
#120: [12 10 9 13]
#121: [12 10 11 13]
#122: [12 11 0 13]
#123: [12 11 1 13]
#124: [12 11 2 13]
#125: [12 11 3 13]
#126: [12 11 4 13]
#127: [12 11 5 13]
#128: [12 11 6 13]
#129: [12 11 7 13]
#130: [12 11 8 13]
#131: [12 11 9 13]
#132: [12 11 10 13]
Beware of the number of path candidates#
In first approximation, the number of path candidates grows exponentially with the path depth. Also, the more a graph is close to a complete graph, the more paths you will generate.
The CompleteGraph class returns
Sized iterators, where the length is roughly
equal to \(\texttt{num_nodes}(\texttt{num_nodes}-1)^{\texttt{depth}-3}\).
As a result, it may sometimes be smarter to estimate a visibility matrix, even
if it is not perfect, or iterate over of chunks of paths
(see *chunks_iter methods in differt.rt.graph)
when not possible.
Comparing DiGraph and CompleteGraph#
Let’s see how many paths we generate with the directed graph[2] and with the complete graph.
for depth in [2, 3, 4, 5, 6, 7]:
num_paths_di_graph = sum(1 for _ in di_graph.all_paths(0, 13, depth=depth))
num_paths_complete_graph = len(complete_graph.all_paths(12, 13, depth=depth))
print( # noqa: T201
f"{depth = }: {num_paths_di_graph:6d} (DiGraph) "
"vs {num_paths_complete_graph:6d} (CompleteGraph)"
)
depth = 2: 1 (DiGraph) vs {num_paths_complete_graph:6d} (CompleteGraph)
depth = 3: 4 (DiGraph) vs {num_paths_complete_graph:6d} (CompleteGraph)
depth = 4: 16 (DiGraph) vs {num_paths_complete_graph:6d} (CompleteGraph)
depth = 5: 56 (DiGraph) vs {num_paths_complete_graph:6d} (CompleteGraph)
depth = 6: 192 (DiGraph) vs {num_paths_complete_graph:6d} (CompleteGraph)
depth = 7: 680 (DiGraph) vs {num_paths_complete_graph:6d} (CompleteGraph)