The blob is coming !!

Posted: 19 Sep 2013 19:30
Tags: blobby

first.jpg

… in next XRT version.

Definition

Blobby objects belong to the family of implicit surfaces. That is, instead of being specified explicitely with an array of points like a polygon mesh or a subdivision surface, a blobby surface is defined by a field function $f(x,y,z)$ that is equal to a threshold value at every point on the surface.

A well-known implicit surface is the sphere with center at the origin and radius r, which is $x^2+y^2+z^2=r^2$. You can find many more examples of implicit surfaces here. XRT algorithm for rendering generic implicit surfaces has been detailed in a previous post. Most of the implicit surfaces have an infinite domain (the range of values that $f(x,y,z)$ can take) and combining them does not lead to anything interesting (for example, if we add two sphere implicit surfaces with two different centers, the resulting surface is a void because, at every point in space, the combined implicit function value will likely be superior to the threshold value)

We can get much more interesting effects when using bump functions. A bump function is smooth (its derivatives are continuous at all orders) and has compact support (in broad terms, the part of the (x,y,z) space where $f(x,y,z)$ is not 0 is a box).

pairs.jpg

In the above example, two such fields are added and their centers are made closer and closer until they seem to swallow each other. What happens? Things get much clearer when we draw the iso-potentials (Image credits).

Image Unavailable
Disjoint supports
Image Unavailable
Overlapping supports

When supports overlap, potentials sum, hence the resulting shape.

A blobby object is a combination of elementary bump functions (which define primitive fields like spheres, segments, boxes … ) through a hierarchy of operations on them (add, sub, div, mul, neg, min, max) resulting in all kinds of rounded objects.

Intersection algorithm

As usual, I have looked at what my glorious predecessors have done but I have not found much. Regarding open source implementations, the most comprehensive is Aqsis's one: blobbies are tesselated into polygon meshes using J. Bloomenthal's implicit surface polygonizer [1]. Because I am a bit prejudiced against tesselation (mostly because there is always a trade-off between accuracy and memory space), I prefer direct algorithms. Unfortunately, the litterature on that subject is quite scarce. Worse, every algorithm seems have restrictions either on the shapes or on the supported operations (usually blending), like for instance [3] (that certainly does not imply I think this is a bad work).

Therefore, a fresh look at the problem was needed. Here is my small contribution.

Because a blobby is an implicit surface, the interval-based bisection algorithm used to raytrace implicit surfaces [2] applies.


However, because interval arithmetic is expensive and because a blobby is built from hundreds or thousands field primitives combined in a tree of operations, the repeated evaluation of the whole field function over an interval is awfully expensive. Fortunately, two key optimisations come to the rescue.

First, for most primitive field functions, it is possible to analytically compute the resulting interval on a given segment in 3D space. This way, the result is much tighter than the direct use of interval arithmetic.

The major optimization stems from the fact that primitive field functions have a compact support. This means that any given ray is likely to hit only a very limited subset of all blobby primitives. Before starting bisection, the ray is tested against the blobby bounding box. This gives a confidence interval where the ray can potentially hit the blobby. All primitives (and then all nodes in the tree) are evaluated against this interval. All leaves and nodes which are always 0 on the interval can be safely discarded which leads to a drastic simplification of the tree. Because of the inclusion property of arithmetic interval, we are guaranteed to compute accurate values on any subdivision of the confidence interval using this tree. This trimmed down (and much faster to evaluate) tree is then used in the bisection. The expensive tree needs to be evaluated only once per ray.

That's all for now. I'll give more details on the available field functions in the next post.

Bibliography
1. J. Bloomenthal, "An Implicit Surface Polygonizer", Graphics Gems IV, 1994
2. A. Knoll, Y. Hijazi, C. D. Hansen, I. Wald, and H. Hagen. "Interactive ray tracing of arbitrary implicit functions". In Proceedings of the 2007 Eurographics/IEEE Symposium on Interactive Ray Tracing, 2007.
3. O. Gourmel, A. Pajot, M. Paulin, L. Barthe, and P. Poulin, "Fitted BVH for Fast Raytracing of Metaballs". Computer Graphics Forum, (Proc. Eurographics '10), 29 (2), pp. 281-288, May 2010

Rate this post:

rating: 0+x

Comments: 0