High quality refinable G‐splines for locally quad‐dominant meshes with T‐gons

Polyhedral modeling and re‐meshing algorithms use T‐junctions to add or remove feature lines in a quadrilateral mesh. In many ways this is akin to adaptive knot insertion in a tensor‐product spline, but differs in that the designer or meshing algorithm does not necessarily protect the consistent combinatorial structure that is required to interpret the resulting quad‐dominant mesh as the control net of a hierarchical spline – and so associate a smooth surface with the mesh as in the popular tensor‐product spline paradigm. While G‐splines for multi‐sided holes or generalized subdivision can, in principle, convert quad‐dominant meshes with T‐junctions into smooth surfaces, they do not preserve the two preferred directions and so cause visible shape artifacts. Only recently have n‐gons with T‐junctions (T‐gons) in unstructured quad‐dominant meshes been recognized as a distinct challenge for generalized splines. This paper makes precise the notion of locally quad‐dominant mesh as quad‐meshes including τ‐nets, i.e. T‐gons surrounded by quads; and presents the first high‐quality G‐spline construction that can use τ‐nets as control nets for spline surfaces suitable, e.g., for automobile outer surfaces. Remarkably, T‐gons can be neighbors, separated by only one quad, both of T‐gons and of points where many quads meet. A τ‐net surface cap consists of 16 polynomial pieces of degree (3,5) and is refinable in a way that is consistent with the surrounding surface. An alternative, everywhere bi‐3 cap is not formally smooth, but achieves the same high‐quality highlight line distribution.     

Inverse optimal stabilization for stochastic nonlinear systems whose linearizations are not stabilizable

After considering the stabilization of a class of high-order stochastic nonlinear systems which are neither necessarily feedback linearizable nor affine in the control input, in this brief paper, we further address the problem of state-feedback inverse optimal stabilization in probability, i.e., our redesigned stabilizing backstepping controller is also optimal with respect to meaningful cost functionals.     

Note on curve and surface energies

Energies of curves and surfaces play a prominent role as fairness functionals in geometric modeling and computer-aided geometric design. In this paper we present a particular discrete surface energy which is expressible in terms of curve energies, and thus particularly appropriate for digital elevation data smoothing with tolerance zone constraints. We also discuss other geometrically meaningful surface energies in the context of invariant theory.     

Surfaces parametrized by the normals

For a surface with non vanishing Gaussian curvature the Gauss map is regular and can be inverted. This makes it possible to use the normal as the parameter, and then it is trivial to calculate the normal and the Gauss map. This in turns makes it easy to calculate offsets, the principal curvatures, the principal directions, etc. Such a parametrization is not only a theoretical possibility but can be used concretely. One way of obtaining this parametrization is to specify the support function as a function of the normal, i.e., as a function on the unit sphere. The support function is the distance from the origin to the tangent plane and the surface is simply considered as the envelope of its family of tangent planes. Suppose we are given points and normals and we want a C ^k -surface interpolating these data. The data gives the value and gradients of the support function at certain points (the given normals) on the unit sphere, and the surface can be defined by determining the support function as a C ^k function interpolating the given values and gradients.     

Interpolatory,solid subdivision of unstructured hexahedral meshes

This paper presents a new, volumetric subdivision scheme for interpolation of arbitrary hexahedral meshes. To date, nearly every existing volumetric subdivision scheme is approximating, i.e., with each application of the subdivision algorithm, the geometry shrinks away from its control mesh. Often, an approximating algorithm is undesirable and inappropriate, producing unsatisfactory results for certain applications in solid modeling and engineering design (e.g., finite element meshing). We address this lack of smooth, interpolatory subdivision algorithms by devising a new scheme founded upon the concept of tri-cubic Lagrange interpolating polynomials. We show that our algorithm is a natural generalization of the butterfly subdivision surface scheme to a tri-variate, volumetric setting.     

Scattered Data Interpolation Using Data Dependant Optimization Techniques

