“Modeling and fabrication with specified discrete equivalence classes” by Liu, Zhang, Zhang, Ye, Liu, et al. …

We propose a novel method to model and fabricate shapes using a small set of specified discrete equivalence classes of triangles. The core of our modeling technique is a fabrication-error-driven remeshing algorithm. Given a triangle and a template triangle, which are coplanar and have one-to-one corresponding vertices, we define their similarity error from a manufacturing point of view as follows: the minimizer of the maximum of the three distances between the corresponding pair of vertices concerning a rigid transformation. To compute the similarity error, we convert it into an easy-to-compute form. Then, a greedy remeshing method is developed to optimize the topology and geometry of the input mesh to minimize the fabrication error defined as the maximum similarity error of all triangles. Besides, constraints are enforced to ensure the similarity between input and output shapes and the smoothness of the resulting shapes. Since the fabrication error has been considered during the modeling process, the fabrication process is easy to proceed. To assist users in performing fabrication using common materials and tools manually, we present a straightforward manufacturing solution. The feasibility and practicability of our method are demonstrated over various examples, including seven physical manufacturing models with only nine template triangles.

1. Pierre Alliez, Giuliana Ucelli, Craig Gotsman, and Marco Attene. 2008. Recent advances in remeshing of surfaces. In Shape analysis and structuring. 53–82.Google Scholar
2. K. S. Arun, T. S. Huang, and S. D. Blostein. 1987. Least-Squares Fitting of Two 3-D Point Sets. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-9, 5 (1987), 698–700.Google ScholarDigital Library
3. Mario Botsch and Leif Kobbelt. 2004. A Remeshing Approach to Multiresolution Modeling. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (SGP ’04). 185–192.Google ScholarDigital Library
4. Mario Botsch, Leif Kobbelt, Mark Pauly, Pierre Alliez, and Bruno Lévy. 2010. Polygon mesh processing. AK Peters/CRC Press.Google Scholar
5. Xuelin Chen, Honghua Li, Chi-Wing Fu, Hao Zhang, Daniel Cohen-Or, and Baoquan Chen. 2018. 3D Fabrication with Universal Building Blocks and Pyramidal Shells. ACM Trans. Graph. 37, 6 (2018).Google ScholarDigital Library
6. Xiao-Xiang Cheng, Xiao-Ming Fu, Chi Zhang, and Shuangming Chai. 2019. Practical Error-Bounded Remeshing by Adaptive Refinement. Computers & Graphics 82 (2019), 163–173.Google ScholarDigital Library
7. Michael Eigensatz, Martin Kilian, Alexander Schiftner, Niloy J. Mitra, Helmut Pottmann, andMark Pauly. 2010. Paneling Architectural Freeform Surfaces. ACM Trans. Graph. 29, 4 (2010).Google ScholarDigital Library
8. Chi-Wing Fu, Chi-Fu Lai, Ying He, and Daniel Cohen-Or. 2010. K-Set Tilable Surfaces. ACM Trans. Graph. 29, 4 (2010).Google ScholarDigital Library
9. Xiao-Ming Fu, Yang Liu, John Snyder, and Baining Guo. 2014. Anisotropic simplicial meshing using local convex functions. ACM Transactions on Graphics (SIGGRAPH Asia) 33, 6 (2014).Google Scholar
10. Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle. 1993. Mesh Optimization. In Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’93). 19–26.Google ScholarDigital Library
11. K. Hu, D. Yan, D. Bommes, P. Alliez, and B. Benes. 2017. Error-Bounded and Feature Preserving Surface Remeshing with Minimal Angle Improvement. IEEE. T. Vis. Comput. Gr. 23, 12 (2017), 2560–2573.Google ScholarCross Ref
12. Mathieu Huard, Michael Eigensatz, and Philippe Bompas. 2015. Planar Panelization with Extreme Repetition. In Advances in Architectural Geometry 2014. 259–279.Google Scholar
13. Wenzel Jakob, Marco Tarini, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Instant Field-aligned Meshes. ACM Trans. Graph. 34, 6 (2015), 189:1–189:15.Google ScholarDigital Library
14. J. A. Nelder and R. Mead. 1965. A Simplex Method for Function Minimization. Comput. J. 7, 4 (1965), 308–313.Google ScholarCross Ref
15. I-Chao Shen, Ming-Shiuan Chen, Chun-Kai Huang, and Bing-Yu Chen. 2020. ZomeFab: Cost-Effective Hybrid Fabrication with Zometools. Comput. Graph. Forum 39, 1 (2020), 322–332.Google ScholarCross Ref
16. Mayank Singh and Scott Schaefer. 2010. Triangle Surfaces with Discrete Equivalence Classes. ACM Trans. Graph. 29, 4 (2010).Google ScholarDigital Library
17. Jian-Ping Su, Chunyang Ye, Ligang Liu, and Xiao-Ming Fu. 2020. Efficient Bijective Parameterizations. ACM Trans. Graph. 39, 4 (2020).Google ScholarDigital Library
18. Bolun Wang, Teseo Schneider, Yixin Hu, Marco Attene, and Daniele Panozzo. 2020. Exact and Efficient Polyhedral Envelope Containment Check. ACM Trans. Graph. 39, 4 (2020).Google ScholarDigital Library
19. Yiqun Wang, Dong-Ming Yan, Xiaohan Liu, Chengcheng Tang, Jianwei Guo, Xiaopeng Zhang, and Peter Wonka. 2018. Isotropic Surface Remeshing without Large and Small Angles. IEEE. T. Vis. Comput. Gr. (2018).Google Scholar
20. Dong-Ming Yan, Bruno Lévy, Yang Liu, Feng Sun, and Wenping Wang. 2009. Isotropic remeshing with fast and exact computation of restricted Voronoi diagram. Computer graphics forum 28, 5 (2009), 1445–1454.Google Scholar
21. Yang Yang, Wen-Xiang Zhang, Yuan Liu, Ligang Liu, and Xiao-Ming Fu. 2020. Error-Bounded Compatible Remeshing. ACM Trans. Graph. 39, 4 (2020).Google ScholarDigital Library
22. Zichun Zhong, Xiaohu Guo, Wenping Wang, Bruno Lévy, Feng Sun, Yang Liu, and Weihua Mao. 2013. Particle-based Anisotropic Surface Meshing. ACM Trans. Graph. 32, 4 (2013), 99:1–99:14.Google ScholarDigital Library
23. Tianyu Zhu, Chunyang Ye, Xiao-Ming Fu, and Shuangming Chai. 2020. Greedy Cut Construction for Parameterizations. Computer Graphics Forum 39, 2 (2020), X.Google ScholarCross Ref
24. Henrik Zimmer, Marcel Campen, David Bommes, and Leif Kobbelt. 2012. Rationalization of Triangle-Based Point-Folding Structures. Comput. Graph. Forum 31, 2pt3 (2012), 611–620.Google Scholar
25. H. Zimmer and L. Kobbelt. 2014. Zometool Rationalization of Freeform Surfaces. IEEE Transactions on Visualization and Computer Graphics 20, 10 (2014), 1461–1473.Google ScholarCross Ref
26. Henrik Zimmer, Florent Lafarge, Pierre Alliez, and Leif Kobbelt. 2014. Zometool shape approximation. Graphical Models 76, 5 (2014), 390 — 401.Google ScholarDigital Library