Large, Symmetric, “7-Around” Hyperbolic Disks

Year: 2015 Authors: Sean Jeng Liu; Young Kim; Raymond Shiau; Carlo H. Séquin

Core claim

A D3-symmetric construction and heuristics allow larger 7-around hyperbolic disk models than prior search-based methods.

Topics

hyperbolic geometry, symmetry, computational modeling, triangle packing

Domains

non-Euclidean geometry, hyperbolic plane, combinatorial geometry, symmetry groups, digital fabrication, mathematical visualization, 3D modeling, generative design

Methods

symmetry reduction, heuristic search, manual construction, proximity checking

Media

equilateral triangles, virtual CAD model, 3-space rendering, animated movie

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Proceedings of Bridges 2015: Mathematics, Music, Art, Architecture, Culture

Large, Symmetric, “7-Around” Hyperbolic Disks

Sean Jeng Liu, Young Kim, Raymond Shiau, Carlo H. Séquin EECS, Computer Science, University of California, Berkeley

Abstract

Maximal symmetry is used to reduce the computational complexity in the construction of the largest possible hyperbolic disk composed entirely of equilateral triangles meeting seven per vertex.

Modeling Hyperbolic Disks

Mathematicians as well as artists are fascinated by the hyperbolic plane. Hilbert proved that the infinite hyperbolic plane cannot be smoothly and isometrically embedded (without self-intersections) in 3-space. Artists have made approximate models of a finite portion of the hyperbolic plane from various materials, for instance by crocheting (Fig.1a) or by gluing together paper triangles (Fig.1b). They may start with a small hyperbolic patch (warped like a potato chip) placed at the origin, and then add consecutive annular ribbons around the perimeter. With each annulus the distance from the origin grows only linearly, but the length of the annular ribbon grows exponentially; thus the outer border becomes ever more convoluted, and needs to curl through space in ever tighter undulations. Soon the physical properties of the modeling material will reach some practical limit of packing density, and a uniform radial extension of such a hyperbolic disk is no longer possible.

Figure 1: Hyperbolic disks: (a) crochet model by G. Meyer [3], (b) paper model by D. A. Richter [4], (c) virtual CAD model by M. Howison [1].

Alternatively, one may try to generate procedurally an approximate virtual model of a much larger hyperbolic disk. Because the geometrical surface is infinitely thin, layers of the curlicue undulations of the outer annuli might be stacked much more densely on top of one another. To make this an interesting and fair competition, some constraint must be imposed. In the current effort we are trying to construct a large hyperbolic disk from all equilateral triangles with unit edge-length – always packing exactly seven such triangles around each vertex. In order to prevent us from creating a trivial solution by running arbitrarily long strips of triangles off to infinity, we will always complete a full annular ribbon before proceeding radially outwards to construct the next annulus. The challenge then is to try to complete as many annuli as possible without encountering any self-intersections. We also disallow dihedral bends of $180^{\circ }$ at the edge between two triangles – which would put them flush on top of one another.

Liu et al.

In 2007 Mark Howison wrote such a program as a course project [1] in a graduate course on solid modeling (CS285). But that program quickly hit a barrier, where an annular ribbon is prevented from growing any further, since it always produces some self-intersections. The left shaded portion of Table 1 shows the exponential growth rate of the number of triangles in consecutive rings, when we first start with a single vertex surrounded by seven equilateral triangles. Howison’s program maxed out at 810 triangles - it never was able to complete the $4^{\text{th}}$ ring (blue); his best result, obtained after a run-time of several hours, is shown in Figure 1c. The program was quite sophisticated and used simulated annealing to explore the combinatorial space of possible angular configurations between triangles as they are added to the surface. Nevertheless, eventually the spatial crowding became so intense, that the program spent most of its time backtracking, trying to undo a bad configuration that preserves no space for new triangles and to establish a looser, more promising configuration. At 810 triangles, the search tree is very deep, and the number of possible branches to be explored becomes astronomical.

Table 1: Growth of hyperbolic disks made from equilateral triangles, clustered 7-around each vertex.

Figure 2: The core of a symmetrical hyperbolic disk: (a) shown in the Poincaré disk, and (b) rendered perspectively in 3-space.

Introducing Symmetry

Our novel idea is to construct a hyperbolic disk that is as symmetrical as possible. If the disk exhibits $n$ -fold symmetry, then only $1/n^{\text{th}}$ of it has to be constructed, and the whole disk is obtained by instantiating

the constructed segment n times. Maximal symmetry can be obtained by starting with a single triangle in the xy-plane, symmetrically straddling the origin. By enforcing the D_{3}-symmetry found in this triangle, we need to construct the sought-after hyperbolic surface in only one wedge of space comprising an angle of 60°. The central core of the disk is almost fully determined by the symmetry constraints: The three triangles surrounding the central triangle must also lie in the xy-plane. The two triangles (gold and olive) sharing vertex #1 (Fig.2a) each have an edge lying on a symmetry axis and must therefore be coplanar. The tilt against the xy-plane is determined by the condition that the two triangles (olive and green) sharing vertex #2 must form a symmetrical “gabled roof” above a right-angled wedge in the xy-plane; thus there are just two mirror solutions. Placing this “gabled roof” six times around the z-axis with D_{3}-symmetry completes ring #1 of this new configuration. The growth rate and the number of triangles in subsequent annuli for this new, symmetrical scheme are shown in the right shaded portion of Table 1.