Interpolation of scattered data has many applications in different areas. Recently, this problem has gained a lot of interest for CAD applications, in combination with the process of reverse engineering, i.e., the construction of CAD models for existing objects. Until now, no method for scattered data interpolation with a bivariate function has produced surface formats that can be directly integrated into a CAD system. Additionally many of the existing interpolation schemes exhibit undesirable curvature distribution of the reconstructed surface. In this paper we present a method for scattered data interpolation producing tensor–product B-splines with high quality curvature distribution. This method first determines the knot vectors in a way that guarantees the existence of an interpolating B-spline. In a second step the degrees of freedom not specified by the interpolation constraints are automatically set using a data dependent optimization technique. Examples demonstrate the quality of the resulting interpolants w.r.t. curvature distribution and approximation of known surfaces.     

Texturing fluids

We present a novel technique for synthesizing textures over dynamically changing fluid surfaces. We use both image textures as well as bump maps as example inputs. Image textures can enhance the rendering of the fluid by either imparting realistic appearance to it or by stylizing it, whereas bump maps enable the generation of complex micro-structures on the surface of the fluid that may be very difficult to synthesize using simulation. To generate temporally coherent textures over a fluid sequence, we transport texture information, i.e. color and local orientation, between free surfaces of the fluid from one time step to the next. This is accomplished by extending the texture information from the first fluid surface to the 3D fluid domain, advecting this information within the fluid domain along the fluid velocity field for one time step, and interpolating it back onto the second surface -- this operation, in part, uses a novel vector advection technique for transporting orientation vectors. We then refine the transported texture by performing texture synthesis over the second surface using our "surface texture optimization" algorithm, which keeps the synthesized texture visually similar to the input texture and temporally coherent with the transported one. We demonstrate our novel algorithm for texture synthesis on dynamically evolving fluid surfaces in several challenging scenarios.     

Exact Constraint Satisfaction for Truly Seamless Parametrization

In the field of global surface parametrization a recent focus has been on so‐called seamless parametrization. This term refers to parametrization approaches which, while using an atlas of charts to enable the handling of surfaces of arbitrary topology, relate the parametrization across the cuts between charts via transition functions from special classes of transformations. This effectively makes the cuts invisible to applications which are invariant to these specific transformations in some sense. In actual implementations of these parametrization approaches, however, these restrictions are obeyed only approximately; errors stem from the tolerances of numerical solvers employed and, ultimately, from the limited accuracy of floating point arithmetic. In practice, robustness issues arise from these flaws in the seamlessness of a parametrization, no matter how small. We present a robust global algorithm that turns a given approximately seamless parametrization into an exactly seamless one ‐ that still is representable by standard floating point numbers. It supports common practically relevant additional constraints regarding boundary and feature curve alignment or isocurve connectivity, and ensures that these are likewise fulfilled exactly. This allows subsequent algorithms to operate robustly on the resulting truly seamless parametrization. We believe that the core of our method will furthermore be of benefit in a broader range of applications involving linearly constrained numerical optimization.     

A simple method for interpolating meshes of arbitrary topology by Catmull–Clark surfaces

Interpolating an arbitrary topology mesh by a smooth surface plays important role in geometric modeling and computer graphics. In this paper we present an efficient new algorithm for constructing Catmull–Clark surface that interpolates a given mesh. The control mesh of the interpolating surface is obtained by one Catmull–Clark subdivision of the given mesh with modified geometric rule. Two methods—push-back operation based method and normal-based method—are presented for the new geometric rule. The interpolation method has the following features: (1) Efficiency: we obtain a generalized cubic B-spline surface to interpolate any given mesh in a robust and simple manner. (2) Simplicity: we use only simple geometric rule to construct control mesh for the interpolating subdivision surface. (3) Locality: the perturbation of a given vertex only influences the surface shape near this vertex. (4) Freedom: for each edge and face, there is one degree of freedom to adjust the shape of the limit surface. These features make interpolation using Catmull–Clark surfaces very simple and thus make the method itself suitable for interactive free-form shape design.     

Interactive Shape Control of Interpolating B-splines

This paper presents a new methodfor providing interactive shape control of interpolating B-splines. The CAD designer can directly interact with geometric entities defined on the B-spline at any interpolated data point; shape adjustments can be performed either globally or locally. Our approach is based on Bλ-splines of order k (λ,k ≥1), i.e. λ-reparametrized, classical B-splines. The method presented can be easily generalised to surfaces defined either as tensor products or by using the skinning technique; interactive shape control can be provided in both surface parametric directions.     

Data Dependent Thin Plate Energy and its use in Interactive Surface Modeling

