1 Introduction

In the twenty-first century, as free-form design has gained popularity, several free-form grid structures have appeared throughout many cities, becoming landmarks of the region with their splendid visual effects [1,2,3]. Compared to a conventional surface, a free-form surface is unable to be expressed accurately by means of one or several analytic functions, and the curvature of such a surface is a complex shape, as shown in Fig. 1. Therefore, with the rapid rise of free-form grid structures, an urgent problem has come along with it, namely, how to mesh these changeable free-form structures to show their esthetic implications without losing the architectural vision of smoothly shaped building envelopes.

Fig. 1
figure 1

Free-form structures

Full size image

Topology optimization is one of the effective methods used to create an efficient structural grid on an imposed surface. Peter and Gilbert [4], Paul et al. [5], and Gao et al. [6] have made substantial progress in this area. However, as Peter [4] pointed out that a grid generated via topology optimization cannot be applied to the actual projects directly and further refinement is needed.

To obtain a better grid with the excellent mechanical properties over a free-form surface, Winslow et al. [7, 8] presented a new algorithm that considers the mechanical performance based on a traditional genetic algorithm. Su et al. [9] also conducted a similar study in this area, proposing an improved wave-front method, which used the structural stress trajectory as the guideline and pushed the grid forward in the direction of the guideline. This can avoid blindness and disorder in the advancement process. However, the disadvantage of this method is that the uniformity of the grid is poor, and some distorted unit cells appear.

Sometimes, one must admit that architects are most concerned about whether the grid has the advantages of fluency and uniformity, and the structural mechanical properties seem to be less important. Some research has reported the progress of grid generation over a free-form surface without taking their structural performance into account. Ding [10, 11] proposed a new method for a free-form surface grid generation, referred to as the iso-parametric line dividing method, which is based on a non-uniform rational B-spline (NRUBS) curve. Li [12] proposed a re-interpolation reflection meshing method to avoid the uneven grids caused by the distortion curvature. Moreover, the extension of the grid meshing modes and the optimization of the grid system were also discussed. Wei [13] and Gao [14] concentrated on the mesh generation based on surface flattening and mapping theory. Persson and Strang [15] developed an iterative technique for the actual mesh generation based on a physical analogy between a simplex mesh and a truss structure. Shimada and Gossard et al. [16,17,18] invented an interesting grid generation method called bubble mesh generation. In its actual implementation, the bubble method generated node configurations that yielded virtually no ill-shaped triangles or tetrahedrals. Similar to the bubble method, Zheleznyakova [19, 20] regarded the grid nodes as interacting particles and developed a new approach for the triangular grid generation based on the molecular dynamics method. However, the drawback of this method is that the grids generated by it are not smooth enough to be directly applied to actual projects.

To obtain a triangular grid with a uniform size and fluent lines on a given free-form surface quickly and efficiently, an automatic triangular grid generation method based on Coulomb’s law is proposed in this paper, which will be referred to as a particle self-organizing system (PSOS). In this system, the nodes of the spatial structure are considered to be interacting particles in an electric field. They move towards each other under the drive of a Coulomb force and complete the process of self-organization. The particle placement is determined via Monte Carlo simulation and well-shaped triangles are created after connecting the particles by constrained Delaunay triangulation. According to the different motion space of the particles, the particle self-organizing system can be divided into a direct method and an indirect method. The particle motion space of the direct method is the physical space of the surface, where a grid is generated directly on the physical domain and no mapping process is needed. The particle motion space of the indirect method is the parameter space of the surface, where the grid layout on parameter space is first obtained, and then it is mapped back to the space surface. The efficiency of the new approach is demonstrated using some engineering design problems, which also demonstrate its ability to generate grids with excellent quality and fluent lines on a given surface.

2 Particle self-organizing system

2.1 Coulomb’s law

The particle self-organizing system (PSOS) was developed based on a natural process known as Coulomb’s Law, which clarifies the law of interaction between charged bodies. It was first published in 1784 by French physicist Coulomb and was verified by a torsion balance experiment, as shown in Fig. 2. Coulomb confirmed that the force of the mutual impact of two electric charges is directly proportional to the product of the value of their charge and inversely proportional to the square of the distance between their middles. The force is along the straight line joining them. If the two charges have the same sign, the electrostatic force between them is repulsive; if they have different signs, the force between them is attractive. As shown in Fig. 3, the greater the distance between two charges, the smaller the Coulomb force.

