Volume Estimation Methods

This page describes the Monte Carlo volume estimation methods implemented in Crater.rs. Monte Carlo methods were pioneered by Metropolis and Ulam 7 and have become essential tools for numerical computation in high-dimensional spaces.

Consider a scalar field $F^i:{\mathbb{R}}^{n\times m}\to {\mathbb{R}}^m$. We define the region enclosed by the surface as:

$$R^i=\{X^{ij}\in D|F^i(X^{ij})\le 0^i\}$$

Where $D$ is the domain of interest.

Monte Carlo Volume Estimation

Monte Carlo volume estimation is a probabilistic method for approximating the volume of complex regions. This method is particularly useful for high-dimensional spaces where traditional grid-based methods would suffer from the curse of dimensionality.

Algorithm Steps:

1. Generate $N$ random points uniformly distributed in domain $D$: $\{X^{ij}\}\sim \text{Uniform}(D)$
2. Evaluate the scalar field at these points: $V^i=F^i(X^{ij})$
3. Count the number of points inside the region: $C={\sum }_{i=1}^N{\mathbb{I}}^i\{V^i\le 0^i\}$
4. Compute the volume approximation: $V(R^i)\approx V(D)\cdot \frac{C}{N}$

To approximate the volume of $R^i$, we sample $N$ points $X^{ij}\in D$ from a uniform distribution, and count the fraction of points that fall inside the region:

$$\frac{V(R^i)}{V(D)}\approx \frac{{\sum }_{j=1}^N{\mathbb{I}}^i\left(F^i(X^{ij})\le 0^i\right)}{N}$$

Where:

• $V(D)$ is the known volume of the domain $D$
• $V(R^i)$ is the volume we're estimating
• ${\mathbb{I}}^i$ is the indicator function that equals 1 if the condition is true, 0 otherwise

Error Analysis

The error in this approximation decreases as $O(1/\sqrt{N})$, where $N$ is the number of points sampled. This makes it suitable for high-dimensional volume estimation where traditional grid-based methods would suffer from the curse of dimensionality.

The standard error of the volume estimate is approximately:

$${\sigma }_V\approx V(D)\sqrt{\frac{p(1-p)}{N}}$$

Where $p=\frac{V(R^i)}{V(D)}$ is the estimated proportion of the domain occupied by the region.

Alternative Methods

While Monte Carlo methods are the primary approach in Crater.rs, other volume estimation methods include:

• Grid-based methods: Discretize space into regular grids (suffers from curse of dimensionality)
• Analytical methods: Exact solutions for simple primitives (limited applicability)
• Adaptive sampling: Concentrate samples in regions of high curvature or complexity

Monte Carlo methods provide the best balance of generality, accuracy, and performance for complex CSG geometries.