Analysis of planar shapes using geodesic paths on shape spaces

For analyzing shapes of planar, closed curves, we propose differential geometric representations of curves using their direction functions and curvature functions. Shapes are represented as elements of infinite-dimensional spaces and their pairwise differences are quantified using the lengths of geodesics connecting them on these spaces. We use a Fourier basis to represent tangents to the shape spaces and then use a gradient-based shooting method to solve for the tangent that connects any two shapes via a geodesic. Using the Surrey fish database, we demonstrate some applications of this approach: 1) interpolation and extrapolations of shape changes, 2) clustering of objects according to their shapes, 3) statistics on shape spaces, and 4) Bayesian extraction of shapes in low-quality images.     

Shortest polygonal paths in space

A classical problem of geometry is the following: given a convex polygon in the plane, find an inscribed polygon of shortest circumference. In this paper we generalize this problem to arbitrary polygonal paths in space and consider two cases: in the “open” case the wanted path of shortest length can have different start and end point, whereas in the “closed” case these two points must coincide. We show that finding such shortest paths can be reduced to finding a shortest path in a planar “channel”. The latter problem can be solved by an algorithm of linear-time complexity in the open as well in the closed case. Finally, we deal with constrained problems where the wanted path has to fulfill additional properties; in particular, if it has to pass straight through a further point, we show that the length of such a constrained polygonal path is a strictly convex function of some angle α, and we derive an algorithm for determining such constrained polygonal paths efficiently.     

An optimization-driven approach for computing geodesic paths on triangle meshes

There are many application scenarios where we need to refine an initial path lying on a surface to be as short as possible. A typical way to solve this problem is to iteratively shorten one segment of the path at a time. As local approaches, they are conceptually simple and easy to implement, but they converge slowly and have poor performance on large scale models. In this paper, we develop an optimization driven approach to improve the performance of computing geodesic paths. We formulate the objective function as the total length and adopt the L-BFGS solver to minimize it. Computational results show that our method converges with super-linear rate, which significantly outperforms the existing methods. Moreover, our method is flexible to handle anisotropic metric, non-uniform density function, as well as additional user-specified constraints, such as coplanar geodesics and equally-spaced geodesic helical curves, which are challenging to the existing local methods.     

Constructing a space from the geodesic equations

Given a space with a metric tensor defined on it, it is easy to write down the system of geodesic equations on it by using the formula for the Christoffel symbols in terms of the metric coefficients. In this paper the inverse problem, of reconstructing the space from the geodesic equations is addressed. A procedure is developed for obtaining the metric tensor explicitly from the Christoffel symbols. The procedure is extended for determining if a second order quadratically semi-linear system can be expressed as a system of geodesic equations, provided it has terms only quadratic in the first derivative apart from the second derivative term. A computer code has been developed for dealing with large systems of geodesic equations.

Program summary

Program title: geodesicCOMMENTED.nbCatalogue identifier: AEBA_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEBA_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 373No. of bytes in distributed program, including test data, etc.: 3641Distribution format: tar.gzProgramming language: MATHEMATICAComputer: Computers that run MATHEMATICAOperating system: MATHEMATICA runs under Linux and windowsRAM: Minimum of 512 kbytesClassification: 1.5Nature of problem: The code we have developed calculates the space when the geodesic equations are given.Solution method: The code gives the user the option of selecting a subset of the metric tensor required for constructing the Christoffel symbols. This system is over-determined hence the results are not unique.Running time: Dependent on the RAM available and complexity of the metric tensor.     

Constrained design of polynomial surfaces from geodesic curves

In a recent work, Wang et al. [Wang G, Tang K, Tai CH. Parametric representation of a surface pencil with common spatial geodesic. Computer-Aided Design 2004;36(5): 447–59] discuss a constrained design problem appearing in the textile and shoe industry for garment design. Given a model and size, the characteristic curve called girth is usually fixed, and preferably should be a geodesic for manufacturing reasons. The designer must preserve this girth, being allowed to modify other areas according to aesthetic criteria. We present a practical method to construct polynomial surfaces from a polynomial geodesic or a family of geodesics, by prescribing tangent ribbons. Differently from previous procedures, we identify the existing degrees of freedom in terms of control points, and our method yields parametric polynomial surfaces that can be incorporated into commercial CAD programs. The extension to rational geodesics is also outlined.     

Symmetry discovery and retrieval of nonrigid 3D shapes using geodesic skeleton paths

Multimedia Tools and Applications - In this paper, we propose a skeleton path based approach for symmetry discovery and retrieval of nonrigid 3D shapes. The main idea is to match skeleton graphs by...     

Constant cusp height tool paths as geodesic parallels on an abstract Riemannian manifold

In free-form surface milling, cusps on a part surface need to be regulated. They should be small enough for precision purposes. On the other hand, we should maintain high enough cusps so as not to waste effort making unnecessary cuts. A widely accepted practice is to maintain a constant cusp height over the surface. This paper introduces a new approach to generating constant cusp height tool paths. First, we define a Riemannian manifold by assigning a new metric to a part surface without embedding. This new metric is constructed from the curvature tensors of a part and a tool surface, which we refer to as a cusp-metric. Then, we construct geodesic parallels on the new Riemannian manifold. We prove that a selection from such a family of geodesic parallels constitutes a “rational” approximation of accurate constant cusp height tool paths.     

Optimal hole shape for minimum stress concentration using parameterized geometry models

The goal of this work is to obtain optimal hole shape for minimum stress concentration in two-dimensional finite plates using parameterized geometry models. The boundary shape for a hole is described by two families of smooth curves: one is a “generalized circular” function with powers as two parameters; the other one is a “generalized elliptic” function a and b are ellipse axes) with powers as two parameters and one of the ellipse axes as the third parameter. Special attention is devoted to the practicability of parameterized equations and the corresponding optimal results under the condition with and without the curvature radius constraint. A number of cases were examined to test the effectiveness of the parameterized equations. The numerical examples show that extremely good results can be obtained under the conditions with and without curvature radius constraint, as compared to the known solutions in the literature. The geometries of the optimized holes are presented in a form of compact parametric functions, which are suitable for use and test by designers. It is anticipated that the implementation of the suggested parameterized equations would lead to considerable improvements in optimizing hole shape with high quality.     

A GA-based design space exploration framework for parameterized system-on-a-chip platforms

The constant increase in levels of integration and reduction in the time-to-market has led to the definition of new methodologies, which lay emphasis on reuse. One emerging approach in this context is platform-based design. The basic idea is to avoid designing a chip from scratch. Some portions of the chip's architecture are predefined for a specific type of application. This implies that the basic micro-architecture of the implementation is essentially "fixed," i.e., the principal components should remain the same within a certain degree of parameterization. Many researchers predict that platforms will take the lion's share of the integrated circuit market. In this paper, we propose an approach based on genetic algorithms for exploring the design space of parameterized system-on-a-chip (SOC) platforms. Our strategy focuses on exploration of the architectural parameters of the processor, memory subsystem and bus, making up the hardware kernel of a parameterized SOC platform for the design of embedded systems with strict power consumption and performance constraints. The approach has been validated on two different parameterized architectures: one based on a RISC processor and another based on a parameterized very long instruction word architecture. The results obtained on a suite of benchmarks for embedded applications are discussed in terms of both accuracy and efficiency. As far as accuracy is concerned, the approach gives solutions uniformly distributed in a region less than 1% from the Pareto-optimal front. As regards efficiency, the exploration times required by the approach are up to 20 times shorter than those required by one of the most efficient and widely referenced approaches in the literature.     

Boolean surfaces with shape constraints

In this paper, we present a new method for the construction of parametric surfaces reproducing an object from a set of spatial data. We adopt a hybrid scheme, based on the Boolean sum of variable degree spline operators, which both interpolate a set of grid lines and approximate the data. As usual the variable degrees can be chosen to satisfy proper shape constraints.     

Additive manufacturing scanning paths optimization using shape optimization tools

