Browsing by Author "Si, Hang"
Now showing 1 - 20 of 27
Results Per Page
Sort Options
- Item3D boundary recovery by constrained Delaunay tetrahedralization(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2010) Si, Hang; Gärtner, KlausThree-dimensional boundary recovery is a fundamental problem in mesh generation. In this paper, we propose a practical algorithm for solving this problem. Our algorithm is based on the construction of a it constrained Delaunay tetrahedralization (CDT) for a set of constraints (segments and facets). The algorithm adds additional points (so-called Steiner points) on segments only. The Steiner points are chosen in such a way that the resulting subsegments are Delaunay and their lengths are not unnecessarily short. It is theoretically guaranteed that the facets can be recovered without using Steiner points. The complexity of this algorithm is analyzed. The proposed algorithm has been implemented. Its performance is reported through various application examples
- ItemAdaptive tetrahedral mesh generation by constrained delaunay refinement(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2006) Si, HangThis paper discusses the problem of refining a constrained Delaunay tetrahedralization (CDT) for adaptive numerical simulation. A simple and efficient algorithm which makes use of the classical Delaunay refinement scheme is proposed. It generates an isotropic tetrahedral mesh corresponding to a sizing function which can be either user-specified or automatically derived from the input CDT. The quality of the produced meshes is guaranteed, i.e., most output tetrahedra have their circumradius-to-shortest-edge ratios bounded except those in the neighborhood of small input angles. Good mesh conformity can be obtained for smoothly changing sizing information. The algorithm has been implemented. Various examples are provided to illustrate its theoretical aspects as well as practical performance.
- ItemAn Anisoptropic Surface Remeshing Strategy Combining Higher Dimensional Embedding with Radial Basis Functions(Amsterdam [u.a.] : Elsevier, 2016) Dassi, Franco; Farrell, Patricio; Si, HangMany applications heavily rely on piecewise triangular meshes to describe complex surface geometries. High-quality meshes significantly improve numerical simulations. In practice, however, one often has to deal with several challenges. Some regions in the initial mesh may be overrefined, others too coarse. Additionally, the triangles may be too thin or not properly oriented. We present a novel mesh adaptation procedure which greatly improves the problematic input mesh and overcomes all of these drawbacks. By coupling surface reconstruction via radial basis functions with the higher dimensional embedding surface remeshing technique, we can automatically generate anisotropic meshes. Moreover, we are not only able to fill or coarsen certain mesh regions but also align the triangles according to the curvature of the reconstructed surface. This yields an acceptable trade-off between computational complexity and accuracy.
- ItemAnisotropic finite element mesh adaptation via higher dimensional embedding(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2015) Dassi, Franco; Si, Hang; Perotto, Simona; Streckenbach, TimoIn this paper we provide a novel anisotropic mesh adaptation technique for adaptive finite element analysis. It is based on the concept of higher dimensional embedding, which was exploited in [1-4] to obtain an anisotropic curvature adapted mesh that fits a complex surface in ℝ3. In the context of adaptive finite element simulation, the solution (which is an unknown function ƒ: Ω ⊂; ℝd → ℝ) is sought by iteratively modifying a finite element mesh according to a mesh sizing field described via a (discrete) metric tensor field that is typically obtained through an error estimator. We proposed to use a higher dimensional embedding, Φf(x) := (x1, …, xd, s f (x1, …, xd), s ∇ f (x1, …, xd))t, instead of the mesh sizing field for the mesh adaption. This embedding contains both informations of the function ƒ itself and its gradient. An isotropic mesh in this embedded space will correspond to an anisotropic mesh in the actual space, where the mesh elements are stretched and aligned according to the features of the function ƒ. To better capture the anisotropy and gradation of the mesh, it is necessary to balance the contribution of the components in this embedding. We have properly adjusted Φf(x) for adaptive finite element analysis. To better understand and validate the proposed mesh adaptation strategy, we first provide a series of experimental tests for piecewise linear interpolation of known functions. We then applied this approach in an adaptive finite element solution of partial differential equations. Both tests are performed on two-dimensional domains in which adaptive triangular meshes are generated. We compared these results with the ones obtained by the software BAMG - a metric-based adaptive mesh generator. The errors measured in the L2 norm are comparable. Moreover, our meshes captured the anisotropy more accurately than the meshes of BAMG.
- ItemAnisotropic Finite Element Mesh Adaptation via Higher Dimensional Embedding(Amsterdam [u.a.] : Elsevier, 2015) Dassi, Franco; Si, Hang; Perotto, Simona; Streckenbach, TimoIn this paper we provide a novel anisotropic mesh adaptation technique for adaptive finite element analysis. It is based on the concept of higher dimensional embedding, which was exploited in [1], [2], [3], [4] to obtain an anisotropic curvature adapted mesh that fits a complex surface in R3. In the context of adaptive finite element simulation, the solution (which is an unknown function f : Ω ⊂ d → ) is sought by iteratively modifying a finite element mesh according to a mesh sizing field described via a (discrete) metric tensor field that is typically obtained through an error estimator. We proposed to use a higher dimensional embedding, Φf (x):= (x1, …, xd, s f (x1, …, xd), s ▿ f (x1, …, xd))t, instead of the mesh sizing field for the mesh adaption. This embedding contains both informations of the function f itself and its gradient. An isotropic mesh in this embedded space will correspond to an anisotropic mesh in the actual space, where the mesh elements are stretched and aligned according to the features of the function f. To better capture the anisotropy and gradation of the mesh, it is necessary to balance the contribution of the components in this embedding. We have properly adjusted Φf (x) for adaptive finite element analysis. To better understand and validate the proposed mesh adaptation strategy, we first provide a series of experimental tests for piecewise linear interpolation of known functions. We then applied this approach in an adaptive finite element solution of partial differential equations. Both tests are performed on two-dimensional domains in which adaptive triangular meshes are generated. We compared these results with the ones obtained by the software BAMG – a metric-based adaptive mesh generator. The errors measured in the L2 norm are comparable. Moreover, our meshes captured the anisotropy more accurately than the meshes of BAMG.
- ItemA curvature-adapted anisotropic surface remeshing method(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2013) Dassi, Franco; Si, HangWe present a new method for remeshing surfaces that respect the intrinsic anisotropy of the surfaces. In particular, we use the normal informations of the surfaces, and embed the surfaces into a higher dimensional space (here we use 6d). This allow us to form an isotropic mesh optimization problem in this embedded space. Starting from an initial mesh of a surface, we optimize the mesh by improving the mesh quality measured in the embedded space. The mesh is optimized by combining common local modifications operations, i.e., edge flip, edge contraction, vertex smoothing, and vertex insertion. All perations are applied directly on the 3d surface mesh. This method results a curvature-adapted mesh of the surface. This method can be easily adapted to mesh multi-patches surfaces, i.e., containing corner singularities and sharp features. The reliability and robustness of the proposed re-meshing technique is provided by a large number of examples including both implicit surfaces and CAD models.
- ItemThe existence of triangulations of non-convex polyhedra without new vertices(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2008) Si, HangIt is well known that a simple three-dimensional non-convex polyhedron may not be triangulated without using new vertices (so-called it Steiner points). In this paper, we prove a condition that guarantees the existence of a triangulation of a non-convex polyhedron (of any dimension) without Steiner points. We briefly discuss algorithms for efficiently triangulating three-dimensional polyhedra.
- ItemGeneralized Regular Quadrilateral Mesh Generation based on Surface Foliation(Amsterdam [u.a.] : Elsevier, 2017) Lei, Na; Zheng, Xiaopeng; Si, Hang; Luo, Zhongxuan; Gu, XianfengThis work introduces a novel algorithm for quad-mesh generation based on surface foliation theory. The algorithm is based on the equivalence among colorable quad-meshes, measure foliations and holomorphic differentials. The holomorphic differentials can be obtained by graph-valued harmonic maps. The algorithm has several merits: it can be applied for surfaces with general topologies; the resulting quad-meshes have global tensor product structure and the least number of singularities; the algorithmic pipeline is fully automatic. The experimental results demonstrate the efficiency and efficacy of the proposed method.
- ItemGuaranteed quality isotropic surface remeshing based on uniformization(Amsterdam [u.a.] : Elsevier, 2017) Ma, Ming; Yu, Xiaokang; Lei, Na; Si, Hang; Gu, XianfengSurface remeshing plays a significant role in computer graphics and visualization. Numerous surface remeshing methods have been developed to produce high quality meshes. Generally, the mesh quality is improved in terms of vertex sampling, regularity, triangle size and triangle shape. Many of such surface remeshing methods are based on Delaunay refinement. In particular, some surface remeshing methods generate high quality meshes by performing the planar Delaunay refinement on the conformal uniformization domain. However, most of these methods can only handle topological disks. Even though some methods can cope with high-genus surfaces, they require partitioning a high-genus surface into multiple simply connected segments, and remesh each segment in the parameterized domain. In this work, we propose a novel surface remeshing method based on uniformization theorem using dynamic discrete Yamabe flow and Delaunay refinement, which is capable of handling surfaces with complicated topologies, without the need of partitioning. The proposed method has the following merits: Dimension deduction, it converts all 3D surface remeshing to 2D planar meshing; Theoretic rigor, the existence of the constant curvature measures and the lower bound of the corner angles of the generated meshes can be proven. Experimental results demonstrate the efficiency and efficacy of our proposed method.
- ItemHigher-quality tetrahedral mesh generation for domains small angles by constrained Delaunay refinement(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2014) Shewchuk, Jonathan Richard; Si, HangAlgorithms for generating Delaunay tetrahedral meshes have difficulty with domains whose boundary polygons meet at small angles. The requirement that all tetrahedra be Delaunay often forces mesh generators to overrefine near small domain angles
- ItemMesh smoothing: An MMPDE approach(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2015) Huang, Weizhang; Kamenski, Lennard; Si, HangWe study a mesh smoothing algorithm based on the moving mesh PDE (MMPDE) method. For the MMPDE itself, we employ a simple and efficient direct geometric discretization of the underlying meshing functional on simplicial meshes. The nodal mesh velocities can be expressed in a simple, analytical matrix form, which makes the implementation of the method relatively easy and simple. Numerical examples are provided.
- ItemA novel surface remeshing scheme via higher dimensional embedding and radial basis functions(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2016) Dassi, Franco; Farrell, Patricio; Si, HangMany applications heavily rely on piecewise triangular meshes to describe complex surface geometries. High-quality meshes significantly improve numerical simulations. In practice, however, one often has to deal with several challenges. Some regions in the initial mesh may be overrefined, others too coarse. Additionally, the triangles may be too thin or not properly oriented. We present a novel mesh adaptation procedure which greatly improves the problematic input mesh and overcomes all of these drawbacks. By coupling surface reconstruction via radial basis functions with the higher dimensional embedding surface remeshing technique, we can automatically generate anisotropic meshes. Moreover, we are not only able to fill or coarsen certain mesh regions but also align the triangles according to the curvature of the reconstructed surface. This yields an acceptable trade-off between computational complexity and accuracy.
- ItemOn decomposition of embedded prismatoids in $R^3$ without additional points(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2019) Si, HangThis paper considers three-dimensional prismatoids which can be embedded in ℝ³ A subclass of this family are twisted prisms, which includes the family of non-triangulable Scönhardt polyhedra [12, 10]. We call a prismatoid decomposable if it can be cut into two smaller prismatoids (which have smaller volumes) without using additional points. Otherwise it is indecomposable. The indecomposable property implies the non-triangulable property of a prismatoid but not vice versa. In this paper we prove two basic facts about the decomposability of embedded prismatoid in ℝ³ with convex bases. Let P be such a prismatoid, call an edge interior edge of P if its both endpoints are vertices of P and its interior lies inside P. Our first result is a condition to characterise indecomposable twisted prisms. It states that a twisted prism is indecomposable without additional points if and only if it allows no interior edge. Our second result shows that any embedded prismatoid in ℝ³ with convex base polygons can be decomposed into the union of two sets (one of them may be empty): a set of tetrahedra and a set of indecomposable twisted prisms, such that all elements in these two sets have disjoint interiors.
- ItemOn indecomposable polyhedra and the number of interior Steiner points(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2015) Goerigk, Nadja; Si, HangThe existence of 3d indecomposable polyhedra, that is, the interior of every such polyhedron cannot be decomposed into a set of tetrahedra whose vertices are all of the given polyhedron, is well-known. While the geometry and combinatorial structure of such polyhedra are much less studied. In this article, we first investigate the geometry of some wellknown examples, the so-called Schönhardt polyhedron [Schönhardt, 1928] and the Bagemihl's generalization of it [Bagemihl, 1948], which will be called Bagemihl polyhedra. We provide a construction of an interior point, so-called Steiner point, which can be used to tetrahedralize the Schönhardt and the Bagemihl polyhedra. We then provide a construction of a larger class of three-dimensional indecomposable polyhedra which often appear in grid generation problems. We show that such polyhedra have the same combinatorial structure as the Schönhardt and Bagemihl polyhedra, but they may need more than one interior Steiner point to be tetrahedralized. Given such a polyhedron with n ≥ 6 vertices, we show that it can be tetrahedralized by adding at most ... interior Steiner points. We also show that this number is optimal in the worst case.
- ItemOn Indecomposable Polyhedra and the Number of Steiner Points(Amsterdam [u.a.] : Elsevier, 2015) Goerigk, Nadja; Si, HangThe existence of indecomposable polyhedra, that is, the interior of every such polyhedron cannot be decomposed into a set of tetrahedra whose vertices are all of the given polyhedron, is well-known. However, the geometry and combinatorial structure of such polyhedra are much less studied. In this article, we investigate the structure of some well-known examples, the so-called Schönhardt polyhedron [10] and the Bagemihl's generalization of it [1], which will be called Bagemihl's polyhedra. We provide a construction of an additional point, so-called Steiner point, which can be used to decompose the Schönhardt and the Bagemihl's polyhedra. We then provide a construction of a larger class of three-dimensional indecomposable polyhedra which often appear in grid generation problems. We show that such polyhedra have the same combinatorial structure as the Schönhardt's and Bagemihl's polyhedra, but they may need more than one Steiner point to be decomposed. Given such a polyhedron with n ≥ 6 vertices, we show that it can be decomposed by adding at most interior Steiner points. We also show that this number is optimal in theworst case.
- ItemOn monotone sequences of directed flips, triangulations of polyhedra, and structural properties of a directed flip graph(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2018) Si, HangThis paper studied the geometric and combinatorial aspects of the classical Lawsons flip algorithm [21, 22]. Let A be a finite point set in R2 and : A R be a height function which lifts the vertices of A into R3. Every flip in triangulations of A can be assigned a direction [6, Definition 6.1.1]. A sequence of directed flips is monotone if all its flips follow the same direction. We first established a relatively obvious relation between monotone sequences of directed flips on triangulations of A and triangulations of the lifted point set A in R3. We then studied the structural properties of a directed flip graph (a poset) on the set of all triangulations of A. We proved several general properties of this poset which clearly explain when Lawsons algorithm works and why it may fail in general. We further characterised the triangulations which cause failure of Lawsons algorithm, and showed that they must contain redundant interior vertices which are not removable by directed flips. A special case of this result in 3d has been shown in [19]. As an application, we described a simple algorithm to triangulate a special class of 3d non-convex polyhedra without using additional vertices. We prove sufficient conditions for the termination of this algorithm, and show it runs in O(n3) time, where n is the number of input vertices.
- ItemOn Tetrahedralisations Containing Knotted and Linked Line Segments(Amsterdam [u.a.] : Elsevier, 2017) Si, Hang; Ren, Yuxue; Lei, Na; Gu, XianfengThis paper considers a set of twisted line segments in 3d such that they form a knot (a closed curve) or a link of two closed curves. Such line segments appear on the boundary of a family of 3d indecomposable polyhedra (like the Schönhardt polyhedron) whose interior cannot be tetrahedralised without additional vertices added. On the other hand, a 3d (non-convex) polyhedron whose boundary contains such line segments may still be decomposable as long as the twist is not too large. It is therefore interesting to consider the question: when there exists a tetrahedralisation contains a given set of knotted or linked line segments? In this paper, we studied a simplified question with the assumption that all vertices of the line segments are in convex position. It is straightforward to show that no tetrahedralisation of 6 vertices (the three-line-segments case) can contain a trefoil knot. Things become interesting when the number of line segments increases. Since it is necessary to create new interior edges to form a tetrahedralisation. We provided a detailed analysis for the case of a set of 4 line segments. This leads to a crucial condition on the orientation of pairs of new interior edges which determines whether this set is decomposable or not. We then prove a new theorem about the decomposability for a set of n (n ≥ 3) knotted or linked line segments. This theorem implies that the family of polyhedra generalised from the Schonhardt polyhedron by Rambau [1] are all indecomposable.
- ItemOn tetrahedralisations of reduced Chazelle polyhedra with interior Steiner points(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2015) Si, Hang; Goerigk, NadjaThe polyhedron constructed by Chazelle, known as Chazelle polyhedron [4], is an important example in many partitioning problems. In this paper, we study the problem of tetrahedralising a Chazelle polyhedron without modifying its exterior boundary. It is motivated by a crucial step in 3d finite element mesh generation in which a set of arbitrary boundary constraints (edges or faces) need to be entirely preserved. We first reduce the volume of a Chazelle polyhedron by removing the regions that are tetrahedralisable. This leads to a 3d polyhedron which may not be tetrahedralisable unless extra points, so-called Steiner points, are added. We call it a reduced Chazelle polyhedron. We define a set of interior Steiner points that ensures the existence of a tetrahedralisation of the reduced Chazelle polyhedron. Our proof uses a natural correspondence that any sequence of edge flips converting one triangulation of a convex polygon into another gives a tetrahedralization of a 3d polyhedron which have the two triangulations as its boundary. Finally, we exhibit a larger family of reduced Chazelle polyhedra which includes the same combinatorial structure of the Schönhardt polyhedron. Our placement of interior Steiner points also applies to tetrahedralise polyhedra in this family.
- ItemOn Tetrahedralisations of Reduced Chazelle Polyhedra with Interior Steiner Points(Amsterdam [u.a.] : Elsevier, 2016) Si, Hang; Goerigk, NadjaThe non-convex polyhedron constructed by Chazelle, known as the Chazelle polyhedron [4], establishes a quadratic lower bound on the minimum number of convex pieces for the 3d polyhedron partitioning problem. In this paper, we study the problem of tetrahedralising the Chazelle polyhedron without modifying its exterior boundary. It is motivated by a crucial step in tetrahedral mesh generation in which a set of arbitrary constraints (edges or faces) need to be entirely preserved. The goal of this study is to gain more knowledge about the family of 3d indecomposable polyhedra which needs additional points, so-called Steiner points, to be tetrahedralised. The requirement of only using interior Steiner points for the Chazelle polyhedron is extremely challenging. We first “cut off” the volume of the Chazelle polyhedron by removing the regions that are tetrahedralisable. This leads to a 3d non-convex polyhedron whose vertices are all in the two slightly shifted saddle surfaces which are used to construct the Chazelle polyhedron. We call it the reduced Chazelle polyhedron. It is an indecomposable polyhedron. We then give a set of (N + 1)2 interior Steiner points that ensures the existence of a tetrahedralisation of the reduced Chazelle polyhedron with 4(N + 1) vertices. The proof is done by transforming a 3d tetrahedralisation problem into a 2d edge flip problem. In particular, we design an edge splitting and flipping algorithm and prove that it gives to a tetrahedralisation of the reduced Chazelle polyhedron.
- ItemPreface(Amsterdam [u.a.] : Elsevier, 2016) Canann, Scott; Owen, Steven; Si, Hang[No abstract available]