nach oben

2005 | Buch

Kapitel lesen Erstes Kapitel lesen

Advances in Multiresolution for Geometric Modelling

herausgegeben von: Neil A. Dodgson, Michael S. Floater, Malcolm A. Sabin

Verlag: Springer Berlin Heidelberg

Buchreihe : Mathematics and Visualization

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Multiresolution methods in geometric modelling are concerned with the generation, representation, and manipulation of geometric objects at several levels of detail. Applications include fast visualization and rendering as well as coding, compression, and digital transmission of 3D geometric objects.

This book marks the culmination of the four-year EU-funded research project, Multiresolution in Geometric Modelling (MINGLE). The book contains seven survey papers, providing a detailed overview of recent advances in the various fields within multiresolution modelling, and sixteen additional research papers. Each of the seven parts of the book starts with a survey paper, followed by the associated research papers in that area. All papers were originally presented at the MINGLE 2003 workshop held at Emmanuel College, Cambridge, UK, 9-11 September 2003.

Inhaltsverzeichnis

Frontmatter

Compression

Recent Advances in Compression of 3D Meshes

Summary

3D meshes are widely used in graphical and simulation applications for approximating 3D objects. When representing complex shapes in raw data format, meshes consume a large amount of space. Applications calling for compact storage and fast transmission of 3D meshes have motivated the multitude of algorithms developed to compress these datasets efficiently. In this paper we survey recent developments in compression of 3D surface meshes. We survey the main ideas and intuition behind techniques for single-rate and progressive mesh coding. Where possible, we discuss the theoretical results obtained for asymptotic behaviour or optimality of the approach. We also list some open questions and directions for future research.

Pierre Alliez, Craig Gotsman

Shape Compression using Spherical Geometry Images

Summary

We recently introduced an algorithm for spherical parametrization and remeshing, which allows resampling of a genus-zero surface onto a regular 2D grid, a spherical geometry image. These geometry images offer several advantages for shape compression. First, simple extension rules extend the square image domain to cover the infinite plane, thereby providing a globally smooth surface parametrization. The 2D grid structure permits use of ordinary image wavelets, including higher-order wavelets with polynomial precision. The coarsest wavelets span the entire surface and thus encode the lowest frequencies of the shape. Finally, the compression and decompression algorithms operate on ordinary 2D arrays, and are thus ideally suited for hardware acceleration. In this paper, we detail two wavelet-based approaches for shape compression using spherical geometry images, and provide comparisons with previous compression schemes.

Hugues Hoppe, Emil Praun

Data Structures

A Survey on Data Structures for Level-of-Detail Models

Summary

In this paper we survey some of the major data structures for encoding Level Of Detail (LOD) models. We classify LOD data structures according to the dimensionality of the basic structural element they represent into point-, triangle-, and tetrahedron-based data structures. Within each class we will review single-level data structures, general data structures for LOD models based on irregular meshes as well as more specialised data structures that assume a certain (semi-) regularity of the data.

Leila De Floriani, Leif Kobbelt, Enrico Puppo

An Algorithm for Decomposing Multi-dimensional Non-manifold Objects into Nearly Manifold Components

Summary

In this paper we address the problem of building valid representations for non-manifold d-dimensional objects. To this aim, we have developed a combinatorial approach based on decomposing a non-manifold d-dimensional object into an assembly of more regular components, that we call initial quasi-manifolds. We present a decomposition algorithm, whose complexity is slightly super-linear in the total number of simplexes. Our approach provides a rigorous basis for designing efficient dimension-independent data structures for describing non-manifold objects.

M. Mostefa Mesmoudi, Leila De Floriani, Franco Morando, Enrico Puppo

Encoding Level-of-Detail Tetrahedral Meshes

Summary

