Root Finding for Raytracing (Ray and Meta-Ball Intersection)

2010-06-30T18:14:15Z

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:

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?

More formally:

Let $f \colon \mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0} $ be continuous, we say that $f$ is a basic potential function iff:

1) $f$ is non-zero

2) $f$ is strictly decreasing

3) $\lim_{x \to \infty} f(x) = 0$

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:

$$g(x) = \sum_{i=1}^n a_i f(\left| x - c_i \right|)$$

Let $k \in \mathbb{R}$ then $S = g^{-1}(k)$ is our level set (meta-ball).

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$)

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)?

Answer by Steven Stadnicki for Root Finding for Raytracing (Ray and Meta-Ball Intersection)

2010-06-30T19:00:12Z

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.

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

Root Finding for Raytracing (Ray and Meta-Ball Intersection) - MathOverflow

Root Finding for Raytracing (Ray and Meta-Ball Intersection)

Answer by Steven Stadnicki for Root Finding for Raytracing (Ray and Meta-Ball Intersection)