INSTALL

# SGAL project

1. Introduction

The Scene Graph Algorithms Library (SGAL) is a toolkit that supports the
construction and maintenance of directed acyclic graphs that represent
scenes and models in three-dimensional space. The toolkit consists of
two libraries, namely SGAL and SCGAL, and an application, called player,
which enables users to visualize the scene in an interactive manner. The
player parses input files that describe the scene in a degenerate yet
extended VRML format. The format is degenerate, as not all VRML features
are supported (yet). However, it has been extended to support several
new features. For example, it has been extended with several geometry
node types, such as the Assembly node type, which represents assemblies
or subassemblies; the AssemblyPart node type, which represents parts of
assemblies; the SphericalGaussianMap node type, which represents
(spherical) Gaussian maps of convex polytopes in 3D, and the
ArrangementOnSphere, which represents arrangements of geodesic arcs
embedded on the sphere. The extended format also supports, for example, a
node type called ExactCoordinate, which represents exact coordinates, and
enables the provision of exact rational coordinates as input. Each node
object of the three types AssemblyPart, SphericalGaussianMap, and
ArrangementOnSphere internally maintains the CGAL data structure that
represents an arrangement of geodesic arcs embedded on the sphere.

2. Installing

The code is cross-platform. Building and executing is supported on Windows
using MSVC and Unix-like systems using GNU tools. It is not supported on
Mac OS (yet).

Ideally, building SGAL amounts to:

  cd sgal                                     # go to SGAL directory
  cmake .                                     # configure SGAL
  make                                        # build the SGAL libraries

2.1. Prerequisites

Installing SGAL requires a few components to be installed apriori: a
supported compiler (see Section 2.3.), bison (see Section 2.5.2),
flex, Boost, gl2ps, Magick++, V8, freetype, GMP, MPFR, Eigen3, and CGAL;
see Section 2.5. for more details on essential third party software.

2.2. Downloading
You can obtain the most up-to-date sources from the git repository
at https://bitbucket.org/.

You need to register and obtain a user account. You also need to add an
ssh key for every machine you would like to access the repository from
via the clone command below.

  git clone git@bitbucket.org:efifogel/sgal.git

If you are on Windows you may not download and run SGAL-1.0-Setup.exe, as
such an installer does not exist (yet).

Directory Content
--------- -------
bison     a submodule for the bison sources; see Section 2.5.2.
data      data files
docs      documents
figs      figures
make      makefile files
src       source files

2.3. Supported Compilers
In order to build the SGAL libraries and the executables, you need a
C++ compiler. SGAL 1.0 is supported for the following combinations of
compilers and operating systems:

Compiler                      | Operating System
------------------------------|-------------------------------------
GNU g++ 4.2 or later          | Linux
MS Visual C++ 10, 11          | MS Windows 95/98/2000/XP/NT4/Vista/7

2.4. SGAL Libraries
SGAL is split into two libraries, namely SGAL and SCGAL. Both libraries
depend on CGAL (Computational Geometry Algorithm Library), However, SGAL
use limited arithmetic precision, while SCGAL uses unlimited precision.

2.5. Essential Third Party Libraries
The focus of SGAL is on scene graph handling. It relies on other highly
specialized libraries and software for other tasks. When an external
library is used and the external library is not installed in a standard
place (e.g.,, /usr/[local/]include and /usr/[local/]lib in Linux), the
directories where the header source files and the library object files
reside must be specified. On Windows, for example, there is no canonical
directory for where to find external libraries.

In addition to the header source and library object files, the shared
library object files (.so on Linux and .dll on Windows) must be made
accessible to the loader. On Windows, this implies that the shared
libraries must be placed in a directory that is in the PATH. On linux,
this can be done by placing the shared libraries is a directory that
is in the LD_LIBRARY_PATH.

2.5.1. List of required packages.

2.5.1.1. Required packages of Ubuntu 14.04:
* libboost-all-dev
* libmagick++-dev
* libgmp-dev
* libmpfr-dev (Currently, a special version of this linrary must be used; see Section 2.5.4. V8 for details.)
* libv8-dev
* libfreetype6-dev
* bison, YACC-compatible parser generator >= 2.7.91
* libeigen3-dev

2.5.1.2. Required items on Windows
* Boost
* ImageMagick
* gl2ps
* GMP
* MPFR
* V8
* Eigen3
* freetype
* flex (cygwin)
* bison (cygwin)

2.5.1.3. Required items on Mint 17
* cmake
* flex
* bison
* libcgal-dev
* flex
* libgl1-mesa-dev
* libglu1-mesa-dev
* libmagick++-dev
* libgmp-dev
* v8-dev

