Isotopic Implicit Surface Meshing

This paper addresses the problem of piecewise linear approximation of implicit surfaces. We first give a criterion ensuring that the zero-set of a smooth function and the one of a piecewise linear approximation of it are isotopic. Then, we deduce from this criterion an implicit surface meshing algorithm certifying that the output mesh is isotopic to the actual implicit surface. This is the first algorithm achieving this goal in a provably correct way.     

Shape from Shadows: A Hilbert Space Setting

We study the problem of recovering a surface from the shadows it casts on itself when lighted by the sun at various times of the day. Shadows can create both linear and nonlinear information. We will show how to incorporate both types of information in the solution. The problem is formulated and solved in a Hilbert space setting and the spline algorithm interpolating the data that result from the shadows is constructed. This algorithm is optimal in terms of the approximation error and has low cost. We furthermore derive optimal information for this problem.     

Newton's method for constrained optimization

We derive a quadratically convergent algorithm for minimizing a nonlinear function subject to nonlinear equality constraints. We show, following Kaufman [4], how to compute efficiently the derivative of a basis of the subspace tangent to the feasible surface. The derivation minimizes the use of Lagrange multipliers, producing multiplier estimates as a by-product of other calculations. An extension of Kantorovich's theorem shows that the algorithm maintains quadratic convergence even if the basis of the tangent space changes abruptly from iteration to iteration. The algorithm and its quadratic convergence are known but the drivation is new, simple, and suggests several new modifications of the algorithm.     

Computing generalized higher-order Voronoi diagrams on triangulated surfaces

We present an algorithm for computing exact shortest paths, and consequently distance functions, from a generalized source (point, segment, polygonal chain or polygonal region) on a possibly non-convex triangulated polyhedral surface. The algorithm is generalized to the case when a set of generalized sites is considered, providing their distance field that implicitly represents the Voronoi diagram of the sites. Next, we present an algorithm to compute a discrete representation of the distance function and the distance field. Then, by using the discrete distance field, we obtain the Voronoi diagram of a set of generalized sites (points, segments, polygonal chains or polygons) and visualize it on the triangulated surface. We also provide algorithms that, by using the discrete distance functions, provide the closest, furthest and k-order Voronoi diagrams and an approximate 1-Center and 1-Median.     

Quality mesh generation for molecular skin surfaces using restricted union of balls

Quality surface meshes for molecular models are desirable in the studies of protein shapes and functionalities. However, there is still no robust software that is capable to generate such meshes with good quality. In this paper, we present a Delaunay-based surface triangulation algorithm generating quality surface meshes for the molecular skin model. We expand the restricted union of balls along the surface and generate an ε-sampling of the skin surface incrementally. At the same time, a quality surface mesh is extracted from the Delaunay triangulation of the sample points. The algorithm supports robust and efficient implementation and guarantees the mesh quality and topology as well. Our results facilitate molecular visualization and have made a contribution towards generating quality volumetric tetrahedral meshes for the macromolecules.     

Non-manifold surface reconstruction from high-dimensional point cloud data

We present an algorithm capable of reconstructing a non-manifold surface embedded as a point cloud in a high-dimensional space. Our algorithm extends a previously developed incremental method and produces a non-optimal triangulation, but will work for non-orientable surfaces, and for surfaces with certain types of self-intersection. The self-intersections must be ordinary double curves and are fitted locally by intersecting planes using a degenerate quadratic surface. We present the algorithm in detail and provide many examples, including a dataset describing molecular conformations of cyclo-octane.     

An algorithm for surface reconstruction from planar contours using smoothing splines

This paper presents a fast algorithm for constructing a smooth three-dimensional surface over a set of cross-sectional contours. We assume that these sections are perpendicular to the z-axis and first consider the case that the surface can be represented in cylindrical coordinates. An approximation is then determined for r(θ, z) by using tensor product splines which satisfy certain boundary constraints. The algorithm is an extension of an existing semi-automatic surface fitting algorithm. The knots of the spline are chosen automatically but a single parameter is expected to control the tradeoff between closeness of fit and smoothness of fit.Both open and closed surfaces can be represented. In particular we demonstrate the use of a non-linear transformation for obtaining smooth closed surfaces.The algorithm can easily be extended to the reconstruction of surfaces which cannot be represented in cylindrical coordinates. A number of applications are also briefly discussed such as the calculation of volumes and the intersection with other surfaces. We have applied the method in practice to obtain a 3-D integrated image of the cerebral blood vessels and CT view of tumor for stereotactic neurosurgery.     

Adaptive Surface Reconstruction Based on Tensor Product Algebraic Splines

Surface reconstruction from unorganized data points is a challenging problem in Computer Aided Design and Geometric Modeling. In this paper, we extend the mathematical model proposed by Juttler and Felis (Adv. Comput. Math., 17 (2002), pp. 135-152) based on tensor product algebraic spline surfaces from fixed meshes to adaptive meshes. We start with a tensor product algebraic B-spline surface defined on an initial mesh to fit the given data based on an optimization approach. By measuring the fitting errors over each cell of the mesh, we recursively insert new knots in cells over which the errors are larger than some given threshold, and construct a new algebraic spline surface to better fit the given data locally. The algorithm terminates when the error over each cell is less than the threshold. We provide some examples to demonstrate our algorithm and compare it with Jiittler's method. Examples suggest that our method is effective and is able to produce reconstruction surfaces of high quality.AMS subject classifications: 65D17     

Conformal Wasserstein distances: Comparing surfaces in polynomial time

We present a constructive approach to surface comparison realizable by a polynomial-time algorithm. We determine the “similarity” of two given surfaces by solving a mass-transportation problem between their conformal densities. This mass transportation problem differs from the standard case in that we require the solution to be invariant under global Möbius transformations. We present in detail the case where the surfaces to compare are disk-like; we also sketch how the approach can be generalized to other types of surfaces.     

Optimal System of Loops on an Orientable Surface

Every compact orientable boundaryless surface M can be cut along simple loops with a common point v₀, pairwise disjoint except at v₀, so that the resulting surface is a topological disk; such a set of loops is called a {\it system of loops} for M. The resulting disk may be viewed as a polygon in which the sides are pairwise identified on the surface; it is called a polygonal schema. Assuming that M is a combinatorial surface, and that each edge has a given length, we are interested in a shortest (or optimal) system of loops homotopic to a given one, drawn on the vertex-edge graph of M. We prove that each loop of such an optimal system is a shortest loop among all simple loops in its homotopy class. We give an algorithm to build such a system, which has polynomial running time if the lengths of the edges are uniform. As a byproduct, we get an algorithm with the same running time to compute a shortest simple loop homotopic to a given simple loop.     

DECUHR: an algorithm for automatic integration of singular functions over a hyperrectangular region

We describe an automatic cubature algorithm for functions that have a singularity on the surface of the integration region. The algorithm combines an adaptive subdivision strategy with extrapolation. The extrapolation uses a non-uniform subdivision that can be directly incorporated into the subdivision strategy used for the adaptive algorithm. The algorithm is designed to integrate a vector function over ann-dimensional rectangular region and a FORTRAN implementation is included.Supported by the Norwegian Research Council for Science and the Humanities.     

Plane viscous incompressible flow in regions with a free boundary

We consider the deformation of a fluid body under the action of surface tension. The apparatus of hydrodynamic potentials is applied to reduce the problem to integrodifferential equations of second kind. An algorithm is constructed that determines the deformation of the fluid body successively in time. Results of numerical calculations are reported. In particular, the problem of deformation of a fluid ellipse under the action of surface tension is analyzed.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 56, pp. 91–97, 1985.     

Uniformly Distributed Circular Porous Pattern Generation on Surface for 3D Printing

