基于特定边界的组合保角球面参数化

针对亏格为零的流形三角网格模型,提出一种基于特定边界的组合保角球面参数化方法。该方法采用平均值坐标计算出原始三角网格模型各顶点间相关的权数,然后用这个权数去修正球面域上的顶点坐标得到新的具有保角性质的顶点坐标,再利用Möbius变换把新生成的球面域质心转化为球心,使其面积的变形程度降低,最后得到一个精度更高的初始球面域。实验结果表明该方法是有效的,且具有变形小、效率高的特点。     

Conformal spherical representation of 3D genus-zero meshes

This paper describes an approach of representing 3D shape by using a set of invariant spherical harmonic (SH) coefficients after conformal mapping. Specifically, a genus-zero 3D mesh object is first conformally mapped onto the unit sphere by using a modified discrete conformal mapping, where the modification is based on Möbius factorization and aims at obtaining a canonical conformal mapping. Then a SH analysis is applied to the resulting conformal spherical mesh. The obtained SH coefficients are further made invariant to translation and rotation, while at the same time retain the completeness, thanks to which the original shape information has been faithfully preserved.     

Automatic unstructured all-hexahedral mesh generation from B-Reps for non-manifold CAD assemblies

This paper describes an automatic and robust approach to convert non-manifold CAD assemblies into unstructured all-hexahedral meshes conformal to the given B-Reps (boundary-representations) and with sharp feature preservation. In previous works, we developed an octree-based isocontouring method to construct unstructured hexahedral meshes for arbitrary non-manifold and manifold domains. However, sharp feature preservation still remains a challenge, especially for non-manifold CAD assemblies. In this paper, boundary features such as NURBS (non-uniform rational B-Splines) curves and surface patches are first extracted from the given B-Reps. Features shared by multiple components are identified and distinguished. To preserve these non-manifold features, one given surface patch may need to be split into several small ones. An octree-based algorithm is then carried out to create an unstructured all-hexahedral base mesh, detecting and preserving all the sharp features via a curve and surface parametrization. Two sets of local refinement templates are provided for adaptive mesh generation, along with a novel 2-refinement implementation. Vertices in the base mesh are categorized into four groups based on the given non-manifold topology, and each group is relocated using various methods with all sharp features preserved. After this stage, a novel two-step pillowing technique is developed for such complicated non-manifold domains to eliminate triangle-shaped quadrilateral elements along the curves and “doublets”, handling non-manifold and manifold features in different ways. Finally, a combination of smoothing and optimization is used to further improve the mesh quality. Our algorithm is automatic and robust for non-manifold and manifold domains. We have applied our algorithm to several complicated CAD assemblies.     

Streaming surface sampling using Gaussian ε-nets

We propose a robust, feature preserving and user-steerable mesh sampling algorithm, based on the one-to-many mapping of a regular sampling of the Gaussian sphere onto a given manifold surface. Most of the operations are local, and no global information is maintained. For this reason, our algorithm is amenable to a parallel or streaming implementation and is most suitable in situations when it is not possible to hold all the input data in memory at the same time. Using ε-nets, we analyze the sampling method and propose solutions to avoid shortcomings inherent to all localized sampling methods. Further, as a byproduct of our sampling algorithm, a shape approximation is produced. Finally, we demonstrate a streaming implementation that handles large meshes with a small memory footprint.     

Perception-motivated multiresolution rendering on sole-cube maps

This paper presents a novel GPU-based multiresolution rendering on sole-cube maps (SCMs), which is a variant of geometry images built upon spherical parameterization. Given spherical parametrization of a manifold mesh, the sphere domain is gnomonically projected to a closed cube, which constitutes the 6-chart sole-cube maps. A quadtree structure of SCMs and normal map atlas are then constructed by using the regular re-sampling. Then, by packing the quadtree nodes into the SCMs texture atlas, a new parallel multiresolution rendering is processed on the latest GPU in two rendering passes: the multiresolution node selection in fragment shader; the triangulation in vertex shader followed by the node culling operation in geometry shader. The proposed approach generates adaptive mesh surfaces dynamically, and can be fully implemented in GPU parallelization. The proposed scheme alleviates the computing load of multiresolution mesh refinement on CPU, and our GPU-based multiresolution rendering is demonstrated with a variety of examples. Our user study confirmed that the visual quality of the SCMs multiresolution rendering, in comparison with the meshes/geometry images rendering, is also highly efficient especially for complex models in large-scale virtual environment.     

