## How to program fast kaleidoscopes

This post repeats parts of earlier posts but I am trying to expand the ideas and explain them better. First, I am showing you how to make rosettes with rotational symmetry and mirror symmetry. This is easier than making kaleidoscopic images, but uses the same principles. Further, it is an important step in efficient programs for kaleidoscopes.

Let’s have two straight lines that intersect and divide the plane into four sectors. We use one of the sectors with an acute angle between the lines at its apex. This angle has to be a unit fraction of 180°; thus its value is 180°/k where k is an integer number greater than 1. We can then use mirror symmetries at the two lines to get a non-overlapping covering of the plane by images of this sector. This seems to be trivial as we can create a symmetric image by cutting out such a sector from an input image with scissors. We would then make copies of the sector and of its mirror image and glue these pieces together to cover the plane. Here is a typical result with green lines at the border of the sector cut out from the input image. Its copies are shown in bleached out colours: How do we program a computer to create such images efficiently? We have to find a colour value from an input image for each pixel depending on its position. Because the mirror symmetries make a non-overlapping covering of the plane by copies of the sector we can map the position of the pixel into this sector using these symmetries. We use this unique mapped position to read a colour from the input image which determines the colour of the pixel. Fortunately we do not need to find the detailed sequence of mirror symmetries as it is difficult to figure out. Instead we use that the two mirror symmetries generate a dihedral group which combines a k-fold rotational symmetry and k mirror axis. You can discover the elements of this group in the above picture.

We choose a coordinate system with its origin at the intersection of the two lines and an x-axis parallel to one of the mirror lines. Using polar coordinates (r,φ) for the position of a pixel, we have to map it into the sector with the same value for r and a new angle φ<180°/k. As a first step we use the k-fold rotational symmetry. The image is thus a periodic function of φ with a period length 2π/k and we can replace φ by its rest φ-2π/k*⌊φ/(2π/k)⌋. Then 0<φ<2π/k. Be careful, the modulo operation of some programming languages might result in something different for negative φ and you better use the universal floor function. The second step is a mirror image and it is only needed if φ>π/k. In this case we put φ->(2π/k)-φ. This gets us rapidly the mapped point in the small sector for any pixel without bothering about sequences of mirror symmetries.

A kaleidoscope uses a triangle. We get it with a third line that cuts across the sector that generated the rosette. Again the angles are unit fractions of 180°. Three numbers (k m n)  characterize the triangle. They are larger than 1 and the angles of the triangle are 180°/k, 180°/m and 180°/n. Such triangles are known as Möbius triangles, which are special cases of Schwarz triangles. The mirror symmetries of the two lines meeting at a corner make k, m or n-fold rotational symmetries in the same way as for a simple rosette. The three mirror symmetries at the three sides of such a triangle generate a larger triangle group. Applying these mirror symmetries on the triangle we get a non-overlapping covering of the plane.

The result differs strongly if the sum of the three angles (1/k+1/m+1/n)*180° is smaller, equal or larger than 180°. Our drawing plane is flat and has no curvature. Thus the sum of the angles of a triangle made of straight lines is equal to 180° and (1/k+1/m+1/n)=1. This equation has only three solutions. With the numbers (4 2 4) we get a triangle having two 45° angles and a right angle. As a kaleidoscope it makes a periodic image with two distinct 4-fold rotational symmetries and a two-fold rotational symmetry. Then (3 3 3) give an equilateral triangle and periodic kaleidoscopic images with three distinct centers of three-fold rotational symmetry. The last triangle results from (6 2 3) and has 30°, 60° and 90° angles. This kaleidoscope has periodic images with 2, 3 and 6-fold rotational symmetries. For some images of these kaleidoscopes see my earlier post “Geometry of kaleidoscopes with periodic images“. Again, we have to find for each pixel the related the unique point in the basic triangle resulting from the mirror symmetries. We only care about the result and use that the image is periodic. In a first step we map the position of the pixel into the periodic unit cell. Then, depending on the position in the unit cell we use some of the mirror symmetries to map the point into the basic triangle. Obviously, this is really fast and needs only a few simple steps. On the other hand, the periodic lengths and mirror symmetries are different for each kaleidoscope and we have to program a different mapping function for each kaleidoscope. This too is expensive and inconvenient.

