A Transversion-Based Machine for Curvature

Fundamental Forms

One of the key properties of a manifold is its curvature.  For simple shapes such a sphere or a plane, curvature is constant, but for the most part it is a function dependent on position in the manifold.  Surfaces in 3D Euclidean space are 2-manifolds that can be overlaid with a 2D coordinate system.

The specific form of a surface is determined by instantaneous curvature at every point.  There are several different parallel concepts that fall under the term curvature, but usually what is referred to is the extrinsic curvature of a manifold as opposed to its intrinsic curvature.  Extrinsic curvature refers to the curvature of a manifold as it exists in an embedding space while intrinsic curvature refers to the inherent curvature of a manifold independent of any embedding space.

Surfaces have both intrinsic and extrinsic curvature unlike curves, which only have extrinsic curvature.  Thus, the particular shape of a surface in an embedding space can vary without changing its intrinsic curvature, so when constructing surfaces in 3D space, we need a measure of the properties of a surface that relates the extrinsic and intrinsic properties to each other.  In differential geometry, there are two important constructs that largely characterize the extrinsic and intrinsic properties of a surface: the first fundamental form and the second fundamental form.

The first fundamental form measures intrinsic properties through the inner product of the local tangent space.  At each point along a surface, there is a plane tangent to that point, which can be defined by the normal at that point.  This plane has two independent directions that can be thought of as 2D vectors in the tangent plane.  How these vectors relate to each other is precisely what the first fundamental form is measuring.  The inner (or dot) product simply measures how orthogonal the vectors are to each other and what their relative scale is.  The first fundamental form is thus a 2×2 matrix correlating the vectors to each other.

If a surface is given by \(X(u, v)\) where \(u\) and \(v\) are the parameterizing coordinates of the surface, then the first fundamental form can be calculated from the first derivatives of these coordinates \(X{_u}, X{_v}\).

\(I = \left[ \begin{array}{ rc c } E & F \\ F & G \end{array} \right] \)

where \(E = X{_u}\cdot{}X{_u}, F= X{_u}\cdot{}X{_v}, G= X{_v}\cdot{}X{_v}\).

The first fundamental form is often referred to as the metric tensor of the surface as it can be used to calculate arc lengths and areas at points along the surface.  The second fundamental form by contrast is also referred to as the shape tensor.  It describes how the extrinsic properties of a surface relate to its intrinsic properties.  It’s a quadratic form in the tangent space and can be calculated from the second derivatives of the surface coordinates and the normal to the surface.  Again, it’s a 2×2 matrix of the form

\(II = \left[ \begin{array}{ rc c } L & M \\ M & N \end{array} \right] \)

where \(M = X{_{uu}}\cdot{}\vec{n}, N = X{_{uv}}\cdot{}\vec{n}, M = X{_{vv}}\cdot{}\vec{n}\) and \(n = X{_u}\wedge{}X{_v}/|X{_u}\wedge{}X{_v}|\).

Taken with the first fundamental form, the second fundamental form defines the curvature of the surface and the shape operator from which the surface can be constructed.  Thus given these two matrices for every point on a surface, the surface itself can be reconstructed.

The Transversion Machine

Given what we know about differential geometry and how various properties of the surface at each point relate to its specific structure, the question now posed is are two-fold: What is the minimal information required to reconstruct a particular surface? and What kinds of structure can we setup to generate this information as intuitively as possible that will enable use to modulate and transform a given surface in new and interesting ways?

For the first question, it’s clear that somehow we need to construct a generator that enables the calculation of the first and second fundamental forms without much computational complexity either explicitly or implicitly.  In addition, the generator should be coordinate free, that is it should not refer directly to coordinates in space but instead according to local, differential structures.  As has been mentioned in previous posts, the best tools for coordinate free geometric calculations are geometric algebra and the related geometric calculus.

The Tangent Plane

For the first fundamental form, the representation is geometric algebra is straightforward.  It’s constructed form the first derivatives over the surface in the principal directions, forming a tangent plane to the surface as well as the normal vector.  In geometric algebra we can represent this construct with a bivector made up of the outer product of two vectors.  In 3D Euclidean space, the dual of the bivector gives the normal as well.

The Osculating Spheres

The second fundamental form is a bit trickier to represent.  First, its geometric meaning needs to be properly expressed.  What the second fundamental form essential describes is how far a nearby point is from the tangent plane along the vertical distance.

If a point (x+dx, x+dy) is a distance D form the tangent plane, then D is given by \(D^2 = Ldx^2 + Mdxdy + Ndy^2\) where L, M, and N are the second fundamental form coefficients.

So the question now is how to relate the way the surface curves away from the tangent plane to some kind of relation in geometric algebra to the tangent plane we’re using to represent the first fundamental form.  Essentially, what we’re after here is a way to ascribe the curvature of the surface to a geometric entity.  When working with plane curves, the curvature of the surface is inversely related to the radius of a circle tangent to the surface at that point.  This circle is called the osculating circle.  Similar to how a tangent vector describes a differential movement along a curve, an osculating circle describes a differential curvature.  For surfaces, the same property is given by an osculating sphere where the radius of the sphere is inversely related to the curvature at a given point.

From our observations about the relationship between curvature and the osculating sphere, we should be able to use a sphere to represent the second fundamental form, but there’s still an open question about how to use it to calculate where exactly the surface will curve to efficiently and an equally tricky issue related to how to handle positive, negative and zero curvature cases.

For both problems, we can find a solution in the 5D conformal model of geometric algebra.  In this model, objects in geometric algebra can be reflected (inverted) in a sphere by treating the sphere as a versor.  If we place a sphere of a certain radius tangent to our tangent plane and reflect it into the sphere, the tangent vectors will be precisely where the curvature described by the radius of the sphere places them.  In other words, given an osculating sphere, the tangent plane can simply be inverted in it to warp it onto the surface described by the first and second fundamental forms.

While spherical inversion is a discrete operation, spherical transversion is a continuous operation that generates loxodromic motions.  The transversion operation is also known as the special conformal transformation.  When properly defined, the transversion operator can smoothly interpolate a sphere through an infinite radius (i.e. a plane) to a sphere of equal radius tangent to it but reflected over the plane generated when its radius was taken to infinity.  