Fig. 2
figure 2

Coulomb’s torsion balance experiment

Full size image
Fig. 3
figure 3

Schematic diagram of Coulomb’s law

Full size image

Coulomb’s law can also be stated as a simple mathematical expression. The vector form of the mathematical equation is as follows:

$$F\,=\,k\frac{{{q_1}{q_2}}}{{{r^2}}}\mathop r\limits^{ \to } ,$$
(1)

where \({q_1},{q_2}\) are the signed magnitudes of the charges, r is the distance between the charges, and k is so-called the factor of proportion expressed in SI system by the following:

$$k\,=\,\frac{1}{{4\pi {\varepsilon _0}}},$$
(2)

where \({\varepsilon _0}\) is the intermediate electric constant in the vacuum; therefore, k is also a constant.

2.2 Electric field intensity

There are interactions between stationary electric charges that can be expressed by Coulomb’s Law. In addition, every charge in the electric field forms an electric field around it. At different locations of the charge, the intensity of the electric field differs. The charge generating the electric field intensity is the source charge, and it is assumed that there is a probe charge located not far from the source charge. Then, the electric field intensity of the probe charge can be defined as follows:

$$E\,=\,F/q,$$
(3)

where F is the Coulomb force and q is the test charge at electric field. This is the definition of electric field intensity, which reflects the nature of electric field and has nothing to do with the value of the probe charge.

2.3 Mechanism of the PSOS

2.3.1 Coulomb force as a driving force

Inspired by Coulomb’s Law, an automatic triangular grid generation method for a free-form single-layer grid structures is developed, which is referred to as the particle self-organizing system (PSOS). In this system, nodes of the spatial structure are considered to be interacting particles in the electric field. The Coulomb force between the charged particles is the driving force, which forces the particles to move towards each other. It is assumed that each charged particle has the same value but a different symbol; that is, \(\left| {{q_1}} \right|=\left| {{q_2}} \right|\), and then, the Coulomb force can be expressed as follows:

$$F\,=\,k\frac{{{Q_1}}}{{{r^2}}},$$
(4)

where \({Q_1}=\left| {{q_1}{q_2}} \right|\) and \({q_1},{q_2}\) are the value of the charges, so the value of the Coulomb force in this paper is only related to distance between two charges. For free-form single-layer grid structures, the Coulomb force between two different nodes can be written as follows:

$$F=1/\sqrt {{{({x_2} - {x_1})}^2}+{{({y_2} - {y_1})}^2}+{{({z_2} - {z_1})}^2}} ,$$
(5)

where \({x_i},{y_i},{z_i}\) are the three-dimensional coordinates of the nodes.

2.3.2 The minimum equivalent field intensity as the target

In PSOS, we ignore the direction of the electric field intensity and only consider its magnitude. Therefore, if i is the source charge that carries a total positive charge Q, the electric field intensity produced at a distance from the source charge \({r_{ij}}\) is \({E_{{\text{ij}}}}\,=\,k\frac{Q}{{{r_{ij}}^{2}}}\), as shown in Fig. 4.

Fig. 4
figure 4

Electric field intensity diagram

Full size image

Furthermore, we explicitly define that every particle only interacts with the nearest six particles, and the interaction with the rest of particles is negligible. This is similar to superposition principle of the electric field intensity; the equivalent electric field intensity at particle j is the sum of the electric field intensity produced by the nearest six particles, as shown in Fig. 5. It is worth noting that the equivalent electric field intensity at a certain point is not the vector sum of the electric field intensity produced by the surrounding charge at this point, but only the algebraic sum.

Fig. 5
figure 5

Calculation of equivalent electric field intensity

Full size image

As shown in Fig. 5a, the Coulomb force of charged particle j in the electric field is as follows:

$$\mathop {{f_j}}\limits^{ \to } =\sum\limits_{{i=1}}^{n} {{{\mathop f\limits^{ \to } }_i}} .$$
(6)

According to the principle of superposition, the electric field intensity is as follows:

$$\mathop {{E_j}}\limits^{ \to } =\frac{{\mathop {{f_j}}\nolimits^{ \to } }}{q}=\frac{{\sum\nolimits_{{i=1}}^{n} {\mathop {{f_i}}\limits^{ \to } } }}{q}\,=\,\sum\limits_{{i=1}}^{n} {\frac{{\mathop {{f_i}}\limits^{ \to } }}{q}} .$$
(7)

