Robust curve skeleton extraction for vascular structures

Extracting curve skeletons for vascular structures is vital for many medical applications. However, most of existing curve skeleton extraction methods are either too complicated or not robust to be applied directly on vascular meshes. In this paper, we present a simple and robust three-step approach for one-dimensional curve skeleton extraction for vascular models. Firstly, the given vascular mesh is iteratively contracted until it is thin enough. Then the contracted mesh is further subdivided. Thereafter our approach proceeds over the point cloud domain yielded by the vertices of the subdivided mesh. Secondly, the joint and branch points of the model are detected. Finally, a skeleton growing procedure is proposed to generate the curve skeleton. Experimental results show that our approach is robust for vascular structures of any topology, e.g. with or without loops or with nearby structures. Additional experiments demonstrate that our approach can be extended to handle other common shapes.     

A mobile environment for sketching-based skeleton generation

Articulated character animation is typically performed by manually creating and rigging a skeleton into an unfolded 3D object. However, such tasks are not trivial, as they require a substantial amount of training and practices. Although automatic skeleton extraction methods have been proposed, they generally may not guarantee that the resulting skeleton can help produce desired animations according to user intention. In this paper, we present a sketching-based skeleton generation method suitable for use in the mobile environment. This method takes user sketching as an input, and based on the mesh segmentation result of a 3D object, it estimates a skeleton for articulated character animation. In addition, we are currently developing a Web-based mobile platform to support mesh editing by a group of collaborative users and we depict the system architecture of such a platform. Results show that our method can produce better skeletons in terms of joint positions and topological structure.     

封闭数据立方体技术研究

数据立方体中有很多冗余信息,去除这些冗余信息不但可以节约存储空间,还可以加快计算速度.数据立方体中的元组可以划分为封闭元组和非封闭元组.对任何一个非封闭元组,一定存在一个封闭元组,它们都是从基本表的同一组元组中经过聚集运算得到的,因而具有相同的聚集函数值.去掉数据立方体中所有的非封闭元组就产生了一个封闭数据立方体.提出了封闭数据立方体的生成算法、查询算法和增量维护算法,并使用合成数据和实际数据做了一些实验.实验结果表明,封闭数据立方体技术是有效的.     

Finite element mesh deformation with the skeleton-section template

To develop fast finite element (FE) adaptation methods for simulation-driven design optimization, we propose a radial basis functions (RBF) method with a skeleton-section template to globally and locally deform FE meshes of thin-walled beam structures.The skeleton-section template is automatically formulated from the input mesh and serves as a hierarchical parameterization for the FE meshes. With this hierarchical parameterization, both the global and the local geometries of a thin-walled beam can be processed in the same framework, which is of importance for designing engineering components. The curve skeleton of the mesh is constructed with Voronoi decomposition, while the cross-sections are extracted from the mesh based on the curve skeleton.The RBF method is employed to locally and globally deform the mesh model with the cross-sections and the skeleton, respectively. The RBF method solves the spatial deformation field given prescribed deformations at the cross-sections. At the local scale, the user modifies the cross-sections to deform a region of the surface mesh. At the global level, the skeleton is manipulated and its deformation is transferred to all cross-sections to induce the mesh deformation.In order to handle curved mesh models and attain flexible local deformations, the input mesh is embedded into its skeleton frame field using an anisotropic distance metric. In this way, even strip-like features along arbitrary directions can be created on the mesh model using only a few cross-sections as the deformation handles. In addition, form features can be rigidly preserved at both deformation levels.Numerical examples demonstrate that intuitive and qualified FE mesh deformations can be obtained with manipulation of the skeleton-section template.     

Automatic Conversion of Mesh Animations into Skeleton-based Animations

Recently, it has become increasingly popular to represent animations not by means of a classical skeleton‐based model, but in the form of deforming mesh sequences. The reason for this new trend is that novel mesh deformation methods as well as new surface based scene capture techniques offer a great level of flexibility during animation creation. Unfortunately, the resulting scene representation is less compact than skeletal ones and there is not yet a rich toolbox available which enables easy post‐processing and modification of mesh animations. To bridge this gap between the mesh‐based and the skeletal paradigm, we propose a new method that automatically extracts a plausible kinematic skeleton, skeletal motion parameters, as well as surface skinning weights from arbitrary mesh animations. By this means, deforming mesh sequences can be fully‐automatically transformed into fullyrigged virtual subjects. The original input can then be quickly rendered based on the new compact bone and skin representation, and it can be easily modified using the full repertoire of already existing animation tools.     

一种改进的基于特征点求解的骨架提取算法

基于特征点求解和Reeb图思想,实现了一种新的骨架提取算法。首先求取模型特征点集,以特征点为计算依据,根据三角网格中每个顶点与特征点的不同对应关系得到网格分支点,聚合成一系列骨架点,依据骨架点携带的拓扑信息,连接拓扑相邻的骨架点得到模型骨架。采用了改进的特征点提取算法,其时间复杂度由O（n^3）提高到了O（n^2log（n））,实验表明算法能够快速提取骨架,针对一般模型的骨架提取效果令人满意。     

骨架驱动的三维模型变形方法

为发展三维网格模型的变形技术,研究了多种三维模型变形算法,通过对骨架驱动变形算法的深入研究,针对现行算法多是以单一骨架驱动变形的不足,提出了一种新的基于多骨架点驱动的交互式局部变形方法.有效结合模型的骨架图结构,确定各骨架点对应的局部区域.并将骨架点拟合为二次Bézier曲线,通过交互式拖动任意骨架点计算与之相连的多骨架点的动态变化,实现模型局部区域的自然形变.实验结果表明了该算法的有效性和直观性.     

基于骨架关节点约束的交互式局部变形

利用广义元球变形技术,提出一种基于骨架关节点约束的交互式局部变形方法。该方法提取多边形网格模型的骨架关节点并结合模型骨架图结构确定骨架关节点对应的局部区域,计算三维网格点到骨架节点的欧式距离,将约束区域的最大欧氏距离作为约束半径,得到各骨架节点对应的势函数值,通过控制骨架节点的空间位置给出三角形面片点的新坐标位置。实验结果表明,该方法有效保持多边形网络模型的局部特征,并确保了模型变形的直观性和高效性。     

Robust mesh editing using Laplacian coordinates

Shape deformation and editing are important for animation and game design. Laplacian surface based methods have been widely investigated and used in many works. In this paper we propose a robust mesh editing framework which improves traditional Laplacian surface editing. It consists of two procedures: skeleton based as-rigid-as-possible (ARAP) shape modeling and detail-preserving mesh optimization. Traditional ARAP shape modeling relies on the mesh quality. Degenerated mesh may adversely affect the deformation performance. A preprocessing step of mesh optimization can alleviate this problem. However, skinny triangles can still be generated during deformation, which adversely affect the editing performance. Thus our method performs Laplacian mesh deformation and optimization alternately in each iteration, which ensures mesh quality without noticeably increasing computational complexity or changing the shape details. This approach is more robust than those solely using Laplacian mesh deformation. An additional benefit is that the skeleton-based ARAP modeling can approximately preserve the volume of an object with large-scale deformations. The volume is roughly kept by leveraging the skeleton information and employing a carefully designed energy function to preserve the edge length. This method does not break the manifoldness of traditional ARAP methods or sacrifice speed. In our experiments, we show that (1) our method is robust even for degenerated meshes, (2) the deformation is natural in terms of recovering rotations, and (3) volumes are roughly kept even under large-scale deformations. The system achieves real time performance for surface meshes with 7k vertices.     

基于凸壳与有向包围盒的骨架提取方法

为获取三维模型的几何及拓扑信息,提出一种基于凸壳与有向包围盒(OBB)的线性骨架提取方法.首先将三维网格模型进行分割生成多个子网格模型;然后对各子网格中的点集求取凸壳作为该子网格点集的近似,由凸壳顶点的形心构成原始骨架点;再用OBB进行重叠计算求出相交点集,以生成关节骨架点;最后对原始骨架点与关节骨架点进行连接,经冗余检测后形成完整骨架.实验结果表明,该方法快速、有效,提取出的骨架能保证连通性与中心性且能很好地提取关节骨架点,为蒙皮关节动画、模型形状分析等提供有效信息.     

基于骨架的网格模型变形

现有骨架驱动变形算法多以单一骨架驱动变形,且骨架预设十分复杂。为此,提出一种基于骨架的网格模型变形算法。结合多分辨率Reeb图方法提取模型的骨架结构,确定各骨架点对应的局部区域,将骨架点插值构造二次Bézier曲线,通过交互式拖动任意骨架点,计算与其相连多骨架点的动态变化情况,实现模型局部区域的自然形变。实验结果表明,该算法能获得较为自然平滑的变形结果。     

Three-dimensional anisotropic geometric metrics based on local domain curvature and thickness

A three-dimensional anisotropic Riemannian metric is constructed from a triangulated CAD model to control its spatial discretization for numerical analysis. In addition to the usual curvature criterion, the present geometric metric is also based on the local thickness of the modeled domain. This local thickness is extracted from the domain skeleton while local curvature is deduced from the model triangulated boundaries. A Cartesian background octree is used as the support medium for this metric and skeletonization takes advantage of this structure through an octree extension of a digital medial axis transform. For this purpose, the octree has to be refined according to not only boundary curvature but also a local separation criterion from digital topology theory. The resulting metric can be used to geometrically adapt any mesh type as long as metric-based adaptation tools are available. To illustrate such an application, geometric adaptation of overlay meshes used in grid-based methods for unstructured hexahedral mesh generation is presented. However, beyond mesh generation, the present metric may also be useful as a shape analysis tool and such a possibility could be explored in future developments.     

Curve skeleton extraction by coupled graph contraction and surface clustering

In this paper, we present a practical algorithm to extract a curve skeleton of a 3D shape. The core of our algorithm comprises coupled processes of graph contraction and surface clustering. Given a 3D shape represented by a triangular mesh, we first construct an initial skeleton graph by directly copying the connectivity and geometry information from the input mesh. Graph contraction and surface clustering are then performed iteratively. The former merges certain graph nodes based on computation of an approximate centroidal Voronoi diagram, seeded by subsampling the graph nodes from the previous iteration. Meanwhile, a coupled surface clustering process serves to regularize the graph contraction. Constraints are used to ensure that extremities of the graph are not shortened undesirably, to ensure that skeleton has the correct topological structure, and that surface clustering leads to an approximately-centered skeleton of the input shape. These properties lead to a stable and reliable skeleton graph construction algorithm.Experiments demonstrate that our skeleton extraction algorithm satisfies various desirable criteria. Firstly, it produces a skeleton homotopic with the input (the genus of both shapes agree) which is both robust (results are stable with respect to noise and remeshing of the input shape) and reliable (every boundary point is visible from at least one curve-skeleton location). It can also handle point cloud data if we first build an initial skeleton graph based on k-nearest neighbors. In addition, a secondary output of our algorithm is a skeleton-to-surface mapping, which can e.g. be used directly for skinning animation.Highlights(1) An algorithm for curve skeleton extraction from 3D shapes based on coupled graph contraction and surface clustering. (2) The algorithm meets various desirable criteria and can be extended to work for incomplete point clouds.     

基于曲率法线流的树点云骨架提取方法

针对树木点云拓扑结构复杂、特征细节繁多等问题,提出一种基于点云收缩提取曲线骨架的算法。首先,为了在点云表面直接应用网格收缩算法,对点云进行局部主成分分析和Delaunay三角剖分;其次,针对树木点云拓扑结构复杂和末枝细节繁多等问题,用曲率法线流算子对点云进行收缩,针对树木枝条细长且弯曲幅度平缓等特点,利用改进后的QEM网格简化方法将三角网格折叠成一维曲线骨架;最后,将得到的曲线骨架进行连通和居中处理。该算法直接在点云上进行操作,不需要额外的信息和预处理操作,对噪声和残缺点云有良好的鲁棒性。实验证明,该算法提取的树木点云骨架充分表达了树木在自然环境下的生物性结构和特征,相对于rosa、L1-中轴等经典算法,在树木点云的骨架提取速度上提高3倍以上,枝条重建度提高25%。     

A new feature-preserving mesh-smoothing algorithm

We present a novel mesh denoising and smoothing method in this paper. Our approach starts by estimating the principal curvatures and mesh saliency value for each vertex. Then, we calculate the uniform principal curvature of each vertex based on the weighted average of local principal curvatures. After that, we use the weighted bi-quadratic Bézier surface to fit the neighborhood of each vertex using the least-square method and obtain the new vertex position by adjusting the parameters of the fitting surface. Experiments show that our smoothing method preserves the geometric feature of the original mesh model efficiently. Our approach also prevents the volume shrinkage of the input mesh and obtains smooth boundaries for non-closed mesh models.     

Polygon Inflation for Animated Models: a Method for the Extrusion of Arbitrary Polygon Meshes

A method for the extrusion of arbitrary polygon meshes is introduced. This method can be applied to model a large class of complex 3-D closed surfaces. It consists of defining a (typically small) set of connected polygons in 3-D that form a skeleton of the final object, and assigning extrusion distances to all polygons. The two sides of a polygon may have different extrusion distances. An automatic extrusion algorithm constructs a closed 3-D polygon mesh around the skeleton, making use of the indicated extrusion distances. We call this process inflating the polygons of the skeleton. Unlike traditional extrusion, the method works for non-planar skeleton configurations, and it also supports branching skeleton structures (i.e. edges with more than two incident polygons). © 1997 by John Wiley & Sons, Ltd.     

基于细分的网格模型骨架驱动变形技术

针对传统骨架驱动变形方法中模型细节特征不能得到有效保持的问题,提出一种基于细分的骨架驱动网格模型变形方法。首先,对网格模型待变形区域基于截交线进行局部骨架提取和控制网格构建,分别建立骨架与控制网格以及控制网格所对应细分曲面与待变形模型区域之间的关联关系;然后,将基本函数作用下的自由变形方法应用于骨架变形,通过骨架变形驱动控制网格变形,将变形前后控制网格所对应细分曲面的变化信息转为网格模型泊松梯度场的改变;最后,根据改变后梯度场重建网格模型。实例表明,该变形方法针对不同网格模型均可以得到较好的编辑效果,且细节信息在变形后都得到了有效保持。与传统骨架驱动变形方法相比,该方法除具备交互操作简单直观的优势外,同时能够更好保持变形模型几何细节特征,更为适合具有丰富几何细节的复杂模型的变形编辑。     

Mesh Sequence Morphing

Morphing is an important technique for the generation of special effects in computer animation. However, an analogous technique has not yet been applied to the increasingly prevalent animation representation, i.e. 3D mesh sequences. In this paper, a technique for morphing between two mesh sequences is proposed to simultaneously blend motions and interpolate shapes. Based on all possible combinations of the motions and geometries, a universal framework is proposed to recreate various plausible mesh sequences. To enable a universal framework, we design a skeleton‐driven cage‐based deformation transfer scheme which can account for motion blending and geometry interpolation. To establish one‐to‐one correspondence for interpolating between two mesh sequences, a hybrid cross‐parameterization scheme that fully utilizes the skeleton‐driven cage control structure and adapts user‐specified joint‐like markers, is introduced. The experimental results demonstrate that the framework, not only accomplishes mesh sequence morphing, but also is suitable for a wide range of applications such as deformation transfer, motion blending or transition and dynamic shape interpolation.     

Parallelization of deduction strategies: An analytical study

In this paper we present a general analysis of the parallelization of deduction strategies. We classify strategies assubgoal-reduction strategies, expansion-oriented strategies, andcontraction-based strategies. For each class we analyze how and what types of parallelism can be utilized. Since the operational semantics of deduction-based programming languages can be construed as subgoal-reduction strategies, our analysis encompasses, at the abstract level, both strategies for deduction-based programming and those for theorem proving. We distinguish different types of parallel deduction based on the granularity of parallelism. These two criteria — the classification of strategies and of types of parallelism — provide us with a framework to treat problems and with a grid to classify approaches to parallel deduction. Within this framework, we analyze many issues, including the dynamicity and size of the database of clauses during the derivation, the possibility of conflicts between parallel inferences, and duplication versus sharing of clauses. We also suggest the type of architectures that may be suitable for each class of strategies. We substantiate our analysis by describing existing methods, emphasizing parallel expansion-oriented strategies and parallel contraction-based strategies for theorem proving. The most interesting and least explored by existing approaches are the contraction-based strategies. The presence of contraction rules — rules that delete clauses — and especially the application ofbackward contraction, emerges as a key issue for parallelization of these strategies. Backward contraction is the main reason for the impressive experimental success of contraction-based strategies. Our analysis shows that backward contraction makes efficient parallelization much more difficult. In our analysis, coarse-grain parallelism appears to be the best choice for parallelizing contraction-based reasoning. Accordingly, we propose a notion ofparallelism at the search level as coarse-grain parallelism for deduction.Supported by the GE Foundation Faculty Fellowship to the University of Iowa and by the National Science Foundation with grant CCR-94-08667.Supported by grant NSC 83-0408-E-002-012T of the National Science Council of the Republic of China.