In the picture above, the blue circle represents the transversing sphere while the black circle is the transversed sphere.  Its trajectory is plotted by the red circles until it reaches infinite radius (the grey line) and finally by the green circles as it returns back to the original radius but reflected over the grey line.  The transformation in this case is defined by a unit dual sphere at the origin along with a translation in the horizontal direction.  For a smooth transformation, the translation’s magnitude is such that it takes 20 steps for the black circle to become the final inner green circle.  The general transversion operation is given by \(V = STS^{-1}\) where S is a dual sphere and T a translation.  In the above case, \(S = o  - \frac{1}{2}\infty\) and \(T = e^{-\frac{e_1\wedge{}\infty}{2*20}}\).

In the general case, the transversing sphere and the transversed sphere can be of any radius with the constraint that the center of the transversing sphere is tangent to the transversed sphere.  Additionally, the direction of translation must be along the line from the center of the transversed sphere to the center of the transversing sphere.  When the radii of the two sphere changes, so does the rate at which the sphere is transversed.  The scaling factor relating the radii of the two sphere is \(\frac{(R_1)^2}{R_2}\) where \(R_1\) is the radius of the transversing sphere and \(R_2\) is the radius of the transversed sphere.  To compare, the image below has \(R_1 = 2\) and \(R_2 = \frac{1}{2}\).

In the image above, we can think of the grey line as the tangent plane and the red and green circles as representing the possible osculating spheres of different radii.  For curves, when the curvature is positive, the osculating circle is to one side of the curve.  When it’s negative, it’s on the other.  The same principle applies to surfaces and the osculating sphere.  Thus, we can say that the red and green circles represent osculating spheres related to positive and negative curvatures respectively and since the transversion operation smoothly interpolates from one to the other through the plane of zero curvature, we can smoothly vary the osculating sphere over the surface by defining a differential transversion operation that continuously varies the spheres from one point on the surface to the next.

Operating the Machine

Given the osculating spheres and the tangent plane as described above, the transversion machine is nearly complete, but there remain a few details to work out.  First, each independent direction over the surface has its own rate of curvature and thus its own osculating sphere.  Second, the operation of the machine is as follows:

  1. Reflect the principal vectors defining the tangent plane are inverted into their corresponding osculating spheres.
  2. A transformation for each  inversion is constructed such that the osculating spheres are rotated and translated to be tangent to the location where the tangent vectors were inverted.
  3. The radius of curvature of each osculating sphere is updated
  4. Repeat from step 1.

It’s important to note that at step 2, there are two movements: one in the u direction and one in the v direction where u and v are the principle directions.  Thus, at each point the machine can be thought of as being duplicated and moved in different directions to form the surface.  Once the surface is closed, the machine stops.

Defining the Parameters of the Machine

Given the transversion machine, there is a question of how to drive it.  The parameters defining the continuous changes in the radii of curvature of the two osculating spheres needs to be defined somehow.  This is where the constraints needed to generate a closed surface are applied and will be the topic of another post.  Essentially, it’s a problem of going from a topology where the curvature parameters are given at the vertices and smoothly interpolating those values over the faces such that a closed surface results.

Posted in Space and Geometry | Tagged , , , | Leave a comment

From Rigid Body Motions to Surfaces: Experiment 1

As mentioned in pervious posts, I’ve been exploring how Geometric Algebra (GA) can be used to generate a surface from a topology.  More specifically, I’m interested in how a pentagonal (5, 4) tiling of the hyperbolic plane can be procedurally transformed into a unique surface embedded in 3D Euclidean space.

The problem is a problem of differential geometry and how to compactly describe how a surfaces evolves according to local curvature.  In other words, I’m wondering if there a quantity that can be placed at the faces, edges, and vertices of the hyperbolic tiling that can then be interpolated across the tiling to give a particular surface and how such a quantity might be defined with minimal information by leveraging the constraints of the hyperbolic tiling and the topology defined by how the tiles are connected.

Hypothesis

Going off the idea that pairs of lines define a the square of a versor transforming one line into the other, I wondered if I could use pairs of lines associated with each edge of the dual graph of the tiling to generate the surfaces.  The motivation for using the dual graph is that the faces become quadrilaterals, which are simpler to interpolate across than pentagons.  If, from the line pairs, I can generate the way a space frame transforms across the quadrilateral edges, I should be able to produce the surface of each quadrilateral and glue them together to create the 2-manifold surface.

The Dual Graph

As a test example, I’m using a torus, which has 4 faces and 6 vertices in the pentagonal tiling.  The dual of the torus has 6 faces and 4 vertices.  For any structure representing a surface with faces, edges, and vertices, the dual of that structure exchanges faces and vertices and edges for their bisectors.

In the above images, the faces are the red dots, vertices are black.  The pink lines are the edges of the faces while the blue lines are the dual edges.  Thus the blue lines mark out the quadrilaterals centered about the dual faces (vertices).

In this particular example, there are 2 degenerate cases where the quadrilateral consists of 2 copies of the same pair of edges.  The dual faces to the far left and far right are both quadrilaterals are double covered because if you trace from one dual vertex to the next and then to the second, you end up at the first.  The third and fourth edges repeat this cycle, completing the double cover.  It’s not easy to see that it’s double covered in the surface view since the edges exactly coincide, but in the hyperbolic tiling view, it’s easy to see that the dual cycle occurs from circulating around a vertex where the pattern of faces encountered has a period of 2.

This degeneracy is described by vertex 3 having a cone angle of 180 degrees since it only takes a 180 degree rotation to go from face 1 to face 3 and back to face 1.  It’s called a cone angle since when a cone is flattened into a plane, the angle made at the apex of the cone is less than 360 degrees.

Constructing the Surface Panels

Keeping in mind the degenerate cases, the basic idea here is to calculate how a space frame transforms across the dual graph edges and use that information of fill in the panels themselves.  Here a space frame is simply the normal, tangent, and bitangent vectors on the surface making up a local coordinate frame.  The way the space frames transform across the surface uniquely determines its form.  To generate the transformations, we can apply versors generated by pairs of lines.

When generating versors from lines, the result is a mixture of translational and rotational components depending on how the lines relate to each other.  If 2 lines intersect, their point of intersection will be the point about which the rotation described by their versor operates.  If they don’t intersect, the vector between their closest points gives the translation.

To generate the surface, all that needs to be done is specify pairs of lines for each dual edge.  Most of the curves are quite trivial since they only involve a rotational component.  For example, the edge along the top of the torus can be generated by lines lying in the XZ-plane intersecting at (0, r, 0) where r is the minor radius.

