# Deep Dive Perception Module

This page aims to give details into the concepts of MOSAICs perception module, for information on the usage view the documentation here. Perception in MOSAIC is evaluated in a two-step process:

- First a spatial search, using a spatial index, is performed to get a pre-selection of relevant vehicles
- Second a Field-Of-View Filter is used to get a list of actually perceived vehicles

### Spatial Search & Spatial indexes

A spatial index is a data structure representing simulation entities on a 2D-plane allowing for fast spatial searches.
For our purpose this means, that we create a minimum bounding rectangle for a vehicles' perception range and perform a
spatial search for entities in that rectangle.
To allow every vehicle to access the spatial index we opted for a global implementation in the
Application Simulator, which is only updated when some vehicle
requests a spatial search (lazy loading).
MOSAIC provides three implementations for the spatial index: `Trivial`

, `QuadTree`

and `Grid`

.

#### Trivial

The trivial index doesn’t implement any index data-structure and just iterates over all entities in a for loop. This is sufficient for small scenarios with limited amount of vehicles.

#### Quad-Tree

The Quad-Tree index represents entities in a tree data structure, that stores entities in a node up to a `splitSize`

amount.
Every node strictly has *no* or *four* children. The four children divide the space into four equally sized quadrants.
Additionally, a `joinSize`

and a `maxDepth`

are configured, that control, when four children are joined back to one node and
the maximum depth of the tree respectively.

The Quad-Tree has the advantage of dynamically separating the space according to the utilization of the map. However, in practise we measured slightly worse performance compared to the grid.

#### Grid

The grid is a simple data-structure that divides the space into equally sized cells with configured `cellWidth`

s and `cellHeight`

s.
Entities positions are converted to grid-coordinates and stored in a map.
When doing a spatial search the pre-selection of vehicles happens by returning all entities in cells, that overlap with the search area.

While showing slightly better performance than the Quad-Tree, the grid requires the memory allocation of all cells at start-up,
which can lead to large memory consumption in big scenarios.
Additionally, the optimal grid size depends on the viewing ranges of your entities. In the best case scenario a maximum of four grid-cells
have to be queried. This is the case if the `cellWidth`

and `cellHeight`

are at least the size of your longest viewing range.

### Field-Of-View Filter

After a pre-selection of entities has been made using the spatial index we have to evaluate if vehicles are actually in the field-of-view of the ego vehicle. The field-of-view boils down to the sector of a circle, which is defined by its two bounding vectors $\overrightarrow{b}$ and $\overrightarrow{c}$ and the radius/sight distance $h$. Using the dot product, we can figure out if an object lies to the right or the left of a vector. Combining this with a check if the distance is smaller than $h$ allows us to determine whether an object $\overrightarrow{m}$ lies within the perception range.

$$ \begin{align} &\text{1. }\overrightarrow{c} \cdot \overrightarrow{m} \geq 0 \\ &\text{2. }\overrightarrow{m} \cdot \overrightarrow{b} \geq 0 \\ &\text{3. }|\overrightarrow{m}| \leq h \end{align} $$

**Left**: Minimum Bounding Rectangle spanned by left and right bounding vectors $\overrightarrow{b}$ & $\overrightarrow{c}$ with length $h$, the

*origin*() and, all cardinal direction vectors $\overrightarrow{a}_0$ to $\overrightarrow{a}_3$ contained within the viewing anlge $\gamma$.

**Right**: Field-Of-View evaluation ($\overrightarrow{m}$ is within range, $\overrightarrow{n}$ is not)