David Cardoze
ABSTRACT
We present a new framework for maintaining the quality of two dimensional triangular moving meshes. The use of curved elements is the key idea that allows us to avoid excessive refinement and still obtain good quality meshes consisting of a low number of well shaped elements. We use B-splines curves to model object boundaries, and objects are meshed with second order Bézier triangles. As the mesh evolves according to a non-uniform flow velocity field, we keep track of object boundaries and, if needed, carefully modify the mesh to keep it well shaped by applying a combination of vertex insertion and deletion, edge flipping, and edge smoothing operations at each time step. Our algorithms for these tasks are extensions of known algorithms for meshes built of straight--sided elements and are designed for any fixed-order Bézier elements and B-splines. Although in this work we have concentrated on quadratic elements, most of the operations are valid for elements of any order and they generalize well to higher dimensions. We present results of our scheme for a set of objects mimicking red blood cells subject to a precomputed flow velocity field.
- James F. Antaki, Guy E. Blelloch, Omar Ghattas, Ivan Malcevic, Gary L. Miller, and Noel J. Walkington. A parallel dynamic-mesh lagrangian method for simulation of flows with dynamic interfaces. In Proceedings of the 2000 ACM/IEEE Conference on Supercomputing, 2000. Google Scholar
Digital Library
- T. J. Baker. Mesh movement and metamorphosis. In Proceedings, 10th International Meshing Roundtable, pages 387--396. Sandia National Laboratories, October 7-10 2001.Google Scholar
- Charles Boivin and Carl F. Ollivier-Gooch. Guaranteed-quality triangular mesh generation for domains with curved boundaries. International Journal for Numerical Methods in Engineering, 55 (10):1185--1213, 2002.Google ScholarCross Ref
- E. Brisson. Representing geometric structures in d dimensions: Topology and order. In Symposimum on Computational Geometry, pages 218--227, 1989. Google ScholarDigital Library
- Scott A. Canann, Joseph R. Tristano, and Matthew L. Staten. An approach to combined laplacian and optimization--based smoothing for triangular, quadrilateral and quad--dominant meshes. In 7th International Meshing Roundtable, pages 479--494. Sandia National Laboratories, 1998.Google Scholar
- Olivier Devillers. On deletion in delaunay triangulation. International Journal of Computational Geometry and Algorithms, 12:193--205, 2002.Google Scholar
- D. H. Douglas and T. K. Peucker. Algorithms for the reduction of the number of points required to represent a line or its caricature. The Canadian Cartographer, 10(2):112--122, 1973.Google ScholarCross Ref
- G. Farin. Curves and Surfaces for CAGD: A Practical Guide. Morgan Kaufman, 2002. Google ScholarDigital Library
- Lori A. Freitag, Mark Jones, and Paul Plassmann. An efficient parallel algorithm for mesh smoothing. In Fourth International Meshing Roundtable, pages 47--58, Albuquerque, New Mexico, October 1995. Sandia National Laboratories.Google ScholarCross Ref
- J. Gallier. Curves and Surfaces in Geometric Modeling: Theory and Algorithms. Morgan Kaufman, 1998. Google ScholarDigital Library
- A. Kuprat, D. George, E. Linnebur, R. K. Smith, and H. E. Trease. Moving adaptive unstructured 3-d meshes in semiconductor process modeling applications. VLSI Journal, 6(1-4):373--378, 1998.Google ScholarCross Ref
- Craig Lawrence, Jial L. Zhou, and André L.Tits. User's guide for CFSQP version 2.5. Technical Report TR--94--16r1, University of Maryland, College Park, 1997.Google Scholar
- C. T. Lawrence and A. L. Tits. A computationally efficient feasible sequential quadratic programming algorithm. SIAM Journal on Optimization, 11(4):1092--1118, 2001. Google ScholarDigital Library
- X.-Y. Li, S.-H. Teng, and A. Üngör. Simultaneous refinement and coarsening: adaptive meshing with moving boundaries. In 7th International Meshing pages 201--210, Dearborn, Mich., 1998.Google Scholar
- Xian-Juan Luo, Mark S. Shepard, Jean-Francois Remacle, Robert M. O'Bara, Mark W. Beall, Barna Szabo, and Ricardo Actis. p-version mesh generation issues. In Proceedings, 11th International Meshing pages 343--354. Sandia National Laboratories, September 15-18 2002.Google Scholar
- Gary L. Miller, Dafna Talmor, and Shang-Hua Teng. Optimal coarsening of unstructured meshes. Journal of 31(1):29--65, Apr 1999. Google ScholarDigital Library
- Todd Phillips. Delaunay refinement for curved boundaries. Poster Presentation, 11th International Meshing Roundtable, September 2002.Google Scholar
- S. H. M. Roth, P. Diezi, and M. H. Gross. Triangular Bézier clipping. Technical Report Rep 347, Institute of Scientific Computing, ETH Zurich, 2000.Google ScholarCross Ref
Index Terms
- A bézier-based approach to unstructured moving meshes
Recommendations
Delaunay Triangular Meshes in Convex Polygons
An algorithm for producing a triangular mesh in a convex polygon is presented. It is used in a method for the finite element triangulation of a complex polygonal region of the plane in which the region is decomposed into convex polygons. The interior ...
Generating well-shaped d-dimensional Delaunay meshes
Computing and combinatoricsA d-dimensional simplicial mesh is a Delaunay triangulation if the circumsphere of each of its simplices does not contain any vertices inside. A mesh is well shaped if the maximum aspect ratio of all its simplices is bounded from above by a constant. It ...
Adaptive skin meshes coarsening for biomolecular simulation
In this paper, we present efficient algorithms for generating hierarchical molecular skin meshes with decreasing size and guaranteed quality. Our algorithms generate a sequence of coarse meshes for both the surfaces and the bounded volumes. Each coarser ...
Reviews
Archana P. Sangole
This paper presents a method to mimic the shape dynamics of blood cells using curved meshes with triangular elements. The ultimate objective is to provide a three-dimensional (3D) simulation of blood flow, at the microscopic level, that takes into account individual cell deformations, and the interaction of the cells with the surrounding fluid. The vertices in the mesh are connected by B-spline curves along the boundaries, and Bézier curves in the interior. The techniques used to modify the mesh under the influence of flow velocity support the Lagrangian formulation for fluid mechanics, and are derived from existing algorithms used for linear meshes. The method of unstructured moving meshes was implemented in modeling the changes in shape characteristics of blood cells during flow, and clearly demonstrates how the algorithms for linear mesh modification can be extended to curved meshes. Although the literature on the modeling aspect is adequately referenced, there is very little discussion of the clinical aspects of the research, to emphasize the suitability of the proposed method by comparing it with existing methods for modeling blood flow. The authors propose extending their method to simulate blood flow. Existing methods in modeling (and visualizing) fluid flow, such as streamlines, velocity vector fields, and computational fluid dynamics (CFD) methods, are able to reflect vortices in the flow that characterize important aspects of its dynamics, and will influence the interaction between the blood cells and fluid. These interactions may or may not translate to a pathological condition. Figure 10 does reflect this behavior, by assuming an obstacle in the path of the cells. Will the proposed modeling mechanism be able to reflect these characteristics, while maintaining shape validity within the mesh for a large number of blood cells__?__ What additional information will it provide from the clinical perspective__?__ How will the method accommodate changes in flow due to branching__?__ On another note, vertices in a mesh are interconnected under topological constraints. Will changes in the topology of the mesh reflect flow characteristics that provide comparable or additional information about blood flow dynamics that are available using conventional modeling methods__?__ Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments