3
$\begingroup$

If I have an ellipsoid in three dimensions (actually an oblate spheroid, the Earth).

$$\frac{x^2+y^2}{a^2} + \frac{z^2}{b^2} = 1$$

And a ray represented by the point $P = (x_p, y_p, z_p)$ with direction vector $D = (x_d, y_d, z_d)$

I can form an ellipse by intersecting the plane formed by the ray and the origin with the ellipsoid. How can I find the points on that ellipse (there should be two I believe), where the normal vector is perpendicular to the ray?

I'm effectively looking for the furthest points on the ellipse that are "visible" to the origin of the ray, $O$. Since there's two solutions, I'd like the one closer to the ray.

Here's a picture that I hope clarifies, after forming an ellipse by intersecting a plane with the ellipsoid, I want to find point A where the normal vector is perpendicular to the line containing the point and the ray origin.

diagram

I believe this is equivalent to finding the tangent line that contains the point P.

$\endgroup$
  • $\begingroup$ Is the ray a line a through the origin? If that's the case, the plane you speak of is not well-defined. $\endgroup$ – Fimpellizieri May 11 '16 at 2:13
  • $\begingroup$ Do you know how to find the tangent plane at a point? With this you can find the normal vector at a point. I think it's really ugly though $\endgroup$ – lordoftheshadows May 11 '16 at 2:19
  • $\begingroup$ It is not clear what you are asking, a ray is described by an origin and a direction. Does $(x_l,y_l,z_l)$ stand for the origin or the direction? Also your ellipse looks strange, should the denominator be $a^2$ and $b^2$? Assume that is the case and you are looking for the locus of point $(x,y,z)$ on $\frac{x^2+y^2}{a^2} + \frac{z^2}{b^2} = 1$ whose normal is perpendicular to the ray joining $(x_l,y_l,z_l)$ and $(x,y,z)$, the locus will be the intersection of the ellipse and the plane $\frac{xx_l + yy_l}{a^2} + \frac{zz_l}{b^2} = 1$. $\endgroup$ – achille hui May 11 '16 at 4:09
  • $\begingroup$ Does the plane "formed by the ray and the origin refer to the plane through the origin which has the normal vector $L$? $\endgroup$ – coffeemath May 11 '16 at 4:10
  • $\begingroup$ @Fimpellizieri no in my case, I'll be doing a test for ray-ellipse intersection before finding these points, so any ray that goes through the origin will intersect the ellipsoid and not be considered. $\endgroup$ – gct May 11 '16 at 12:54
2
$\begingroup$

The plane through the ray and the origin intersects your ellipsoid to form a planar ellipse. To find this planar ellipse one must establish a basis vector on the plane such that any point on the plane can be represented by two parameters ($\alpha$ and $\beta$). $$ \vec{r} = \alpha \vec{p} + \beta \vec{d} $$

The ellipse on the plane is now given by the equation

$$ \alpha^2 C_{11} + 2 \alpha\beta C_{12} + \beta^2 C_{22} = 1 $$

$$ \pmatrix{\alpha \\ \beta \\ 1}^\top \pmatrix{C_{11} & C_{12} & \\ C_{12} & C_{22} & \\ & & -1} \pmatrix{\alpha \\ \beta \\ 1} =0 $$

where $$\begin{align} C_{11} &= \frac{x_p^2}{a^2} + \frac{y_p^2}{a^2} + \frac{z_p^2}{b^2} \\ C_{22} &= \frac{x_d^2}{a^2} + \frac{y_d^2}{a^2} + \frac{z_d^2}{b^2} \\ C_{12} &= \frac{x_p x_d}{a^2} + \frac{y_p y_d}{a^2} + \frac{z_p z_d}{b^2} \end{align} $$

Now for the fun part. To be perpendicular to the ray the point $\vec{r}$ must obey the projection $$ \vec{d}^\top (\vec{r}-\vec{p}) =0 $$

From the expansion of $\vec{r}$ in terms of the planar coordinates $\alpha$ and $\beta$ this projection is used to solve for

$$ \alpha = 1- \frac{\vec{d}^\top \vec{d}}{\vec{d}^\top \vec{p}} \beta = 1-\frac{x_d^2+y_d^2+z_d^2}{x_d x_p + y_d y_p + z_d z_p} \beta = 1- \lambda \, \beta $$

So given any distance along the ray $\beta$ the 3D position of the point is $\vec{r} = (1-\lambda \,\beta) \vec{p} + \beta \vec{d} $ where $\lambda$ is the fixed ratio $\lambda = \frac{x_d^2+y_d^2+z_d^2}{x_d x_p + y_d y_p + z_d z_p}$.

