Root Finding for Raytracing (Ray and Meta-Ball Intersection) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T08:40:28Z http://mathoverflow.net/feeds/question/30087 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/30087/root-finding-for-raytracing-ray-and-meta-ball-intersection Root Finding for Raytracing (Ray and Meta-Ball Intersection) qwerty1793 2010-06-30T18:14:15Z 2010-06-30T23:55:45Z <p>The motivation behind this is to find the points of intersection between a ray and a level set of a potential function $g$, built in terms of a basic potential function $f$ (the building is explained later). This is a problem in ray tracing where the level set is known as a meta-ball. Normally, the basic potential function $f$ is of the form $\exp(-x)$ or $1/x^n$ where $n \geq 1$ and the the problem is solved by finding the roots of a (generally high order) polynomial by a numerical method. However my question is:</p> <blockquote> <p>Is there an alternative basic potential function $f$ such that the points of intersection between a ray and a level set of $g$ can always be found explicitly and without requiring numerical methods?</p> </blockquote> <p>More formally:</p> <p>Let <code>$f \colon \mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}$</code> be continuous, we say that $f$ is a basic potential function iff:</p> <p>1) $f$ is non-zero</p> <p>2) $f$ is strictly decreasing</p> <p>3) $\lim_{x \to \infty} f(x) = 0$</p> <p>Let $f$ be a basic potential function, $c_1, \ldots, c_n \in \mathbb{R}^3$ and $a_1, \ldots a_n \in \mathbb{R}$, then we build the potential function $g \colon \mathbb{R}^3 \to \mathbb{R}$ in the following way: </p> <p>$$g(x) = \sum_{i=1}^n a_i f(\left| x - c_i \right|)$$</p> <p>Let $k \in \mathbb{R}$ then $S = g^{-1}(k)$ is our level set (meta-ball).</p> <p>We describe a ray $R$ as a pair $(o, d) \in \mathbb{R}^3 \times S^3$, where $o$ is the origin of the ray and $d$ is the direction in which it is 'pointing'. Using this we may see that finding the points in $R \cap S$ is equivalent to solving $$h(t) = g(o + td) = k$$ (with $t \geq 0$)</p> <p>Traditionally in ray tracing, the choice of basic potential function $f$ would mean that this could be solved by numerical methods, but is there a basic potential function $f$ such that the solutions of $h(t) = k$ can always be found explicitly (or an alternative way of finding the points in $R \cap S$ without requiring numerical methods)?</p> http://mathoverflow.net/questions/30087/root-finding-for-raytracing-ray-and-meta-ball-intersection/30095#30095 Answer by Steven Stadnicki for Root Finding for Raytracing (Ray and Meta-Ball Intersection) Steven Stadnicki 2010-06-30T19:00:12Z 2010-06-30T19:00:12Z <p>While this isn't precisely high mathematics, I've done a fair bit of metaball modeling in the past. They're not a basic potential functions in the sense you use ($f$ is only non-zero on a bounded interval), but either the classic ease-in ease-out function $f(x) = 1+3x^2-2x^3 (x\leq1)$, $f(x) = 0 (x\geq1)$ (with $r^2$ being used as the value for $x$ here) or Wyvill's similar cubic satisfying $f(0) = 1$, $f(1) = 0$, $f'(1) = 0$, $f(1/4) = 1/2$ (so that when $r=1/2$, $f(r^2)=1/2$) allow for explicit solutions by explicitly solving the (separate) cubics on each piece of a given ray.</p> <p>More broadly, though, I have to ask why you'd rather an explicit solution than numerical methods? Keep in mind that the sqrt operation you're going to get from your floating-point processor (which is likely to be involved in most explicit solutions) is calculated by numerical methods (usually a variant of Newton's algorithm, though there are other good sqrt algorithms) on the processor itself, and likewise something like the log function is probably done with tables, linear approximations and a Newton iteration or two. Even if your own solution is explicit, somewhere behind the works some approximation is likely being done...</p>