Triangulation of simple arbitrarily shaped polyhedra by cutting off one vertex at a time

We describe a heuristic method of triangulating arbitrarily shaped polyhedra without the addition of Steiner points. The polyhedra are simple, with each vertex connected to at least 3 other vertices (ie, coplanarity and colinearity are not considered). They may, however, be convex or concave and consist of dozens or even hundreds of facets. This makes the treatment universal enough to well meet the requirements of models used to simulate fractured rock masses. Certain concepts are defined in the work, eg, adjacent vertices, polygon of adjacent vertices, and closed cone of a vertex. A polygon of adjacent vertices of an apex can be subdivided into a set of nonoverlapping triangles without adding any vertices. These triangles, together with the apex, form tetrahedra whose union is the closed cone of the apex. The polyhedron is thus the union of the closed cones. Subsequently, we triangulate the polyhedron by gradually removing the closed cones of its vertices. The number of vertices of the polyhedron decreases by one each time a closed cone is removed. A block with n vertices can produce no more than n?3 tetrahedra. We present the analysis procedure and discuss the core issues of the method proposed.     

A new contact detection method for arbitrary dilated polyhedra with potential function in discrete element method

Contact detection significantly affects the computational efficiency of discrete element simulations, especially for irregularly shaped elements. The dilated polyhedron is constructed by the Minkowski sum of a dilated sphere and a core convex polyhedron. One of the greatest advantages of using the dilated polyhedron in contact detection lies in its ability to be solved by calculating the nearest distance between corresponding core polyhedra. The approximate envelope function (AEF) of a dilated polyhedron is formed by the weighted summation of the second-order dilated function of the polyhedral and spherical functions. The AEF can be used to represent the element in the optimization model for the contact center. Geometric calculations are then employed for the contact points on the core polyhedron, whereupon the contact detection is solved. The accuracy and stability of the proposed method by a 3-D Voronoi tessellation are validated using analytical solutions and previously published simulation results. The efficiency tests show that the speedup of the CPU-based multithread algorithm can reach 14 on a desktop. The direct shear test of the Voronoi shaped ballast is analyzed by this method. The shear stress under different vertical pressure is compared with previously published experimental and simulated results.     

多边形构型双边球形凸多面体解析计算方法

基于从平面单元到凸多面体空间单元拓扑映射的约束条件,以特征角点坐标作为变量,建立双边凸多面体约束方程组,求特征角点径长的变异系数的极小值,实现多边形构型凸多面体的球形优化,从而建立了一种可实现多边形构型双边球形凸多面体系列化构建的解析计算方法。将旋转对称性双边球形凸多面体对应的大矢跨比球冠应用于天线罩,具有以下显著优势:球形网壳结构具有良好的力学性能;由于多边形网格具有平面性,因此透波窗口便于做成薄膜单层形式,这是有利于天线罩取得良好电磁性能的因素。     

An approach to refining three-dimensional tetrahedral meshes based on Delaunay transformations

A technique for refining three-dimensional tetrahedral meshes is proposed in this paper. The proposed technique is capable of treating arbitrary unstructured tetrahedral meshes, convex or non-convex with multiple regions resulting in high quality constrained Delaunay triangulations. The tetrahedra generated are of high quality (nearly equilateral). Sliver tetrahedra, which present a real problem to many algorithms are not produced with the new method. The key to the generation of high quality tetrahedra is the iterative application of a set of topological transformations based on the Voronoi–Delaunay theory and a reposition of nodes technique. The computational requirements of the proposed technique are in linear relationship with the number of nodes and tetrahedra, making it ideal for direct employment in a fully automatic finite element analysis system for 3-D adaptive mesh refinement. Application to some test problems is presented to show the effectiveness and applicability of the new method.     

Structural features of cubic “polyhedra” up to 24 vertices with four-, five- and six-sided faces

We present a complete list of three-dimensional structures corresponding to all cubic polyhedral graphs with the number of vertices up to 24, which have only square, pentagonal and hexagonal cycles. It can be considered as an Atlas of possible small- and middle-sized cages of three-dimensional 4-coordinated frameworks. Adhering to graph-theoretical terminology, we use the term “polyhedron”. But, strictly speaking, most of the constructed three-dimensional figures are not polyhedra because their “faces” are not planar. In addition, many polyhedra are significantly different in shape from conventional fullerenes. The spiral codes are used as the main topological identifier of the polyhedra. Three-dimensional coordinates of polyhedra are calculated by minimizing the sum of the squared deviations of the edge lengths and distances between the second neighbors from the idealized values. It is concluded that the minimum value of this sum can be considered as a new supplementary identifier of polyhedra and as a measure of deviation of the polyhedral structure from the set of true face-regular polyhedra. An algorithm for constructing polyhedral structures with edges of the same length is proposed. Also, we discuss the geometric properties of the constructed polyhedra and their relation to the stability of molecular systems.     

A new mathematical model for the Weber location problem with a probabilistic polyhedral barrier

With the wide application of location theory in a variety of industries, the presence of barriers ?merits the attention of managers and engineers.? In this paper, we assess the Weber location problem in the presence of a polyhedral barrier which probabilistically occurs on a given horizontal barrier route in the rectilinear space. A left triangular distribution function is used for the starting point of the barrier and therefore an expected rectilinear barrier distance function is formulated. In addition, a modification of the polyhedral barrier is presented which is equivalent to the original problem. Therefore, a mixed integer nonlinear programming model, which has a nonconvex solution space, is presented. Furthermore, by decomposing the feasible space into a finite number of convex solution spaces, an exact heuristic solution method is proposed. Then, a lower bound problem based on the forbidden region is applied. Some theorems and an example are reported.     

Tetrahedral mesh generation in convex primitives

This paper presents a method for generating tetrahedral meshes in three-dimensional primitives. Given a set of closed and convex polyhedra having non-zero volume and some mesh controlling parameters, the polyhedra are automatically split to tetrahedra satisfying the criteria of standard finite element meshes. The algorithm tries to generate elements close to regular tetrahedra by maximizing locally the minimum solid angles associated to a set of a few neighbouring tetrahedra. The input parameters define the size of the tetrahedra and they can be used to increase or decrease the discretization locally. All the new nodes, which are not needed to describe the geometry, are generated automatically.     

Polyhedral particles for the discrete element method

The geometry of convex polyhedra is described by a set of half spaces. This geometry representation is used in the discrete element method to model polyhedral particles. An algorithm for contact detection and the calculation of the interaction forces for these particles is presented. Finally the presented model is exemplified by simulating the particle flow through a hopper.     

Ray tracing with a space-filling finite element mesh

A new ray-tracing technique is presented which does not work with ray–object intersections per se, but is based on the traversal of an unstructured tetrahedral mesh providing a convex enclosure of a scene of polyhedral objects. The tetrahedral mesh provides tight bounding and an adaptive subdivision of space. This non-hierarchical data structure is traversed adaptively until one is led directly and unconditionally to the first object intersected. Rendering times are directly related to the average thickness of the enclosing mesh since all tetrahedra are traversed in constant time. Since the proposed algorithm operates directly with volume elements, it allows for volumetric rendering effects. Volume rendering or anisotropic media can be implemented without any further effort. This is an important advantage as compared to usual techniques, which only operate on surface data. Timings for several examples show that the use of this type of ray-tracing technique, which is more suitable for general purpose visualization codes than traditional techniques, results in CPU times that are comparable with the best ray-tracing techniques presently used. This is an unexpected and important result, as the vectorization and parallclization of the proposed technique are straightforward, in contrast with traditional ray-tracing techniques.     

Pareto navigator for interactive nonlinear multiobjective optimization

We describe a new interactive learning-oriented method called Pareto navigator for nonlinear multiobjective optimization. In the method, first a polyhedral approximation of the Pareto optimal set is formed in the objective function space using a relatively small set of Pareto optimal solutions representing the Pareto optimal set. Then the decision maker can navigate around the polyhedral approximation and direct the search for promising regions where the most preferred solution could be located. In this way, the decision maker can learn about the interdependencies between the conflicting objectives and possibly adjust one’s preferences. Once an interesting region has been identified, the polyhedral approximation can be made more accurate in that region or the decision maker can ask for the closest counterpart in the actual Pareto optimal set. If desired, (s)he can continue with another interactive method from the solution obtained. Pareto navigator can be seen as a nonlinear extension of the linear Pareto race method. After the representative set of Pareto optimal solutions has been generated, Pareto navigator is computationally efficient because the computations are performed in the polyhedral approximation and for that reason function evaluations of the actual objective functions are not needed. Thus, the method is well suited especially for problems with computationally costly functions. Furthermore, thanks to the visualization technique used, the method is applicable also for problems with three or more objective functions, and in fact it is best suited for such problems. After introducing the method in more detail, we illustrate it and the underlying ideas with an example.     

Study on the structures of N-containing melilite Y2Si3O3N4 and Nd2Si2.5Al0.5O3.5N3.5

Rietveld refinements have been used to determine the structure of Y2Si3O3N4 from X-ray data and Nd2Si2.5Al0.5O3.5N3.5 from neutron powder diffraction data. The refinements show that in the melilite phase Y2Si3O3N4 and melilite solid solution Nd2Si2.5Al0.5O3.5N3.5 the distributions of cations and anions are almost identical. They are analogous to the akermanite (Ca2MgSi2O7) structure, with Si/Si,Al atoms at the origin and centre of the unit cell and with four N/N,O atoms forming the SiN4/(Si,Al)(N3.5O0.5) tetrahedra which share corners with SiO2N2/(Si,Al)O2.25N1.75 tetrahedra to form a continuous sheet structure. Each Y3+ or Nd3+ ion is surrounded by eight N/O atoms forming the coordination polyhedron in Y2Si3O3N4 and Nd2Si2.5Al0.5O3.5N3.5 respectively. The arrangement of Al, Si atoms in the tetrahedra in Nd2Si2.5Al0.5O3.5N3.5 structure is also discussed. This revised version was published online in November 2006 with corrections to the Cover Date.     

A new deterministic global optimization method for general twice-differentiable constrained nonlinear programming problems

A deterministic global optimization method that is applicable to general nonlinear programming problems composed of twice-differentiable objective and constraint functions is proposed. The method hybridizes the branch-and-bound algorithm and a convex cut function (CCF). For a given subregion, the difference of a convex underestimator that does not need an iterative local optimizer to determine the lower bound of the objective function is generated. If the obtained lower bound is located in an infeasible region, then the CCF is generated for constraints to cut this region. The cutting region generated by the CCF forms a hyperellipsoid and serves as the basis of a discarding rule for the selected subregion. However, the convergence rate decreases as the number of cutting regions increases. To accelerate the convergence rate, an inclusion relation between two hyperellipsoids should be applied in order to reduce the number of cutting regions. It is shown that the two-hyperellipsoid inclusion relation is determined by maximizing a quadratic function over a sphere, which is a special case of a trust region subproblem. The proposed method is applied to twelve nonlinear programming test problems and five engineering design problems. Numerical results show that the proposed method converges in a finite calculation time and produces accurate solutions.     

非完整形态KH2PO4晶体薄表面层生长特性

实时观察了非完整形态的KH2PO4 (KDP)晶体在过饱和溶液中以薄表面层生长形式恢复其结晶学形态的过程.提出了晶体形态恢复的“最小多面体原理”,即:在自由生长系统中,对于非完整形态的KDP晶体,当其以薄表面层形式恢复其结晶学完整形态时,薄表面层将选择相应的奇异面方向生长,使晶体形态最终恢复为一个由各结晶学显露面所围成的体积最小的凸多面体.利用PBC理论分析了生长基元在非结晶学显露面上的附着情况并阐述了锥顶处薄表面层倒垂生长的原因.结果表明,薄表面层形成与晶体非完整结晶学形态及不均匀水动力学条件相关联.柱面凹角与非正常棱边及Z切片正常棱角均可诱发产生薄表面层,且薄表面层生长终止于其所在奇异面的正常结晶学晶棱.     

Particle shape effects in discrete element modelling of cohesive angular particles

This paper investigates the effect of particle angularity on general granular response concentrating on flow and stress-strain behaviour. A 2D polygon DEM model is developed to a 3D polyhedron model. The effect of particle shape on the response of polygons in simple shear and polyhedra under gravity flow is investigated using regular shapes with rounded vertices. The study concentrates on the angularity rather than aspect ratio by comparing circles, near squares and near equilateral triangles in 2D and spheres, tetrahedra and octahedra in 3D. In summary the more angular the particle the greater the resistance to the forcing load and the flowability is reduced. A mix of spheres and octahedra demonstrates an approximate linear combination of effects.     

Triangular meshes for regions of complicated shape

A method using techniques of computational geometry for triangular mesh generation for regions with complicated polygonal boundaries in the plane is presented. The input to the method includes the desired number of triangles and a mesh smoothness parameter to be specified, as well as the polygonal curves of the region's boundary and, possibly, internal interfaces. The triangulation generated conforms to the length scales of the edges of the boundary curves, but the method can be extended to provide additional control of the triangulation by a mesh distribution function. The region is decomposed into convex subregions in two stages, such that triangles of one length scale can be generated in each subregion. This decomposition uses algorithms which run in times that are linear in the number of vertices of the input polygons. Details of two major computational experiments are provided.     

Simulated airflow and rigid fiber behavior in a realistic nasal airway model

Particles may become airborne due to numerous natural and anthropogenic processes. The nose provides protection for the respiratory system through deposition that prevents particles from reaching more sensitive regions. A series of simulations have been conducted to better predict the deposition efficiency within the nasal passages. Computational fluid dynamics coupled with Lagrangian particle tracking have been used to estimate the deposition of both fibrous and spherical particles. MRI data was collected from the left and right passages of an adult male of mass 120.2?kg and height 181.6?cm. The two passages were constructed into separate computational volumes consisting of approximately 950,000 unstructured polyhedral cells each. A steady, incompressible, laminar flow model was used to simulate the inhalation portion of a human breathing cycle. Volumetric flow rates were varied to represent the full range of human nasal breathing. Qualitatively, the simulated airflow field was shown to agree well with previously published in vitro studies on different nasal replicas. An empirical expression for pressure drop as a function of flow rate that takes the form of Rohrer’s equation is proposed based on the measured data. Deposition efficiency was shown to depend on fiber aspect ratio, particle size, and flow rate. Nasal geometry was also identified as a key factor affecting deposition. A modified Stokes number is proposed along with a novel empirical expression for fiber deposition efficiency in the nasal airway.     

有间隙多层板接触分析的广义协调元法

从有间隙多层板接触系统分区广义势能泛函出发,以广义协调理论为基础,通过建立和分析板单元区、接触单元区的势能泛函,提出求解多层板接触问题的广义协调元法;并构造了广义协调矩形板-板接触单元PZC21。数值结果表明,单元PZC21具有较好的稳定性和收敛性。     

Calculation of Eddy currents in terms of H on hexahedra

The eddy current equations are formulated here in terms of H [1] instead of the more usual vector potential A [2,3]. In both cases a combination with a scalar potential is necessary in the non conducting regions. In the case of A this leads to either a non symmetric or not positive definite system of equations to be solved. This is avoided by the formulation in H, but special elements have to be chosen in order to satisfy the interface conditions between the two regions. The construction of such elements on tetrahedra or rectangular blocks can be found in [4]. The construction for hexahedra, or more specifically, isoparametric bricks, is shown here. Compared to filling a hexahedron with tetrahedra, this method reduces the number of unknowns by a half. The computed approximations for the eddy currents are exactly non divergent.     

区间模型非概率可靠性指标的一维优化算法

证明了基于区间模型的非概率可靠性指标只可能存在于:标准化区间向量张成的凸域及其扩展空间中,通过原点和凸域顶点的有限条超射线与标准化失效面的某个交点处,从而极大地缩小了优化方法求取非概率可靠性指标的可行域,使放弃计算结果极易扩张的区间运算法则和计算量太大的高维寻优方法成为可能。提出了求取非概率可靠性指标的一维优化方法,讨论了一维优化方法搜索区间关于0对称且具有半径递减的特性,利用该特性明显提高一维优化算法的效率。     

A multigrid accelerated hybrid unstructured mesh method for 3D compressible turbulent flow

 A cell vertex finite volume method for the solution of steady compressible turbulent flow problems on unstructured hybrid meshes of tetrahedra, prisms, pyramids and hexahedra is described. These hybrid meshes are constructed by firstly discretising the computational domain using tetrahedral elements and then by merging certain tetrahedra. A one equation turbulence model is employed and the solution of the steady flow equations is obtained by explicit relaxation. The solution process is accelerated by the addition of a multigrid method, in which the coarse meshes are generated by agglomeration, and by parallelisation. The approach is shown to be effective for the simulation of a number of 3D flows of current practical interest. Sponsored by The Research Council of Norway, project number 125676/410 Dedicated to the memory of Prof. Mike Crisfield, a respected colleague