The tricky part comes when both a rotational and translation component are involved.  To generate the transformations for the degenerate dual faces, the space frame needs to rotate 90 degrees in the XY-plane and 45 degrees in the XZ-plane with a translation component thrown in.

Of course, it’s trivial to do with with two separate versors, but with a single versor, it doesn’t quite work out.  The problem is that the translational component is partially in the plane of rotation.  As a result the transformation cannot be described by ratios of lines.  To see this, imagine trying to define a translational versor as seen above.  Notice how the lines are parallel.  Now imagine trying to generate the exact same motion but with lines pointing in the direction of the motion.  It’s impossible because the line translated along its direction is the exact same line.  A line extends to infinity in both directions, so it can’t be translated along this path.  If two lines define a rotation, that rotation has a plane and if we also need to define a rotation in that plane, then we’re out of luck because the nature of the lines won’t accomodate it since the translation will at least partially be in the invariant direction defined by the lines.

Conclusion

I puzzled over how to generate the above transformation with a single versor for a long time before I realized what the problem was.  It seems that lines are not good candidates for what I’m trying to do in the end despite their usefulness in describing rigid body motions.  Instead, I need another primitive tool that can more properly describe the differential geometry quantities involved, namely curvature.  This will be investigated in the next experiment.

Posted in Computational Technique, Space and Geometry | Tagged , , | Leave a comment

Rigid Body Motion

Rigid body motions are the set of motions preserving the distance between points on a body, which means they don’t account for any kind of elastic or relativistic deformations.  All rigid body motions can be described by a combination of translations and rotations, forming a group of transformations called the Special Euclidean group SE(n).  In mechanics and robotics, much of the theory of rigid body motions falls under Screw Theory, which describes rigid body motions by a rotation and a translation along the axis of rotation.

In computer graphics, rigid body transformations are typically represented by a 4×4 matrix representing the 3D rotation as a 3×3 matrix and the translation as the 4th column vector.  Often, quaternions are used to represent and generate the 3×3 rotation sub-matrix because they have better algebraic properties and don’t suffer from gimbal lock, however quaternions do not represent the full SE(n) group since they don’t incorporate translations into their algebra.  Interestingly, quaternions are an element in Geometric Algebra (GA), so we might ask what modifications to the quaternions might be required to create an object that can represent both rotations and translations.

Rotors and Quaternions

In GA, the geometric elements are both objects and operators.  For example, in Euclidean space vectors represent both a familiar vector object as well as a reflection operation.  Given a vector v and an object a, the operation \(vav^{-1}\) will reflect a through v.  Where the multiplication operation between elements is understood to be the geometric product.

If we add a second vector w to the mix, we can produce rotations since rotations are nothing more than double reflections \(vwaw^{-1}v^{-1}\).  In the rotation diagram, the blue line is the same as the second pink line in the reflection diagram, while the second pink line is the reflection of the blue line though the additional black line.  Notice how the angle between the two pink lines is twice that of the angle between the black lines.

We now observe that this last operation defined by the geometric product of 2 vectors performs the exact same operation as a quaternion: it rotates objects.  In fact, this is precisely what a quaternion is.  The only caveat is that quaternions are usually defined in terms of left-handed coordinates while the product of 2 vectors is in right-handed coordinates.  In GA, the product of 2 vectors is known as a rotor in this specific case and a versor in the general case.  A versor is simple the geometric product of set of vectors.

Like complex numbers, a rotor can be written in exponential form and once something is in exponential form, it’s trivial to interpolate it.  Complex numbers can be expressed as \(a+{i}b = re^{{i}\Theta}\).  Rotors can be expressed as \(R=e^{-B\phi/2} = cos(\phi) + B sin(\phi).\) Interpolating in this instance requires finding the differential rotor dR such that given two rotors R1 and R2, we can apply the differential rotor N times to R1 and arrive at R2, giving N-1 intermediary poses between R1 and R2.  Finding the differential rotor thus boils down to finding the Nth root of \(R{_2}/R{_1} = e^{-(B{_1}\phi{_1}-B{_2}\phi{_2})/2}\).  The Nth root of any function \(f(x) = e^{g(x)}\) satisfies \(\sqrt[n]{f(x)} = e^{g(x)/n}\) since \( (e^{g(x)/n})^n = e^{g(x)}\).  The reason we want the Nth root is that we’re multiplying by the differential N times, so the value we multiply by is the Nth root of the differential.

Rotations and Translations

While the 3D Euclidean model doesn’t combine translations with rotations into a single versor, there are a number of GA models that do.  How might this happen?  Rotations move an object about an axis.  If we plot out the movement of an object while applying a succession of incremental rotations, the object will mark out a circle.  This is due to the planar nature of rotations in 3D where the axis of rotation defines the plane of rotation.  If instead of rotation around a finite circle, we choose a circle of infinite radius, the circle transforms into a line at the limit.  Thus, translations can be thought of a simply a special case of rotations where the plane of rotation defines a circular path of infinite radius.  The question now is how to express such object incorporating infinity.

In the conformal model of GA, 2 extra dimensions are added to the usual 3.  These extra dimensions are the origin \(o\) and the point at infinity \(\infty\).  I won’t go into the details about the derivation of the conformal model, but will mention a few properties:

  • Distance between elements is expressed through the inner product
  • The point at infinity is left invariant by all Euclidean transformations
  • In addition to vectors, planes, etc. there are circles, spheres, and other objects
  • Directions are expressed as bivectors with the infinite point e.g. \(e_{1}\wedge\infty\)

With translations and rotations incorporated into the model, we can now express versors that both translate and rotate.  Translations in the conformal model are given by \(T = e^{-\boldsymbol{t}/(2\infty)}\) where t is a point describing the amount of translation.  To create a combined translation-rotation versor, all that needs to be done is multiply T by R \(V=TR\) with one major caveat: T must be along the axis of rotation for it to be commutative and thus for the sandwich product \(VxV^{-1}\) to work properly.  For an arbitrary translation, t must first be decomposed into a vector along the screw axis (axis of rotation) and a vector in the rotation plane.  There’s an excellent paper entitled The Representation of Rigid Body Motions in the Conformal Model of Geometric Algebra by Leo Dorst for further details.