Level-Of-Detail (LOD) techniques can be a valid support to the analysis and visualisation of volume data sets of large size. In our previous work, we have defined a general LOD model for d-dimensional simplicial meshes, called a Multi-Tessellation (MT), which consists of a partially ordered set of mesh updates. Here, we consider an instance of the MT for tetrahedral meshes, called a Half-Edge MT, which is built through a common simplification operation, half-edge collapse. We discuss two compact encodings for a Half-Edge MT, based on alternative ways to represent the partial order.

Neta Sokolovsky, Emanuele Danovaro, Leila De Floriani, Paola Magillo

Multi-Scale Geographic Maps

Summary

We consider geographic maps represented as plane graphs, which undergo a process of generalisation performed through sequences of local updates. Generalisation transforms a highly detailed map into one with fewer details, spanning many different scales of representation through the sequence of updates. We study intrinsic dependency relations among updates in the sequence and, on this basis, we derive a multi-scale model that supports efficient retrieval of maps at different scales, possibly variable through the domain.

Raquel Viaña, Paola Magillo, Enrico Puppo

Modelling

Constrained Multiresolution Geometric Modelling

Summary

This paper surveys the state-of-the-art of geometric modelling techniques that integrate constraints, including direct shape manipulation, physics-based modelling, solid modelling and freeform deformations as well as implicit surface modelling. In particular, it focuses on recent advances of multiresolution modelling of shapes under constraints.

Stefanie Hahmann, Gershon Elber

Multi-scale and Adaptive CS-RBFs for Shape Reconstruction from Clouds of Points

Summary

We describe a multi-scale approach for interpolation and approximation of a point set surface by compactly supported radial basis functions. Given a set of points scattered over a surface, we first use down-sampling to construct a point set hierarchy. Then starting from the coarsest level, for each level of the hierarchy, we use compactly supported RBFs to approximate the set of points at the level as an offset of the RBF approximation computed at the previous level. A simple RBF centre reduction scheme combined with the multi-scale approach accelerates the latter and allows us to achieve high quality approximations using relatively small number of RBF centres.

We also develop an adaptive RBF fitting prsocedure for which the RBF centres are randomly chosen from the set of points of the level. The randomness is controlled by the density of points and geometric characteristic of the set. The support size of the RBF we use to approximate the point set at a vicinity of a point depends on the local density of the set at that point. Thus parts with complex geometry are approximated by dense RBFs with small supports.

Numerical experiments demonstrate high speed and good performance of the proposed methods in processing irregularly sampled and/or incomplete data.

Yutaka Ohtake, Alexander Belyaev, Hans-Peter Seidel

Parameterization

Surface Parameterization: a Tutorial and Survey

Summary

This paper provides a tutorial and survey of methods for parameterizing surfaces with a view to applications in geometric modelling and computer graphics. We gather various concepts from differential geometry which are relevant to surface mapping and use them to understand the strengths and weaknesses of the many methods for parameterizing piecewise linear surfaces and their relationship to one another.

Michael S. Floater, Kai Hormann

Variations on Angle Based Flattening

Summary

Angle Based Flattening is a robust parameterization technique allowing a free boundary. The numerical optimisation associated with the approach yields a challenging problem. We discuss several approaches to effectively reduce the computational effort involved and propose appropriate numerical solvers. We propose a simple but effective transformation of the problem which reduces the computational cost and simplifies the implementation. We also show that fast convergence can be achieved by finding approximate solutions which yield a low angular distortion.

Rhaleb Zayer, Christian Rössl, Hans-Peter Seidel

Subdivision

Recent Progress in Subdivision: a Survey

Summary

After briefly establishing the traditional concepts in subdivision surfaces, we survey the way in which the literature on this topic has burgeoned in the last five or six years, picking out new trends, ideas and issues which are becoming important.

Malcolm Sabin

Optimising 3D Triangulations: Improving the Initial Triangulation for the Butterfly Subdivision Scheme

Summary

