Shape Metrics: A Unified Approach to Shape Inversions and Custom Distance Functions

Year: 2020 Authors: Risto A. Paju

Core claim

Shape inversion can be expressed as ordinary inversion in a metric defined by the shape itself, enabling simpler formulas and new non-inversion uses.

Topics

shape inversion, shape metrics, fractal art, Voronoi diagrams, 3D graphics

Domains

metric geometry, Euclidean and non-Euclidean distance, pseudo-metrics, high-dimensional geometry, mathematical art, fractal imagery, generative graphics, visual pattern design

Methods

distance-function reformulation, shape inversion, Voronoi coloring, ray marching

Media

lattice figures, cube and octahedron models, Voronoi diagrams, computer-generated images

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.

Bridges 2020 Conference Proceedings

Shape Metrics: A Unified Approach to Shape Inversions and Custom Distance Functions

Risto A. Paju http://algoristo.com/ Jyväskylä, Finland; risto.a.paju@iki.fi

Abstract

I present a new approach to shape inversions that provides both computational simplicity and an alternative, unified understanding of the inversion operation. Instead of modifying the circle inversion formula for different shapes, my method changes the metric from Euclidean to a shape-dependent one. As a by-product, I outline a technique to construct new metrics and pseudo-metrics from given shapes, and suggest various non-inversion applications.

(a) Iterated hexagon inversions of an infinite hexagonal lattice

(b) Iterated cube inversions of a central octahedron

Figure 1: Fractal art created with shape inversions using shape metrics

Shape Inversions with a Metric Interpretation

From Apollonius of Perga to today’s fractal programmers, circle inversion remains a fruitful tool for mathematical artists. The inversion of the point $\mathbf{p}=(x,y)\in {\mathbb{R}}^2$ by an origin-centred circle of radius $R$ is given by

where $d_E(0,\mathbf{p})=\sqrt{x^2+y^2}$ is the Euclidean distance from $0$ to $\mathbf{p}$. Gdawiec [3] generalized this to non-circular shapes by replacing the fixed radius $R$ with a varying distance $r_S(0,\mathbf{p})$:

Paju

Specifically, $r_S(0,\mathbf{p})$ is the Euclidean distance from $0$ to the shape-defining set $S$ along the ray from $0$ to $\mathbf{p}$ , i.e. $r_S(0,\mathbf{p})=d_E(0,\mathbf{q})$ in Figure 2. Note that for $r_S$ to be well-defined, $S$ must be a star-shaped set [3] with respect to $0$ : it must intersect the ray at exactly one point for each $\mathbf{p}$ .

Figure 2: Inversion in the square $S$

I was introduced to shape inversions by Gregg Helt [4] and proceeded with my own experiments, resulting in pictures such as Figure 1(a). In order to switch between circles and other shapes more easily, I rewrote (2) as

where

is the shape metric. This retains the original form of circle inversion (1), with the shape information now subsumed into the metric. For circles, $r_S(0,\mathbf{p})=R\Rightarrow d_S=d_E$ , so (3) reverts to (1) as a special case.

The advantages of this definition become clear when we notice that $d_S$ is a familiar metric for many common shapes besides circles. First, recall that the shape $S$ is defined by $r_S(0,\mathbf{p})=d_E(0,\mathbf{q})$ . Setting $\mathbf{p}=\mathbf{q}$ in (4) we then get $d_S(0,\mathbf{q})=R$ ; in other words, $S$ is a “circle” of the metric $d_S$ .

For the square $S$ in Figure 2, $d_S(0,(x,y))=\max (|x|,|y|)$ , the sup or max norm $\Vert \mathbf{p}{\Vert }_{\infty }$ , and $R=1$ . Using this with (3) is considerably simpler than finding $r_S(0,\mathbf{p})$ and computing $d_E(0,\mathbf{p})$ in (2). Moreover, it is conceptually satisfying that shape inversion be realized with the metric that defines the shape itself.

Further Examples with Known Metrics

This approach is readily extended to ${\mathbb{R}}^3$ and higher-dimensional spaces. Cube inversion would use $d_S(0,\mathbf{p})=\max (|x|,|y|,|z|)$ in analogy with the square. Other simple shapes of inversion include

• Octahedron with the Manhattan or Taxicab metric $d_S(0,\mathbf{p})=\Vert \mathbf{p}{\Vert }_1=|x|+|y|+|z|$
• Rounded square with $d_S(0,\mathbf{p})=\Vert \mathbf{p}{\Vert }_k=\sqrt[k]{|x{|}^k+|y{|}^k}$ where k > 2

Constructing Metrics and Pseudo-Metrics from Shapes

For inversion with a general shape $S$ and the associated $r_S(0,\mathbf{p})$ , my approach with (4) and (3) is needlessly complicated in comparison to (2). However, (4) provides a way to construct shape metrics for any application besides inversion. Note that these may not be metrics in the strict sense; see the ‘Caveats’ section for details.

Non-inversion Applications

Voronoi diagrams are colourings of the plane, based on a set of seed points. Each point on the plane is coloured according to its nearest seed. The “nearness” depends on the choice of the metric, so the style of a Voronoi diagram can be varied by using non-Euclidean distance functions. Figure 4(a) shows a Voronoi colouring with 32 seed points, using the pseudo-metric derived from the shape in Figure 3(a). The wavy nature of the shape metric is reflected in the shapes of the coloured partitions. For comparison, Figure 4(b) uses a metric mixed from Euclidean and Manhattan distances, namely $d_S(0,(x,y))=\frac{1}{2}\left(\sqrt{x^2+y^2}+(|x|+|y|)\right)$ , with the corresponding shape depicted in Figure 3(b).

Shape Metrics: A Unified Approach to Shape Inversions and Custom Distance

Functions

(a) $r_S(\varphi )=1+\frac{1}{5}\cos (5\varphi )$

(b) Mixed Euclidean+Manhattan circle

(c) $r_S(\varphi )=1+\frac{1}{3}\cos (4\varphi )$ Figure 3: Curved forms for constructing metrics and pseudo-metrics

Many graphics rendering techniques, such as ray tracing, rely on metrics due to their reverse nature. On a basic level, such algorithms comb over all points in the view, testing whether each point is in the desired set. For example, a sphere at the origin is generated by the test $d_E(0,\mathbf{p})\le R$ . Shape metrics provide an efficient solution to matching other shapes; the octahedron in Figure 1(b) is generated with the Manhattan metric.

Ray marching [2] is a variant of ray tracing that aims for faster rendering by skipping over empty areas. This requires an estimate of the Euclidean distance to the surface, which must not overshoot. In some cases, shape metrics can provide fast and safe estimates. For example, for a cube defined by $\Vert \mathbf{p}{\Vert }_{\infty }\le R$ , the distance from external points $\mathbf{q}$ to its surface is at least $\Vert \mathbf{q}{\Vert }_{\infty }-R$ . Other shape metrics may also be similarly applicable, possibly with a suitable scaling constant.

In 3D graphics, a realistic scene generally requires simulated lighting with surface reflections, which depend on the normal vectors of the surface. For a surface defined by a shape metric with $d_S(\mathbf{c},\mathbf{p})=R$ , the surface normal at $\mathbf{p}$ is simply given by the gradient $\nabla d_S(\mathbf{c},\mathbf{p})$ . In some cases, this can be made simpler by using a suitable power or other modification of $d_S$ , provided it maintains the surface equation $f(\mathbf{p})=\text{constant}$ .

(a) Voronoi diagram using the pseudo-metric from Figure 3(a) Figure 4: Applications of shape metrics

(b) Voronoi “giraffe” pattern Euclidean + Manhattan metric using (c) 1 Euro coin after a circle-to-square distortion

In Figure 1(b) I bring together a number of the techniques covered above: cube inversion with the max norm, octahedron shape matching and ray marching with the Manhattan metric, and lighting via surface

