Mathematics of Surfaces XIII

Frontmatter

Computing Isophotes on Free-Form Surfaces Based on Support Function Approximation

Abstract

The support function of a free-form-surface is closely related to the implicit equation of the dual surface, and the process of computing both the dual surface and the support function can be seen as dual implicitization. The support function can be used to parameterize a surface by its inverse Gauss map. This map makes it relatively simple to study isophotes (which are simply images of spherical circles) and offset surfaces (which are obtained by adding the offsetting distance to the support function).

We present several classes of surfaces which admit a particularly simple computation of the dual surfaces and of the support function. These include quadratic polynomial surfaces, ruled surfaces with direction vectors of low degree and polynomial translational surfaces of bidegree (3,2).

In addition, we use a quasi-interpolation scheme for bivariate quadratic splines over criss-cross triangulations in order to formulate a method for approximating the support function. The inverse Gauss maps of the bivariate quadratic spline surfaces are computed and used for approximate isophote computation. The approximation order of the isophote approximation is shown to be 2.

M. Aigner, L. Gonzalez-Vega, B. Jüttler, M. L. Sampoli

Swept Volume Parameterization for Isogeometric Analysis

Abstract

Isogeometric Analysis uses NURBS representations of the domain for performing numerical simulations. The first part of this paper presents a variational framework for generating NURBS parameterizations of swept volumes. The class of these volumes covers a number of interesting free-form shapes, such as blades of turbines and propellers, ship hulls or wings of airplanes. The second part of the paper reports the results of isogeometric analysis which were obtained with the help of the generated NURBS volume parameterizations. In particular we discuss the influence of the chosen parameterization and the incorporation of boundary conditions.

M. Aigner, C. Heinrich, B. Jüttler, E. Pilgerstorfer, B. Simeon, A. -V. Vuong

Numerical Checking of C 1 for Arbitrary Degree Quadrilateral Subdivision Schemes

Abstract

We derive a numerical method to confirm that a subdivision scheme based on quadrilateral meshes is C ¹ at the extraordinary points. We base our work on Theorem 5.25 in Peters and Reif’s book “Subdivision Surfaces”, which expresses it as a condition on the derivatives within the characteristic ring around the EV. This note identifies instead a sufficient condition on the control points in the natural configuration from which the conditions of Theorem 5.25 can be established.

U. H. Augsdörfer, T. J. Cashman, N. A. Dodgson, M. A. Sabin

The Invariant Functions of the Rational Bi-cubic Bézier Surfaces

Abstract

Patterson’s work [1] on the invariants of the rational Bézier paths may be extended to permit weight vectors of mixed-sign [2]. In this more general situation, in addition to Patterson’s continuous invariants, a discrete sign-pattern invariant is required to distinguish path geometry. The author’s derivation of the invariants differs from that of Patterson’s and extends naturally to the rational Bézier surfaces. In this paper it is shown that 13 continuous invariant functions and a discrete, sign-pattern, invariant exist for the bi-cubic surfaces. Explicit functional forms of the invariant functions for the bi-cubics are obtained. The results are viewed from the perspective of the Fundamental Theorem on invariants for Lie groups.

H. E. Bez

Crazy Cuts: Dissecting Planar Shapes into Two Identical Parts

Abstract

We analyze a well known type of puzzle in planar geometry: given a planar shape, it is required to find a cut that divides the shape into two identical parts (up to rotation and translation). Clearly not all shapes can be so dissected and for some shapes that appear in puzzles the cutting curve is quite surprising and difficult to find. In this paper we first analyze the inverse problem of assembling planar shapes from two identical parts having partially ‘matching’ boundaries and then use the insights gained on this topic to derive an efficient algorithm to solve the dissection puzzle in quite general situations.

A. M. Bruckstein, D. Shaked

Piecewise Rational Manifold Surfaces with Sharp Features

Abstract

We present a construction of a piecewise rational free-form surface of arbitrary topological genus which may contain sharp features: creases, corners or cusps. The surface is automatically generated from a given closed triangular mesh. Some of the edges are tagged as sharp ones, defining the features on the surface. The surface is \(\mathcal C^s\) smooth, for an arbitrary value of s, except for the sharp features defined by the user. Our method is based on the manifold construction and follows the blending approach.

G. Della Vecchia, B. Jüttler

Deriving Box-Spline Subdivision Schemes

