International Summer School on
Computational Methods for Shape Modelling and Analysis
Genova, 14-18 June 2004, Area della Ricerca, CNR, Genova

The School will provide training courses aimed at PhD, PostDoc or researchers with either a computer science, informatics or mathematics background, and prior knowledge of geometric modelling techniques.
Download the leaflet of the school programme (.PDF)

The school will focus on different aspects related to shape modelling, processing and analysis, and the final programme will include training on the following topics:



Despite a recent effort to make digital geometry tools robust to arbitrarily irregular meshes, most scanned surfaces need to undergo complete remeshing (alteration of the sampling and of the connectivity) before any further processing: results of finite element computations, compression, or editing rely heavily on an good description of the original geometry. In the first part of this course,  three different approaches for remeshing will be presented (isotropic, anisotropic and efficient remeshing), while in the second part of the course applications of remeshing to model compression will be described and methods for post-processing remeshed models will be discussed.

Speaker: Pierre Alliez (INRIA Sophia-Antipolis)
Duration: 2 hours
Isotropic remeshing leads to well-shaped triangles, and thus high-quality meshes when the notion of quality is related to the shape of the triangles. Such meshes are important for simulation or geometry processing (smoothing, compression) where the quality of the mesh elements is critical. In this work, we achieve isotropic vertex sampling prescribed by a given density function on the mesh. We use a modification of Lloyd's relaxation method to construct a weighted centroidal Voronoi tessellation of the mesh. We apply these iterations locally on small patches of the mesh that are parameterized into the 2D plane.
Anisotropic polygonal remeshing exploits the intrinsic anisotropy of natural or man-made geometry. In this work, we use the principal curvature directions to drive the remeshing process, mimicking the lines that artists themselves would use when creating 3D models from scratch. After extracting and smoothing the curvature tensor field of an input surface, lines of minimum and maximum curvatures are used to determine appropriate edges for the remeshed version in anisotropic regions, while spherical regions are simply isotropically point-sampled.
In this work, we depart from the accustomed approximation strategy by casting shape approximation as a variational geometric partitioning problem. Using a new concept of geometric proxies, we drive the distortion error down through repeated clustering of faces into best-fitting regions. Our approach is entirely discrete and error-driven, and does not require parameterization or local estimations of differential quantities. We also introduce a new metric based on normal deviation, and demonstrate its superior behavior at capturing anisotropy.

Time permitting, I will run several demos made with the computational geometry algorithm library CGAL (
These work have been done in collaboration with Mathieu Desbrun, Olivier Devillers, David Cohen-Steiner, Craig Gotsman, Vitaly Surazhsky and Bruno Levy.

Speaker: Marco Attene (IMATI-CNR Genova)
Duration: 1:30
In the latest years, remeshing proved to be one of the most promising directions when dealing with the compression of polygonal models. Most applications, in fact, do not require that the precise vertex positions on the surface and the original mesh connectivity is preserved. In all these cases, lossy techniques based on a remeshing of the model promise to provide higher compression ratios.
In this lecture, I will describe the SwingWrapper algorithm for remeshing-based compression of manifold triangle meshes. Due to the regularity of the meshes produced by SwingWrapper, their connectivity can be compressed to less than a bit per triangle. Moreover, the remeshing is performed so that the position of each vertex can be expressed with a single parameter. After quantization and arithmetic coding, SwingWrapper leads to an average compression rate of 0.4 bits/triangle with an L2 distortion of about 0.01% of the bounding box diagonal.

The SwingWrapper scheme, as well as various 3D acquisition, analysis, visualization and other remeshing approaches, samples surfaces of 3D shapes in a uniform fashion, without any attempt to align the samples with the sharp edges and corners of the original shape. Consequently, the interpolating triangle meshes chamfer these sharp features and thus exhibit a relatively large error in their vicinity. In this lecture I will describe EdgeSharpener, which is an automatic method for restoring most of the sharp edges and corners lost by feature-insensitive (re)meshing techniques. Also, I will present the Bender algorithm, which subdivides the resulting triangle mesh using a combination of the Butterfly subdivision scheme, for the smooth portion of the mesh, with a four-point subdivision scheme, for the sharp edges, in order to preserve the sharpness of the recovered sharp edges while bending their polyline approximations into smooth curves. Besides improving the visual appearance of the model, this combined Sharpen&Bend post-processing significantly reduces the error produced by feature-insensitive sampling processes.

These work have been developed at IMATI-CNR, in collaboration with Jarek Rossignac, within the Project Surface Analysis.



Computational topology is gaining increasing importance in computer graphics and vision. These lectures will deal with topological representations of digital shapes, focusing on size theory and Reeb graphs. Size theory will be introduced as a geometric-topological method for shape comparison, with definition of size functions, their main mathematical properties and size function computation methods. The definition of Reeb graph will be introduced, with its properties, and algorithms for its computation in different application fields.

Details on the programme:

Size theory as a geometric-topological method for shape comparison
Speaker: Patrizio Frosini (ARCES, Bologna)
Duration: 6 hours

1.    The natural pseudodistance: a geometric-topological tool for comparing shapes. (1 hour)
    a)    introduction to the problem;
    b)    definition of the natural pseudodistance between
    c)    size pairs (manifolds paired with real functions);
    d)    main properties of the natural pseudodistance.

2.    Size functions: comparing shapes by counting equivalence classes (2 hours)
    a)    definition of size function and examples;
    b)    main mathematical properties of size functions;
    c)    invariance under transformation groups;
    d)    size functions, noise and occlusions;
    e)    algebraic representation;
    f)    comparing size functions.

3.    Size functions as a tool for evaluating the natural pseudodistance (1 hour)
    a)    the link between the natural pseudodistance and
    b)    size functions: the lower bound theorem;
    c)    computing the natural pseudodistance via the lower
    d)    bound theorem.

4.     Computing size functions (1 hour)
    a)    size graphs and discrete size functions;
    b)    the approximation theorem;
    c)    reduction of size graphs.

Morse theory and Reeb graphs for shape understanding and coding
Speaker: Silvia Biasotti (IMATI, CNR, Genova)
Duration: 1:30 hours

1.    Homology and Morse Theory: an introduction
    a)    Elements of geometry and topology of surfaces
    b)    Elements of computational topology

2.    Reeb Graphs
    a)    Definition
    b)    Properties and relations with Morse theory

3.    Reeb Graphs and mapping functions
    a)    height function
    b)    integral of the geodesic distance
    c)    distance from the barycenter

4.    Applications of Reeb Graphs
    a)    DTM
    b)    Surface simplification
    c)    Shape matching

Speaker: Roberto Scopigno (ISTI, CNR, Pisa)
Duration: 4 hours


These lectures relate to the pipeline of tasks for the acquisition of the shape and colour of 3D objects, and for the creation of digital models to be efficiently used in local and/or remote graphics applications. The shape acquisition process, based on the adoption of optical 3D scanning approaches, implies the analysis, design, and implementation of efficient algorithms for the registration and alignment of the multiple scans into a common reference system, for the fusion of the scans into a unique digital model, the geometric simplification of the generated models, the editing and interactive corrections of small acquisition flaws, the acquisition of the colour and of the original texture, the efficient use of the models in local and/or distributed applications. Applications in the field of 3D Cultural Heritage will be shown.

- 3D Scanning Technology
      - Fundamentals of 3-D sensing:
        active 3D sensing (basic optical triangulation; pattern projection;
        time of flight systems)
        passive 3D sensing (silhouettes, space carving, stereo)

 - Range Data Registration and Merging 
      - Two-scan registration (iterative closest point);
        Multi-view registration
      - Volumetric methods for scan integration / merging
      - Connect-the-dots -- Delaunay sculpting; alpha-shapes; ball-pivoting;
      - Point-based methods

 - Surface Attributes Acquisition and Management
      - Using color images directly as texture maps
      - Using "unlit" color images to estimate diffuse reflectance
      - Estimated BRDF

 - Simplification and Rendering
      - Approaches for huge meshes simplification (external memory)
      - Rendering huge meshes on low-cost computers: triangle-based
        approaches (LOD, bump-mapping), hierarchical point-based approaches
      - Secure rendering of scanned models

 - 3D Scanning Experiences in Cultural Heritage Applications

Speaker: Nicholas M. Patrikalakis and Takis Sakkalis (Massachusetts Institute of Technology)
Duration: 1:30 hours  