In fact, I needed more packages from cygwin to build bison (see
Section 2.5.2.1.) , but I hope that this is temporary.

2.5.1. Boost
Boost is a set of portable C++ source libraries. Most Boost libraries
are library-less (headers only), but a few of them need to be compiled
into binaries or installed.

SGAL requires Boost version 1.39 or higher. In particular, the header
files and the Boost.Thread, Boost.System, and Boost.Program_options
binaries.

On Windows, as auto-linking is used, you also need the binaries of
Boost.Serialization and Boost.DateTime, but the dependency is artificial
and used only at link-time: the SGAL libraries do not depend on the
DLL's of those two libraries.

If Boost is not installed on your system already, you can obtain it from
http://www.boost.org/. For Windows an installer from precompiled libraries
is not available. (For old versions an installed can be obtained at
http://www.boostpro.com/download/.) However, the procedure is faily easy:

  ./bootstrap
  ./b2 link=static,shared threading=single,multi variant=debug,release

If you build for a 64 bit target architecture use:
  ./b2 link=static,shared threading=single,multi variant=debug,release address-model=64

2.5.2. bison and flex

2.5.2.1. bison
Bison is a general-purpose parser generator that converts an annotated
context-free grammar into a deterministic LR or generalized LR (GLR)
parser employing LALR(1) parser tables. For more information see
http://www.gnu.org/software/bison/

The code of SGAL is using an advanced feature of bison available in
bison version 2.7.91 and above. Ubuntu versions 14.04 an above include
Bison version 3.0 or above. However, the binaries of the required bison
release has not made it yet to the other standard distrubution channels
(e.g., Red Hat, cygwin, and bison for Windows). Thus, it must be built
from sources on the corresponding platform. A bison submodule exists in
the SGAL git repository for convenience. To build bison you need to
install apriori the components listed in the table below. The table lists
the cygwin packages that contain the components.

  Component  Category Package
  ---------- -------- -------
  gcc        Devel    gcc
  autopoint  Devel    gettext-devel
  make       Devel    make
  automake   Devel    automake
  autoconf   Devel    autoconf
  texinfo    Text     texinfo
  pkg-config Devel    pkg-config
  rsync      Net      rsync

This holds for Linux as well as for Windows, assuming you are going to
build bison via cygwin. First you need to update the bison sources.
Assuming you are in the main SGAL directory, issue the following command:

  git submodule update

The command above will populate the files in the bison submodule; see
Section 2.5.2.

If, for some reason, you want the latest bison sources, issue the
following command:

  git submodule -q foreach git pull -q origin master

To obtain the latest version of bison from its git repository
(using anonymus checkout) issue:

  git clone git://git.savannah.gnu.org/bison.git

Then, change directory to the bison directory. Typically, building
bison, ammounts to:

  ./bootstrap
  ./configure
  make

Then, place the generated bison executable (src/bison[.exe]) somewhere
in your PATH, so that it is picked up before any other bison executable
that may reside on your system. I place it under $ROOT/bin, which is in
my PATH; see Section 2.6.1. for a discusion about environment variables.

On Windows, you can build an executable using GNU tools from a cygwin
bash terminal. Unfortunately, bootstrap fails, but I found a workaround.
The issue is described at
http://stackoverflow.com/questions/17143607/i-cannot-build-bison-on-cygwin-using-bootstrap/17157991?noredirect=1#17157991. In short,

Edit the file bootstrap.conf and search for the statement:

  gnulib_tool_option_extras='--symlink --makefile-name=gnulib.mk'

remove the '--symlink' option. Then, run the bootstrap script while forcing
(hard) copies over symbolic links and proceed as above:

  ./bootstrap --copy
  ./configure
  make

Finally, bison requires m4 among the others. If you build bison via
cygwin, you need to set the environment variable BISON_PKGDATADIR to
point to the bison data directory (otherwise m4sugar/m4sugar.m4 is not
found) before running cmake:

export BISON_PKGDATADIR=${BISON}/data

2.5.2.2. flex (Fast Lexical Analyzer)
Flex is a fast lexical analyser generator. It is a tool for generating
programs that perform pattern-matching on text. Flex is a free (but
non-GNU) implementation of the original Unix lex program. To download
the software, get the documentation, and more, see the Flex home
page at http://flex.sourceforge.net/.

2.5.3. Magick++ (ImageMagick)
ImageMagick® is a software suite to create, edit, compose, or convert
bitmap images; see http://www.imagemagick.org/

2.5.4. V8
V8 is Google's open source JavaScript engine. Ubuntu distribution
includes a development package. However, the code of SGAL is using a
recent API, which is different than the API of the precompiled library
object included in the standard distribution. Thus, you need to build
v8 of a certain version from sources both in Linux and in Windows. You
need to obtain the sources; then, build the engine.

You must install python before you start the build, as the build tool uses
python.

2.5.4.1. Linux

ubuntu:14.04, for example, comes with V8 engine version 3.14.5.8. This
version is too old. The default version that comes with ubuntu:16.04 is
also too old. V8 resides in a git repository and there is no easy way
to build from a tarball. However, there is a ppa that contains an appropriate
version.

2.5.4.1.1. PPA

  1. Enable access to the ppa & install it.
  sudo add-apt-repository ppa:pinepain/libv8
  sudo apt-get update && sudo apt-get upgrade
  sudo apt-get install -y libv8-6.6 libv8-6.6-dev

  2. Export the include and lib directories
  export V8_INC_DIR=/opt/libv8-6.6/include
  export V8_LIB_DIR=/opt/libv8-6.6/lib

2.5.4.1.2. From sources
To obtain v8 and build,
  1. Clone the depot tools:
  git clone https://chromium.googlesource.com/chromium/tools/depot_tools.git

  2. Add depot_tools to your PATH, e.g.,:
  export PATH=`pwd`/depot_tools:"$PATH"

  3. Fetch, checkout the latest stable version, and build
  export V8_BUILD_DIR=<build-directory>
  cd $V8_BUILD_DIR
  fetch v8
  cd v8
  git checkout -b 6.6 -t branch-heads/6.6
  gclient sync
  gn gen out.gn/x64.release --args='is_debug=false target_cpu="x64" is_component_build=true v8_use_external_startup_data=false'
  ninja -C out.gn/x64.release

  4. Export the include and lib directories
  export V8_INC_DIR=$V8_BUILD_DIR/v8/include
  export V8_LIB_DIR=$V8_BUILD_DIR/v8/out.gn/x64.release

2.5.4.1. Windows
  svn co http://gyp.googlecode.com/svn/trunk build/gyp
  svn co https://src.chromium.org/chrome/trunk/deps/third_party/cygwin@231940 third_party/cygwin
  svn co https://src.chromium.org/chrome/trunk/deps/third_party/icu46 third_party/icu
  build/gyp_v8 -Dtarget_arch=ia32 -Dcomponent=shared_library
    or
  build/gyp_v8 -Dtarget_arch=x64 -Dcomponent=shared_library

  # The following 2 command are a required workaround!
  unset TEMP
  unset TMP

  # Assuming you are using vc10:
  /cygdrive/c/Program\ Files\ \(x86\)/Microsoft\ Visual\ Studio\ 10.0/Common7/IDE/devenv.com /build Release build/all.sln

2.5.5. freetype

FreeType is a freely available software library to render fonts.

2.5.5.1. Windows

Currently, the CMake find module for freetype on Windows is
broken. One workaroud is setting FREETYPE_INCLUDE_DIRS and
FREETYPE_LIBRARY explicitly when running cmake:

  -DFREETYPE_INCLUDE_DIRS="${FREETYPE_DIR}/include" \
  -DFREETYPE_LIBRARY="${FREETYPE_DIR}/lib/freetype.lib" \

where FREETYPE_DIR is the folder where freetype is installed under,
which is by default "C:/Program Files (x86)/GnuWin32"

2.5.6. CGAL
The Computational Geometry Algorithms Library (CGAL) is an open
source software library that provides industrial and academic users
with easy access to reliable implementations of efficient geometric
algorithms.

Ideally, building CGAL amounts to:

  cd CGAL-4.4                                 # go to CGAL directory
  cmake .                                     # configure CGAL
  make                                        # build the CGAL libraries

For more information see
http://www.cgal.org/Manual/latest/doc_html/installation_manual/contents.html

Many SGAL features supported by the SCGAL library of SGAL depend on the
latest release and on features developed in various branches. A feature
of SGAL can be (typically) enabled and disabled by setting an
appropriate environment variable. For example, consider the
"Lines Through Segments" feature. You need to set the environment
variable SGAL_USE_LTS to 1 to enable this feature, and enable the
corresponding CGAL feature. The corresponding CGAL feature has been
developed in the CGAL branch origin/Lines_through_segments-pmoeller.
You need to merge the source of this branch with the sources you use to
build CGAL. The sequence of commands bellow will merge all CGAL branches
used to develope relevant CGAL features.

  git checkout -b combined --no-track cgal/master
  git merge cgal-public-dev/Cubical_gaussian_map-efif
  git merge cgal-public-dev/Envelope_voronoi_2-ophirset
  git merge cgal-public-dev/Lines_through_segments-pmoeller
  git merge cgal-public-dev/Aos_2-sgm-efif
  git merge cgal-public-dev/Aos_2-flatgeodesics_on_torus-tau

2.5.7. GMP and MPFR
The SGAL library SCGAL requires CGAL with unlimited precision, and
CGAL with unlimited precision in turn requires GMP and MPFR, which are
libraries for multi precision integers and rational numbers, and for
multi precision floating point numbers.

CGAL combines floating point arithmetic with exact arithmetic, in order
to be efficient and reliable. Cgal has a built-in number type for that,
but GMP and MPFR provide a faster solution, and we recommend to use them.

Having GMP version 4.2 or higher and MPFR version 2.2.1 or higher installed
is recommended. These libraries can be obtained from http://gmplib.org/ and
http://www.mpfr.org/, respectively.

As Visual C++ is not properly supported by the GMP and MPFR projects,
CGAL provides precompiled versions of GMP and MPFR, which can be downloaded
with the installer of CGAL-4.2-Setup.exe.

2.5.8. Eigen3
Eigen is a library for linear algebra: matrices, vectors, numerical solvers,
and related algorithms. It is optionaly required by CGAL and optionaly
required by SGAL. If not present, filling holes of a polyhedral surface is
not supported.

2.5.9. OpenGL
OpenGL (Open Graphics Library) provides an API for applications that produce
2D and 3D computer graphics. SGAL depends on OpenGL. There is no alternative.
That is, SGAL does not use Direct 3D (on Windows) or any other proprietary
API.

Typically, OpenGL is preinstalled on systems; if not, it can be downloaded
from http://www.opengl.org/.

2.5.10. gl2ps
GL2PS is a C library providing vector output for any OpenGL application.
For more information see http://www.geuz.org/gl2ps/.

2.5.11. Some X libraries (forgot the name)
This applies to Linux only. These libraries are not installed by default.
You will get an error message during link if they are not installed.

2.6. Building SGAL

Recall that the environment variable CGAL_DIR points at the directory
where CGAL is installed. The version of CGAL installed may combine
several features that are possibly developed in different branches.

Let FTR be an acronym of a feature. Set the corresponding Boolean flag
as an input argument to cmake to enable the feature. If the feature
requires a corresponding CGAL feature, you must also install an
appropriate version of CGAL that supports the corresponding CGAL
feature.

   SGAL_USE_V8=1    # For V8 Support.

   SGAL_USE_SCGAL=1 # CGAL
   SGAL_USE_NGM=1   # Nef Gaussian Map (CGAL)
   SGAL_USE_LTS=1   # Lines Through Segments
   SGAL_USE_AOS=1   # Arrangement On Surface
   SGAL_USE_VOS=1   # Voronoi On Sphere
   SGAL_USE_SGM=1   # Spherical Gaussian Map
   SGAL_USE_NEF=1   # Nef
   SGAL_USE_CGM=1   # Cubical Gaussian Map
   SGAL_USE_GMP=1   # Link with GMP & MPFR
   SGAL_USE_SSC=1   # Smallest stabbing cube

   SGAL_USE_LTS=1 requires origin/Lines_through_segments-pmoeller
   SGAL_USE_CGM=1 requires origin/Cubical_gaussian_map-efif
   SGAL_USE_VOS=1 requires remotes/origin/Envelope_voronoi_2-ophirset
   SGAL_USE_AOS=1 requires origin/Aos_2-remove_opt-efif

For example:
cmake -G"NMake Makefiles" \
  -DCMAKE_VERBOSE_MAKEFILE=ON \
  -DSGAL_USE_V8:BOOL=ON \
  -DSGAL_USE_SCGAL:BOOL=ON \
  -DSGAL_USE_NGM:BOOL=OFF \
  -DSGAL_USE_LTS:BOOL=OFF \
  -DSGAL_USE_AOS:BOOL=ON \
  -DSGAL_USE_VOS:BOOL=ON \
  -DSGAL_USE_SGM:BOOL=ON \
  -DSGAL_USE_NEF:BOOL=ON \
  -DSGAL_USE_CGM:BOOL=ON \
  -DSGAL_USE_SSC:BOOL=ON \
  ${SGAL_SOURCE_DIR}

2.7. Testing