Regular meshes

ABSTRACT

This paper presents our preliminary results on regular meshes in which all faces have the same size and all vertices have the same valence. A regular mesh is denoted by (n, m, g) where n is the number of the sides of faces, m is the valence of vertices and g is the genus of the mesh. For g = 0, regular meshes include regular platonic solids, all two sided polygons. For g = 1 regular meshes include regular tilings of infinite plane. Our work shows that there exist infinitely many regular meshes for g > 1. Moreover, we have constructive proofs that describe how to create high genus regular meshes that consist of triangles and quadrilaterals (3, m, g) and (4, m, g).

REFERENCES

• 1: Akleman, E., and Chen, J. 1999. Guaranteeing the 2-manifold property for meshes with doubly linked face list. International Journal of Shape Modeling 5, 2,149--177.
• 2: Akleman, E., and Srinivasan, V. November 2002. Honeycomb subdivision. In Proceedings of ISCIS'02, 17th International Symposium on Computer and Information Sciences, vol. 17, 137--141.
• 3: Semiregular Pentagonal Subdivisions, Proceedings of the Shape Modeling International 2004 (SMI'04), p.110-118, June 07-09, 2004 [doi>10.1109/SMI.2004.53]
• 4: Michael Barnsley, Fractals everywhere, Academic Press Professional, Inc., San Diego, CA, 1988
• 5: Bruce G. Baumgart, Winged edge polyhedron representation., Stanford University, Stanford, CA, 1972
• 6: Brahana, H. 1926. Regular maps on an anchor ring. Amer. J. Math 48, 4, 225--240.
• 7: Bulatov, V., 2005. Infinite regular polyhedra,. http://www.physics.orst.edu/bulatov/polyhedra/.
• 8: Catmull, E., and Clark, J. 1978. Recursively generated b-spline surfaces on arbitrary topological meshes. Computer Aided Design, 10, 350--355.
• 9: Johan Claes , Koen Beets , Frank Van Reeth, A Corner-Cutting Scheme for Hexagonal Subdivision Surfaces, Proceedings of the Shape Modeling International 2002 (SMI'02), p.13, May 17-22, 2002
• 10: Cohen, M., Shade, J., Hiller, S., and Deussen, O. 2003. Wang tiles for image and texture generation. In Proceedings of SIGGRAPH 2003, ACM Press/ ACM SIGGRAPH, Computer Graphics Proceedings, Annual Conference Series, ACM, 287--294.
• 11: Coxeter, H. S. M. 1937. Regular skew polyhedra in three and four dimensions. Proc. London Math. Soc. 43, 33--62.
• 12: Coxeter. 1965. Non-Euclidean Geometry. University Toronto Press.
• 13: Cromwell, P. 1997. Polyhedra. Cambridge University Press.
• 14: Doo, D., and Sabin, M. 1978. Behavior of recursive subdivision surfaces near extraordinary points. Computer Aided Design, 10, 356--360.
• 15: Dyn, N., Levin, D., and Simoens, J. 2002. Face-value subdivision schemes on triangulations by repeated averaging. In Curve and Surface Fitting: Saint-Malo 2002, 129--138.
• 16: Alexei A. Efros , William T. Freeman, Image quilting for texture synthesis and transfer, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.341-346, August 2001 [doi>10.1145/383259.383296]
• 17: Escher, M. C. 1994. The graphic works: introduced and explained by the artist (image plates 41 and 43). Barnes and Nobles Books, New York.
• 18: Helaman Ferguson , Alyn Rockwood , Jordan Cox, Topological design of sculptured surfaces, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.149-156, July 1992
• 19: Fomenko, A. T., and Kunii, T. L. 1997. Topological Modeling for Visualization. Springer-Verlag, New York.
• 20: Gott, J. R. I. 1967. Pseudopolyhedrons. American Mathematical Monthly 73, 497--504.
• 21: Green, M., 2005. Infinite polyhedra,. http://www.superliminal.com/geometry/infinite/infinite.htm.
• 22: Jonathan L. Gross , Thomas W. Tucker, Topological graph theory, Wiley-Interscience, New York, NY, 1987
• 23: Branko Grünbaum , G C Shephard, Tilings and patterns, W. H. Freeman & Co., New York, NY, 1986
• 24: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 25: Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 26: Leif Kobbelt, √3-subdivision, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.103-112, July 2000 [doi>10.1145/344779.344835]
• 27: Loop, C. 1987. Smooth Subdivision Surfaces Based on Triangles. Master's thesis, University of Utah.
• 28: Mandelbrot, B. 1980. The Fractal Geometry of Nature. W. H. Freeman and Co., New York.
• 29: M. Mantyla, Introduction to Solid Modeling, W. H. Freeman & Co., New York, NY, 1988
• 30: McMullan, P. Schulter, E., and Rota, G. 2002. Abstract Regular Polytops. Cambridge University Press.
• 31: Fabrice Neyret , Marie-Paule Cani, Pattern-based texturing revisited, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.235-242, July 1999 [doi>10.1145/311535.311561]
• 32: Peter Oswald , Peter Schröder, Composite primal/dual √3-subdivision schemes, Computer Aided Geometric Design, v.20 n.3, p.135-164, June 2003 [doi>10.1016/S0167-8396(03)00026-8]
• 33: Jörg Peters , Ulrich Reif, The simplest subdivision scheme for smoothing polyhedra, ACM Transactions on Graphics (TOG), v.16 n.4, p.420-431, Oct. 1997 [doi>10.1145/263834.263851]
• 34: Prautzsch, H., and Boehm, W., 2000. Chapter: Box splines. The Hanbook of Computer Aided Geometric Design.
• 35: Ringel, G., and Youngs, J. W. T. 1968. Solution of the heawood map-coloring problem. In Proc. Nat. Acad. Sci. USA Volume 60, 438--445.
• 36: Sabin, M., 2000. Subdivision: Tutorial notes. Shape Modeling International 2001, Tutorial, May.
• 37: Srinivasan, V., and Akleman, E. 2004. Connected and manifold sierpinski polyhedra. In Proceedings of solid Modeling and Applications, 261--266.
• 38: Stam, J., 1997. Aperiodic texture mapping. Technical Report R046.
• 39: Stewart, I. 1991. Game, Set and Math: Enigmas and Conundrums. Penguin Books, London.
• 40: Shigeo Takahashi , Yoshihisa Shinagawa , Tosiyasu L. Kunii, A feature-based approach for smooth surfaces, Proceedings of the fourth ACM symposium on Solid modeling and applications, p.97-110, May 14-16, 1997, Atlanta, Georgia, United States [doi>10.1145/267734.267760]
• 41: William Welch , Andrew Witkin, Free-form shape design using triangulated surfaces, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.247-256, July 1994 [doi>10.1145/192161.192216]
• 42: Wells, D. 1991. The Penguin Dictionary of Curious and Interesting Geometry. London: Penguin.
• 43: Williams, R. 1972. The Geometrical Foundation of Natural Structures. Dover Publications, Inc.
• 44: Zorin, D., and P. Schröder, E., 2000. Subdivision for modeling and animation,. ACM SIGGRAPH 2000 Course #23 Notes, July.
• 45: Zorin, D., and Schröder,. P., 2002. A unified framework for primal/dual quadrilateral subdivision schemes. Computer Aided Geometric Design, CAGD.