Shape interrogation is the process of extraction of information from a geometric model.  It is a fundamental component of CAD/CAM systems. In this lecture, we focus on shape interrogation of geometric models bounded by free-form or sculptured surfaces. Such surfaces are widely used in the bodies of ships, automobiles, aircraft, propeller and turbine blades, and various consumer devices.  Our basic thesis is that shape interrogation problems can usually be recast in terms of the solution of a nonlinear system of equations, typically a polynomial system.  Much of our work is based on the Interval Projected Polyhedron (IPP) Algorithm, which reduces a continuous shape interrogation problem into the discrete problem of computing convex hulls and their intersections.  In this way, a bridge between the largely disparate fields of geometric modeling of free-form shapes (based on numerical analysis and approximation theory) and discrete computational geometry (based on the theory of algorithms and combinatorics) is established.  Various applications arising from surface intersections, distance function computations, global> differential geometry of curves and surfaces, and offsets are described and are reduced to the same unified solution framework.  A discussion of unresolved problems in this area is also provided.

- Nonlinear Polynomial Solvers
      * Introduction
      * Algebraic and hybrid techniques
      * Subdivision methods
          - The Projected Polyhedron (PP) algorithm
          - The Interval Projected Polyhedron (IPP) algorithm

- Intersection Problems and their Applications
      *  Curve/curve intersection
      *  Curve/surface intersection
      *  Surface/surface intersection
      *  Global differential geometry
      *  Distance functions and offsets

SHAPE SIMILARITY: Ambient Isotopy and Free-Form Object Matching
Speaker: Nicholas M. Patrikalakis and Takis Sakkalis (Massachusetts Institute of Technology)
Duration: 1:30 hours


This talk will address problems of similarity of 2D and 3D objects. The first part of the talk will consist of the notion of ambient isotopy as a means of similarity of two shapes, usually taken as two-dimensional manifolds. The second part will present problems of free-form matching for the point vs. NURBS surface and the NURBS surface vs. NURBS surface cases, and its application to copyright protection. Two new methods are developed to solve a global and partial matching problem with no a priori information on correspondence or initial transformation and no scaling effects: the KH and the umbilic method. The KH method establishes a correspondence between two objects by utilizing the Gaussian and mean curvatures. The umbilic method uses the qualitative properties of umbilical points to find correspondence information between two objects.  The matching algorithms are applied to problems of copyright protection. Three types of tests, the weak, intermediate and strong tests, are proposed for similarity assessment between two objects. They are organized in two decision algorithms so that they produce systematic and statistical measures for a similarity decision between two objects in a hierarchical manner.  Based on the systematic statistical evaluation of similarity, a decision can be reached whether the suspect model is a copy of the original model.

 - Ambient Isotopy
      *  Introduction and motivation
      *  Preliminaries
      *  Topological equivalence versus ambient isotopy
      *  Ambient isotopic approximations
      *  Interval solids
      *  Piecewise linear approximations of curves and surfaces
      *  Applications

 - 3D Free-Form Object Matching
      *  Introduction and motivation
      *  Classification of matching problems
      *  Umbilical point method
      *  Curvature method: KH method
      *  Resolving scaling effects
      *  Similarity evaluation
      *  Application to copyright protection


Speaker: Remco Veltkamp (Utrecht University)
Duration: 4 hour


Shape matching is a central problem in visual information systems,  computer vision, pattern recognition, and robotics. Applications of shape matching include industrial inspection, fingerprint matching, and content-based  image retrieval. A few examples are:
 - Applications in agricultural inspection. A typical problem here is to find  a matching transformation. Based on shape characteristics, we can  find the   transformation that matches one piece of fruit with another.
- Point matching in fingerprint identification applications. After extraction of featuring points, two point sets must be matched. The difficulty here is that there is typically no one to one correspondence between the two point sets. The matching technique should be robust against noise and  occlusion.
- Application in multimedia retrieval. Given the query shape, the task is to find all pictures that contain similar shapes. The typical problem  is that only pieces of the query shape appear in only parts of some of the database  pictures.
This tutorial is about the matching of shape, both in 2D and in 3D. We will survey:
 - Classes of applications
 - Vaious matching problem
 - Shape features
 - Similarity measures
 - Algorithms
We will address perceptual issues, as well as formal properties of  features, similarity measures, and algorithms.

Speaker: Michela Mortara, Giuseppe Patenè, Simone Marini (IMATI, CNR, Genova)
Duration: 2 hours


A skeletal structure is a lower-dimensional representation, which encodes the decomposition of a shape into relevant parts that may have either a geometric or an application-dependent meaning. Several well-known skeletal descriptors of shapes will be introduced, such as the medial axis transformation and the Reeb graph, with their properties and limits. We will show how each representation has peculiarities that makes it more feasible for certain applications and unfeasible for others.


