I guess you could do something like a quadtree/octree but using polar/spherical coordinates instead of cartesian. Instead of (x, y)-(x, y) regions, you have (rho, theta)-(rho, theta) windows. Add a radius in there to describe a 'box' within the sphere (for full 3D spacefields).

a bsp (on your cartesian coordiantes) with the split planes all passing through 0,0,0 will definitely do the job

I suppose you can consider a certain notion of geodesic polygon (ordered set of vertices, connected by geodesic segments (a geodesic segments belongs to the intesection of the sphere and a plane containing the origin that we will call a geodesic circle or line (meridians are such lines)) along the sphere instead of just standard segments.
Now, know that considering two points on a sphere, there always are two geodesing segments connecting them (one short, and one lon going all around the sphere). We will always consider the shortest.
If you think about is for a bit, the notion of convexity remains on those polygons (using geodesic segments instead of normal segments).
So we basically have somethin similar to 2D convex polygons and 2D bsp, except that the split planes are just splitting geodesic lines that lead to nodes being "geodesic convex polygons"

Now choosing split planes (that match one to one with geodesic lines by considering their intersection with the sphere), can be tricky.
You couls find the largest axis of the current node's content (in this skewed metric), and choose a split geodesic line orthogonal to that, that will ensure proper point cound balancing in its child leaves.

That's how I would do it, but then again, I have not tried it yet.
J

Quote:Original post by Lutz

Quote:Original post by superpig
I guess you could do something like a quadtree/octree but using polar/spherical coordinates instead of cartesian. Instead of (x, y)-(x, y) regions, you have (rho, theta)-(rho, theta) windows. Add a radius in there to describe a 'box' within the sphere (for full 3D spacefields).

Hmmm, I'm not sure whether a spherical coordinate quad tree would be a good idea.
The quadtree cells would cluster at the poles. Unless... I could reduce the subdivision level near the poles... That might work.
I guess I'll test it.

In general, you want to construct a quadtree such that the objects in each leaf are balanced - not such that the spaces are equal. If you move the splitpoint of each node around such that objects are evenly distributed into each quarter, then the tree should adapt to the layout of your stars - it'll be clustered around the poles if they are clustered around the poles.

Eelco:
If I may suggest
you have the sphere center : O
The centroid : C
The furthest point from C : F
the split plane would better be the plane containing OC and the segment CM choosing M such that CM is orthogonal to CF