Last update: May 22, 2006

BACK

"Ada Lovelace's great grand daughters initiative"

• http://www.gdv.uni-hannover.de/schools/lovelace/index.php

Publications by F.-E. Wolter et al. :

• A Vibrotactile Approach to Tactile Rendering, 2006+.
  
• Laplace-Spectra as Fingerprints for Image Recognition, 2006+.
  
• Laplace-Beltrami Spectra as Shape DNA of Surfaces and Solids, 2006.
• Laplace Spectra as Fingerprints for Shape Matching, 2005.
  
• Geometric Modeling of Complex Shapes and Engineering Artifacts, 2004.
• Shape Intrinsic Watermarks for Free-Form Objects, 2004.
• Shape Intrinsic Properties for Free-Form Object Matching, 2003
• Shape Intrinsic Fingerprints for Free-Form Object Matching, 2003.
• Shape Intrinsic Watermarks for 3D Solids, 2003. (patent)
• Simplification of Closed Triangulated Surfaces Using Simulated Annealing, 2001.
• Local & Global Geometric Methods for Analysis Interrogation, Reconstruction, Modification & Design of Shape, 2000.
• Geometrical criteria on the higher order smoothness of composite surfaces, 1999.
• Haptical Rendering of Rough Surfaces using their Fractal Dimension, 1999.
• Geodesic Voronoi Diagrams on Parametric Surfaces, 1997.
• Computation of Medial Curves in Surfaces, 1996.
• Differential and Topological Properties of Medial Axis Transforms, 1996.
• Umbilics and Lines of Curvature for Shape Interrogation, 1996.
• Surface curve design by orthogonal projection of space curves onto free-form surfaces, 1996.
• The Geometric Modeling and Interrogation System Praxiteles, 1995.
• Numerical Experiments in Surface Approximation with Degree Reduction, 1994/3.
• Cut Locus & Medial Axis in Global Shape Interrogation & Representation, 1993.
• Inspection and Feature Extraction of Marine Propellers, 1993.
• Geometrical Criteria to Guarantee Curvature Continuity of Blend Surfaces, 1992.
• Approximation of High-Degree and Procedural Curves, 1992.
• Curvature Computations for degenerate surface patches, 1992.
• Topological and Differential-Equation Methods for Surface Intersections, 1992.
• Designing and Mapping Trimming Curves on Surfaces Using Orthogonal Projection, 1990.
  
• A Simple Practical Criterion to Guarantee Second Order Smoothness of Blend Surfaces, 1989.
  
• Cut Loci in Bordered and Unbordered Riemannian Manifolds, Ph.D., 1985.
• Interior Metric, shortest paths and loops in Riemannian manifolds with not necessarily smooth boundary, 1979.
• Distance Function and Cut Loci on a Complete Riemannian Manifold, 1979.

BibTeX references

Web link. : Cut Locus and Medial Axis in the Euclidean Space and on Surfaces, 2000.

A Vibrotactile Approach to Tactile Rendering

Abstract

Abstract

In the area of image retrieval from data bases and for copyright protection of large image collections there is a growing demand for unique but easily computable fingerprints for images. These fingerprints can be used to quickly identify every image within a larger set of possibly similar images. This paper introduces a novel method to automatically obtain such fingerprints from an image. It is based on a re-interpretation of an image as a Riemannian manifold. This representation is feasible for gray value images and color images.

We discuss the use of the spectrum of eigenvalues of different variants of the Laplace operator as a fingerprint and show the usability of this approach in several use cases. Contrary to existing works in this area we do not only use the discrete Laplacian, but also with a particular emphasis the underlying continuous operator. This allows better results in comparing the resulting spectra and deeper insights in the problems arising. We show how the well known discrete Laplacian is related to the continuous Laplace-Beltrami operator. Furthermore we introduce the new concept of solid height functions to overcome some potential limitations of the method.

Laplace-Beltrami Spectra as Shape DNA of Surfaces and Solids

Martin Reuter, Franz-Erich Wolter and Niklas Peinecke

Computer-Aided Design, vol. 38 (4), pp. 342-366, April 2006.

PDF file.