Substituting Eq. (1) into Eq. (7) yields

$$\mathop {{E_j}}\limits^{ \to } =\sum\limits_{{i=1}}^{n} {\frac{1}{{4\pi {\varepsilon _0}}}} \frac{{{q_i}}}{{r_{i}^{2}}}\mathop {{r_i}}\limits^{ \to } ,$$
(8)

where \(q\) is electric quantity of probe charge j, \({q_i}\) is the electric quantity of the source charge i, \({r_i}\) is the distance between the source charge and the probe charge, and n is the number of source charges.

The direction of the Coulomb force and electric field intensity is not considered in PSOS. We only consider their magnitudes. Based on this, the equivalent electric field intensity at node s of the single-layer grid structure as shown in Fig. 5b can be expressed as follows:

$${E_s}\,=\,\sum\limits_{{t=1,s \ne t}}^{m} {{E_{{\text{st}}}}} ,$$
(9)

where m is the number of nodes around the node s, and \({E_{{\text{st}}}}\) is electric field intensity at node s that is produced by the surrounding node t. Adjusting the position of nodes continuously, once the equivalent electric field intensity satisfies the convergence tolerance, the iteration will be terminated and the nodes will be located at a similar distance to one another.

2.3.3 Updating of particle coordinates

In Coulomb’s Law, if two charges have the same sign, the electrostatic force between them is repulsive; if they have different signs, the force between them is attractive, with the force joining them along a straight line. In PSOS, we introduce the threshold of inter-particle distance R, a value that is specified by the user. When the distance between two charged particles is less than R, we define the two charges to be like-signed, and the Coulomb force F is repulsive. When the distance between the two particles is more than R, we define them to have opposite signs, so the Coulomb force F is now attractive. As shown in Fig. 6, particle i is the current active particle; its coordinates are taken as the center of a circular, and the threshold of the inter-particle distance R is used as the radius of the circular. When the surrounding particles fall within the circular, they will move towards away from particle i driven by the Coulomb repulsion. When the surrounding particles fall outside the circular, they will be attracted and move towards particle i under the influence of coulomb attraction. The force is still along a straight line joining the two particles.

Fig. 6
figure 6

Interaction of particles

Full size image

The updated particle coordinates are determined by a statistical sampling-based Monte Carlo (MC) method according to Zhang [21]. As shown in Fig. 7, A and B are the initial positions of the particles; D is the updated position of the particle; \(\eta\) is the moving coefficient, which is selected according to experience, the best value is between 0 and 0.5; L is the actual distance between the two particles; R is threshold of inter-particle distance. When the actual distance between the two particles is greater than R, the force between the particles is attractive, so B moves to A, where CB is the search interval, as shown in Fig. 7a. When the actual distance is less than R, the force is repulsive, so B moves away from A, where BC is search interval, as shown in Fig. 7b.

Fig. 7
figure 7

Schematic diagram of particle coordinate updating

Full size image

2.4 Termination criterion

The terminating criterion is one of the following:

  1. 1.

    Maximum number of iterations The process is terminated when the iteration reaches the maximum number of iterations, which is set by the user.

  2. 2.

    Maximum number of stay steps If the equivalent electric field intensity still has no improvement after the maximum number of stay steps, the process is terminated.

  3. 3.

    Minimum convergence error If the equivalent electric field intensity is less than a pre-fixed anticipated threshold, the process is terminated.

2.5 Implementation of PSOS

The procedure of PSOS is summarized in Fig. 8.

Fig. 8
figure 8

Flowchart of PSOS

Full size image

3 Representation of NURBS surface

The non-uniform rational B-spline (NURBS) was originally proposed by Versprille [22] in his doctoral thesis. Subsequently, Piegl [23,24,25] systematically explored the construction and shape adjustment of non-uniform rational B-spline curves and surfaces. Due to their flexibility and accuracy, NURBS models can be used in any process, from illustration, scientific visualization, and animation to manufacturing. Modern CAD systems, such as 3DSMAX, MAYA, CATIA, and UG, can perfectly support the NURBS models. The free-form surfaces described in this paper all refer to NURBS surfaces.

A surface of degree k in the u direction and degree l in the v direction can be defined by the following:

