Applied Geometric Computing, Spring 2000

0368.4073.0
Lecture: Monday 16:00–19:00, Schreiber 6

Instructor: Dan Halperin
Office hours: Wednesday, 16:00–17:00, Schreiber 114

Teaching Assistant: Eti Ezra, [email protected]

Assignments: instructions, program fragments, input files

The final assignment and oral exam [psz]

The course will cover geometric-computing techniques that are useful in solving problems in a variety of application domains including robotics, computer-aided design and manufacturing, GIS and more. The emphasis will be on practical solutions. Among the topics of the course: geometric arrangements and their applications; configuration space and robot motion planning; movable separability and assembly planning for multi-part objects. In addition we will address robustness issues in geometric software, data types for exact computing, and handling of degenerate input.

The course is geared towards graduate students in computer science. Third-year undergrads are welcome.

Prerequisites: software1, data structures, and a course on algorithms. Knowledge of C++ would help.
Having taken the course Computational Geometry is an advantage but not a requirement.

The final grade will be determined by: 80% homework assignments including one large-scale assignment, and 20% oral exam.

Bibliography

Course summary

  • 21.02.2000 Introduction
    • Motivating problems: object placement and compaction, robot motion planning, part orienting, mechanical assembly planning, visibility
    • From problems to solutions: formulating the problem in a convenient `configuration space’, combinatorial analysis, representation/data structures, algorithms, implementation
    • Example: aspects graphs of a convex polygon in parallel and perspective projections, the circle of directions, arrangements of lines
    • See references to books and surveys on arrangements in the course bibliography
  • 28.02.2000 Minkowski sums
    • Motivating problems: object placement, robot motion planning, tolerance and offset
    • The connection between motion planning and Minkowski sums
    • Minkowski sum of two convex polygons: properties and algorithm
    • Arrangements of segments, constraint curves, upper bound on the complexity of Minkowski sums of general polygonal sets
    • Minkowski sum of a convex and general polygon; to be continued
    • Most of the material is taken from the book by de Berg et al. (see the course bibliography ), Chapter 13

Assignment no. 1 [psz], due: March 20th, 2000

frame programs, example input files

  • 06.03.2000 Minkowski sums, cont’d
    • Minkowski sum of a convex \(m\)-gon and general \(n\)-gon: proof of the tight complexity bound \(O(mn)\) of the free space
    • Introduction to lower envelopes
    • background material for those who did not take the course computational geometry: representing 2D maps—DCEL and vertical decomposition, a quick review of the seep line algorithm for detecting the intersection of segments in the plane
    • Most of the material is taken from the book by de Berg et al. (see the course bibliography)
      The Minkowski sum bound appears in Chapter 13 in the book.
      The background material appears in Chapter 2
  • 09.03.2000 Talks on the CGAL project and library
    • Mariette Yvinec: Triangulations in CGAL
    • Stefan Schirra: Precision and Robustness in CGAL
    • Much material about CGAL can be found in our local CGAL web site which contains links to documentation and in particular to the CGAL getting started manual
    • The paper below surveys the CGAL activities at Tel Aviv University
      • Robust geometric computing in motion [psz]
    • For robustness and precision in geometric computing, see a recent comprehensive survey by Stefan Schirra which is available on-line in Schirra’s web site
  • 20.03.2000 Approximate swept volumes (given by Sigal Raab, 2 hours only)
    • Approximating swept volumes of polyhedral objects in 3-space; an algorithm by S.A. Abrams and P.K Allen, described in the paper
      • Swept volumes and their use in viewpoint computation in robot work-cells
        In Proceedings of the IEEE International Symposium on Assembly and Task Planning, 1995, pp. 188–193
    • More on precision and robustness problems
  • 27.03.2000 Lower envelopes, Motivation
    • The connection between lower envelopes and Voronoi diagrams
    • Davenport-Schinzel sequences
    • Algorithms for computing the lower envelope
    • Most of the material is taken from the book by Sharir and Agarwal (see the course bibliography), Chapter 1. The connection between lower envelopes and Voronoi diagrams is discussed in Appendix 7.1 in the book

Assignment no. 2 [psz], due: May 1st, 2000

frame programs, example input files

  • 03.04.2000 Lower envelopes, cont’d, Molecular surfaces I
    • An improved algorithm for computing the lower envelope (Hershberger); the algorithm is described in the book by Sharir and Agarwal (see the courses bibliography), Section 6.2.2
    • Introduction to 3D arrangements
    • The complexity of arrangements of planes and of spheres
    • The complexity of the union boundary of a collection of spheres
    • “Fatness”, the favorable setting of spheres in the hard sphere model of a molecule
    • Efficient intersection structure for molecules
    • The material related to spheres and molecules can be found in the paper:
      • Spheres, molecules, and hidden surface removal [psz]
        D. Halperin and M.H. Overmars
        Computational Geometry: Theory and Applications 11 (2), 1998, 83–102
  • 10.04.2000 Molecular surfaces II
    • The different molecular surfaces: van der Waals, Lee and Richards’s solvent accessible surface, Richard’s “smooth” molecular surface
    • Computing molecular surfaces (the boundary of the union of balls/spheres)
    • Alpha-hulls and molecular surfaces
    • Approaches to handling degeneracies in arrangements
    • Controlled perturbation of arrangement of spheres (introduction)
    • The material is covered in two papers:
      • Spheres, molecules, and hidden surface removal [psz]
        D. Halperin and M.H. Overmars, Computational Geometry: Theory and Applications 11 (2), 1998, 83–102
      • A perturbation scheme for spherical arrangements with application to molecular modeling (MIT AI MEMO)
        D. Halperin and C.R. Shelton
        The full version [psz]

Assignment no. 3 [psz], due: May 29th, 2000

frame programs, example input files

  • 01.05.2000 Controlled perturbation, Compact representation of the invariants of an arrangement
    • Controlled perturbation of arrangements of spheres
    • The material is in the paper:
      • A perturbation scheme for spherical arrangements with application to molecular modeling (MIT AI MEMO)
        D. Halperin and C.R. Shelton
        The full version [psz]
    • Compact representation of the invariants of an arrangement. Example 1: compactly storing all the maps in the aspect graph of a set of convex polygons in the plane under orthogonal projection in the plane
    • Compact representation of the invariants of an arrangement
  • 08.05.2000  Aspect graphs in 3D
    • The aspect graph of a polyhedral scene under orthographic projection
    • Computing the lower envelope of a set of non-intersecting triangles in 3-space: divide-and-conquer, `arrangement’ algorithm (projecting all the triangles onto the \(xy\)-plane and computing the envelope over each face)
    • Compactly representing all the maps in the aspect graph. See
      • Efficiently computing and representing aspect graphs of polyhedral objects
        Z. Gigus, J. Canny and R. Seidel, IEEE Trans. Pattern Anal. Mach. Intell. , Vol. 13. no. 6 (1991), 542–551
    • (Yet another) introduction to 3D arrangements
  • 15.05.2000 Arrangements of triangles in 3D
    • The complexity of such arrangements
    • Vertical decomposition of arrangement of triangles: what it is, how complex it is and how to construct it in an output-sensitive manner
    • All the material covered in class appears in the paper:
      • Vertical decompositions for triangles in 3-space [pgz]
        M. de Berg, L.J. Guibas and D. Halperin, Discrete and Computational Geometry, 15 (1996), 36–61
  • 22.05.2000 Arrangements of well-behaved surfaces in 3D, The area bisectors of a polygon
    • Arrangements of well-behaved surfaces in 3D
    • The compelxity and output-sensitive computation of the vertical decomposition of such arrangements
    • Navigating the arrangement through non-vertical faces
    • The material covered in class appears in the later sections of the paper:
      • Vertical decompositions for triangles in 3-space [psz]
        M. de Berg, L.J. Guibas and D. Halperin, Discrete and Computational Geometry, 15 (1996), 3–61
    • The area bisectors of a polygon: introduction
    • The material appears in the the paper:
      • On the area bisectors of a polygon [psz]
        K.F. Böhringer, B.R. Donald and D. Halperin, Discrete and Computational Geometry, 22 (1999), 269–285

Assignment no. 4 [psz], due: June 12th, 2000 (in Eti Ezra’s mailbox)

frame programs, example input files

  • 29.05.2000 The area bisectors of a polygon
    • Properties of area bisectors, combinatorial bounds, output-sensitive algorithm
    • The material appears in the the paper:
      • On the area bisectors of a polygon [psz]
        K.F. Böhringer, B.R. Donald and D. Halperin, Discrete and Computational Geometry, 22 (1999), 269–285

The Final Assignment [psz], due: August 14th, 2000

Installing CGAL and related programs on Windows operating system

This page explains how to install CGAL 4.9 with Boost 1.59.0 and Qt5 5.7.1 on Windows 8 using Visual Studio 12 (2013) generating 64 bit binaries. The same procedure should apply to earlier versions of Windows.

Note that during the entire setup you need Internet connection!

Note that the installation requires significant disk space. Make sure to free enough disk space before the installation.

Instructions on adding Environment Variables in Windows are at the end.

DOWNLOADS:

IMPORTANT: make sure that you install everything in 64-bit.

  1. Visual Studio 12 Professional (recommended) or Express.
    Professional – Students can get a free version here
  2. Boost 1.59.0: here
  3. CMake 3.7.1
  4. CGAL 4.9.0
  5. Qt5 5.7.1
