The Visilib project aims to provide an efficient and robust library for exact visibility computation in 3D.
Given a set of polygonal geometries that are treated as occluders, the library allows to determine if two primitives called sources are mutually visible. In case of mutual visibility, Visilib optionally computes the set of lines stabbing the two primitives, providing a complete description of the mutual visibility information.
The from-region visibility computations are computed in an exact way, without making any simplification.
The core algorithm is based on CSG (Constructive Solid Geometry) operations in a 5D projective space called Pücker space. If you are interested in implementation detail please refer to this technical paper describing the core algorithm. However, since this publication the library has been completely rewritten and benefits from several improvements (see Features).
Visilib is written in C++, it is cross-platform and distributed as a header only library.
- From-region visibility computations are exact: contrary to conservative or aggressive visibility methods, the Visilib library does not make any assumption and performs the complete penumbra fusion of the occluders
- Visibility performed via CSG (Constructive Solid Geometry) operations in Plücker space:
- Polytope splitting algorithm using only skeleton of polytopes (vertices and edges)
- Silhouette optimization algortihm reducing drastically the number of CSG operations
- Guided aperture sampling and early termination: rays are casted in the visibility apertures left by the previously processed occluders, leading to early termination in case of mutual visibility
- Occluder selection using already computed visibility information
- Computational geometry predicates in Plücker space
NEW (since paper publication)
- The source primitives that can be used are polygons, segments and points, allowing to perform polygon-to-polygon, polygon-to-segment, polygon-to-point, and point-to-segment visibility query
- Optimal minimum polytope building algorithm in Plucker space (as described in Charneau et al.),
- Robust arithmetic computation based on CGAL and Leda libraries (multiple precision arithmetic combined with interval arithmetic computations)
- Fast ray tracing based on Intel Embree library
- Easy to deploy: header-only library
- Filtering of small polytopes (next release)
- Early stop or complete skeleton extraction
- Watertight ray-triangle intersection
- Pre-filtering of useless CGS splits
- Output sensitive occluder selection using optimized convex hull construction
- Lazy on-demand computation of occluders of silhouettes
- Representative line sampling computation correction
- Potentially Visible Set computation (PVS)
- Sound propagation (edge diffraction)
- Shadow and lighting computation
The only mandatory dependency is CMake used for cross-platform compilation.
The following dependencies are optional:
- CGAL and Leda and Boost for optional exact arithmetic support
- Intel Embree, for optional fast ray-tracing support
- freeglut and OpenGl for the interactive demo application
We also use Doxygen for documentation generation.
Visilib is partially unit tested, using the CMake framework. The implementation of the unit test is provided in the /test/src/ folder. The name of executable to run the unit tests is visilibTest.
- Summary of set up
LINUX
#install required dependency
sudo apt-get install freeglut3-dev
sudo apt-get install cmake
#clone repository
git clone https://github.com/dhaumont/visilib.git
#configure
cd visilib
source configure.sh
#build
cd build
make -j10
#Launch demo
demo/visilibDemo
WINDOWS
Visilib is GNU GPL v3 licensed.
If you use Visilib in a publication, please refer to the project homepage (https://github.com/dhaumont/visilib) and cite the following paper:
@inproceedings{
title = {A Low Dimensional Framework for Exact Polygon-to-Polygon Occlusion Queries},
author = {Denis Haumont and
Otso Makinen and
Shaun Nirenstein},
booktitle = {Proceedings of the Eurographics Symposium on Rendering Techniques,
Konstanz, Germany, June 29 - July 1, 2005},
pages = {211--222},
publisher = {Eurographics Association},
year = {2005}
}
visilibDemo is an interactive demo application provided with visilib library.
It allows to test the different library options interactively, by pressing the following keys:
| Key | Usage | Description |
|---|---|---|
| f | enable/disable detect aperture only | When activated, the visibility computation stops as soon as the two sources are proven to be mutually visible. Otherwise, the computation continues until the complete visibility information has been computed |
| s | enable/disable silhouette optimisation | When activated, only the potential silhouette edges of the occluders wrt the source polygons are considered for CSG operations |
| n | enable/disable hypersphere nomalization | When activated, all the Plücker points are projected onto an unit hypersphere, in order to reduce numerical errors |
| r | enable/disable representative line sampling strategy | |
| f | enable/disable fast silhouette rejection test | |
| + | increase source size | Increase the size of the source polygons |
| - | decrease source size | Decrease the size of the source polygons |
| 1 | decrease source vertex count | Decrease the number of vertices of the first source polygon |
| 2 | increase source vertex count | Increase the number of vertices of the first source polygon |
| w | write config | |
| o | open config | |
| space | start/pause sources animation | When animation is started, the source polygons will perform a rotation around the scene |
| Enter | show/hide geometry | For debugging purpose, allow to change the representation of the scene and of the query polygons |
| h | display help | Display the list of keys and their effect |
We would like to thanks the following persons for their contribution to this library:
- Otso Mäkinen for the silhouette computation implementation
- Shaun Nirenstein for all the technical discussions
- Eric Lengyel for the polygon clipping algorithm
- Joseph O'Rourke and Cédric Laugerotte for the convex hull implementation
- Sven Woop et al. for the watertight triangle intersection code
- Bajaj and Patucci for the interpolation algorithm code
- David Eberly for the AABB to ray intersection code
- Jiry Bittner for the Plücker point anchor computation
- Meshlab team for the obj reader code
We used several useful libraries and tools to implement Visilib (see Dependencies). We would like to especially thank their authors for their great work and publishing the code.
For any question about this library, please contact Denis Haumont.