   3-D map
  This is partly graphics, partly resource usage, and partly game design, so I'm putting it here, where I hope it'll fit. Anyway, I am trying to make a strategic-level 4X game. I have decided I want to show a globe, rather than any sort of 2-D projection, for my map. So my first project was to find a way to convert a Mercator map back into 3-D coordinates, undoing the area distortion. I got it in the end, though admittedly with some rather non-robust code suited only to one particular bitmap. Still, generalising wouldn't be so difficult. Here's the globe :Ok, it's a bit primitive, but it does work and you can rotate it and whatnot. In fact, that's rather the problem, it's slow as molasses. My approach was to just store the coordinates and height (0 or 1, blue or green) for every point on a latitude-longitude grid, 1800 by 3600 - works out to squares about 20km on a side. Naturally this takes a bit of memory, and as I mentioned, it's kind of slow - you can physically feel the drawing time when you try to rotate.My other problem is that I didn't really think the organisation through. I intend to split this map into provinces. So the first question is, how do I inform the province of what area it covers? I would really prefer not to have to specify which province several million points belong to. One solution I thought of was to specify the border of each province, and figure out programmatically what the internal points are. But I would love it if anyone has a better idea.Second; how can I speed this up a bit and shrink the memory usage? I'm not absolutely wedded to the idea of specifying 6.5 million points, by any means, but this is the sort of detail I'd like to have. Actually, that gives me an idea. Suppose I just specify the western and eastern border of each province for each latitude? That would only come to something on the order of some tens of thousands of points to specify. Then I could use that as the borders of a polygon for each province; that should be orders of magnitude faster. One problem is that I can't have provinces in a U-shape, for example, but I suppose I could generalise - allowing more than one border. I like this idea, thanks for listening to me while I thought it out. I'd love to hear if anyone has a better one, though. :)One thing that perhaps someone more experienced with textures could help me with : Given that I proceed to make polygons for provinces, as outlined, is there any technique (maybe with a tutorial?) for figuring out how my texture borders map to those outlines? I'd like to differentiate mountain from plain, and so on, with textures.   
  Well for the province problem you could probably adapt a Flood Fill algorithm so you could specify the border and fill in the internal area.About the rest of the problems, I can't really help much at the moment.   ;  Don't have any answers per se, but maybe I can help you think about it a bit.Let's say for the sake of argument that along with the heights and water/land differentiation on your original 2d map, you also have the vertices of the (possibly non-convex) polygons that represent the countries, provinces, or what have you. Presumably, since you can map the individual samples to the surface of the sphere, you could also map the vertices of these polygons as well.Once mapped to the sphere, the edges of the polygons become arcs along the surface. Furthermore, the endpoints of the arcs along with the center of the sphere form a plane; thus, each polygon can be represented by a set of planes.I'm just hypothesizing here, but it seems that the standard point inclusion algorithm for non-convex polygons could then be adapted to work with these plane sets. To test a point on the sphere surface for inclusion in a polygon, you would fire a ray in an arbitrary direction tangent to the sphere. If it intersects an odd number of edges (arcs) it's inside the poly, else outside. Here, intersection with an arc requires intersection with the arc plane, and that the point lie within the arc (a simple angle test).If something like this could be implemented it seems it could address a number of problems and provide a valuable tool overall, being useful for AI, area and object picking, and so on. One caveat is that unlike the standard 2D version of the point-in-poly test, with the sphere version there would be some robustness issues to deal with.I don't know what platform or graphics API you're using, but assuming PC/DirectX/OpenGL, dealing with 6.5 million samples doesn't seem practical either from a rendering or gameplay point of view. It seems you'd be better off with a triangle model, and furthermore only rendering the half (more or less) of the globe visible to the viewer. The polygon approach might be helpful here as well, as the province polygons could be tesselated into sets of triangles that could be rendered using vertex arrays. Of course there are many additional areas you could get into here, such as level of detail.Setting aside the issue of blending textures together for the moment, it seems texture mapping wouldn't be too difficult. Assuming a polygon (say, representing a lake or desert) isn't too large with respect to the sphere, you could simply project it onto a plane tangential to the sphere at the polygon center and perform planar mapping in this coordinate system. Or, you could perform spherical texture mapping on the polygon vertices.I'll also post a link to this thread, which includes some discussion of moving about on a spherical surface and various ways to map rectilinear surfaces to a sphere.Well, that's probably a long enough post for now. I'm sure these problems have already been dealt with in various applications, so all this brainstorming is probably just reinventing some wheel or another. But maybe it'll help.   ;  I developed a similar thing, although not for games. We have a reduced-resolution set of data for the outlines of all the countries in the world. This was adapted from the data available to download from NASA or USGS. I can't remember where this data is but a similar process could be based upon SWBD from USGS.I stored the coordinates as 3D vectors, the file for which is less than 3MB. The resolution is relatively low compared to SWBD but it's probably OK. I wrote my own 3D engine which was specifically for this dataset. I'm sure you could use OpenGL or whatever, but you probably have to tesselate the shapes because they are not convex.The 3D vectors are actually larger than the 3D lat/long values, but they do remove the problems associated with polygons crossing the international dateline.You can then specify provinces etc. as 3D polygons which are rendered using the same technique.All in all it's definitely got to be faster (and more space-efficient) than a huge grid of land/sea values. Plus you won't get those artefacts around the equator.Drop me a mail if you need any more help.;  Thanks for the replies. Just a note : Those aren't artifacts aroud the equator, I put that in by hand to mark it. :)I have pretty much given up the idea of the height grid, and my thoughts indeed turned towards polygons for the provinces, but I hadn't thought of putting them on my bitmap. That's actually a splendid idea, because the reason I went for the Mercator conversion of a bitmap in the first place was to avoid having to specify umpteen million points by hand! The problem is rather reduced if you go for province borders, but even so, it does run into the tens of thousands; a largish project. What I might do, then, is to go back to my black-white bitmap, and put in province borders in red. Then I need a tessellating algorithm for non-convex provinces; that could be a bit tricky. This should reduce the rendering to a few thousand polygons, which is a bit more realistic. Thanks for the thoughts. :)   