Constructing self-supporting surfaces with planar quadrilateral elements

Our method takes a self-supporting surface represented by triangle mesh as input. We first compute the principal curvatures and directions for each triangular face using a new method for computing the curvature tensor on triangle meshes. Then we group the triangular faces whose principal curvature difference is small. We call these faces free faces and the remaining faces fixed faces. Since the principal directions on fixed charts are already conjugate, our goal is to construct a pair of conjugate directions for each free chart. Towards this goal, we compute a stretching matrix that turns the principal directions of free charts into conjugate directions. The principal directions of the fixed charts and the conjugate directions of the free charts induce a conjugate direction field on the input mesh. Applying the mixed integer quadrangulation method [ 22 ] to the CDF, we parameterize the triangle mesh and extract the planar quadrilateral elements. We present the algorithmic details in Sections 3.2-3.6. We show the algorithmic pipeline of our method in Fig. 2 and pseudocode in Algorithm 1. To ease reading, we list major notation in Table 1 .

10.1007/s41095-021-0257-1.F002 Fig. 2Algorithmic pipeline. The input is a 3D self-supporting surface represented by a triangle mesh. First, we compute principal curvatures and principal directions for each triangular face. Then, we group the faces with similar principal curvatures, which are called free faces (green). We compute a smooth cross field on the free faces and generate a pair of conjugate directions by stretching the principal directions. Next, we parameterize the triangle mesh using the mixed principal direction field and conjugate direction field. Finally, we extract the planar quadrilateral mesh from the parameterization.

Curvature is the amount by which a curve deviates from a straight line, or a surface deviates from planar. For a smooth 3D surface $𝒓(u,v)$ , the curvature tensor $𝑪$ satisfies $𝑪{𝒓}_u=-{𝒏}_u$ and $𝑪{𝒓}_v=-{𝒏}_v$ , where ${𝒓}_u$ , ${𝒓}_v$ are the tangent vectors of $𝑺$ and ${𝒏}_u$ , ${𝒏}_v$ the partial derivatives of unit normal $𝒏$ .

Since we deal with 3D self-supporting surfaces represented by triangle meshes, we need to discretize $𝑪$ . The key idea is to consider ${𝒓}_u$ , ${𝒓}_v$ as the movement of observation points on the surface. Consider a triangular face $\mathrm{△}ABC$ and its neighbors $\mathrm{△}CBD$ , $\mathrm{△}ACF$ , and $\mathrm{△}BAE$ . Let $𝒏$ , ${𝒏}_i$ $(i=1,2,3)$ be the normals of $\mathrm{△}ABC$ , $\mathrm{△}CBD$ , $\mathrm{△}ACF$ , and $\mathrm{△}AEB$ , and $\delta {𝒏}_i$ be the derivatives of these normals.

10.1007/s41095-021-0257-1.F003 Fig. 3Difference between the observation point movement strategy used in Rusinkiewicz’s method [ 23 ] and our method. (a) In Ref. [ 23 ], the derivatives are $\delta {𝒓}_1=\stackrel{\to }{CB}$ , $\delta {𝒓}_2=\stackrel{\to }{AC}$ , and $\delta {𝒓}_3=\stackrel{\to }{BA}$ , and are based on mesh vertices. (b) In our method, we define $\delta {𝒓}_i={\stackrel{\to }{OO}}_i$ , where $O$ and $O_i$ are the centers of the circumscribed circles of $\mathrm{△}ABC$ and its neighbors.

Observe that each face normal is the cross product of two edge vectors, and each vertex normal is computed as the weighted average of face normals. Therefore, face normals are usually more accurate than vertex normals on triangle meshes. Our movement strategy is to use the centers $O$ and $O_i$ $(i=1,2,3)$ of the circumscribed circles of $\mathrm{△}ABC$ and its neighbors $\mathrm{△}BCD$ , $\mathrm{△}ACF$ , and $\mathrm{△}BAE$ . We compute the derivatives as

(1) $$\delta {𝒓}_i={\stackrel{\to }{OO}}_i$$

and

(2) $$\delta {𝒏}_i=𝒏-{𝒏}_i$$

for $i=1,2,3$ . Since the curvature tensor $𝑪$ satisfies $𝑪\delta {𝒓}_i=-\delta {𝒏}_i$ $(i=1,2,3)$ , we form an over-constrained linear system:

(3) $$\left[\begin{array}{ccc}\hfill \delta {𝒓}_1\cdot {𝒆}_1\hfill & \hfill \delta {𝒓}_1\cdot {𝒆}_2\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill \delta {𝒓}_1\cdot {𝒆}_1\hfill & \hfill \delta {𝒓}_1\cdot {𝒆}_2\hfill \\ \hfill \delta {𝒓}_2\cdot {𝒆}_1\hfill & \hfill \delta {𝒓}_2\cdot {𝒆}_2\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill \delta {𝒓}_2\cdot {𝒆}_1\hfill & \hfill \delta {𝒓}_2\cdot {𝒆}_2\hfill \\ \hfill \delta {𝒓}_3\cdot {𝒆}_1\hfill & \hfill \delta {𝒓}_3\cdot {𝒆}_2\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill \delta {𝒓}_3\cdot {𝒆}_1\hfill & \hfill \delta {𝒓}_3\cdot {𝒆}_2\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \\ \hfill x_3\hfill \end{array}\right]=\left[\begin{array}{c}\hfill \delta {𝒏}_1\cdot {𝒆}_1\hfill \\ \hfill \delta {𝒏}_1\cdot {𝒆}_2\hfill \\ \hfill \delta {𝒏}_2\cdot {𝒆}_1\hfill \\ \hfill \delta {𝒏}_2\cdot {𝒆}_2\hfill \\ \hfill \delta {𝒏}_3\cdot {𝒆}_1\hfill \\ \hfill \delta {𝒏}_3\cdot {𝒆}_2\hfill \end{array}\right]$$

where ${𝒆}_1$ and ${𝒆}_2$ are the axes of the local coordinate system on $\mathrm{△}ABC$ . Then we compute $x_i$ $(i=1,2,3)$ by solving a linear least squares problem. After that, we can form the curvature tensor $𝑪$ :

$$𝑪=\left[\begin{array}{cc}\hfill x_1\hfill & \hfill x_2\hfill \\ \hfill x_2\hfill & \hfill x_3\hfill \end{array}\right]$$

since $𝑪$ is symmetric. The eigenvalues ${\kappa }_i$ and eigenvectors ${𝒅}_i$ $(i=1,2)$ of $𝑪$ are the principal curvatures and directions of face $\mathrm{△}ABC$ . Algorithm 2 gives pseudocode for computing principal curvatures and directions on triangle meshes.