Abstract

We describe and demonstrate an arrow notation for deriving box-spline subdivision schemes. We compare it with the z-transform, matrix, and mask convolution methods of deriving the same. We show how the arrow method provides a useful graphical alternative to the three numerical methods. We demonstrate the properties that can be derived easily using the arrow method: mask, stencils, continuity in regular regions, safe extrusion directions. We derive all of the symmetric quadrilateral binary box-spline subdivision schemes with up to eight arrows and all of the symmetric triangular binary box-spline subdivision schemes with up to six arrows. We explain how the arrow notation can be extended to handle ternary schemes. We introduce two new binary dual quadrilateral box-spline schemes and one new \(\sqrt2\) box-spline scheme. With appropriate extensions to handle extraordinary cases, these could each form the basis for a new subdivision scheme.

N. A. Dodgson, U. H. Augsdörfer, T. J. Cashman, M. A. Sabin

Geometric Characterizations of Graphs Using Heat Kernel Embeddings

Abstract

In this paper, we investigate the heat kernel embedding as a route to computing geometric characterisations of graphs. The reason for turning to the heat kernel is that it encapsulates information concerning the distribution of path lengths and hence node affinities on the graph. The heat kernel of the graph is found by exponentiating the Laplacian eigensystem over time. The matrix of embedding co-ordinates for the nodes of the graph is obtained by performing a Young-Householder decomposition on the heat kernel. Once the embedding of its nodes is to hand we proceed to characterise a graph in a geometric manner. To obtain this characterisation, we focus on the edges of the graph under the embedding. Here we use the difference between geodesic and Euclidean distances between nodes to associate a sectional curvature with edges. Once the section curvatures are to hand then the Gauss-Bonnet theorem allows us to compute Gaussian curvatures at nodes on the graph. We explore how the attributes furnished by this analysis can be used to match and cluster graphs.

H. El-Ghawalby, E. R. Hancock

Compressive Algorithms—Adaptive Solutions of PDEs and Variational Problems

Abstract

This paper is concerned with an overview of the main concepts and a few significant applications of a class of adaptive iterative algorithms which allow for dimensionality reductions when used to solve large scale problems. We call this class of numerical methods Compressive Algorithms. The introduction of this paper presents an historical excursus on the developments of the main ideas behind compressive algorithms and stresses the common features of diverse applications. The first part of the paper is addressed to the optimal performances of such algorithms when compared with known benchmarks in the numerical solution of elliptic partial differential equations. In the second part we address the solution of inverse problems both with sparsity and compressibility constraints. We stress how compressive algorithms can stem from variational principles. We illustrate the main results and applications by a few significant numerical examples. We conclude by pointing out future developments.

M. Fornasier

Symmetry-Aware Mesh Processing

Abstract

Perfect, partial, and approximate symmetries are pervasive in 3D surface meshes of real-world objects. However, current digital geometry processing algorithms generally ignore them, instead focusing on local shape features and differential surface properties. This paper investigates how detection of large-scale symmetries can be used to guide processing of 3D meshes. It investigates a framework for mesh processing that includes steps for symmetrization (applying a warp to make a surface more symmetric) and symmetric remeshing (approximating a surface with a mesh having symmetric topology). These steps can be used to enhance the symmetries of a mesh, to decompose a mesh into its symmetric parts and asymmetric residuals, and to establish correspondences between symmetric mesh features. Applications are demonstrated for modeling, beautification, and simplification of nearly symmetric surfaces.

A. Golovinskiy, J. Podolak, T. Funkhouser

Recent Advances in Computational Conformal Geometry

Abstract

Computational conformal geometry focuses on developing the computational methodologies on discrete surfaces to discover conformal geometric invariants. In this work, we briefly summarize the recent developments for methods and related applications in computational conformal geometry. There are two major approaches, holomorphic differentials and curvature flow. The holomorphic differential method is a linear method, which is more efficient and robust to triangulations with lower quality. The curvature flow method is nonlinear and requires higher quality triangulations, but more flexible. The conformal geometric methods have been broadly applied in many engineering fields, such as computer graphics, vision, geometric modeling and medical imaging. The algorithms are robust for surfaces scanned from real life, general for surfaces with different topologies. The efficiency and efficacy of the algorithms are demonstrated by the experimental results.

X. D. Gu, F. Luo, S. -T. Yau

