Please submit an archive that contains all source files and documentation in a flat directory structure (that is, place all files in one directory); send the archive file via email to [email protected].

Place the model(s) under /vol/scratch/<your-account-name>/ in our net. app. and let me know that it is there. (You will need to create the sub-directory <your-account-name>.) You can access this directory via Samba (the Windows network system) as well.

Exercise 2.1.a

General

Your solution to exercise 2.1.a should consist of at least one source file, CMakeLists.txt (input to cmake), and a pdf file called compute_width_3d.pdf that describes the implemented algorithm.

Running cmake on the provided CMakeLists.txt followed by compilation and linkage should produce an executable called compute_width_3d

You must develop in C++ and you must use CGAL for this exercise.

You can develop on any platform, but the code must compile and run using g++ on Linux.

Contest

We will hold a contest between all the different programs (including ours) of exercises 2.1.a and 2.1.b. To this end you are also required to add to your code a timer that measures the execution time-consumption.

Use a Boost timer.

• Add the directive below at the top of your cpp source file:
  #include <boost/timer.hpp>
• Introduce a timer after reading the input files:
  boost::timer timer;
• At the end of the code that executes the algorithm (and before the start of the code that prints out the final result) measure the elapsed time:
  double secs = timer.elapsed();

Input & Output

The program compute_width_3d accepts one argument on the command line, namely, the name of the file that contains the description of the input polyhedron. The format of the input file should be either STL or VRML. (A file in the STL format has the .stl extension and a file in the VRML format has the .wrl extension.) The VRML format supports colors. (There are simple extensions to the STL format that support color, but in a very limited way.) The 3D Systems’ Projet 660 3D printer can be fed with files in the VRML format and 3D-print colorful objects. If you choose to use the STL format, you will have to find a way to convert from VRML to STL to complete Exercise 2. Otherwise, you can exploit the sources of the sample program called viewer provided below to parse files in the VRML format.

A rational number is given by a numerator and denominator separated by ‘/’ (e.g., 1/3), where the numerator and denominator are both unlimited integers.

The program should export the following lines of text to the standard output stream:

The square of the width of the polyhedron is <num>
The direction of the width vector is <x> <y> <z>
The execution time was <s>

where <num> is the square of the width of the polyhedron given as a rational number, <x> <y> and <z> are the (not-necessary) normalized coordinates of the direction of the outer normal of the supporting planes the distance between which defines the width, and <s> is the timer elapsed time in seconds as a decimal (floating point) number.

Use the following functions to export a rational number in the format specified above and a direction.

std::ostream& operator<<(std::ostream& os, const Kernel::FT& n)
{
  std::cout << n.exact();
  return os;
}

std::ostream& operator<<(std::ostream& os, const Kernel::Direction_3& d)
{
  std::cout << d.dx() << " " << d.dy() << " " << d.dz();
  return os;
}

An archive that contains convex polytopes in the VRML format, which can be used as input can be downloaded from here. (Run tar zxvf data.tar.gz to expand.) The results are listed here.

I will upload additional test cases, mainly of polytopes that are not necessarily convex, later on.

Viewer

This program is given a polyhedron as input, opens a window with a 3D-graphics context, and renders the polyhedron in it. It uses glut, the OpenGL Utility Toolkit, for the handling of the 3D-graphics context and window events. It accepts one argument on the command line, namely, the name of the file that contains the description of the input polyhedron in the VRML format. It parses the file using flex and bison, and constructs a data structure the type of which is an instance of the CGAL::Polyhedron_3 class template. The VRML format is a text file format. The program only looks for the keywords point and coordIndex. The former is followed by an array of points in 3D space, given by their x, y, and z Cartesian coordinates, that specify the geometric mapping of the vertices of a polyhedron. The latter is followed by a sequence of indices into the array mentioned above and -1 markers. A facet on the boundary of the polyhedron is given by a sequence of indices to the points on the facet boundary followed by the -1 (the end-of-facet marker). The input file must contain at least one occurrence of each of the two keywords mentioned above. If a keyword appears more than once, the last occurrence is respected. You really don’t need to be familiar with the entire VRML format. However, if you are interested, you can find a good specification here. The following is a specification of a tetrahedron in the VRML format.

#VRML V2.0 utf8
IndexedFaceSet {
  coord Coordinate { point[-1.0 -1.0  -.0, 0.0 -1.0 -1.3, -1.4 -0.2 -1.4, -1.5 -1.7 -1.5] }
  coordIndex[0,1,2,-1, 0,2,3,-1, 0,3,1,-1, 1,3,2,-1]
}

An archive that contains the sources can be found here.

Alternatively, you can clone a public git repository that contains all sources from GitHub using the following command:

git clone https://[email protected]/mytaucgl/viewer.git

The program depends on glut, flex, and bison; thus, you must install these components before you attempt to build the viewer program. The archive contains a CMakeLists.txt file, so if everything is installed properly, all you need to do is run cmake followed by make.

I don’t guarantee that the program parses all valid VRML files, and even if it parses a file successfully, it ignores most keywords. If you want to view a VRML file that contains rich content, use a VRML viewer, such as Cortona3D.

Gaussian Map

For this exercise you will need to construct a data structure that represents the Gaussian map (a.k.a., a normal diagram) of a closed polyhedron, referred to as a polytope. As I’ve mentioned in class, it is unofficially supported by CGAL, meaning that the code is there, but it is not documented.

Instances of the class templates CGAL::Arr_spherical_gaussian_map_3 and CGAL::Arr_polyhedral_sgm are types that can be used to represent a Gaussian map. The later derives from the former. An object of this type (an instance of CGAL::Arr_polyhedral_sgm) can be initialized from an object, the type of which is an instance of the CGAL::Polyhedron_3. The Gaussian map data structures, and in particular their initializers, require (i) that the input polytope is convex, (ii) that adjacent facets are not coplanar, and (iii) that the coefficients of the underlying planes of the facets of the input polytope have been computed. Thus, you need to compute the convex hull of the input polytope before you construct a Gaussian map data structure. The CGAL function that computes the convex hull of points in 3D space, namely CGAL::convex_hull_3(), results with an object, the type of which is an instance of the CGAL::Polyhedron_3. Therefore, I suggest that you use the type CGAL::Arr_polyhedral_sgm. Nevertheless, information about both Gaussian map class templates will be provided. The output of the function CGAL::convex_hull_3() results with a polyhedral surface that consists of triangles. Thus, after you compute the convex hull and before you construct a Gaussian map, you must merge coplanar facets of the convex polytope. Finally, before you construct the Gaussian map of a convex polytope you must compute the coefficients of the underlying planes of the facets.

Important

The code that handles Gaussian maps depends on an instance of the Arrangement_on_surface_2 class template that can be used to represent an arrangement of arcs of great circles (a.k.a. Geodesic arcs) embedded on the unit sphere. By default the sphere is parameterized as follows:

Φ = [-π,+π] x [-π/2,+π/2], φ(u,v) = (cos u cos v, sin u cos v, sin v)

where Φ is a rectangular area (referred to as the parameter space) that is mapped onto the sphere by the function φ(u,v).

The code in CGAL does not handle curves on the sphere, the pre-image of which lies on the boundary of the parameter space. We are currently working to eliminate this deficiency. In the meantime, simply add the following macro definition to your code:

#define CGAL_IDENTIFICATION_XY 2

For those of you who are curious, it alters the parametrization above to be:

Φ = [-π+α,+π+α] x [-π/2,+π/2], φ(u,v) = (cos u cos v, sin u cos v, sin v)

where α=arctan(7/11). With this change the probability that we hit an curve on the boundary of the parameter space are slim.

An example of using the class template CGAL::Arr_polyhedral_sgm follows:

#include <CGAL/Arr_spherical_gaussian_map_3/Arr_polyhedral_sgm.h>
#include <CGAL/Arr_spherical_gaussian_map_3/Arr_polyhedral_sgm_traits.h>
#include <CGAL/Arr_spherical_gaussian_map_3/Arr_polyhedral_sgm_polyhedron_3.h>

typedef CGAL::Arr_polyhedral_sgm_traits<Kernel>                         Gm_traits;
typedef CGAL::Arr_polyhedral_sgm<Gm_traits>                             Gm;
typedef Kernel                                                          Gm_polyhedron_traits;
typedef CGAL::Arr_polyhedral_sgm_polyhedron_3<Gm, Gm_polyhedron_traits> Gm_polyhedron;
typedef CGAL::Arr_polyhedral_sgm_initializer<Gm, Gm_polyhedron>         Gm_initializer;

  Gm gm;
  Gm_initializer gm_initializer(gm);
  gm_initializer(polyhedron);

