Scalar Fields, Isosurfaces and Constructive Solid Geometry

This page provides the mathematical foundation for this library. Understanding of the notation, conventions and constructions in this page is integral to effective use the advanced methods the library has to offer.

Tensor Notation

This library employs tensor notation throughout. Understanding the notation conventions will help clarify the mathematical exposition.

• Objects with no indices are scalar-valued. (e.g. $\lambda$, $f:{\mathbb{R}}^n\to \mathbb{R}$)
• Objects with one or more indices are tensor-valued. (e.g. $x^i$, $X^{ij}$, $F^i(X^{ij}):{\mathbb{R}}^{m\times n}\to {\mathbb{R}}^m$)
• Rank-$1$ tensors (vectors) are represented in lower-case, rank-$r$ where $r>1$ tensors use upper-case. (e.g. $x^j$, $X^{ij}$)
• Tensor operations use Einstein summation notation, eliding the summation notation (e.g. $x^j{x}_j={\sum }_j{x}^j{x}_j$)
• Element-wise or broadcasted multiplication is indicated by juxtaposition (e.g. $x^i{y}^i$). Shared indices indicate broadcasted multiplication (e.g. $X^{ij}{y}^i$ is the action of multiplying each row of $X^{ij}$ by the $i$-th element of $y^i$).
• The spacial dimension is indexed by $j$, and the batch dimension is indexed by $i$. (e.g. $x^j$, $X^{ij}$)

Scalar Fields and Isosurfaces

Consider a scalar-valued function $f:{\mathbb{R}}^n\to \mathbb{R}$. This function is a field defined over a domain $D\subset {\mathbb{R}}^n$. An isosurface of $f$ is the set of points $x^j\in D$ such that $f(x^j)=c$, where $c\in \mathbb{R}$ is a constant. Without loss of generality, we study $c=0$ only.

Naturally, we define the surface of $f$, $\partial f(D)$, as the set of points $x^j\in D$ such that $f(x^j)=0$.

$$\partial f(D)=\{x^j\in D\mid f(x^j)=0\}$$

Classifying vectors as inside or outside the region enclosed by $\partial f(D)$ is a common task in computer graphics. Specifically, a vector is inside the surface if $f(x^j)<0$ and outside the surface if $f(x^j)>0$.

Batch Processing with Tensors

In the form above, $f$ operates sequentially over vectors $x^j\in D$. To enable batch evaluation of $f$, we define a tensor-valued function $F^i:{\mathbb{R}}^{m\times n}\to {\mathbb{R}}^m$.

$$F^i(X^{ij})=v^i$$

where $v^i$ is a rank-$1$ tensor with length $m$. Concretely, $F^i$ satisfies the following properties:

$$F^k(X^{kj})=f(x^j)\forall k\in [1,m]\text{ with }{x}^j=X^{kj}$$ $$\frac{\partial F^i}{\partial X^{kj}}={\delta }^{ik}\frac{\partial F^i}{\partial X^{ij}}$$

where ${\delta }^{ik}$ is the Kronecker delta.

The first property states that $F^i$ is equivalent to evaluating $f$ over each row of $X^{ij}$ independently.

The second property states that the Jacobian of $F^i$ with respect to our choice of input is block diagonal, meaning each output row is a function of only its corresponding input row.

For the remainder of this work, we opt to use our batch, tensor-valued formulation of $F^i$ for all computations.

Transformations

Any function $T^i:{\mathbb{R}}^{m\times n}\to {\mathbb{R}}^{m\times n}$ can be used to perform covariant transformations on our scalar fields, without having to change our definition of $F^i$.

$$F^i(X^{ij})\mapsto F^i(T^i(X^{ij}))$$

Intuitively, the transformation is not on $F^i$, but on the domain of $F^i$.

Concretely, we can implement common transformations on our scalar fields by choosing an appropriate $T^i$.

Translation

Translation can be written as a tensor-valued function $T^i:{\mathbb{R}}^{m\times n}\to {\mathbb{R}}^{m\times n}$ that takes a tensor $X^{ij}\in {\mathbb{R}}^{m\times n}$ and returns a translated tensor $T^i(X^{ij})\in {\mathbb{R}}^{m\times n}$.

$$T^i(X^{ij})=X^{ij}-t^j$$