Is it possible to make a single efficient mapping procedure that works for all three cases? To do this we treat the three mirror symmetries differently as shown in this image for a kaleidoscope with a (6 2 3) triangle: As for the rosette, two mirror lines (shown in green) make a dihedral symmetry group around their point of intersection. The third line (shown in red) of the triangle adds an extra mirror symmetry. The triangle cut off from the input image is shown in full colours and its copies are bleached out. To map any point into this triangle we use an iterative procedure of two steps as indicated in the figure by the blue dots and arrows. First, the dihedral symmetry maps the point into the sector between its two mirror lines. Then, if the point is still not inside the triangle we apply the mirror symmetry at the third line. These steps are repeated until the point goes inside the triangle. The example shown above used two iterations. You can see that each iteration reduces the distance between the point and the origin. Thus this iterative procedure should generally terminate and give a solution. It is very fast, versatile and easy to program. To be safe we have to limit the number of iterations used for mapping a point. The number of iterations needed for mapping a point into the triangle increases with its distance from the origin. Thus the maximum number of iterations determines the size of the resulting image and affects its border.

If the sum of the angles of the triangle is not 180° we can still use the same iterative procedure. Two sides of the triangle are still straight lines making up the dihedral symmetry and we only have to replace the third straight line by a circle. This makes it possible to have any angles of intersection between the straight lines and the circle because we are free to choose its radius and center.

We have to replace the mirror symmetry at the third line by an inversion at the circle. A circle of radius R with its center at position c inverts a point p into an image point q=c+(pc)*R²/|pc|². This inversion at a circle is very similar to a mirror symmetry. Very close to the circle the inversion gives the same results as a mirror symmetry at a tangent line. The inversion does not change local angles of intersection between lines. Actually, looking only at a small region the inverted image is similar to the original as only its orientation and size changes. At a larger scale inversion causes distortions and bends straight lines. These are important differences to mirror images that have the same size as the original and that leave straight lines intact.

We have to know that the inverted images of circles and lines are circles and lines too, but usually with a different radius. Only circles and straight lines that are perpendicular to the circle do not change upon inversion, as in this figure: The blue and red circles intersect at a right angle. An inversion of the disk bounded by the blue circle at the red circle yields again the same disk and every point outside this disk stays outside. The area of intersection between the two discs is shown in orange colour. Inversion maps it into the area inside the blue circle and outside the red circle, which is shown in green. This property of inversion is important for analyzing kaleidoscopic images.

If the sum of angles of the triangle is less than 180° we get an image with hyperbolic geometry. As an example let us look at the kaleidoscope resulting from the (5 2 4) triangle. It has 5, 2 and 4-fold rotational symmetry resulting from its angles of 36°, 90° and 36° with a sum of 171°. This is an example image: As before, the triangle cut out from an input image is shown in full colour and its copies are bleached out. The triangle has two straight lines as sides, shown in green. They generate a dihedral symmetry with five-fold rotational symmetry for the image. The third side of the triangle is a part of the circle shown in red. As mentioned above, we use the same iterative procedure as for triangles with three straight edges. Using the dihedral symmetry we map points outside the triangle into the sector containing the triangle. Note that the triangle lies outside the circle. Thus, if the point is inside the circle we invert the point at the red circle. If this does not map the point inside the triangle we repeat these mappings.

Using enough iterations, all points inside the blue circle are mapped into the triangle. The blue circle has its center at the intersection of the green lines and is perpendicular to the red circle. Inversion at the red circle does not map the points outside the blue circle into the blue circle. These points would thus never reach the triangle and they have to be disregarded. The image of this kaleidoscope fills only the inside of the blue circle. It is a decorated Poincaré disc model for hyperbolic space.

The number of iterations increases for points that are closer to the blue circle and becomes infinite at the circle. Thus we need to limit the number of iterations. If this limit is too small we would get a rough outer border for the image. But fortunately, only few pixels take a large number of iterations and we can use a very large limit, such that the border appears to be a smooth circle.

If the sum of angles of the triangle is less than 180° we get an image with elliptic geometry. As an example let us look at the kaleidoscope resulting from the (4 2 3) triangle. It has 4, 2 and 3-fold rotational symmetry resulting from its angles of 45°, 90° and 60° with a sum of 195°. This is an example image: This is very similar to the hyperbolic images discussed above, except that the red circle making up the third side of the triangle now contains the triangle itself. We can use the same iterative procedure as before but now we invert the point at the circle if the point lies outside the circle. This procedure maps every point into the triangle with only a few iterations. The resulting images are stereographic projections of decorated regular tilings of a sphere.

For more images of higher resolution have a look at my Flickr album “kaleidoscopic”.

This entry was posted in Anamorphosis, Kaleidoscopes, programming, Tilings and tagged , , , , . Bookmark the permalink.

This site uses Akismet to reduce spam. Learn how your comment data is processed.