Robust Spherical Parameterization of Triangular Meshes

Parameterization of 3D mesh data is important for many graphics and mesh processing applications, in particular for texture mapping, remeshing and morphing. Closed, manifold, genus-0 meshes are topologically equivalent to a sphere, hence this is the natural parameter domain for them. Parameterizing a 3D triangle mesh onto the 3D sphere means assigning a 3D position on the unit sphere to each of the mesh vertices, such that the spherical triangles induced by the mesh connectivity do not overlap. This is called a spherical triangulation. In this paper we formulate a set of necessary and sufficient conditions on the spherical angles of the spherical triangles for them to form a spherical triangulation. We formulate and solve an optimization procedure to produce spherical triangulations which reflect the geometric properties of a given 3D mesh in various ways.     

H∞-norm and invariant manifolds of systems with state delays

The problem of finding bounds on the H_∞-norm of systems with a finite number of point delays and distributed delay is considered. Sufficient conditions for the system to possess an H_∞-norm which is less or equal to a prescribed bound are obtained in terms of Riccati partial differential equations (RPDE’s). We show that the existence of a solution to the RPDE’s is equivalent to the existence of a stable manifold of the associated Hamiltonian system. For small delays the existence of the stable manifold is equivalent to the existence of a stable manifold of the ordinary differential equations that govern the flow on the slow manifold of the Hamiltonian system. This leads to an algebraic, finite-dimensional, criterion for systems with small delays.     

Gravitational pose estimation

Problem of relative pose estimation between a camera and rigid object, given an object model with feature points and image(s) with respective image points (hence known correspondence) has been extensively studied in the literature. We propose a “correspondenceless” method called gravitational pose estimation (GPE), which is inspired by classical mechanics. GPE can handle occlusion and uses only one image (i.e., perspective projection of the object). GPE creates a simulated gravitational field from the image and lets the object model move and rotate in that force field, starting from an initial pose. Experiments were carried out with both real and synthetic images. Results show that GPE is robust, consistent, and fast (runs in less than a minute). On the average (including up to 30% occlusion cases) it finds the orientation within 6° and the position within 17% of the object’s diameter. SoftPOSIT was so far the best correspondenceless method in the literature that works with a single image and point-based object model like GPE. However, SoftPOSIT’s convergence to a result is sensitive to the choice of initial pose. Even “random start SoftPOSIT,” which performs multiple runs of SoftPOSIT with different initial poses, can often fail. However, SoftPOSIT finds the pose with great precision when it is able to converge. We have also integrated GPE and SoftPOSIT into a single method called GPEsoftPOSIT, which finds the orientation within 3° and the position within 10% of the object’s diameter even under occlusion. In GPEsoftPOSIT, GPE finds a pose that is very close to the true pose, and then SoftPOSIT is used to enhance accuracy of the result. Unlike SoftPOSIT, GPE also has the ability to work with three points as well as planar object models.     

Consistent mesh partitioning and skeletonisation using the shape diameter function

Mesh partitioning and skeletonisation are fundamental for many computer graphics and animation techniques. Because of the close link between an object’s skeleton and its boundary, these two problems are in many cases complementary. Any partitioning of the object can assist in the creation of a skeleton and any segmentation of the skeleton can infer a partitioning of the object. In this paper, we consider these two problems on a wide variety of meshes, and strive to construct partitioning and skeletons which remain consistent across a family of objects, not a single one. Such families can consist of either a single object in multiple poses and resolutions, or multiple objects which have a general common shape. To achieve consistency, we base our algorithms on a volume-based shape-function called the shape-diameter-function (SDF), which remains largely oblivious to pose changes of the same object and maintains similar values in analogue parts of different objects. The SDF is a scalar function defined on the mesh surface; however, it expresses a measure of the diameter of the object’s volume in the neighborhood of each point on the surface. Using the SDF we are able to process and manipulate families of objects which contain similarities using a simple and consistent algorithm: consistently partitioning and creating skeletons among multiple meshes.     

Shape from silhouette outlines using an adaptive dandelion model

In this paper we study the problem of shape from silhouette outlines (SFO) using a novel adaptive dandelion model. SFO reconstructs a 3D model using only the outmost silhouette contours and produces a solid called the “bounding hull”. The dandelion model is composed of a pencil of organized line segments emitted from a common point which samples the bounding hull surface in regularly distributed orientations with the ending points serving as sampling points. The orientations and the topology of the line segments are derived from a geodesic sphere. The lengths of the line segments are computed by cutting rays in 2D with silhouette outlines. Based on the subdivision structure of the geodesic sphere, the sampling resolution can be refined adaptively until the desired precision is achieved. Finally a manifold mesh is extracted from the dandelion model.     

Approximating Planar Conformal Maps Using Regular Polygonal Meshes

Continuous conformal maps are typically approximated numerically using a triangle mesh which discretizes the plane. Computing a conformal map subject to user‐provided constraints then reduces to a sparse linear system, minimizing a quadratic ‘conformal energy’. We address the more general case of non‐triangular elements, and provide a complete analysis of the case where the plane is discretized using a mesh of regular polygons, e.g. equilateral triangles, squares and hexagons, whose interiors are mapped using barycentric coordinate functions. We demonstrate experimentally that faster convergence to continuous conformal maps may be obtained this way. We provide a formulation of the problem and its solution using complex number algebra, significantly simplifying the notation. We examine a number of common barycentric coordinate functions and demonstrate that superior approximation to harmonic coordinates of a polygon are achieved by the Moving Least Squares coordinates. We also provide a simple iterative algorithm to invert barycentric maps of regular polygon meshes, allowing to apply them in practical applications, e.g. for texture mapping.     

三角网格曲面的球面参数化

提出了一种球面参数化三角网格曲面的方法。结合平面凸参数化和球面参数化,计算出封闭网格的切割线边界,网格边界映射到球面的凸区域边界上。然后分别参数化各子网格,最后将三角网格内部点映射到球面上。并用实例验证了此方法的可行性和有效性。     

Generating a nice triangular mesh on a regular parametric surface

In this paper, we present an iterative algorithm to generate a nice triangular curvilinear mesh on a regular parametric surface. The main idea is to obtain a reparametrization of the surface that behaves approximately like a conformal map in a finite number of points. These points are the vertices of a planar triangulation T ^op in the parameter space, which we would like to lift on the surface. The image of T ^op by means of the reparametrization provides us a triangular curvilinear mesh on the surface which reflects the properties of T ^op .     

任意拓扑三角形网格的全局参数化

提出了一种零亏格的任意拓扑流形三角形网格自动全局参数化方法 .算法首先采用顶点对合并的网格简化方法构造一个网格的累进表示 ,在进行网格简化的同时 ,对被删除的顶点相对于顶点合并操作所得到的新顶点的邻域进行局部参数化 ,由此得到一个带局部参数化信息的累进网格 ;然后将网格简化所得到的基网格进行中心投影到一个单位球面上 ,并采用累进恢复的方法将删除的顶点按与删除时相反的顺序逐次添加回网格上来 ,所添加顶点的坐标不再是其删除前的坐标值 ,而是由局部参数化信息计算得到 ,并且保证是位于单位球面上的 .由此得到原始网格的单位球面参数化网格     

An analytical representation of conformal mapping for genus-zero implicit surfaces and its application to surface shape similarity assessment

This paper develops an analytical representation of conformal mapping for genus-zero implicit surfaces based on algebraic polynomial functions, and its application to surface shape similarity assessment. Generally, the conformal mapping often works as a tool of planar or spherical parameterization for triangle mesh surfaces. It is further exploited for implicit surface matching in this study. The method begins with discretizing one implicit surface by triangle mesh, where a discrete harmonic energy model related to both the mesh and the other implicit surface is established based on a polynomial-function mapping. Then both the zero-center constraint and the landmark constraints are added to the model to ensure the uniqueness of mapping result with the Möbius transformation. By searching optimal polynomial coefficients with the Lagrange–Newton method, the analytical representation of conformal mapping is obtained, which reveals all global and continuous one-to-one correspondent point pairs between two implicit surfaces. Finally, a shape similarity assessment index for (two) implicit surfaces is proposed through calculating the differences of all the shape index values among those corresponding points. The proposed analytical representation method of conformal mapping and the shape assessment index are both verified by the simulation cases for the closed genus-zero implicit surfaces. Experimental results show that the method is effective for genus-zero implicit surfaces, which will offer a new way for object retrieval and manufactured surface inspection.     

A new parallel meshing technique integrated into the conformal FDTD method for solving complex electromagnetic problems

A new efficient parallel finite-difference time-domain （FDTD） meshing algorithm, based on the ray tracing technique, is proposed in this paper. This algorithm can be applied to construct various FDTD meshes, such as regular and conformal ones. The Microsoft F# language is used for the algorithm coding, where all variables are unchangeable with its parallelization advantage being fully exploited. An improved conformal FDTD algorithm, also integrated with an improved surface current algorithm, is presented to simulate some complex 3D models, such as a sphere ball made of eight different materials, a tank, a J-10 aircraft, and an aircraft carrier with 20 aircrafts. Both efficiency and capability of the developed parallel FDTD algorithm are validated. The algorithm is applied to characterize the induced surface current distribution on an aircraft or a warship.     

Hierarchical Quad Meshing of 3D Scanned Surfaces

In this paper we present a novel method to reconstruct watertight quad meshes on scanned 3D geometry. There exist many different approaches to acquire 3D information from real world objects and sceneries. Resulting point clouds depict scanned surfaces as sparse sets of positional information. A common downside is the lack of normals, connectivity or topological adjacency data which makes it difficult to actually recover a meaningful surface. The concept described in this paper is designed to reconstruct a surface mesh despite all this missing information. Even when facing varying sample density, our algorithm is still guaranteed to produce watertight manifold meshes featuring quad faces only. The topology can be set‐up to follow superimposed regular structures or align naturally to the point cloud's shape. Our proposed approach is based on an initial divide and conquer subsampling procedure: Surface samples are clustered in meaningful neighborhoods as leafs of a kd‐tree. A representative sample of the surface neighborhood is determined for each leaf using a spherical surface approximation. The hierarchical structure of the binary tree is utilized to construct a basic set of loose tiles and to interconnect them. As a final step, missing parts of the now coherent tile structure are filled up with an incremental algorithm for locally optimal gap closure. Disfigured or concave faces in the resulting mesh can be removed with a constrained smoothing operator.     

Feedback linearization of a flexible manipulator near its rigid body manifold

It is shown that a ‘slow’ 2n-dimensional manifold exists in the 4n-dimensional state space of an n-link manipulator with n flexible joints. While the flexible manifold is not linearizable by feedback, its restriction to'the slow manifold is. A method is given for computing a feedback control which achieves an approximate linearization.     

CPH: A Compact Representation for Hierarchical Meshes Generated by Primal Refinement

We present CPH (Compact Primal Hierarchy): a compact representation of the hierarchical connectivity of surface and volume manifold meshes generated through primal subdivision refinements. CPH is consistently defined in several dimensions and supports multiple kinds of tessellations and refinements, whether regular or adaptive. The basic idea is to store only the finest mesh, encoded in a classical monoresolution structure that is enriched with a minimal set of labels. These labels allow traversal of any intermediate level of the mesh concurrently without having to extract it in an additional structure. Our structure allows attributes to be stored on the cells not only on the finest level, but also on any intermediate level. We study the trade‐off between the memory cost of this compact representation and the time complexity of mesh traversals at any resolution level.     

A hexahedral mesh connectivity compression with vertex degrees

This paper introduces a new algorithm for the compression of manifold hexahedral meshes topology, using vertex degree. The topology compression consists of two parts—the mesh’s boundary consisting of quadrilaterals is compressed first, and then the hexahedra are processed by the help of six commands. The topology compression algorithm has been matched against the best-known method to-date, and shows itself to be competitive.