INSTALLATION:
In parentheses are the paths on my computer.
1) Visual C++ 2013:
  •  If you use the offline version, choose to install Visual C++.
  •  Accept the license terms.
  •  You may select a custom installation (instead of full) and select only Visual C++ (unselect other features).
  •  You don’t need to install “SQL Server” & “Silverlight Runtime” although you may.
  •  There is a chance that it is recommended to reboot now.
2) Boost

Versions earlier than 1.55 used to include a binary installer. Such an installer is no longer available. However, the procedure is fairly simple. There are several ways to build boost; the following is referred to as “build from source”.

  • Open a command-line terminal, such as ‘cmd’.
  • Make the compiler known by running the following batch file:
c:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\bin\vcvars32.bat
  • Download the boost archive, unpack it to a target directory of your choice (e.g., C:\boost\boost_1_55_0), and change directory to target directory.
  • Run:
.\bootstrap
  • Then, build the static, shared, single and multi threaded boost libraries:
.\b2 link=static,shared threading=single,multi variant=debug,release
  • Make sure the subdirectory stage\lib\ has been populated with the compiled libraries (both .lib and .dll files).
3) CMake
  •  -Agree to the license.
  •  Check “Add CMake to the system PATH for all users”.
  • Check “create desktop icon”.
  •  Next, Next, Next.
  •  Finish
4) QT
  •  Agree to the license.
  •  Next, Next, Next, Install.
  •  Add QTDIR variable with the value C:\Qt\5.7.1 to the environment variables (if it’s not already there).
  •  Add <QT>\bin to the system PATH. (C:\Qt\5.7.1\bin)
4.1) QT Visual Studio 2013 addin:
  •  install the addin (Is it still necessary in VC 12?)
5) CGAL
  •  CGAL installation will need to connect to the internet for GMP and MPFR.
  •  Be amazed by the splash screen.
  •  Agree to the license.
  •  Just choose the default: with GMP and MPFR, and with examples and demos.
  •  64-bit (for me).
  •  In the “Setting Environment Variables” screen, choose all users and make sure that CGAL_DIR is checked.
  •  Install.
  •  Add <CGAL_DIR >\auxiliary\gmp\lib to the system PATH. (C:\Program Files\CGAL-4.9\auxiliary\gmp\lib)
Now you need to compile CGAL
  •  Open CMake – cmake-gui (on the Desktop) – if you are using win7 make sure you open the program in administrator mode – right click on the icon and click on “run as administrator”.
  •  For both “Where is the source code” and “Where to build the binaries” specify the CGAL Installation folder (C:\Program Files\CGAL-4.9)
  •  Click Configure.
  •  Choose “Visual Studio 12 2013” and click “Finish”
  •  Click Generate
  •  A solution named CGAL was created in the directory.
  •  Compile ALL_BUILD project both in Debug and Release (ignore the compilation error in CGAL_imageIO).
  •  All CGAL libraries should be under the lib directory.
6) Sanity check (optional)
  •  Open CMake (cmake-gui, can be found on the desktop) – (for win7 users, use “Run as admin”)
  •  Choose “Where is the source code:” to be the Triangulation_2 demo directory under the CGAL installation. Namely, <CGAL>/demo/Triangulation_2 (C:\Program Files\CGAL-4.9/demo/Triangulation_2).
  •  Choose “Where to build the binaries:” to the same directory.
  •  Click Configure
  •  Click Generate
  •  Go to the directory (C:\Program Files\CGAL-4.9) and open the solution and compile. Run the Delaunay_triangulation project for check (in debug and release)
