Shape‐Up: Shaping Discrete Geometry with Projections

We introduce a unified optimization framework for geometry processing based on shape constraints. These constraints preserve or prescribe the shape of subsets of the points of a geometric data set, such as polygons, one‐ring cells, volume elements, or feature curves. Our method is based on two key concepts: a shape proximity function and shape projection operators. The proximity function encodes the distance of a desired least‐squares fitted elementary target shape to the corresponding vertices of the 3D model. Projection operators are employed to minimize the proximity function by relocating vertices in a minimal way to match the imposed shape constraints. We demonstrate that this approach leads to a simple, robust, and efficient algorithm that allows implementing a variety of geometry processing applications, simply by combining suitable projection operators. We show examples for computing planar and circular meshes, shape space exploration, mesh quality improvement, shape‐preserving deformation, and conformal parametrization. Our optimization framework provides a systematic way of building new solvers for geometry processing and produces similar or better results than state‐of‐the‐art methods.     

Modeling 3D Curves of Minimal Energy

Modeling a curve through minimizing its energy yields an overall smooth curve. A common way to model shape features is to perform the minimization subject to a number of interpolation constraints. This way of modeling is attractive because the designer is not bothered with the precise representation of the curve (e.g. control points). However, local shape specification by means of interpolation constraints is very limited. On the other hand, local deformation by repositioning control points is powerful but very laborious, and destroys the minimal energy property. In this paper, deform operators are introduced for 3D curve modeling that have built-in energy terms that have an intuitive effect. These operators allow local shape modification and do justice to the energy minimization way of modeling.     

Extending Collision Avoidance Methods to Consider the Vehicle Shape, Kinematics, and Dynamics of a Mobile Robot

Most collision avoidance methods do not consider the vehicle shape and its kinematic and dynamic constraints, assuming the robot to be point-like and omnidirectional with no acceleration constraints. The contribution of this paper is a methodology to consider the exact shape and kinematics, as well as the effects of dynamics in the collision avoidance layer, since the original avoidance method does not address them. This is achievable by abstracting the constraints from the avoidance methods in such a way that when the method is applied, the constraints already have been considered. This study is a starting point to extend the domain of applicability to a wide range of collision avoidance methods.     

基于NURBS方法的气动外形优化设计

采用NURBS曲线曲面,对钝锥弹头和钝双锥弹体建立参数化曲面模型,取NURBS曲线控制点作为设计参数,应用高超声速面元法求解气动力特性,在给定设计约束下,采用遗传算法进行气动外形优化设计,并对优化结果进行了比较分析。结果表明,采用NURBS方法构造参数化外形,并结合优化技术可方便快速地获得所需最优外形;与应用二次曲线构造参数化外形相比,该方法对弹体形状控制更加灵活,并可局部修改弹头曲线形状。因此,基于NURBS方法发展整套的系统优化设计算法很有现实意义和应用价值。     

基于约束优化的Bézier曲面形状修改

Bézier曲线和曲面广泛应用于CAGD(计算机辅助几何设计)和计算机图形学,对Bézier曲线或者曲面的设计和形状修改是一个重要的问题。研究了基于几何约束的Bézier曲面优化问题,对单点和多点约束的问题,提出了一种通过修改控制点的约束优化方法。用这种方法,通过修改原Bézier曲面的控制点来修改曲面的形状并满足给定的约束条件,同时给出了数值实例,其结果表明,用拉格朗日方法能有效地解决Bézier曲面的形状修改问题。     

Interactive design exploration for constrained meshes

In architectural design, surface shapes are commonly subject to geometric constraints imposed by material, fabrication or assembly. Rationalization algorithms can convert a freeform design into a form feasible for production, but often require design modifications that might not comply with the design intent. In addition, they only offer limited support for exploring alternative feasible shapes, due to the high complexity of the optimization algorithm.We address these shortcomings and present a computational framework for interactive shape exploration of discrete geometric structures in the context of freeform architectural design. Our method is formulated as a mesh optimization subject to shape constraints. Our formulation can enforce soft constraints and hard constraints at the same time, and handles equality constraints and inequality constraints in a unified way. We propose a novel numerical solver that splits the optimization into a sequence of simple subproblems that can be solved efficiently and accurately.Based on this algorithm, we develop a system that allows the user to explore designs satisfying geometric constraints. Our system offers full control over the exploration process, by providing direct access to the specification of the design space. At the same time, the complexity of the underlying optimization is hidden from the user, who communicates with the system through intuitive interfaces.     

A unified approach to optimization of structural members under general constraints

A unified numerical approach, based on a control parameterization technique, for solving structural crosssectional optimization problems is presented. The key factor to the unified formulation lies in the framing of the objective functional and the constraints into the same unified canonical form. Consequently, the different types of objective functionals, geometrical and performance constraints can be treated in the same way, thus paving the path for the problems to be solved under a single approach using a general purpose software. To demonstrate this versatile approach, several illustrative examples of cross-sectional shape optimization of structural members under a variety of constraints were examined.     