We could now use this 16-triangle “core” as a starting base and let a random search algorithm similar to Howison’s program calculate the next annulus sector, which would have as an outer border the vertex chain from #3 through #8. However, since there are still a substantial number of constraints in this ribbon domain, we decided to also complete this swath by hand. The two triangles (blue and teal) sharing vertex #3 also share an edge on a symmetry axis and thus must be coplanar; and there are again just two possible solutions for the position of vertex #4. We choose to give vertex #4 the same sign for its z-coordinate as for vertex #2; this produces a nice tall arch in the z-direction with ample room for the next annular ring to undulate around this looping border.

We make some further arbitrary decisions to complete this swath inside the vertex chain #3 through #8. First we choose the tilt around the C_{2} symmetry axis for the (red/magenta) double triangle attached to vertex #1 so that it becomes coplanar with the (gold/olive) double triangle inside vertex #1. This particular choice leaves a 90° open angle in this shared tilted plane; this can again be spanned by a “gabled roof,” which we choose to angle upwards. Finally we fill in three more triangles around vertex #2 (yellow/cyan/yellow) by letting them form an upward-pointing arch in the shape of a symmetrical 3-panel “Mansard roof.” The result of these constructions, replicated six times around the origin, can be seen in Figure 2b. We always start from this fixed symmetrical “core” when we try to construct larger hyperbolic disks.

Triangle Placement Heuristics

Triangles are added to the disk individually or in pairs along the current open border forming a new annular ribbon. Individual triangles connect to that border with just a single edge, and thus there is a degree of freedom concerning the dihedral angle at the junction. We want to avoid forming acute dihedral angles, because they may make it difficult to place triangles in that region in the subsequent annulus; thus we choose a dihedral angle from a flat distribution (this seems to work better than a Gaussian distribution) in an interval that spreads δ = ±60 degrees around a coplanar extension. Along the border, one vertex at a time, we complete the fan of seven triangles around every vertex. The last two triangles in each 7-element fan have to be placed as a pair, since they need to close up seamlessly with the first triangle in the fan; they form a “gabled roof” (Fig. 2b, top) in the remaining angular space around the current vertex, and there is the binary choice of angling the roof upwards or downwards.

For each triangle that we place, we must check that it does not intersect any other triangles. But just checking for current intersections is too shortsighted; near-misses will definitely cause problems in the next outer annulus. Thus we do a more conservative proximity check, measuring the overlap of the circumsphere of the new triangle against the circumspheres of all other triangles in the neighborhood. If the distance of the centers of these spheres falls below a certain threshold, we try a series of different dihedral angles, and if they all fail, we backtrack and reposition the previous triangle. More details about the various heuristics employed can be found in the Appendix of the electronic, extended and updated version of the paper [2].

Liu et al.

Results

With the above heuristics in place, we now can let the program run many times to complete successive swathes in a $60^{\circ }$ sector around the core’s border. We visually inspect the results for a particular swath, and among several possible solutions pick the one that we think will form the most beneficial border for the subsequent swath. Such a good solution can then be “frozen” and added to an extended starting core. With this approach we have constructed good solutions for swaths #1 and #2. By June 4, working from both ends of swath #3, we were able to place up to 103 triangles into the subsequent annulus with typical run times of just a few minutes. This result is shown in Figure 3a using the following color coding: the central starting triangle is white, the manually constructed core of 60 triangles around it is dark red, swath #1 is light green, swath #2 is dark blue, and the triangles in the outermost ring are magenta-colored. After instantiating the constructed sector six times, we then had a total of 1111 triangles in our hyperbolic disk. Figure 3b shows the full disk geometry with randomized coloring of the triangles. On June 9, we were able, for the first time, to successfully complete swath #3 for a total of 1321 triangles. These results can be seen in the electronic version of the proceedings, including a brief dynamic file “clip-1321-compressed.mov” that conveys a better 3D understanding of this geometry.

Our program is still in the “fine-tuning” phase, where we try to find the best values for the parameters in our various heuristic subroutines. Of course, we will continue our efforts through the summer and will report the best results obtained at the time of the conference and in an on-line report [2].

Figure 3: Best result to-date: (a) core_61 plus one $60^{\circ }$ sector, (b) fully assembled disk.

References

[1] M. Howison, Constructing Models of the Seven-Around Surface. Final Report for CS 285: Solid Modeling — http://www.cs.berkeley.edu/~sequin/CS285/2007_REPORTS/Howison_7-around.pdf (April 2015). [2] S. J. Liu, Y. Kim, R. Shiau, C. H. Séquin, Large, Symmetric, “7-Around” Hyperbolic Disks. Extended and updated version of this paper. — http://www.cs.berkeley.edu/~sequin/PAPERS/2015_Bridges_7-around-ext.pdf [3] G. Meyer, Hyperbolic Disk with Red Rim. — http://gallery.bridgesmathart.org/exhibitions/2014-joint-mathematics-meetings/gabriele_meyer (April 2015). [4] D. Richter, A paper model of the seven-around surface. — http://homepages.wmich.edu/~drichter/hyperbolicimbed.htm (April 2015). [5] T. Möller, A Fast Triangle-Triangle Intersection Test. Journal of Graphics Tools, A.K.Peters, Vol.2, Issue 2, (1997), pp 25-30.