This paper introduces a method to extract "Shape-DNA," a numerical fingerprint or signature, of any 2D or 3D manifold (surface or solid) by taking the eigenvalues (i.e., the spectrum) of its Laplace-Beltrami operator. Employing the Laplace-Beltrami spectra (not the spectra of the mesh Laplacian) as fingerprints of surfaces and solids is a novel approach. Since the spectrum is an isometry invariant it is independent of the object's representation including parametrization and spatial position. Additionally the eigenvalues can be normalized, so that uniform scaling factors for the geometric objects can be obtained easily. Therefore, checking if two objects are isometric needs no prior alignment (registration/localization) of the objects but only a comparison of their spectra.

In this paper we describe the computation of the spectra and their comparison for objects represented by NURBS or other parametrized surfaces (possibly glued to each other), polygonal meshes as well as solid polyhedra. Exploiting the isometry invariance of the Laplace-Beltrami operator, we succeed in computing eigenvalues for smoothly bounded objects without discretization errors caused by approximation of the boundary. Furthermore, we present two non-isometric but isospectral solids that cannot be distinguished by the spectra of their bodies and present evidence that the spectra of their boundary shells can tell them apart.

Moreover, we show the rapid convergence of the heat trace series and demonstrate that it is computationally feasible to extract geometrical data such as the volume, the boundary length and even the Euler characteristic from the numerically calculated eigenvalues. This fact not only confirms the accuracy of our computed eigenvalues, but also underlines the geometrical importance of the spectrum. With the help of this "Shape-DNA" it is possible to support copyright protection, database retrieval and quality assessment of digital data representing surfaces and solids.

Laplace Spectra as Fingerprints for Shape Matching

M. Reuter, F.-E. Wolter and N. Peinecke

Proceedings of the ACM Symposium on Solid and Physical Modeling, June 2005.

Abstract

Since the spectrum is an isometry invariant of the respective object this fingerprint is also independent of the spatial position. Additionally the eigenvalues can be normalized so that scaling factors for the geometric object can be obtained easily. Therefore checking if two objects are isometric needs no prior alignment (registration / localization) of the objects, but only a comparison of their spectra.

With the help of such fingerprints it is possible to support copyright protection, database retrieval and quality assessment of digital data representing surfaces and solids.

A geometric model of an object - in most cases being a subset of the three dimensional space -- can be used to better understand the object's structure or behaviour. Therefore data such as the geometry, the topology and other application specific data have to be represented by the model. With the help of a computer it is possible to manipulate, process or display these data.

We will discuss different approaches for representing such an object: Volume based representations describe the object in a direct way, whereas boundary representations describe the object indirectly by specifying its boundary. A variety of different surface patches can be used to model the object's boundary. For many applications it is sufficient to know only the boundary of an object.

For special objects explicit or implicit mathematical representations can easily be given. An explicit representation is a map from a known parameter space e.g. the unit cube to 3D-space. Implicit representations are equations or relations such as the set of zeros of a functional with three unknowns. These can be very efficient in special cases.

As an example of volume based representations we will give a brief overview of the voxel representation. We also show how the boundary of complex objects can be assembled by simpler parts e.g. surface patches. These come in a variety of forms: planar polygons, parametric surfaces defined by a map from 2D-space to 3D-space, especially spline surfaces and trimmed surfaces, multiresolutionally represented surfaces, e.g., wavelet-based surfaces and surfaces obtained by subdivision schemes.

In a boundary representation only the boundary of a solid is described. This is usually done by describing the boundary as a collection of surface patches attached to each other at outer edges. One of the (topologically) most complete schemes is the half-edge data structure as described by Mäntylä. Simple objects constructed via any of the methods above can be joined to build more complex objects via Boolean operators (constructive solid geometry, CSG). Constructing an object one has to assure that the object is in agreement with the topological requirements of the modeling system. Notoriously difficult problems are caused by the fact that most modeling systems can compute surface intersections only with a limited precision. This yields numerical results that may finally cause major errors, e.g., topologically contradictory conclusions.

The rather new method of "Medial Modeling" is also presented. Here an object is described by its medial axis and an associated radius function. The medial axis itself is a collection of lower dimensional objects, i.e. for a 3D-solid a set of points, curves and surface patches. This medial modeling concept developed at the Welfenlab yields a very intuitive user interface useful for solid modeling, and also gives as a by-product a natural meshing of the solid for FEM computations.

Additional attributes can be attached to an object, i.e. attributes of physical origin or logical attributes. Physical attributes include photometric, haptical and other material properties, such as elasticity or roughness. Physical attributes are often specified by textures, i.e. functions that relate surface points to certain quantities of the attribute. The most common use for these are photometric textures, although they can also be used for roughness etc. Logical attributes relate the object to its (data-)environment. They can for example group objects which are somehow related, or they can associate scripts to the object, such as callbacks for user interactions.