once you have two objects of type Gm, say gm1 and gm2, you can compute their Minkowski sum as follows:

gm.minkowski_sum(gm1, gm2);

where gm is also an object of type Gm.

The (in) complete manual can be found here.

Exercise 2.1.b

Most of the instructions given for Exercise 2.1.a apply also for Exercise 2.1.b.

Name the program compute_approx_width_3d and provide a corresponding pdf file.

The program compute_width_approx_3d accepts two argument on the command line, namely, the name of the file that contains the description of the input polyhedron and a rational number ε > 0.

The program should export the following lines of text to the standard output stream:

The square of the approximate width of the polyhedron is <num>
The direction of the approximate width vector is <x> <y> <z>
The execution time was <s>

Exercise 2.1.c

Scaling, translating, or rotating a polyhedral object given in the VRML format simply amounts to editing the file and adding a Transform node with scale, translation, or rotation fields, respectively. For example:

#VRML V2.0 utf8
Transform {
  translation 1 2 3
  rotation 0 0 1 0.785 # 45 deg.
  scale 2.0 2.0 2.0
  children [
    Shape {
      appearance Appearance {
        material Material {}
      }
      geometry IndexedFaceSet {
        coord Coordinate { point[-1.0 -1.0  -.0, 0.0 -1.0 -1.3, -1.4 -0.2 -1.4, -1.5 -1.7 -1.5] }
        coordIndex[0,1,2,-1, 0,2,3,-1, 0,3,1,-1, 1,3,2,-1]
      }
    }
  ]
}

A rotation is specified by the axis of rotation followed by the rotation angle.

Consider the following Transform node:

Transform {
    center           C
    rotation         R
    scale            S
    scaleOrientation SR
    translation      T
    children         [...]
}

The transformations are applied in the following order (copy-pasted from the spec):

P' = T x C x R x SR x S x -SR x -TC x P  (P is a column vector)

Transform nodes can be nested. The above is equivalent to the following:

Transform { translation T
 Transform { translation C 
  Transform { rotation R
   Transform { rotation SR 
    Transform { scale S 
     Transform { rotation -SR 
      Transform { translation -C
              ... 
}}}}}}}

Your solution to Exercise 2.1.c should consist of one source file that accepts two arguments on the command line, namely, the name of the file that contains the description of the input polyhedron and a Boolean flag used to determine whether the width or an approximation of the width should be considered. A value of “true” indicates that an approximation of the width should be considered. The program reads the input polyhedron. Then, it computes either the width or an approximation of the width based on the given flag. Then, it computes the translation vector and rotation value, such that when the polyhedron is transformed accordingly, it will have minimal (or close-to-minimal) vertical span and its lowest point will be at z=0. If you want to prepare for Exercise 2.2, the same program can also compute the scale vector necessary to scale the polyhedron so that it will fit inside a cube of edge size 100mm. The precise format of the output is irrelevant, since you will have to run the program and then edit the file using the obtained results.

Exercise 2.2

Obtain a file in the VRML format that contains the description of the polyhedron you wish to 3D-print. If the programs developed per Exercise 2.1 read VRML files, directly apply the program from exercise 2.1.c on your model. If these programs read STL files, convert the VRML file to a file in the STL format first.

Installation and Assistance

You can obtain the latest CGAL public release from here.

The CGAL installation manual is available here.

Q&A

1. 1. Are there examples that use CGAL arrangement?
      • You have at least two options to obtain sources of example programs of the 2D Arrangement package.
        1. Obtain all the sources of CGAL from the public repository:

           git clone https://github.com/CGAL/cgal.git /path/to/cgal.git

        2. Obtain all examples of the CGAL Arrangements and Their Applications book from the Web page at:

           http://acg.cs.tau.ac.il/cgal-arrangement-book/source-code-data-and-miscellaneous-files

---

