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.     

An intrinsic algorithm for computing geodesic distance fields on triangle meshes with holes

As a fundamental concept, geodesics play an important role in many geometric modeling applications. However, geodesics are highly sensitive to topological changes; a small topological shortcut may result in a significantly large change of geodesic distance and path. Most of the existing discrete geodesic algorithms can only be applied to noise-free meshes. In this paper, we present a new algorithm to compute the meaningful approximate geodesics on polygonal meshes with holes. Without the explicit hole filling, our algorithm is completely intrinsic and independent of the embedding space; thus, it has the potential for isometrically deforming objects as well as meshes in high dimensional space. Furthermore, our method can guarantee the exact solution if the surface is developable. We demonstrate the efficacy of our algorithm in both real-world and synthetic models.     

Efficiently computing geodesic offsets on triangle meshes by the extended Xin–Wang algorithm

Geodesic offset curves are important for many industrial applications, such as solid modeling, robot-path planning, the generation of tool paths for NC machining, etc. Although the offset problem is well studied in classical differential geometry and computer-aided design, where the underlying surface is sufficiently smooth, very few algorithms are available for computing geodesic offsets on discrete representation, in which the input is typically a polyline curve restricted on a piecewise linear mesh. In this paper, we propose an efficient and exact algorithm to compute the geodesic offsets on triangle meshes by extending the Xin–Wang algorithm of discrete geodesics. We define a new data structure called parallel-source windows, and extend both the “one angle one split” and the filtering theorem to maintain the window tree. Similar to the original Xin–Wang algorithm, our extended algorithm has an O(n) space complexity and an O(n²logn) asymptotic time complexity, where n is the number of vertices on the input mesh. We tested our algorithm on numerous real-world models and showed that our algorithm is exact, efficient and robust, and can be applied to large scale models with complicated geometry and topology.     

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.     

Obtuse triangle suppression in anisotropic meshes

Anisotropic triangle meshes are used for efficient approximation of surfaces and flow data in finite element analysis, and in these applications it is desirable to have as few obtuse triangles as possible to reduce the discretization error. We present a variational approach to suppressing obtuse triangles in anisotropic meshes. Specifically, we introduce a hexagonal Minkowski metric, which is sensitive to triangle orientation, to give a new formulation of the centroidal Voronoi tessellation (CVT) method. Furthermore, we prove several relevant properties of the CVT method with the newly introduced metric. Experiments show that our algorithm produces anisotropic meshes with much fewer obtuse triangles than using existing methods while maintaining mesh anisotropy.     

Eigenmodes computation on quadrilateral meshes

We approximate a fluid-structure interaction eigenvalue problem by means of finite elements on quadrilateral meshes. The problem under consideration looks simple and has been the object of a wide investigation: actually, no standard numerical scheme achieves acceptable results in presence of field singularities. We consider a three-field mixed method introduced by Bathe et al. and based on rectangular meshes (see [3, 12]). Recent results show that particular care has to be taken into account when dealing with finite element approximation on general quadrilateral meshes. We present numerical experiments on several sequences of meshes which definitely show how the “local” approach has to be discarded, while the “global” approach gives reasonable results. Received: 30 January 2001 / Accepted: 30 May 2001     

可调自适应三角网格的细分曲面造型方法

为了研究一种简单的有效的细分曲面方法使生成的曲面不仅光滑而且可调,提出了一种面向三角网格的可调自适应细分曲面造型法,该方法通过在传统的Loop细分模式中加入形状控制因子以使生成的曲面形状可调,同时引入二面角作为控制误差来判断相邻三角形夹角是否满足给定的阈值,以此实现自适应细分过程。模拟算例结果表明,该方法不仅能用较少网格获得性能良好的曲面,而且可以通过选取不同的值调整生成曲面形状,满足工程需要。     

An efficient exact algorithm for triangle listing in large graphs

This paper presents a new efficient exact algorithm for listing triangles in a large graph. While the problem of listing triangles in a graph has been considered before, dealing with large graphs continues to be a challenge. Although previous research has attempted to tackle the challenge, this is the first contribution that addresses this problem on a compressed copy of the input graph. In fact, the proposed solution lists the triangles without decompressing the graph. This yields interesting improvements in both storage requirement of the graphs and their time processing.     

Real-time human segmentation from RGB-D video sequence based on adaptive geodesic distance computation

Multimedia Tools and Applications - In this paper, we propose a method for extracting humans in the foreground of video frames using color and depth information. To ensure real-time performance and...     

Sharpen&Bend: recovering curved sharp edges in triangle meshes produced by feature-insensitive sampling

Various acquisition, analysis, visualization, and compression approaches sample surfaces of 3D shapes in a uniform fashion without any attempt to align the samples with sharp edges or to adapt the sampling density to the surface curvature. Consequently, triangle meshes that interpolate these samples usually chamfer sharp features and exhibit a relatively large error in their vicinity. We present two new filters that improve the quality of these resampled models. EdgeSharpener restores the sharp edges by splitting the chamfer edges and forcing the new vertices to lie on intersections of planes extending the smooth surfaces incident upon these chamfers. Bender refines the resulting triangle mesh using an interpolating subdivision scheme that preserves the sharpness of the recovered sharp edges while bending their polyline approximations into smooth curves. A combined Sharpen&Bend postprocessing significantly reduces the error produced by feature-insensitive sampling processes. For example, we have observed that the mean-squared distortion introduced by the SwingWrapper remeshing-based compressor can often be reduced by 80 percent executing EdgeSharpener alone after decompression. For models with curved regions, this error may be further reduced by an additional 60 percent if we follow the EdgeSharpening phase by Bender.     

Merging enriched Finite Element triangle meshes for fast prototyping of alternate solutions in the context of industrial maintenance

A new approach to the merging of Finite Element (FE) triangle meshes is proposed. Not only it takes into account the geometric aspects, but it also considers the way the semantic information possibly associated to the groups of entities (nodes, faces) can be maintained. Such high level modification capabilities are of major importance in all the engineering activities requiring fast modifications of meshes without going back to the CAD model. This is especially true in the context of industrial maintenance where the engineers often have to solve critical problems in very short time. Indeed, in this case, the product is already designed, the CAD models are not necessarily available and the FE models might be tuned. Thus, the product behaviour has to be studied and improved during its exploitation while prototyping directly several alternate solutions. Such a framework also finds interest in the preliminary design phases where alternative solutions have to be simulated. The algorithm first removes the intersecting faces in an n-ring neighbourhood so that the filling of the created holes produces triangles whose sizes smoothly evolve according to the possibly heterogeneous sizes of the surrounding triangles. The hole-filling algorithm is driven by an aspect ratio factor which ensures that the produced triangulation fits well the FE requirements. It is also constrained by the boundaries of the groups of entities gathering together the simulation semantic. The filled areas are then deformed to blend smoothly with the surroundings meshes.     

Symbolic computation of exact solutions expressible in hyperbolic and elliptic functions for nonlinear PDEs

Algorithms are presented for the tanh- and sech-methods, which lead to closed-form solutions of nonlinear ordinary and partial differential equations (ODEs and PDEs). New algorithms are given to find exact polynomial solutions of ODEs and PDEs in terms of Jacobi’s elliptic functions.For systems with parameters, the algorithms determine the conditions on the parameters so that the differential equations admit polynomial solutions in tanh, sech, combinations thereof, Jacobi’s sn or cn functions. Examples illustrate key steps of the algorithms.The new algorithms are implemented in Mathematica. The package PDESpecialSolutions.m can be used to automatically compute new special solutions of nonlinear PDEs. Use of the package, implementation issues, scope, limitations, and future extensions of the software are addressed.A survey is given of related algorithms and symbolic software to compute exact solutions of nonlinear differential equations.     

Fast computation of the prime implicants by exact direct-cover algorithm based on the new partial ordering operation rule

In this study, a novel OFF-set based direct-cover Exact Minimization Algorithm (EMA) is proposed for single-output Boolean functions represented in a sum-of-products form. To obtain the complete set of prime implicants covering the given Target Minterm (ON-minterm), the proposed method uses OFF-cubes (OFF-minterms) expanded by this Target Minterm. The amount of temporary results produced by this method does not exceed the size of the OFF-set. In order to achieve the goal of this study, which is to make faster computations, logic operations were used instead of the standard operations. Expansion OFF-cubes, commutative absorption operations and intersection operations are realized by logic operations for fast computation. The proposed minimization method is tested on several classes of benchmarks and then compared with the ESPRESSO algorithm. The results show that the proposed algorithm obtains more accurate and faster results than ESPRESSO does.     

Sequencing surgical cases in a day-care environment: An exact branch-and-price approach

In this paper we investigate how to sequence surgical cases in a day-care facility. We specify a multi-criteria objective function in which we minimize the peak use of recovery beds, the occurrence of recovery overtime and the violation of various patient and surgeon preferences. The limited availability of resources and the occurrence of medical precautions, such as an additional cleaning of the operating room after the surgery of an infected patient, are taken into account. We apply column generation to solve this combinatorial optimization problem and propose a dynamic programming algorithm to solve the pricing problem. The computational efficiency of this dynamic programming approach is validated through comparison with a mixed integer linear programming approach. In order to obtain integer variables, we embed the column generation loop in an enumerative branch-and-price framework. We elaborate on various branching strategies and branching schemes and examine their impact on the solution quality. The test instances for the computational experiments are generated using real-life data of the surgical day-care center at the academic hospital UZ Leuven Campus Gasthuisberg (Belgium).     

基于粒子群优化算法的三角网格孔洞修补

为了对三角网格模型中的复杂孔洞和曲率变化较剧烈部位处的孔洞进行修补,提出了一种基于粒子群优化算法（PSO）的三角网格孔洞修补算法。首先对孔洞多边形进行初始网格化,并计算所有网格顶点的梯度值,然后采用PSO搜索与孔洞边缘顶点梯度匹配的点集,最后根据孔洞匹配点集中顶点的梯度对孔洞中的初始网格进行修正,实现三角网格孔洞的修补。实验表明,该算法对各种复杂或曲率变化较大的孔洞,都有很好的修补效果。     

The exact computation of the number of zeros of a real polynomial in the open unit disk: An algebraic approach

A new algebraic proof and method for the exact computation of the number of zeros of a real polynomial inside the unit disk is given in this paper.     

三角网格模型的补洞算法研究

提出了一种三角网格模型的空间孔洞修补算法.首先根据网格中的点、边和三角形之间的关系提取孔洞边界,然后根据孔洞区域的夹角的顺序在空间中依次填补三角形直至修补完全,接着对新增加的高度弯曲的三角形进行细分,最后对修补后的孔洞网格进行几何形态调整,光顺化整个孔洞曲面.实验结果证明,该算法简单、有效,孔洞修补效果好.     

三角网格简化过程中属性问题的研究

在计算机视觉、计算机仿真、网络传输中,经常遇到带有颜色、纹理等属性的三角网格模型的简化问题.提出一种基于边折叠和改进二次误差测度的快速简便的算法来简化带属性的网格模型.在Garland算法基础上引入边重要度概念,并加入到误差测度中,使得二次误差测度不仅能够度量距离偏差,而且能够反映模型局部表面几何变化.实验结果表明,该算法既能保证简化模型同初始模型在几何上尽可能相似,又能较好地保留初始模型的颜色、纹理等属性信息.     

基于测地线投票的CT图像肺裂检测

在医学图像中,某些重要的CT图像中肺裂的检测在早期疾病检查和后期治疗中起着关键作用。然而,在2D断面方向上肺裂表现为细薄的曲线,对比度较低,密度值分布不均匀;肺部血管、支气管的存在也会干扰肺裂的检测。针对这些问题,提出了一种新的基于测地线投票的区域迭代回溯方法。该方法的主要处理流程为：首先采用快速行进方法构造测地线距离场,用直方图峰值查找方法定位肺裂分支,然后用区域迭代回溯方法搜索肺裂分支;结合测地线投票,从而在抑制噪声干扰的同时保持分支拓扑结构。实验结果表明该方法对噪声不敏感,具有良好的抗噪容错性能,较传统的全局回溯方法,区域回溯提高了检测的准确率和计算效率。