Generating equidistant points on the surface of a sphere given the sphere's radius

This is what I’d like to do and I’ve done a little research and I’m guessing what I’m wanting to produce is a geodesic, and I could probably even find some code to produce geodesics for me, which I will continue looking for, but I guess my ultimate question is, what mathematics do I need to learn in order to understand exactly how the algorithm would generate the points?

I think you can achieve what you want using mercator projection. There is classes for that in jme3tools.navigation.

Here`s a little something. It might work or not for you…



[java]

private Vector3f getOrbitPoint(Moon moon) {

float angle = FastMath.PI / FastMath.nextRandomInt(0, 360) * 360;

float x = getOrbitPlacement(moon) * FastMath.cos(angle);

float z = getOrbitPlacement(moon) * FastMath.sin(angle);

float scaledRad = moon.getRadius() / GameConstants.SOLAR_SYSTEM_SCALE;

return new Vector3f(x, 0, z).add(scaledRad, 0, scaledRad);

}

[/java]



You can change it to something like that, technically that should work. Just use the angle you need:

[java]

private Vector3f getOrbitPoint(float radius) {

float angle = FastMath.PI / FastMath.nextRandomInt(0, 360) * 360;

float x = radius * FastMath.cos(angle);

float z = radius * FastMath.sin(angle);

return new Vector3f(x, 0, z);

}

[/java]

Can I ask the meta-question? What’s this for?

Thanks madjack. I can play around with that code. That does give me some idea of how to plot a point somewhere on the surface of a sphere with a given radius (i think).



The bigger objective for me is not to do it, but be able to understand it. I think it’s mostly trig so I should search for trig and spheres and find some math resources.



To answer pspeed, I’ve always been fascinated with the idea of developing a game where the game world is a sphere. A very big sphere with all the points being land zones and having different characteristics, and probably being kept in a database or file system. And somehow be able to translate a section of the surface into a zoomed in view to interact with.

Then GIS techniques may be what you want to look at. People have been building whole databases of our planet for a long time… and the fact that our planet isn’t really a sphere is only a small part of the complication. :slight_smile:



I asked because as I recall, dividing a sphere into equidistant points/lines is impossible beyond an icosahedron (think 20-sided D&D die). Beyond that some of the edges have to be slightly shorter or slightly longer to properly represent the sphere. This is easy to visualize from the 20 sided shape since each side is an equilateral triangle. There is no way to split this triangle that would suddenly make it curve to the sphere without changing the length of some sides. (But I may be remembering incorrectly… maybe there are several hundred sided polyhedrons that are spherical and I’ve forgotten… at any rate you will likely not be able to derive them from similar shapes anyway.)



And if you are already going to deal with oddly shaped parts and/or distortion then there might be easier data structures to start with than triangular ones. For example, if you start with a cube and subdivide each face, projecting the points outward to the sphere then you are essentially dealing with six distorted grids. And grids are way easier to deal with in computers.



Of course, a real GIS is never so specific. Data is just as likely to start out geographic or geodetic lat/lon and then get projected into whatever local projection fits.

So you know, the formula above is to get any point on the circumference of a 2D sphere of the given radius.



To get it for a 3D sphere it’s a bit more involved, but not much more complicated. Check wikipedia.

Yes, that’s neat that I come home from class to read your reply because I actually thought a lot about it in my db class which is completely useless to me, but I guess it’s good for something because I found a solution. My solution involved a diamond and subdividing the triangles, projecting the points outward, then doing it again over and over until I end up with distances small enough for what I want. And it was then that I realized what you stated about after a certain point, you can’t get equidistant points. I think you’re right about the icosahedron(they really need to add that word to spell check) having the most equidistant points. I thought at one point it was perfect because I thought all the surfaces were hexagons and so I was like, there you go, I’ll just have a hexagonal map like civilization, and then looking closer, I realized at certain points (6 points, I think) they are actually pentagons and I was like, shit, how would I deal with that.



I think I’m going to go with subdividing either the diamond or the cube as you suggested(I’ll have to first consider the pros/cons of having triangles or quads to work with). I’m guessing it will take quite a while to generate what I want because I decided I’d like each point to be about a meter or maybe half a meter from each other point and just going off a smaller version of the earth, I think I’ll go with around a 5000 kilometer radius. Knowing now that the points wont be equidistant, I’ll just have to compensate for it. It could actually make the system more interesting. I’m trying to figure a way that I can generate sections of the world on the fly. For example, when a player starts the game, they get a grey(undiscovered) sphere. They click a point on the sphere and I should be able to do some kind of intersection math and figure out the exact intersecting point, then the world actually starts getting generated. Whatever face the point hits, I take that face and subdivide it, then I subdivide whatever face the point hits within those subdivisions and so on recursively. Then once I have the final face whose points are within 1 meter apart, I start subdividing neighboring faces until I have enough faces to represent a decent portion of area. Then as the player moves about the land, I subdivide and generate when necessary. This way the whole planet doesn’t have to be generated at once, because I’m guessing that only small portions of the planet will actually need generation, but it’s still flexible.



I think I’m going to go with a cube. Much easier to work with when placing structures, building buildings and such. I could implement elevation as well. I’m guessing there wont be a coordinate system. Every point will have neighboring points and that’s how I could keep track of where things are. Every position of every entity could be at a point between 4 points or something. Dunno, gotta think through that one and do some testing. I think I should start with a small sphere and see how it works out. Like, a kilometer radius maybe.

I worked out this formula in class tonight, but I’m not sure. I know Pythagorean’s theorem to find the distance between points in 2 d space, it’s like sqrt(DxDx+DyDy) or sqrt(Dx^2+Dy^2), not sure which is optimal.



And I think for 3d space it should just be sqrt(DxDx+DyDy+Dz*Dz), but that seems too easy.



It’s so hard for me to visualize 3d stuff in my head.



But I am pretty sure I can subdivide faces in 3d space, you just get the midpoint between two points which should be x1+Dx/2 for the x position, y1+Dy/2 and same for the z. Then to project, umm… I gotta think about that. Say I end up with a point that is 950 meters and I want it to be 1000 meters, I would just divide each vertex(x,y,z are vertices right?) by the percentage of it’s distance so multiply by 950/1000. Yeah, 950/(950/1000) = 1000 so when I divide each vertex by 950/1000 the new distance should be 1000.



If my math is correct, this should be a lot easier than I thought. I thought I’d have to use cos/sin/tan/atan and all those functions I only halfway understand and always have to look them up when I’ve ever used them.



Please let me know if you find any errors in my thinking or advice that may help me avoid any pitfalls.

On a 5000 kilometer radius I think for a diamond the starting points would be 5000 around 7000 kilometers apart. I wonder how many subdivisions it would take to get down to 1 meter apart. Cause that’s 7,000,000 meters… crazy. I divided 7000000 meters by 2 23 times and ended up with about .83 meters but I’m guessing there will be more than 23 subdivisions because after projection, the division ends up being a little more than half. I’m curious if it’s the same percentage each time, if there were a way to actually calculate exactly what the length would be after x divisions without actually projecting and all that. Some kind of recursive formula.

3D Distance…

[java]

Vector3f v = new Vector3f( dx, dy, dz );

float dist = v.length();

[/java]



…you could look at the code but it’s pretty much what you had.



And if you want to project it to 1000 you can multiply it by 1000/v.length()… which is the same as dividing by v.length()/1000 but I like mult better. :slight_smile:

yeah, I think I read somewhere you should always multiply instead of divide if possible, it’s like one less low level operation or something.



Thanks a lot, who knows when I would have realized there was already a function to do what I want. I guess that’s why they have libraries lol… How handy.



How about getting the midpoint between two Vector3f? N/m, I’m gonna go study Vector3f :stuck_out_tongue:

Midpoint is easy, conceptually: (v1 + v2) * 0.5

Now I need to think of a way to randomly generate elevation while subdividing. Kilimanjaro, highest elevation at around 6 kilometers but the average elevation is slightly above sea level so peaks should be fairly rare. average water depth is around 4 kilometers not sure what the max is. Maybe elevation should be generated after max subdivision. Going to have to play around with that.

Sweet, so I’m assuming Vector3f has all the functions needed to do math on more than one of them.

I also need to determine pros and cons of a flat file system or mysql.

In a file it would be…

4 bytes * 3 for the vertices(floats),

So 12 bytes… then 4 neighbor file position pointers, 4 bytes each as ints so 16 + 12 = 28 bytes for a point



maximum of 2,147,483,647 points. Dunno if 2.15 billion points would be enough.



Ugh, corners, I think I need to use a diamond instead of a cube. Because the corners of a cube don’t have n,s,e,w neighbors.

Hmm… this is get’n complicated.

You might be overthinking it. If it’s a grid then I’m not sure why you need to track neighbors. If you are going from a cube then you at any point your are in one of 6 grids and you can just use your location to figure that out.



…anyway… yes, it’s complicated. This is why geo software is its own industry. :slight_smile:



Anyway… I’ll let you sort all of that out.



For a database, I can highly recommend: http://hsqldb.org/



For embedding a database into a Java app, it’s about the fastest/smallest/simplest thing you’ll find. And it just works.

Diamond is 6 points. after first subdivision, there are 8 more points. Then 16 more points… then I guess 32

so it’s 6 + 2^(subdivisions+2)

Since I said it would take around 23 subdivision, probably more like 24…

2^26 = about 67 million points. That doesn’t sound too bad. I wonder if my math is off though.

Oh wow, I’m going to check that hsqldb out… that could be perfect. thanks.

Well I won’t go into so much detail about your project, but I can paste some code. :slight_smile: I found it on some other game dev forum and rewrote it to Java. This function basically takes number of points you want to generate and returns their positions on a sphere. Points are equidistant or at least try to be. From my experience, the results are very good. You should then multiply all returned vectors with the same scalar to put the points on desired radius. Cheers! :slight_smile:



[java]

private Vector3f[] getPointsOnSphere(int n) {

Vector3f[] points = new Vector3f[n];

float inc = FastMath.PI * (3 - FastMath.sqrt(5));

float off = 2f / n;

float x;

float y;

float z;

float r;

float phi;



for (int k = 0; k < n; k++){

y = k * off - 1 + (off /2);

r = FastMath.sqrt(1 - y * y);

phi = k * inc;

x = FastMath.cos(phi) * r;

z = FastMath.sin(phi) * r;



points[k] = new Vector3f(x, y, z);

}



return points;

}

[/java]