ECG final workshop

Titles, abstracts, and slides (click on titles)

Invited talks

Bernhard Schölkopf MPI für biologische Kybernetik Tübingen	Learning with kernels The talk will start with a short introduction to kernel methods in machine learning. Following this, we will describe how some recent methods for nonlinear dimensionality reduction (such as locally linear embedding, or the graph Laplacian algorithm) can be viewed as kernel methods.
Peter Giblin The University of Liverpool	Recent work on skeletons of curves and surfaces The skeleton or medial axis of a curve in the plane or a surface in 3-space has been an object of interest ever since Blum introduced the idea in the context of biological shape in the 1970s. It is used as in some sense an index of the shape of the curve or surface and contains a great deal of information about the shape. In this talk I shall review some recent work, including construction of the skeleton using computer graphics, the evolution of the skeleton in 3D through a family of surfaces, the existence of geometrical constraints on the skeleton at points where it is singular, and the remarkable work of Damon which seeks to reduce the 3D skeleton to 'essentially' a tree structure.
Tamal Dey The Ohio State University	Delaunay and Voronoi Diagrams in Sample Based Modeling Modeling geometry from point samples offers flexibility in many science and engineering applications. Delaunay and Voronoi diagrams of the input points provide a data structure from which several geometric and topological properties of the sampled object can be derived. In this talk we present algorithms and their implementations for sampling, reconstructing, segmenting and extracting features from the Delaunay/Voronoi diagrams of the point sample of a shape.
Konrad Polthier Zuse Institute Berlin	Prescribed Mean Curvature Flow for Mesh Optimization We introduce anisotropic curvature operators for polyhedral surfaces and present applications in the context of noise removal and geometric feature detection. The discrete differential operators combine techniques from discrete geometry, finite element numerics and computer graphics.

ECG overview talks

These talks will present the achievements of the ECG consortium in the different work areas.

Dan Halperin Tel Aviv University - Israel	Arrangements
Kurt Mehlhorn MPI Saarbrücken - Germany	Algebraic and Arithmetic issues
Jean-Daniel Boissonnat INRIA Sophia Antipolis - France	Voronoi diagrams I and II
Joachim Giesen ETH Zürich - Switzerland	Surface reconstruction
Gert Vegter Rijksuniversiteit Groningen - Netherlands	Meshing of surfaces

Short talks
(sorted by alphabetical order of speakers)