We present an algorithm for uniformly distributed circular porous pattern generation on surface for three-dimensional (3D) printing using a phase-field model. The algorithm is based on the narrow band domain method for the nonlocal Cahn–Hilliard (CH) equation on surfaces. Surfaces are embedded in 3D grid and the narrow band domain is defined as the neighborhood of surface. It allows one can perform numerical computation using the standard discrete Laplacian in 3D instead of the discrete surface Laplacian. For complex surfaces, we reconstruct them from point cloud data and represent them as the zero-level set of their discrete signed distance functions. Using the proposed algorithm, we can generate uniformly distributed circular porous patterns on surfaces in 3D and print the resulting 3D models. Furthermore, we provide the test of accuracy and energy stability of the proposed method.     

多幅图像恢复有高光和阴影物体的三维表面

提出一种在多光源下多幅图像来恢复有高光和阴影物体三维表面的方法.对有高光和阴影图片恢复物体的三维表面,物体表面可以认为是L am bertian模型加上高光阴影区域的混合模型.     

A degree bound for families of rational curves on surfaces

We give an upper bound for the degree of rational curves in a family that covers a given birationally ruled surface in projective space. The upper bound is stated in terms of the degree, sectional genus and arithmetic genus of the surface. We introduce an algorithm for constructing examples where the upper bound is tight. As an application of our methods we improve an inequality on lattice polygons.     

Reconstruction Using Witness Complexes

We present a novel reconstruction algorithm that, given an input point set sampled from an object S, builds a one-parameter family of complexes that approximate S at different scales. At a high level, our method is very similar in spirit to Chew’s surface meshing algorithm, with one notable difference though: the restricted Delaunay triangulation is replaced by the witness complex, which makes our algorithm applicable in any metric space. To prove its correctness on curves and surfaces, we highlight the relationship between the witness complex and the restricted Delaunay triangulation in 2d and in 3d. Specifically, we prove that both complexes are equal in 2d and closely related in 3d, under some mild sampling assumptions.     

Optimal design of a fin in steady-state

A fin serves as an extended surface to enhance the heat transfer from a larger heated mass to which it is attached. We consider a fin in steady-state and find its shape that maximizes the efficiency. Our approach is based on a piecewise linear approximation of design. We develop the corresponding algorithm and conduct numerical experiments. Our optimization problem is similar but not identical to the problem studied by L. Hanin. We discuss the applicability of Schmidt’s hypothesis for our model. This paper is an extension of the previous authors’ paper where we considered the shape of the fin that minimizes the cooling time of a heated mass.     

Threshold Dynamics for Networks with Arbitrary Surface Tensions

We present and study a new algorithm for simulating the N‐phase mean curvature motion for an arbitrary set of (isotropic) surface tensions. The departure point is the threshold dynamics algorithm of Merriman, Bence, and Osher for the two‐phase case. A new energetic interpretation of this algorithm allows us to extend it in a natural way to the case of N phases, for arbitrary surface tensions and arbitrary (isotropic) mobilities. For a large class of surface tensions, the algorithm is shown to be consistent in the sense that at every time step, it decreases an energy functional that is an approximation (in the sense of Gamma convergence) of the interfacial energy. A broad range of numerical tests shows good convergence properties. An important application is the motion of grain boundaries in polycrystalline materials: It is also established that the above‐mentioned large class of surface tensions contains the Read‐Shockley surface tensions, both in the two‐dimensional and three‐dimensional settings.© 2015 Wiley Periodicals, Inc.     

Analysing differences between algorithm configurations through ablation

Developers of high-performance algorithms for hard computational problems increasingly take advantage of automated parameter tuning and algorithm configuration tools, and consequently often create solvers with many parameters and vast configuration spaces. However, there has been very little work to help these algorithm developers answer questions about the high-quality configurations produced by these tools, specifically about which parameter changes contribute most to improved performance. In this work, we present an automated technique for answering such questions by performing ablation analysis between two algorithm configurations. We perform an extensive empirical analysis of our technique on five scenarios from propositional satisfiability, mixed-integer programming and AI planning, and show that in all of these scenarios more than 95 % of the performance gains between default configurations and optimised configurations obtained from automated configuration tools can be explained by modifying the values of a small number of parameters (1–4 in the scenarios we studied). We also investigate the use of our ablation analysis procedure for producing configurations that generalise well to previously-unseen problem domains, as well as for analysing the structure of the algorithm parameter response surface near and between high-performance configurations.