Conformal Type Locomotion

In a previous post I talked about how whole-body locomotion could be performed on void-sponge fractals using Mobius transformations. Since then I have made this Shadertoy game to try out how well the control techniques work.

Before getting into the control system I'll recap what is happening here. The controllable player is a 3D conformal-type. A conformal-type is the equivalence class of points under conformal symmetries, which in 3D are the 3D Mobius transformations. So unlike a shape, this is natively non-rigid; it flexes. 

The particular conformal-type in question is a void-sponge, built as the inversive limit set of 16 generating spheres in 4D centred on the vertices of an 8-cell and projected stereographically into 3D. You can use the vertices of other 4D polytopes too, like the 5-cell, 16-cell, 24-cell, 120-cell and 600-cell but the 8-cell is particularly convenient for keyboard control as it has right-angled symmetry.

So there are two parts to this study of control techniques. The first is how you can use the Mobius transformations to locomote the object in various environments, and the second is how you can use keyboard control efficiently to do so.

1. Physical Locomotion

The go-to Mobius transformation here is the elliptic transformation, also called circulation. As previously shown, this allows swimming through water, and flying. On ground, circulation is applied more carefully. A small amount of circulation around a vertically oriented circle will tip the sponge in the normal direction of the circle's plane. 

In fact I found that the circle needs to be tipped slightly downwards at first, then tend to horizontal as the sponge gains speed and 'walks' across the landscape. The sponge seems to be able to climb up to 13% slopes with this circulation method. 

2. Keyboard Control

The 8-cell sponge supports an intuitive and efficient form of keyboard control, entirely with the four arrow keys and the A/Z keys for vertical motion. The camera finds the closest principle axes (with pitch/roll removed) on the sponge to the camera's current orientation and converges towards a chosen orientation close to this axis, typically looking slightly down on the sponge.

A: Swimming

The desired velocity vector for the left/right/up/down arrows are left/right/forwards/backwards on these closest principle axes. Similarly for the A/Z keys it is the up/down of the closest principle axes. Consequently the controls are approximately screen-space; you press left, the sponge moves left.

These 6 principle desired velocity vectors are quite crude on their own, so we support a secondary key press. Whatever direction you hold down the orthogonal four keys can then be pressed to tilt the desired velocity in the that direction. For instance, if you hold A to go up, then press the left arrow, the desired velocity will point up and a little to the left.

We then need a feedback controller that can rotate the body to match the tilt, and circulate the body to acheive the desired velocity. A simple PD controller is used, which adds a small amount of lateral circulation to compensate for the angular and angular velocity error of the sponge relative to the desired velocity vector's angle.

For upwards swimming this gives four tilt directions and the untilted direction, so five for each of the 6 principle swim directions, giving a total of 30 swimming directions. Note that for the horizontal swim directions, pressing an orthogonal horizontal direction yaws the sponge, which causes the camera to rotate accordingly, as a result this horizontal control is not a tilt but a curved path, it is steering the swimming.

B. Surface Swimming

If you swim laterally and press A as the secondary key then the sponge will eventually reach the surface, where the lack of drag on its top half will pitch it upwards. The feedback controller (if strong enough) modifies the 'stroke' to be shorter movements at the base to compensate for this pitch. The result is a surface swimming motion. I am not sure if this is the best way to surface swim with this conformal-type but it may well be.

C. Flying

Flying is quite similar to swimming, but only uses the upwards A key as the main direction. The motion is also faster to account for the lower drag of air compared to water. You can therefore press and hold A to begin circulating the sponge vertically, and then press the arrow keys to tilt the sponge and so fly in the respective lateral direction. 

Unlike swimming you reach a maximum height and so move laterally even when holding A. You can only descend by stopping holding A.

Flying

D. Walking

The 'walking' uses a slight circulation of the sponge in the walk direction (arrow keys) to bend the sponge to repeatedly tip in that direction. As with the swimming you can press an orthogonal horizontal direction while your main direction is held, which turns the sponge, steering it in a circular path. It also supports the A/Z secondary direction, which tilts the circulation up and down. This can help in some cases such as getting started but is mainly there just for consistency.

 

You can see the simulated walking movement here.

E. Crouching

The Z key on its own currently just circulates the sponge down slightly, which is like a crouch. 

The control is nicely consistent across all three mediums, with the secondary key allowing steering on top of the main movement direction. There are a few motions that I haven't programmed but would be interesting to try in future:

i. Jumping

For a standing jump pressing Z (crouch) and then A could work it made strong enough, but bumps on the ground may always make that problematic. It also would make flight more realistic if the sponge had to jump first.

For a walking jump, pressing Z as the secondary key and then A might work similarly.

ii. Digging:

The controls of digging can be the same as swimming. The primary key is the digging direction and the secondary key steers, with yaw being a continuous angle change and pitch and roll being a fixed tilt. 

The only thing that is different is that it uses a parabolic rather than elliptic Mobius transformation.

iii. Rolling

The first difficulty with rolling is to get the sponge into the right configuration at the right angle. The main idea for rolling forwards is: hold left key, then right key to tip onto edge. both pressed triggers it to form the wheel shape.

At this point, if the wheel is on a slope then it will start to roll down it. We use changes to the circulation vector to auto-balance the wheel while both keys are held down. If it is not on a slope then forward and back arrows can adjust the circulation vector to weight the wheel forwards or backwards. 

Finally it may be possible to lift the left or right keys individually to steer the wheel as it rolls.

Summary

Unlike shapes, conformal-types are flexible and their range of motion allows for multiple forms of locomotion. For the 8-cell based sponge this seems to be particularly amenable to keyboard control where just the arrow keys plus A/Z allow a wide variety of motion and steering that is more-or-less the same regardless of medium: air, ground, water, underground. So this has plenty of potential as a game character or vehicle.

The main area that requires a bit more complexity would be rolling locomotion.

Substitution multi-sets

The ability to substitute in a child inversive limit set allows an interesting feature to be implemented in the substitution limit sets algorithm. We can have two spheres that overlap with a non-integer order.

This allows for instance the branches of a tree to pass nearby to each other, where they normally would either connect in a sponge structure or just touch tips. Instead they ignore each other and pass close-by.

We do this by assigning a special order flag (-2) to edges. Noting that 0 means the spheres must be separated and -1 means they contact on their edge. With this flag, two spheres are not constrained relative to each other. In order to deal with this non-group structure a separate rendering thread is kicked off for each -2 connection between spheres that both overlap the point. These each estimate distance in the usual way and the minimum distance is used, representing a union of the multiple iteration paths.

Here is a limit set where the two coloured spheres intersect at a non-integer order (order = pi / dihedral angle):

If we render the limit set normally it has some degree of discontinuities due to the non-integer order:

If however we give the two coloured spheres a parallel connection (-2) then you can see that it adds a lot more geometry:

But these sort of limit sets have a lot of overlap.

What we can do instead is make the two parallel spheres substitute in child sets where each child set lacks the opposite sphere:

If we were to render this without the parallel threads (the standard render) then as you see it creates discontinuities due to the substituting spheres overlapping (I'm not adding an overlap limit set here either):

But if we put the parallel rendering code back in then we get a valid limit set:

One of the key features of this method is that the set can include branches that interlock or thread around each other without the usual behaviour where they just meet at the tips into a sponge. This can be seen between the green and blue tree-cluster-tree geometry on the left hand side. 

You can see that the limbs get near each other and enter each others' space. This is not possible with standard limit sets or substitution sets, it allows parts of a limit set to effectively ignore other parts, which it good for making more elaborate tree-like structures, rather than just recursive domes. Because there is no constraint on the angle between the two coloured spheres, they are free to be animated continuously. If can of course cause overlapping geometry if the spheres overlap too far. 

The above was a tree-cluster-tree, since it is a tree cluster-tree (a cluster-tree made of trees, which means trees that touch) and also a tree-cluster tree (a cluster of trees that touch with tree connectivity). Here I do the same thing with a tree-tree:

See the close but unaligned branches at the bottom. Again the parallel threads are needed, otherwise you get discontinuities:

 It uses a tetrakis hexahedron set of generating spheres, but two of the pyramidal apexes are extra large spheres and therefore overlap considerably:

You can see three of the cube of spheres in the middle. The outer spheres don't overlap apart from the green and orange ones. 

Here's a slight variant that more clearly shows some overlapping branches just below centre:

The other benefit of these parallel overlaps is that multiple non-interacting limit sets can exist inside a single system. That effectively turns a substitution limit set system into a scene graph. You would just need some code to keep track of moving spheres and update the parallel connections according to which spheres they are overlapping. That is for later work.

Improving Global Landscapes

Looking at the mixed landscape from the previous post

there are a few problems that would be nice to address. The first is that substituting in a child limit set creates a distribution of patches (good) but each patch is solidly that one limit set, which looks a bit extreme. Here I show a simple case of substituting the green tree-tree set on the top sphere:

bottom image is the generating spheres with an arrow showing the substitution.

We can get rid of that solidity by making the child limit set substitute back to the parent. In this case the same sphere is substituting back:

I prefer this way of viewing the substitutions, even if it could sometimes be ambiguous:

You can substitute a different sphere back to get a less geometric result:

but I'm not sure if the surface is continuous in this case. You have to be careful with overlapping spheres when making substitutions.

If the tree area is now too sparse you can substitute back to the golden sphere limit set only on a grandchild instead:

barely noticeable from this distance but there are little patches of 'smooth earth' inside the green areas here.

The second problem is that the patches are perfectly round. In fact deeper zooms would be less round patches as that is partially due to the outer set being perfectly icosahedral. But they'd still be fairly round. 

One way to fix this is to substitute multiple overlapping spheres across to the child set rather than lone spheres. The first step would be two overlapping spheres.  

The only way I know how to do this currently is for those two spheres and neighbours to be the same (up to a Mobius transformation) in the child limit set. That reduces the free spheres to adjust to four. But due to the lack of symmetry it only allows one parameter to change. So back to tree-tree / shell-shell structures.

If we make a brown such tree-tree on sphere 0:

then we can also add one to sphere 1, since we made the child set match 0,1 and their neighbours:

this is continuoue and invariant to order of sphere processing. If we make sphere 0's sphere 0 substitute to child sphere 0 and sphere 1's sphere 1 substitute to child sphere 1 then we get smaller surface patches. They are round in some places, but at the overlap (top left) they combine correctly into longer shapes, which wouldn't otherwise happen. We usually have problems when substituting neighbouring spheres: 

The third problem is that we can't do substitutions on neighbouring spheres. But we can use the same solution above, just give the child sets different values of the shell-shell to tree-tree parameter. 

Here sphere 0 links to the brown tree-tree set and sphere 1 links to the grey shell-shell:

Notice that the overlap between top and left patches prioritises sphere 0 (top). That means sphere processing order does effect the shape. The only fix to this would be to create some sort of tree/shell mixture in the overlap and I currently don't know how to do this.

Nevertheless, the landscape still works in the sense of being continuous. And just as discussed at the top, the patches neededn't be solid, we can for instance substitute sphere 0 of the shell child back to the tree child and sphere 1 of the tree child back to the shell child:

This produces a lot of variety, with three sets being blended (pale grey sphereical, grey craters and brown hills) and the two child sets overlapping. Nevertheless we are only working with a one-parameter knob, from crater to hills. 

We can do better than this by making a special set for the overlap region between child sets A and B. We allow A and B their full usual freedom where only the replacement ball and its neighbours are constrained to the parent balls. For this icosahedral configuration that means 6 balls of freedom. 

The overlap set is constrained so that A's constrained ball indices are constrained between the overlap set and B, while B's constrained ball indices are constrained between the overlap and A. That leaves 4 balls of freedom on the overlap set. 

Below uses the ridgey set in green for ball 0 and a hilly set in brown for ball 1:

Note the discontinuity (gap) between green and brown. Now we add in the interpolating overlap set:

These are two variants, the left uses the green shape for the four free balls and the right uses the brown hilly shape. In both cases the overlap region exactly connects the brown and green sets together.

You can also see in the bottom right that this overlap automatically applies to the smaller patches too. 

Bottom left you see a green patch that doesn't have an overlap region with the large brown region on the left. This is a discontinuity, so we need to apply the intermediate patch to this too. 

To do this requires a careful procedure inside the iteration loop:

1. whenever inside a sphere with a substitution set,  record this substitution set as destination_set.

2. if the query point leaves either this sphere or its neighbours then switch to destination_set.

3. if the query point ends up in any overlapping sphere with a substitution set, then switch to that overlap set

The result applies the transitional set on the smaller green patches too:

and you can also see that the orange patches transition onto the bigger green patch. 

In terms of 2D classification, the non-overlapping substitution sets were a cluster-solid of patches, whereas the overlapping substitution sets form a tree-solid of patches. The outline of green-and-brown is a fractal tree, which is quite nice as it is a more natural transition than a smooth disk. It for instance matches the sort of shape of mountains over flatlands or snowcaps over a mountain range.

It doesn't just work on a sphere, here's a cratered globe (by pulling in the lowest sphere):

The brown hilly set and the green ridgey set are:

Adding the ridges to sphere 0 and hills to sphere 1, together with the transitional overlap set:

The above craters don't overlap the two child sets, so let's get a bit more adventurous and dent sphere 2, which is a neighbour of both child sets (at sphere's 0 and 1):

 

and a close up:

So this is a good indication that the method is working, and that it really is adding these child sets without discontinuity. 

A more thorough write up of the algorithm is here: https://www.researchgate.net/publication/407295122_Inversive_Substitution_Systems

Inversive Global Landscapes

One of the nice things about inversive limit sets is that they typically are deviations from a sphere (e.g. here) so it is tempting to think they could be used to define a global landscape such as mountains, craters and hills on a planet or moon. To get the variety you can use the inversive substitution rules approach of my recent post, which happened to be based on an octahedral configuration of six spheres. You then start with a spherical limit set and switch to varied configurations. There are a wide variety of configuration but in this post I'll consider only distortions, meaning the same connectivity but different placement and size of the spheres.

The problem with the octahedral arrangement is that there is only one degree of freedom in distorting from a sphere. This gives you a cratered shell-shell all the way to the lumpy tree-tree seen in the recent post, but no others. Even here the degree of freedom is only when the octahedron is perfectly regular.

For the tetrahedral spherical limit set it is worse, there are no degrees of freedom. You must stay as a sphere.

For the cubic arrangement there are also no degrees of freedom. The faces must stay planar.

For the dodecahedral arrangement there is no connectivity diagram possible that covers the whole face, which means it does not generate a surface.

That leaves only the icosahedral arrangement among the regular spherical limit sets. Its limit set is shown on the right:

Fortunately this does allow at least four degrees of freedom in transitioning from spherical. In these examples the top six spheres remain fixed to allow the transition. I'll give the degrees of freedom parameter names:

Peak: this controls how large the bottom sphere is. 

above right shows the bottom six spheres viewed from below, with red being the enlarged one

Below positive peak value is a tree-tree (left), negative is a shell-shell.

Mid: controls how large the bottom ring of five spheres are.

because the sphere at the bottom is still small it creates a shell-tree (craters and domes). Positive (left) and negative (right):

Ridge: enlarges a ridge of three spheres along the bottom:

positive(left) and negative (right). These seem to generate more ridges and valleys than above.

 

Offset: enlarges a cluster of three spheres at the bottom but offset from centred:

Quite similar quality to the ridge parameter. The ridges and valleys cross each other.

 

From these four degrees of freedom we can create any weighted combination of peak, mid, ridge and offset parameters to describe the landscape one level down from the outer sphere. For instance, here is the globe with the top sphere substituting for the positive ridge set:

Or the top sphere one level down substituting for the ridge set. You can just about make out some indentations here. Which would of course be huge on the zoomed in planet.

Here is a combination of mid times 1.4 and ridge times 1.7:

which seems to be a little more ridgey and less cratery, here it is on the north polar region:

and here I'm making it more of a snowy mountain white and combining with a green hilly variant (peak 3.8, mid 0.5) and a golden shell-tree variant (peak 1.3, mid 1.6):

So there's more variety to be had with just distortions of the icosahedron. There are also a few other distortion types than just the four shown, but I showed the main ones.

It is interesting to see that there is a class of surfaces that is different from the standard shell-tree. Its craters and domes cross over each other to generate a surface of ridges, valleys, and saddles where they meet. This is closer to realistic landscapes where ridges and valleys are common.