Unusual ray tracing - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T00:27:41Z http://mathoverflow.net/feeds/question/12442 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/12442/unusual-ray-tracing Unusual ray tracing Daniel 2010-01-20T18:54:59Z 2010-01-21T00:37:51Z <p><strong>Background</strong></p> <p>Ray tracing is very common in computational geometry and the problem is then to find the point of intersection between the equation of a <strong>line</strong> and the equation of a <strong>plane</strong> in <strong>3D</strong>.</p> <p>The parametric form of the line is given by</p> <p><code>$\mathbf{p}_\mathrm{line}=\mathbf{p}_\mathrm{a} + \xi (\mathbf{p}_\mathrm{b}-\mathbf{p}_\mathrm{a})$</code></p> <p>and the plane can be defined by</p> <p><code>$\mathbf{p}_\mathrm{plane} \cdot \mathbf{n}+\mathrm{d}=0$</code>,</p> <p>where <code>$\mathbf{p}_\mathrm{plane}$</code> is a point on the plane and <code>$\mathbf{n}$</code> is the normal vector to the plane.</p> <p>Combining these two equations <code>$(\mathbf{p}_\mathrm{line}=\mathbf{p}_\mathrm{plane})$</code> gives a convenient expression for the desired point from</p> <p><code>$\xi=\frac{-\mathrm{d}-\mathbf{p}_\mathrm{a} \cdot \mathbf{n}}{(\mathbf{p}_\mathrm{b}-\mathbf{p}_\mathrm{a}) \cdot \mathbf{n}}$</code>.</p> <p><hr /></p> <p><strong>Question</strong></p> <p>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?</p> http://mathoverflow.net/questions/12442/unusual-ray-tracing/12470#12470 Answer by fuzzytron for Unusual ray tracing fuzzytron 2010-01-21T00:37:51Z 2010-01-21T00:37:51Z <p>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 "<a href="http://www.amazon.com/Ideals-Varieties-Algorithms-Computational-Undergraduate/dp/0387946802" rel="nofollow">Ideals, Varieties, and Algorithms</a>" by David Cox, John Little, and Donal O'Shea. Additionally, many computer algebra systems (such as <a href="http://www.wolfram.com/products/mathematica/index.html" rel="nofollow">Mathematica</a>) provide implementations of these kinds of algorithms.</p>