GRAND3 — Ground structure based topology optimization for arbitrary 3D domains using MATLAB

Abstract

Since its introduction, the ground structure method has been used in the derivation of closed–form analytical solutions for optimal structures, as well as providing information on the optimal load–paths. Despite its long history, the method has seen little use in three–dimensional problems or in problems with non–orthogonal domains, mainly due to computational implementation difficulties. This work presents a methodology for ground structure based topology optimization in arbitrary three–dimensional (3D) domains. The proposed approach is able to address concave domains and with the possibility of holes. In addition, an easy–to–use implementation of the proposed algorithm for the optimization of least–weight trusses is described in detail. The method is verified against three–dimensional closed–form solutions available in the literature. By means of examples, various features of the 3D ground structure approach are assessed, including the ability of the method to provide solutions with different levels of detail. The source code for a MATLAB implementation of the method, named GRAND3 — GRound structure ANalysis and Design in 3D, is available in the (electronic) Supplementary Material accompanying this publication.

1 Introduction

The ground structure method (Dorn et al. 1964), is a discrete element topology optimization approach that can address relatively large problems on standard computers. Using a reduced (finite) number of discrete elements, the method can provide an approximation to the optimal Michell structure (Michell 1904; Hemp 1973), composed of an infinite number of members. The limited computational capability and lack of flexibility in current methods are to blame for the decreased interest in three–dimensional topology optimization. The problem of finding the least–weight (least volume) truss for a single load case, under elastic and linear conditions, subjected to stress constraints can be posed as a linear programming problem (Ohsaki 2010), and is the base of the method’s efficiency. The ground structure method tackles the topology optimization problem (sizing and geometry), as a sizing–only optimization problem for a highly interconnected and redundant truss, i.e. the ground structure.

The authors’ previous work (Zegard and Paulino 2014) in 2D, generates the ground structure using linear algebra operations. Members generated in concave regions or holes are detected and removed using collision tests, in an approach derived from the video–game and ray–tracing literature. In the present work, it will be shown that this approach can successfully scale to three–dimensional space, provided that the 3D analogues to the two–dimensional collision tests are developed. The algorithms are described in detail, and a MATLAB implementation of the method is provided, which is also used to provide examples and show the capabilities and limitations of the proposed method. Before addressing problems for which the solution is not known, the proposed method is verified against known solutions available in the literature.

Three–dimensional ground structure analysis has been successfully performed in the past (Gerdes 1994; Smith 1998; Gilbert et al. 2005; Tyas et al. 2006). Unfortunately, most of these works are restricted to structured and orthogonal discretizations. The interest in unstructured non–orthogonal domains is reasonable considering that applied engineering problems are often not boxes and may include geometrical constraints such as holes. The method does require the domain to be discretized, and as a consequence, the boundary is represented in a piecewise linear fashion.

Michell (1904) derived closed–form optimal structures for a variety of two–dimensional problems, with a single three–dimensional problem: The optimal structure to transfer a moment pair distributed over small circumferences with no constraint on the domain size (Fig. 1a). Michell’s derivations did not include details, and the solution was later re–derived by Hemp (1973) and Lewiński (2004). The optimal solution resembles a hollow ball with curved mutually–orthogonal members on its surface as shown in Fig. 1b. The proposed method’s capability to address unstructured non–orthogonal domains offers a reasonable numerical approximation to the analytical closed–form solution. The result obtained with the proposed algorithm is shown in Fig. 1c for comparison.

Fig. 1

Optimal structure to transfer a moment pair. a Domain and loads: The moments are distributed on equal rings at a latitude ϕ _F . b Analytical closed–form solution adapted from Michell (1904). c Numerical approximation obtained with GRAND3

The limitations and assumptions of the present implementation are:

• single static load case scenario;

• constant forces (design independent);

• small deformations.

It can, however, address different limits in tension σ _T and compression σ _C (Sokół 2011).

Throughout this manuscript, the terms truss member and bar are used interchangeably. The manuscript is organized as follows: Section 2 briefly reviews the formulation used and its extension to three–dimensions. Section 3 provides details on the implementation of the method. The method and its implementation are verified against closed–form solutions in Section 4. Selected examples and their convergence are analyzed in Section 5. Conclusions and findings are summarized in Section 6. Appendix A has the nomenclature and symbols used in the manuscript. Finally, the derivations for the three–dimensional collision tests are given in Appendix B.

2 Formulations

This section briefly reviews the ground structure formulation based on plastic analysis. The reader can refer to Hemp (1973), Ohsaki (2010), Christensen and Klarbring (2009), and Gilbert and Tyas (2003) for additional details on the plastic and elastic versions of the method.

Consider a stable truss (no mechanisms), with N _{d o f} nodal forces f (excluding the components with supports), and assume that the supports are sufficient to prevent rigid body motions. The minimum volume truss that satisfies the force equilibrium equations (plastic analysis) is (Hemp 1973; Ohsaki 2010):

$$ \begin{array}{rl} \min\limits_{\mathbf{a}} & V=\mathbf{l}^{T}\mathbf{a}\\ \mathrm{s.t.} & \mathbf{B}^{T}\mathbf{n}=\mathbf{f}\\ {~} & -\sigma_{C} a_{i} \leq n_{i} \leq \sigma_{T} a_{i} \quad i=1,2 {\dots} N_{b}~, \end{array} $$

(1)

with V the truss’ volume, a _i , l _i and σ _i the cross–sectional area, length and stress of the ith truss member (for all N _b members in the truss). The matrix B ^T is the nodal equilibrium matrix of size N _{d o f} ×N _b , built from the directional cosines of the members, and n is a vector with the internal (axial) force for all members in the ground structure. Theoretically, a member is absent (removed) from the truss if a _i =0. The redundancy of the ground structure is N _b −N _{d o f} and should be greater than zero to provide multiple layout options. This formulation, based on plastic analysis, only enforces force equilibrium, i.e. the compatibility or stress-strain relations are not included (Kirsch 1993).

The stress constraint, either in tension or compression, must be active for all members at the optimum. This can be proven intuitively: if the ith member has n _i <σ _T a _i and n _i >−σ _C a _i , then a _i can be reduced (reducing the total volume) without violating the constraints. Incorporating slack variables s ⁺ and s ⁻ in the stress constraints (Hemp 1973; Achtziger 2007), the inequalities can be converted into equalities, and the optimization problem in (1) becomes a linear programming problem as:

$$ \begin{array}{rl} \min\limits_{\mathbf{s}^{+},\mathbf{s}^{-}} & V=\mathbf{l}^{T}\left( \frac{\mathbf{s}^{+}}{\sigma_{T}} + \frac{\mathbf{s}^{-}}{\sigma_{C}} \right) \\[+7pt] \mathrm{s.t.} & \mathbf{B}^{T}\left( \mathbf{s}^{+} - \mathbf{s}^{-} \right)=\mathbf{f} \\ {~} & s_{i}^{+},s_{i}^{-} \geq 0 \:, \end{array} $$

(2)

with $a_{i} = s_{i}^{+} / \sigma _{T} + s_{i}^{-} / \sigma _{C}$ and $n_{i} = s_{i}^{+} - s_{i}^{-}$. Note that for any active member, only one of $s_{i}^{+}$ and $s_{i}^{-}$ is non–zero. The member is in tension if $s_{i}^{+} > 0$, and in compression if $s_{i}^{-} > 0$. If the truss structure is stable and has no repeated or overlapping members, then the rank of matrix B ^T is N _{d o f} (i.e. the solution lies on a corner of the feasible domain). The solution of the linear program in (2) yields at most N _{d o f} non–zero basic variables, with the remainder non–basic variables absent from the optimal structure (i.e. a _i =0). Therefore, the optimal truss is statically determinate and the solution is also globally optimal (Sved 1954; Kicher 1966): The optimal solution will automatically satisfy the kinematic compatibility and stress–strain relations (Dorn et al. 1964; Hemp 1973).

Defining the stress limits ratio as κ=σ _T /σ _C and using matrix notation, (2) can be rewritten as:

$$\begin{array}{@{}rcl@{}} \underset{\mathbf{s}^{+},\mathbf{s}^{-}}{\min} && V^{\star} = \frac{V}{\sigma_{T}} = \underset{1 \times 2N_{b}}{\left\{\mathbf{l}^{T} \kappa \, \mathbf{l}^{T}\right\}} {\begin{array}{c}\left\{\begin{array}{c} \mathbf{s^{+}} \\ \mathbf{s^{-}} \end{array} \right\}\\2N_{b} \times 1 \end{array}}\\ \mathrm{s.t.} && {\begin{array}{c} \left[\mathbf{B}^{T} -\mathbf{B}^{T}\right]\\ N_{dof} \times 2N_{b} \end{array} } {\begin{array}{c} \left\{ \begin{array}{c} \mathbf{s^{+}} \\ \mathbf{s^{-}} \end{array} \right\}\\2N_{b} \times 1 \end{array} }= \underset{N_{dof} \times 1}{\mathbf{f}}\\ {~} && s_{i}^{+},s_{i}^{-} \geq 0 \end{array} $$

