Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Normandy]

@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).

[Normandy]

(Well this was originally an accidental double-post, but I'll use it as an addendum)

A more generalized version of my first method is to realize that all triangle grid cells, regardless of position, will have 3 neighbors, and what is simply being done is turning a continuous mapping of coordinate bases into a discontinuous mapping, i.e. by mapping the coordinates of each triangle relative to a 2d coordinate basis defined tangent to each of the 20 sub-triangles. So it is really not doing anything special at all, rather it is just implicitly assigning each triangle grid cell an 'x' and 'y' direction in the embedding space (explicitly, when we do this in 3-space on a 2-sphere, we are assigning each triangle grid cell two perpendicular 3-vectors tangent to the sphere that specify a coordinate bases for a local tangent 2-space) and using the simplification that by decomposing the sphere into an icosahedron we can decompose the set of all these directions assigned to triangle grid cells into 20 groups of directions that are close enough to each other that the variations in direction can be ignored and treated as the same direction. So, if working with something like a torus or a ringworld where the hairy ball theorem is not an issue and a good continuous mapping of coordinate bases can be created, you can use the method without breaking up the surface into sub-triangles or other triangle groupings.

Which does remind me, laurimann you refer to the wrapping in your method as being similar to a ball, but it is actually similar to a torus. (That's the mathematician in me speaking...)

[CR055H41RZ]

This would be amazing

[laurimann]

Which does remind me, laurimann you refer to the wrapping in your method as being similar to a ball, but it is actually similar to a torus. (That's the mathematician in me speaking...)

Yes, I am not a mathematician, far from it. However, what you said sounds a lot like speech of mathematician - good theory, but does it work in practice? I didn't really understand at all from your text WHY what you just described would make the running of the plate tectonic simulation more efficient than doing it on a pure 2D square or more simpler to than doing it on a pure 3D sphere. However if you just wanted to describe another way to map 2D square onto a 3D pseudo-sphere, or icosahedron, like Nadaka did in his/her own post, then I understand your point and agree that it might be a good approach in accuracy/complexity terms. But even this method will cause deformations - and the more I think about it, the more assured I am that there's no point in doing plate tectonics on anything else than either pure 2D plane or 3D sphere. If there is a need to map it onto a sphere for visual appeal, then this icosahedron approach is probably as good as any.

However, I am of course open for discussion, persuation and reassurance.

[Normandy]

Oh, sorry about being dense in my post then!

I wasn't commenting about the computational efficiency of the icosahedron mapping to the sphere versus a pure 2d grid - rather, I was commenting on how this method could extend methods which create good visual results on a 2d plane to a 3d sphere (and for that matter, any 2d surface) without any change in the terrain generation step, which would be easier than creating separate methods for the 2d plane and 3d sphere.

I admit though that this only addresses a small concern, and doesn't help make the method run any faster or make it any more accessible to artists/level designers, so it doesn't make this a very practical method...

By the way, have you ever seen this article: http://software.intel.com/en-us/articles/fluid-simulation-for-video-games-part-1/? Fluid simulation is an example of something that requires a lot of detail in a small amount of area to look good, so the ideas they use to decrease computational complexity in this series might be directly applicable to plate tectonic simulations, which have small amounts of activity far away from plate boundaries but a lot of activity close to them.

[laurimann]

Alright, thanks for clarifying. However, I read about 2D->3D mapping a bit here and a little there and found out that you could also do the 2D physics on a cube and for visualization or what ever reason cast it into a sphere as described in http://mathproofs.blogspot.com/2005/07/mapping-cube-to-sphere.html Seems like a marvelous idea to me!

From one things to another: Thank you so much for that article/link! It's superb, I love that approach to computationally heavy stuff and fluid dynamics is something I think I must implement sooner or later - there's simply too many applications, not to mention the amount of experience gained (over 9000!!!).

However, I was introduced a game that implements fluid dynamics already (since 2010). Hydrophobia is a 3D shooter using "HydroEngine" which is capable of simulating fluid dynamics in real time. Heard about that already? In any case the point is that doing real time fluid simulation (mantle convections?) is at our reach today!

[Rose]

Ah, hydrophobia. was a good game up until you got the force.

[WovenTales]

I don't have too much to add in the way of actual terrain generation (though I do want to start working on it soon), but I may have a solution to the problem of points on a sphere not being the same distance from each other, and I'd like to know if it would actually work before I try to implement it in anything—namely, said realistic terrain generation. Of course, not being overly knowledgeable in these fields, it could be anything from common knowledge to needlessly complicating a simple process to complete nonsense, but knowing how functional it is would allow me to research, explain, and very likely use it or its replacement better.

Because of keyboard limitations, t represents theta.
Anyway, for a sphere of radius r, there are three vectors x, y, and z (again, for ease of typing). Each lies along a plane p perpendicular to the other two when t=0 for that vector, and all are joined at the origin. However, each vector v_i rotates around the origin through the plain p_j that is perpendicular to p_i and parallel to v_i when t_i=0 (thus when t_i=90 and t_j=0, v_i is the same as v_j). At distance r along each vector, a plane is calculated parallel to p_i, and if the angles are kept so that |t_x|+|t_y|+|t_z|=90, exactly one point should be described, at the intersection of all three.

If I am imagining this correctly, moving any point along one of the planes (keeping that particular angle constant) by a fixed amount in one of the other measured angles will place it the same distance away from its initial location no matter where it starts as long as r remains constant. Admittedly the third angle will also change (by the inverse amount) to maintain the equation, but I do think it might work. Of course, it does not help at all for transferring functions from rectangular coordinate systems, let alone trying to flatten anything, but it might hopefully be interesting to think about.

EDIT: Might as well say that this is essentially multiple systems of latitude with different axes. Mapping is even worse than the latitude-longitude system as there are six points where the parallel circles converge, but keeping it three dimensional doesn't have the same problem.