I thought the easiest way to go about this would be to create a triangulated shell around the planet against which a ray from and normal to the surface could be intersected, the triangle that was hit would let me know which country the point was within.

My very first go at this involved setting up an array of 200 points chosen at random around the surface of a sphere enclosing the planet, these were created by simply choosing random numbers in the [-1, 1] range for the X, Y and Z positions then normalising the resulting vector. Once I had these I use the QuickHull Algorithm to produce a triangulation of the convex hull formed by these points and assigned a country ID to each - albeit really just a colour at this point. The control net mesh looked like this:

Triangulation of country control net created purely from seed points |

Countries found by ray-casting from the surface |

Unless you know of a planet with purely triangular countries though it's not particularly realistic. To make the results a bit more organic I played with adding some noise to the vector shot from the surface against the control net which initially produced some slightly more encouraging results:

Perturbing the ray from the surface |

"Bubbles" of one country leaking into it's neighbour |

### Edge Subdivision

Instead of noise then I had to come up with plan B - my second approach was to subdivide the edges of the triangles adding displacements to the introduced points to make the edges more interesting. In this way the boundaries can be more interesting while still preventing "bubble" errors. The process here is to recursively divide any boundary edge over some minimum length introducing a new boundary point in the middle of it. The cross product of the edge vector and the normal gives a tangent which is used to displace this new point by some random amount. The magnitude of this displacement is capped to be a proportion of the length of the edge so long edges have their midpoint displaced further than short edges to keep things in proportion.

Subdividing the edges did turn my nice triangles into n-gons so I also had to add in a triangulation step to turn each set of country boundary points back into a mesh I could both ray test against and render for debugging purposes. As I knew the boundaries couldn't have holes I used the trusty Ear Clipping Algorithm as it's so simple to implement and fast enough for this case.

There is still a potential for error here though as there is a possibility that the displaced midpoint might end up within an adjacent country's boundary causing the boundary edges to intersect creating invalid boundary pockets:

An edge between two countries that has been subdivided |

Displacing the newly introduced midpoint perpendicularly to the edge by a distance proportional to the edge's length to make the boundary more interesting... |

...but if you displace it too far the new edges can intersect the other existing edges of one or other boundary making an invalid boundary |

If no intersection is found the displaced point is valid and I move on testing the two created edges to see if they in turn can be sub-divided, if however either of the two new edges intersect a remaining edge I have to pick a new position for the midpoint and try again. To reduce the chance of getting stuck trying to find a valid position each time I have to reposition it I reduce the maximum magnitude of the displacement with each attempt so the new midpoint gradually tends back to the original edge. If the magnitude gets so low it's not worth dividing the edge at all I just give up, leave the original edge undivided and move on to the next edge. This only tends to happen in highly acute boundary corners where slivers are produced.

Running the process dividing any edge longer than 50Km gives a noticeably better result than the simple triangles I started with:

Country control net produced by subdividing edges of triangular countries |

Randomly merging adjacent countries helps obscure their triangular origins somewhat |

Unrealistic nexus points where many countries meet, another consequence of the triangular basis |

### Dual Meshing

Rather than shrink the triangles I thought it would be better to start from a more friendly base so instead of using the triangulation of the convex hull surrounding my initial seed points I instead calculated the dual of this mesh effectively producing faces surrounding each seed point rather than passing through them. This immediately gave me what I thought was a better initial mesh, effectively similar to a 3D Voronoi diagram:

Using the dual of the triangular mesh produces better country shapes as a basis |

Subdividing the edges of the new countries makes them more realistic |

Randomly merging adjacent countries provides more variety of scale |

Note the triangulation of the country boundary control net doesn't necessarily produce a spherical mesh as such as the edges of triangles spanning large areas will at times be much closer to the centre of the sphere than their unit length vertices producing odd looking kinks in the geometry:

An obvious kink in the yellow country caused by the control net's triangles spanning a wide solid angle on the planet |

### A Note on Ray-Triangle Intersections

While working on this there were a number of times when I had to intersect rays or 3D line segments with triangles. I was using a trusty old intersection routine I've had kicking around for years but found that even with double precision there were times when a ray or line would be reported as missing a triangle that it really should have intersected, usually when falling on an edge between two adjoining triangles. Puzzled by this I did a little research (i.e. consulted Google) and found a better intersection algorithm specifically designed for intersecting with meshes, "Watertight Ray/Triangle Intersection"

Implementing this solved all my problem cases in one fell swoop so it turned out to be a good find, if you are interested in using it do note however that there appears to be a minor error in the code presented in the paper, see near the bottom of this blog post for more info.

### Conclusion

Although this has been focussed on country generation, while working on it I have thought that the system could also be used to produce areas of water for oceans and seas by simply flagging certain boundaries as water zones. This would produce some nicely shaped features while avoiding the problem of parts of a country being underwater if water was placed by a different system. I will need to feed the country boundaries into the elevation production system however for this to work so the water zones and coastlines are given appropriate topology. Something for the future anyway.

So there you have it, a set of what I feel are quite realistically shaped countries I can use to move on to the next step, possibly placement of towns and cities followed by primary road or rail networks...that sounds like it should be interesting to look into anyway.

Enclaves and Exclaves are a thing. "Bubbles" of the territory of one country being entirely surrounded by another country are not unrealistic, and in some cases can be very extreme.

ReplyDeleteThanks for pointing this out, it's not something I had really thought of - after a little Wikipedia though (http://en.wikipedia.org/wiki/List_of_enclaves_and_exclaves) I agree it's definitely worth considering. There are some advantages to having the country boundaries encoded as geometry as I feel they will be useful when placing boundary related entities such as border points or fences which would be hard to locate using noise perturbation but I think it would make things interesting to try to incorporate this real world feature into the control net somehow.

DeletePerhaps the merging routine could be adapted so boundaries that are close but not conterminous could be merged to produce exclaves...the odd enclave might appear by chance too. Something to think about anyway!

This comment has been removed by the author.

ReplyDelete