“K-set tilable surfaces” by Fu, Lai, Cohen-Or and Ying

  • ©Chi-Wing Fu, Chi-Fu Lai, Daniel Cohen-Or, and He Ying




    K-set tilable surfaces



    This paper introduces a method for optimizing the tiles of a quad-mesh. Given a quad-based surface, the goal is to generate a set of K quads whose instances can produce a tiled surface that approximates the input surface. A solution to the problem is a K-set tilable surface, which can lead to an effective cost reduction in the physical construction of the given surface. Rather than molding lots of different building blocks, a K-set tilable surface requires the construction of K prefabricated components only. To realize the K-set tilable surface, we use a cluster-optimize approach. First, we iteratively cluster and analyze: clusters of similar shapes are merged, while edge connections between the K quads on the target surface are analyzed to learn the induced flexibility of the K-set tilable surface. Then, we apply a non-linear optimization model with constraints that maintain the K quads connections and shapes, and show how quad-based surfaces are optimized into K-set tilable surfaces. Our algorithm is demonstrated on various surfaces, including some that mimic the exteriors of certain renowned building landmarks.


    1. Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., and Protasi, M. 1999. Complexity and Approximation. Springer. ISBN 3-540-65431-3.Google Scholar
    2. Blanc, A., McEvoy, M., and Plank, R., Eds. 1993. Architecture and construction in steel. Taylor & Francis. 640 pages, ISBN 978-0419176602.Google Scholar
    3. Bobenko, A. I., and Suris, Y. B. 2008. Discrete Differential Geometry. American Math. Society. ISBN 978-0821847008.Google Scholar
    4. Daniels, J., Silva, C. T., Shepherd, J., and Cohen, E. 2008. Quadrilateral mesh simplification. ACM Trans. Graph. (SIGGRAPH ASIA 2008) 27, 5. Google ScholarDigital Library
    5. Eigensatz, M., Kilian, M., Schiftner, A., Mitra, N., Pottmann, H., and Pauly, M. 2010. Paneling architectural freeform surfaces. ACM Tran. Graphics (Proc. of SIGGRAPH) 29, 3. Google ScholarDigital Library
    6. Gal, R., Sorkine, O., Mitra, N. J., and Cohen-Or, D. 2009. iWIRES: an analyze-and-edit approach to shape manipulation. ACM Trans. Graph. (SIGGRAPH 2009) 28, 3. Google ScholarDigital Library
    7. Kilian, M., Flöry, S., Chen, Z., Mitra, N. J., Sheffer, A., and Pottmann, H. 2008. Developable surfaces with curved creases. In Advances in Architectural Geometry, 33–36.Google Scholar
    8. Liu, Y., Pottmann, H., Wallner, J., Yang, Y.-L., and Wang, W. 2006. Geometric modeling with conical meshes and developable surfaces. ACM Trans. Graph. (SIGGRAPH 2006) 25, 3, 681–689. Google ScholarDigital Library
    9. Massarwi, F., Gotsman, C., and Elber, G. 2007. Papercraft models using generalized cylinders. In 5th Pacific Conf. on Comp. Graphics and App., 148–157. Google ScholarDigital Library
    10. Mitani, J., and Suzuki, H. 2004. Making papercraft toys from meshes using strip-based approximate unfolding. ACM Tran. Graphics (Proc. of SIGGRAPH) 23, 3, 259–263. Google ScholarDigital Library
    11. Mitra, N. J., Guibas, L., and Pauly, M. 2007. Symmetrization. ACM Tran. on Graphics (SIGGRAPH 2007) 26, 3. Google ScholarDigital Library
    12. Mori, Y., and Igarashi, T. 2007. Plushie: an interactive design system for plush toys. ACM Tran. Graphics (Proc. SIGGRAPH) 26, 3. Google ScholarDigital Library
    13. Pottmann, H., Asperl, A., Hofer, M., and Kilian, A. 2007. Architectural Geometry. Bentley Institute Press. 724 pages, ISBN 978-1-934493-04-5.Google Scholar
    14. Pottmann, H., Liu, Y., Wallner, J., Bobenko, A., and Wang, W. 2007. Geometry of multi-layer freeform structures for architecture. ACM Tran. Graphics (SIGGRAPH 2007) 26, 3. Google ScholarDigital Library
    15. Pottmann, H., Schiftner, A., Bo, P., Schmiedhofer, H., Wang, W., Baldassini, N., and Wallner, J. 2008. Freeform surfaces from single curved panels. ACM Tran. Graphics (SIGGRAPH 2008) 27, 3. Google ScholarDigital Library
    16. Rose, K., Sheffer, A., Wither, J., Cani, M.-P., and Thibert, B. 2007. Developable surfaces from arbitrary sketched boundaries. In Symposium on Geometry Processing (SGP), 163–172. Google ScholarDigital Library
    17. Schiftner, A., Höbinger, M., Wallner, J., and Pottmann, H. 2009. Packing circles and spheres on surfaces. ACM Trans. Graph. (SIGGRAPH ASIA 2009) 28, 5. Google ScholarDigital Library
    18. Shatz, I., Tal, A., and Leifman, G. 2006. Paper craft models from meshes. Visual Computer 22, 9, 825–834. Google ScholarDigital Library
    19. Singh, M., and Schaefer, S. 2010. Triangle surfaces with discrete equivalence classes. ACM Tran. Graphics (Proc. of SIGGRAPH) 29, 3. Google ScholarDigital Library
    20. Xu, K., Zhang, H., Tagliasacchi, A., Liu, L., Li, G., Meng, M., and Xiong, Y. 2009. Partial intrinsic reflectional symmetry of 3D shapes. ACM Trans. Graph. (SIGGRAPH ASIA 2009) 28, 5. Google ScholarDigital Library
    21. Yan, D.-M., Liu, Y., and Wang, W. 2006. Quadric surface extraction by variational shape approximation. In Geometric Modeling and Processing, Springer Berlin/Heidelberg, 73–86. Google ScholarDigital Library

ACM Digital Library Publication: