The software voxelize is a solver that uses interval arithmetic to enclose the solutions of a polynomial system with equalities and positive or negative inequalities.

The standalone version writes the solutions in a file that can be visualize with a 3D software such as meshlab or paraview. Section Standalone example shows step by step how to use voxelize to enclose a 3D circle from two equalities.

The python version pyvoxelize returns the solution boxes as a python array that can be further processed within a python script. Section Python example shows step by step how to use pyvoxelize on a simple example.

Installation

Standalone

The standalone software depends on openmp for multithreading, and optionally on the library quadmath for 128-bit precision floating points.

The standard installation is:

make

Then you can move the executable in a directory in your path, such as /usr/local/bin for example:

sudo mv voxelize /usr/local/bin

For float128 support

make voxelize_float128
sudo mv voxelize_float128 /usr/local/bin

For more compact memory usage

make voxelize_compact
sudo mv voxelize_compact /usr/local/bin

Python

The package pyvoxelize is a Python 3 interface to voxelize and can be installed with:

pip install git+https://gitlab.inria.fr/gmoro/voxelize.git

or after cloning this repository with:

sudo python setup.py install

Usage

voxelize [-d depth] [-s signs] [-p precision] [-l lower corner]\n",
         [-u upper corner] [-c depth] [-g grid size] [-a axes]\n",
         [-o output file] [-b basename] [-0] [-1] [-2] [-3] \n",
         [-r depth] [-i scale] [-v level] filename1 filename2 ...\n",

Given a list of polynomials and a list of signs, this command output a
file of format ply encoding the solutions of the corresponding system.

   -s signs:        comma separated list of values -1, 0 or 1 representing
                    the sign (-1, 0 or 1) for each polynomial file; if the
                    number of signs is less than the number of files, the
                    last sign is associated to the remaining polynomials
                    (default: 0)
   -p precision:    the precision of the intermediate computations
                    either 32, 64, 80 or 128
                    (default: 64)
   -i scale:        inflation as a double; the scale at which boxes are 
                    inflated when checking for zeroes
                    (default: 1.0)
   -l lower corner: the coordinates of the lower corner of the view box
                    as a comma separated list of floating points; if the
                    number of values is less than the number of variables,
                    the last value is used for the remaining coordinates
                    (default: -2)
   -l lower corner: the coordinates of the upper corner of the view box
                    as a comma separated list of floating points; if the
                    number of values is less than the number of variables,
                    the last value is used for the remaining coordinates
                    (default: 2)
   -g grid size:    comma separated list of integers; the initial view box
                    is uniformly divided in each direction according to
                    the corresponding number in grid size; if the number
                    of values is less than the number of variables, the
                    last value is used for the remaining coordinates
                    (default: 1)
   -a axes:         comma separated list of integers; the indices of the
                    variables to visualize; if the number of values is
                    greater than the number of variables, the first three
                    indices of variables are kept
                    (default: 1,2,3)
   -d depth:        integer for the minimal depth of the subdivision tree;
                    until the value d, all the boxes are subdivided
                    (default: 7)
   -c depth:        integer for a depth in the subdivision tree; until the
                    value depth, on each box the polynomials are evaluated
                    after being recentered
                    (default: 0)
   -r depth:        integer for the maximal depth in the subdivision tree;
                    the boxes at a depth greater or equal to d and less
                    than r are subdivided only if they are not guaranteed
                    to contain a solution of the input system
                    (default: 0)
   -n bool:         specifies that the output file will contain a points
                    cloud with normals instead of a set of cubes
                    (default: false)
   -m               specifies that the output file will contain a mesh
                    with normals instead of a set of cubes
                    (default: false)
   -t               when the option -n is active, the option -t specifies
                    that centers of boxes not contracting are removed
                    (default: false)
   -0
   -1
   -2:              selects the order of the expansion for the evaluation:
                    0 is direct, 1 is linear and 2 is quadratic
                    (default: 2)
   -v verbose:      integer 0, 1 or 2 for the level of verbose
                    (default: 0)

Polynomial file representation

The directory polys contains several example of polynomial files. A polynomial file is a text file with the extension .poly that contains a monomial per line. A monomial line is a space separated list of number of the form : c n1 n2 n3 ...

The first number c represents the coefficient of the monomial and the following numbers are integers that represent the exponent of the variables in the monomial.

