Convert implicit surface defined with global support to compact support

In mathematics functions are sometime characterized as compactly or globally supported. I will explain what it means and how to convert a function from global to compact support in the context of implicit surface modeling (i.e. boolean modeling with implicit surfaces as objects).

Compact Vs Global in 1D

What follows is not a strict definition but should give the intuition:  a function with a compact support has its values vanishing to zero outside a specific range. For instance \( f : \mathbb R \rightarrow \mathbb R \) has a compact support if its values vanishes to zero as we go to \( -\infty \) or \( +\infty \):

bump function source wikipedia

The function above is also called a bump function. We can bound the function variations in the interval \( [-1, 1] \) which is why we say \( f \) has a compact support.

A globally supported function is a  function that never vanishes at infinity. For instance \( f(x) = x^2 \) has a global support.

Compact Vs Global in 3D for implicit surfaces

The following sections only treats implicit surfaces.

Example of compact support with Metaballs

Metaballs are defined with functions compactly supported. Indeed the scalar field is defined as the distance from the center of the Metaball by a function \( d : [0, +\infty] \rightarrow [1, 0]\) which usually looks like this:

$$ d( x) = \left (1 - min \left ( \frac{ x^2 }{ r_m^2 } , 1 \right ) \right )^4 $$
two metaballs not in contact

With \( r_m = 1\) for the radius of the Metaball. The surface of the Metaball is usually defined for every points \( \mathbf p \) such as \( d( \| \mathbf p - \mathbf c\|) = 0.5 \) with \( \mathbf c \) the center of the Metaball. The compact support of \( d \) enable us to define a 3D aligned bounding box of the scalar field. This box enclose all the none zero values of the Metaballs.

Here is for instance a nice property: if we sum two Metaballs to blend them \( f(\mathbf x) = f_0(\mathbf x) + f_1(\mathbf x) \) we have the garantee that function \( f \)'s box is equal to the union of the boxes of \( f_0 \) and \( f_1\). So we can roughly know the region of the space where a surface can appear or not.

two metaballs not in contact two metaballs with bbox and contour lines
two metaballs in contact two metaballs in contact with bbox and contout lines

Above is an example of such blending. The right figure shows contour lines of  the Metaballs as well as the associated axis aligned bounded boxes. The red box is the union of the green boxes of each Metaballs. Contour lines shows the variation of the potential. Red curves means \( f(\mathbf x) < 0.5 \) and blue \( f(\mathbf x) > 0.5 \). The black is drawn for very small values \( \epsilon << 10^{-3} \), farther the potential is null.

Example of global support with the sphere equation

The function of a sphere of radius \( r_s \), depends on the distance from the center \( \mathbf c \) of the sphere to the evaluated point \( \mathbf x \) with:

$$ f(\mathbf x) =  \| \mathbf x - \mathbf c \| - r_s = \sqrt{ (x-c_x)^2 + (y-c_y)^2 + (z-c_z)^2} - r_s $$

The surface is usually defined for every point \( \mathbf p \) such as \( f(\mathbf p) = 0 \). The support of \( f: [0, +\infty] \rightarrow [-r, +\infty] \) is global: the farther \( \mathbf x \) from \( \mathbf c \) is the bigger the value of \( f \). Its value never vanishes at \( +\infty \). As a consequence we cannot find a 3D bounded box to bound the values of \( f \). The function varies everywhere and may have interactions anywhere.

Why compact support is better than global?

In the context of implicit surface modeling (modeling objects with booleans operators) compact support has two main advantages over global support.

Speed

Compact support can be faster if properly handled. The bounding box of the implicit surface can be used to create various data structures such as octrees or bounding box hierarchies to speed up the rendering. For instance when animating objects the marching cube algorithm can re-compute only what is inside the bounding box of an object to update triangles. The ray tracing of implicit surface will be of course a lot faster, the ray traversal through the scalar field can be accelerated by intersecting the hierachy of boxes.

It is much harder to predict where the surface will be for a globaly supported scalar function. In this case bounding boxes has no obvious limits and the surface may be anywhere, especially if we use fancy blending operators between implicit surface primitives.

Compositon

The famous '\( + \)' operator used to blend Metaballs can't be used with global support functions. If we consider a sphere for instance the farther the other objects are from it the higher the potential of the sphere will be. This means that farther objects will be altered more by the sphere field. The object's surface defined by zero values  will eventually disappear as we add the sphere's values. There is no way the sum produces the expected blend for globaly supported functions unlike compact support.

There is actulally two classes of composition operators (i.e blending, union, intersection etc.) one for global support and one for compact support. It is usually harder to create new composition operators for global support functions because it means we have to handle properly the whole ambiant space. It is not rare that an operator behaves well at proximity of the implicit surface but introduces big distorsion farther away in the scalar field. Later these "invisible" distorsions can result in artefacts if other blends occurs.

Finally we can add that there is more interesting and controllable operators for compact support than global. The latest at this date would be "A Gradient-Based Implicit Blend" introduced by Olivier Gourmel & Al.

How to convert from global to compact using a map function

There is plenty of implicit surface primitives ranging from compact to global support. It would be a shame not to be able to use global support  for the reasons depicted earlier. A simple solution is to use a function \(t_r : \mathbb R \rightarrow \mathbb R \) that maps the scalar field from a global to compact support. A globaly supported primitive \( g : \mathbb R^3 \rightarrow \mathbb R\) can now be converted to a new compactly supported primitive \( f(\mathbf x) = t_r(g(\mathbf x)) \). Here is the definition and plot of \( t_r \):

$$ t_r(x)
=
\left\{
\begin{array}{ll}
  1 & \mathrm{ if } \quad x < -r \\
  0 & \mathrm{ if } \quad x >  r \\
  \frac{-3}{16}  \left(\frac{x}{r}\right)^5 + \frac{5}{8}  \left(\frac{x}{r}\right)^3 - \frac{15}{16}  \left(\frac{x}{r}\right) + \frac{1}{2} & \mathrm{
otherwise }\mbox{ ,}\\
\end{array}
\right. $$

two metaballs not in contact

The plot of the function is done for \( r = 2 \). We can see that \( t_r \) correctly maps the values of \( g \) to the new values of \( f \) with compact support. When \( g(\mathbf x) = 0\) the composition returns \( t_r( g(\mathbf x) ) = 0.5 \) as the compact support convention requires. when we go away from the surface \( g > 0 \) and has increasing values  which means \( t_r( g(\mathbf x) ) \) vanishes to zero if we reach the radius \( r \). On the contrary when we go inside \( g <0 \) and has diminishing values which means \( t_r( g(\mathbf x) ) \) will increase untill we reach the radius \( r \).

You will have to choose the radius \( r \) wisely. If \( r \) is too small then the new surface defined by \( f \) will have its innercore with constant values of ones. This is a plot of a sphere function with global support converted to a compact support with different values of \( r \):

3D sphere sphere small radius sphere medium radius sphere big radius

From left to right: the sphere, then the contour lines corresponding to the compact support from small to large radius of the parameter \( r \) (not to be confused with sphere radius which is constant). For the smaller \( r \) we observe a black disc which correspond to values equal to one. Inside the disc the gradient is null, in some application this can be problematic.

No comments

All html tags except <b> and <i> will be removed from your comment. You can make links by just typing the url or mail-address.
Spam bot question: