Biswajit Banerjee

Generating periodic RVEs with polydisperse ellipsoids

Part 4: An barycentric coordinate face intersection check


vertex numbering
Figure 1. Periodic unit cell showing particles missed by the face-ellipsoid intersection check in blue and the periodic particles in green.

In the Part 3, we discussed an actual implementation of a face-ellipsoid intersection algorithm. However, this algorithm has two drawbacks:

  • More floating point operations are needed than absolutely necessary.
  • The algorithm misses some particles depending of their position and shape.

In this article we will see an alternative (and easier) way of identifying if a particle intersects a face.

Point inside triangle in barycentric coordinates

Notice that each face of the container can be divided into two triangles. A simpler check of intersection is to find whether the projection of the center of the ellipsoid on to a face lies inside either triangle. We can use barycentric coordinates on a triangle to find if a point is inside the triangle. In these coordinates, a point in a triangle is given by

$$ \mathbf{x}_p = s \mathbf{x}_1 + t \mathbf{x}_2 + u \mathbf{x}_3 $$

where are parameters and are the coordinates of the three vertices. The parameters have the properties that and .

Using the second property, we can write

$$ \mathbf{x}_p - \mathbf{x}_3 = s (\mathbf{x}_1 - \mathbf{x}_3) + t (\mathbf{x}_2 - \mathbf{x}_3) $$

If we define

$$ \mathbf{v}_p := \mathbf{x}_p - \mathbf{x}_3 ~,~~ \mathbf{v}_1 := \mathbf{x}_1 - \mathbf{x}_3 ~,~~ \mathbf{v}_2 := \mathbf{x}_2 - \mathbf{x}_3 $$

we can write the coordinates of a point in barycentric coordinates as

$$ \mathbf{v}_p = s \mathbf{v}_1 + t \mathbf{v}_2 $$

To find , we take dot products of the above equation with to get

$$ \begin{align} \mathbf{v}_p \cdot \mathbf{v}_1 & = s \mathbf{v}_1 \cdot \mathbf{v}_1 + t \mathbf{v}_2 \cdot \mathbf{v}_1 \\ \mathbf{v}_p \cdot \mathbf{v}_2 & = s \mathbf{v}_1 \cdot \mathbf{v}_2 + t \mathbf{v}_2 \cdot \mathbf{v}_2 \end{align} $$


$$ \begin{align} v_{p1} & := \mathbf{v}_p \cdot \mathbf{v}_1 ~,~~ v_{p2} := \mathbf{v}_p \cdot \mathbf{v}_2 \\ v_{11} & := \mathbf{v}_1 \cdot \mathbf{v}_1 ~,~~ v_{12} := \mathbf{v}_2 \cdot \mathbf{v}_1 = \mathbf{v}_1 \cdot \mathbf{v}_2 ~,~~ v_{22} := \mathbf{v}_2 \cdot \mathbf{v}_2 \end{align} $$

and solve for to get

$$ \begin{align} t &= \frac{v_{p2} v_{11} - v_{p1} v_{12}}{v_{11} v_{22} - v_{12} v_{12}} \\ s &= \frac{v_{p1} - t\, v_{12}}{v_{11}} \end{align} $$

A point lies inside the triangle if

$$ s > 0,~ t > 0,~ s + t < 1 $$

Face-ellipsoid intersection

vertex numbering
Figure 2. Periodic unit cell showing that particles missed by the previous approach are identified correctly using the barycentric coordinate check.

If we use the above approach to compute face ellipsoid intersections, particles intersecting faces of the domain are identified correctly (Figure 2). In this particular case, we have shrunk the domain by an amount equal to twice the shortest particle radius. We can see the effect of that choice in Figure 2 where a blue particle is visible at the bottom of the domain because it is just outside the shrunk box.

If you have questions/comments/corrections, please contact banerjee at parresianz dot com dot zen (without the dot zen).