1. Introduction on Shape descriptors
2. the Medial Axis Transformation and its properties
3. Brief recall about Reeb Graphs
4. Other skelatal structures, among which:
    a) approximated multi-scale MAT for planar shapes
    b) curvature-base skeleton
    c) approximated axis of tubular shapes

Speakers: Leila De Floriani (DISI, UNIGE, Genova), Enrico Puppo (DISI, UNIGE, Genova),  Paolo Cignoni (ISTI, CNR, Pisa)
Duration: 5 hours


Triangular meshes are probably the most common way to represent the geometry of 3d surface shapes. In many cases, this representation results too verbose and possibly too detailed for the needs of applications. More generally, it is desirable to have more or less detailed representations of the same shape available, where detail may also vary on different parts of the object and through time.

The task of finding a compact representation in terms of number of triangles, goes under the name of simplification. Many different algorithms and strategies have been presented and many different ways of evaluating the importance of the surface features that have to been presented exist and will be discussed in this course.

By elaborating upon the simplification technology, Level of Detail models are obtained. These models offer the possibility of extracting, through queries, several different representations with a level of detail satisfying specific requirements posed by the user in the query parameters. We will introduce the basic concepts of Level-Of-Detail modeling by presenting a general framework which encompasses existing models proposed in the literature and allows for their analysis and comparison.

Level-Of-Detail models can be divided into two broad classes: those designed for regularly-spaced data, and those for scattered data. We define the basic queries on a Level-Of-Detail model, and identify algorithms for answering such queries as well as primitives involved in such algorithms which must be supported by data structures.
We will then present a survey of data structures for encoding Level-Of-Detail models, according to the classification into regular and irregular meshes.

Simplification algorithms and level-of-detail models can be extended to volumetric models representing scalar data in 3D by means of tetrahedral decompositions. We will also present such extensions and discuss both simplification algorithms, as well as LOD data structures and query algorithms.

·    Mesh-based shape representations: data structures and update operations
·    Error metric for mesh-based shape approximation
·    Simplification algorithms for surfaces and 2D/3D scalar fields
·    A framework for Level-Of-Detail (LOD) shape modeling
·    LOD models for surfaces
·    LOD models for volume data sets

Pierre Alliez
Marco Attene
Silvia Biasotti
Paolo Cignoni
Leila De Floriani
Bianca Falcidieno
Patrizio Frosini
Simone Marini
Michela Mortara
Giuseppe Patanè
Nicholas M. Patrikalakis
Enrico Puppo
Takis Sakkalis
Roberto Scopigno
Michela Spagnuolo
Remco Veltkamp

The School is organized within and sponsored by the following projects:

MACROGeo: Metodi Algoritmici e Computazionali per la Rappresentazione di Oggetti Geometrici

AIM@SHAPE: Advanced and Innovative Models And Tools for the development of Semantic-based systems for Handling, Acquiring, and Processing knowledge Embedded in multidimensional digital objects

The number of participants to the School is limited to 80 participants

Registration fee:

200 €    150 € for
AIM@SHAPE and MACROGeo fellows

The registration fee includes school material, lunch coupons, coffee breaks, and social dinner.

Registration fees can be paid either by money order or cash at the registration desk. Please note that payment by credit card will not be accepted.

Details for money order payment:

Bank account
: c/c 218155
                          holder: Consiglio Nazionale delle Ricerche,
                                    Piazzale Aldo Moro 7, 00185 Roma, ITALY
                          description: "Incassi Giornalieri da Altre Dipendenze"

Payment reference:

Bank details:
     Bank name: Banca Nazionale del Lavoro, Sportello CNR 6392
                    Bank/Sort/Swift code: ABI: 01005   CAB: 03392   SWIFT:BNLIITRARBE
                    Street name: Piazzale Aldo Moro 7
                    PostCode: 00185
                    City: Rome
                    Country: Italy

To register:

1. Download the REGISTRATION FORM (.doc   or   .pdf)
2. Fill in the form and send it by Fax.
3. Fax the copy of the bank transfer (if this is your choice of payment).

Our Fax number: +390106475660.

For accommodation information, please refer to the convention web site
Please note that Genova is the European Capital of Culture in 2004. We strongly recommend to book your accommodation as soon as possible!

Mr Shape
Shape Modelling Group