#
Workshop of Geometry Processing and Applications

**
September 15-16, 2004
**

IMPA / PUC-Rio

Organizers: Luiz Velho and Geovan Tavares

*Sponsored by
Instituto do Milênio - AGIMB*

### Wednesday Sep 15 (1:30 - 6:00)

- 1:30 - Opening
- Luiz Velho and Geovan Tavares
- 2:00 - Defining Point-set Surfaces
- Nina Amenta
- 3:00 - Geometry Problems in Cryo-Electron Microscopy
- Marshall Bern
- 4:00 - Interval Methods in Computer Graphics
- Luiz Henrique de Figueiredo
- 5:00 -
Mesh Ops: Handlebody and Stellar Theory Applied to Geometric Modeling
- Hélio Lopes

### Thursday Sep 16 (2:00 - 6:00)

- 2:00 - Low-cost 3D Digitization of Ceramic Fragments
- Jorge Stolfi
- 3:00 -
Applications of Radial Basis Functions in Surface Modeling and Reconstruction
- Claudio Esperança
- 4:00 - Discrete Morse Theory and Cell Complex Representations
- Thomas Lewiner
- 5:00 - Beta-Connection: Generating a Family of Models from Planar Cross Sections
- Luiz Gustavo Nonato

All sessions will be held at IMPA, Auditório 1

### Defining Point-set Surfaces

*Nina Amenta, University of California at Davis*

The MLS surface, used for modeling and
rendering with point clouds, was defined originally by David Levine
as the output of a particular meshless construction.
We give a new explicit definition in terms of the critical points of an
energy function
on lines determined by a vector field.
This definition reveals connections to
research in computer vision and computational topology, and provides a
framework for generalizing the construction.

Cryo-EM is a technique for obtaining 3D structures of molecules
and molecular complexes directly from an electron microscope.
The technique combines 2D projections from many different viewpoints
as in computed tomography. Unlike computed tomography, however,
"single particle" cryo-EM must compute the unknown viewpoints at the
same time that it computes the 3D reconstruction. I will talk about
the current state of the art, some proposed improvements, and some
basic mathematical and algorithmic questions inspired by cryo-EM.

I'll give a brief survey of the use of interval methods in computer
graphics. I'll discuss the application of interval and affine arithmetic
to problems in rendering and modeling, such as: approximation of
implicit curves; computation of offsets, bisectors, and medial axes
of parametric curves; ray tracing of implicit surfaces; strip tree
approximation of parametric curves; and intersection of parametric
surfaces.
[joint work with J. Stolfi, J. B. Oliveira, and H. Lopes]

In this work we introduce an unified framework for basic operations on
combinatorial 2-manifolds
with or without boundary. We show that there are two kinds of primitive
operators on the underlying meshes:
operators which change the topological characteristic nature of the mesh
and operators which just modify its combinatorial structure. To show the
completness of this set of operators we used Morse and Stellar Theory.
We also present several successful examples of their use in geometric
compression, mesh simplification and surface reconstruction. (This is a
joint work with Luiz Velho, Geovan Tavares, Thomas Lewiner and Esdras
Medeiros).

Many museums own huge collections of ceramic shards, with 10^{5} to 10^{6}
pieces, stored in their basements. That material is extremely valuable in
theory, but nearly useless in practice because the fragments that a researcher
may need are rather difficult to access and nearly impossible to locate.
Both problems could be solved by creating accurate digital models of the
pieces and making them available via the internet or other media. However,
in order to satisfy most current and potential uses (such as identification
of matching fragments and virtual reassembly of the original objects), the
models must be very detailed, with dimensions correct to 0.1 mm or so and
accurate texture and color.
While modern 3D laser scanners may be able to satisfy those requirements,
the scanning of 10^6 fragments seems to be well beyond the human and
financial resources of Brazilian museums. We have been investigating cheaper
alternatives, namely a combination of traditional multiview stereo and
multisource photometric stereo, using ordinary digital cameras and lighting
fixtures. Although neither method will suffice by itself, we hope that they
can be combined synergistically to yield the necessary accuracy.
[joint work with Helena C. G. Leitao]

The process of computing implicit objects as solutions of scattered
points interpolation problems constitutes a powerful paradigm for
modeling and reconstruction. In particular, several approaches have been
reported recently which interpolate point sets obtained from 3D scanning
process using Radial Basis Functions implicits (RBFs). Additionally,
these objects have found application in "free-form" surface modelling.
In this talk we shall discuss several key aspects of RBFs and associated
computational problems. We will also describe a novel poligonization
scheme and several modelling techniques that exploit unique
characteristics of these objects.

Among the various Morse theory that are used in the discrete world,
Forman introduced in 1995 the most comprehensive and rigorous one. After
a brief introduction to the classical Morse theory and the Smale
CW-complex representation, we will see how this concepts are expressed
in Forman's theory. We will then explore how this theory actually
structres Cell Complexes in interlaced layers of graphs.

Despite the significant evolution of techniques for 3D
reconstruction from planar cross sections, establishing the
correspondence of regions in adjacent slices remains an important
issue. In this talk we propose a novel approach for solving the
correspondence problem in a flexible manner.
We show that from the 3D Delaunay triangulation, it is possible to
derive a distance measure amongst regions lying in adjacent
slices. Such distance is used to define a positive integer
parameter, called "Beta", responsible for establishing the
connections. Varying "Beta" thus allows the construction of
different models from a given set of cross-sectional regions:
small values of "Beta" causes closer regions to be connected into
a single component, and as "Beta" increases more distant regions
are connected together. The algorithm, named Beta-connection,
will be described, and examples are provided that illustrate its
applicability in solid modeling and model reconstruction from real
data. The underlying reconstruction method is effective, which
jointly with the Beta-connection correspondence strategy
improve the usability of volumetric reconstruction techniques
considerably.