Web site: http://engr.smu.edu/nsf2004/main.html

Methods are proposed for digital shape intrinsic watermarking of 3D solids represented via the boundary representation method (B-rep) with NURBS surfaces. Surface intrinsic properties are computed and used for comparison purposes, and a rigid body transformation for aligning two objects is estimated using integral properties and curvatures. Two algorithms are proposed to check if one object is a copy of the other. They consist of three similarity tests (e-offset test, principal curvature test and umbilical test), which provide systematic and hierarchical criteria for judgment of copyright violation.

This paper presents matching and similarity evaluation methods between two NURBS surfaces, and their application to copyright protection of digital data representing solids or NURBS surfaces. Two methods are employed to match objects: the moment and the curvature methods. The moment method uses integral properties, i.e., the volume, the principal moments of inertia and directions, to find the rigid body transformation as well as scaling factor. The curvature method is based on the Gaussian and the mean curvatures to establish correspondence between two objects. The matching algorithms are applied to problems of copyright protection. A suspect model is aligned to an original model through the matching methods so that similarity between two models can be assessed to determine if the suspect model contains part(s) of the original model, which may be stored in an independent repository. Three types of tests, the weak, intermediate and strong tests, are proposed for similarity assessment between two objects. The weak and intermediate tests are performed at node points obtained through shape intrinsic wireframing. The strong test relies on isolated umbilical points which can be used as fingerprints of an object for supporting an ownership claim to the original model. The three tests are organized in two decision algorithms such that they produce systematic and statistical measures for a similarity decision between two objects in a hierarchical manner. Based on the systematic and statistical evaluation of similarity, a decision can be reached whether the suspect model is an illegal copy of the original model.

PDF file.

Patent linked to this work:

• Shape-intrinsic watermarks for 3-D solids, US Pat Appl 20030128209
• http://home.att.net/~castleisland/up35/up35_109.htm
• Link at the USPTO

Web Link

The purpose of our project is to use roughness dependent information of a given 2D-texture for haptic rendering. A well-known fact in the area of Computer Graphics states a strong correlation of surface roughness and its fractal dimension. Basically we pursue two approaches to generate haptical impression of roughness after estimating the fractal dimension Dfrac of a given texture. These approaches are based on Brownian surfaces and motions. The textures in question have to be available in an appropriate representation applied to computed Dfrac.

A generalization of a theorem by Pegna and Wolter --- called Linkage Curve Theorem --- is presented. The new theorem provides a condition for joining two surfaces with high order geometric continuity of arbitrary degree n. It will be shown that the Linkage Curve Theorem can be generalized even for the case when the common boundary curve is only G1.

Author Keywords: Linkage curve theorem; Higher order smoothness

Web Link

Web Link

Web link.

The medial axis transform is a representation of an object which has been shown to be useful in design, interrogation, animation, finite element mesh generation, performance analysis, manufacturing simulation, path planning, and tolerance specification. In this paper, the theory of the medial axis transform for 3-D objects is developed. For objects with piecewise C² boundaries, relationships between the curvature of the boundary and the position of the medial axis are developed. For n-dimensional submanifolds of nwith boundaries which are piecewise C² and completely G¹, a deformation retract is set up between each object and its medial axis, which demonstrates that if the object is path connected, then so is its medial axis. Finally, it is proven that path connected polyhedral solids without cavities have path connected medial axes.

This paper describes a method to extract the generic features of free-form parametric surfaces for shape interrogation. The umbilical points, which are the singular points of the orthogonal net of lines of curvature, have generic features and may act like fingerprints for shape recognition. We investigate the generic features of the umbilics and behavior of lines of curvature which pass through an umbilic on a parametric free-form surface. Our method is based on a coordinate transformation to set the parametric surface in Monge form and on a Taylor expansion to compute the angles of the tangent lines to the lines of curvatures at an umbilic. We also develop a novel and practical criterion which assures the existence of local extrema of principal curvature functions at umbilical points. Finally, numerical experiments illustrate how the generic features of the umbilics can be applied for surface recognition.

Keywords: Umbilics; Lines of curvature; Monge form; Shape recognition; Perturbation; CAGD; CAD; Vision