7) Customizing env – If you are not using CMake to create new VS projects
 
 Note: the following operations should be repeated for the Debug and Release modes
  •  Right-click on the selected project and select “Properties”.
   Go to C/C++ -> General . Add the following to “Additional Include Directories” (include)
   * include: <Boost> (C:\Program Files\boost\boost_1_59)
   * include: <CGAL>\include (C:\Program Files\CGAL-4.9\include)
   * include: <CGAL>\auxiliary\gmp\include (C:\Program Files\CGAL-4.9\auxiliary\gmp\include)
   * include: <QT>\include\Qt (C:\Qt\5.7.1\include\Qt)
   * include: <QT>\include\QtCore (C:\Qt\5.7.1\include\QtCore)
   * include: <QT>\include\QtGui (C:\Qt\5.7.1\include\QtGui)
  Go to Linker -> General. Add the following to “Additional Dependencies” (include)
   * library: <CGAL>\lib (C:\Program Files\CGAL-4.9\lib)
   * library: <QT>\lib (C:\Qt\5.7.1\lib)
   * library: <Boost>\lib (C:\Program Files\boost\boost_1_59\lib)
   * library: <CGAL>\auxiliary\gmp\lib (C:\Program Files\CGAL-4.9\auxiliary\gmp\lib)
For a specific project using CGAL you need to ignore the auto-link of gmp and mpfr. The names below are for Debug.
 – Linker -> Input
   * Add libgmp-10.lib and libmpfr-4.lib to “Additional Dependencies”
   * Add gmp-vc100-mt-gd.lib and mpfr-vc100-mt-gd.lib to “Ignore Specific Library” (gmp-vc100-mt.lib and mpfr-vc100-mt.lib in release mode).
For a specific project using QT:
 – Linker -> Input
   * Add qtmaind.lib, QtGuid4.lib, and QtCored4.lib to “Additional Dependencies” (qtmain.lib;QtCore4.lib;QtGui4.lib in release).
Important: In case that the compilation succeeds but the linker is unable to find cgal-related dlls (“the program can’t start because cgal-vc100-mt-gd-4.2.dl is missing”)
find these files in the CGAL directory and copy them either to the system32 folder of windows, or the folder of the visual studio project.
Try to compile this programs:
Hello CGAL: http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Introduction/Chapter_main.html

Setting up PATH variable or other Environment variables on windows systems

    1. From the desktop, right-click My Computer and click properties.
    2. (on Vista/Win7/Win8 click Advanced system settings on the left side)
    3. In the System Properties window, click on the Advanced tab.
    4. In the Advanced section, click the Environment Variables button.
    5. Finally, in the Environment Variables window, highlight the path variable in the Systems Variable section and click edit. Add or modify the path lines with the paths you wish the computer to access. Each different directory is separated with a semicolon as shown below.C:\Program Files;C:\Winnt;C:\Winnt\System32

The material covered in class is scattered in several books and recent papers. As we proceed you’ll find here as well as in the course’s summary more references and links to relevant publications.

  • Basic techniques of computational geometry can be found in the following book:
    • Computational Geometry: Algorithms and Applications
      M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Springer, 1997

Below you’ll find more references to books on computational geometry

  • For robot motion planning, see
    • J.-C. Latombe
      Robot Motion Planning , Kluwer Academic Publishers, 1991
  • For books on arrangements, see
    • Davenport-Schinzel Sequences and Their Geometric Applications
      M. Sharir and P.K. Agarwal, Cambridge University Press, New York, 1995
    • Algorithms in Combinatorial Geometry
      H. Edelsbrunner, Springer Verlag, Heidelberg, 1987
  • For surveys on arrangements, see
    • Arrangements
      P.K. Agarwal and M. Sharir, Handbook of Computational Geometry J.-R. Sack and J. Urrutia (eds.), Elsevier Science Publishers, 1999, pp. 49–119
    • Arrangements [psz]
      D. Halperin, Handbook of Discrete and Computational Geometry J.E. Goodman and J. O’Rourke (eds.), CRC Press, Inc., Boca Raton, FL, 1997, pp. 389–412
  • More books on computational geometry:
    • Computational Geometry in C, 2nd Edition
      J. O’Rourke,Cambridge University Press, 1998
    • Algorithmic Geometry
      J.-D. Boissonnat and M. Yvinec, Cambridge University Press, 1995, 1998 (English version) [link]
    • Handbook of Discrete and Computational Geometry
      J.E. Goodman and J. O’Rourke (editors) CRC Press LLC, Boca Raton, FL, 1997
    • Computational Geometry: An Introduction Through Randomized Algorithms
      K. Mulmuley, Prentice Hall, Englewood Cliffs, NJ, 1994
    • Computational Geometry: An Introduction
      F.P. Preparata and M.I. Shamos, Springer-Verlag, New York, NY, 1985

Yair Oz - Webcreator

Contact

Mobile. 052-4703139 | WhatsApp
Email. [email protected]

Skip to content