Neighhhhbours, everybody needs...

...to-know-the-orientation-of-themselves-to-their neighhhhbours, that's when non-uniformly-laid-out neighbours, become good-at-preventing-cracking-due-to-different-levels-of-detail-and-also good friends.

Just as in the soap, my geomipmapped planet needs to take care when linking a patch to one of it's neighbours.  However, whereas the soap intended to create cracks between neighbours, my objective is the opposite.  Each patch at any level of detail is set up to have 4 children: top-left, top-right, bottom-left and bottom-right; and 4 neighbours: north, south, east and kylie west.  This image (which I use as a texture for debugging) should make it clearer.  The text "back" at the centre is just so I know from which of the main cube faces (my sphere is really a subdivided cube) this patch comes from.

The neighbours of the main faces of the cube are set up manually at the start, but they need a way to set up the neighbours of their children when they are subdivided.  The internal neighbour case is fairly trivial for when a patch subdivides:

• east of the top left child is the top right child
• west of the bottom right child is the bottom left child
• north of the bottom left child is the top left child
• south of the top right child is the bottom right child 
• and so on...

To get the external neighbours for its children a patch will have to look to its own neighbours, so:

• east of the top right child is the top left child of the patch to the east
• south of the bottom left child is the top left child of the patch to the south
• and so on...

This might perhaps be more obvious in the following diagrams where the level of detail goes up by one for the patch at the back of the cube.

In the first image the top left child gets subdivided and it would set its own top right child to have the main patch's top right child's top left child as its eastern patch.  Confused?  Maybe this will help:

backPatch.topLeftChild.topRightChild.east = backPatch.topRightChild.topLeftChild;

This can be generalised to work recursively (assuming east is set up correctly) to:

patch.topRightChild.east = patch.east.topLeftChild;

Basically, for a child to find its external neighbour (a neighbour from outside its own family) it will have to look at its parents neighbours.  If a person wanted to find out their cousins, they would have to find the children of their parent's siblings.

Ok got it now?  I hope so, because I went through the same confusion only to find out it doesn't always work.

If you stand at the north pole of the earth, any direction you go in will be south.  This doesn't play too well with my north, south, east & west neighbour collection.  These 2 videos show the problem, if you set the main cube faces so that moving east to west is ok, moving north to south will be problematic (they look upside-down compared to each other).  You could fix it so north to south worked ok, but then east to west wouldn't work.

Moving east to west matches up

Moving north to south shows up clashing patches

The video is a bit blurry, so here's an image highlighting the problem, it shows the where the front (A), right (B) and top (C) patches meet.  Because the top patch only has one south, it clashes with the right patch (if I go north from the B then go south again, instead of ending up back at B where I started - I end up on the front patch A).

This can cause cracking because neighbours aren't actually neighbours.  If the code for setting the top left's north was like this:

topLeft.north = north.bottomLeft;

For north neighbours, it would work for A to C but not for B to C.  For the case of B, north of topLeft is actually north.bottomRight.  B.topLeft should look at C.bottomRight when it's rendering otherwise it might try to fix a crack when it's not there or vice versa.  The solution is to look at the orientation of the current patch to the north patch, for example if this patch (B) is to the east of this patch's north (C) then topLeft.north = north.bottomRight.  I found it difficult to visualise what neighbours go where when I was writing the code to handle odd orientations so somewhat embarrassingly I cut out 2 bits of paper and used that to help.

Of course all of this is my own meandering implementation, there are much more elegant methods out there by people who know what they're doing (like Sean O'Neil's).  There isn't even a bit of crack to be seen with these neighbours, if only that were true of the soap.  Next I'll do some clean-up with the code, and look at generating the base textures from scratch.