In the end, it can be shown that a rigid body motion (rotation and translation) is fully described lines in the conformal model.  Intuitively, we know that two points define a line and thus a position in space and a direction.  We can imagine, then, that the position in space is the translation versor and the direction the rotation versor.  If we then define a second line, the operation of transforming the first line into the second line will incorporate a translation and rotation.  In fact, the ratio of two lines describes the squared versor representing such an operation.  To get the actual versor, we have to take the square root.  The square root can also be performed via logarithms such that given lines L1 and L2 \(V = \sqrt{L2/L1} = e^{log(L2/L1)/2}\).

The above rigid body pose interpolations are generated by the following bivectors where the x-axis is Red, the y-axis is Green, and the z-axis is Blue:

  1. \(e1\wedge{}e2\pi – e3\wedge{}\infty\)
  2. \(e1\wedge{}e3\pi – e3\wedge{}\infty\)
  3. \(e2\wedge{}e3\pi – e3\wedge{}\infty\)
Posted in Computational Technique, Space and Geometry | Leave a comment

LuaAV3: OSX Binary Release

We finally officially released the latest version of LuaAV after a lot of work this past fall.  This release has been all about making things more consistent and simpler in terms of naming and making the audio system more robust and flexible.  LuaAV now includes LLVM 2.8, which can JIT compile even the most complicated C++ code.  As a result, the audio system was rebuilt around the Gamma audio synthesis library, giving us a lot of DSP functions without much effort.

We have also worked hard on a documentation system for generating reference pages to make LuaAV easier to learn and use.  The documentation system can parse out annotations from both Lua and C/C++ source files in order to generate reference pages for the entire LuaAV ecosystem.  The documentation generating code is essentially a re-written LuaDoc with a simpler and more flexible interface.

What’s Next?

With the latest release, LuaAV is becoming both more stable and simpler to use.  We still have a fair amount of work to do to bring the Linux version to parity with the OSX version, however.  The next release of LuaAV will focus more on expanding the audio system to spatial audio and frequency domain processing and extending the space module with the Bullet Physics for better dynamics integration and spatial partitioning as well as the possibility of adding constraints.  Other improvements will include making the VideoRecorder functional, potentially some new geometry processing modules I’ve been kicking around and probably many other surprises!

Posted in Software Engineering | Leave a comment

The Algebra of Space and the Emergence of Structure

The Construction of Space

When we think about space, particularly in a computational setting, we usually deal with matrices (linear algebra) and vectors where the matrices represent transformations and the vectors are frequently a conflation of direction and location.  Even in the typical mathematics education and much of the literature, we very rarely encounter ideas about how to move up and down dimensions and between different spaces be they spherical, Euclidean, hyperbolic, projective, affine, or even conformal. The structure of space is incredibly rich, but to understand it, you have to undo in your mind what you think you know about space, shedding years and years of intuition to replace it with a proper algebraic conceptualization of space, namely Geometric (Clifford) Algebra.

Geometric Algebra (GA) is simply the geometric interpretation of Clifford Algebra.  They two terms can be interchanged freely.  GA is a geometric extension of the real number system to provide a complete description of direction and magnitude. GA starts with the concept of a k-blade where k is the dimensionality of space a quantity exists in.  For example, a 1-blade is a vector and a 2-blade is a plane.  The number ‘k’ in k-blade is called the grade.

GA Basics

The fundamental operation in GA is called the geometric product.  The geometric product relates blades of different grades to each other, providing algebraic relationships between the different spaces they represent.  The geometric product itself can be broken down into two other products: the inner product and the outer product.  The inner product is a grade-lowering operation while the outer product is a grade-raising operation.  In other words, these two products can be used to move up and down different dimensions of space.  The inner product can be thought of as a generalization of the familiar dot product in vector math.  The outer product can be similarly thought of as a generalization of the cross product.

Learning GA

The basis for GA is straightforward, but it can quickly feel overwhelming at first because of all of the unfamiliar terminology and the very different spatial logic required.  Even in normal 3D space, things can quickly get complicated.  Just think about how alien quaternions seem at first.  The best way to approach learning GA is to read a couple of introductory articles and books to get a feel for the terminology and basic structure even if you don’t fully understand it.  The two I recommend are Geometric Algebra for Computer Science and Geometric Algebra for Computer Graphics.  It helps to have a rough image of what it’s all about before doing any detailed studying.  Next, I would start with the simplest setting for GA, which is the plane (2D Euclidean space).  There is an excellent document on planar GA called Treatise of Plane Geometry Through Geometric Algebra by Ramon González Calvet, which is geared toward people just learning GA.  It helps to have a decent understand of complex numbers first, but it’s not entirely necessary.

The End of Conflation

The case of GA in plane geometry is enlightening in a number of ways.  Frequently when we think of plane geometry, we think of 2D points and vectors and perhaps even complex numbers, but that’s all.  In physics and many engineering disciplines, complex numbers are used to describe rotations and phases and sometimes duality transformations (through conjugation).  Describing all of these operations with complex numbers conflates what are actually different operations with different structures and objects.  It’s especially confusing when different modes are mixed in the same equation.

The same observation can be made with pairs of numbers used to represent both vectors and points.  There is a huge different between a point and a vector, yet we freely mix them even giving a second thought.  The key oversight here is that there is a fundamental difference between a scalar and a scalar with direction.  The GA framework properly treats scalars with direction, giving rise to a rich structure for handling not just directions like vectors, but directed areas, directed volumes, and higher dimension directed spaces.  Vectors in GA are pairs of directed numbers, not pairs of scalars.

In the plane, we can construct a vector space with two orthogonal bases (axes).  Usually we say the x- and y-axis, but in GA the convention is to say the bases {e1e2}.  This is because we can construct spaces of very high dimension in GA, so it makes sense to just number them instead of using the x, y, z convention.

I’ll leave the details out as they’re in the plane geometry details, but suffice to say that the GA of the plane consists of {1, e1, e2, e12}.  Here 1 is the scalars, e1 and e2 the directions, and e12 the fundamental area element, which can also be thought of as the imaginary number in complex numbers.  These elements are related by the geometric product, forming the algebra Cl2 (Clifford Algebra in 2D).  The reason we have an e12 element as area is that the outer product of the bases e1 and e2 gives an area e1e2, which we can simply write e12.

Think about the cross product in 3D and how it gives a normal to a plane.  It’s a similar idea here, where 2 vectors through an outer product describe a plane, but its not a plane in 3Dspace, but the space itself (the unit element of the entire Euclidean plane).