This work is concerned with the construction of a “good” 3D triangulation of a given set of points in 3D, to serve as an initial triangulation for the generation of a well shaped surface by the butterfly scheme. The optimisation method is applied to manifold meshes, and conserves the topology of the triangulations. The constructed triangulation is “optimal” in the sense that it locally minimises a cost function. The algorithm for obtaining a locally-optimal triangulation is an extension of Lawson's Local Optimisation Procedure (LOP) algorithm to 3D, combined with a priority queue. The first cost function designed in this work measures an approximation of the discrete curvature of the surface generated by the butterfly scheme, based on the normals to this surface at the given 3D vertices. These normals can be expressed explicitly in terms of the vertices and the connectivity between them in the initial mesh. The second cost function measures the deviations of given normals at the given vertices from averages of normals to the surface generated by the butterfly scheme in neighbourhoods of the corresponding vertices. It is observed from numerical simulations that our optimisation procedure leads to good results for vertices sampled from analytic objects. The first cost function is appropriate for analytic surfaces with a large proportion of convex vertices. Furthermore, the optimisation with this cost function improves convex regions in non-convex complex models. The results of optimisation with respect to the second cost function are satisfactory even when all the vertices are non-convex, but this requires additional initial information which is obtainable easily only from analytic surfaces.

Nurit Alkalai, Nira Dyn

Simple Computation of the Eigencomponents of a Subdivision Matrix in the Fourier Domain

Summary

After demonstrating the necessity and the advantage of decomposing the subdivision matrix in the frequency domain when analysing a subdivision scheme, we present a general framework based on a method, introduced by Ball and Storry, which computes the Discrete Fourier Transform of a subdivision matrix. The efficacy of the technique is illustrated by performing the analysis of Kobbelt's $\sqrt 3 $ scheme in a very simple manner.

Loïc Barthe, Cédric Gérot, Malcolm Sabin, Leif Kobbelt

Subdivision as a Sequence of Sampled Cp Surfaces

Summary

This article deals with practical conditions for tuning a subdivision scheme in order to control its artifacts in the vicinity of a mark point. To do so, we look for good behaviour of the limit vertices rather than good mathematical properties of the limit surface. The good behaviour of the limit vertices is characterised with the definition of C²-convergence of a scheme. We propose necessary explicit conditions for C²-convergence of a scheme in the vicinity of any mark point being a vertex of valency greater or equal to three.

Cédric Gérot, Loïc Barthe, Neil A. Dodgson, Malcolm Sabin

Reverse Subdivision

Summary

We present a reverse Chaikin algorithm which generates a multiresolution representation of any line chain. It has applications in multiresolution editing and compression. We also sketch how this might be extended to the bivariate Loop subdivision algorithm.

Mohamed F. Hassan, Neil A. Dodgson

$$\sqrt 5 $$ -subdivision

Summary

Most established subdivision schemes have the refined grid at each stage aligned with the previous one. The $\sqrt 3 $ and $\sqrt 2 $ schemes alternate orientations. This paper is one of the first detailed studies of a skew scheme in which the axis directions after refinement do not either lie along or bisect those before. It raises the issue of how the analysis techniques can be applied in this new context and provides an example of how they may be thus applied.

Ioannis P. Ivrissimtzis, Neil A. Dodgson, Malcolm Sabin

Geometrically Controlled 4-Point Interpolatory Schemes

Summary

We present several non-linear 4-point interpolatory schemes, derived from the “classical” linear 4-point scheme. These new schemes have variable tension parameter instead of the fixed tension parameter in the linear 4-point scheme. The tension parameter is adapted locally according to the geometry of the control polygon within the 4-point stencil. This allows the schemes to remain local and in the same time to achieve two important shape-preserving properties - artifact elimination and convexity-preservation. The proposed schemes are robust and have special features such as “double-knot” edges corresponding to continuity without geometrical smoothness and inflection edges support for convexity-preservation. A convergence proof is given and experimental smoothness analysis is done in detail, which indicates that the limit curves are C¹.

Martin Marinov, Nira Dyn, David Levin

Thinning

