Refine
Year of publication
Language
- English (48)
Keywords
- optimal control (5)
- trajectory storage (4)
- Currents (2)
- Matching (2)
- Newton-CG (2)
- compression (2)
- discrete differential geometry (2)
- face numbers of polytopes (2)
- 3D mesh compression (1)
- Acetabulum (1)
Application Area
- F (48) (remove)
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 [KNP07], 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 pure quad mesh.
We investigate optimal elliptic
regularity (within the scale of Sobolev spaces) of anisotropic
div--grad operators in three dimensions at a multi-material vertex on
the Neumann boundary part of a polyhedral spatial domain. The
gradient of a solution to the corresponding elliptic PDE (in a
neighbourhood of the vertex) is integrable to an index greater than
three.
We provide conditions for convergence of polyhedral surfaces and their
discrete geometric properties to smooth surfaces embedded in R^3. The
notion of totally normal convergence is shown to be equivalent to the convergence
of either one of the following: surface area, intrinsic metric, and
Laplace-Beltrami operators. We further show that totally normal convergence
implies convergence results for shortest geodesics, mean curvature,
and solutions to the Dirichlet problem. This work provides the justifi-
cation for a discrete theory of differential geometric operators defined on
polyhedral surfaces based on a variational formulation.
Durhuus and Jonsson (1995) introduced the class of “locally constructible” (LC) 3-spheres and showed that there are only exponentially-many combinatorial types of simplicial LC 3-spheres. Such upper bounds are crucial for the convergence of models for 3D quantum gravity.
We characterize the LC property for d-spheres ("the sphere minus a facet collapses to a (d-2)-complex") and for d-balls. In particular, we link it to the classical notions of collapsibility, shellability and constructibility, and obtain hierarchies of such properties for
simplicial balls and spheres. The main corollaries from this study are: (1.) Not all simplicial 3-spheres are locally constructible. (This solves a problem by Durhuus and Jonsson.)
(2.) There are only exponentially many shellable simplicial 3-spheres with given number of facets. (This answers a question by Kalai.)
(3.) All simplicial constructible 3-balls are collapsible. (This answers a question by Hachimori.)
(4.) Not every collapsible 3-ball collapses onto its boundary minus a facet. (This property appears in papers by Chillingworth and Lickorish.)
Discrete Laplace--Beltrami operators on polyhedral surfaces play an important role for various applications in geometry processing and related areas like physical simulation or computer graphics. While discretizations of the weak Laplace--Beltrami operator are well-studied, less is known about the strong form. We present a principle for constructing strongly consistent discrete Laplace--Beltrami operators based on the cotan weights. The consistency order we obtain, improves previous results reported for the mesh Laplacian. Furthermore, we prove consistency of the discrete Willmore energies corresponding to the discrete Laplace--Beltrami operators.
Deformable surface models are often represented as triangular meshes in image segmentation applications. For a fast and easily regularized deformation onto the target object boundary, the vertices of the mesh are commonly moved along line segments (typically surface normals). However, in case of high mesh curvature, these lines may intersect with the target boundary at “non-corresponding” positions, or may not intersect at all. Consequently, certain deformations cannot be achieved. We propose omnidirectional displacements for deformable surfaces (ODDS) to overcome this limitation. ODDS allow each vertex to move not only along a line segment but within a surrounding sphere, and achieve globally optimal deformations subject to local regularization con-
straints. However, allowing a ball-shaped instead of a linear range of motion per vertex significantly increases runtime and memory. To alleviate this drawback, we propose a hybrid approach, fastODDS, with improved runtime and reduced memory requirements. Furthermore, fastODDS can also cope with simultaneous segmentation of multiple objects. We show the theoretical benefits of ODDS with experiments on synthetic data, and evaluate ODDS and fastODDS quantitatively on clinical image data of the mandible and the hip bones. There, we assess both the global segmentation accuracy as well as local accuracy in high curvature regions, such as the tip-shaped mandibular coronoid processes and the ridge-shaped acetabular rims of
the hip bones.
We present a unified computational framework for matching 3d geometric objects (points, lines, surfaces, volumes) of highly varying shape. Our approach is based on the Large Deformation Diffeomorphic Metric Mapping (LDDMM) method acting on $m$-currents. After stating an optimization algorithm in the function space of admissible morph generating velocity fields, two innovative aspects in this framework are presented: First, we spatially discretize the velocity field with conforming adaptive finite elements and discuss advantages of this new approach. Secondly, we directly compute the temporal evolution of discrete $m$-current attributes. Several numerical experiments demonstrate the effectiveness of this approach.
A capillary surface in a negative gravitational field describes the shape of the surface of a hanging drop in a capillary tube with wetting material on the bottom. Mathematical modeling leads to the volume- and obstacle-constrained minimization of a nonconvex nonlinear energy functional of mean curvature type which is unbounded from below. In 1984 Huisken proved the existence and regularity of local minimizers of this energy under the condition on gravitation being sufficiently weak. We prove convergence of a first order finite element approximation of these minimizers. Numerical results demonstrating the theoretic convergence order are given.
We introduce and analyze nonsmooth Schur-Newton methods for a class of nonsmooth saddle point problems. The method is able to solve problems where the primal energy decomposes into a convex smooth part and a convex separable but nonsmooth part. The method is based on nonsmooth Newton techniques for an equivalent unconstrained dual problem. Using this we show that it is globally convergent even for inexact evaluation of the linear subproblems.
We construct and analyze multigrid methods
for discretized self-adjoint elliptic problems on triangular surfaces in $\RR^3$.
The methods involve the same weights for restriction and prolongation as in the case of planar triangulations
and therefore are easy to implement. We prove logarithmic bounds of the convergence
rates with constants solely depending on the ellipticity, the smoothers and on the
regularity of the triangles forming the triangular surface.
Our theoretical results are illustrated by numerical computations.
Modeling the orientation distribution function by mixtures of angular central Gaussian distributions
(2010)
In this paper we develop a tensor mixture model for diffusion weighted imaging
data using an automatic model selection criterion for the order of tensor
components in a voxel. We show that the weighted orientation distribution
function for this model can be expanded into a mixture of angular central
Gaussian distributions. We show properties of this model in extensive
simulations and in a high angular resolution experimental data set. The results
suggest that the model may improve imaging of cerebral fiber tracts. We
demonstrate how inference on canonical model parameters may give rise to new
clinical applications.
In recent years, substantial progress in shape analysis has been achieved through methods that use the spectra and eigenfunctions of discrete Laplace operators. In this work, we study spectra and eigenfunctions of discrete differential operators that can serve as an alternative to discrete Laplacians for applications in shape analysis. We construct such operators as the Hessians of surface energies or deformation energies. In particular, we design a quadratic energy such that, on the one hand, its Hessian equals the Laplace operator if the surface is a part of the Euclidean plane, and, on the other hand, the Hessian eigenfunctions are sensitive to the extrinsic curvature (e.g. sharp bends) on curved
surfaces. Furthermore, we consider eigenvibrations induced by deformation energies, and we derive a closed form representation for the Hessian (at the rest state of the energy) for a general class of deformation energies. Based on these spectra and eigenmodes, we derive two shape signatures. One that measures the similarity of points on a surface, and another that can be used to identify features of surfaces.
This paper presents efficient computational techniques for solving an optimization problem in cardiac defibrillation governed by the monodomain equations. Time-dependent electrical currents injected at different spatial positions act as the control. Inexact Newton-CG methods are used, with reduced gradient computation by adjoint solves. In order to reduce the computational complexity, adaptive mesh refinement for state and adjoint equations is performed. To reduce the high storage and bandwidth demand imposed by adjoint gradient and Hessian-vector evaluations, a lossy compression technique for storing trajectory data is applied. An adaptive choice of quantization tolerance based on error estimates is developed in order to ensure convergence. The efficiency of the proposed approach is demonstrated on numerical examples.
For the solution of optimal control problems governed by nonlinear parabolic PDEs, methods working on the reduced objective functional are often employed to avoid a full
spatio-temporal discretization of the problem. The evaluation of the reduced gradient requires one solve of the state equation forward in time, and one backward solve of
the adjoint equation. The state enters into the adjoint equation, requiring the storage of a full 4D data set. If Newton-CG methods are used, two additional trajectories
have to be stored. To get numerical results which are accurate enough, in many case very fine discretizations in time and space are necessary, which leads to a significant
amount of data to be stored and transmitted to mass storage. Lossy compression methods were developed to overcome the storage problem by reducing the accuracy of the stored
trajectories. The inexact data induces errors in the reduced gradient and reduced Hessian. In this paper, we analyze the influence of such a lossy trajectory compression
method on Newton-CG methods for optimal control of parabolic PDEs and design an adaptive strategy for choosing appropriate quantization tolerances.
Abstract—We present a novel coder for lossless compression
of adaptive multiresolution meshes that exploits their special
hierarchical structure. The heart of our method is a new
progressive connectivity coder that can be combined with
leading geometry encoding techniques. The compressor uses
the parent/child relationships inherent to the hierarchical mesh.
We use the rules that accord to the refinement scheme and
store bits only where it leaves freedom of choice, leading to
compact codes that are free of redundancy. To illustrate our
scheme we chose the widespread red-green refinement, but
the underlying concepts can be directly transferred to other
adaptive refinement schemes as well. The compression ratio of
our method exceeds that of state-of-the-art coders by a factor
of 2 to 3 on most of our benchmark models.
Lifted Domain Colorings
(2009)
Complex-valued functions are fundamental objects in complex analysis, algebra, differential geometry and in many other areas such as numerical mathematics and physics. Visualizing complex functions is a non-trivial task since maps between two-dimensional spaces are involved whose graph would be an unhandy submanifold
in four-dimensional space. The present paper improves the technique of “domain coloring” in several aspects: First, we lift domain coloring from the complex plane to branched Riemann surfaces, which are essentially the
correct domain for most complex functions. Second, we extend domain coloring to the visualization of general 2-valued maps on surfaces. As an application of such general maps we visualize the Gauss map of surfaces as domain colored plots and establish a link to current surface parametrization techniques and texture maps. Third, we adjust the color pattern in domain and in image space to produce higher quality domain colorings. The new color schemes specifically enhance the display of singularities, symmetries and path integrals, and give better qualitative measures of the complex map.
We propose a framework for deformation-based surface modeling that is interactive, robust and intuitive to use. The deformations are described by a non-linear optimization problem that models static states of elastic shapes under external forces which implement the user input. Interactive response is achieved by a combination of model reduction, a robust energy approximation, and an efficient quasi-Newton solver. Motivated by the observation that a typical modeling session requires only a fraction of the full shape
space of the underlying model, we use second and third derivatives of a deformation energy to construct a low-dimensional shape space that forms the feasible set for the optimization. Based on mesh coarsening, we propose an
energy approximation scheme with adjustable approximation quality. The quasi-Newton solver guarantees superlinear convergence without the need of costly Hessian evaluations during modeling. We demonstrate the effectiveness of the approach on different examples including the test suite introduced in [Botsch and Sorkine 2008].
R is a language and environment for statistical computing and graphics. It can be considered an alternative implementation of the S language developed in the 1970s and 1980s for data analysis and graphics (Becker and Chambers, 1984; Becker et al., 1988). The R language is part of the GNU project and offers versions that compile and run on almost every major operating system currently available. We highlight several R packages built specifically for the analysis of neuroimaging data in the context of functional MRI, diffusion tensor imaging, and dynamic contrast-enhanced MRI. We review their methodology and give an overview of their capabilities for neuroimaging. In addition we summarize some of the current activities in the area of neuroimaging software development in R.
We introduce hexagonal global parameterizations, a new
type of surface parameterizations in which parameter lines respect six-fold rotational symmetries (6-RoSy). Such parameterizations enable the tiling of surfaces with nearly regular hexagonal or triangular patterns, and can be used for triangular remeshing.
To construct a hexagonal parameterization on a surface, we provide an automatic algorithm to generate a 6-RoSy field that respects directional and singularity features of the surface. This field is then used to direct a hexagonal global parameterization. The framework, called HexCover, extends the QuadCover algorithm and formulates necessary conditions for hexagonal parameterization.
We demonstrate the usefulness of our geometry-aware global parameterization with applications such as surface tiling with nearly regular textures and geometry patterns, as well as triangular and hexagonal remeshing.
This work concerns the approximation of the shape operator of smooth surfaces in R^3 from polyhedral surfaces. We introduce two generalized shape operators that are vector-valued linear functionals on a Sobolev space of vector fields and can be rigorously defined on smooth and on polyhedral surfaces. We consider polyhedral surfaces that approximate smooth surfaces and prove two types of approximation estimates: one concerning the approximation of the generalized shape operators in the operator norm and one concerning the pointwise approximation of the (classic) shape operator. We show experimental results that confirm our estimates.
This work concerns the approximation of the shape operator of smooth surfaces in $\mathbb{R}^{3}$ from polyhedral surfaces. We introduce two generalized shape operators that are vector-valued linear functionals on a Sobolev space of vector fields and can be rigorously defined on smooth and on polyhedral surfaces. We consider polyhedral surfaces that approximate smooth surfaces and prove two types of approximation estimates: one concerning the approximation of the generalized shape operators in the operator norm and one concerning the pointwise approximation of the (classic) shape operator, including mean and Gaussian curvature, principal curvatures, and principal curvature directions.
The estimates are confirmed by numerical experiments.
Spectral deferred correction methods for solving stiff ODEs are known to
converge rapidly towards the collocation limit solution on equidistant grids,
but show a much less favourable contraction on non-equidistant grids such as
Radau-IIa points. We interprete SDC methods as fixed point iterations for the
collocation system and propose new DIRK-type sweeps for stiff problems based
on purely linear algebraic considerations. Good convergence is recovered also
on non-equidistant grids. The properties of different variants are explored on
a couple of numerical examples.
We analyze a remarkable class of centrally symmetric polytopes, the Hansen
polytopes of split graphs. We confirm Kalai's 3^d-conjecture for such polytopes
(they all have at least 3^d nonempty faces) and show that the Hanner polytopes
among them (which have exactly 3^d nonempty faces) correspond to threshold
graphs. Our study produces a new family of Hansen polytopes that have only
3^d+16 nonempty faces.
In this work, we study the spectra and eigenmodes of the Hessian of various discrete surface energies and discuss applications to shape analysis. In particular, we consider a physical model that describes the vibration modes and frequencies of a surface through the eigenfunctions and eigenvalues of the Hessian of a deformation energy, and we
derive a closed form representation for the Hessian (at the rest state of the energy) for a general class of deformation energies. Furthermore, we design a quadratic energy, such that the eigenmodes of the Hessian of
this energy are sensitive to the extrinsic curvature of the surface. Based on these spectra and eigenmodes, we derive two shape signatures. One that measures the similarity of points on a surface, and another that
can be used to identify features of the surface. In addition, we discuss a
spectral quadrangulation scheme for surfaces.
We introduce a novel method for the construction of discrete conformal mappings from surface meshes of arbitrary topology to the plane. Our approach is based on circle patterns, i.e., arrangements of circles—one for each face—with prescribed intersection angles. Given these angles the circle radii follow as the unique minimizer of a convex energy. The method supports very flexible boundary conditions ranging from free boundaries to control of the boundary shape via prescribed curvatures. Closed meshes of genus zero can be parameterized over the sphere. To parameterize higher genus meshes we introduce cone singularities at designated vertices. The parameter domain is then a piecewise Euclidean surface. Cone singularities can also help to reduce the often very large area distortion of global conformal maps to moderate levels. Our method involves two optimization problems: a quadratic program and the unconstrained minimization of the circle pattern energy. The latter is a convex function of logarithmic radius variables with simple explicit expressions for gradient and Hessian. We demonstrate the versatility and performance of our algorithm with a variety of examples.
We consider Large Deformation Diffeomorphic Metric Mapping of general $m$-currents. After stating an optimization algorithm in the function space of admissable morph generating velocity fields, two innovative aspects in this framework are presented and numerically investigated: First, we spatially discretize the velocity field with conforming adaptive finite elements and discuss advantages of this new approach. Second, we directly compute the temporal evolution of discrete $m$-current attributes.
Despite the success of quad-based 2D surface parameterization methods, effective parameterization algorithms for 3D volumes with cubes, i.e. hexahedral elements, are still missing. CubeCover is a first approach which provides both, a consistent theoretical framework for volume parameterization plus a full pipeline for generating
a hexahedral tessellation of a given volume with boundary aligned cubes which are guided by a frame field.
The input of CubeCover is a tetrahedral volume mesh. First, a frame field is designed with manual input from
the designer. It guides the interior and boundary layout of the parameterization. Then, the parameterization and
the hexahedral mesh are computed so as to align with the given frame field.
CubeCover has similarities to the QuadCover algorithm and extends it from 2D surfaces to 3D volumes. The
paper also provides theoretical results for 3D hexahedral parameterizations and analyses topological properties
of the appropriate function space.
Multiresolution meshes provide an efficient and structured representation of geometric objects. To increase the
mesh resolution only at vital parts of the object, adaptive refinement is widely used. We propose a lossless compression
scheme for these adaptive structures that exploits the parent-child relationships inherent to the mesh
hierarchy. We use the rules that correspond to the adaptive refinement scheme and store bits only where some
freedom of choice is left, leading to compact codes that are free of redundancy. Moreover, we extend the coder to
sequences of meshes with varying refinement. The connectivity compression ratio of our method exceeds that of
state-of-the-art coders by a factor of 2 to 7.
For efficient compression of vertex positions we adapt popular wavelet-based coding schemes to the adaptive
triangular and quadrangular cases to demonstrate the compatibility with our method. Akin to state-of-the-art
coders, we use a zerotree to encode the resulting coefficients. Using improved context modeling we enhanced the
zerotree compression, cutting the overall geometry data rate by 7% below those of the successful Progressive
Geometry Compression. More importantly, by exploiting the existing refinement structure we achieve compression
factors that are 4 times greater than those of coders which can handle irregular meshes.
We introduce FreeLence, a lossless single-rate connectivity compression algorithm for triangle surface meshes. Based upon a geometry-driven traversal scheme we present two novel and simple concepts: free-valence connectivity encoding and entropy coding based on geometric context. Together these techniques yield signicantly smaller rates for connectivity compression than current state of the art approaches - valence-based algorithms and Angle- Analyzer, with an average of 36% improvement over the former and an average of 18% over the latter on benchmark 3D models, combined with the ability to well adapt to the regularity of meshes. We also prove that our algorithm exhibits a smaller worst case entropy
for a class of ”well-behaved” triangle meshes than valence-driven connectivity encoding approaches.
Diffusion weighted imaging is a magnetic resonance based method to investigate
tissue micro-structure especially in the human brain via water diffusion.
Since the standard diffusion tensor model for the acquired data failes in
large portion of the brain voxel more sophisticated models have bee developed.
Here, we report on the package dti and how some of these models
can be used with the package.
Riemann surfaces naturally appear in the analysis of complex functions that are branched over the complex plane. However, they usually possess a complicated topology and are thus hard to understand. We present an algorithm for constructing Riemann surfaces as meshes in R3 from explicitly given branch points with corresponding branch indices. The constructed surfaces cover the complex plane by the canonical
projection onto R2 and can therefore be considered as multivalued graphs
over the plane – hence they provide a comprehensible visualization of the
topological structure. Complex functions are elegantly visualized using domain coloring on
a subset of C. By applying domain coloring to the automatically constructed Riemann surface models, we generalize this approach to deal with functions which cannot be entirely visualized in the complex plane.
A new method for noise removal of arbitrary surfaces
meshes is presented which focuses on the preservation
and sharpening of non-linear geometric features such
as curved surface regions and feature lines. Our method
uses a prescribed mean curvature flow (PMC) for simplicial
surfaces which is based on three new contributions:
1. the definition and efficient calculation of a
discrete shape operator and principal curvature properties
on simplicial surfaces that is fully consistent with
the well-known discrete mean curvature formula, 2. an
anisotropic discrete mean curvature vector that combines
the advantages of the mean curvature normal with
the special anisotropic behaviour along feature lines of
a surface, and 3. an anisotropic prescribed mean curvature
flow which converges to surfaces with an estimated
mean curvature distribution and with preserved nonlinear
features. Additionally, the PMC flow prevents
boundary shrinkage at constrained and free boundary
segments.
We prove an existence and uniqueness theorem for weighted Delaunay triangulations (with non-intersecting site-circles) with prescribed combinatorial type and circle intersection angles. Such weighted Delaunay triangulations can also be interpreted as hyperbolic polyhedra with vertices beyond the infinite boundary. The proof is based on a variational principle. This extends similar work by Rivin on Delaunay triangulations and ideal polyhedra to weighted Delaunay triangulations and hyperideal polyhedra.
It is known that for each combinatorial type of convex 3-dimensional
polyhedra, there is a representative with edges tangent to the unit sphere.
This representative is unique up to projective transformations that fix the unit
sphere. We show that there is a unique representative (up to congruence) with
edges tangent to the unit sphere such that the origin is the barycenter of the
points where the edges touch the sphere.
Modelling incompressible ideal fluids as a finite collection of
vortex filaments is important in physics (super-fluidity, models for the
onset of turbulence) as well as for numerical algorithms used in computer
graphics for the real time simulation of smoke. Here we introduce
a time-discrete evolution equation for arbitrary closed polygons in 3-
space that is a discretisation of the localised induction approximation of
filament motion. This discretisation shares with its continuum limit the
property that it is a completely integrable system. We apply this polygon
evolution to a significant improvement of the numerical algorithms
used in Computer Graphics.
We define a discrete Laplace-Beltrami operator for simplicial surfaces. It depends only on the intrinsic geometry of the surface and its edge weights are positive. Our Laplace operator is similar to the one defined by Pinkall and Polthier (the so called “cotan formula”) except that it is based on the intrinsic Delaunay triangulation of the simplicial surface. This leads to new definitions of discrete harmonic and holomorphic functions, discrete mean curvature, and discrete minimal surfaces.