Above is the multiplication table for the geometric product in Cl2 and its sub-algebra for the complex numbers.  By attaching the concept of direction to the scalars, we get a much richer structure.

The Big Picture

The really interesting part about GA is that it is completely coordinate free.  In it, we can formulate algebraic expressions describing, for instance, the intersection point of 2 lines, the distance of a point from a line, the common subspace of 2 subspaces, etc.  All of the formulations can be made without referring to the dimensionality of the space we’re working in, so they’re dimension and coordinate independent.  This means that through coordinate free operations, it’s possible to fully describe a manifold, be it scalar, vector, or of higher dimensionality.  As a result, we can describe the precise structure of a 2-manifold surface embedded in Euclidean 3-space without having to refer to coordinates in the 3-space.

Describing a surface, as mentioned in previous posts, requires referring to extrinsic descriptors and formulating a shape operator.  We can describe a shape operator in terms of GA, but of course we also have to dip into differential forms.  This means developing a calculus over GA, the so-called Geometric Calculus (GC).  All GA spaces are linear, so this is completely doable, but like GA it requires reconstructing our intuitions.  GC is essentially a coordinate free way of treating differential geometry, which is exactly what we need to describe the evolution of a surface.

Posted in Space and Geometry | Leave a comment

A Hyperbolic Perspective on TopoSynth

The original motivation for exploring hyperbolic tessellations was to develop a framework for producing topologically complex 2-manifolds with a regular tiling using a single type of polygon.  First, using only a single, regular tile simplifies the description of calculations over the surface of the mesh since every face has the same structure and can be uniformly treated.  Second, there seemed to be a link between hyperbolic tiling and some new computational paradigms that make use of exponential computational spaces.

In Theoretical Computer Science there are what are called splicing systems and membrane systems.  Splicing systems or H-systems (also DNA computing) model computation based on abstractions taken from how enzymes manipulate strands of DNA.  Membrane systems or P-systems model computation based on abstractions from the way cells use membranes and internal compartments to manipulate molecular signals and transformations.  Both of these computational paradigms make use of parallelism to construct exponential working areas equivalent to what Margenstern describes in relation to hyperbolic computing.

From Topology to Geometry: Coordinate Free

Hyperbolic Tiling

The Doubly Linked Face List (DLFL) data structure used in topological meshing maps easily to hyperbolic tilings.  For example, in the image below a sphere with 2 unique faces, 5 unique vertices, and 5 unique edges can be clearly seen.  In the hyperbolic tiling, the closed 2-manifold is periodic, producing the repetition of the first face at the second layer of the tiling.

Aside from providing a clear visualization of a rather complex data structure, the mapping of the DLFL to hyperbolic tilings adds constraints to the possible ways in which faces, vertices, and edges are connected to each other.  The first obvious constraint is that all faces are pentagons in the case of the (5, 4) tiling.  Second, it’s possible to derive how many unique vertices and edges are in a structure simply by the arrangement of faces in the tiling.  Third, the insertion and removal of faces as well as their connections can only be manipulated in certain ways.

The primitive operations defined in the original DLFL structure are insert_vertex, remove_vertex, insert_edge, and remove_edge.  In the mapping of the DLFL to a hyperbolic tiling – from now on the Hyperbolic DLFL or HDLFL – these operations no longer apply in quite the same way since they don’t necessarily preserve the regularity of the tiling.  Instead, the basic operations of the HDLFL are insert_face, remove_face, and swap_edges.

Insert_face and remove_face both operate on pairs of faces.  In the 2-manifold (5, 4) tiling, there are have be an even number of faces, otherwise there will be free edges that don’t pair up.  As a result, insert_face will actually insert 2 faces while remove_face will correspondingly remove 2 faces.

In comparison, swap_edges has no effect on the number of faces, but it can change the number of unique vertices and edges.  When an existing edge belonging to a face is brought into contact with another, it first has to be separated from the opposite face.  The edge it is going to reconnect to also has to be separated.  Finally, the formerly paired edges are also connected.  If the vertices involved with both edges are different, two of the vertices will can be removed and replaced with the remaining vertices, upping the genus of the 2-manifold by 1.  Otherwise, the genus doesn’t change.

Since these operations are defined on a hyperbolic tiling and are local in nature, their description can be mapped from the more typical topological operations framed in terms of vertices, edges, and faces and expressed instead in terms of hyperbolic coordinates based on Fibonacci sequences.  In other words, the operations can be expressed as automata on the hyperbolic plane.  I have only just started exploring the implications of this, but there is the potential for a very direct and straightforward link to be made between automata (computation) and topological structure.

Curvature and Harmonics

Aside from the restrictions on modifications to the DLFL that the HDLFL provides and the coordinate system it provides, the HDLFL also generates periodic coloring of the tiling.  This periodicity can be exploited in the conversion of a purely topological structure to a geometric one that can describe a specific 2-manifold structure embedded in Euclidean 3D space.  To produce an embedded 2-manifold we need to somehow generate the defining extrinsic properties of the surface that produce a particular form.

One approach is dynamical, where the vertices and edges of a graph (i.e. a topological structure) are given weights and forces.  The forces are then simulated until the graph reaches a stable configuration.  The final result is a particular geometric form with extrinsic properties.  The problem with this approach is that the dynamical system can get stuck in local minima and is difficult to control to produce specific forms since the connection between forces and final shape can be difficult to divine for even moderately sized graphs.

Another approach is to actually specify the extrinsic curvature directly.  In differential geometry, this is expressed by the Second Fundamental Form.  If we can somehow produce a periodic function parameterizing the Second Fundamental Form over the hyperbolic tiling, we will be able to precisely specify and control the particular structure out 2-manifold takes on in its embedding space.  This function is called the shape operator.  It maps a point on the surface to the Gaussian curvature at that point.

In the periodic coloring of the hyperbolic tiling, the shape function becomes a harmonic function of curvature.  There are a number of ways to generate harmonic functions for given boundary conditions.  We could impose boundary conditions by marking vertices and/or faces with specific curvature values and solve form there using a diffusion simulation, or we could employ a generator of harmonic functions like a Fourier or wavelet decomposition.

The shape function is a tensor product of the differential changes in the distance measure of the surface.  It can be expressed in a coordinate-free manner by making use of Geometric Algebra.  The surface itself, can be marked be Geometric Algebra elements and the shape function expressed as a differential over those elements.  Thus the shape function can be fully and compactly described using Geometric Calculus.  A talk on Geometric Calculus was given by Hestenes at the AGACSCE2010 conference.

