Before my question proper, a little background: I'm wanting to optimise some computer rendering by eliminating the drawing of things that aren't visible given the current view.
Suppose we have a sphere. Consider a grid of points on its surface, lying on longitude and latitude lines, equally divided around the sphere. (i.e. think of a grid of points, but instead of X and Y, we have longitude and latitude.) There are points at A unique longitudes and B unique latitudes, and therefore A(B – 2) + 2 points on the sphere.
Suppose your eye is positioned right at the centre of the sphere. Your eye has a looking 'through' a rectangular aperture with horizontal field of view M and vertical field of view N. It is looking at a point on the sphere of longitude G and latitude H (such that -90 <= H <= 90).
Which of the aforementioned points on the sphere are visible in this situation? Looking for a reasonably quick computation of this (i.e. runtime efficient).
(The harder part of this problem is the variance in latitude, rather than longitude — for all intents and purposes, we could assume the eye is looking at longitude 0 if we want.)
Best Answer
First you solve the problem by any means at all, and then you see how to optimize the solution for computation. I can do the first part, and I’ll leave the second part to @occulus.
This is a simple problem in spherical trigonometry, once you look at it close enough, and I managed to find a kind of a solution by that method. But since @occulus seemed to want a criterion to decide whether a point on the sphere was or was not within the equiangular quadrilateral (not a rectangle!) that’s gotten by projecting the rectangular window onto the sphere from a point (the eye) at the center of the sphere, it seems to me that a nontrigonometric approach is called for.
The first first thing to observe is that we can always turn a (long,lat) pair of numbers into the Cartesian coordinates of a point in space, say at unit distance from the origin. So, if the $(0,0)$-point of the sphere is on the $x$-axis and the poles are on the $z$-axis, the Cartesian coordinates of $(\theta,\rho)$ are $(\sin\rho\cos\theta,\sin\rho\sin\theta,\cos\rho)$, where $\rho$ is the “colatitude”, namely $\pi/2-$ lat., and $\theta$ would be the longitude measured counterclockwise through the polar axis viewed from the north.
I’m assuming, though @occulus did not make it explicit, that the rectangular window is positioned so that its center is the closest point to the eye. Call the width of the rectangle $2w$, and the height $2h$, and suppose that it’s a distance of $d$ from the eye. Then the apparent half-width $\omega$ has $\tan\omega=w/d$, and the apparent half-height $\eta$ has $\tan\eta=h/d$.
Now let’s do as @occulus suggests, and put the center of the rectangle on the meridian of longitude $0$, I’ll call this great circle $g$ (for Greenwich), and suppose, as I think the poster does, that the rectangle is “level with respect to the equator”, so that its vertical axis of symmetry coincides with $g$. Let’s suppose also that the horizontal axis of symmetry of the rectangle crosses the meridian $g$ at the point of colatitude $\rho$. In the discussion that follows, I’m thinking of everything interesting happening in the northern hemisphere, and my own mental pictures are based on this, so that $0<\rho<\pi/2$. In the drawing below, I’m thinking of looking at the sphere from a point outside it, on the $x$-axis, so above the equator and the meridian $g$.
We have six great circles: the unlabeled horizontal axis of symmetry, the vertical axis of symmetry $g$, the “upper horizontal edge” $h_1$, the lower horizontal edge $h_2$, and the vertical edges $v_1$ and $v_2$. One sees that $h_1$ crosses $g$ orthogonally at colatitude $\rho-\eta$, and $h_2$ crosses similarly at colatitude $\rho+\eta$. The efficient way to describe a great circle is by its pole (there are actually two!). I’ll use $G=(0,1,0)$ as the pole of $g$, so that a point $P$ is on $g$ if and only if $P\cdot(0,1,0)=0$. And $P$ is to the left of $g$ if and only if the dot product is negative. Similarly, you see that the pole $H_1$ of $h_1$ has longitude $\pi$ and colatitude $\pi/2-\rho+\eta$, while the pole $H_2$ of $h_2$ is at long. $=\pi$, colat. $=\pi/2-\rho-\eta$. The corresponding Cartesian coordinates are $H_1=(\cos(\rho-\eta),0,-\sin(\rho-\eta))$, and of $H_2$ the same, with $\eta$ replaced by $-\eta$. So you see that for a point $P$ to be in our rectangle, it must at least have $P\cdot H_1\le0$, $P\cdot H_2\ge0$.
But what are the poles $V_1$ and $V_2$ of $v_1$ and $v_2$, respectively? You see that you get $v_2$ by rotating $g$ counterclockwise by an amount of $\omega$, only not with respect to the north pole, but with respect to the pole of the horizontal axis of symmetry, whose coordinates are just $(-\cos\rho,0,\sin\rho)$. If I did the computations correctly, we get $V_1=(\sin\omega\sin\rho,\cos\omega,-\sin\omega\cos\rho)$, and $V_2=(-\sin\omega\sin\rho,\cos\omega,\sin\omega\cos\rho)$. Then the remaining inequalities are $P\cdot V_1\ge0$, $P\cdot V_2\le0$. The simultaneous satisfaction of the four inequalities should be equivalent to $P$ being visible through the window.