Combinatorial mesh optimization

A new mesh optimization framework for 3D triangular surface meshes is presented, which formulates the task as an energy minimization problem in the same spirit as in Hoppe et al. (SIGGRAPH’93: Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques, 1993). The desired mesh properties are controlled through a global energy function including data attached terms measuring the fidelity to the original mesh, shape potentials favoring high quality triangles, and connectivity as well as budget terms controlling the sampling density. The optimization algorithm modifies mesh connectivity as well as the vertex positions. Solutions for the vertex repositioning step are obtained by a discrete graph cut algorithm examining global combinations of local candidates.     

A data locality methodology for matrix–matrix multiplication algorithm

Matrix-Matrix Multiplication (MMM) is a highly important kernel in linear algebra algorithms and the performance of its implementations depends on the memory utilization and data locality. There are MMM algorithms, such as standard, Strassen–Winograd variant, and many recursive array layouts, such as Z-Morton or U-Morton. However, their data locality is lower than that of the proposed methodology. Moreover, several SOA (state of the art) self-tuning libraries exist, such as ATLAS for MMM algorithm, which tests many MMM implementations. During the installation of ATLAS, on the one hand an extremely complex empirical tuning step is required, and on the other hand a large number of compiler options are used, both of which are not included in the scope of this paper. In this paper, a new methodology using the standard MMM algorithm is presented, achieving improved performance by focusing on data locality (both temporal and spatial). This methodology finds the scheduling which conforms with the optimum memory management. Compared with (Chatterjee et al. in IEEE Trans. Parallel Distrib. Syst. 13:1105, 2002; Li and Garzaran in Proc. of Lang. Compil. Parallel Comput., 2005; Bilmes et al. in Proc. of the 11th ACM Int. Conf. Super-comput., 1997; Aberdeen and Baxter in Concurr. Comput. Pract. Exp. 13:103, 2001), the proposed methodology has two major advantages. Firstly, the scheduling used for the tile level is different from the element level’s one, having better data locality, suited to the sizes of memory hierarchy. Secondly, its exploration time is short, because it searches only for the number of the level of tiling used, and between (1, 2) (Sect. 4) for finding the best tile size for each cache level. A software tool (C-code) implementing the above methodology was developed, having the hardware model and the matrix sizes as input. This methodology has better performance against others at a wide range of architectures. Compared with the best existing related work, which we implemented, better performance up to 55% than the Standard MMM algorithm and up to 35% than Strassen’s is observed, both under recursive data array layouts.     

Differential Representations for Mesh Processing

Surface representation and processing is one of the key topics in computer graphics and geometric modeling, since it greatly affects the range of possible applications. In this paper we will present recent advances in geometry processing that are related to the Laplacian processing framework and differential representations. This framework is based on linear operators defined on polygonal meshes, and furnishes a variety of processing applications, such as shape approximation and compact representation, mesh editing, watermarking and morphing. The core of the framework is the definition of differential coordinates and new bases for efficient mesh geometry representation, based on the mesh Laplacian operator.     

Approximate dynamic programming for link scheduling in wireless mesh networks

In this paper a novel interference-based formulation and solution methodology for the problem of link scheduling in wireless mesh networks is proposed. Traditionally, this problem has been formulated as a deterministic integer program, which has been shown to be -hard. The proposed formulation is based on dynamic programming and allows greater flexibility since dynamic and stochastic components of the problem can be embedded into the optimization framework. By temporal decomposition we reduce the size of the integer program and using approximate dynamic programming (ADP) methods we tackle the curse of dimensionality. The numerical results reveal that the proposed algorithm outperforms well-known heuristics under different network topologies. Finally, the proposed ADP methodology can be used not only as an upper bound but also as a generic framework where different heuristics can be integrated.     

Parallel decoupled terminal-edge bisection method for 3D mesh generation

We present a practical and stable algorithm for the parallel refinement of tetrahedral meshes. The algorithm is based on the refinement of terminal-edges and associated terminal stars. A terminal-edge is a special edge in the mesh which is the longest edge of every element that shares such an edge, while the elements that share a terminal-edge form a terminal star. We prove that the algorithm is inherently decoupled and thus scalable. Our experimental data show that we have a stable implementation able to deal with hundreds of millions of tetrahedra and whose speed is in between one and two order of magnitude higher from the method and implementation we presented (Rivara et al., Proceedings 13th international meshing roundtable, 2004).Maria-Cecilia Rivara and Carlo Calderon's work was partially supported by Fondecyt 1040713.Andriy Fedorov’s work is supported in part by ITR #ACI-0085969, and NGS #ANI-0203974.Nikos Chrisochoides’s work is supported in part by NSF Career Award #CCR-0049086, ITR #ACI-0085969, NGS #ANI-0203974, and ITR #CNS-0312980.     