From Topology to Computation: Biological Systems and Dynamic Structure

The second primary motivation for moving to the HDLFL representation was to incorporate some of the techniques from natural computing to describe the evolution of the 2-manifold structures.  After all, all of this work is part of a larger project of figuring out how to construct complex dynamic spaces with the Chemoton as a model.  The link between complex surfaces and their relationship to biological systems is the true subject at hand.

Biological systems can be broadly characterized has being dynamical systems with dynamical structure.  They can’t be fully described by a set of partial differential equations since the actual structure of the system itself changes over time, particularly during morphogenesis.  Thus, there has to be in any description of a biological system, a way to characterize how the system evolves in a structure-dependent manner.  In some sense, this is what membrane systems do.  They describe how elements evolve in relation to each other as well as the structural elements (membranes).  Membranes can be divided, dissolved, modified, etc.  However, this perspective can be generalized by taking a topological approach to the computation and description of a biological system.

Precedents and Implications

The topological point of view on computation, particularly in a biological setting, has been most clearly put forth in the MGS (Modèle Général de Simulation/Système) project.  They take a topological point of view on computation by formulating the concept of a data structure (DS) as a pair of a dataset D and an organization o (i.e. DS = (D, o)).  As a result, the data structure describes a set of positions between which a computation moves, meaning there is a defined neighborhood of computation, which is required to deal with topological concepts.

Within this topological framework, computation is defined as taking place along a path defined over neighborhoods.  All computations and transformations are local since they can only operate over neighborhoods, so any rule defined in a program must be described in terms of local information and operations.  In the MGS system, rules are given imperatively, meaning the description of changes in program state are given not the manner in which those changes are implement as in declarative programming.  The transformation from an imperative input to a running program is derived from applying some principles of algebraic topology to the given rules.  Since the rules are defined over neighborhoods, which give a topology, the principles of algebraic topology can be used to transform the rules into a runtime structure.

The topological approach to computing can be taken quite far, ending up in places like synthetic topology and category theory.  More importantly, however, is that the topological approach enables a way of programming that easily admits dynamical structure.  Instead of writing many procedures for different contexts, we can instead write simple rules that apply when their conditions are met no matter what the context or structure of the program is.  Since biological systems are characterized by dynamical structure, we can model biological systems in a straightforward manner using the concepts of topological computing.

From Topological Computing to Biological Computing

Since the topological approach to computing brings us in to the realm of biological, it’s natural to ask what some of its deeper implications are and what biological computing might look like.  For example, what does the concept of genus mean abstractly?  Geometrically, we have an intuition that it’s the number of holes in a manifold, but more precisely its a number given to a category of objects which can be continuously transformed into each other.  In other words, it’s a way of categorizing objects homeomorphically.  Genus can also be thought of as a kind of cardinality.

If we can think of genus in terms of computation and understand its implications, then what might some fundamental biological structures look like in a computational setting?  For example, every biological system is based on some kind of autocatalytic loop.  Cellular metabolisms, for example, are autocatalytic loops.  These have an inherent topological structure along with kinetic properties.  In a biological approach to computing, we are essentially asking what image does an autocatalytic loop in the context of computation?  In other words, what is its mathematico-logical form in a time-varying system?

Posted in Computational Technique, Space and Geometry | Leave a comment

Navigating Hyperbolic Space with Fibonacci Trees

When moving from the usual Euclidean flat space to a curved space like hyperbolic space, one not only has to work with new models of basic geometric concepts like points, lines, and triangles, but one also has to deal with new ways of counting.  When creating software that deals with space, ways of counting in space are of utmost importance because counting forms the basis for the design of compact and efficient data structures.

For example, software dealing with particle systems and forces between particles must have a mechanism for spatial partitioning in order to mitigate the combinatorial explosion of particle-particle interactions and make the system computationally tractable.  In 2D space, this is typically done with a tree-based data structure such as a quadtree or in 3D an octree.  These data structures are based on a linear counting that tracks the structure of how flat space divides in to smaller pieces.

In hyperbolic space, however, space does not divide so neatly due to the exponential growth in the size of the space as one moves from a reference point.  Instead, what is needed is counting mechanism that tracks the exponential nature of hyperbolic space.

So how might we go about constructing a counting system for hyperbolic spaces in order to design hyperbolic data structures?  First, we can look at the fundamental work on hyperbolic spaces by Coxeter in which he links hyperbolic tiling to group theory, which has been extended in to computational group theory.  The process of tiling is in a sense a kind of counting just like group theory can be boiled down to arithmetic on the integers, but it still doesn’t quite show us how to build data structures over the tilings.  For that, we need to develop a coordinate system over the tiles so that we can quickly construct neighborhoods around a particular cell and navigate from one cell to another along a shortest path.  This is where Maurice Margenstern‘s hyperbolic cellular automata comes in.

In developing hyperbolic cellular automata, Margenstern has developed a way of overlaying a coordinate system over the hyperbolic tilings (5, 4) and (7, 3).  The critical insight is that the Fibonacci sequence maps perfectly to the sectors of the hyperbolic tile where one sector corresponds to a the tiles connected to one side of the central polygon.  In the (5, 4) tiling, there are 5 sectors and thus 5 Fibonacci sequences covering the tiling.  The Fibonacci series maps on to the tilings through a tree structure where the coordinates of child, parent, and sibling nodes can be calculated by working with simple operations on Fibonacci numbers.

The image above shows a single pentagonal sector with its corresponding Fibonacci tree.  The tree is constructed with 2 simple riles: each white node has children (black, white, white) and each black node has children (black, white).  The square at the top of the tree is the fundamental polygon, which links together the 5 trees of the complete tiling.  Interestingly, the resulting Fibonacci tree is a 2-3 tree, which is a data structure in computer science that creates well-balanced trees, making modification and searching efficient.

Notice that the indices in the tree nodes count like normal integers and not like Fibonacci numbers.  Here, the Fibonacci sequence doesn’t define the way that nodes are counted but instead the way that integers are assigned to them and the way the tree is structured.  For instance, each row of the tree has F[2*n+2] nodes where F[n] is the nth Fibonacci number.

