Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.