Reductions in the search space for deriving a fractal set of an arbitrary shape

At present, the problem of finding a quick and efficient way of representing an arbitrary shape as a set of contraction mappings (an iterated function system) is unresolved. Such a representation is particularly useful in shape representation since the primitives used to construct the shape will automatically have the correct morphology. Several attempts have been made to solve this problem and some of these are discussed. The main difficulty with these approaches is the large size and great complexity of the search space. This paper examines several constraints, all of a low computational complexity, which can be placed on each of the mappings which make up a possible solution. These constraints reduce the search space of four of the six coefficients of a mapping by between 20% and 85%, and of the other two by between 75% and 95% (the size of the reduction depends only on the size of the bounding box of the shape). Since these constraints apply to each mapping of an IFS, their cumulative effect on the search space is substantial. It is anticipated that these reductions in the search space can be used to aid a variety of search algorithms.     

Facial expressions in American sign language: Tracking and recognition

This paper presents work towards recognizing facial expressions that are used in sign language communication. Facial features are tracked to effectively capture temporal visual cues on the signers' face during signing. Face shape constraints are used for robust tracking within a Bayesian framework. The constraints are specified through a set of face shape subspaces learned by Probabilistic Principal Component Analysis (PPCA). An update scheme is also used to adapt to persons with different face shapes. Two tracking algorithms are presented, which differ in the way the face shape constraints are enforced. The results show that the proposed trackers can track facial features with large head motions, substantial facial deformations, and temporary facial occlusions by hand. The tracked results are input to a recognition system comprising Hidden Markov Models (HMM) and a support vector machine (SVM) to recognize six isolated facial expressions representing grammatical markers in American sign language (ASL). Tracking error of less than four pixels (on 640×480 videos) was obtained with probability greater than 90%; in comparison the KLT tracker yielded this accuracy with 76% probability. Recognition accuracy obtained for ASL facial expressions was 91.76% in person dependent tests and 87.71% in person independent tests.     

Constrained 3D shape reconstruction using a combination of surface fitting and registration

We investigate 3D shape reconstruction from measurement data in the presence of constraints. The constraints may fix the surface type or set geometric relations between parts of an object's surface, such as orthogonality, parallelity and others. It is proposed to use a combination of surface fitting and registration within the geometric optimization framework of squared distance minimization (SDM). In this way, we obtain a quasi-Newton like optimization algorithm, which in each iteration simultaneously registers the data set with a rigid motion to the fitting surface and adapts the shape of the fitting surface. We present examples to show the applicability of our method to constrained 3D shape fitting for reverse engineering of CAD models and to high accuracy fitting with kinematic surfaces, which include surfaces of revolution (reconstructed from fragments of archeological pottery) and spiral surfaces, which are fitted to 3D measurement data of shells. Our optimization algorithm can combine registration of multiple scans of an object and model fitting into a single optimization process which is shown to be superior to the traditional procedure, which first registers the data and then fits a model to it.     

Monocular Template-based Reconstruction of Inextensible Surfaces

We present a monocular 3D reconstruction algorithm for inextensible deformable surfaces. It uses point correspondences between a single image of the deformed surface taken by a camera with known intrinsic parameters and a template. The main assumption we make is that the surface shape as seen in the template is known. Since the surface is inextensible, its deformations are isometric to the template. We exploit the distance preservation constraints to recover the 3D surface shape as seen in the image. Though the distance preservation constraints have already been investigated in the literature, we propose a new way to handle them. Spatial smoothness priors are easily incorporated, as well as temporal smoothness priors in the case of reconstruction from a video. The reconstruction can be used for 3D augmented reality purposes thanks to a fast implementation. We report results on synthetic and real data. Some of them are compared to stereo-based 3D reconstructions to demonstrate the efficiency of our method.     

Variational geometric modeling with black box constraints and DAGs

CAD modelers enable designers to construct complex 3D shapes with high-level B-Rep operators. This avoids the burden of low level geometric manipulations. However a gap still exists between the shape that the designers have in mind and the way they have to decompose it into a sequence of modeling steps. To bridge this gap, Variational Modeling enables designers to specify constraints the shape must respect. The constraints are converted into an explicit system of mathematical equations (potentially with some inequalities) which the modeler numerically solves. However, most of available programs are 2D sketchers, basically because in higher dimension some constraints may have complex mathematical expressions. This paper introduces a new approach to sketch constrained 3D shapes. The main idea is to replace explicit systems of mathematical equations with (mainly) Computer Graphics routines considered as Black Box Constraints. The obvious difficulty is that the arguments of all routines must have known numerical values. The paper shows how to solve this issue, i.e.,   how to solve and optimize without equations. The feasibility and promises of this approach are illustrated with the developed DECO (Deformation by Constraints) prototype.     

A consistent formulation for imposing packaging constraints in shape optimization using Vertex Morphing parametrization

This paper aims at imposing no-penetration condition over arbitrary surfaces which act as bounding surfaces, also known as packaging constraints, on the design surface of shape optimization problem. We use Vertex Morphing technique for the shape parametrization. Vertex Morphing is a consistent surface control approach for node-based shape optimization. The suitability of this technique has been assessed and demonstrated for a wide range of engineering applications without geometric shape constraints. In this contribution, a consistent formulation is presented for the implementation of numerous point-wise geometric constraints in four main steps. First, a potential contact between optimization surface points and the bounding surface is identified via the so-called gap function. Second, the shape gradients of objective functions and active constraints are mapped onto the Vertex Morphing’s control space, where the optimization problem is formulated. Third, the linear least squares method is used to project the steepest-descent search direction onto the subspace tangent to the mapped active constraints. Finally, the feasible design update is mapped onto the geometry space. To verify the perfect consistency between the geometry space (where the constraints are formulated) and the control space (where the optimization problem is solved) two applications of CFD shape optimization in the automotive industry are presented.     

Perceptually-motivated shape exaggeration

Image communication would appear more efficient if the visual cases of the concerned parts can be enhanced. One way to achieve this is by local shape exaggeration in rendering. In this paper, we present an interactive scheme for controllable local shape exaggeration. Our approach achieves local, direct, and consistent appearance enhancement by modifying the surface orientation in an intuitive and globally optimized manner with sparse user-specified constraints. Compared with previous approaches, the main contribution of this paper is the introduction of adaptive exaggeration function (AEF), which is capable of modulating the extent of detail enhancement to obtain a satisfactory shape exaggeration result. The AEF model is derived based on a series of experiments. We complement our new approach with a variety of examples, user studies, and provide comparisons with recent approaches.     

Moment-based alignment for shape prior with variational B-spline level set

This paper presents a new shape prior-based implicit active contour model for image segmentation. The paper proposes an energy functional including a data term and a shape prior term. The data term, inspired from the region-based active contour approach, evolves the contour based on the region information of the image to segment. The shape prior term, defined as the distance between the evolving shape and a reference shape, constraints the evolution of the contour with respect to the reference shape. Especially, in this paper, we present shapes via geometric moments, and utilize the shape normalization procedure, which takes into account the affine transformation, to align the evolving shape with the reference one. By this way, we could directly calculate the shape transformation, instead of solving a set of coupled partial differential equations as in the gradient descent approach. In addition, we represent the level-set function in the proposed energy functional as a linear combination of continuous basic functions expressed on a B-spline basic. This allows a fast convergence to the segmentation solution. Experiment results on synthetic, real, and medical images show that the proposed model is able to extract object boundaries even in the presence of clutter and occlusion.     

Distributed formation control with relaxed motion requirements

Heterogeneous formation shape control with interagent bearing and distance constraints involves the design of a distributed control law that ensures the formation moves such that these interagent constraints are achieved and maintained. This paper looks at the design of a distributed control scheme to solve different formation shape control problems in an ambient two‐dimensional space with bearing, distance and mixed bearing and distance constraints. The proposed control law allows the agents in the formation to move in any direction on a half‐plane and guarantees that despite this freedom, the proposed shape control algorithm ensures convergence to a formation shape meeting the prescribed constraints. This work provides an interesting and novel contrast to much of the existing work in formation control where distance‐only constraints are typically maintained and where each agent's motion is typically restricted to follow a very particular path. A stability analysis is sketched, and a number of illustrative examples are also given. Copyright © 2014 John Wiley & Sons, Ltd.     

Contact shape optimization: a bilevel programming approach

We consider the problem of shape optimization of nonlinear elastic solids in contact. The equilibrium of the solid is defined by a constrained minimization problem, where the body energy functional is the objective and the constraints impose the nonpenetration condition. Then the optimization problem can be formulated in terms of a bilevel mathematical program. We describe new optimality conditions for bilevel programming and construct an algorithm to solve these conditions based on Herskovits’ feasible direction interior point method. With this approach we simultaneously carry out shape optimization and nonlinear contact analysis. That is, the present method is a “one shot” technique. We describe some numerical examples solved in a very efficient way. Received July 27, 1999     

Direct shape optimization for strengthening 3D printable objects

Recently there has been an increasing demand for software that can help designers create functional 3D objects with required physical strength. We introduce a generic and extensible method that directly optimizes a shape subject to physical and geometric constraints. Given an input shape, our method optimizes directly its input mesh representation until it can withstand specified external forces, while remaining similar to the original shape. Our method performs physics simulation and shape optimization together in a unified framework, where the physics simulator is an integral part of the optimizer. We employ geometric constraints to preserve surface details and shape symmetry, and adapt a second‐order method with analytic gradients to improve convergence and computation time. Our method provides several advantages over previous work, including the ability to handle general shape deformations, preservation of surface details, and incorporation of user‐defined constraints. We demonstrate the effectiveness of our method on a variety of prinTable 3D objects through detailed simulations as well as physical validations.