There is a well-known way to represent integers with Fibonacci numbers called the Zeckendorf representation.  The Zeckendorf theorem states that any integer can be represented uniquely by a set of non-consecutive Fibonacci numbers.  As a result, any integer can be written as a binary number where each bit corresponds to an index in the Fibonacci sequence.  For example, 14 can be written as 13+1.  The Zeckendorf representation of 14 is therefore 100001.  7 is 5+2 or 1010.  What Margenstern realized is that the parent-child relationships of nodes in the tree covering the hyperbolic tilings (5, 4) and (7, 3) can be calculated using the Zeckendorf representation of the integers since the structure of the tree follows a Fibonacci growth pattern.  For example, node 2 has children 5 and 7.  In Zeckendorf notation, 2=10, 5=1000, and 7=1010.  The children of 2 are it’s Zeckendorf representation with 00 and 10 tacked on in the end.  This pattern generalized to all black nodes (those with 2 children).  The complete set of rules for white and black nodes can be found in Margenstern’s paper Cellular Automata in the Hyperbolic Plane: Proposal for a New Environment.

The Zeckendorf counting generalizes beyond describing parent child relationships to describing in a simple closed form all of the connections a particular tile has to neighboring tiles.  This gives not only a way of constructing a hyperbolic coordinate system, but a way of easily navigating hyperbolic space without having to explicitly model the connections themselves, saving both memory and computation.

Based on Zeckendorf counting, we can also build intuitive hyperbolic interfaces for interacting with data in hyperbolic space.  Here, the idea is to place whatever data is being inspected in the central polygon and have its neighborhood represented in the surrounding visible region.  This is essentially the problem of mapping one tree on to another.  The first tree is rather small and is for structuring the spatial layout defining the number of cells visible at any given moment.  The second tree can be infinite in size and contains the data to be displayed.  I won’t describe the mapping algorithm in detail here, but it suffices to say that the mapping is made extremely simple through the manipulation of Zeckendorf counting.  

Above are 2 examples of mapping a data tree onto a display tree.  The first maps the cell (0:0) into the central polygon.  I’ve colored each of the 5 sectors with a different color to distinguis the 5 trees.  Since (0:0) is the original coordinate of the central polygon anyway, the mapping is trivial.  Notice that each edge from the central polygon to its children is a different color.  This is because the central polygon links together all 5 trees.  The the second example, the central node is (3:2), that is the 2nd node of the 3rd tree.  Notice how almost the entire graph of connections is blue.  When (3:2) was shifted to the center, the focus moved from all trees to the 3rd tree, so nodes from the 3rd tree shifted into the surrounding neighborhood, leaving only a few cells of the 2nd tree visible at the top.  Also, cell (0:0) has moved into what used to be cell (1:2) in the top right.

Posted in Computational Technique, Space and Geometry | Tagged , , , | Leave a comment

Hyperbolic Geometry: Poincaré Disc Tessellation How-to

Background

Figuring out how to draw lines in hyperbolic space is pretty straightforward.  It’s just some basic geometry and the details are easy to find with a little searching.   What is not so easy to find is the details on how to construct a hyperbolic tessellation.  There are plenty of images of hyperbolic tessellations, but nothing that describes the process of creating one in detail.

The best resources I’ve found so far are the work by Coxeter and Dunham.  Coxeter did most of the seminal work in hyperbolic tessellations and corresponded with M.C. Escher when he was working on his Circle Limit drawings

There are two main problems to solve when creating a basic hyperbolic tessellation once the basic mechanics of hyperbolic geometry are worked out.  First, for any particular regular polygon, the radius of the circumscribing circle needs to be calculated.  Second, the pattern of transformations that tile the hyperbolic plane need to be enumerated.  The paper The Trigonometry of Hyperbolic Tessellations by Coxeter is the only place I’ve found a clear solution for the first problem.  For the second, the papers Creating Repeating Hyperbolic Patterns and Hyperbolic Symmetry by Dunham illustrate how tilings of the hyperbolic plane are generated from the fundamental region.

What I find fascinating about hyperbolic tilings as compared to Euclidean tilings is the dependence on distance.  In the Euclidean plane, any sized square, rectangle and regular hexagon will tile the plane.  In the hyperbolic plane, many different N-gons with different patterns of tilings are possible, but only if the shapes have a particular size.

Technique

The key technique we have to master in order to generate hyperbolic tessellations is that of inverse geometry, particularly taking the inverse with respect to a circle as this is how every polygon in the tessellation will be generated once the first polygon is placed in the plane.  Since lines in the Poincaré model of the hyperbolic plane are really circular arcs, we can perform reflections over hyperbolic lines simply by taking the inverse with respect to the circle that the arc is on.  The procedure for generating the tessellation is as follows:

  1. Calculate the radius of the circumscribing circle of the fundamental region.
  2. Calculate the positions of the vertices of the fundamental polygon on the circumscribing circle.
  3. Reflect the fundamental polygon across the edges of the fundamental polygon, generating N new polygons.
  4. For any edge on an existing polygon that only borders a single polygon, perform a reflection of that polygon across the edge to continue the tessellation
  5. Repeat step 4 ad infititum

Fundamental Region (1 & 2)

Calculating the radius of the circumscribing circle from first principles is rather involved so I’ll skip all of the details since they’re in the Coxeter paper mentioned above.  The end result if a simple equation that can be applied and depends only on the number of sides the fundamental polygon has.  One interesting note about the derivation is that it depends on what is called the Angle of Parallelism.  In the above diagram, the angle of parallelism is the angle between AN and AO.  The angles defining the tessellation are π/p and π/q where p is the number of sides of the fundamental polygon and q the number of polygons meeting at a vertex.  In the case above (p, q) = (5, 4).

As you can see, the circle with center O on the line AC generates an parallel line at the angle of parallelism.  Through a series of geometric operations, it can be shown that this circle defines precisely one of the edges of the fundamental polygon and since we know that the angle between vertices is 2π/p, we can draw a ray AB and intersect it with the circle to find the first vertex of the polygon.  From there it is simply a matter of placing vertices every 2π/p radians at a distance AB from the center A to form the complete fundamental polygon.

The equations for calculating the center O and radius OC of the circle defining the fundamental polygon are:

  • O = (d, 0, 0)
  • length(OC) = r
  • d = 1/sqrt(1-((s*s)/(c*c)))
  • r = 1/sqrt(((c*c)/(s*s))-1)
  • s = sin(π/p)
  • c = cos(π/q)