When modeling spline surfaces of complex shape, one has to deal with an overwhelming number of control points. Modeling by direct manipulation of the control points is a tedious task. In particular, it is very difficult to maintain a generally pleasant looking surface shape. It becomes therefore increasingly important to build tools that allow the designer to specify only a few geometric constraints while automatically determining the explicit representation of the surface. The basic concept of such a tool is simple. In a first step one has to somehow measure the “fairness” (=quality) of a surface. Once this is achieved, an optimization process selects the one surface with optimal fairness from all surfaces satisfying the user specified geometric constraints. To measure the fairness, thin plate energy functionals are a good choice. However, for interactive use these functionals are far too complex. W e will present appropriate approximations to these functionals that allow an optimization nearly in real time. Thefunctionals are obtained by introducing reference surfaces thus leading to data dependent, quadratic approximations to the exact thin plate energy functionals. We apply the method to interactive surface manipulations based on energy constraints.     

A Greedy Algorithm for Decomposing Convex Structuring Elements

This paper presents a greedy algorithm for decomposing convex structuring elements as sequence of Minkowski additions of subsets of the elementary square (i.e., the 3 × 3 square centered at the origin). The technique proposed is very simple and it is based on algebraic and geometric properties of Minkowski additions. Besides its simplicity, the advantage of this new technique over other known algorithms is that it generates a minimal sequence of not necessarily convex subsets of the elementary square. Thus, subsets with smaller cardinality are generated and a faster implementation of the corresponding dilations and erosions can be achieved. Experimental results, proof of correctness and analysis of computational time complexity of the algorithm are also given.     

Loop Subdivision Surface Based Progressive Interpolation

A new method for constructing interpolating Loop subdivision surfaces is presented. The new method is an extension of the progressive interpolation technique for B-splines. Given a triangular mesh M, the idea is to iteratively upgrade the vertices of M to generate a new control mesh M such that limit surface of M would interpolate M. It can be shown that the iterative process is convergent for Loop subdivision surfaces. Hence, the method is well-defined. The new method has the advantages of both a local ...     

Mesh Optimization Using Global Error with Application to Geometry Simplification

This paper presents a linear running time optimization algorithm for meshes with subdivision connectivity, e.g., subdivision surfaces. The algorithm optimizes a model using a metric defined by the user. Two functionals are used to build the metric: a rate functional and a distortion (i.e. error) functional. The distortion functional defines the error function to minimize, whereas the rate functional defines the minimization constraint. The algorithm computes approximations within this metric using jointly global error and an optimal vertex selection technique inspired from optimal tree pruning algorithms used in compression. We present an update mechanism, that we name merging domain intersections (MDIs), allowing the control of global error through the optimization process at low cost. Our method has application in progressive model decomposition, compression, rendering, and finite element methods. We apply our method to geometry simplification and present an algorithm to compute a decomposition of a model into a multiresolution hierarchy in O(n log n) time using global error, where n is the number of vertices in the full-resolution model. We show that a direct approach, i.e. not using MDIs, recomputing global error has at least cost O(n²). We analyze the optimality of the algorithm and give several for its properties. We present results for semi-regular meshes obtained from approximation of subdivision surfaces whose connectivity is obtain from (triangulated) quadrilateral quadrisection (e.g. 4-8 or Catmull-Clark subdivision).     

Shape aware normal interpolation for curved surface shading from polyhedral approximation

Independent interpolation of local surface patches and local normal patches is an efficient way for fast rendering of smooth curved surfaces from rough polyhedral meshes. However, the independently interpolating normals may deviate greatly from the analytical normals of local interpolating surfaces, and the normal deviation may cause severe rendering defects when the surface is shaded using the interpolating normals. In this paper we propose two novel normal interpolation schemes along with interpolation of cubic Bézier triangles for rendering curved surfaces from rough triangular meshes. Firstly, the interpolating normal is computed by a Gregory normal patch to each Bézier triangle by a new definition of quadratic normal functions along cubic space curves. Secondly, the interpolating normal is obtained by blending side-vertex normal functions along side-vertex parametric curves of the interpolating Bézier surface. The normal patches by these two methods can not only interpolate given normals at vertices or boundaries of a triangle but also match the shape of the local interpolating surface very well. As a result, more realistic shading results are obtained by either of the two new normal interpolation schemes than by the traditional quadratic normal interpolation method for rendering rough triangular meshes.     

Volumes with piecewise quadratic medial surface transforms: Computation of boundaries and trimmed offsets

MOS surfaces (i.e., medial surface transforms obeying a sum of squares condition) are rational surfaces in R^3,1 which possess rational envelopes of the associated two-parameter families of spheres. Moreover, all offsets of the envelopes admit rational parameterizations as well. Recently, it has been proved that quadratic triangular Bézier patches in R^3,1 are MOS surfaces. Following this result, we describe an algorithm for computing an exact rational envelope of a two-parameter family of spheres given by a quadratic patch in R^3,1. The paper focuses mainly on the geometric aspects of the algorithm. Since these patches are capable of producing C¹ smooth approximations of medial surface transforms of spatial domains, we use this algorithm to generate rational approximations of envelopes of general medial surface transforms. One of the main advantages of this approach to offsetting is the fact that the trimming procedure becomes considerably simpler.     

Variational Design and Fairing of Spline Surfaces

Variational principles have become quite popular in the design of free form surfaces. Among others they are used for fairing purposes. The choice of the ‘right’ fairness functional is a crucial step. There is always a tradeoff between high quality and computational effort. In this paper we present fairness functionals that allow fairing efficiently, i.e., produce high quality surfaces in a reasonable amount of time. These functionals can be considered as simplified thin plate energy functionals for parametric surfaces or as simplified MVC functionals.     

A New QEM for Parametrization of Raster Images

We present an image processing method that converts a raster image to a simplical two‐complex which has only a small number of vertices (base mesh) plus a parametrization that maps each pixel in the original image to a combination of the barycentric coordinates of the triangle it is finally mapped into. Such a conversion of a raster image into a base mesh plus parametrization can be useful for many applications such as segmentation, image retargeting, multi‐resolution editing with arbitrary topologies, edge preserving smoothing, compression, etc. The goal of the algorithm is to produce a base mesh such that it has a small colour distortion as well as high shape fairness, and a parametrization that is globally continuous visually and numerically. Inspired by multi‐resolution adaptive parametrization of surfaces and quadric error metric, the algorithm converts pixels in the image to a dense triangle mesh and performs error‐bounded simplification jointly considering geometry and colour. The eliminated vertices are projected to an existing face. The implementation is iterative and stops when it reaches a prescribed error threshold. The algorithm is feature‐sensitive, i.e. salient feature edges in the images are preserved where possible and it takes colour into account thereby producing a better quality triangulation.     

A computational approach to joint line detection on triangular meshes

In this paper, we present formulae for evaluating differential quantities at vertices of triangular meshes that may approximate potential piecewise smooth surfaces with discontinuous normals or discontinuous curvatures at the joint lines. We also define the C ¹ and C ² discontinuity measures for surface meshes using changing rates of one-sided curvatures or changing rates of curvatures across mesh edges. The curvatures are computed discretely as of local interpolating surfaces that lie within a tolerance to the mesh. Together with proper estimation of local shape parameters, the obtained discontinuity measures own properties like sensitivity to salient joint lines and being scale invariant. A simple algorithm is finally developed for detection of C ¹ or C ² discontinuity joint lines on triangular meshes with even highly non-uniform triangulations. Several examples are provided to demonstrate the effectiveness of the proposed method.     

Homological and Cohomological Invariants of Electric Circuits

An attempt was made to substantiate strictly the tensor point of view on the electric circuit that was first introduced in the classical works of G. Kron. Geometrical structure of the circuit was shown to generate groups of homologies and cohomologies to which two pairs of vector spaces are assigned isomorphically. Here, invariance of the input and output powers turns out to be a natural consequence of the topological nature of the circuit, which enables one to construct a tensor model of electric circuits: currents and voltages of the all-loop and all-node circuits can be regarded as the countervariant and covariant vectors of the conjugate spaces, and the passage from the primitive circuit to the all-loop (all-node) one is done by transforming the bases of the homological and cohomological spaces; the matrices of inductances, capacities, and conductances are of tensor nature, i.e., are the coordinate representations of the covariant and countervariant circuit invariants, and the kinetic and potential energies of the circuit are represented as the corresponding bilinear functionals.