The points on the ellipse that are perpendicular to the ray solve the equation

$$ (1-\lambda\,\beta)^2 C_{11} + 2 (1-\lambda\,\beta)\beta C_{12} + \beta^2 C_{22} = 1 \\ (C_{11} \lambda^2 -2 C_{12} \lambda + C_{22}) \beta^2 + 2 (C_{12}-C_{11} \lambda) \beta + (C_{11-1}) = 0 $$

This has two solutions (as expected)

$$ \beta = \frac{C_{11} \lambda-C_{12} \pm \sqrt{ C_{11} (\lambda^2-C_{22}) + C_{12}^2 -2 C_{12} \lambda + C_{22}}}{C_11 \lambda^2 -2 C_{12} \lambda + C_{22}} $$

And the back substitution

$$ \alpha = 1 - \lambda\, \beta \\ \vec{r} = \alpha \vec{p} + \beta \vec{d} $$

Edit 1 To find the lines tangent to the planar ellipse, and passing through P you do the following:

  1. The planar coordinates of P are $(\alpha=1,\beta=0)$, or in homogeneous coordinates $$P=\pmatrix{1,& 0,& 1}$$
  2. The homogeneous coordinates of the planar ellipse are $$C=\left| \matrix{C_{11} & C_{12} & \\ C_{12} & C_{22} & \\ & & -1} \right|$$
  3. The polar line of P is $L=C\,P$ $$L = \left[ \matrix{C_{11}, & C_{12},& -1} \right]$$
  4. The polar line intersects the ellipse at the tangent points $Q_1$ and $Q_2$. To find these points form the equation of the line $C_{11} \alpha + C_{12} \beta - 1 =0$ and plug it into the ellipse equation to find $$Q_1 = \pmatrix{ 1 + \tfrac{C_{12} \sqrt{C_{11}-1}}{K}, & - \tfrac{C_{11} \sqrt{ C_{11}-1 }}{K}, & C_{11} }$$ $$Q_2 = \pmatrix{ 1 - \tfrac{C_{12} \sqrt{C_{11}-1}}{K}, & \tfrac{C_{11} \sqrt{ C_{11}-1 }}{K}, & C_{11} }$$ where $K=\sqrt{C_{11} C_{22}-C_{12}^2}$.

  5. The tangent line coordinates are $T_1 = C \,Q_1$ and $T_2 = C \, Q_2$ $$ T_1 = \left[ \matrix{ C_{11}, & C_{12} -K \sqrt{C_{11}-1} , & -C_{11} } \right] $$ $$ T_2 = \left[ \matrix{ C_{11}, & C_{12} +K \sqrt{C_{11}-1} , & -C_{11} } \right] $$

  6. In equation form the tangent lines are $$ (C_{11}) \alpha + (C_{12} - K \sqrt{C_{11}-1}) \beta - C_{11} = 0 $$ $$ (C_{11}) \alpha + (C_{12} + K \sqrt{C_{11}-1}) \beta - C_{11} = 0 $$

$\endgroup$
  • $\begingroup$ Brilliant answer! I've seen some of your other answers and was hoping you'd see my question. $\endgroup$ – gct May 16 '16 at 13:01
  • $\begingroup$ Actually, I'm not sure this is quite what I need. I don't necessarily want the points on the ellipse perpendicular to the ray itself, rather I want the points on the ellipse whose tangent lines contain the point P. This is for a ray caster, and in particular when a ray misses the ellipsoid, I wish to find the point furthest away which is "visible" to the origin of the ray (the viewpoint), which are the aforementioned tangent points. $\endgroup$ – gct May 16 '16 at 13:15
  • $\begingroup$ Also I'm curious how you got the initial equation for the ellipse, is that just what falls out when you intersect the ellipsoid and plane in homogeneous coordinates? $\endgroup$ – gct May 16 '16 at 13:30
  • $\begingroup$ @gct I took the ellipsoid equation (in terms of xyz) and plugged in $\vec{r} = (x,y,z)$ to get an equation in terms of $\alpha$, $\beta$. $\endgroup$ – ja72 May 16 '16 at 14:16
  • $\begingroup$ that makes perfect sense, thanks. What do you think about finding the tangent points I mentioned above? My thought is that $C*l$ gives you the tangent line for a point $l$ on the conic. But actually finding the tangent point $l$ given that the tangent line must contain $\vec{p}$ eludes me. $\endgroup$ – gct May 16 '16 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.