B can be found by intersecting the ray A at angle π/p with the circle.

Reflection by Circle Inversion (3 & 4)

Once the radius of the fundamental region is calculated, the points of the fundamental polygon are easy to calculate.  In Dunham’s paper on hyperbolic symmetry, he outlines an approach of calculating the fundamental region (the dark grey triangle) and replicating that across the hyperbolic plane.  In his model, there are 3 reflections required to tile the entire plane.  The first reflects across a line and creates a triangular segment of the fundamental polygon.  This triangle is then reflected across the hypotenuse of the fundamental region repeatedly to fill in the fundamental polygon.  The the third reflection is applied across the hyperbolic line to generate the other tiles.

Dunham is interested in tessellating patterns across the hyperbolic plane whereas I’m solely interested in drawing the polygons themselves and not any kind of pattern inside the polygons as found in M.C. Escher’s work.  As a result, I can simplify Dunham’s approach a bit.  First though, we need to understand circle inversion.

Inversion by a circle follows a simple procedure:

  1. Draw a ray from the center of the circle O to the point A that is to be inverted
  2. Calculate the inverted point A’ via length(OA) * length(OA’) = R^2

In other words, the process of inverting by a circle simply sets up a proportion of the distance to the point to the inverse distance of the inverted point where the proportions are related by the radius of the circle.

Going back to generating the fundamental polygon, my approach is to simply mark out every 2π/p radians a point the appropriate distance away from the center.  This generates the entire polygon but discards Dunham’s internal reflections within the polygon, which I don’t carry about anyway.

The next step is to invert the polygon across each edge of the polygon following the procedure for circle inversion just outlined.  Once this is done, one level of the tessellation will be completed.  To continue the tessellation, simply repeat the inversion process across all remaining edges.

Posted in Space and Geometry | Tagged , , | Leave a comment

Hyperbolic Geometry: Poincaré Disc

One of the most common models used to visualize hyperbolic geometry is the Poincaré disc.  The Poincaré disc maps the point at infinity of a hyperbolic space to a circle where hyperbolic lines are represented as arcs of circles intersecting the Poincaré disc at 90 degrees.  As we move away from the origin of a hyperbolic space, the space itself expands due to negative curvature, so as we reach the perimeter of the Poincaré disc, the scale of the space changes dramatically, subdividing into an infinite number of pieces.

Typically, the Poincaré disc is given a radius of 1, but any radius will work.  There are quite a number of other models for hyperbolic space, including the Klein disc model and the Weierstrass model depicted below.  The Weierstrass model places the hyperbolic plane on a single sheet of a hyperboloid.

The biggest difference between Euclidean space and hyperbolic space is the change in curvature.  This is expressed in the Poincaré model by the mapping of hyperbolic lines to circular arcs.  These arcs must be interior to the Poincaré disc and can only be on circles that have their center outside of or on the disc perimeter and that intersect the disc at 90 degree angles.  Lines passing through the center of the Poincaré disc are on circles of infinite radius and this look like straight lines.  Below are some examples with the supporting constructive geometry visualized:

In these images, the hyperbolic line is black, the Poincaré disc has a thick grey border, and the circle on which the arc lies is light grey and thin.  Notice the dramatic change in scale of the Poincaré disc relative to the circle constructing the hyperbolic line.  Also notice how each line, if continued along its circle, would intersect infinity from 2 directions.  In hyperbolic space, each line is parallel to exactly 2 other sets of lines and is “ultraparallel” to many other lines that do not intersect it either directly or asymptotically at infinity like parallel lines.

Posted in Space and Geometry | Tagged , | Leave a comment

Hyperbolic Tessellations

I’ve recently been working on a different approach to composing complex topologies using hyperbolic spaces.  The motivation for this approach comes from recognizing that biological structures are by and large made up of 5-sided forms and that pentagons can be sued to tile any 2-manifold object.  In other words, 2-manifold objects can be viewed through the lens of pentagonal tessellations, however, pentagons cannot tile the Euclidean plane.  They do however tile the hyperbolic plane.  For some background information, there’s a video on 3-manifolds that is fantastic.

Hyperbolic space has an infinite number of possible planar tessellations whereas spherical and Euclidean planar spaces have a just a small number (5 and 3 respectively). The space of possible tessellations can be mapped out by graphing the number of sides of the basic polygon (p) versus the number of polygons coinciding at a vertex (q).

The idea to use hyperbolic space for composing topology is to color the hyperbolic plane with a periodic pattern of colored tiles where each unique color corresponds to a unique tile.  Where the pattern repeats, we can say that there is a loop or hole constructed on a 2-manifold surface.  In other words, we break the 2-manifold surface into tiles and map the connections between tiles onto the hyperbolic plane.  For example, a torus made of 4 pentagons and a (5, 4) tiling looks like this:

Notice that some tiles connect more than once.  This is completely valid as we’re not restricting the way tiles can connect in any way as long as the tiling is a (5, 4) tiling.  We could for instance model a sphere as a tessellation with a single tile that repeats in all directions.

In the above diagrams, the (5, 4) tiling wasn’t chosen arbitrarily.  While I did restrict myself to pentagons at the start, I could have chosen from an infinite number of values for q.  4 was chosen because of it computational properties.  Not only are hyperbolic tessellations useful for topology, but they have some really interesting applications to the design of automata and grammars, particularly with respect to questions concerning the fundamental nature of computation.  The main researcher in this area is Maurice Margenstern, who was written extensively about hyperbolic tiling in the context of computer science.

From Margenstern’s work, the Fibonacci trees are of particular interest because they provide a straightforward mechanism to overlaying hyperbolic tessellations with a kind of computational connective tissue in the sense that they become easy to navigate and manipulate since a simple data structure can be used to describe the entire domain including both its connective and hierarchical relationships.  The best introduction to this subject is Margenstern’s Cellular Automata in the Hyperbolic Plane: Proposal for a New Environment paper.

The Fibonacci tree follows 2 simple rewrite rules in the process of covering the hyperbolic plane: white -> black, white, white and black -> black, white.  The fundamental polygon (root of the tree) in the center has no color and its children are all white nodes.

With the Fibonacci tree in place, and the basic mechanics of working in hyperbolic space worked out, the next step is to work on the navigation of the tiling so that mappings can be made to the pentagonal grid and tiles on a 2-manifold.

Posted in Computational Technique, Space and Geometry | Tagged , , , , | Leave a comment