Search ACM DL

Search TOG

enter search term and/or author name

Devendra Kalra and Alan H. Barr, *Guaranteed Ray Intersections with Implicit Surfaces*, Computer Graphics (SIGGRAPH '89 Proceedings), vol. 23, July 1989, p. 297-306

*submitted by Andrei Sherstyuk (ash@cs.monash.edu.au), July 11, 1998, (approval pending):*

I found a typo in the math appendix of the paper, apparently introduced during typesetting. In the paper, there is a brief description how to compute L and G for Gaussian potentials, a.k.a. Blinn's blobs:

f(r) = B exp {-A r^2},

where r^2 is a squared distance to the center of the blob. (page 305).

I did not check the computations of L (the Lipschitz constant for the functions itself). However, computations of G must be corrected in the following way: the 2nd directional derivative h(t) is given as:

h = -2.0*AB*exp(-A*r2)*(k1 - A*(k2 + t*k1)*(k2 + t*k1));

The correct expression is:

```
h = -2.0*AB*exp(-A*r2)*(k1 - 2.0*A*(k2 + t*k1)*(k2 + t*k1));
^^^
```

The result of this typo is that the G-values for each blob come out smaller than they really are. This may cause the algorithm to underestimate the rate of change of the field function and start closing on the root in the interval where the function is not monotonic.

In principle, this could cause divergence (if Newton's method is used) or the first intersection may be missed (if regular falsi is used, which may converge to the second root).

In practice, with all datasets that I tried this bug does not surface. The reason is the following: the collective G-value for a sum of several blobs is calculated as a sum of G-values computed for individuals blobs. This is a very conservative result. In a way, the algorithm is very self-protective and always sets the safety limits basing on the worst-case behavior of the collective field function, which in practice (almost) never happens. Therefore, a little loosening of G only helps the speed at the expense of safety.

However, since so much math is involved already, it makes sense to do it by the rules, which makes the algorithm absolutely reliable.

To finish, the plot of h(t) (Figure 21) should be viewed upside-down. This minor inconvenience is not really important for the algorithm.

Eric Haines, On-Line Editor / erich@acm.org

Last change: *October 22, 1998*