Structural and Multidisciplinary Optimization - This paper investigates path planning strategies for additive manufacturing processes such as powder bed fusion. The state of the art mainly studies...     

Incorporating shape prior into geodesic active contours for detecting partially occluded object

A new method to incorporate shape prior knowledge into geodesic active contours for detecting partially occluded object is proposed in this paper. The level set functions of the collected shapes are used as training data. They are projected onto a low dimensional subspace using PCA and their distribution is approximated by a Gaussian function. A shape prior model is constructed and is incorporated into the geodesic active contour formulation to constrain the contour evolution process. To balance the strength between the image gradient force and the shape prior force, a weighting factor is introduced to adaptively guide the evolving curve to move under both forces. The curve converges with due consideration of both local shape variations and global shape consistency. Experimental results demonstrate that the proposed method makes object detection robust against partial occlusions.     

Deformation similarity measurement in quasi-conformal shape space

This paper presents a novel approach based on the shape space concept to classify deformations of 3D models. A new quasi-conformal metric is introduced which measures the curvature changes at each vertex of each pose during the deformation. The shapes with similar deformation patterns follow a similar deformation curve in shape space. Energy functional of the deformation curve is minimized to calculate the geodesic curve connecting two shapes on the shape space manifold. The geodesic distance illustrates the similarity between two shapes, which is used to compute the similarity between the deformations. We applied our method to classify the left ventricle deformations of myopathic and control subjects, and the sensitivity and specificity of our method were 88.8% and 85.7%, which are higher than other methods based on the left ventricle cavity, which shows our method can quantify the similarity and disparity of the left ventricle motion well.     

State space reduction in modeling checking parameterized cache coherence protocol by two-dimensional abstraction

Scalability of cache coherence protocol is a key component in future shared-memory multi-core or multi-processor systems. The state space explosion is the first hurdle while applying model-checking to scalable protocols. In order to validate parameterized cache coherence protocols effectively, we present a new method of reducing the state space of parameterized systems, two-dimensional abstraction (TDA). Drawing inspiration from the design principle of parameterized systems, an abstract model of an unbounded system is constructed out of finite states. The mathematical principles underlying TDA is presented. Theoretical reasoning demonstrates that TDA is correct and sound. An example of parameterized cache coherence protocol based on MESI illustrates how to produce a much smaller abstract model by TDA. We also demonstrate the power of our method by applying it to various well-known classes of protocols. During the development of TH-1A supercomputer system, TDA was used to verify the coherence protocol in FT-1000 CPU and showed the potential advantages in reducing the verification complexity.     

Algorithmic shape modeling with subdivision surfaces

We present methods for synthesizing 3D shape features on subdivision surfaces using multi-scale procedural techniques. Multi-scale synthesis is a powerful approach for creating surfaces with different levels of detail. Our methods can also blend multiple example multi-resolution surfaces, including procedurally defined surfaces as well as captured models.     

Navigating in a shape space of registered models

New product development involves people with different backgrounds. Designers, engineers, and consumers all have different criteria, and these criteria interact. Early concepts evolve in this kind of collaborative context, and there is a need for dynamic visualization of the interaction between design shape and other shape-related design criteria. In this paper, a Morphable Model is defined from simplified representations of suitably chosen real cars, providing a continuous shape space to navigate, manipulate, and visualize. Physical properties and consumer-provided scores for the real cars (such as 'weight' and 'sportiness') are estimated for new designs across the shape space. This coupling allows one to manipulate the shape directly while reviewing the impact on estimated criteria, or conversely, to manipulate the criterial values of the current design to produce a new shape with more desirable attributes.     

Generalized shape operators on polyhedral surfaces

This work concerns the approximation of the shape operator of smooth surfaces in R³ 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.     

Finding shortest paths on surfaces using level sets propagation

We present a new algorithm for determining minimal length paths between two regions on a three dimensional surface. The numerical implementation is based on finding equal geodesic distance contours from a given area. These contours are calculated as zero sets of a bivariate function designed to evolve so as to track the equal distance curves on the given surface. The algorithm produces all paths of minimal length between the source and destination areas on the surface given as height values on a rectangular grid