where $t^j\in {\mathbb{R}}^n$ is the translation vector.

Scaling

Scale can be written as a tensor-valued function $S^i:{\mathbb{R}}^{m\times n}\to {\mathbb{R}}^{m\times }$ that takes a tensor $X^{ij}\in {\mathbb{R}}^{m\times n}$ and returns a scaled tensor $S^i(X^{ij})\in {\mathbb{R}}^{m\times n}$.

$$S^i(X^{ij})=X^{ij}{s}^j$$

where $s^j\in {\mathbb{R}}^n$ is the scale factor.

Rotation

A general $N$-dimensional coordinate rotation can be written as an operator $R^i:{\mathbb{R}}^{m\times n}\to {\mathbb{R}}^{m\times n}$ that takes a tensor $X^{ij}\in {\mathbb{R}}^{m\times n}$ and returns a rotated tensor $R^i(X^{ij})\in {\mathbb{R}}^{m\times n}$ and $R^i\in SO(n)$.

Rotations like $R^i$ can be represented by a sequence of individual plane rotations. A plane rotation is a rotation in a 2D plane spanned by two coordinate axes, $a$ and $b$, and is parameterized by a rotation angle ${\theta }_{ab}$. Call this plane rotation $G(a,b,{\theta }_{ab})$. Then, the general $N$-dimensional rotation can be written as a product of $N(N-1)/2$ plane rotations.

$$R^i=\prod _{a=2}^N\prod _{b=1}^{a-1}G(a,b,{\theta }_{ab})$$

Intuitively, $G(a,b,0)$ is the identity tensor.

CSG Operations

The fundamental object in CSG is the Region, which is defined as the set of points $x^j\in D$ such that $f(x^j)\le 0$. Regions are combined using the set-theoretic operations of union, intersection, and difference 4. Mathematically, these operations are defined as the following tensor:

$$\begin{array}{rl}{F}^i\cup G^i& =\max (F^i,G^i)\\ F^i\cap G^i& =\min (F^i,G^i)\\ F^i\setminus G^i& =F^i\cap -G^i\end{array}$$

In direct set notation, these composite Regions are defined as follows:

$$\begin{array}{rl}{R}_1\cup R_2& =\{x|F_1(x)\le 0\text{ or }{F}_2(x)\le 0\}\\ R_1\cap R_2& =\{x|F_1(x)\le 0\text{ and }{F}_2(x)\le 0\}\\ R_1\setminus R_2& =\{x|F_1(x)\le 0\text{ and }{F}_2(x)>0\}\end{array}$$

These operations align with our intuitive understanding of set theory over ${\mathbb{R}}^n$, but they are expressed solely in terms of scalar fields.

CSG Algebras

In practice, one is free to override and redefine these operations. We define an Algebra as an implementation of the above contract. This is an algebra in the mathematical sense, as well as in our algorithms. The theoretical foundation for R-functions used in CSG operations was established by Rvachev 3.

$$\mathbb{A}=(P(D),\cup ,\cap )$$

where $P(D)$ is the power set of $D$.

Advanced CSG Operations

Beyond the basic operations, crater.rs implements more sophisticated ways to combine scalar fields.

Differentiable Approximations

In practice, one may wish to use a differentiable approximation of the basic CSG operations. These methods provide smooth blending capabilities as described in the Function Representation literature 2.

$$\begin{array}{rl}{F}^i\cup G^i& =\frac{F^i+G^i+\sqrt{(F^i{F}^i)+(G^i{G}^i)-2{\alpha }^i(F^i{G}^i)}}{1^i+{\alpha }^i}\\ F^i\cap G^i& =\frac{F^i+G^i-\sqrt{(F^i{F}^i)+(G^i{G}^i)-2{\alpha }^i(F^i{G}^i)}}{1^i+{\alpha }^i}\end{array}$$

where ${\alpha }^i$ is a parameter that controls the smoothness of the operation. ${\alpha }^i=1^i$ reduces to the original min-max operations.

Blending

One such custom CSG algebra enables continuous blending between two regions.

The blending function is defined as follows, and is added to the outputs of both the $\cup$ and $\cap$ operators.

$$\varphi (f_1,f_2)=\frac{a_0}{1+(f_1/a_1{)}^2+(f_2/a_2{)}^2}$$