Example of the equation of the sphere in a .poly file:

 1 2 0 0
 1 0 2 0
 1 0 0 2
-1 0 0 0

Creating polynomial files from standard text representation

A file of type .poly can be produced by the python parser to_poly in the utils directory. This script takes as input a file where the first line contains the list of variables separated by a comma. The rest of the file contains a polynomial in expanded form, or several polynomials separated by blank lines or semicolons. The script will create one or several files starting with the same basename as the input file.

Standalone example

Assume that we want to find boxes enclosing the half sphere given by the following system:

\left\{\begin{aligned} x^2+y^2+z^2 - 1 &= 0\\
                         y-x > 0
         \end{aligned}\right.

First write the following file my_polynomials.txt:

x, y, z

x^2 + y^2 + z^2 - 1

y-x

Then generate the .poly files using the parser to_poly

./to_poly my_polynomials.txt

This will create the two files my_polynomials_1.poly and my_polynomials_2.poly. It is now possible to use the command voxelize to compute enclosing boxes.

voxelize -s0,1 -o half_sphere.ply my_polynomials_1.poly my_polynomials_2.poly

Finally the half sphere can by visualized with meshlab for example.

meshlab half_sphere.ply

Python example

TODO

More example

The voxelize command produces a file of type ply. This type of file can be viewed with meshlab or paraview for example. For surfaces computed with the option -n, the software meshlab can compute a mesh using for examples the filters "Surface Reconstruction: Ball Pivoting" followed by "Laplacian Smooth".

Note that on mac, the names of the files must be after the options.

The following example are available in the directory polys of the repository.

• Plotting a sphere.

  voxelize -l-2 -u2 -d7 -m -o /tmp/test.ply sphere.poly 

• A generic polynomial of degree 30, with all boxes guaranteed to contain a zero.

  voxelize -2 -d7 -r15 -v1 -l-2 -u2 -o /tmp/test.ply random_3D_30_1.poly

• A generic 3D curve of degree 900.

  voxelize -l-2 -u2 -d11 -v1 -o /tmp/test.ply random_3D_30_1.poly random_3D_30_2.poly

• A curve and a surface from control theory. These take a couple of minutes.

  voxelize_float128 -l0 -u10 -2 -g10,1 -c1 -d9 -r16 -o /tmp/test.ply -v1 alban_curve.poly
  voxelize_float128 -l0,0.5 -u0.1,1.5 -2 -g1,5 -c3 -d6 -o /tmp/test.ply -v1 alban.poly
  
  voxelize_float128 poly_rho_0_1.poly -v1 -l-0.1,3 -u0.7,10 -d9 -r20 -o /tmp/test.ply -c3
  voxelize_float128 Polynome_Lambda_Gr_rho_3.poly -v1 -l0,-0.1,3 -u1,0.7,10 -c4 -d9 -o /tmp/test.ply -n

• A surface from a robotic 3-RPR mecanism, rendered with boxes, points cloud and a mesh respectively. Note the handle of the Whitney umbrella that is refined.

  voxelize -c1 -2 -d5 -r8 -l0 -u5,50 -g1,10 -o /tmp/test.ply -v1 3rpr_surface.poly
  voxelize -c1 -2 -d7 -r8 -l0 -u5,50 -g1,10 -o /tmp/test.ply -v1 3rpr_surface.poly -n
  voxelize -c1 -2 -d7 -r8 -l0 -u5,50 -g1,10 -o /tmp/test.ply -v1 3rpr_surface.poly -m

• A surface defined by 2 polynomial equations in 4 variables.

  voxelize -2 -d8 -v1 -l-10 -u10 -o /tmp/test.ply marc_1.poly marc_2.poly
  voxelize -2 -d9 -v1 -l-10 -u10 -n -o /tmp/test.ply marc_1.poly marc_2.poly

• A surface of degree 13 and its silhouette with two different representations

  voxelize random_3D_13.poly -l-2 -u2 -d10 -v1 -o /tmp/test.ply -n
  
  voxelize derivative_z.poly random_3D_13.poly -l-2 -u2 -d12 -v1 -o /tmp/test.ply
  
  voxelize discriminant_13.poly -l-1 -u1 -c5 -d12 -v1 -o /tmp/test.ply
  voxelize discriminant_13.poly -l-2 -u2 -c4 -d12 -r20 -v1 -o /tmp/test.ply