A Unified Primal-Dual Algorithm Framework Based on Bregman Iteration

In this paper, we propose a unified primal-dual algorithm framework for two classes of problems that arise from various signal and image processing applications. We also show the connections to existing methods, in particular Bregman iteration (Osher et al., Multiscale Model. Simul. 4(2):460–489, 2005) based methods, such as linearized Bregman (Osher et al., Commun. Math. Sci. 8(1):93–111, 2010; Cai et al., SIAM J. Imag. Sci. 2(1):226–252, 2009, CAM Report 09-28, UCLA, March 2009; Yin, CAAM Report, Rice University, 2009) and split Bregman (Goldstein and Osher, SIAM J. Imag. Sci., 2, 2009). The convergence of the general algorithm framework is proved under mild assumptions. The applications to ℓ ¹ basis pursuit, TV−L ² minimization and matrix completion are demonstrated. Finally, the numerical examples show the algorithms proposed are easy to implement, efficient, stable and flexible enough to cover a wide variety of applications.     

Constrained mesh optimization on boundary

This paper presents a new mesh optimization approach aiming to improve the mesh quality on the boundary. The existing mesh untangling and smoothing algorithms (Vachal et al. in J Comput Phys 196: 627–644, 2004; Knupp in J Numer Methods Eng 48: 1165–1185, 2002), which have been proved to work well to interior mesh optimization, are enhanced by adding constrains of surface and curve shape functions that approximate the boundary geometry from the finite element mesh. The enhanced constrained optimization guarantees that the boundary nodes to be optimized always move on the approximated boundary. A dual-grid hexahedral meshing method is used to generate sample meshes for testing the proposed mesh optimization approach. As complementary treatments to the mesh optimization, appropriate mesh topology modifications, including buffering element insertion and local mesh refinement, are performed in order to eliminate concave and distorted elements on the boundary. Finally, the optimization results of some examples are given to demonstrate the effectivity of the proposed approach.     

A Sound Framework for δ-Rule Variants in Free-Variable Semantic Tableaux

We propose a generic sound δ-rule, based on a quite general method for the construction of Skolem terms, which can be used as a common framework for proving the soundness of known variants of the δ-rule, and we compare their relative effectiveness. Attempts to instantiate some of the δ-rules present in the literature within our framework allowed us to pinpoint unsoundness problems for two of them. In both cases, we propose revised versions that are proved sound by reducing them within our framework. This paper is based on results preliminarily presented in [5].     

Adaptive physics based tetrahedral mesh generation using level sets

We present a tetrahedral mesh generation algorithm designed for the Lagrangian simulation of deformable bodies. The algorithm’s input is a level set (i.e., a signed distance function on a Cartesian grid or octree). First a bounding box of the object is covered with a uniform lattice of subdivision-invariant tetrahedra. The level set is then used to guide a red green adaptive subdivision procedure that is based on both the local curvature and the proximity to the object boundary. The final topology is carefully chosen so that the connectivity is suitable for large deformation and the mesh approximates the desired shape. Finally, this candidate mesh is compressed to match the object boundary. To maintain element quality during this compression phase we relax the positions of the nodes using finite elements, masses and springs, or an optimization procedure. The resulting mesh is well suited for simulation since it is highly structured, has topology chosen specifically for large deformations, and is readily refined if required during subsequent simulation. We then use this algorithm to generate meshes for the simulation of skeletal muscle from level set representations of the anatomy. The geometric complexity of biological materials makes it very difficult to generate these models procedurally and as a result we obtain most if not all data from an actual human subject. Our current method involves using voxelized data from the Visible Male [1] to create level set representations of muscle and bone geometries. Given this representation, we use simple level set operations to rebuild and repair errors in the segmented data as well as to smooth aliasing inherent in the voxelized data.     

Optimized triangle mesh reconstruction from unstructured points

A variety of approaches have been proposed for polygon mesh reconstruction from a set of unstructured sample points. Suffering from severe aliases at sharp features and having a large number of unnecessary faces, most resulting meshes need to be optimized using input sample points in a postprocess. In this paper, we propose a fast algorithm to reconstruct high-quality meshes from sample data. The core of our proposed algorithm is a new mesh evaluation criterion which takes full advantage of the relation between the sample points and the reconstructed mesh. Based on our proposed evaluation criterion, we develop necessary operations to efficiently incorporate the functions of data preprocessing, isosurface polygonization, mesh optimization and mesh simplification into one simple algorithm, which can generate high-quality meshes from unstructured point clouds with time and space efficiency. Published online: 28 January 2003 Correspondence to: Y.-J. Liu