46
Creative Projects / Re: The World is Just Awesome - Advanced Terrain Generation Thread
« on: May 15, 2012, 04:14:48 pm »
@laurimann:
I imagine that to do this smoothly on a sphere, you may need to rethink your coordinate mappings, since you'll always have issues trying to map a method designed for a 2d orthonormal basis onto a sphere (cf. Hairy ball theorem), although that's not to say that 2d methods are useless, since most of us tend to use and design around flat maps anyways!
I thought of two ways of circumventing this issue. This first one/two I documented here http://www.bay12forums.com/smf/index.php?topic=76404.msg1957246#msg1957246 (though the stuff I put there is very informal; also read Nadaka's post directly following). The idea break the sphere into an icosahedron, and define a locally flat coordinate system in each of the 20 sub-triangles that doesn't have issues cropping up with poles and such. With the (r,c) coordinates I set up it is possible to determine the coordinates of all of the neighbors of a triangle grid without branching logic (unless the triangle is on a triangle boundary, but that is easy to determine as well), and it is possible to store the triangle grid data in constant-length arrays.
However, the triangle method is simply a different way of storing 2d data on a sphere that has nicer symmetries than other methods of putting data on a sphere. To actually solve the issue of plate tectonics however, you still need to deal with coordinate mappings, which I got around by simply reposing the problem as simulating plate tectonics on 20 separate flat maps that have boundary conditions imposed by the neighboring sub-triangles (i.e. how fast the plates should be moving, how much material is being added/subtracted, etc...). This method has the benefit of using the same exact mechanics (and if you're clever about isolating your coordinate system from your math, the same exact code) as plate tectonics on a 2d grid (but using triangles instead of squares), so methods could transfer easily (in theory) between 2d and 3d surfaces that can be broken up into a triangular grid (I can imagine fantastical objects like ringworlds with plate tectonics...).
An alternative method for dealing with the issue is to completely scrap the idea of using 2d methods on a 3d object and instead think of grid cells as points floating in 3-space that simply constrained to lie on a 2-sphere using constraints from classical mechanics. That is, instead of each grid point only having a 2d velocity, have a 3d velocity, and if the direction of this velocity vector is not tangent to the surface of the sphere, then apply a force on the grid point to bring the velocity back onto the sphere. You will still need to come up with a discretization of the sphere surface (such as the icosahedron discretization) but then there are no artifacts due to choice of coordinates (although there still might be lingering artifacts from discretization since it is impossible to uniformly put a grid onto a sphere, but I feel triangle artifacts are less jarring than rectangular artifacts since triangles form hexagons and pentagons, which feel more natural than right angles...). The previous 'z-axis' of your work can then simply be reinterpreted as perpendicular depth, and can be continued to be treated in much the same way (since the sphere is locally flat and so over small scales we can ignore curvature effects).
I imagine that to do this smoothly on a sphere, you may need to rethink your coordinate mappings, since you'll always have issues trying to map a method designed for a 2d orthonormal basis onto a sphere (cf. Hairy ball theorem), although that's not to say that 2d methods are useless, since most of us tend to use and design around flat maps anyways!
I thought of two ways of circumventing this issue. This first one/two I documented here http://www.bay12forums.com/smf/index.php?topic=76404.msg1957246#msg1957246 (though the stuff I put there is very informal; also read Nadaka's post directly following). The idea break the sphere into an icosahedron, and define a locally flat coordinate system in each of the 20 sub-triangles that doesn't have issues cropping up with poles and such. With the (r,c) coordinates I set up it is possible to determine the coordinates of all of the neighbors of a triangle grid without branching logic (unless the triangle is on a triangle boundary, but that is easy to determine as well), and it is possible to store the triangle grid data in constant-length arrays.
However, the triangle method is simply a different way of storing 2d data on a sphere that has nicer symmetries than other methods of putting data on a sphere. To actually solve the issue of plate tectonics however, you still need to deal with coordinate mappings, which I got around by simply reposing the problem as simulating plate tectonics on 20 separate flat maps that have boundary conditions imposed by the neighboring sub-triangles (i.e. how fast the plates should be moving, how much material is being added/subtracted, etc...). This method has the benefit of using the same exact mechanics (and if you're clever about isolating your coordinate system from your math, the same exact code) as plate tectonics on a 2d grid (but using triangles instead of squares), so methods could transfer easily (in theory) between 2d and 3d surfaces that can be broken up into a triangular grid (I can imagine fantastical objects like ringworlds with plate tectonics...).
An alternative method for dealing with the issue is to completely scrap the idea of using 2d methods on a 3d object and instead think of grid cells as points floating in 3-space that simply constrained to lie on a 2-sphere using constraints from classical mechanics. That is, instead of each grid point only having a 2d velocity, have a 3d velocity, and if the direction of this velocity vector is not tangent to the surface of the sphere, then apply a force on the grid point to bring the velocity back onto the sphere. You will still need to come up with a discretization of the sphere surface (such as the icosahedron discretization) but then there are no artifacts due to choice of coordinates (although there still might be lingering artifacts from discretization since it is impossible to uniformly put a grid onto a sphere, but I feel triangle artifacts are less jarring than rectangular artifacts since triangles form hexagons and pentagons, which feel more natural than right angles...). The previous 'z-axis' of your work can then simply be reinterpreted as perpendicular depth, and can be continued to be treated in much the same way (since the sphere is locally flat and so over small scales we can ignore curvature effects).