Motion Planning

Tools, Toolkits, and Libraries

• Computational Geometry
  • CGAL
  • LEDA, Gmp, CORE
  • Collision Detection and such
    • Opcode
    • Rapid, Swift
    • Solid
  • QHULL
• Visualization
  • OpenGl
  • GLUT
  • QT
  • Geomview
• Other
  • Optimizer
  • QSlim

CGAL

• A Computational Geometry Algorithms Library
• A collection of Data Structure and Operations
• Conists ot 3 major parts
  • kernel - constant-size non-modifiable geometric primitive objects and operations on these objects
  • basic library - a collection of basic geometric data structures and algorithms
  • non-geometric support facilities, such as circulators, random sources, I/O support for debugging and for interfacing CGAL to various visualization tools

CGAL Technical Info

• Written in C++
• Uses Generic Programming paradigm
  • Generic Programmimg
• Developed by a consortium consisting of
  • ETH Zürich (Switzerland)
  • Freie Universität Berlin (Germany)
  • INRIA Sophia-Antipolis (France)
  • Martin-Luther-Universität Halle-Wittenberg (Germany)
  • Max-Planck Institut für Informatik, Saarbrücken (Germany)
  • RISC Linz (Austria)
  • Tel-Aviv University (Israel)
  • Utrecht University (The Netherlands)
• CGAL home page
• CGAL at TAU

CAGL Kernel

• Contains objects of constant size, such as
  • point, vector, direction, line, ray, segment, triangle, iso-oriented rectangle and tetrahedron.
• Each type comes a set of functions that can be applied to an object of this type.
  • Access functions, tests of the position of a point relative to the object, a function returning the bounding box, the length, or the area of an object, etc..
• More basic operations
  • affine transformations, detection and computation of intersections, and distance computations.

CAGL Kernel Robustness

• Most geometric algorithms assume exact computation with real numbers
  • Leads to a problem with the implementation of geometric algorithms
  • often the exact real arithmetic is replaced by inexact floating-point arithmetic in the implementation
  • Rounding errors introduced by an inaccurate arithmetic may lead to inconsistent decisions, causing unexpected failures
• In CGAL you can choose the underlying number types and arithmetic.
• You can use different types of arithmetic simultaneously
  • The choice can be easily changed
• So you can choose between implementations with fast but occasionally inexact arithmetic and exact computation

CAGL Basic Library

• The collection of basic geometric algorithms and data structures
  • polygons, half-edge data structures, polyhedral surfaces, topological maps, planar maps, arrangements of curves, triangulations, convex hulls, alpha shapes, optimisation algorithms, dynamic point sets for geometric queries, and multidimensional search trees.
• Tel-Aviv Packages

  Topological map

  A structure with combinatorial information and no geometric information. It can also be used as a base class for deriving geometric subdivisions

  Planar Map

  An embedding of a topological map into the plane

  Arrangement

  A structure that supports 2D arrangements. The data structure maintains a planar map and curve hierarchy trees. Given a collection C of planar curves, the arrangement A(c) is the partition of the plane to vertices, edges and faces induced by the curves of C

LEDA

• A C++ class library for efficient data types and algorithms.
• Provides algorithmic in-depth knowledge in the field of graph- and network problems, geometric computations, combinatorial opimization and other.
• Used in application areas such as telecommunication, GIS, VLSI design, scheduling, traffic planning, computational biology and computer-aided design.
• offers algorithm building blocks such as graphs, sequences, dictionaries, trees, points, flows, matchings, segments, shortest paths, and many more.
• Follows object-oriented generic programming paradigms
• LEDA home page
• CGAL is independent of LEDA, but the two work well together.
  • The exact number types provided by LEDA are a way to deal with robustness issues of the geometric algorithms

Gmp

• GNU MP is a library for arbitrary precision arithmetic
• operating on signed integers, rational numbers, and floating point numbers
• It has a rich set of functions, and the functions have a regular interface.
• GNU MP is designed to be as fast as possible for small and huge operands
• Gmp home page
• Online Manual

Core

• Core home page

Optimizer

• OpenGL Optimizer is a C++ toolkit for CAD applications that enables interactive, robust visualization of large-model databases.
• Optimizer provides the following tools:
  • High-quality surface representations, that is, topologically consistent, parametric definitions of surfaces
  • Tessellation
  • Occlusion culling
  • Support for multiprocessor computing and advanced graphics hardware

Optimizer Technical Info

• Created and Maintained by SGI
• Optimizer home page
• Fully documented. Programming Guide
• API, library, and suite of tools == toolkit
• free, Irix and Windows
• Built on top of OpenGl
• Uses Cosmo3D Scene-Graph API

Culling with Optimizer

• Occlusion Culling
  • Identifies triangles in a scene graph that are occluded by objects in the foreground, and prevents their further processing in the graphics pipeline
• View-Frustum Culling
• Detail Culling
  • Level-of-detail are useful for adjusting the number of vertices associated with any given object.
• Back-Face Culling
  • Typically, triangles should not be rendered when their front sides do not face the viewpoint.

Occlusion and View-Frustum Culling

• The culler uses bounding boxes to determine whether a geometrical component is occluded.
• You can control what you mean by “occluded;”
  • the occlusion culler allows you to eliminate objects for which a specified fraction of their bounding boxes are occluded by foreground objects.

Opcode Collision Detection

• A small collision detection library.
  • Similar to popular packages (e.g., SOLID, RAPID, etc.) more memory-friendly, and often faster.
• Opcode home page
• C++ interface, developed for Windows systems using VC++ 6.0 and Linux
• Efficient memory usage BV's

Bounding Volumes

• Bounding-volume hierarchies are the most common collision detection (CD) structures when dealing with non-convex meshes or polygon soups
• used in numerous freely-available collision detection packages
• A complete BV-tree is made of 2*N-1 nodes
  • N is the number of primitives (e.g., triangles) in the input model.
  • In complete trees each leaf node contains a single primitive,
  • N-1 internal nodes
• Many Types
  • Sphere
    • SSV - Point Swept Sphere
    • LSS - Line Swept Sphere
    • RSS - Rectangle Swept Sphere
  • AABB - Axis Aligned Bounding Box
  • OBB - Orientaed Bounding Box
  • ...

NCU Gamma

• Geometric Algorithms for Modeling, Motion and Animation.
• Gamma home page

RAPID

• a robust and accurate polygon interference detection library for large environments composed of unstructured models.
• Applicable to polygon soups - models that contain no adjacency information, and obey no topological constraints.
  • may contain cracks, holes, self-intersections, and nongeneric (e.g. coplanar and collinear) configurations.
• Numericaly robust - the algorithm is not subject to conditioning problems, and requires no special handling of nongeneric cases (such as parallel faces).
• Free for non-commercial use.
• simple user interface: the user to be familiar with only about five function calls

SOLID

• a library for collision detection of three-dimensional objects
  • undergoing rigid motion and deformation
• Used in interactive 3D graphics applications
• suited for collision detection of objects and worlds described in VRML.
• Solid home page
• written in standard C++ (uses STL)
• Compiles under GNU g++ version 2.8.1 and Visual C++ 5.0.

QHULL

• Qhull is a general dimension code for computing
  • convex hulls
  • Delaunay triangulations
  • halfspace intersections about a point
  • Voronoi diagrams
  • furthest-site Delaunay triangulations, and
  • furthest-site Voronoi diagrams.
• QHULL home page

QSlim

• A programming interface with ANSI C bindings for writing window system independent OpenGL programs
• QSlim home page

glut

• The OpenGL Utility Toolkit
• An ANSI C implementation of GLUT for the X Window System developed by the author
• For windows