Finite Curvature Continuous Polar Patchworks

Abstract

We present an algorithm for completing a C ² surface of up to degree bi-6 by capping an n-sided hole with polar layout. The cap consists of n tensor-product patches, each of degree 6 in the periodic and degree 5 in the radial direction. To match the polar layout, one edge of these patches is collapsed.

We explore and compare with alternative constructions, based on more pieces or using total-degree, triangular patches.

K. Karčiauskas, J. Peters

A New Approach to Point Membership Classification in B-rep Solids

Abstract

A fundamental problem in computational geometry is determining whether a point is inside a B-rep solid. Methods currently used for such point classification are unreliable or inefficient or both. A new approach is illustrated by showing how a simple method for loops of planar curves represented by B-splines can be extended from two dimensions to three. The plan in two dimensions is to construct a polygon so that the point will be inside the loop if and only if it is inside the polygon. Once such a polygon is found, it is easy to compute its winding number with respect to the point. In three dimensions, an analogous (although more complicated) method is robust and efficient.

F. Klein

Probabilistic Modeling and Visualization of the Flexibility in Morphable Models

Abstract

Statistical shape models, and in particular morphable models, have gained widespread use in computer vision, computer graphics and medical imaging. Researchers have started to build models of almost any anatomical structure in the human body. While these models provide a useful prior for many image analysis task, relatively little information about the shape represented by the morphable model is exploited. We propose a method for computing and visualizing the remaining flexibility, when a part of the shape is fixed. Our method, which is based on Probabilistic PCA, not only leads to an approach for reconstructing the full shape from partial information, but also allows us to investigate and visualize the uncertainty of a reconstruction. To show the feasibility of our approach we performed experiments on a statistical model of the human face and the femur bone. The visualization of the remaining flexibility allows for greater insight into the statistical properties of the shape.

M. Lüthi, T. Albrecht, T. Vetter

Parameterizing Singularities of Positive Integral Index

Abstract

Classical surface parameterization algorithms often place singularities in order to enhance the quality of the resulting parameter map. Unfortunately, singularities of positive integral index (as the north pole of a sphere) were not handled since they cannot be described with piecewise linear parameter functions on a triangle mesh. Preprocessing is needed to adapt the mesh connectivity. We present an extension to the QuadCover parameterization algorithm [1], which allows to handle those singularities.

A singularity of positive integral index can be resolved using bilinear parameter functions on quadrilateral elements. This generalization of piecewise linear functions for quadrilaterals enriches the space of parameterizations. The resulting parameter map can be visualized by textures using a rendering system which supports quadrilateral elements, or it can be used for remeshing into a quad mesh.

M. Nieser, K. Polthier

Two Step Time Discretization of Willmore Flow

Abstract

Based on a natural approach for the time discretization of gradient flows a new time discretization for discrete Willmore flow of polygonal curves and triangulated surfaces is proposed. The approach is variational and takes into account an approximation of the L ²-distance between the surface at the current time step and the unknown surface at the new time step as well as a fully implicity approximation of the Willmore functional at the new time step. To evaluate the Willmore energy on the unknown surface of the next time step, we first ask for the solution of a inner, secondary variational problem describing a time step of mean curvature motion. The time discrete velocity deduced from the solution of the latter problem is regarded as an approximation of the mean curvature vector and enters the approximation of the actual Willmore functional. To solve the resulting nested variational problem in each time step numerically relaxation theory from PDE constraint optimization are taken into account. The approach is applied to polygonal curves and triangular surfaces and is independent of the co-dimension. Various numerical examples underline the stability of the new scheme, which enables time steps of the order of the spatial grid size.

N. Olischläger, M. Rumpf

Surface Triangulation and the Downstream Effects on Flattening

Abstract

Many applications within computer aided engineering require the support of a triangulation to gain geometrical and structural insight into the original surface being approximated. Therefore, downstream applications such as computer numerically controlled (CNC) machine path generation, finite element analysis (FEA) and flattening are triangulation dependant processes. However, despite the importance of triangulation in these applications, very little work has been focused on the downstream effects of triangulation. This paper investigates these effects on the application of surface flattening and demonstrates how subtle, but important changes in the triangulation can have a major impact on the flattening results.

S. S. Parwana, R. J. Cripps

On Mesh Editing, Manifold Learning, and Diffusion Wavelets

Abstract