1. 1. Where do the unexpected vertices at direction (-11,7) come from and how should we handle them?
      • As mentioned above, the parameter space is a rectangular area mapped onto the sphere. The unexpected vertices at direction (-11,7) lie on the boundary of the parameter space. When a curve is inserted into an arrangement it is first split into x-monotone sub-curves. In case of an arrangement on a sphere mapped from a parameter space, where the left and right boundaries are identified, the notion of x-monotonicity is augmented: Here, we also split curves that cross this identified boundary. These unexpected vertices are artificial and should be ignored. Such an artificial vertex has degree exactly 2. Notice that real vertices may end up on the identification curve (with direction (-11,7), but their degree will be greater than 2.

---

1. 1. What about really large files?
      • I’ve updated the archive file. It now contains a file called icosahedron_6.wrl. I’ve also updated the results page.
        Make sure the stack size is at least 10Mbytes when attempting to run your solution on this file; see next item.

---

1. 1. My program requires a stack of size larger than the default, because of the recursive call Arr_polyhedral_sgm_initializer_visitor::process_vertex. Is this normal?
      • Yes, it is expected. You need to increase the stack size. On Linux the stack size is controlled by an env. var.The command:

        ulimit -a

        spits out some information including the stack size, which, as aforementioned is 8Mb on my machine by default.

        The command:

        ulimit -s 10240

        sets the stack size to 10Mb.

        The default stack size on my (Ubuntu) machine is 8Mb. This is sufficient for all example files except for icosahedron_6.wrl, which requires 10Mb. The default stack size on Windows platform is typically 1Mb, which is insufficient also for icosahedron_5.wrl.

        On windows the stack size is stored in the executable and can be set during compilation; see, e.g., here.

---

1. 1. Compilation with some recent MSVC compilers (e.g., VC 2013 and VC 2014)  fails at Arr_geodesic_arc_on_sphere_traits_2.h line 2939.
      • Until the sources of CGAL are fixed, apply the following patch:

        diff --git a/Arrangement_on_surface_2/include/CGAL/Arr_geodesic_arc_on_sphere_traits_2.h 
        b/Arrangement_on_surface_2/include/CGAL/Arr_geodesic_arc_on_sphere_traits_2.h
        index 9a750fa..24b4e3f 100644
        --- a/Arrangement_on_surface_2/include/CGAL/Arr_geodesic_arc_on_sphere_traits_2.h
        +++ b/Arrangement_on_surface_2/include/CGAL/Arr_geodesic_arc_on_sphere_traits_2.h
        @@ -2936,7 +2936,7 @@ public:
             CGAL_precondition(!kernel.equal_3_object()(source, target));
             CGAL_precondition(!kernel.equal_3_object()
                               (kernel.construct_opposite_direction_3_object()(source),
        -                       target));
        +                       static_cast<const Direction_3&>(target)));
             this->m_normal = this->construct_normal_3(source, target);
         
             // Check whether one of the endpoints coincides with a pole: */
        

---

1. 1. What do we need to provide as output for Exercise 2.1.b
      • The approximation algorithm shown in class computes an approximate width, but does not provide the direction this width is obtained at. Thus, it is sufficient that your program reports only the approximate width. In any case, the reported approximate width must not be larger then (1+ε) times the real width.
      • Other approaches do compute an approximate width and the corresponding direction.
      • The contest will include two parts: In the first you are asked to provide only an approximate width. In the second you are asked to provide an approximate width and the corresponding direction. If you solve exercise 2.1.b in a way that does not provide the direction, or if you simply prefer, you can submit to the contest your solution to exercise 2.1.a for both parts.

---

1. 1. I would like to apply point location on a Gaussian map, but the code does not compile.
      • The 2D Arrangement package supports four strategies implemented by respective four templates:
        1. Arr_naive_point_location<Arrangement>
        2. Arr_landmarks_point_location<Arrangement,Generator>
        3. Arr_trapezoid_ric_point_location<Arrangement>
        4. Arr_walk_along_line_point_location<Arrangement>

        Indeed, not all the four strategies can be used with a Gaussian map yet. The naive strategy is guaranteed to work though.

      • For those interested, to be precise,  the strategies that cannot be used with a Gaussian map, are not yet supported on arrangements of type Arrangement_on_surface_2<Traits, Arr_spherical_topology_traits_2<Traits, Dcel> >

      ---

   2. Running the viewer on my VRML file results with the following error message

      Syntax error on line 2 token

      • Your text file probably has “dos” endings. To rectify, run

        dos2unix <filename>

      • To find whether a file has a “dos” ending, run, for example

        grep -U $'\015'  <filename>

        if nothing is provided as output, the file does not have “dos” endings.

---

1. Running the viewer on my VRML file results with the following error message

   Syntax error on line 1 token #

   • Your VRML file is of version 1.0. You need to convert it to VRML 2.0 (a.k.a. VRML 97).