Adaptive Thinning for Terrain Modelling and Image Compression

Summary

Adaptive thinning algorithms are greedy point removal schemes for bivariate scattered data sets with corresponding function values, where the points are recursively removed according to some data-dependent criterion. Each subset of points, together with its function values, defines a linear spline over its Delaunay triangulation. The basic criterion for the removal of the next point is to minimise the error between the resulting linear spline at the bivariate data points and the original function values. This leads to a hierarchy of linear splines of coarser and coarser resolutions.

This paper surveys the various removal strategies developed in our earlier papers, and the application of adaptive thinning to terrain modelling and to image compression. In our image test examples, we found that our thinning scheme, adapted to diminish the least squares error, combined with a post-processing least squares optimisation and a customised coding scheme, often gives better or comparable results to the wavelet-based scheme SPIHT.

Laurent Demaret, Nira Dyn, Michael S. Floater, Armin Iske

Simplification of Topologically Complex Assemblies

Summary

In this paper we present a new simplification approach intended for scenes containing a huge number of simple objects forming a topologically complex assembly. Our method combines appearance preservation and topology reduction by converting a 3D model to and from an intermediate octree representation. During the conversion of the input mesh into an octree, appearance attributes such as colour are stored in the octree nodes. Unlike related approaches, the inside/outside values at octree vertices are computed according to neighbourhood configuration rather than by direct sampling. This allows the reconstructed surface to span only a reduced subset of the terminal nodes of the octree (those which are classified as border nodes), thus avoiding small cracks and removing internal structures not visible from the outside. The reconstruction step of our method succeeds in preserving the appearance of most of the scene objects while drastically simplifying the geometry and topology.

Carlos Andújar, Marta Fairén, Pere Brunet, Víctor Cebollada

Topology Preserving Thinning of Vector Fields on Triangular Meshes

Summary

We consider the topology of piecewise linear vector fields whose domain is a piecewise linear 2-manifold, i.e. a triangular mesh. Such vector fields can describe simulated 2-dimensional flows, or they may reflect geometric properties of the underlying mesh. We introduce a thinning technique which preserves the complete topology of the vector field, i.e. the critical points and separatrices. As the theoretical foundation, we have shown in an earlier paper that for local modifications of a vector field, it is possible to decide entirely by a local analysis whether or not the global topology is preserved. This result is applied in a number of compression algorithms which are based on a repeated local modification of the vector field — namely a repeated edge-collapse of the underlying piecewise linear domain.

Holger Theisel, Christian Rössl, Hans-Peter Seidel

Wavelets

Periodic and Spline Multiresolution Analysis and the Lifting Scheme

Summary

The lifting scheme is a well-known general framework for the construction of wavelets, especially in finitedimensional settings. After a short introduction about the basics of lifting, we discuss how wavelet constructions, in two specific finite settings, can be related to the lifting approach. These examples concern, on the one hand, polynomial splines and, on the other, the Fourier approach for translation-invariant spaces of periodic functions.

Jürgen Prestin, Ewald Quak

Nonstationary Sibling Wavelet Frames on Bounded Intervals: the Duality Relation

Summary

This note presents the setting of sibling frames on a compact interval together with a discussion on the duality relation.

Laura Beutel

Haar Wavelets on Spherical Triangulations

Summary

We construct piecewise constant wavelets on spherical triangulations, which are orthogonal with respect to a scalar product on L²($\mathbb{S}$²). Our classes of wavelets include certain wavelets obtained by Bonneau and by Nielson et al. We also prove the Riesz stability and show some numerical experiments.

Daniela Roşca

Backmatter

Titel: Advances in Multiresolution for Geometric Modelling
herausgegeben von: Neil A. Dodgson
Michael S. Floater
Malcolm A. Sabin
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-26808-6
Print ISBN: 978-3-540-21462-5
DOI: https://doi.org/10.1007/b138117

Premium Partner

Marktübersichten

Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.

Zur Marktübersicht