TřiVis

Versatile, Reliable, and High-Performance Tool for Computing Visibility in Polygonal Environments

About

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

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.

Main Features

Supported Queries

TřiVis supports all the queries defined above, each with a specialized, easy-to-use API.

Worst-Case Query Complexity

The main feature of TřiVis is the triangular expansion algorithm (Bungiu et al., 2014; Xu and Güting, 2015), which provides $O(n)$ query time for two-point visibility and ray-shooting queries, $O(nh)$ for visibility region and visible vertices/points queries, $O(n^2h)$ for the vertex-vertex visibility graph, and $O(pnh)$ for point-point and point-vertex visibility graphs. Here, $n$ is the number of vertices in the polygonal environment, $h$ is the number of holes, and $p$ is the number of input interior points.

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).

Efficient Limited-Range Queries

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.

Fast Point Location

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 $O(1)$ expected query time for point location queries.

Robustness and Reliability

TřiVis relies on floating-point arithmetic and incorporates a unique combination of adaptive robust geometry predicates (Shewchuk, 1997) and $\epsilon$-geometry (Fortune and Van Wyk, 1993). Thanks to this combination, TřiVis is characterized by reliable and predictable behavior, free from crashing or infinite looping, providing consistent outputs that align with user expectations, as supported by the results of our evaluation on exceptionally complex query instances. For more information, refer to the Performance Evaluation section.

Performance on Large Instances

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.

Building and Linking

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.

Basic Usage

Initialization

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.

Computing Visibility Queries

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.
}

Two-Point Visibility Query

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.
}

Ray-Shooting Query

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.
    }
}

Visibility Region Query

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.
}

Visible Vertices Query

if (plr.has_value()) {
    std::vector<int> visible_vertices = vis.VisibleVertices(query, plr.value(), range);
    // TODO: Do something with the visible vertices.
}

Visible Points Query

// 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.
}

Visibility Graphs

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.

Dependencies

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.

Repository Contents

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.

TřiVis Codebase

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+

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:

Boost, for filesystem operations, program options and logging.
Cairo, for 2D graphics rendering.

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.

Examples

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.

2-Point/Ray-Shooting Example

./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

Visibility Region Example

./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

Visible Vertices Example

./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

Visibility Graph Example

./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

Performance Evaluation

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.

Replication Guide (Performance Evaluation)

Building the Project

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.

Getting the Dataset

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.

Generating the Test Points

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

Constructing the Visibility Regions

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

Comparing the Results With the Reference Implementation (CGAL-TEA-CE)

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

Processing the Results

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.

Mesh Optimization

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.

Replication Guide (Mesh Optimization)

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.

Building the Project

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.

Getting the Dataset

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.

Running the Experiments

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.

Processing the Results

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.

Documentation

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.

License

Please see the LICENSE.md file for the license of TřiVis.

Name		Name	Last commit message	Last commit date
Latest commit History 57 Commits
conda		conda
data		data
examples		examples
mesh_optim		mesh_optim
performance		performance
trivis		trivis
trivis_plus		trivis_plus
.gitignore		.gitignore
CMakeLists.txt		CMakeLists.txt
LICENSE.md		LICENSE.md
README.md		README.md
build.bash		build.bash
setup.bash		setup.bash

License

janmikulacz/trivis

Folders and files

Latest commit

History

Repository files navigation

TřiVis

About

Table of Contents

Definitions

Main Features

Supported Queries

Worst-Case Query Complexity

Efficient Limited-Range Queries

Fast Point Location

Robustness and Reliability

Performance on Large Instances

Building and Linking

Basic Usage

Initialization

Computing Visibility Queries

Two-Point Visibility Query

Ray-Shooting Query

Visibility Region Query

Visible Vertices Query

Visible Points Query

Visibility Graphs

Dependencies

Repository Contents

TřiVis Codebase

TřiVis+

Examples

2-Point/Ray-Shooting Example

Visibility Region Example

Visible Vertices Example

Visibility Graph Example

Performance Evaluation

Replication Guide (Performance Evaluation)

Building the Project

Getting the Dataset

Generating the Test Points

Constructing the Visibility Regions

Comparing the Results With the Reference Implementation (CGAL-TEA-CE)

Processing the Results

Mesh Optimization

Replication Guide (Mesh Optimization)

Building the Project

Getting the Dataset

Running the Experiments

Processing the Results

Documentation

License

About

Resources

License

Stars

Watchers

Forks

Releases 6

Contributors 3

Languages