Unusual ray tracing

Question

Background

Ray tracing is very common in computational geometry and the problem is then to find the point of intersection between the equation of a line and the equation of a plane in 3D.

The parametric form of the line is given by

$\mathbf{p}_\mathrm{line}=\mathbf{p}_\mathrm{a} + \xi (\mathbf{p}_\mathrm{b}-\mathbf{p}_\mathrm{a})$

and the plane can be defined by

$\mathbf{p}_\mathrm{plane} \cdot \mathbf{n}+\mathrm{d}=0$,

where $\mathbf{p}_\mathrm{plane}$ is a point on the plane and $\mathbf{n}$ is the normal vector to the plane.

Combining these two equations $(\mathbf{p}_\mathrm{line}=\mathbf{p}_\mathrm{plane})$ gives a convenient expression for the desired point from

$\xi=\frac{-\mathrm{d}-\mathbf{p}_\mathrm{a} \cdot \mathbf{n}}{(\mathbf{p}_\mathrm{b}-\mathbf{p}_\mathrm{a}) \cdot \mathbf{n}}$.

---

Question

I now consider the problem of finding the intsersection(s) between an ellipse and a plane in 3D. Is there an effective way to perform this without an iterative scheme?

Answer 1

The sets you mention (plane, ellipse) can be expressed as the zero sets of certain polynomial functions; you are asking about the set on which both of these polynomials vanish simultaneously -- this is a basic question in algebraic geometry. One common computational solution is to apply Buchberger's algorithm for computing a Gröbner basis for the corresponding ideal (the basis will give an explicit description of the zero set). An excellent resource on this subject -- even if you have no background in algebraic geometry -- is the book "Ideals, Varieties, and Algorithms" by David Cox, John Little, and Donal O'Shea. Additionally, many computer algebra systems (such as Mathematica) provide implementations of these kinds of algorithms.