Workshop of Geometry Processing and Applications

September 15-16, 2004

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.

Geometry Problems in Cryo-Electron Microscopy
Marshall Bern, PARC

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.

Interval Methods in Computer Graphics
Luiz Henrique de Figueiredo, IMPA

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]

Mesh Ops: Handlebody and Stellar Theory Applied to Geometric Modeling
Hélio Lopes, PUC-Rio

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).

Low-cost 3D Digitization of Ceramic Fragments
Jorge Stolfi, UNICAMP

Many museums own huge collections of ceramic shards, with 105 to 106 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]

Applications of Radial Basis Functions in Surface Modeling and Reconstruction
Claudio Esperança, UFRJ

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.

Discrete Morse Theory and Cell Complex Representations
Thomas Lewiner, PUC-Rio

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.

Beta-Connection: Generating a Family of Models from Planar Cross Sections
Luis Gustavo Nonato, USP

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.