Author: Brittney Fahnestock and Yixin Lok
Project Mentor: Rulin Chen, Singapore University of Technology and Design
Volunteer Teaching Assistant: Kyle Onghai
Introduction
A K-set surface is a surface mesh that has each of its faces categorized into K discrete equivalence classes. Each discrete equivalence class corresponds to a fixed template polygon, and instances of these templates are used in place of the original mesh faces to form the final assembly structure. As we reduce the variety of building components, we improve the ease of fabrication and assembly – which is why we use K-set surfaces.
In this project, we use a hierarchical approach to cluster polygons and the ShapeOp library to optimize the given surfaces to produce K-set surfaces. Compared to previous works that aim to produce K-set surfaces in fixed topology (e.g., triangular surfaces or quadrilateral surfaces), our approach is able to create K-set surfaces with a variety of topologies.
Problem Formulation
Our input is a freeform surface and a chosen topology. Our output is a small set of discrete equivalence classes (i.e., template polygons) where the instances of template polygons can resemble the given surface as close as possible. Other design requirements include: 1) each polygon should be planar for easing fabrication and assembly process; 2) the intra-cluster variance should be converged to zero if possible.
Method
We use a cluster-and-optimize approach to produce K-set surfaces. In general, our approach includes four stages: (i) base mesh initialization; (ii) polygon clustering; (iii) mesh optimization; and (iv) template replacement.
(i) Base mesh initialization
In order to map the 2D pattern to the surface, we will utilize an as-rigid-as-possible algorithm. As-rigid-as-possible algorithm is utilized because of its ability to maintain the pattern while mapping.
Figure 1. Base mesh initialization.
(ii) Polygon clustering
We use a hierarchical approach to cluster polygons, i.e., we first cluster edges and diagonals, then we use the cluster labels of edges and diagonals to cluster polygons. The user may input two Ks to directly control the edges and diagonals, but may not directly control the K for polygons. Note that the premise for using this clustering approach is all the polygons should be planar. For each polygon cluster, we compute a centroid polygon template as the target polygon for the polygons in the cluster at the following optimization stage.
Figure 2. Our proposed hierarchical approach to clustering the base mesh polygons.
(iii) Mesh optimization
At this stage, our goal is to optimize base mesh to minimize the intra-cluster variances, i.e., each polygon should be as similar as its corresponding polygon template computed at the previous clustering stage. Our optimization function is as following:
\( E = E_{\text{polygon}} + E_{\text{surf}} + E_{\text{smth}} \)
where
\( E_{\text{polygon}} = E_{\text{edge}} + E_{\text{diagonal}} + E_{\text{planar}} \)
Epolygon: This term refers to the requirement that each polygon be optimized to closely match its corresponding centroid polygon template. Specifically, the length of each edge and diagonal should be as close as possible to the corresponding edge and diagonal in the centroid polygon, while maintaining the planar condition.
Esurf: This term refers to the requirement that the optimized surface should be as close as possible to the user-specified given surface.
Esmooth: This term refers to the requirement that the optimized surface should be as smooth as possible.
The geometry solver used is ShapeOp, as this library uses a state of the art physics solver that applies multiple constraints needed for shape optimization. In this project, ShapeOp helps us to convert the our proposed energy terms to the optimization functions represented by vertex positions.
(iv) Template replacement
After mesh optimization, we replace each polygon in the opimized surface with its corresponding template. In each polygon replacement process, we will find a best alignment orientation by calculating the minimal distance between vertices of polygons:
\( s(S_i, \tilde{S}_i) = \displaystyle\min_{k} \displaystyle\sum_{l=1}^{2L} \| \mathbf{v}_l – T_k(\tilde{\mathbf{v}}_l) \|^2 \)
After the polygon replacement, there will be errors since the conflicting optimization goals. Thanks to our proposed mesh optimization method, these errors are well minimized.
Figure 3. Errors after polygon replacement.
Result
We provide a series of K-set surfaces witn various surfaces and topologies. For each result, we provide the surfaces before and after centroid polygon replacement. The greater the similarity between the results before and after replacement, the more it demonstrates the effectiveness of our proposed method for producing K-set surfaces. We observe that there tends to be a trade off between a low K value and a low surface approximation error, as we replace each original mesh face with K templates.
| K-set surface before replacement | K-set surface after replacement | Number of polygons | Number of unique polygons |
 |  | 204 | 12 |
 |  | 423 | 20 |
 |  | 250 | 58 |
 |  | 289 | 51 |
 |  | 161 | 24 |
References
[1] Fu, Chi-Wing, et al. “K-set tilable surfaces.” ACM transactions on graphics (TOG) 29.4 (2010): 1-6.
[2] Singh, Mayank, and Scott Schaefer. “Triangle surfaces with discrete equivalence classes.” ACM SIGGRAPH 2010 papers. 2010. 1-7.
[3] Chen, Rulin, et al. “Masonry shell structures with discrete equivalence classes.” ACM Transactions on Graphics 42.4 (2023).
[4] Deuss, Mario, et al. “ShapeOp—a robust and extensible geometric modelling paradigm.” Modelling Behaviour: Design Modelling Symposium 2015. Springer International Publishing, 2015.
