Versatile, Reliable, and High-Performance Tool for Computing Visibility in Polygonal Environments
TřiVis, named after the Czech word 'tři' (meaning 'three') and the term 'visibility', is a C++ library for computing visibility-related structures in 2D polygonal environments. It is based on the triangular expansion algorithm (Bungiu et al., 2014; Xu and Güting, 2015), which uses preprocessing to convert the input polygonal environment into a triangular mesh, and then traverses the mesh to compute visibility regions, visibility graphs, ray-shooting queries, and other visibility-related structures.
- Definitions
- Main Features
- Building and Linking
- Basic Usage
- Dependencies
- Repository Contents
- TřiVis Codebase
- TřiVis+
- Examples
- Performance Evaluation
- Mesh Optimization
- Documentation
- License
- Polygonal Environment: A 2D environment consisting of a single outer boundary and zero or more inner boundaries (holes), where each boundary is a simple polygon.
- Triangular Mesh: A mesh of triangles including adjacency information that covers the polygonal environment, where the intersection of any two triangles is either empty, a common edge, or a common vertex.
- Point Location Query: Determines the triangle of the triangular mesh that contains a given point in the polygonal environment or reports that the point is outside the environment.
- Visibility: Two points in the polygonal environment are visible to each other if the line segment connecting them lies entirely within the environment (touching the boundaries is allowed).
- Two-Point Visibility Query: Determines whether two given points in the polygonal environment are visible to each other.
- Ray-Shooting Query: Determines an intersection point of a ray starting at a given interior point in a given direction with the boundary of the polygonal environment.
- Visibility Region Query: Determines the region of the polygonal environment visible from a given interior point.
- Visible Vertices Query: Determines the subset of vertices of the polygonal environment visible from a given interior point.
- Visible Points Query: Determines the subset of given interior points that are visible from another given interior point.
- Vertex-Vertex Visibility Graph: A graph where vertices represent the vertices of the polygonal environment, and edges represent visibility between pairs of vertices.
- Point-Point Visibility Graph: A graph where vertices represent given interior points, and edges represent visibility between pairs of points.
- Point-Vertex Visibility Graph: A graph where vertices represent both given interior points and vertices of the polygonal environment, and edges represent visibility between pairs of points and vertices.
- Limited Visibility Range: A constraint on the visibility queries that restricts the visibility range to a given distance from the query point.
TřiVis supports all the queries defined above, each with a specialized, easy-to-use API.
The main feature of TřiVis is the triangular expansion
algorithm (Bungiu et al., 2014; Xu and Güting, 2015), which provides
It is important to note that the query time complexity is worst-case, and the actual query time may be significantly lower in practice. This is especially true for TřiVis, as the triangular expansion algorithm is known to exhibit output-sensitive behavior to some extent, traversing only the triangles that are partially or fully visible from the query point (Bungiu et al., 2014).
TřiVis supports limited-range queries, employing an early termination mechanism to avoid traversing unnecessary triangles of the triangular mesh. This can significantly reduce the query time for queries with a highly restricted visibility range relative to the average size of the open space in the environment.
TřiVis employs a bucketing technique to accelerate point location queries, which are essential for visibility-related queries.
Using the bucketing technique from (Edahiro et al., 1984), TřiVis achieves
TřiVis relies on floating-point arithmetic and incorporates a unique combination of adaptive robust geometry predicates (Shewchuk, 1997) and
TřiVis has been tested on 34 complex polygonal environments with up to 8,320 vertices and 679 holes by computing visibility regions for 1,000 interior points in each environment. With an average query time of 9±6μs, TřiVis outperforms other tested implementations by at least an order of magnitude, while keeping the preprocessing time below 20ms for the tested polygonal environments. For more information, refer to the Performance Evaluation section.
TřiVis is built with CMake.
To make the library available to your C++ project, you can copy the trivis/ directory and include it in your CMakeLists.txt:
add_subdirectory(path_to_trivis) # Add the library to your project.
target_link_libraries(your_target PUBLIC Trivis) # Link the library to your target.
The build has been tested with the GCC 12.3.0 compiler and CMake 3.28.1 on the Ubuntu 20.04.6 LTS operating system. For your convenience, the conda/trivis.yml file describes Conda environment with the exact compiler and CMake versions used by the authors.
To create and test the environment, run the following in the root directory of this repository:
# Assuming you have Conda installed:
conda env create -f conda/trivis.yml
conda activate trivis
gcc --version
cmake --version
mkdir build
cd build
cmake ../trivis
make
Apart from TřiVis's source code, this repository also contains TřiVis+, an extension adding support for data loading and visualization, and an Examples project depending on TřiVis+, demonstrating the library's usage.
For more information, refer to the Repository Contents section.
To use the library in your C++ project, include the main header file:
#include "trivis/trivis.h"
TřiVis's main API is the trivis::Trivis
class, which provides methods for visibility-related queries.
It is initialized with a polygonal environment represented by a trivis::geom::PolyMap
object.
trivis::Trivis vis;
{ // Scope for the environment.
trivis::geom::PolyMap environment;
// TODO: Fill the environment.
vis = trivis::Trivis{std::move(environment)};
} // The environment was moved to vis.
The triangular mesh of the environment has just been constructed. To inspect it, you can access the mesh directly through const reference:
const trivis::mesh::TriMesh &mesh = vis.mesh();
// TODO: Do something with the mesh.
To perform most of the visibility-related queries, you need to provide the query point, the point location result, and the visibility range (if limited).
trivis::geom::FPoint query;
// TODO: Fill the query.
std::optional<double> range;
// TODO: Set the visibility range or leave it unlimited.
std::optional<trivis::Trivis::PointLocationResult> plr = vis.LocatePoint(query);
if (plr.has_value()) {
// The query point is inside the environment.
// TODO: Perform visibility queries.
} else {
// The query point is outside the environment.
// TODO: Handle the case.
}
if (plr.has_value()) {
trivis::geom::FPoint target;
// TODO: Fill the target.
bool is_visible = vis.IsVisible(query, plr.value(), target, range);
// TODO: Do something with the visibility result.
}
if (plr.has_value()) {
trivis::geom::FPoint direction;
// TODO: Fill the direction.
std::optional<trivis::Trivis::RayShootingResult> rsr = vis.ShootRay(query, plr.value(), direction, range);
if (rsr.has_value()) {
trivis::geom::FPoint intersection = rsr->p;
// TODO: Do something with the intersection point.
} else {
// The intersection point is outside the visibility range.
}
}
if (plr.has_value()) {
trivis::AbstractVisibilityRegion abs_vis_region = vis.VisibilityRegion(query, plr.value(), range);
trivis::RadialVisibilityRegion vis_region = vis.ToRadialVisibilityRegion(abs_vis_region);
if (range.has_value()) {
vis_region.IntersectWithCircleCenteredAtSeed(range);
}
// Optional post-processing:
auto vis_region_appx = vis_region; // Copy the visibility region.
if (range.has_value()) {
vis_region_appx.SampleArcEdges(M_PI / 180.0); // Approximate circular arc edges with line segments.
}
trivis::geom::FPolygon vis_polygon_appx = vis_region_appx.ToPolygon();
// TODO: Do something with the visibility polygon.
}
if (plr.has_value()) {
std::vector<int> visible_vertices = vis.VisibleVertices(query, plr.value(), range);
// TODO: Do something with the visible vertices.
}
// Prepare the input structures outside 'if (plr.has_value())' as they might be reused.
std::vector<trivis::geom::FPoint> input_points;
// TODO: Fill the input points.
std::vector<std::optional<trivis::Trivis::PointLocationResult>> input_plrs;
input_plrs.reserve(input_points.size());
for (const auto &p : input_points) {
input_plrs.push_back(vis.LocatePoint(p));
}
if (plr.has_value()) {
std::vector<int> visible_points = vis.VisiblePoints(query, plr.value(), input_points, input_plrs, range);
// TODO: Do something with the visible points.
}
std::vector<std::vector<int>> vertex_vertex_graph = vis.VertexVertexVisibilityGraph(range);
// TODO: Do something with the vertex-vertex visibility graph.
std::vector<std::vector<int>> point_point_graph = vis.PointPointVisibilityGraph(input_points, input_plrs, range);
// TODO: Do something with the point-point visibility graph.
std::vector<std::vector<int>> point_vertex_graph = vis.PointVertexVisibilityGraph(input_points, input_plrs, range);
// TODO: Do something with the point-vertex visibility graph.
TřiVis is self-contained, meaning it does not depend on external libraries. However, it includes some third-party libraries that are freely available for private, research, and institutional use, and they are bundled with TřiVis's source code:
- Triangle, for triangular mesh generation (Shewchuk, 1996).
- Robust Geometric Predicates, for geometry primitives (Shewchuk, 1997).
- Clipper2, for polygon clipping operations and related geometric algorithms.
These third-party libraries are located in the trivis/lib directory. While the source code of these libraries is included in TřiVis, their licenses are preserved and can be found in the respective subdirectories of the trivis/lib directory. Please refer to the exact licencing terms in LICENSE.md.
If you use TřiVis, please make sure to comply with the licenses of the third-party libraries and give proper attribution to their authors.
This repository includes TřiVis, as well as some extensions, example projects and utilities:
- conda/: Convenience Conda environment files.
- data/: A data directory structure, initially empty except for a single example map, for storing polygonal environments (maps), meshes, and query points. The example projects assume this directory structure.
- examples/: Example project demonstrating the usage of TřiVis.
- mesh_optim/: Mesh optimization project.
- performance/: Performance evaluation project.
- trivis/: TřiVis library (core).
- trivis_plus/: TřiVis+ library, an extension adding support for data loading and visualization.
- build.bash: A convenience script for building the library and example projects.
- CMakelists.txt: The main CMake configuration file for building the library and example projects.
- LICENSE.md: The license file for TřiVis.
- README.md: This README file.
- setup.bash: A convenience script for setting the environment variables configuring the build. By default, it contains configuration for building just the TřiVis library, but you can modify it to include TřiVis+ and the example projects.
Assuming we are in the trivis/ directory, the root directory of the TřiVis codebase, the lower-level directory structure is as follows:
- include/trivis/: Header files of the TřiVis library.
- geom/: Geometric types and utilities (includes a wrapper around Robust Geometric Predicates).
- mesh/: Triangular mesh type and utilities (includes a wrapper around Triangle).
- pl/: Point location class and utilities.
- utils/: General utilities (includes conversions to and from Clipper2).
- trivis.h: The main TřiVis API (
trivis::Trivis
class). - vis_regions.h: Visibility region types and utilities.
- lib/: Contains the third-party libraries bundled with TřiVis.
- clipper/: Clipper2.
- robust-predicate/: Robust Geometric Predicates.
- triangle/: Triangle.
- CMakelists.txt: The CMake configuration file for building the third-party libraries.
- src/trivis/: Contains the source files of the TřiVis library. Copies the structure of include/trivis/.
- CMakelists.txt: The CMake configuration file for building the TřiVis library.
TřiVis+ is an extension of TřiVis that adds support for data loading and visualization, as well as some extra utilities.
It includes two additional, heavier dependencies, which is why it is separated from the TřiVis (core) library:
To make TřiVis+ available to your C++ project, you can copy the trivis/ and trivis_plus/ directories and include them in your CMakeLists.txt.
add_subdirectory(path_to_trivis) # Add the library to your project.
add_subdirectory(path_to_trivis_plus) # Add the extension to your project.
target_link_libraries(your_target PUBLIC TrivisPlus) # Link just the extension to your target.
For your convenience, the conda/trivis_boost_cairo.yml file describes Conda environment with the exact compiler, CMake version, and the Boost and Cairo libraries used by the authors.
To create and test the environment, run the following in the root directory of this repository:
# Assuming you have Conda installed:
conda env create -f conda/trivis_boost_cairo.yml
conda activate trivis
mkdir build
cd build
echo "add_subdirectory(../trivis .)\nadd_subdirectory(../trivis_plus .)" > CMakeLists.txt
cmake .
make
Assuming we are in the trivis_plus/ directory, the root directory of the TřiVis+ codebase, the lower-level directory structure is as follows:
- include/trivis_plus/: Header files of the TřiVis+ extension.
- data_loading/: Data loading utilities.
- drawing/: Drawing utilities (includes a wrapper around Cairo).
- utils/: General utilities, including logging.
- trivis_plus.h: Convenience header including all TřiVis+ headers.
- src/trivis_plus/: Contains the source files of the TřiVis+ extension. Copies the structure of include/trivis_plus/.
- CMakelists.txt: The CMake configuration file for building the TřiVis+ extension.
For usage examples, refer to the Examples sections.
The example project located in the examples/ directory demonstrates the usage of TřiVis (and secondarily also TřiVis+).
To build the project, you may first need to create the respective Conda environment:
conda env create -f conda/trivis_boost_cairo.yml
conda activate trivis
Alternatively, you may already have all the necessary dependencies installed.
Now, you need to set the environment variables to configure the build:
export TRIVIS_BUILD_TRIVIS_PLUS=1
export TRIVIS_BUILD_EXAMPLES=1
Alternatively, you may modify the setup.bash to fix the configuration and run source setup.bash
.
Now, you can build the project:
bash build.bash
This will create the build-Release
directory with the executables located in the build-Release/examples
directory.
Now you can experiment with the examples and once you are done, you can inspect the source codes in the examples/ directory.
When experimenting with the examples, the default behavior is that the input polygonal environment is loaded from the data/maps/ directory, the text output is printed to the console and the graphical output is saved to the examples/outputs/ directory.
Next are some examples of how to run the example executables.
./build-Release/examples/vis_2point
./build-Release/examples/vis_2point --vis-radius 10
./build-Release/examples/vis_2point --shoot-ray
./build-Release/examples/vis_2point --help # to see all options
./build-Release/examples/vis_region
./build-Release/examples/vis_region --vis-radius 8
./build-Release/examples/vis_region --vis-radius 8 --sample-arc-edges 0.1
./build-Release/examples/vis_region --vis-radius 8 --sample-arc-edges 0.1 --to-polygon
./build-Release/examples/vis_region --help # to see all options
./build-Release/examples/vis_vertices
./build-Release/examples/vis_vertices --reflex-only
./build-Release/examples/vis_vertices --vis-radius 6
./build-Release/examples/vis_vertices --help # to see all options
./build-Release/examples/vis_graph
./build-Release/examples/vis_graph --reflex-only
./build-Release/examples/vis_graph --reflex-only --vis-radius 6
./build-Release/examples/vis_graph --point-vertex --reflex-only --vis-radius 6
./build-Release/examples/vis_graph --point-point
./build-Release/examples/vis_graph --help # to see all options
Once you are done experimenting with the examples, and you have inspected the source codes, you can start writing your own experimental code based on the examples.
For your convenience, we provide the examples/sandbox.cc file, which you can use as a starting point for your own experiments. It is built together with the examples by default, and you can run it as follows:
./build-Release/examples/sandbox --help # to see all options
TřiVis, or more specifically, its computation of visibility regions, has been extensively evaluated against several competing implementations on a dataset of 34 complex polygonal environments.
The competing implementations were:
- CGAL-TEA-CE: CGAL's triangular expansion algorithm (v5.6) with exact constructions.
- CGAL-TEA-CI: CGAL's triangular expansion algorithm (v5.6) with inexact constructions.
- CGAL-RSA-CE: CGAL's rotational sweep algorithm (v5.6) with exact constructions.
- CGAL-RSA-CI: CGAL's rotational sweep algorithm (v5.6) with inexact constructions.
- VisiLibity1: VisiLibity (v1).
The evaluation is detailed in a manuscript currently (as of March 2024) submitted to the 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
Below is a guide on how to replicate the performance evaluation from the manuscript.
The performance evaluation project is located in the performance/ directory. It is dependent on the TřiVis+ extension, and includes two additional dependencies:
- CGAL (version 5.6), which can be installed system-wide or in a Conda environment.
- VisiLibity1, which is included in the performance/lib/ directory.
To build the project, you may first need to create the respective Conda environment:
conda env create -f conda/trivis_boost_cairo_cgal.yml
conda activate trivis
Alternatively, you may already have all the necessary dependencies installed.
Now, you need to set the environment variables to configure the build:
export TRIVIS_BUILD_TRIVIS_PLUS=1
export TRIVIS_BUILD_PERFORMANCE=1
Alternatively, you may modify the setup.bash to fix the configuration and run source setup.bash
.
Building the project is now as simple as running:
bash build.bash
This will create the build-Release
directory with the executables located in the build-Release/performance
directory.
Note: The dataset was derived from the Iron Harvest dataset (Harabor et al., 2022). We have only preprocessed the dataset to TřiVis's input format by selecting the largest polygon per map, including its holes, and discarding the remaining polygons (mainly artifacts). If you are going to use the dataset, please give proper attribution to the authors of the original dataset.
Download the dataset from here and extract it to the data/maps/ directory.
The following will generate the test points in the data/points/ directory and save the CDT mesh for each map in the data/meshes/ directory:
cd performance
bash gen_points_all.bash
The following will construct the visibility regions by all the implementations and save the raw outputs in the performance/outputs/ directory:
bash test_all.bash # this may take several hours
The following will compare the results with the reference implementation and save the evaluation results in the performance/results/csv/ directory:
bash eval_all.bash # this may take several minutes
rm outputs/* # you can now remove the raw outputs
The results are processed with datatable. To use it, you may need to create a Conda environment with the conda/datatable.yml file:
conda create env -f ../conda/datatable.yml
conda activate datatable
Now, you can process the results:
cd results
python process1.py
This will generate the results.csv
file in the performance/results/ directory, which you can inspect and compare with the authors' results located in the performance/results/authors_results.csv file.
In our original research (Mikula and Kulich, 2024), we have addressed the problem of improving the query performance of the triangular expansion algorithm for computing visibility regions by finding the most advantageous instance of the triangular mesh.
TřiVis (in its earlier stages of development) was used as the basecode for the research, and the mesh optimization project in the mesh_optim/ implemented the mesh optimization algorithms and experiments.
Below is a guide on how to replicate the experiments from the research.
Note: The results presented in Mikula and Kulich (2024) were obtained using earlier version of TřiVis (0.3.0). The current version of mesh_optim/ project has been later updated to work with the current versions of TřiVis and TřiVis+. However, due to the extensive experiments, the authors have not yet had the time to test the updated version of the project on the full dataset.
The mesh optimization project is located in the mesh_optim/ directory. It is dependent on the TřiVis+ extension.
To build the project, you may first need to create the respective Conda environment:
conda env create -f conda/trivis_boost_cairo_python.yml
conda activate trivis
Alternatively, you may already have all the necessary dependencies installed.
Now, you need to set the environment variables to configure the build:
export TRIVIS_BUILD_TRIVIS_PLUS=1
export TRIVIS_BUILD_MESH_OPTIM=1
Alternatively, you may modify the setup.bash to fix the configuration and run source setup.bash
.
Building the project is now as simple as running:
bash build.bash
This will create the build-Release
directory with the executables located in the build-Release/mesh_optim
directory.
Note: The dataset was derived from the Iron Harvest dataset (Harabor et al., 2022). We have only preprocessed the dataset to TřiVis's input format by selecting the largest polygon per map, including its holes, and discarding the remaining polygons (mainly artifacts). Additionally, we have generated simple-polygon versions of the maps, as described in detail in the manuscript (Mikula and Kulich, 2024). If you are going to use the dataset, please give proper attribution to the authors of the original dataset.
Download the dataset from here and extract it to the data/maps/ directory.
To replicate every single experiment from Mikula and Kulich (2024), run the following:
cd mesh_optim/experiments
bash run_experiments_all.bash # this may take a few days
cd ../..
Alternatively, you can inspect the scripts in the mesh_optim/experiments/ directory and run them individually.
The results are processed with datatable. To use it, you may need to create a Conda environment with the conda/datatable.yml file:
conda create env -f conda/datatable.yml
conda activate datatable
To process all the results, run the following:
cd mesh_optim/results
bash process_all.bash # this may take several minutes
cd ../..
Alternatively, you can inspect the scripts in the mesh_optim/results/ directory and run them individually.
The results are saved in the csv/, figures/, and tables/ subdirectories of the mesh_optim/results/ directory.
Currently, TřiVis lacks detailed documentation beyond this README file due to time constraints faced by the authors. However, the simplicity of the API, coupled with the guidance provided in the Basic Usage section and the examples available in the examples/ directory (further explained in the Examples section), should facilitate seamless adoption of TřiVis for users.
Please see the LICENSE.md file for the license of TřiVis.