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.     

Fast approximate geodesic paths on triangle mesh

We present a new algorithm to compute a geodesic path over a triangle mesh.Based on Novotni's propagating wavefront method which is similar to the well known Dijkstra algorithm,we made some improvements which Novotni had missed and we also gave the method to find out the geodesic path which Novotni had not.It can handle both convex and non-convex surfaces or even with boundaries.Experiment results show that our method works very well both in efficiency and precision.     

A fast propagation scheme for approximate geodesic paths

Geodesic paths on surfaces are indispensable in many research and industrial areas, including architectural and aircraft design, human body animation, robotic path planning, terrain navigation, and reverse engineering. 3D models in these applications are typically large and complex. It is challenging for existing geodesic path algorithms to process large-scale models with millions of vertices. In this paper, we focus on the single-source geodesic path problem, and present a novel framework for efficient and approximate geodesic path computation over triangle meshes. The algorithm finds and propagates paths based on a continuous Dijkstra strategy with a two-stage approach to compute a path for each propagating step. Starting from an initial path for each step, its shape is firstly optimized by solving a sparse linear system and then the output floating path is projected to the surface to obtain the refined one for further propagation. We have extensively evaluated our algorithms on a number of 3D models and also compared their performance against existing algorithms. Such evaluation and comparisons indicate our algorithm is fast and produces acceptable accuracy.     

一种新颖的测地距傅立叶轮廓描述符

在传统的用于图像检索的傅里叶轮廓描述符的基础上,提出了一种新颖的、基于图像轮廓的测地距傅里叶描述符,并在标准图像轮廓数据库MPEG-7上进行了测试。实验结果表明这种轮廓描述符在性能上优于其他基于图像轮廓的傅里叶描述符。     

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.     

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.     

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.     

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.     

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.     

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.     

Including shape handles in recursive subdivision surfaces

In the present paper, the problem of the generation of an interpolating surface for a given, general polyhedron is studied. The surface must interpolate the set of vertices of the initial polyhedron, and allow a certain shape control. A two-step process based on a topological modification of the polyhedron, and a subsequent biquadratic recursive subdivision is used. It allows the definition of a set of scalar shape handles associated to the initial vertices, that do not affect the interpolatory properties of the surface. Their effect on the quality of the final shape is discussed, and an iterative algorithm for the computation of an optimal set of shape handles is proposed.     

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.     

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.     

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.