dhaumont / visilib Goto Github PK

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:

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.