We spell out a formal equivalence between the naive Laplacian editing and semi-supervised learning by bi-Laplacian Regularized Least Squares. This allows us to write the solution to Laplacian mesh editing in a ‘closed’ form, based on which we introduce the Generalized Linear Editing (GLE). GLE has both naive Laplacian editing and gradient based editing as special cases. GLE allows using diffusion wavelets for mesh editing. We present preliminary experiments, and shortly discuss connections to segmentation.

R. M. Rustamov

Gradient Approximation on Uniform Meshes by Finite Differences and Cubic Spline Interpolation

Abstract

For the approximation of gradients from data values at vertices of a uniform grid, we compare two methods based on cubic spline interpolation with a classical method based on finite differences. For univariate cubic splines, we use the so-called de Boor’s Not a Knot property and a new method giving pretty good slopes. Then these methods are used on parallels to the axes for estimating gradients on bivariate grids. They are illustrated by several numerical examples.

P. Sablonnière

Metric Methods in Surface Triangulation

Abstract

We consider the problem of better approximating surfaces by triangular meshes. The approximating triangulations are regarded as finite metric spaces and the approximated smooth surfaces are viewed as their Haussdorff-Gromov limit. This allows us to define in a more natural way the relevant elements, constants and invariants, such as principal directions and Gauss curvature, etc. By a “natural way” we mean intrinsic, discrete, metric definitions as opposed to approximating or paraphrasing the differentiable notions. Here we consider the problem of determining the Gauss curvature of a polyhedral surface, by using the metric curvatures in the sense of Wald, Menger and Haantjes. We present three modalities of employing these definitions for the computation of Gauss curvature.

E. Saucan, E. Appleboim

Setback Vertex Blends in Digital Shape Reconstruction

Abstract

Digital shape reconstruction (DSR) deals with creating CAD models of physical objects using 3D scanned data. Our primary interest is to reconstruct mechanical engineering objects that are usually composed of a hierarchy of surfaces – primary surfaces, connecting features (fillets) and vertex blends – and are structured by well-defined topological rules. After an overview of segmenting large polygonal meshes by the functional decomposition paradigm, we focus on the reconstruction of vertex blends using setbacks. This topic was thoroughly studied more than a decade ago in the context of constructive CAD; now the concept is revisited for DSR. A new method is presented to locate the optimal cross-sectional termination of fillets and construct the boundary curves of vertex blends on the mesh. These will correspond to the vertex blend boundaries of the final CAD model, as well. Finally, we discuss special cases of self-intersecting segmenting curve networks, and show how these problems can be resolved by setback vertex blends.

Z. Terék, T. Várady

Learning a Self-organizing Map Model on a Riemannian Manifold

Abstract

We generalize the classic self-organizing map (SOM) in flat Euclidean space (linear manifold) onto a Riemannian manifold. Both sequential and batch learning algorithms for the generalized SOM are presented. Compared with the classical SOM, the most novel feature of the generalized SOM is that it can learn the intrinsic topological neighborhood structure of the underlying Riemannian manifold that fits to the input data. We here compared the performance of the generalized SOM and the classical SOM using real 3-Dimensional facial surface normals data. Experimental results show that the generalized SOM outperforms the classical SOM when the data lie on a curved Riemannian manifold.

D. J. Yu, E. R. Hancock, W. A. P. Smith

Surface Quasi-Conformal Mapping by Solving Beltrami Equations

Abstract

We consider the problem of constructing quasi-conformal mappings between surfaces by solving Beltrami equations. This is of great importance for shape registration.

In the physical world, most surface deformations can be rigorously modeled as quasi-conformal maps. The local deformation is characterized by a complex-value function, Beltrami coefficient, which describes the deviation from conformality of the deformation at each point.

We propose an effective algorithm to solve the quasi-conformal map from the Beltrami coefficient. The major strategy is to deform the conformal structure of the original surface to a new conformal structure by the Beltrami coefficient, such that the quasi-conformal map becomes a conformal map. By using holomorphic differential forms, conformal maps under the new conformal structure are calculated, which are the desired quasi-conformal maps.

The efficiency and efficacy of the algorithms are demonstrated by experimental results. Furthermore, the algorithms are robust for surfaces scanned from real life, and general for surfaces with different topologies.

W. Zeng, F. Luo, S. -T. Yau, X. D. Gu

Backmatter