Domain discretization by Voronoi tessellation

Domain discretization is based on a Voronoi diagram on an irregular set of points, which serve as computational nodes for both the elasticity and diffusion analyses. In three dimensions, the Voronoi diagram is a set of convex polyhedra that fill the domain. By definition, the Voronoi polyhedron (or cell) associated with node i is the set of points closer to node i than all other nodes in the domain (Okabe et al., 1992).

In this expression, X represents a point by its spatial coordinates and d denotes distance. Discretization starts with the specification of coordinates for the bounding box that encloses the three-dimensional domain. Thereafter, the following steps are taken during the discretization process (Fig. 1):

  • Insertion of computational nodes into the domain, based on coordinates determined from a pseudo-random number generator. By specifying a minimum allowable distance between nodes, the domain eventually becomes saturated with such points. Trial points are rejected with increasing frequency as the domain is filled. A partitioned domain search is used to accelerate this computationally expensive process (Yip et al., 2005). For three-dimensional elasticity problems, each node has six degrees of freedom (three translational and three rotational degrees of freedom); only one degree of freedom per node is required for discretizing the scalar field in the diffusion analyses;
  • Placement of a set of auxiliary points related to boundary construction (Bolander and Saito, 1998; Yip et al., 2005). For a node enclosed in a convex domain with M planar surfaces, a corresponding auxiliary point is placed outside the domain for each of the M surfaces. For each surface, the node and corresponding auxiliary point are equidistant from and on a line that is normal to the surface, thus extending the Voronoi construction to exactly meet the desired surface; and
  • Voronoi tessellation of the entire point set, including auxiliary points. There are a number of procedures for constructing the Voronoi diagram directly from the generated point set (Okabe et al., 1992). Here, the Voronoi diagram is constructed from its dual, the Delaunay tessellation, since the latter is generally easier to construct and a robust program was available for doing so (Taniguchi et al., 2002). The edges of the Delaunay tetrahedra indicate the lattice element connectivity between the nodal points (Fig. 1b).

Figure 1: Voronoi discretization of irregular point set

By strategically introducing nodes and auxiliary points, prior to the random filling process, various geometries can be discretized, including non-convex domains (Yip et al., 2005), as shown in Fig. 2. It is possible to explicitly model material features, including the boundaries between two phases (which generally do not run along the grid lines produced by a regular triangular or square lattice), such as for the spherical inclusions shown in Fig. 2.

Figure 2: a) Three point bend test of notched concrete beam; b) modeling of spherical inclusions

return

 

References

  1. Okabe, A., Boots, B. and Sugihara, K., "Spatial Tessellations - Concepts and Applications of Voronoi Diagrams." (John Wiley & Sons, Chichester, UK, 1992).
  2. Yip, M., Mohle, J. and Bolander, J.E., "Automated modeling of 3-D structural components using irregular lattices." Computer-Aided Civil and Infrastructure Engng (submitted for review).
  3. Bolander, J.E. and Saito, S., "Fracture analysis using spring networks with random geometry." Engng. Fracture Mech. 61, 1998, 569-591.
  4. Taniguchi, T., Yamashita, Y. and Moriwaki, K., "Generation of arbitrary 3-dimensional domain from nodes on its surface." 8th Conference on Numerical Grid Generation, Hawaii, USA, June 2002.