$$\begin{aligned}P(u,v)&=\frac{{\sum\nolimits_{{i=0}}^{n} {\sum\nolimits_{{j=0}}^{m} {{B_{i,k}}(u){B_{j,l}}(v){w_{i,j}}{P_{i,j}}} } }}{{\sum\nolimits_{{i=0}}^{n} {\sum\nolimits_{{j=0}}^{m} {{B_{i,k}}(u){B_{j,l}}(v){w_{i,j}}} } }}\\&\quad {u_{\text{min} }} \leq u \leq {u_{\text{max} }},{v_{\text{min} }} \leq v \leq {v_{\text{max} }},\end{aligned}$$
(10)

where \({P_{i,j}}\) are the control points, which are arranged in a rectangle to form a control grid. \({w_{i,j}}\) are the weights corresponding to \({P_{i,j}}\) and specify that the weights at the apex of the four corners are positive. \({B_{i,k}}(u)\) and \({B_{j,l}}(v)\) are the non-rational S-spline basis functions defined on the knot vectors:

$$\left\{ \begin{gathered} U=[{u_{\text{min} }}, \ldots \ldots {u_{\text{min} }},{u_{k+1}}, \ldots \ldots ,{u_{r - k - 1}},{u_{\text{max} }}, \ldots \ldots {u_{\text{max} }}] \hfill \\ V=[{v_{\text{min} }}, \ldots \ldots {v_{\text{min} }},{v_{l+1}}, \ldots \ldots ,{v_{s - l - 1}},{v_{\text{max} }}, \ldots \ldots {v_{\text{max} }}] \hfill \\ \end{gathered} \right.,$$
(11)

where r = n + k + 1 and s = m + l + 1.

4 Triangular grid generation on a free-form surface based on PSOS

According to the NURBS surface definition, there is a rectangular parameter domain for every surface whose parameter value is u, v. There is a bidirectional nonlinear mapping relationship between the three-dimensional space domain and the two-dimensional parameter domain. Each point S (u, v) in the parameter domain corresponds to a point P (x, y, z) in the three-dimensional European space. The mapping relationship between a spatial surface and its parameter domain is shown in Fig. 9.

Fig. 9
figure 9

Mapping from parametric domain to space surface

Full size image

The PSOS presented in this paper will be used to provide a building meshing plan for the arbitrary NURBS surface shown in Fig. 10. The initial particles are generated on the surface randomly, as shown in Fig. 11. The points on the boundary are fixed, while the middle points are considered to be the moving particles. This is what must be done to change the positions of the middle points to achieve the formation of a discrete grid, which meets the architectural requirements.

Fig. 10
figure 10

An arbitrary surface

Full size image
Fig. 11
figure 11

The initial particles

Full size image

4.1 Layout of initial points

The first step to generate a grid on a free-form surface using PSOS is to determine the position of the initial point. In general, there are two ways that can be done: plane projection and random generation. To illustrate the efficiency and robustness of the proposed method, we use a random generation method to obtain the layout of initial point. The number of initial points can be determined by the following formula according to the threshold of inter-particle distance R and the surface area:

$$N=\frac{2}{{\sqrt 3 }}\lambda \frac{{{A_{\text{s}}}}}{{{R^2}}},$$
(12)

where N is the number of initial points on surface, \(\lambda\) is a factor whose value is approximately 1 (the specific value must be determined by a trial calculation), and \({A_{\text{s}}}\) is the spatial surface area.

4.2 Grid-quality evaluation

It is well-known that the grid-quality evaluation indicators in the FEM include the slenderness ratio, taper ratio, internal angle, warpage amount, tensile value, edge node position deviation, etc. However, it is clear that some of these is no longer applicable in the field of spatial structure. In practice, it is sometimes more important for the spatial structure to generate a grid that has regular shapes and uniform rod lengths.

Therefore, a grid uniformity quality index is used to evaluate the shape and rod-length quality in this paper according to [26, 27]. While the shape quality responds to the regularity of the grid, the standard deviation of the rod length is used to evaluate the uniformity of the grids.

The standard deviation of the rod length can be defined as follows:

$${\alpha _l}=\sqrt {\frac{{\sum {{{({l_i} - \bar {l})}^2}} }}{M}} ,$$
(13)

where \({l_i}\) is the length of rod, \(\bar {l}\) is the mean value of the rod length, and M is the number of rods. Because of the existence of dimensions, for structures with different grid sizes, the uniformities of the rods represented by the same standard deviation are also very different. Therefore, some measurements need to be taken to convert it into a dimensionless unit. In this paper, the ratio of the standard deviation \({\alpha _l}\) to the mean value of rod length \(\bar {l}\) was taken as the new uniformity of the grids, which we called the equivalent standard deviation of the rod length, which is shown as follows:

$${\alpha ^{\prime} }= \frac{{{\alpha _l}}}{{\bar {l}}}.$$
(14)

The shape quality evaluation index of the triangular grid can then be expressed as follows:

$$Q=4\sqrt 3 \frac{A}{{l_{1}^{2}+l_{2}^{2}+l_{3}^{2}}},$$
(15)

where A is the area of triangles, and \({l_1},{l_2},{l_3}\) are their lengths. The value of Q is between 0 and 1. A higher value of Q means a better shape quality of the grid. When the value of Q is 1, the triangle is an equilateral triangle whose shape quality is considered to be the best. When the value of Q is 0, it indicates that the triangle has degenerated into a straight line, and the shape quality is the worst.

According to the different motion space of particles, the PSOS method proposed in this paper was implemented with two methods: an indirect method and a direct method. The particle motion space of the indirect method is the parameter domain; the grid layout on the parameter domain is first obtained, and then, it is mapped back to the space surface. The particle motion space of the direct method is the physical domain; with the help of surface attraction to particles, a grid is generated directly on the physical domain and no mapping process is needed.

4.3 Indirect generation method based on parameter domain mapping

In this section, the indirect generation method of PSOS, which is based on parameter domain mapping, is used to divide the surface and parameter domain was chosen as the motion space of the particles. First, a certain number of grid points are randomly decorated on the spatial surface. Second, the space grid points are projected to the parameter domain plane. The initial grid layout on parameter domain is determined by the Delaunay method, as shown in Fig. 12a. Finally, the grid layout on the physical domain is obtained by re-mapping the grid on the parameter domain back to spatial surface, as shown in Fig. 13a. It is obvious that the quality of the initial grid generated by the Delaunay method is very poor, since the position of the points is randomly distributed. The size of the grid changes dramatically, and there is no obvious fluent lines.

Fig. 12
figure 12

Grid layout on parameter domain

Full size image
Fig. 13
figure 13

Grid layout on physical domain

Full size image

Then, the PSOS is used to find the appropriate position of the particles on the parameter field. After multiple iterations, a more uniform particle distribution on the parameter domain is obtained, and obvious smooth lines appeared, as shown in Fig. 12b. The equivalent standard deviation of the rod-length index and the shape quality index of the grid are presented in Table 1. It is shown in the table that the equivalent standard deviation of the rod length and the standard deviation of the grid shape quality index of the grid obtained by PSOS are rapidly reduced when compared to the initial state, specifically to 0.09 and 0.03, respectively. The average shape quality index of the grid is as high as 0.98, which indicates that the triangles on the parameter domain are closer to equilateral triangles, and the grid quality is good. It also shows that the PSOS method is, indeed, feasible and effective.

Table 1 Grid-quality evaluation
Full size table

The result of mapping the parameter domain grid back to the spatial surface is shown in Fig. 13b. It shows that the uniformity of the grid on the physical domain is deteriorated compared to the grid on the parameter domain, and the mean value of the shape quality is reduced to 0.91, while the equivalent standard deviation of the rod length is increased to 0.28. That is, because the mapping distortion occurs when the grid on the parameter domain is mapped back to the spatial surface, which is also the reason why the grid quality on the spatial surface dropped rapidly and a better grid cannot be obtained. To solve this problem, a virtual curvature of the surface is introduced to control the Coulomb force between the particles on the parameter domain and reduce the mapping distortion.

The geometric meaning of virtual curvature is the ratio of the distance a particle moves in the parameter domain to its corresponding particle moving distance on the physical domain. A smaller value indicates that more particles are affected by the curvature in the physical domain. In other words, the minor movement of the particles in the parameter domain can result in a significant change in the physical domain. Similarly, the larger the value is, the less the particle in the physical domain is affected by the curvature.

According to Zheleznyakova [19], the virtual curvature in the \(u,v\) direction of a particle on the surface can be expressed as follows:

$$\begin{gathered} K_{E}^{u}=\frac{{2{\text{d}}u}}{{\left| {S({u_{\text{p}}}+{\text{d}}u,v) - S({u_{\text{p}}} - {\text{d}}u,v)} \right|}} \hfill \\ K_{{\text{p}}}^{v}=\frac{{2dv}}{{\left| {S(u,{v_{\text{p}}}+{\text{d}}v) - S(u,{v_{\text{p}}} - {\text{d}}v)} \right|}}, \hfill \\ \end{gathered}$$
(16)

where \({\text{d}}u,{\text{d}}v\) are the small distance increments in parameters u and v, \(({u_{\text{p}}}+{\text{d}}u,v)\), \(({u_{\text{p}}} - {\text{d}}u,v)\), \((u,{v_{\text{p}}}+{\text{d}}v)\), and \((u,{v_{\text{p}}} - {\text{d}}v)\) are position vectors of the points on the parameter domain; \(S({u_{\text{p}}}+{\text{d}}u,v)\), \(S({u_{\text{p}}} - {\text{d}}u,v)\), \(S(u,{v_{\text{p}}}+{\text{d}}v)\), and \(S(u,{v_{\text{p}}} - {\text{d}}v)\)are the position vectors of the points on the NURBS surface. \(K_{{\text{p}}}^{u},K_{{\text{p}}}^{v}\) denote the curvature in the \(u,v\) direction of the surface, respectively. After considering the virtual curvature of the surface, the threshold of the inter-particle distance R is redetermined by\({R^{\text{s}}}=R\sqrt {K_{{\text{p}}}^{u}K_{{\text{p}}}^{v}}\). In this way, the distance between the particles on the parameter domain is adjusted, as is the size of the grid.

Taking the virtual curvature into consideration, the particle motion space is still the parameter domain. The result of the grid layout on the parameter domain is shown in Fig. 12c. It can be found that the grid on the parameter domain has become sparse and orderly, and it is no longer uniform. The mean value of the shape quality index drops to 0.92. However, once it is mapped back to the space surface, as shown in Fig. 13c, the grid uniformity is improved compared to that without considering the virtual curvature. The standard deviation of the rod length and the standard deviation of shape quality index rapidly decrease to 0.1 and 0.06, respectively, and the mean value of the shape quality is increased to 0.97, which means the triangle is closer to an equilateral triangle. This shows that, due to the existence of virtual curvature, the distortion generated during mapping is overcome to some extent, the uniformity of the grid after mapping from the parameter domain back to the physical domain is improved, and finally, a high-quality grid in the physical domain is obtained.

4.4 Direct generation method of applying surface attraction

In the previous section, the motion space of particles was the parameter domain; that is, an indirect method to find the particles’ reasonable positions in the parameter domain and then map it back to the physical domain to complete the grid generation of the spatial surface. In this section, we transfer the particle motion space from the parameter domain to the spatial physics domain and introduce the forced attraction of the surface to the particles to find the reasonable position of the particles on the surface, and then, the surface Delaunay method is used to generate the triangular grid. The surface Delaunay method is achieved by finding the dual transformation of the surface Voronoi diagram, which is formed by the intersection between the surface and the three-dimensional Voronoi diagram of the particles. It is a direct grid generation method of PSOS used to generate a grid on the spatial surface by transferring the motion space of the particles to the physical domain.

The attraction of the spatial surface to the particles can be derived from the following:

$${F_i}={k_s}{d_{s,i}},$$
(17)

where \({d_{s,i}}\) is the shortest distance between the surface and the new position of particle i after deviating from the surface, and \({k_{\text{s}}}\) is the surface attraction constant. The effect of attraction is to pull the particles that have deviated from the surface back to ensure the particles always move onto the surface.

Figure 14 shows the grid layout obtained by the direct method of PSOS, which suggest that the grids generated by the direct method are of a better quality, regular shape and have fluent lines. As shown in Table 1, the equivalent standard deviation of the rod length and the shape quality index of the grids on the physical domain are reduced by up to 80% and 93%, respectively, compared to the initial state, while they are reduced by up to 40% and 66%, respectively, compared to the indirect method, which considered the virtual curvature of the surface.

Fig. 14
figure 14

Grid generation considered the effect of attraction

Full size image

In addition, the average value of the grid shape quality index of the physical domain is up to 0.99. The result shows that, once the surface attraction was introduced, a better grid with higher shape quality and fluent lines can be generated, and the distortion caused by the mapping can be avoided significantly.

5 Grid generation study for special surfaces

In this section, we will discuss the adaptability of PSOS to the grid generation on several special surfaces. In general, for a simple surface or a surface with a relatively gentle curvature change, a grid with good shape quality can be obtained using the mapping method such as the indirect method of PSOS. Unfortunately, due to the existence of mapping distortion, the mapping method is no longer suitable for some special surfaces or a surface with a sharp curvature, as shown in Fig. 15, 16, and 17.

Fig. 15
figure 15

Mobius band

Full size image
Fig. 16
figure 16

The EXPO sun valleys in Shanghai

Full size image
Fig. 17
figure 17

Admirant entrance building

Full size image

A Mobius Band is shown in Fig. 15, which was discovered independently by the German mathematicians Mobius and Listing in 1858. It is a surface with only one side and only one boundary. What makes it interesting is that an ant can traverse the entire surface and back to its starting point without having to cross its edge.

Figure 16 shows the EXPO Sun Valleys in Shanghai. The first impression for most people is that it looks like a funnel, and the dimensions of its upper and lower ends vary dramatically, which causes the surface to change drastically. Obviously, it is difficult to obtain a uniform triangular grid on such a curved surface by the direct mapping method.

The surface shown in Fig. 17 is a drawing of the Admirant entrance building in Holland designed by Fuksas. It is similar to a precious jewel that attracts the public’s attention and leads pedestrians into the heart of the building.

The PSOS proposed in this paper is used to generate triangular grid on the above surfaces and considered the effects of the virtual curvature and surface attraction on the grid quality separately. The grid-quality evaluation indexes are shown in Table 2. In the initial state, since the particles were randomly generated, the equivalent standard deviation of the rod length and the standard deviation of the shape quality index were relatively large. On the other hand, the mean value of shape quality index was very small, the maximum of which was not more than 0.9.

Table 2 Grid-quality evaluation of the above surfaces
Full size table

As shown in Table 2, once the virtual curvature was considered, the average value of the shape quality was improved, while the equivalent standard deviation of the rod length and the standard deviation of shape quality index decreased by more than 50% compared to the initial state. However, a grid with a better shape quality and fluent lines was obtained after applying the surface attraction. It can be certified from comparing the data in Table 2.

When the surface attraction was applied, the equivalent standard deviation of the rod length and the standard deviation of the shape quality index were reduced significantly, at more than 70% lower than the initial state and more than 30% lower than the indirect method which considering the virtual curvature. Furthermore, all of the average values of shape quality indexes were above 0.98, which indicates that the grid obtained by the direct method of PSOS is better than the indirect method. The final grids generated by the direct method are shown in Fig. 15 - Fig. 17. Due to the uniform rod length, regular shape, and fluent lines, we must conclude that the grid shown above not only satisfies the aesthetic requirements but also embodies the connotation of the architecture.

In the above examples, the whole optimization process only took a few minutes on a Personal Computer with Intel i7 3.6 GHz processor and 16 GB RAM. The number of particles is between 227 and 465, and the time spent is between 451 s and 605 s.

6 Conclusion

This paper proposes a triangle grid automatic generation technique, which we referred to as the particle self-organizing system (PSOS) based on Coulomb’s Law. Using it, we are able to create lattice structures with the unique topology, where all of the nodes are located at a similar distance to one another. Therefore, the grid generated by connecting the nodes is also uniform in size and regular in shape.

To reduce the distortion caused by mapping, the effects of the virtual curvature and surface attraction on particle motion are considered, and PSOS is divided into an indirect method and a direct method. The particle motion space of the indirect method is the parameter domain. The grid on the free-form surface is obtained by mapping the grid, which is generated through PSOS on parameter domain back to spatial physical domain. Thanks to the help of virtual curvature, the indirect method can reduce the mapping error to some extent and generate a good quality grid.

On the other hand, the particle motion space of the direct method is transferred to physical domain. The results show that, under the effect of surface attraction, the mapping errors are completely avoided, and a grid with a better quality is obtained. The mean values of the shape quality of the grid generated by the direct method of PSOS are more than 0.98. Moreover, the equivalent standard deviation of the rod length and the standard deviation of the shape quality index are more than 70% lower than initial state and more than 30% lower than the indirect method.