共查询到20条相似文献,搜索用时 15 毫秒
1.
Three-Dimensional Delaunay Mesh Generation 总被引:1,自引:0,他引:1
We propose an algorithm to compute a conforming Delaunay mesh of a bounded domain in
specified by a piecewise linear complex. Arbitrarily small input angles are allowed, and the input complex is not required
to be a manifold. Our algorithm encloses the input edges with a small buffer zone, a union of balls whose sizes are proportional
to the local feature sizes at their centers. In the output mesh, the radius-edge ratio of the tetrahedra outside the buffer
zone is bounded by a constant independent of the domain, while that of the tetrahedra inside the buffer zone is bounded by
a constant depending on the smallest input angle. Furthermore, the output mesh is graded. Our work is the first that provides
quality guarantees for Delaunay meshes in the presence of small input angles. 相似文献
2.
For any 2D triangulation τ, the 1-skeleton mesh of τ is the wireframe mesh defined by the edges of τ, while that for any 3D triangulation τ, the 1-skeleton and the 2-skeleton meshes, respectively, correspond to the wireframe mesh formed by the edges of τ and the “surface” mesh defined by the triangular faces of τ. A skeleton-regular partition of a triangle or a tetrahedra, is a partition that globally applied over each element of a conforming mesh (where the intersection of adjacent elements is a vertex or a common face, or a common edge) produce both a refined conforming mesh and refined and conforming skeleton meshes. Such a partition divides all the edges (and all the faces) of an individual element in the same number of edges (faces). We prove that sequences of meshes constructed by applying a skeleton-regular partition over each element of the preceding mesh have an associated set of difference equations which relate the number of elements, faces, edges and vertices of the nth and (n−1)th meshes. By using these constitutive difference equations we prove that asymptotically the average number of adjacencies over these meshes (number of triangles by node and number of tetrahedra by vertex) is constant when n goes to infinity. We relate these results with the non-degeneracy properties of longest-edge based partitions in 2D and include empirical results which support the conjecture that analogous results hold in 3D. 相似文献
3.
The quality of a finite element solution has been shown to be affected by the quality of the underlying mesh. A poor mesh may lead to unstable and/or inaccurate finite element approximations. Mesh quality is often characterized by the “smoothness” or “shape” of the elements (triangles in 2-D or tetrahedra in 3-D). Most automatic mesh generators produce an initial mesh where the aspect ratio of the elements are unacceptably high. In this paper, a new approach to produce acceptable quality meshes from a topologically valid initial mesh is presented. Given an initial mesh (nodal coordinates and element connectivity), a “smooth” final mesh is obtained by solving a constrained optimization problem. The variables for the iterative optimization procedure are the nodal coordinates (excluding, the boundary nodes) of the finite element mesh, and appropriate bounds are imposed on these to prevent an unacceptable finite element mesh. Examples are given of the application of the above method for 2- and 3-D meshes generated using
automatic mesh generators. Results indicate that the new method not only yields better quality elements when compared with the traditional Laplacian smoothing, but also guarantees a valid mesh unlike the Laplacian method. 相似文献
4.
Analysis of and workarounds for element reversal for a finite element-based algorithm for warping triangular and tetrahedral meshes 总被引:1,自引:0,他引:1
We consider an algorithm called FEMWARP for warping triangular and tetrahedral finite element meshes that computes the warping using the finite element method itself. The algorithm takes as input a two- or three-dimensional domain defined by a boundary mesh (segments in one dimension or triangles in two dimensions) that has a volume mesh (triangles in two dimensions or tetrahedra in three dimensions) in its interior. It also takes as input a prescribed movement of the boundary mesh. It computes as output updated positions of the vertices of the volume mesh. The first step of the algorithm is to determine from the initial mesh a set of local weights for each interior vertex that describes each interior vertex in terms of the positions of its neighbors. These weights are computed using a finite element stiffness matrix. After a boundary transformation is applied, a linear system of equations based upon the weights is solved to determine the final positions of the interior vertices. The FEMWARP algorithm has been considered in the previous literature (e.g., in a 2001 paper by Baker). FEMWARP has been successful in computing deformed meshes for certain applications. However, sometimes FEMWARP reverses elements; this is our main concern in this paper. We analyze the causes for this undesirable behavior and propose several techniques to make the method more robust against reversals. The most successful of the proposed methods includes combining FEMWARP with an optimization-based untangler. 相似文献
5.
We describe a distributed memory parallel Delaunay refinement algorithm for simple polyhedral domains whose constituent bounding edges and surfaces are separated by angles between 90° to 270° inclusive. With these constraints, our algorithm can generate meshes containing tetrahedra with circumradius to shortest edge ratio less than 2, and can tolerate more than 80% of the communication latency caused by unpredictable and variable remote gather operations.
Our experiments show that the algorithm is efficient in practice, even for certain domains whose boundaries do not conform to the theoretical limits imposed by the algorithm. The algorithm we describe is the first step in the development of much more sophisticated guaranteed-quality parallel mesh generation algorithms. 相似文献
6.
Boundary conforming Delaunay mesh generation 总被引:3,自引:0,他引:3
A boundary conforming Delaunay mesh is a partitioning of a polyhedral domain into Delaunay simplices such that all boundary simplices satisfy the generalized Gabriel property. It’s dual is a Voronoi partition of the same domain which is preferable for Voronoi-box based finite volume schemes. For arbitrary 2D polygonal regions, such meshes can be generated in optimal time and size. For arbitrary 3D polyhedral domains,
however, this problem remains a challenge. The main contribution of this paper is to show that boundary conforming Delaunay
meshes for 3D polyhedral domains can be generated efficiently when the smallest input angle of the domain is bounded by arccos 1/3 ≈ 70.53°. In addition, well-shaped tetrahedra and an appropriate mesh size can be
obtained. Our new results are achieved by reanalyzing a classical Delaunay refinement algorithm. Note that our theoretical
guarantee on the input angle (70.53°) is still too strong for many practical situations. We further discuss variants of the
algorithm to relax the input angle restriction and to improve the mesh quality. 相似文献
7.
8.
Aristotle contended that (regular) tetrahedra tile space, an opinion that remained widespread until it was observed that non-overlapping
tetrahedra cannot subtend a solid angle of 4π around a point if this point lies on a tetrahedron edge. From this 15th century argument, we can deduce that tetrahedra do
not tile space but, more than 500 years later, we are unaware of any known non-trivial upper bound to the packing density
of tetrahedra. In this article, we calculate such a bound. To this end, we show the existence, in any packing of regular tetrahedra,
of a set of disjoint spheres centered on tetrahedron edges, so that each sphere is not fully covered by the packing. The bound
on the amount of space that is not covered in each sphere is obtained in a recursive way by building on the solid angle argument.
The argument can be readily modified to apply to other polyhedra. The resulting lower bound on the fraction of empty space
in a packing of regular tetrahedra is 2.6…×10−25 and reaches 1.4…×10−12 for regular octahedra. 相似文献
9.
10.
In this paper we study the representation complexity of a kind of data structure that stores the information necessary to compute the distance from a point to a geometric body. These data structures called adaptive splitting based on cubature distance fields (ASBCDF), are binary search trees generated by the adaptive splitting based on cubature (ASBC) algorithm that adaptively subdivides the space surrounding the body into tetrahedra. Their representation complexity is measured by the number of nodes in the tree (two times the number of tetrahedra in the resulting tessellation). In the case of convex polyhedra we prove that this quantity remains bounded as the number of vertices of the polyhedra increases to infinity. Experimental results show that the number of tetrahedra in the tessellations is almost independent of the combinatorial complexity of the polyhedra. This means that the average compute time of the distance to arbitrary convex polyhedra is almost constant. Therefore, ASBCDFs are especially suitable for real time applications involving rapidly changing environments modelized with complex polyhedra. 相似文献
11.
Let be a tetrahedral mesh. We present a 3-D local refinement algorithm for which is mainly based on an 8-subtetrahedron subdivision procedure, and discuss the quality of refined meshes generated by the algorithm. It is proved that any tetrahedron produces a finite number of classes of similar tetrahedra, independent of the number of refinement levels. Furthermore, , where , is a positive constant independent of and the number of refinement levels, is any refined tetrahedron of , and is a tetrahedron shape measure. It is also proved that local refinements on tetrahedra can be smoothly extended to their neighbors to maintain a conforming mesh. Experimental results show that the ratio of the number of tetrahedra actually refined to the number of tetrahedra chosen for refinement is bounded above by a small constant.
12.
Elizabeth R. Chen Michael Engel Sharon C. Glotzer 《Discrete and Computational Geometry》2010,44(2):253-280
We present the densest known packing of regular tetrahedra with density $\phi =\frac{4000}{4671}=0.856347\ldots\,We present the densest known packing of regular tetrahedra with density
f = \frac40004671=0.856347? \phi =\frac{4000}{4671}=0.856347\ldots\,. Like the recently discovered packings of Kallus et al. and Torquato–Jiao, our packing is crystalline with a unit cell of
four tetrahedra forming two triangular dipyramids (dimer clusters). We show that our packing has maximal density within a
three-parameter family of dimer packings. Numerical compressions starting from random configurations suggest that the packing
may be optimal at least for small cells with up to 16 tetrahedra and periodic boundaries. 相似文献
13.
Michael Goldberg 《Journal of Combinatorial Theory, Series A》1974,16(3):348-354
A space-filling polyhedron is one whose replications can be packed to fill three-space completely. Only five space-filling tetrahedra have been described in the literature. The constructions of these are shown. Three new infinite one-parameter families of space-filling tetrahedra are derived. Special cases of these families yield three of the five space-filling tetrahedra already in the literature. 相似文献
14.
The Gergonne center of a triangle is the intersection
of the cevians through the points where the incircle touches the sides.
This does not admit a direct generalization to tetrahedra since the
cevians of a tetrahedron through the points where the insphere touches
the faces are not necessarily concurrent. This article introduces an
alternative definition of the Gergonne center that coincides with the
previous definition for the triangle and that admits a generalization to
tetrahedra. The same is done for the Nagel center.
Received 4 February 2000; revised 1 May 2000. 相似文献
15.
C. Chisholm 《Journal of Number Theory》2006,121(1):153-185
Buchholz [R.H. Buchholz, Perfect pyramids, Bull. Austral. Math. Soc. 45 (1991) 353-368] began a systematic search for tetrahedra having integer edges and volume by restricting his attention to those with two or three different edge lengths. Of the fifteen configurations identified for such tetrahedra, Buchholz leaves six unsolved. In this paper we examine these remaining cases for integer volume, completely solving all but one of them. Buchholz also considered Heron tetrahedra, which are tetrahedra with integral edges, faces and volume. Buchholz described an infinite family of Heron tetrahedra for one of the configurations. Another of the cases yields a new infinite family of Heron tetrahedra which correspond to the rational points on a two-parameter elliptic curve. 相似文献
16.
Jeff Erickson 《Discrete and Computational Geometry》2014,52(3):427-449
A topological quadrilateral mesh \(Q\) of a connected surface in \(\mathbb {R}^3\) can be extended to a topological hexahedral mesh of the interior domain \(\varOmega \) if and only if \(Q\) has an even number of quadrilaterals and no odd cycle in \(Q\) bounds a surface inside \(\varOmega \) . Moreover, if such a mesh exists, the required number of hexahedra is within a constant factor of the minimum number of tetrahedra in a triangulation of \(\varOmega \) that respects \(Q\) . Finally, if \(Q\) is given as a polyhedron in \(\mathbb {R}^3\) with quadrilateral facets, a topological hexahedral mesh of the polyhedron can be constructed in polynomial time if such a mesh exists. All our results extend to domains with disconnected boundaries. Our results naturally generalize results of Thurston, Mitchell, and Eppstein for genus-zero and bipartite meshes, for which the odd-cycle criterion is trivial. 相似文献
17.
Ten regular tetrahedra can be arranged in such a way that their vertices are coincident with the vertices of a regular dodecahedron
and that two tetrahedra meet at each vertex of the dodecahedron. If the resultant structure is considered as a bar-and-joint
structure, there will be 60 bars, lying along the edges of the tetrahedra, and 20 joints at the vertices of the dodecahedra;
six bars meet at each joint. Although the structure more than satisfies Maxwell's rule, it is known to admit finite mechanisms.
Recently, a new method for detecting symmetric finite mechanisms in symmetric bar-and-node structures has been developed.
The method only requires a count of the number of bars, and the number of nodes, that are left unmoved by each of the symmetry
operations allowable for the structure. This paper will describe the application of this method to the structure described
above. The structure has icosahedral symmetry, I
h
, and the analysis confirms the existence of the mechanisms with C
3v
and C
5v
symmetry that have previously been detected using ad-hoc methods.
This revised version was published online in August 2006 with corrections to the Cover Date. 相似文献
18.
19.
We show that any locally-fat (or (α,β)-covered) polyhedron with convex fat faces can be decomposed into O(n) tetrahedra, where n is the number of vertices of the polyhedron. We also show that the restriction that the faces are fat is necessary: there are locally-fat polyhedra with non-fat faces that require Ω(n2) pieces in any convex decomposition. Furthermore, we show that if we want the tetrahedra in the decomposition to be fat themselves, then their number cannot be bounded as a function of n in the worst case. Finally, we obtain several results on the problem where we want to only cover the boundary of the polyhedron, and not its entire interior. 相似文献
20.
C. Chisholm 《Journal of Number Theory》2008,128(2):251-262
This paper discusses tetrahedra with rational edges forming a geometric progression, focussing on whether they can have rational volume or rational face areas. We examine the 30 possible configurations of such tetrahedra and show that no face of any of these has rational area. We show that 28 of these configurations cannot have rational volume, and in the remaining two cases there are at most six possible examples, and none have been found. 相似文献