max planck institut
informatik
informatik
There is a multitude of representations for geometry data, the choice and and construction of an appropriate mathematical model is crucial for further processing of the data. Our research lead to new techniques for the reconstruction and modeling of surface and volume data.
Surfaces are commonly represented as polygonal meshes. Given huge scattered data from digitization, e.g., from a 3D-scan, it is not straightforward to construct a consistent, high-quality mesh due to the presence of measurement noise and variation of sampling density, i.e., oversampling and missing data. Our new approaches to related problem focus on sparse meshing of noisy data (Section 0.1.1), statistical learning methods (Section 0.1.2) and implicit surface fitting (0.1.3) for shape reconstruction. In addition we address subdivision techniques (Section 0.1.4) as a efficient model for smooth data in surface design and animation.
Volume data arise in many applications like medical imaging, seismic applications, and numeric simulations. We developed and investigated new kinds of trivariate splines as efficient models of such data (Section 0.1.5).
Investigators: Oliver Schall and Alexander Belyaev
Surface reconstruction is a field of intensive research in computer graphics. Hence, a large variety of efficient surface reconstruction techniques has been proposed including Delaunay-based and volumetric methods being of particular interest. However, in practice, most surface reconstruction techniques are still limited to handle clean data.
In [SBS05], we propose a clustering method for sparse surface reconstruction from dense noisy surface scattered data. The approach is inspired by the kernel density estimation method (Parzen-window estimation method). The approach computes a global uncertainty function modeling the contribution of each noisy point sample to the smooth surface which is supposed to be reconstructed. To find a sparse set of approximation centers of the smooth surface, minima of the uncertainty function are extracted using a gradient descent like technique. Once the approximation centers are determined their applications are versatile. The approximated smooth surface can be rendered using different visualization techniques like for instance surface splatting or accurately reconstructed using different established meshing techniques (see Figure 0.1).
 |
Investigators: Ioannis Ivrissimtzis and Waqar Saleem
With the recent progress in data acquisition systems the typical mesh size in a computer graphics application grows exponentially. This leads to a shift towards statistical methods in mesh processing because such methods can better cope with the computational time and memory restrictions imposed by large data sets. Moreover, as the size (and sometimes the noise) of the data increases, the average amount of information carried by a mesh primitive drops, making the statistical methods a more appropriate choice than their geometry based counterparts.
In collaboration with Won-Ki Jeong from the University of Utah and Seungyong Lee and Yunjin Lee from POSTECH, Korea, we study the use of Self-Organizing Maps in surface reconstruction. In [JIS03] we study a self-organizing mesh which develops using normal rather than spatial information, producing this way curvature adaptive reconstructions. In [IJS03] we improve an algorithm we proposed earlier, solving in particular the problem of changes in the mesh topology. In [Sal04] instead of the usual signal counters we use a relative evaluation of the activity of each vertex, improving the efficiency of the algorithm. In [ILL+04] we show that using an ensemble of self-organizing meshes rather than a single one, that is, averaging many different reconstruction of the same input data, improves the robustness. In [IOSS05] we study the applicability of clustering techniques in surface reconstruction.
In [IJL+05] we notice that even though self-organizing meshes have very limited ability to correct topological mistakes occurring at he early stages of their growth, nevertheless, such false topological features tend to shrink later in the process and become geometric details. We proposed a geometry forgetting component, in the form of coarse voxelization followed by remeshing, which periodically erase all the geometric detail. We showed that forgetting geometric detail is a very robust way to learn topology, see Fig. 0.2.
|
Investigators: Yutaka Ohtake and Alexander Belyaev
There are many applications that rely on building accurate digital models of real-world objects. Modern 3D digitizing techniques can yield millions of 3D point locations on the object that is being digitized. Once these points have been collected, it is a non-trivial task to build a surface representation that is faithful to the collected data.
In a series of papers [OBS04b,OBS04a,OBA+03,OBS03], we use radial basis function (RBF) and partition of unity (PU) approximations to develop surface reconstruction methods allowing for fast and accurate reconstruction of scattered data sets by implicit surfaces. The proposed methods are fast, capable of reconstructing sharp features, and robust in the presence of holes and abrupt variations in the sampling density. We also demonstrate that such RBF, PU, and RBF+PU composite implicit surface representations of digital shapes are often more accurate, easier to handle, and better adapted for various geometric modeling tasks then the traditional mesh-based representation.
Investigators: Ioannis Ivrissimtzis and Rhaleb Zayer
Subdivision surfaces are becoming the favored standard of the entertainment industry for surface representation. This is due to their simplicity, their ability to capture complex topology, and their hybrid representation both as a sequence of meshes of increasing size and as a smooth limit surface.
In collaboration with Malcolm Sabin from Numerical Geometry Ltd and Neil Dodgson from the University of Cambridge we studied several theoretical aspects of subdivision. In [ISD04] we studied the support of subdivision, that is, the area of the surface affected by the change in position of a single vertex of the initial mesh. Our results explain why for a binary scheme the support is usually a polygon which can be easily computed. We also show that if the scheme is not binary, then, in many cases the support will be fractal. In particular, we show that the support of the 3-scheme is a fractal and on its boundary we can identify sets like the classic ternary Cantor set. In [IDS04a] we presented a classification of the various subdivision schemes based on lattice transformations. In [IDS04b] we proposed a 5-subdivision scheme for quadrilateral meshes.
In [IS04,IZS04,IZS05] we work on the spectral analysis of subdivision surfaces. We notice that even though spectral analysis is the main tool for studying subdivision surfaces, nevertheless, the literature focuses on the analysis of the subdivision matrix rather than the analysis of mesh neighborhoods. In [IS04] we study eigen-decompositions of polygonal neighborhoods of the control mesh. Fig. 0.3 shows an eigen-basis for planar pentagons and hexagons, while we work with similar 3D decompositions. We show that such eigen-decompositions determine many of the properties of the subdivision surface. In particular, they determine when the surface has a singularity and if there is no singularity they determine the normal of the limit surface. In [IZS04,IZS05] we show that these decompositions can be extended to larger neighborhoods around a control vertex. This extension makes possible the study of schemes with larger support like the Catmull-Clark scheme.
Investigator: Christian Rössl
Splines are a valuable tool for approximating and modeling data well-known in Computer Aided Geometric Design. We focussed our research on the modeling and visualization of volumetric data using new trivariate splines, i.e., piecewise polynomials in three variables that are defined w.r.t. certain uniform tetrahedral partitions of the volumetric domain.
We studied the dimension of C¹-splines on these partitions in [HNR+04], which provides the theoretic foundation for the subsequent work and which indicates that the construction of such spline spaces is much more complex than in the bivariate setting.
In [RZNS03,RZNS04a] we propose a new approach to reconstruct non-discrete models from gridded volume samples, e.g., data stemming from a CT or MRI sensor. As a model, we use quadratic trivariate super splines which fulfill appropriate smoothness conditions using polynomial pieces of the lowest possible total degree two. This enables efficient and exact ray intersections with an isosurface for ray-casting. Our approach enables efficient reconstruction of the data using only repeated averaging. We studied the smoothness and approximation properties of the quasi-interpolating quadratic super splines in [NRZS05]. Here, we observe as a non-standard phenomenon that the derivatives of our splines yield optimal approximation order for smooth data, while the theoretical error of the values is nearly optimal due to the carefully chosen averaging rules. The optimal approximation properties of the derivatives allow to simply sample the necessary gradients directly from the polynomial pieces of the splines for efficient high-quality visualization of isosurfaces (see Fig. 0.4 (a)).
|
In [RZNS04b] we address the approximation of general data, i.e., the data is distributed over arbitrarily shaped volumes. We base our approach on cubic trivariate splines, which are determined from the discrete data as a result of a two-step method, where local discrete least squares polynomial approximations of varying degrees are extended by using natural conditions, i.e., the continuity and smoothness properties which determine the underlying spline space. The main advantages of this approach with linear algorithmic complexity are as follows: no tetrahedral partition of the volume data is needed, only small linear systems have to be solved, the local variation and distribution of the data is automatically adapted, noisy data are automatically smoothed. Our numerical examples with huge data sets for synthetic data as well as some real-world data confirm the efficiency of the methods, show the high quality of the spline approximation and illustrate that the rendered isosurfaces inherit a visual smooth appearance from the volume approximating splines (see Fig. 0.4 (b)).