Eric Berberich MPI Saarbrücken - Germany.	Recent Progress on Computing Arrangements of Quadrics A cell in an arrangement of quadrics can be computed using a projection of the spatial intersection curves to the plane. We present an exact, robust and efficient C++ implementation that computes the arrangements induced by the intersection curves on the lower and upper part of each quadric in such an arrangement. The implementation handles all degenerate cases and is able to restore spatial information which is lost due to the projection. It forms an algebraic basis as starting point for an exact, robust and efficient CAD system handling quadrics. Joint work with Elmar Schömer and Nicola Wolpert
Ioannis Z. Emiris, National Kapodistrian University of Athens, Greece.	Computing with real algebraic numbers of degree less than 5 Our motivation is the efficient and exact implementation of predicates in computer-aided design and nonlinear computational geometry, eg. in computing arrangements of conic arcs. We compare real algebraic numbers by precomputing generalized Sturm sequences, thus avoiding iterative algorithms. One important ingredient, of independent interest, is the determination of rational isolating points as functions of the coefficients, between any pair of real roots. We also exploit invariants and common subexpressions, in order to minimize the practical complexity. The degree of the tested quantities in the input coefficients is optimal for algebraic numbers of degree up to 3, and for degree 4 in most cases. All degeneracies are handled, including when the polynomials drop degree. The method applies to real solving of pairs of quadratic equations, and to sign determination of polynomials over algebraic numbers of degree less than 5. These operations have been implemented for numbers of degree up to 4, in a recent module of library Synaps 2.1. We have compared against certain general algebraic packages which, unlike our code, are able to treat arbitrary-degree algebraic numbers. First, against the publicly available approach by R. Rioboo (Issac'92) implemented on Axiom, the implementation by Guibas, Karavelas, and Russel [GKR04], and the built-in capabilities of Core 1.6, Maple 9, and Synaps 2. Our code runs about 4 times faster than the filtered version of [GKR04] ; the other implementations are slower. Second, the code was used by Athanasios Kakargias with the curved kernel (see Pion-Teillaud's talk) for circles and CGAL arrangements, where it was never slower and usually more than 3 times faster than the Leda 4.2 library. This is joint work with Elias Tsigaridas, National Kapodistrian University of Athens, Greece.
Efi Fogel Tel Aviv University - Israel.	CGAL Arrangements of Curves: More Generic than Ever
Menelaos Karavelas University of Notre Dame, USA.	A computational framework for handling motion We present a framework for implementing geometric algorithms involving motion. It is written in C++ and modeled after and makes extensive use of CGAL (Computational Geometry Algorithms Library). The framework allows easy implementation of kinetic data structure style geometric algorithms---ones in which the combinatorial structure changes only at discrete times corresponding to roots of functions of the motions of the primitives. This paper discusses the architecture of the framework and how to use it. We also briefly present a polynomial package we wrote, that supports exact and filtered comparisons of real roots of polynomials and is extensively used in the framework. We plan to include our framework in the next release of CGAL. Movie This joint work with Leonidas Guibas and Daniel Russell from Stanford University.
Nico Kruithof Rijksuniversiteit Groningen - Netherlands.	Meshing of skin surfaces Skin surfaces are traditionally used for the visualisation of molecules. They form a class of tangent continuous surfaces defined in terms of a set of balls (the atoms of the molecule) and a shrink factor. More recently, we used skin surfaces for approximation purposes. We have developed an algorithm to approximate a skin surface with a topological correct mesh. The algorithm consists of two steps: first construct a coarse topologically correct mesh and then a refinement step. The complexity of the coarse mesh is quadratic in the number of input balls, which is worst case optimal. In the talk, I present the main ideas of our algorithm and describe the use of CGAL in our implementation.
André Lieutier Dassault Systèmes Provence	Properties of the distance fonctions and Medial Axis of non smooth objects A natural extension of the gradient of the distance function to a finite point sample defines a flow which, together with its associated critical points and stable/unstable manifolds have been proven to provide powerfull tools for understanding which topological feature can be captured by a sampling of an object, at least for smooth (positive lfs) objects. After a brief presentation of theses notions, we examine how these properties extends to the distance function to an arbitary compact set, including a non smooth boundary. As an application we examine the computation of the "Lambda-Medial Axis", a subset of the Medial Axis which remains stable under Hausdorff distance perturbations of the boundary. On can then derive a very simple algorithm for the computation of the "Lambda-Medial Axis" which is an illustration of a model of computation taking aproximate inputs. Joint work with Frédéric Chazal, Université de Bourgogne, Dijon, France.
Bernard Mourrain INRIA Sophia Antipolis, France.	Algorithms for curves and surfaces; an algebraic point of view The treatment of shapes on a computer leads to a large domain of investigation, connected to topological, differential, numeric, symbolic questions and with many applications. In this talk, we will consider representation of shapes based on algebraic models, in particular on parameterised and implicit representation. We will describe different techniques to compute points of intersection on curves and surfaces, which involve approximate, control or certified computation. A special attention will be given to topology certification. We will mentioned 3 types of methods for computing the topology of a planar or a three dimensional curve or for meshing an implicit surface even in the presence of singularity. These methods will be illustrated by experiments with the library axel, dedicated to algebraic curves and surfaces. Joint work with J.P. Técourt, G. Gatellier, J.P. Pavone, G Comtes.
Steve Oudot INRIA Sophia Antipolis, France.	An Effective Condition for Sampling Surfaces with Guarantees The notion of e-sample, as introduced by Amenta and Bern, has proven to be a key concept in the theory of sampled surfaces. Of particular interest is the fact that, if E is an e-sample of a smooth surface S for a sufficiently small e, then the Delaunay triangulation of E restricted to S, Del|S(E), is a good approximation of S, both in a topological and in a geometric sense. Hence, if one can construct an e-sample, one also gets a good approximation of the surface. Moreover, correct reconstruction is ensured by various algorithms. In this talk, we will introduce the notion of loose e-sample. We show that the set of loose e-samples contains and is asymptotically identical to the set of e-samples. The main advantage of loose e-samples over e-samples is that they are easier to check and to construct. Work in collaboration with Jean-Daniel Boissonnat.
Sylvain Petitjean INRIA Lorraine, France.	Intersecting Quadrics: An Efficient and Exact Implementation We present the first complete, exact and efficient C++ implementation of a method for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based on the near-optimal algorithm recently introduced by Dupont et al. (see SoCG'03). Unlike existing implementations, it correctly identifies and parameterizes all the connected components of the intersection in all the possible cases, returning parameterizations with rational functions whenever such parameterizations exist. In addition, the coefficient field of the parameterizations is either minimal or involves one possibly unneeded square root. Joint work with S. Lazard and L. M. Peñaranda, INRIA Lorraine.
Simon Plantinga University of Groningen, The Netherlands.	Isotopic approximation of implicit curves and surfaces Several algorithms exist for generating piecewise linear approximations of implicit surfaces, but most of them are based on a user-defined stepsize or bounds to indicate the precision, and therefore cannot guarantee topological correctness. Interval arithmetic provides a mechanism to determine global properties of the implicit function. In this talk we present an algorithm that uses these properties to generate a piecewise linear approximation of implicit curves and surfaces, that is isotopic to the curve or surface itself. The algorithm is simple and fast, and is among the first to guarantee isotopy for implicit surface meshing.
Marc Pouget INRIA Sophia Antipolis, France.	Differential geometry of sampled smooth surfaces: principal frames, umbilics and ridges In this talk we investigate properties of curvature related quantities and objects on a sampled smooth surface given as a triangulated surface or a point cloud. First, we present an algorithm which consists of fitting the local representation of the surface as a height function, and derive the corresponding approximation order for the estimation of point-wise differential quantities. Second, we show how these differential quantities ---up to the fourth order--- can be used to detect and the classify umbilics and report ridge lines ---extrema of principal curvatures. Joint work with Frédéric Cazals, INRIA Sophia Antipolis.
Monique Teillaud INRIA Sophia Antipolis, France.	Towards a CGAL curved kernel The kernel of the CGAL library provides several functionalities which are, however, mostly restricted to linear objects. We present the design, implementation and testing of a kernel for computing arrangements of circular arcs. A preliminary implementation exists also for conic curves. We plan to submit this curved kernel framework as a new CGAL package. Joint work with Sylvain Pion, INRIA Sophia Antipolis, Ioannis Z. Emiris, Athanasios V. Kakargias and Elias P. Tsigaridas, National Kapodistrian University of Athens, Greece.
Ron Wein Tel-Aviv University, Israel.	Continuous Path Verification in Multi-Axis NC-Machining We introduce a new approach to the problem of collision detection between a rotating milling-cutter of an NC-machine and a model of a solid workpiece, as the rotating cutter continuously moves near the workpiece. Having five degrees of motion freedom, this problem is hard to solve exactly and we approximate the motion of the tool by a sequence of sub-paths of pure translations interleaved with pure rotations. The detection problem along each sub-path is then solved by using radial projection of the obstacles (the workpiece and other parts of the NC-machine) around the tool axis to obtain a collection of critical surface patches in space, and by examining planar silhouettes of these surface patches. We thus reduce the problem to successive computations of the lower envelope of a set of planar curves of degree 2 --- this reduction is exact, and incurs no loss of accuracy. We have implemented our algorithm in the {\sc Irit} environment for solid modeling, using an extension package of the {\sc Cgal} library for computing envelopes. The algorithm, combined with the proper data structures, solves the collision detection problem in a robust manner, yet it yields efficient computation times as our experiments show. Our approach yields accurate results in case of a purely translational motion, and provides guaranteed (and good) approximation bounds in case the motion includes rotations. Joint work with Dan Halperin, Tel-Aviv University, and with Oleg Ilushin and Gershon Elber, Technion, Haifa, Israel.