Jump to content
  • Advertisement
Sign in to follow this  

Space Partitioning on Sphere

This topic is 1595 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

What approaches would be best for space partitioning on a sphere? I'm working with a visualizing data on the surface of the earth.


Some operations that would be relevant

  • Find the closest stored point to a given point
  • See if a the given point is within a region
  • Adding and removing points and regions


Currently, some of the approaches that I've thought of taking are:

  • Start with a octahedron and do triangle tessellation, 4 triangles to each parent triangle. I'm not sure how to approach indexing nodes from latitude, longitude. The pros would be that the partitions would be basically equal area.
  • Quadtree, with the first level separated by north/south hemisphere (positive/negative y) and then a normal quadtree based on the x, z coordinates. This might be a bit easier to index, but leaves might not be balanced well.

Are there any other common approaches that you guys know of or can think of?



Share this post

Link to post
Share on other sites

Hmm, why not use the same grid system that is used to represent Earth coordinates. In other words use spherical coordinates.


Spherical coordinates can easily be worked out from Cartesian coordinates as long as you know the radius and position of the sphere in question. 

So you create the boundaries virtually by specifying [?, ?] extent of each grid cell, as you may be used to when working with normal grids.

Then you can calculate indices for the cells by coordinates, which is done as following:

int GetLocationIndex(const Vec2f &sphericalPoint) 
 Vec2f indices2D = sphericalPoint / extent; 
 return (unsigned int)(indices2D.x) + extent.x*(unsigned int)(indices2D.y); 

The x coordinates of the vectors, are Theta, and the y coordinates are Phi.


Note, i have not tried this, so it is only an approach that may work.
However good luck smile.png

Edited by Tapped

Share this post

Link to post
Share on other sites

In case you are still interested, a simple method for detecting points in a tessellated sphere is to detect the side of the plane formed by 2 sphere points and the sphere center. (dot product of the normal), and perform this for each side of a triangle to detect if a point is inside. You can also use the radial distance from the center of the sphere to divide the elevation of a point.

Share this post

Link to post
Share on other sites

maybe icospheres is what you are looking for




Seconding icospheres. I'm using one for a "tiny planet" style procedural environment and have found it very easy to work with. Some semi-discrete things I've implemented with on it so far are various procedural generation techniques, global illumination baking with radiosity, and collision detection with the ground. At no point did the shape of the environment pose a great challenge, thanks to the simplicity & elegance of icospheres. Here's a screenshot.


Don't use a subdivided octahedron (I tried this initially). At first glance, they appear more "square" and therefore easy to work with, but they're not very balanced, creating greatly varying triangles at the leaves. Plus, icospheres can be squared up as needed. Study the common net of an icosahedron to find out how. I just use five rects (I call "pents") that sit above each regular grid of triangles.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!