Jump to content

  • Log In with Google      Sign In   
  • Create Account


Space Partitioning on Sphere

  • You cannot reply to this topic
7 replies to this topic

#1 Axiverse   Members   -  Reputation: 343

Like
0Likes
Like

Posted 01 June 2013 - 01:27 PM

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?

 

Thanks!



Sponsor:

#2 Tapped   Members   -  Reputation: 384

Like
0Likes
Like

Posted 02 June 2013 - 09:05 AM

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, 02 June 2013 - 09:07 AM.


#3 apatriarca   Crossbones+   -  Reputation: 1607

Like
4Likes
Like

Posted 02 June 2013 - 10:38 AM

Regions computed by uniformly subdividing spherical coordinates are not very balanced. The regions near the poles will be a lot smaller than regions at the equator. It is better to uniformly subdivide the cylindrical coordinates (so you consider the longitude and z).


Edited by apatriarca, 02 June 2013 - 10:59 AM.


#4 Pottuvoi   Members   -  Reputation: 240

Like
4Likes
Like

Posted 03 June 2013 - 02:09 AM

One easy way would be starting with cube and normalize the vertex posistions to a sphere.



#5 oggs91   Members   -  Reputation: 233

Like
0Likes
Like

Posted 13 June 2013 - 07:31 AM

maybe icospheres is what you are looking for

 

http://en.wikipedia.org/wiki/Icosphere



#6 technotheist   Members   -  Reputation: 110

Like
0Likes
Like

Posted 28 June 2014 - 09:41 AM

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.



#7 Baiame   Members   -  Reputation: 209

Like
0Likes
Like

Posted 02 July 2014 - 09:49 AM

maybe icospheres is what you are looking for

 

http://en.wikipedia.org/wiki/Icosphere

 

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.



#8 godmodder   Members   -  Reputation: 637

Like
0Likes
Like

Posted Today, 10:47 AM

You should take a look at Healpix if you want an equal-area division.







PARTNERS