SkyServer.org - HTM

Geometrical Querying

We want to have a generic possibility to intersect the HTM with any given surface on the sphere. For a certain area, we want to get all HTM nodes of a given depth that are either completely or partially covered by it. We would like to know for each triangle which category it falls into -- completely contained in the area, partially contained or not at all. In this section, we give the geometry primitives that can be used to define any area on the sphere. These primitives can easily be intersected with the HTM nodes to decide into which category they fall. We give the outline of the algorithms that can be used to deduce the HTM category for any area composed of the geometry primitives.

Geometry Definition

Constraints

The constraint is our basic geometry primitive. It is a cap on the unit sphere. We get a constraint by slicing it off the sphere with a plane. Any constraint can be characterized by the direction of the plane \vv and its distance d from the origin:

                 ->           -> 
          c := { v ; d }     |v| = 1    ;    -1 < d < 1
(6)

We allow for 'negative' constraints d<0, which cover more than half of the spherical surface. They look like 'holes' on the sphere. The sign of the constraint is defined to be the sign of d:

          sign(c) := negative     d < 0
                     zero         d = 0
                     positive     d > 0
(7)

We also define the opening angle of a constraint:

          phi_c = arccos(d)
(8)

Examples: {v = (0,0,1) ; d = 0.5 } defines the cap north of 30^o latitude north. {v = (0,0,-1); d = -0.5 } defines everything but the same cap.

Convexes

We define a convex as the logical AND of constraints, i.e. the intersection of caps on the sphere:

          x := c₁  &&  c₂  &&  ···   &&  c_n                 n in N⁺
(9)

Such a geometry is a convex in 3D but not necessarily a convex area on the spherical surface. As an example, the convex { (0,0,1) ; -0.01} && { (0,0,-1) ; -0.01} defines a narrow strip around the equator. It is not even true that convexes are always a contiguous area on the sphere. Imagine the convex given by the intersection of two great-circle strips that are not in the same plane -- the resulting convex is given by two disjoint areas where the strips meet. Consider as another example a cube centered around the origin whose corner points are barely outside the unit sphere. Then the corresponding convex on the sphere is given by the 8 segments just around the cube corners. Note that all these convexes are composed of negative constraints.

However, convexes that are composed entirely of positive and zero constraints always define a convex area on the sphere, which are easier to handle. Thus, it makes sense to define a sign for the convexes too:

    sign(x) := negative     c_i  all negative or zero
               zero         c_i  all zero
               positive     c_i  all positive or zero
               mixed}       at least one positive and one negative constraint
(10)

The sign will be important when we actually calculate the intersections with the HTM.

Domains

We define a domain to be logical OR of convexes:

d := x₁  ||  x₂  ||   ···       ||  x_n            n in  N⁺ 
(11)

Thus a single domain can represent any complicated area on the sphere. If we devise a generic method to intersect domains with the HTM triangles, we have a powerful indexing tool at hand.

Simplifications

Convexes and domains may contain redundant constraints that can be localized and eradicated. The most trivial cases are the following: Consider a convex made out of two constraints c₁ and c₂ with opening angles varphi_c1 and varphi_c2 respectively. Define the angle between them as

          ->   ->
          v_c1· v_c2 = cos(theta_{c1 c2}) 
(12)

If both constraints are non negative, we can drop c₂ if

      varphi_c1 >= varphi_c2 + theta_c1c2

If both constraints are negative or zero, we can drop c₂ if
```
      varphi_c2 >= varphi_c1 + theta_c1c2
```

And we can drop the whole convex if

      varphi_c1 + varphi_c2 <= theta_c1c2}

These simplifications are true even if there are more than two constraints in the convex, we can check each pair of convexes for the above cases. For zero convexes, where all constraints are great circles, we can easily do more simplifications. The above cases only would apply if we have two exactly opposing half spheres, i.e. v₁ = -v₂ . Zero-convexes can be drawn as a polygon on the sphere. The corners of the polygon can be localized using the following algorithm (Nomenclature : L is a list containing all constraints that have been already processed, P is a list of the polygon corners that are determined one by one):

1. Assume there are n constraints in the convex. Start with constraint c_i, i=0.

2. Get the intersection points with convex c_j , j not in L and j not= i, which for zero constraints are given by the cross product of the two constraint vectors

          ->       ->  ->
          W_1,2 = ±|v_i X v_j|

3. Check whether any of the two intersection points lies inside all the other constraints, i.e. if

          ->   -> 
          W_1,2· v_k  > 0              k not= i,j

4. If one of the points w_1,2 does lie within all constraints, append it to the list of polygon corners P, insert i into the list of visited constraints L and continue at point 2 with i=j.

5. If a constraint i does not fulfill point 4, i.e. there are no intersection points to be found that lie within all other convexes, it means that the polygon of the convex lies completely inside or completely outside of c_i . Test for one of the already known points in P whether it is inside c_i (if P is empty, just continue and come back to this constraint later). If it is inside, drop c_i, if it is outside, drop the entire convex.

6. If there are no j not in L to be found, we are done, P contains an ordered list of all polygon corners.

William O'Mullane
Last Modified :Tuesday, March 30, 2004 at 6:59:43 PM , $Revision 1.2 $