Index Terms: Computational geometry; Pattern recognition; Mathematical transformations; Computational methods; Functions; Perturbation techniques; Computer aided design; Computer vision; Umbilical points; Lines of curvature; Shape interrogation; Monge form; Taylor expansion; Principal curvature functions; Surface recognition

Download PDFs here.

NB: Shows how to compute orthogonal projection points onto a surface, i.e., it computes a space point´s locally nearest foot point on some surface.

Donwload PDF file here.

Web Link

This paper presents a method to compute curvatures of a surface patch S obtained from a degenerate representation defined over a rectangular domain. To compute curvatures at a point q in S where the surface representation is degenerate one has to assume that the point set S has a tangent plane and well defined curvatures at the point q where the curvatures are to be computed. Our computation method employs a local height function representation of S in a neighborhood of the point q where the height function h is defined over the tangent plane of S at the point q. In our method the second order partial derivatives of the height function h at q are computed by using second order derivatives of any three surfaces curves on S which end up in q with pairwise linearly independent tangent directions. The curvature entities of S at q are then computed by using the second order partial derivatives of the height function h at q. We also show how the method is extended to compute partial derivatives of any order of the function h at q. For this purpose we show (in Theorem 1) how the partial derivatives up to nth order of a surface at a point q can be computed using derivatives up to order n of n + 1 surface curves emanating from q.

We also present a definition of a concept of generalized surface curvatures under weaker assumptions appropriate for degenerate surfaces. Under those weaker assumptions one does not require a locally C²-smooth height function representation of the surface over the tangent plane at the degenerate point q, nor a locally well defined (single-valued) height function representation of the surface in a neighborhood of the point q. One only needs the existence of a unique local second order approximation of the degenerate surface with a quadratic function defined over the tangent plane at q. The surface curvatures of the corresponding approximating quadratic surface then define the curvatures of the approximated degenerate surface in the contact point q.

Author Keywords: Degenerate surfaces; differential geometry; curvature.

Download PDF here.

PDF (scanned) file.

• Preface (pp. 4-10)
• 1. Introduction --- Summary of Results, Related Work of Other Authors (pp. 11-34)
• 2. Preliminaries (pp. 35-39)
• 3. Extenders, Picas, Cut Loci and Regularity of the Distance-Function (pp.40-63)
  • (a) Glueing Seam Lemma (p.61)
• 4. Lipschitz Points and Simulation of Certain Conjugate Points (pp. 64-113)
• 5. Applications (pp. 114-137)
• 6. Cut Loci on Bordered Surfaces (pp. 138-218)
• Appendix --- Technical Lemmata (pp. 219-240)
• References (pp. 241-249)

PDF (scanned) file.

In a metric space with an interior metric the distance between any two points is realized by the infinimum of the lengths of all paths joining those two points. In this space the length of a continuous parameterized path is defined by the supremum of all sums built by distances between any two consecutive points corresponding to any partition of the parameterization interval of the path. For locally compact and (Cauchy) complete metric space with an interior metric there exists for any two points a shortest path joining those points and (the assumption of an interior metric assures that) the length of the shortest path equals the metric distance between the end points of that path.

In case the latter metric space is not simply connected then there exists a shortest path in any homotopy class of closed paths with fixed base point. If further more the latter metric space is compact then there exists a closed shortest path in any non trivial free homotopy class of closed paths. Complete Riemannian manifolds provide classical examples for spaces with an interior metric where any two points can be joined by a shortest path realizing the distance between the two points. The main subject of this thesis are shortest paths in Riemannian manifolds that may have a boundary that is not necessarily smooth .

Let M be an n-dimensional Riemannian manifold with or without boundary. If the boundary of M is not empty then we assume that M is a topological manifold whose boundary is an (n-1)-dimensional topological manifold. Furthermore we assume that any point in M has a neighborhood containing a set being C¹-diffeomorphic to a cone in the n-dimensional Euclidean space. If the latter manifold M carries a (merely) continuous Riemannian metric then it can be employed to define the length of piece wise C¹-smooth paths useful to define the distance between any two given points in M. This distance endows M with an interior metric s. o. whose topology agrees with the manifold topology of M.

We assume now that the Riemannian metric is locally Lipschitz continuous and that every point of M has a neighborhood being C¹ diffeomorphic to a convex set in Euclidean space. Then an arclength parameterized shortest path joining any two points in M has an absolutely continuous first derivative and the square of the second derivative is Lebesgue integrable. This implies that the aforementioned first derivative is Hoelder-1/2-continuous. Combining the latter results with the general existence results for shortest paths stated above then we obtain:

If a Riemannian manifold M is locally C¹ diffeomorphic to some convex set in the Euclidean space and if M carries a locally Lipschitz continuous Riemannian metric then M becomes a metric space with an interior metric. If the latter metric space is complete then any two points p, q in M can be joined by a shortest C¹-smooth path whose length realizes the metric distance between p and q. The first derivative of that shortest path is Hoelder-1/2-continuous as the square of its second derivative is Lebesgue integrable. Furthermore there exists a shortest path in any homotopy class of closed paths with fixed base point. An arc length parameterization of the latter path is C¹-smooth and has all the aforementioned continuity properties. Note that at the base point (being the starting point and the end point) of the closed shortest path there usually exist two distinct tangent directions related to the start and the end point (respectively) of the parameterized shortest path.

Under the additional assumption that the space M is compact we have in any (non trivial) free homotopy class of closed paths a shortest path that is C¹ smooth everywhere. This means now at any point chosen as start and end point of (the aforementioned) closed path the tangent directions at the start point and at the end point agree. This implies if M is not simply connected and compact then there exists a shortest non contractible closed path (loop) and that path is C¹ smooth everywhere having the same derivative at the beginning and the end of the closed path.

The result stated above concerning existence and continuity of shortest (i.e., distance minimal paths) for the space M specified above (with quite weak assumptions) can be employed to prove that on M the distance function d(A, x) describing the distance of a variable point x in M with respect to some closed set A has a continuous gradient outside the cut locus of the set A, if x avoids A, cf. F.- E. Wolter, Ph. D. thesis 1985.

The aforementioned results imply the respective corresponding classical results that are valid for unbordered Riemannian manifolds, however, the techniques of the proofs are completely different and employ specific variational methods and tools from analysis.

• Preface and Introduction (pp. i-iv)
• I - Metric Spaces with Interior Metric (pp. 1-15)
  1. When is a Metrical Space Heine-Borelsch?
  2. Remarks on a Counter Example Named "Dimension-Rambler" (p.4)
  3. Shortest Paths in Metrical Spaces (p.8)
  4. Covering Spaces and Shortest Loops (p.9)
  5. Supplemented Remark on "Distance Between Points in a Covering Space of a Riemannian Manifold" (p.15)
• II - Interior Metric on Manifolds which Satisfy a Cone-Condition (pp. 16-32)
  1. Differentiable Manifolds with Not Necessarily Smooth Boundary Fulfilling a Cone-Condition
  2. Interior Metric on Manifolds which Satisfy a Cone-Condition and Carry a Riemannian Structure (p.25)
  3. Interior Metric on Manifolds which are Locally Diffeomorphic to a Convex Set in E^n (p.29)
• III - Smoothness Properties of Shortest Paths (pp. 33-51)
  1. The Length of an Absolutely Continuous Path
  2. Smoothness of a Rectifiable Shortest Path (p.39)
  3. Applications (p.46)
• Appendix A - Analytic Tools (pp. 52-61)
  1. The Spaces H_0 and H_1 and Imbedding Results
  2. Calculus of Difference Quotients and Smoothness Criteria (p.56)
• Appendix B - Arclength of C¹-smooth Curves in a Banach Space (pp. 62-64)
• References (pp. 65-66)

PDF (scanned) file.

Summary

Contains basic key results results and fundamental ideas on Cut Loci that were the starting point for Wolter's later follow up generalizations in his Ph.D. thesis and in the MIT report focussing on cut loci and medial Axes in the Euclidean case.

From section "1.Introduction."

"The results of this note are a characterisation of cut loci (Theorem 1) and the fact that a complete n-dimensional Riemannian manifold M is necessarily diffeomorphic to R^n if there is a point p in M for which the square of the distance functions d²(p, .) is everywhere directional differentiable, i.e., the directional derivative exists for all directions through that point (Theorem 2)."

From section "2. Statement of results."

Theorem 1:

• The cut locus Cu(p) on a complete Riemannian manifold is the closure of the set of all points in M which have at least two minimal geodesic connections to p.

Theorem 2:

• Assume there exists on the complete n-dimensional Riemannian manifold M a point p with the property that d²(p, .) is directional-differentiable on all M; then M is diffeomorphic to R^n.

BACK

Page created & maintained by Frederic Leymarie, 2000-6.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu