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}}$.


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?

  • $\begingroup$ Your question is probably a borderline one for this forum. And it's also unclear. Do you want light rays to travel on ellipses, is that what you mean? $\endgroup$ – Ryan Budney Jan 20 '10 at 19:24
  • 1
    $\begingroup$ Yes. The details depend on how you describe the ellipse, but but most sane choices this reduces to the solution of a quadratic equation. This is mostly not MO-material, really. The faq lists at mathoverflow.net/faq#whatnot several other places where you will surely get help. $\endgroup$ – Mariano Suárez-Álvarez Jan 20 '10 at 20:11
  • $\begingroup$ I have rewritten the question for clarity. $\endgroup$ – Daniel Jan 20 '10 at 20:13

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.


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.