(3)

The number of degrees–of–freedom (DOFs) is N _{d o f} =3N _n −N _{s u p} , with N _n the number of nodes in the ground structure and N _{s u p} the number of fixed (supported) degrees of freedom. The optimal volume V ^⋆ is calculated for σ _T =1, and should be scaled by 1/σ _T for values other than unity. Equation (3) highlights the sizes of the variables involved. By introducing slack variables, the number of design variables in (3) is doubled compared to the number of design variables in (1). However, while (1) is a nonlinear program, (3) is a linear program and can be solved more efficiently using the interior-point algorithm (Karmarkar 1984; Wright 2004). Problems with solutions that lie on a facet (or edge) of the feasible domain are called degenerate, and tend to be computationally more difficult to solve.

3 Implementation

The implementation is an extension of the two–dimensional GRAND (Zegard and Paulino 2014). The concepts and algorithms from the previous two–dimensional implementation are directly extended with a few exceptions that are detailed here.

3.1 Domain definition — Base mesh

The ground structure generation algorithm requires a base mesh from where to generate the nodal connectivity matrix. No edge, facet or volume information is needed from this base mesh—it is strictly used to obtain nodal connectivity information. The ground structure generation process begins by connecting all nodes within an element: this is referred as level 1 connectivity. Take the 2 element mesh in Fig. 2a for example (a hexahedron and a wedge element); the ground structure with a level 1 connectivity will generate bars between all the nodes belonging to an element, as shown in Fig. 2b. These nodes are direct neighbors of each other based on the element connectivity provided by the mesh. At level 2, the proposed method will generate bars up to the neighbors or my neighbors, therefore including level 1 bars. The (new) bars at level 2, will traverse 2 elements in the base mesh as shown in Fig. 2c. The generated ground structure will become more redundant and dense with each connectivity level. The method can use any base mesh provided that it is built from convex polytopes; this because at level 1, all nodes within an element are connected regardless. While the elements in the base mesh need to be convex, the mesh itself does not. This and other details on the ground structure generation are addressed in Section 3.2.

Fig. 2

Ground structure generation algorithm based on element connectivities. Base mesh composed of a single hexahedron and a wedge. b Ground structure for level 1 connectivity: all nodes within an element are interconnected with bars. c Ground structure for level 2 connectivity: the new bars added at level 2 are plotted with solid lines

The fact that no edge or facet information is provided can prove to be challenging for plotting routines if complicated convex polytopes are given. In addition, the maturity of 3D polytope meshing algorithms (Barber et al. 1996; Herceg et al. 2013; Rycroft 2014) is lagging behind that of more traditional meshing algorithms based on standard elements (hedrahedra, tetrahedra, wedges, etc). Therefore, while the algorithm for ground structure generation and analysis can address any element type in the base mesh, for practical purposes, the current implementation is limited to 7 simple elements: 4 volumetric and 3 surface elements (the segment, although not flat, is grouped with surface elements). The 7 elements supported in the current implementation are illustrated in Fig. 3.

Fig. 3

Elements supported by GRAND3 and their corresponding node numbering scheme. a Volumetric elements: Hexahedron (8-nodes), Prism (6-nodes), Pyramid (5-nodes) and Tetrahedron (4-nodes). b Surface elements: Quadrangle (4-nodes), Triangle (3-nodes) and Segment (2-nodes)

These elements have a unique topology (facets and edges), provided that they are numbered properly. The surface elements are not two–dimensional, but three–dimensional entities that can be used to define shells, domes and membranes for example. The segment element is special: it can be used to fine–tune the nodal connectivity matrix by allowing two non–neighboring nodes to share level 1 connectivity.

The input specification for the base mesh, supports and loads for the provided implementation, is detailed in Table 1. The ELEM variable is a structure (or struct) with fields V and S for volumetric and surface elements respectively. The analysis can comprise volumetric, surface or a combination of elements in the base mesh. In other words, at least one field in ELEM must be defined (V or S). The total number of volumetric and surface elements are N _{v e} and N _{s e} respectively. Therefore, the total number of elements in the base mesh is N _e =N _{v e} +N _{s e} .

Table 1 Domain definition (base mesh) input requirements for GRAND; the provided implementation of the method

3.2 Ground structure generation

The ground structure generation follows the procedure outlined in the two–dimensional implementation (Zegard and Paulino 2014). The connectivity level parameter (L v l) indirectly controls the level of redundancy, or inter–connectedness, of the initial ground structure (refer to Fig. 2). Two nodes are considered neighbors and share level 1 connectivity if they belong to the same element in the base mesh. From this idea of neighbors, the connectivity level can be explained as follows:

• Level 1 connectivity will generate members between all neighboring nodes.

• Level 2 connectivity will generate members up to the neighbors of the neighbors.

• Level 3 connectivity will generate members up to the neighbors of the neighbors of the neighbors.

This process scales rapidly and only decelerates when the member generation is reaching full connectivity throughout the domain. The nodal connectivity matrix for level 1, A ₁, is built from the base mesh and is defined as follows:

$$ \left[\mathbf{A}_{1}\right]_{p,q} = \left\{ \begin{array}{lll} 1 \text{ or} & \verb+true+ & \text{ if nodes }p,q \text{ share an element }\\ 0 \text{ or } & \verb+false+ & \text{ otherwise or if }p=q \end{array} \right.\!\! \:, $$

(4)

resulting in a symmetric A ₁, i.e. bi–directional.

The second level connectivity can be obtained as $\mathbf {A}_{2}=\mathbf {A}_{1}\mathbf {A}_{1}=\left [ {\mathbf {A}_{1}^{2}} \right ]$. However, some entries may well be >1 and have values other than zero in the diagonal. Therefore, the nodal connectivity matrix for levels n>1 is then:

$$ \left[\mathbf{A}_{n}\right]_{p,q} = \left\{ \begin{array}{lll} 0 \text{ or} & \verb+false+ & \text{ if } \left[\mathbf{A}_{1}^{n}\right]_{p,q}=0\text{ or if }p=q\\ 1 \text{ or} & \verb+false+ & \text{ if }\left[\mathbf{A}_{1}^{n}\right]_{p,q}>0\text{ and }p \neq q \end{array} \right. $$

(5)

The new bars for level n can be obtained as:

$$ \mathbf{G}_{n}=\mathbf{A}_{n}-\mathbf{A}_{n-1} \:, $$

(6)

where G _n has non–zero entries for the bars generated at level n (note that G ₁=A ₁). The new bars obtained from G _n are considered candidate bars: they still need to pass the collinearity and restriction zone checks (Sections 3.3 and 3.4 respectively) to be included in the final ground structure.

The number of bars, and therefore the number of variables in the optimization problem, grow rapidly with an increase of the connectivity level. In general, it is not recommended to use high values for the connectivity level; i.e. connect nodes that are far away from each other. The analytical closed–form solutions are typically composed of curved members (Michell 1904; Lewiński 2004). The method can better approximate these curved–member solutions with many short bars in a piecewise fashion, as opposed to the long members that result from a high connectivity level.

3.3 Collinearity check

The collinearity (or overlapping) member check assumes the following:

• 1. New bars added at level n are deleted if found collinear with bars from previous levels.

• 2. New bars added at level n are assumed not to be collinear between them. They are only checked for collinearity against previously generated bars (not to each other).

In general, new bars are longer than those generated at lower connectivity levels, thus justifying the decision to eliminate the newly generated bar as opposed to the previously accepted one. The second assumption may be violated if the base mesh has elements that are not strictly convex, although most meshing algorithms will generate meshes with strictly convex elements. More uncommonly, as the ground structure for higher levels is generated, the algorithm expansion may reach two collinear nodes at a single step: this unlikely situation may occur in domains that curl or spiral around themselves and is generally not a concern within the scope of this work.

The length of a member spanning between nodes p and q with coordinates $\left \{x_p,y_p,z_p\right \}$ and $\left \{x_q,y_q,z_q\right \}$ is defined as:

$$ L_{p,q} = \sqrt{ (x_q-x_p)^2 + (y_q-y_p)^2 + (z_q-z_p)^2 } $$

(7)

The directional cosines vector for the bar between nodes p and q is $\boldsymbol {\hat {\mathrm {d}}}_{p,q}$:

$$ \boldsymbol{\hat{\mathrm{d}}}_{p,q} = \frac{\left\{ x_q-x_p , y_q-y_p , z_q-z_p \right\}}{L_{p,q}} $$

(8)

Note that the bar length and directional cosines are also used in the formulation of the ground structure optimization problem (3).

Once G _n is obtained, the new (candidate) bars must be checked not to be collinear with members already in the ground structure. A candidate bar $\overline {pq}$ is rejected due to collinearity if it has a small–enough angle with a previously accepted bar in the ground structure. The angle between bars is checked using the dot product of the directional cosines¹:

$$ \left\{\begin{array}{ll} \text{accept bar }\overline{pq}\text{ if} & \quad\hat{\mathbf{d}}_{p,q} \cdot \hat{\mathbf{d}}_{p,i} < ColTol \quad \forall \, i \\ \text{reject bar }\overline{pq} & \quad\text{otherwise} \end{array} \right. $$

(9)

The user–defined $ColTol \lesssim 1$ controls the admissible collinearity between members: the minimum angle between generated bars is $\alpha \geq \text {acos}\left (ColTol\right )$. Additional details (with examples) on the collinearity check can be found in Zegard and Paulino (2014).

3.4 Restriction zones

Analogous to the two–dimensional implementation of the method, the restriction zone idea is inspired by known collision detection algorithms used in video–games and in computational geometry (Ericson 2004).

The domain may have concave regions or holes that no bar should intersect. To prevent the ground structure generation algorithm from laying out members in these regions, the user defines restriction zones (i.e. hitboxes): geometric entities that no bar should intersect. The current implementation of GRAND3 provides the following restriction primitives:

• box

• cylinder

• disc

• quadrangle (flat)

• rod (finite cylinder)

• sphere

• triangle (flat)

• surface²

These primitives can be combined to create complicated regions or boundaries, and the user can easily implement new collision primitives in GRAND3. The derivation and details on these primitives are given in Appendix B.

Nodes in the base mesh must not intersect the restriction zones nor its boundary. If this happens, then all bars originating from such node will be flagged for removal during the restriction zone check. Thus, a small reduction in size of the restriction primitives is advised. This setback (or margin) is in the form of a small tolerance tol as shown in Fig. 4. The setback distance tol is defined by the user when defining the restriction zones, and should be relative to the scale of the problem.

Fig. 4

Restriction zone setback: this user–defined setback is a margin of comparatively small size tol in order to ensure that the domain’s nodes remain outside the restriction zones. a Example of the restriction zone for a domain with a circular concavity. The concavity radius is R, however the actual restriction zone applied is R−t o l. b Detail of the restriction zone setback: the nodes on the domain’s concave boundary (shown in the Figure) must remain clear of the restriction primitive

The ground structure generation, after the collinearity and restriction zone checks, returns a list of (accepted) bars (or members). This process operates over symmetric (or bi–directional) matrices. However, to prevent duplicate members, only bars $\overline {pq}$ with p<q are reported.

4 Verification

The following examples aim to verify GRAND3 by approximating optimal closed–form solutions. Members with cross–sectional area $a_{i} < \left (\mathit {Cutoff}\,\right ) \max \left (\mathbf {a}\right )$ are not plotted. Unless otherwise stated, the stress limit ratio is κ=1.0 with σ _T =1, the collinear tolerance is C o l T o l=0.999999 and the plotting cutoff is C u t o ff=0.005.

4.1 Torsion cylinder

A cylindrical domain of radius r and height H is subjected to an end moment distributed over the outer ring of the upper end cap (Fig. 5a). The domain is fully supported on the bottom end cap. This problem is of interest since the analytical volume for the theoretical optimal structure can be derived. A moment pair causes a pure–shear condition on the cylinder surface. Therefore, the principal stress lines are oriented at ±π/4. The members in the optimal solution must follow the lines of principal stresses (Michell 1904; Hencky 1923; Hemp 1973). A single fiber following a principal stress line has a length $l_{f} = \sqrt {2} H$. The force in the fiber due to the moment pair is $n_{f} = \sqrt {2} M / 4 \pi r^{2}$ for tension, and −n _f for compression. Finally, the volume of the optimal cylinder in torsion is:

$$\begin{array}{@{}rcl@{}} V_{opt} &= &\left[ \frac{ \left( n_{f}\right) \left( l_{f}\right) }{\sigma_{T}} - \frac{ \left( -n_{f}\right) \left( l_{f}\right) }{\sigma_{C}} \right] \left( 2\pi r\right) \\ {~} &=& \left( \frac{\sqrt{2}M}{4 \pi r^{2}}\right) \left( \sqrt{2}H\right) \left[ \frac{1}{\sigma_{T}} + \frac{1}{\sigma_{C}} \right] \left( 2\pi r\right)\\ {~} &= &\frac{MH}{r} \left[ \frac{1}{\sigma_{T}} + \frac{1}{\sigma_{C}} \right] \end{array} $$

(10)

Fig. 5

Torsion cylinder problem. a Domain definition, loading and supports. b Sample mesh for H=11, r=3 discretized with N _z =11, N _r =6 and N _𝜃 =18. c Axisymmetric plot of the sample mesh with H=11, r=3, N _z =11 and N _r =6. d Solution obtained for N _b =152,795, generated from a cylindrical domain with N _e =1,188, N _n =1,308 and L v l=3

Using cylindrical coordinates, the model is discretized in N _z ×N _r ×N _𝜃 elements corresponding to the z, r and 𝜃 coordinate axes respectively. The problem is analyzed for the specific case where H=11, r=3 and M=5. A sample mesh discretized with $\left \{ N_{z} , N_{r} , N_{\theta } \right \} = \left \{ 12 ,6 ,16 \right \}$ is shown in Fig. 5b. An axisymmetrical plot of this mesh is given in Fig. 5c. One of the solutions obtained with the proposed method is plotted in Fig. 5d as an example. The convergence of the ground structure method with refinement of the base mesh is given in Table 2 and Fig. 6. There is a convergence towards the optimal volume V _{o p t} =36.6667.

Fig. 6

Convergence for the cylinder problem with base mesh refinement

Table 2 Convergence for a cylinder under torsion with M=5, H=11 and r=3

4.2 Torsion cone

A capped cone domain of height H=10 with lower and upper radius r _L =7 and r _U =2 respectively, is subjected to an end moment M=3 distributed over the outer ring at the upper end cap (Fig. 7a). The analytical solution for this problem was derived by Lewiński (2004), by constraining the solution to exist in the cone’s surface:

$$ V_{opt} = M \frac{ \sqrt{H^{2} + \left( r_{L} - r_{U} \right)^{2} } }{r_{L} - r_{U}} \log \left( \frac{r_{L}}{r_{U}} \right) \left[ \frac{1}{\sigma_{T}} + \frac{1}{\sigma_{C}} \right] \:, $$

(11)

that for the specific geometry and loads being considered results in V _{o p t} =16.8076.

Fig. 7

Torsion cone problem. a Domain definition, loading and supports. b Sample mesh for H=10, r _L =7 and r _U =2 discretized with N _z =9, N _r =5, N _𝜃 =20 and λ=0.870058. c Axisymmetric plot of the sample mesh with H=10, r _L =7, r _U =2, N _z =9, N _r =5 and λ=0.870058. d Solution obtained for N _b =115,789, generated using a discretization in cylindrical coordinates with N _e =900, N _n =1,010 and L v l=3

Using cylindrical coordinates, the model is discretized in N _z ×N _r ×N _𝜃 elements corresponding to the z, r and 𝜃 coordinate axes respectively. An axisymmetrical plot of this mesh is given in Fig. 7c. In an effort to preserve the aspect ratio of the elements in the mesh, the spacing in the z direction is such that Δh _i+1/Δh _i =λ, with λ being constant. A sample mesh discretized with $\left \{ N_{z} , N_{r} , N_{\theta } \right \} = \left \{ 9 , 5 , 20 \right \}$ and λ=0.87006 is shown in Fig. 7b. One of the solutions obtained with the proposed method is plotted in Fig. 7d as an example. The convergence of the ground structure method with refinement of the base mesh is given in Table 3 and Fig. 8. The increasingly refined solutions converge smoothly toward the optimum, with a relatively small oscillation appearing when the number of bars is N _b >400,000. The reason behind this oscillation being that the node positions do not precisely match the locations dictated by the analytical closed–form solution; i.e. the height is not a multiple of π. The quality of the approximation will therefore depend on the aspect ratio of the elements in the base mesh, as defined by N _z , N _𝜃 and λ. However, the overall trend does converge to the analytical optimum as expected.

Fig. 8

Convergence for the cone problem with base mesh refinement

Table 3 Convergence for a capped cone under torsion with M=3, H=10, r _L =7 and r _U =2

4.3 Torsion ball (orthogonal domain)

The optimal structure for transmitting a torsion pair is a ball, provided that the domain is large enough to allow the full solution to develop (Fig. 1b). In contrast, the torsion cylinder (Section 4.1) addresses a similar problem but with a constrained domain. With no previous knowledge of the optimal solution, it is reasonable to use a regular and orthogonal base mesh. The moment (and support) is applied at the four nodes closest to the poles, as shown in Fig. 9a and b.

Fig. 9

Torsion ball problem modeled using an orthogonal domain. a Domain definition, loading and supports. b Sample mesh with N=5. c Optimal structure obtained with N=5, L v l=4 and N _b =15,980. d Optimal solution obtained with N=13, L v l=4 and N _b =475,996

The optimal volume for this problem was obtained by Michell (1904), but a detailed derivation was not given. The solution for the torsion ball was later re–derived (Hemp 1973; Lewiński 2004) and confirmed.³ The optimal volume of the torsion ball is:

$$ V_{opt} = 2M \log \left( \tan \left\{ \frac{\pi}{4} + \frac{\phi_{F}}{2} \right\} \right) \left[\frac{1}{\sigma_{T}}+\frac{1}{\sigma_{C}}\right] \:, $$

(12)

where ϕ _F is the latitude of the small rings where the moment is applied (Fig. 14a). It should be noted that the optimal volume is independent of the sphere’s radius R. Nonetheless, the domain must be large enough to allow the solution’s sphere with radius R to develop.

The problem domain considered has L=1 and M=1, and is discretized regularly into N×N×N elements. Sample solutions obtained for two different discretizations are shown in Fig. 9c and d. The convergence of the ground structure method for increasingly refined base meshes is given in Table 4 and Fig. 10. Because the problem considers applying the loads and supports at the four nodes closest to the poles, this distance will decrease with refinement, i.e. the angle ϕ _F will increase as the element size in the base mesh decreases (Fig. 14c). Thus, the optimal volume V _{o p t} changes with the discretization. For a regular structured–orthogonal cube mesh of dimension L, discretized with N elements in each direction (Fig. 9), the angle ϕ _F is:

$$\begin{array}{@{}rcl@{}} dx &= &\frac{L}{N} \\ r_{F} &=& \frac{1}{2}\sqrt{dx^{2}+dx^{2}} = \frac{\sqrt{2}L}{2N} \\ \phi_{F} &=& \text{atan} \left( \frac{L/2}{r_{F}} \right) = \text{atan} \left( \frac{\sqrt{2}N}{2} \right)\\ R &=& \sqrt{\left( \frac{L}{2}\right)^{2} + {r_{F}^{2}}} = \frac{L}{2N} \sqrt{N^{2} + 2} \:, \end{array} $$

(13)

where dx is the dimension of a single hexahedral element in the base mesh, r _F is the distance from the pole to the loaded nodes (radius of the moment application ring), and R is the radius of the (optimal) sphere.

Fig. 10

Convergence to the optimal solution of increasingly refined regular orthogonal base meshes under torsion. For this problem, increasing the ground structure connectivity level does have much impact on the quality of the solution

Table 4 Convergence for a regular orthogonal domain of side L=1 under torsion with M=1

The poor convergence rate observed with mesh refinement, and even worse with connectivity level, is attributed to a number of reasons:

• This is a particularly unfavourable scenario for the method: approximating a sphere with a box.

• The load and supports are applied at four discrete locations as opposed to continuously throughout the ring.

• Increasing ϕ _F (equivalent to reducing the radius of the ring where the moment is applied), makes the problem more difficult to approximate numerically. Truss elements, cannot equilibrate a moment applied at a single point, and thus as ϕ _F ≈π/2 the optimal volume $V_{opt} \rightarrow \infty$ (refer to (12)).

• The radius of the (optimal) sphere R (13), exceeds the boundaries of the domain⁴, i.e. 2R>L=1. Thus, the domain does not fully accommodate the optimal analytical solution (refer to the values of R given in Table 4). This situation, however, improves with mesh refinement due to an increase in ϕ _F (see Fig. 11a).

• For this problem in particular, the theoretical optimal solution is comprised solely of curved members. A high connectivity level will generate longer straight members, which do not improve the approximation for this analytical solution. Figure 11b shows the analytical solution viewed from the poles, along with a fictitious discretization illustrating some members at different connectivity levels: lower level members (shorter) have a better chance at approximating the solution.

• The method is discrete, and therefore sensitive to the shape and level of the discretization.

• Finite computational precision, inherent nature of a numerical optimizer, and tolerance parameters used.

Fig. 11

Sources of poor accuracy and convergence for the torsion ball problem approximated with a regular structured–orthogonal cube mesh of dimension L. a A cube domain is not able to accommodate the optimal solution. The radius of the (optimal) sphere R is larger than half of the domain’s width L/2 (refer to (13)). b Polar view of the analytical closed–form solution for the torsion ball problem. A fictitious regular discretization with some members is shown to highlight the inability of higher level members to approximate the solution

4.4 Torsion ball (orthogonal domain) with constant moment latitude ϕ _F

Again using and orthogonal box domain as in the previous example, the error coming from an increase in ϕ _F can be eliminated. Starting with a domain discretized as in Fig. 12a, the mesh can be refined while keeping the locations of the loads and supports fixed as shown in Fig. 12b and c. For a level 3 connectivity, the convergence in this case is shown in Table 5 and Fig. 13. While there is an improvement in the results, these are not yet satisfactory: the optimal solution, a sphere, is discretized and approximated by a box, is a naïve initial guess for this problem, but likely to be made with no a priori knowledge of the solution.

Fig. 12

Top view of the orthogonal domains used in approximating the torsion ball problem, while maintaining a constant angle ϕ _F . a Domain discretized into N=5 elements in each direction. b Domain discretized into N=10 elements in each direction. c Domain discretized into N=15 elements in each direction

Fig. 13

Convergence to the optimal solution of increasingly refined regular orthogonal base meshes under torsion, while maintaining the moment application latitude ϕ _F constant

Table 5 Convergence for the torsion ball problem in an orthogonal domain, with constant moment application latitude ϕ _F

4.5 Torsion ball (spherical domain)

Once knowledge is gained that the solution lies in a close–to–spherical domain, the base mesh can be modified to provide a better approximation. The base mesh in this case is a thick hollow sphere. This is not a shell, for it allows the solution to modify its radii if needed. The load is applied at an intermediate radius r _m between the inner and outer radii of the hollow sphere, r _i and r _o respectively, as shown in Fig. 14a. The domain is represented using spherical coordinates, and is discretized in the 𝜃, ϕ and r directions using N _𝜃 , N _ϕ and N _r elements respectively. A sample mesh discretized with $\left \{ N_{\theta } , N_{\phi } , N_{r} \right \} = \left \{ 30 ,14 ,2 \right \}$ is shown in Fig. 14b, with an axisymmetrical plot given in Fig. 14c. The sphere is hollow, and thus a spherical restriction zone with radius r _i is used.

Fig. 14

Torsion ball problem. a Domain definition, loading and supports. b Sample mesh with r _i =2.9, r _m =3 and r _o =3.1 discretized with N _𝜃 =30, N _ϕ =14 and N _r =2. c Axisymmetric plot of the sample mesh with π/2−ϕ _F =π/10, r _i =2.9, r _m =3 and r _o =3.1 discretized with N _ϕ =14 and N _r =2

If the domain is discretized with a constant spacing on ϕ, then the angle ϕ _F of the applied force is:

$$ \phi_{F} = \frac{\pi}{2} \frac{N_{\phi} - 2}{N_{\phi}} $$

(14)

The optimal volume, given by (12), will increase with refinement on the base mesh due to an increase in ϕ _F . Optimal volumes for increasingly refined base meshes with constant spacing in ϕ are given in Table 6.

Table 6 Convergence for a hollow spherical domain with M=7, r _i =2.9, r _m =3.0 and r _o =3.1

In order to fix the latitude of the applied loads ϕ _F , the size of the first and last element on the ϕ partition are fixed, and the remaining elements are evenly distributed. Thus making ϕ _F constant for all discretizations (Fig. 14c), and consequently V _{o p t} constant regardless of the refinement in the base mesh. Taking π/2−ϕ _F =π/10, the analytical optimal volume is V _{o p t} =51.5964. The optimized volumes for increasingly refined base meshes are given in Table 7, with one of these solutions previously shown in Fig. 1c.

Table 7 Convergence for a hollow spherical domain with M=7, r _i =2.9, r _m =3.0 and r _o =3.1

Making ϕ _F constant ensures that the refinement is approximating the same boundary value problem, and thus a smooth convergence to the analytical closed–form solution is obtained. If ϕ _F is variable, then the method is approximating a different problem with each discretization, and thus convergence is not guaranteed. The torsion ball problem becomes more difficult to approximate numerically if the radius where the moment couple is applied is small (large ϕ _F ). Convergence curves for both cases, variable and constant ϕ _F , are shown in Fig. 15.

Fig. 15

Convergence to the optimal solution of increasingly refined spherical base meshes. The case where ϕ _F increases with refinement begins to diverge as ϕ _F ≈π/2. The case where ϕ _F is constant converges as expected

5 Examples

The following problems were selected to showcase features and issues of the method and its implementation (named GRAND3, and provided as ESM accompanying this publication). Members with cross–sectional area $a_{i} < \left (\mathit {Cutoff}\,\right ) \max \left (\mathbf {a}\right )$ are not plotted. Unless otherwise stated, the stress limit ratio is κ=1.0 with σ _T =1, the collinear tolerance is C o l T o l=0.999999 and the plotting cutoff is C u t o ff=0.005.

5.1 Edge–supported (double) cantilever beam

This problem consists of a three–dimensional box domain, fixed at one end on two (opposite) vertical edges, and loaded at the center of the other end (Fig. 16a). The domain has dimensions L _x =3 and L _y =L _z =1, is loaded with P=1, and is discretized with a regular partition in all three dimensions. Examples for a coarse and a fine base mesh are given in Fig. 16b and c. The optimal volumes obtained from a series of increasingly refined meshes exhibit convergence to a unique value as expected.

Fig. 16

Edge–supported double cantilever problem. a Domain with loads, boundary conditions and dimensions. b Base mesh used to generate a coarse ground structure: L _x =3, L _y =L _z =1 and P=1, discretized with N _x =6 and N _y =N _z =2, resulting in N _e =24 and N _n =63. c Base mesh used to generate a fine ground structure: L _x =3, L _y =L _z =1 and P=1, discretized with N _x =30 and N _y =N _z =10, resulting in N _e =3,000 and N _n =3,751. d Solution for a coarse base mesh with L v l=2 and N _b =962. e Solution for a fine base mesh with L v l=6 and N _b =1,474,218

Two sample solutions obtained for the coarse and a fine base meshes are shown in Fig. 16d and e. These results hint that the optimal closed–form solution consists of two flat cantilever beams (as in Lewiński et al. (1994)), meeting at the load application point. With this assumption, a new base mesh is created for the problem: this (improved) base mesh allows for perfectly flat cantilevers to develop if the optimal structure requires it, as shown in Fig. 17a. The optimal structure obtained for this new base mesh can be seen in Fig. 17b, and confirms the flat cantilever hypothesis.

Fig. 17

Edge–supported double cantilever problem with improved base mesh discretization. a Base mesh used to generate the ground structure: discretized with N _x =5 and N _y =N _z =10, resulting in N _e =1,000 and N _n =726. b Solution using the improved base mesh with L v l=6 and N _b =137,877. The resulting optimal volume is V=14.2725

The optimal volumes obtained using regular base meshes show convergence to an absolute optimal in the vicinity of V _{o p t} ≈13.93: this value was obtained using the two–dimensional implementation described in Zegard and Paulino (2014). Convergence data and plots are shown in Table 8 and Fig. 18 respectively.

Fig. 18

Convergence of the optimal volume for the edge–supported double cantilever problem, for a set of increasingly refined ground structures

Table 8 Convergence for the three–dimensional double cantilever beam with L _x =3, L _y =L _z =1 and P=1, approximated using a regular–orthogonal mesh

5.2 Diamond problem

The diamond problem is a cylindrical domain with a coin–shaped (or disc) discontinuity in the middle. This problem shows the capability of the method to find optimal load paths for problems that include discontinuities, imperfections or barriers in their structure. The domain has a vertical load along it’s z axis, as shown in Fig. 19a. The domain is meshed as in Fig. 19b and c. The ground structure is generated for a L v l=3 connectivity, resulting in N _b =109,820. The restriction zone is a disc primitive in the coin–shaped discontinuity. The resulting optimal structure resembles a diamond: the members fan away from the axis to evade the discontinuity. At the point of maximum width, it creates a strong ring with the purpose of shifting the member orientation back into the support as shown in Fig. 19d.

Fig. 19

Diamond problem: Vertically loaded cylinder with a coin–shaped discontinuity. a Half–domain with loads, boundary conditions and dimensions. b Base mesh used to generate the ground structure: N _z =12, N _𝜃 =16 and N _r =5. c Axisymmetric plot of the base mesh with N _z =12 and N _r =5. d Optimal solution obtained with L v l=3 and N _b =109,820

5.3 Cup problem (spider)

This problem consists of an inverted cup–shaped domain, loaded vertically in the interior. Figure 20a shows the half–domain with loads, boundary conditions and dimensions. The domain is discretized using cylindrical coordinates, and the restriction zone is a single rod primitive in the interior of the cup. The resulting mesh is shown in Fig. 20b, with a axisymmetric view given in Fig. 20c. The solution to this problem is shown in Fig. 20d.

Fig. 20

Vertically loaded inverted cup problem. a Half–domain with loads, boundary conditions and dimensions. b Base mesh used to generate the ground structure. c Axisymmetric plot of the base mesh. d Optimal structure generated with L v l=3 and N _b =168,436, resulting in an optimal volume of V=2.9384. e Detail of the optimal structure

Inspecting the top part of the solution (Fig. 20e), it can be seen that this problem is degenerate; the solution lies on a facet of the feasible domain. This is not an issue of the ground structure method, but rather a characteristic of the problem: it does not have a unique solution (Rozvany 1997). This situation can be better understood with a simple 3 force problem (Mazurek et al. 2011): the optimal structure to carry 3 radial forces evenly distributed on a circle of radius R is not unique, as shown in Fig. 21. For the topology in Fig. 21a, the force in each member is N _i =P, and the length of the members is L _i =R. Thus, the optimal volume is:

$$V_{opt1} = 3\left( \frac{P}{\sigma_{T}}\right)\left( R\right) = 3 \frac{PR}{\sigma_{T}} $$

Repeating the analysis for the topology in Fig. 21b, the force in each member is $N_{i}=P/\sqrt {3}$, and the member’s length is $L_{i}=\sqrt {3}R$. Thus, the optimal volume is:

$$V_{opt2} = 3\left( \frac{P/\sqrt{3}}{\sigma_{T}}\right)\left( \sqrt{3}R\right) = 3 \frac{PR}{\sigma_{T}} $$

In fact, any combination of the previous two cases, as in Fig. 21c and d for example, will result in the same optimal volume. In practice, when facing an optimal structure with a degenerate solution like in Fig. 20d, the engineer can decide the final topology. Figure 22a and b are examples of possible optimal topologies for the problem in Fig. 20e.

Fig. 21

Structural optimization problem with a non–unique (degenerate) solution: a, b, c and d are all optimal topologies

Fig. 22

Options of topologies for a degenerate problem: a Spoke and hub option. b Slab option

5.4 Crane problem

The crane (or tower) problem was introduced by Smith (1998), in whose work the domain had to be partitioned into regions in a specialized CAD system. A three–dimensional ground structure was then generated within these regions.

The approach presented here, requires no subdivision of the domain, but does require the definition of restriction zones. Domains are often procedurally generated using geometric primitives. Because the restriction zone is typically a subset of the primitives used to construct the domain, the additional work required is comparatively small.

The domain in Fig. 23a is discretized with two different degrees of refinement as in Fig. 23b and c. The restriction zone is the union of two boxes under both of the tower’s arms. The optimized ground structures for each case are shown in Fig. 23d and e. This example showcases the capability of the method (and implementation) to provide solutions with different levels of detail. Highly detailed solutions provide information into the optimal load transfer mechanism, while coarse solutions are more likely to be developed into real structures.

Fig. 23

Crane problem: Tower with arms loaded at four points. a Domain with loads, boundary conditions and dimensions. b Base mesh used to generate a coarse ground structure: N _e =10 and N _n =38. c Base mesh used to generate a fine ground structure: N _e =768 and N _n =935. d Solution for the coarse base mesh: L v l=3 and N _b =315. e Solution for the fine base mesh: L v l=3 and N _b =47,076; the plotting cutoff is C u t o f f=0.002 to prevent members from ending mid–air

5.5 Lotte tower (Seoul, South Korea)

The Lotte tower is a shell–like domain (no thickness) that is square at the base and circular at the top. This problem was inspired by the design competition of the same name by Skidmore, Owings & Merill LLP (Fig. 24a), and has been previously optimized using a density–based optimization approach by Stromberg et al. (2010). In the present example, the domain is optimized for two loading scenarios: lateral load at the tip acting at 4 points (Fig. 24b), and a torsional load distributed over the top circumference (Fig. 24c).

Fig. 24

Lotte tower problem: a Rendering of the Lotte tower [Ⓒ Skidmore, Owings & Merrill LLP]. b Domain definition, loading and boundary conditions for the laterally loaded tower. c Domain definition, loading and boundary conditions for the torsionally loaded tower. d Base mesh for the ground structure generation, with the restriction surface also shown

The domain’s height is H=80, the square at the base has sides 2a=10, and the circle at the top has a diameter of 2r=10. The domain is discretized using quadrangular surface elements; partitioned into N _z =12 elements along its height, and N _𝜃 =16 elements around, resulting in N _e =192 and N _n =208. The restriction zone is a surface primitive set–back from the interior of the domain by a small spacing, as shown in Fig. 24d.

The ground structure is generated for a L v l=5 connectivity, resulting in N _b =4,100 potential members. The optimized ground structures for the lateral loading and torsional loading cases are shown in Fig. 25a and b respectively.

Fig. 25

Lotte tower problem: a Optimized ground structure for a lateral loading at the top. b Optimized ground structure for a torsional load at the top

The lateral loading causes part of the resulting topology to work as a web (front view in Fig. 25a); developing an arrangement similar to an optimal cantilever, and analogous to optimal flat cantilever beams (Lewiński et al. 1994). The other side of the solution (side view in Fig. 25a) acts as a flange, transferring the load in tension/compression away from the web and to the foundation supports. On the other hand, the problem optimized for torsion results in a diagrid pattern, similar to those used in high–rise buildings.

6 Conclusions

The ground structure generation and analysis methodology presented in Zegard and Paulino (2014) is successfully extended to three–dimensional space. Concavities and holes in the domain are addressed using three–dimensional collision primitives—an extension of the two–dimensional approach. Collision primitives for a variety of shapes are developed, among which the surface primitive offers a viable alternative in the eventual case that no other primitive is adequate.

The method is verified and benchmarked using three problems for which the solutions are known, with the method converging to the analytical solution. Features and details of the convergence process are explored in detail. Additional problems showcase the capability of the method to address complicated domains, and to generate structures with various levels of detail. The ability to handle domains other than boxes has resulted in innovative bio–inspired and natural designs, as is the case with the “Diamond problem” and the “Cup domain or spider” (Figs. 19b and 20d respectively).

The rapid scaling of the complexity in three–dimensional space, make it necessary for the user to employ engineering judgement in order to obtain reasonably good solutions for applied problems. A good solution is such that it can be obtained within reasonable computer time, is detailed enough, and can be manufactured. The “Lotte tower” problem loaded under torsion (Section 5.5), for example, results in a diagrid structure that is both; attractive and feasible.

Appendices

Appendix A: – Nomenclature

A :

Connectivity matrix

a :

Cross–sectional areas vector

B ^T :

Force equilibrium (geometric) matrix

C o l T o l :

Tolerance in the collinearity check

$\hat {\mathbf {d}}$ :

Member’s directional cosines vector

f :

Nodal load vector

G :

Candidate member matrix

l :

Member’s length vector

L v l :

Ground structure connectivity level

n :

Internal (axial) forces vector

N _b :

Number of bars (truss members)

N _{d o f} :

Number of degrees–of–freedom of the structure

N _e :

Number of elements in the base mesh

N _f :

Number of nodes with fixities

N _l :

Number of nodes with loads

N _n :

Number of nodes in the domain

N _{s u p} :

Number of fixed nodal components (or DOFs)

s ⁺,s ⁻ :

Stress constraint (positive) slack variables

V :

Volume

κ :

Tension to compression stress limit ratio

σ :

Member’s (axial) stresses vector

σ _T ,σ _C :

Stress limits in tension and compression

ϕ _F :

Latitude of the the moment application ring for the torsion ball problem

Appendix B: – Collision (intersection) tests

The collision (or intersection) tests are quite common in the the video–game industry and in the field of computational geometry. While not constituting a new development, these derivations are given here for the sake of completeness. The collision primitives for the box, triangle, quadrangle and cylinder follow procedures outlined in Ericson (2004) with some modifications. The sphere, disc and rod⁵ were developed specifically for GRAND3, although similar procedures are likely to be found in literature given the relatively simple nature of the problem.

The surface primitive, built from the triangle and quadrangle primitives, is special; a complicated restriction volume can be translated into testing the collision on its surface. This allows the method to address complicated volumes that would be difficult to represent with the already available primitives.

1.1 B.1 Box primitive

The box primitive is defined by the coordinates of the two extreme vertices; $A_{min}=\left \{ x_{min} ~,~ y_{min} ~,~ z_{min} \right \}$ and $A_{max}=\left \{ x_{max} ~,~ y_{max} ~,~ z_{max} \right \}$. Given a segment $\overline {pq}$, the segment’s directional vector is $\mathbf {d}=\overrightarrow {PQ}=Q-P$, and any point X in the segment is defined as X=P+t d, with 0≤t≤1. The segment collides with the box if there is a sub–segment within $\overline {pq}$ contained inside the box, as shown in Fig. 26.

Fig. 26

Collision test between a box and a segment

Defining the sub–segment $\overline {P^{\prime }Q^{\prime }}$, with $P^{\prime }=P+t_{min}\mathbf {d}$ and $Q^{\prime }=P+t_{max}\mathbf {d}$, the sub–segment is valid if 0≤t _{m i n} ≤t _{m a x} ≤1. Initially t _{m i n} =0 and t _{m a x} =1, positioning nodes P ^′ and Q ^′ at P and Q respectively. The sub–segment is then clipped by the box’s 6 planes, corresponding to x _{m i n} , x _{m a x} , y _{m i n} , y _{m a x} , z _{m i n} and z _{m a x} . If the sub–segment is still valid after the clipping has been done, then the sub–segment is inside the box.

Defining a unit vector in the x direction $\hat {\mathbf {e}}_1 = \left \{ 1 ~,~ 0 ~,~ 0 \right \}$, the procedure for clipping on the x plane is as follows:

$$ t_1 = \frac{ A_{min} \cdot \hat{\mathbf{e}}_1 - P \cdot \hat{\mathbf{e}}_1 }{ \mathbf{d} \cdot \hat{\mathbf{e}}_1} \qquad t_2 = \frac{ A_{max} \cdot \hat{\mathbf{e}}_1 - P \cdot \hat{\mathbf{e}}_1 }{ \mathbf{d} \cdot \hat{\mathbf{e}}_1} $$

(15)

Depending on the orientation of $\overline {pq}$, it could occur that t ₁>t ₂, and in such case their values are switched; $t_1 \leftarrow t_2$ and $t_2 \leftarrow t_1$. Finally, the clipping process is simply:

$$ t_{min} \leftarrow \max \left( t_{min} ~,~ t_1 \right) \qquad t_{max} \leftarrow \min \left( t_{max} ~,~ t_2 \right) $$

(16)

The process is then repeated for the y plane with $\hat {\mathbf {e}}_2 = \left \{ 0 ~,~ 1 ~,~ 0 \right \}$, and finally the z plane with $\hat {\mathbf {e}}_3 = \left \{ 0~,~ 0 ~,~ 1 \right \}$. The segment collides with the box if t _{m i n} ≤t _{m a x} after all the clipping has been carried out. Incidentally, this procedure can address the accidental case where A _{m i n} and A _{m a x} are reversed.

1.2 B.2 Triangle primitive

Given a segment $\overline {pq}$, intersecting the plane defined by points A, B and C in space at a point W (Fig. 27). The segment intersects the triangle △A B C if point W lies inside the triangle.

Fig. 27

Collision test between a triangle and a segment

One possible solution is to find the point W, and then check if such point is inside the triangle. Assuming the triangle is defined counterclockwise: point W is inside the triangle if it is located to the left for all edges. Extending to any triangle arrangement (clockwise or counterclockwise): point W is inside the triangle if it is located to the same side for all edges. Based on this idea, the volumes of the three distinct tetrahedra can be defined by segment $\overline {pq}$, and each one of the triangle’s edges. These volumes can be computed by triple products, with the sign of these triple products depending on the manifold orientation of the three vectors defining the tetrahedron. If point W is found to the same side of all edges, then the sign of these volume calculations (triple products) is the same.

Defining the segment’s directional vector as $\mathbf {d}=\overrightarrow {PQ}=Q-P$, then any point X within the segment is defined as X=P+t d, with 0≤t≤1. The normal to the triangle’s plane is $\mathbf {n}=\overrightarrow {AB}\times \overrightarrow {AC}$. The intersection point with the plane of the triangle W is defined as W=P+t _w d, with:

$$ t_w = \frac{\overrightarrow{PA} \cdot \mathbf{n}}{\mathbf{d} \cdot \mathbf{n}} \:. $$

(17)

The triple products are defined as:

$$\begin{array}{@{}rcl@{}} V_1 &=& \left[ \mathbf{d}~ \overrightarrow{PC} ~ \overrightarrow{PB} \right] \\ V_2 &= &\left[ \mathbf{d} ~ \overrightarrow{PA} ~ \overrightarrow{PC} \right]\\ V_3 &=& \left[ \mathbf{d} \; \overrightarrow{PB} \; \overrightarrow{PA} \right] \end{array} $$

(18)

Finally, the segment $\overline {pq}$ intersects the triangle △A B C if and only if:

$$ 0\leq t_w \leq 1 \qquad \text{and} \qquad \text{sign} \left( V_1 \right) = \text{sign} \left( V_2 \right) = \text{sign} \left( V_3 \right) $$

(19)

1.3 B.3 Quadrangle primitive

Splitting the quadrangle into two triangles, the quadrangle is really an extension of the triangle primitive case. It is assumed that the quadrangle is flat and all 4 points lie (approximately) in the same plane. Compared to two complete triangle tests, there is a potential computational saving if one of the two triangles is chosen early in the calculations (triangles △A B ₁ C and △A C B ₂ in Fig. 28).

Fig. 28

Collision test between a quadrangle and a segment

Defining the segment’s directional vector as $\mathbf {d}=\overrightarrow {PQ}=Q-P$, then any point X within the segment is defined as X=P+t d, with 0≤t≤1. The normal to the quadrangle’s plane is $\mathbf {n}=\overrightarrow {AB_1}\times \overrightarrow {AB_2}$. The intersection point with the plane of the quadrangle is defined as W=P+t _w d, with:

$$ t_w = \frac{\overrightarrow{PA} \cdot \mathbf{n}}{\mathbf{d} \cdot \mathbf{n}} ~. $$

(20)

The triple products are defined as:

$$\begin{array}{@{}rcl@{}} V_a = & \left[ \mathbf{d} ~ \overrightarrow{PC} ~ \overrightarrow{PB_1} \right] &= \mathbf{e}_1 \cdot \overrightarrow{PB_1}\\ V_b = & \left[ \mathbf{d} ~ \overrightarrow{PC} ~ \overrightarrow{PB_2} \right] & = \mathbf{e}_1 \cdot \overrightarrow{PB_2}\\ V_2 = & - \left[ \mathbf{d} ~ \overrightarrow{PC} ~ \overrightarrow{PA} \right] & = - \mathbf{e}_1 \cdot \overrightarrow{PA} ~, \end{array} $$

(21)

with $\mathbf {e}_1 = \mathbf {d} \times \overrightarrow {PC}$. If the segment collides with a triangle, then all triple products must have the same sign. Thus, the correct triangle can be chosen at this stage, and the third (and last) triple product can be computed:

$$\begin{array}{@{}rcl@{}} \mathbf{e}_2 &=& ~ \left\{ \begin{array}{lll} \mathbf{d} \times \overrightarrow{PB_1} & ~ \text{ if } ~ & \text{sign} \left( V_a \right) = \text{sign} \left( V_2 \right) \\ \mathbf{d} \times \overrightarrow{PB_2} & ~ \text{ if } ~ & \text{sign} \left( V_b \right) = \text{sign} \left( V_2 \right) \end{array}\right.\\ V_3 &=& \mathbf{e}_2 \cdot \overrightarrow{PA} \end{array} $$

(22)

The segment collides with the quadrangle $\Box AB_1CB_2$ if and only if:

$$ 0\leq t_w \leq 1 \qquad \text{and} \qquad \text{sign} \left( V_2 \right) = \text{sign} \left( V_3 \right) $$

(23)

1.4 B.4 Sphere primitive

Defining the segment’s directional vector as $\mathbf {d}=\overrightarrow {PQ}=Q-P$, then any point X in the segment is defined as X=P+t d, with 0≤t≤1. The segment intersects the sphere if any of the following three criteria is met (Fig. 29):

• 1. Point P is inside the sphere.

• 2. Point Q is inside the sphere.

• 3. The point in the segment that is closest to the sphere’s center is between P and Q and inside the sphere.

Fig. 29

Collision test between a sphere and a segment

Defining a vector v=C−P, then there is collision according to the first criteria if:

$$ \mathbf{v} \cdot \mathbf{v} \leq r^2 $$

(24)

Similarly, there is collision according to the second criteria if:

$$ \left( \mathbf{v}-\mathbf{d} \right) \cdot \left( \mathbf{v}-\mathbf{d} \right) = \mathbf{v} \cdot \mathbf{v} - 2 \mathbf{v} \cdot \mathbf{d} + \mathbf{d} \cdot \mathbf{d} \leq r^2 $$

(25)

The closest point in the line defined by P and Q to the sphere’s center, measured from point P is:

$$ \mathbf{w} = \frac{\mathbf{v} \cdot \mathbf{d}}{\mathbf{d} \cdot \mathbf{d}} \mathbf{d} $$

(26)

This point is inside the sphere if:

$$\begin{array}{@{}rcl@{}} \left( \mathbf{v}-\mathbf{w} \right) \cdot \left( \mathbf{v}-\mathbf{w} \right) & \leq & r^2 \\ \left( \mathbf{v}- \frac{\mathbf{v} \cdot \mathbf{d}}{\mathbf{d} \cdot \mathbf{d}} \mathbf{d} \right) \cdot \left( \mathbf{v} - \frac{\mathbf{v} \cdot \mathbf{d}}{\mathbf{d} \cdot \mathbf{d}} \mathbf{d} \right) & \leq & r^2~, \end{array} $$

(27)

with this point inside the segment $\overline {pq}$ if and only if 0≤w⋅d≤d⋅d, which is an equivalent expression to 0≤t≤1.

1.5 B.5 Disc primitive

Defining the segment’s directional vector as $\mathbf {d}=\overrightarrow {PQ}=Q-P$, then any point X in the segment is defined as X=P+t d, with 0≤t≤1.

The disc is centered at point A, and the normal points towards a point B as in Fig. 30. The normal to the plane of the disc is n=B−A. Defining $\mathbf {v}=\overrightarrow {AP}=P-A$, the intersection with the disc’s plane is found at a point W=P+t _w d:

$$ t_w = - \frac{\mathbf{v} \cdot \mathbf{n}}{\mathbf{d} \cdot \mathbf{n}} $$

(28)

The segment collides with the disc if the distance between point W and the disc’s center A is less than or equal to the disc’s radius:

$$ \overrightarrow{AW} = W-A = P-A+t_w \mathbf{d} = \mathbf{v} - \frac{\mathbf{v} \cdot \mathbf{n}}{\mathbf{d} \cdot\mathbf{n}} \mathbf{d} $$

(29)

Finally, the segment collides with the disc if and only if:

$$ \overrightarrow{AW} \cdot \overrightarrow{AW} = \left( \mathbf{v} - \frac{\mathbf{v} \cdot \mathbf{n}}{\mathbf{d} \cdot \mathbf{n}} \right) \cdot \left( \mathbf{v} - \frac{\mathbf{v} \cdot \mathbf{n}}{\mathbf{d} \cdot \mathbf{n}} \right) \leq r^2 ~, $$

(30)

with 0≤t _w ≤1.

Fig. 30

Collision test between a disc and a segment

1.6 B.6 Cylinder primitive (infinite cylinder)

Defining the segment’s directional vector as $\mathbf {d}=\overrightarrow {PQ}=Q-P$, then any point X in the segment is defined as X=P+t d, with 0≤t≤1. The segment is found to collide with the (infinite) cylinder if:

• 1. The segment collides with the cylinder’s surface.

• 2. The segment is completely contained within the cylinder.

The cylinder’s axis is defined by n=B−A as in Fig. 31. The intersection with the cylinder’s surface is found at points W=P+t _w d. Defining the radial vector of length r from the cylinder’s axis to point W as m, then:

$$\begin{array}{@{}rcl@{}} 0 &=& \mathbf{m} \cdot \mathbf{m} - r^2 \\ 0 &=& \left( \overrightarrow{AW} - \frac{\overrightarrow{AW} \cdot \mathbf{n}}{\mathbf{n} \cdot \mathbf{n} } \mathbf{n} \right) \cdot \left( \overrightarrow{AW} - \frac{\overrightarrow{AW} \cdot \mathbf{n}}{\mathbf{n} \cdot\mathbf{n} } \mathbf{n} \right) - r^2 \end{array} $$

(31)

Defining $\mathbf {v}=\overrightarrow {AP}=P-A$, and expanding $\overrightarrow {AW}$ in terms of v, d and t _w :

$$\begin{array}{@{}rcl@{}} 0 &=& \left( \left( \mathbf{v} + t_w \mathbf{d} \right) - \left[ \frac{ \left( \mathbf{v} + t_w \mathbf{d} \right) \cdot \mathbf{n}}{\mathbf{n} \cdot \mathbf{n} } \right] \mathbf{n} \right) \cdot \\ && \left( \left( \mathbf{v} + t_w \mathbf{d} \right) - \left[ \frac{ \left( \mathbf{v} + t_w \mathbf{d} \right) \cdot \mathbf{n}}{\mathbf{n} \cdot \mathbf{n} } \right] \mathbf{n} \right) - r^2 ~, \end{array} $$

(32)

where terms can be ordered to obtain a quadratic equation for t _w :

$$\begin{array}{@{}rcl@{}} 0 &=& \left[ \mathbf{d} \cdot \mathbf{d} - \frac{\left( \mathbf{d} \cdot \mathbf{n}\right)^2}{\mathbf{n} \cdot \mathbf{n}} \right] t_w^2 \;+ \\ && 2 \left[ \mathbf{v} \cdot \mathbf{d} - \frac{ \left( \mathbf{d} \cdot \mathbf{n}\right)\left( \mathbf{v} \cdot \mathbf{n}\right)}{\mathbf{n} \cdot \mathbf{n}} \right] t_w \;+ \\ && \left( \mathbf{v} \cdot \mathbf{v} \right) - \frac{\left( \mathbf{v} \cdot \mathbf{n}\right)^2}{\mathbf{n} \cdot \mathbf{n}} - r^2 \end{array} $$

(33)

Multiplying by n⋅n, the quadratic equation becomes:

$$\begin{array}{@{}rcl@{}} 0 &=& a t_w^2 + b t_w + c \\ a &=& \left( \mathbf{n} \cdot \mathbf{n} \right) \left( \mathbf{d} \cdot \mathbf{d} \right) - \left( \mathbf{d} \cdot \mathbf{n}\right)^2\\ \frac{b}{2} &=& \left( \mathbf{n} \cdot \mathbf{n} \right) \left( \mathbf{v} \cdot \mathbf{d} \right) - \left( \mathbf{d} \cdot \mathbf{n} \right) \left( \mathbf{v} \cdot \mathbf{n} \right) \\ c &=& \left( \mathbf{n} \cdot \mathbf{n} \right) \left[ \left( \mathbf{v} \cdot \mathbf{v} \right) - r^2 \right] -\left( \mathbf{v} \cdot \mathbf{n}\right)^2, \end{array} $$

(34)

with solutions given by:

$$ t_w = \frac{-b \pm \sqrt{b^2-4ac}}{2a} = \frac{-\frac{b}{2} \pm \sqrt{\left( \frac{b}{2}\right)^2-ac}}{a} $$

(35)

The (infinite) line defined by the segment does not intersect the cylinder if the discriminant in (35) is negative (i.e. $\left (b/2\right )^2-ac < 0$). If the discriminant is positive, then an additional check must be made to ensure the intersection point is within the segment $\overline {pq}$. The segment collides with the cylinder if 0≤t _w ≤1 for any of the two roots (points W and W ^′ in Fig. 31).

Fig. 31

Collision test between a cylinder (infinite length) and a segment

Finally, the segment is completely contained inside the cylinder, if the distance from the cylinder’s axis to point P is less than or equal to the radius r:

$$ \left( \mathbf{v} - \frac{\mathbf{v} \cdot \mathbf{n}}{\mathbf{n} \cdot \mathbf{n} } \mathbf{n} \right) \cdot \left( \mathbf{v} - \frac{\mathbf{v} \cdot \mathbf{n}}{\mathbf{n} \cdot \mathbf{n} } \mathbf{n} \right) \leq r^2 $$

(36)

1.7 B.7 Rod primitive

The rod primitive is a combination of the infinite cylinder and disc primitives with some minor modifications. The segment collides with the rod if any of the following 4 situations occur:

• The segment collides with the finite cylinder’s surface.

• The segment collides with the A endcap (disc).

• The segment collides with the B endcap (disc).

• The segment is fully contained within the rod.

The collision with the finite cylinder’s surface begins from the test primitive for the infinite cylinder outlined in (34) and (35). In addition, the intersection points W and $W^{\prime }$ (Fig. 32) must be in the surface between the endcaps. Thus, an additional check is required; the segment collides with the finite cylinder’s surface if:

$$\begin{array}{@{}rcl@{}} 0 &\leq & \mathbf{w} \cdot \mathbf{n} \leq \mathbf{n} \cdot \mathbf{n} \\ 0 &\leq & \left( \mathbf{v} + t_w \mathbf{d} \right) \cdot \mathbf{n} \leq \mathbf{n} \cdot \mathbf{n} \end{array} $$

(37)

for any of the two roots of t _w from (35), with 0≤t _w ≤1.

Fig. 32

Collision test between a rod (finite cylinder with endcaps) and a segment

The collision with the endcaps A and B follow the procedure for the disc primitive. Equation (30) can be used with no modification to test the collision against endcap A. The B endcap is analogous to the endcap A; the segment collides with endcap B if:

$$\begin{array}{@{}rcl@{}} \overrightarrow{BW} \cdot \overrightarrow{BW} &\leq & r^2 \\ \left( \mathbf{v} + \frac{\mathbf{n} \cdot \mathbf{n} - \mathbf{v} \cdot \mathbf{n}}{\mathbf{d} \cdot \mathbf{n}}\right) \cdot \left( \mathbf{v} + \frac{\mathbf{n} \cdot \mathbf{n} - \mathbf{v} \cdot \mathbf{n}}{\mathbf{d}\cdot \mathbf{n}} \right) &\leq& r^2 ~, \end{array} $$

(38)

with:

$$ 0\leq \left( t_w = \frac{\mathbf{n} \cdot \mathbf{n} - \mathbf{v} \cdot \mathbf{n}}{\mathbf{d} \cdot \mathbf{n}} \right) \leq 1 $$

(39)

Finally, if the segment is completely contained in the rod, then point P must be inside the rod. In other words, if the distance from point P to the cylinder’s axis is less than or equal to r:

$$ \left( \mathbf{v} - \frac{\mathbf{v} \cdot \mathbf{n}}{\mathbf{n} \cdot \mathbf{n} } \mathbf{n} \right) \cdot \left( \mathbf{v} - \frac{\mathbf{v} \cdot \mathbf{n}}{\mathbf{n} \cdot \mathbf{n} } \mathbf{n} \right) \leq r^2 ~, $$

(40)

with an additional check to verify point A is between the endcaps:

$$ 0 \leq \frac{\mathbf{v} \cdot \mathbf{n}}{\mathbf{n} \cdot \mathbf{n} } \leq 1 $$

(41)

1.8 B.8 Surface primitive

The surface primitive builds from the base of the triangle and quadrangle primitives. The surface primitive can handle any surface provided that it is tessellated (discretized) and the points in each facet lie (approximately) in the same plane. In addition, it is assumed that all facets are convex in their own plane. An example of a tessellated surface is shown in Fig. 33: the surface was tessellated using triangles and quadrangles. The inputs for this collision primitive are:

• A matrix of nodes RNODE of size N _{r n} ×3, where N _{r n} is the number of nodes in the collision surface.

• A list (cell) with facet connectivity RFACE of size N _{r f} ×1, where N _{r f} is the number of facets in the collision surface. Each entry in RFACE is a row vector with nodal connectivity (based on RNODE).

Fig. 33

Collision surface example: Surface is tessellated into triangles and quadrangles

The surface collision primitive can address facets with more than 4 nodes (flat polygons), provided that all the nodes lie in (approximately) the same plane. This polygon will be subdivided into triangles and evaluated sequentially.

1.9 B.9 Development & debugging of collision tests

Algorithms for additional intersection tests can be found in literature or derived. It is strongly recommended however, to test and debug new collision primitives thoroughly. In the present work for example, simple game–like user interfaces were used for live testing the collision primitives (see Fig. 34 for an example).

Fig. 34

User interface for live testing and debugging the disc collision primitive