“Packing circles and spheres on surfaces”
Conference:
Type(s):
Title:
- Packing circles and spheres on surfaces
Session/Category Title: Shape analysis
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Inspired by freeform designs in architecture which involve circles and spheres, we introduce a new kind of triangle mesh whose faces’ incircles form a packing. As it turns out, such meshes have a rich geometry and allow us to cover surfaces with circle patterns, sphere packings, approximate circle packings, hexagonal meshes which carry a torsion-free support structure, hybrid tri-hex meshes, and others. We show how triangle meshes can be optimized so as to have the incircle packing property. We explain their relation to conformal geometry and implications on solvability of optimization. The examples we give confirm that this kind of meshes is a rich source of geometric structures relevant to architectural geometry.
References:
1. Alliez, P., Colin de Verdière, É., Devillers, O., and Isenburg, M. 2005. Centroidal Voronoi diagrams for isotropic surface remeshing. Graphical Models 67, 204–231. Google ScholarDigital Library
2. Aurenhammer, F. 1987. Power diagrams: Properties, algorithms and applications. SIAM J. Comput. 16, 1, 78–96. Google ScholarDigital Library
3. Bach, K., Ed. 1990. Radiolaria, vol. 33 of Publ. Inst. Lightweight Structures. Univ. Stuttgart. (series editor: Frei Otto).Google Scholar
4. Bobenko, A., and Springborn, B. 2004. Variational principles for circle patterns and Koebe’s theorem. Trans. Amer. Math. Soc. 356, 659–689.Google ScholarCross Ref
5. Bobenko, A., and Suris, Yu. 2008. Discrete differential geometry: Integrable Structure. No. 98 in Graduate Studies in Math. American Math. Soc.Google Scholar
6. Bobenko, A., Hoffmann, T., and Springborn, B. A. 2006. Minimal surfaces from circle patterns: Geometry from combinatorics. Annals Math. 164, 231–264.Google ScholarCross Ref
7. Cecil, T. 1992. Lie Sphere Geometry. Springer.Google Scholar
8. Chen, Y., Davis, T. A., Hager, W. W., and Rajamanickam, S. 2008. Algorithm 887: Cholmod, supernodal sparse Cholesky factorization and update/downdate. ACM Trans. Math. Softw. 35, 3, #22, 1–14. Google ScholarDigital Library
9. Gu, X. D., and Yau, S.-T. 2008. Computational Conformal Geometry. International Press.Google Scholar
10. He, Z. X., and Schramm, O. 1993. Fixed points, Koebe uniformization and circle packings. Annals Math. 137, 369–406.Google ScholarCross Ref
11. Jin, M., Kim, J., Luo, F., and Gu, X. D. 2008. Discrete surface Ricci flow. IEEE Trans. Vis. Comput. Graph. 14, 5, 1030–1043. Google ScholarDigital Library
12. Jin, M., Zeng, W., Luo, F., and Gu, X. D. 2009. Computing Teichmüller shape space. IEEE Trans. Vis. Comput. Graph. 15, 3, 504–517. Google ScholarDigital Library
13. Liu, Y., Pottmann, H., Wallner, J., Yang, Y.-L., and Wang, W. 2006. Geometric modeling with conical meshes and developable surfaces. ACM Trans. Graphics 25, 3, 681–689. Proc. SIGGRAPH. Google ScholarDigital Library
14. Liu, Y., Wang, W., Lévy, B., Sun, F., Yan, D.-M., Lu, L., and Yang, C. 2009. On centroidal Voronoi tessellation — energy smoothness and fast computation. ACM Trans. Graphics. to appear. CS Tech. Report 2008–18, Univ. Hong Kong. Google ScholarDigital Library
15. Luo, F., Gu, X. D., and Dai, J. 2008. Variational Principles for Discrete Surfaces. International Press.Google Scholar
16. Luo, F. 2004. Combinatorial Yamabe flow on surfaces. Commun. Contemp. Math 6, 765–780.Google ScholarCross Ref
17. Pottmann, H., Asperl, A., Hofer, M., and Kilian, A. 2007. Architectural Geometry. Bentley Institute Press.Google Scholar
18. Pottmann, H., Brell- Cokcan, S., and Wallner, J. 2007. Discrete surfaces for architectural design. In Curves and Surface Design: Avignon 2006. Nashboro Press, 213–234.Google Scholar
19. Pottmann, H., Liu, Y., Wallner, J., Bobenko, A., and Wang, W. 2007. Geometry of multi-layer freeform structures for architecture. ACM Trans. Graphics 26, 3, #65, 1–11. Proc. SIGGRAPH. Google ScholarDigital Library
20. Pottmann, H., Kilian, A., and Hofer, M., Eds. 2008. AAG 2008 — Advances in Architectural Geometry. Proceedings of the Conference in Vienna, September 13–16.Google Scholar
21. Springborn, B., Schröder, P., and Pinkall, U. 2008. Conformal equivalence of triangle meshes. ACM Trans. Graphics 27, 3, #77, 1–11. Proc. SIGGRAPH. Google ScholarDigital Library
22. Spuybroek, L. 2004. NOX: Machining Architecture. Thames&Hudson.Google Scholar
23. Stephenson, K. 2005. Introduction to Circle Packing. Cambridge Univ. Press.Google Scholar
24. Toledo, S., 2003. TAUCS, a library of sparse linear solvers. C library, http://www.tau.ac.il/~stoledo/taucs/.Google Scholar
25. Yang, Y.-L., Guo, R., Luo, F., Hu, S.-M., and Gu, X. D. 2009. Generalized discrete Ricci flow. Computer Graphics Forum 28, 7. to appear, Proc. Pacific Graphics.Google ScholarCross Ref
