Unusual ray tracing

2010-01-20T18:54:59Z

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 by fuzzytron for Unusual ray tracing

2010-01-21T00:37:51Z

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.

Unusual ray tracing - MathOverflow

Unusual ray tracing

Answer by fuzzytron for Unusual ray tracing