normals using the gradient of the metric. For the iteration with multiple inversion centres, I use optimizations adapted from Nakamura and Ahara [5].

Finally, for a bit of simple fun, smooth visual distortions can be realized with the shape metrics of the source and target shapes. For example, a disc-shaped picture can be transformed into a square with ${\mathbf{p}}^{\prime }=\frac{d_F(0,\mathbf{p})}{\max (|x|,|y|)}\mathbf{p}$ to produce results such as square coins (Figure 4(c)).

Alternative Definitions of Shape Metrics

Associating shapes with metrics is known in a number of disciplines. Perhaps the most famous example is Einstein’s general theory of relativity, an application of differential geometry where the metric tensor defines the shape of spacetime.

A closer example to the present definition is found in a study of geometric graphs by Bonato and Janssen [1]. They define $d_S(0,\mathbf{p})={\max }_i|{\mathbf{a}}_i\cdot \mathbf{p}|$ where ${\mathbf{a}}_i,i\in \{1,...,n\}$ are the $n$ distinct surface normals of $S$. This can be shown to be equivalent to (4) with a suitable normalization, at least for regular convex polygons.

Caveats

In general, shape metrics of arbitrary shapes will not fulfil the definition of a true metric, which includes the following two conditions:

1. Symmetry $d(\mathbf{a},\mathbf{b})=d(\mathbf{b},\mathbf{a})\to$ the shape must be centrosymmetric, i.e. $r_S(0,\mathbf{p})=r_S(0,-\mathbf{p})$.
2. Triangle inequality $d(\mathbf{a},\mathbf{b})+d(\mathbf{b},\mathbf{c})\ge d(\mathbf{a},\mathbf{c})\to$ the shape must be convex. Although I have not proved this, it can be argued intuitively with counterexamples. In Figure 3(c), $d_S(\mathbf{a},0)+d_S(0,\mathbf{b})=2$ as the points $\mathbf{a}$ and $\mathbf{b}$ are on the unit “circle” of $d_S$, while $d_S(\mathbf{a},\mathbf{b})=d_S(0,\mathbf{b}-\mathbf{a})=\sqrt{2}\cdot \frac{4}{3}/(1+\frac{1}{3}\cos \left(4\cdot -\frac{\pi }{4}\right))=2\sqrt{2}$.

However, for artistic purposes, such conditions can be relaxed. Figure 3(a) represents a shape whose distance function breaks both of the above conditions, yet it is artistically useful for the making of Figure 4(a). In this case the violations result in visual discontinuities. Some of the colour partitions in Figure 4(a) are broken into separate parts, which can be seen as the “exclaves” without seed points. In contrast, Figure 4(b) exemplifies that even a rather simple, proper metric can be used to create interesting Voronoi diagrams.

Acknowledgements

My inversion art has been greatly inspired by Gregg Helt and Kento Nakamura, while Noira Martiskainen has provided other invaluable contributions to my works. Finally, I would like to thank the reviewers for their helpful suggestions.

References

• [1] Anthony Bonato and Jeannette Janssen. Infinite random geometric graphs from the hexagonal metric. Combinatorial Algorithms: 23rd International Workshop, IWOCA 2012, 7643, 07 2012.
• [2] Mikael H Christensen. Distance estimated 3d fractals (part i). http://blog.hvidtfeldts.net/index.php/2011/06/distance-estimated-3d-fractals-part-i/ (as of Sept. 3, 2019).
• [3] Krzysztof Gdawiec. Star-shaped set inversion fractals. Fractals, 22:1450009, 12 2014.
• [4] Gregg Helt. Extending mandelbox fractals with shape inversions. In Proceedings of Bridges 2018, pages 547–550, Phoenix, Arizona, 2018. Tessellations Publishing.
• [5] Kento Nakamura and Kazushi Ahara. A new algorithm for rendering kissing schottky groups. In Proceedings of Bridges 2016, pages 367–370, Phoenix, Arizona, 2016. Tessellations Publishing.