Chapter 1: Introduction to 3D Computer Vision

A point cloud is a set $\{\mathbf{p}_i\}_{i=1}^N$ where each $\mathbf{p}_i = (x_i, y_i, z_i) \in \mathbb{R}^3$. The storage cost is exactly $3N$ floats (plus per-point attributes). Because points are unordered, any algorithm must be permutation-invariant: if $f(\{\mathbf{p}_1, \ldots, \mathbf{p}_N\}) = y$, then $f(\{\mathbf{p}_{\sigma(1)}, \ldots, \mathbf{p}_{\sigma(N)}\}) = y$ for any permutation $\sigma$. This constraint directly motivated architectures like PointNet, which uses per-point MLPs followed by a symmetric function (max pooling).

A mesh $(V, F)$ consists of vertices $V \in \mathbb{R}^{|V| \times 3}$ and faces $F \subset \binom{V}{3}$. The Euler characteristic $\chi = |V| - |E| + |F|$ is a topological invariant: $\chi = 2$ for any closed surface homeomorphic to a sphere. For a triangle mesh, $|E| = 3|F|/2$ (each edge shared by two faces), so $|V| - 3|F|/2 + |F| = 2$. This means given $|V|$ and $|F|$, you can predict $|E|$ exactly --- any deviation indicates holes or non-manifold geometry.

A voxel grid at resolution $n$ requires $O(n^3)$ storage, but most voxels are empty. Octrees exploit this sparsity by recursively subdividing only occupied regions, reducing storage to $O(s \cdot \log n)$ where $s$ is the number of surface voxels (typically $O(n^2)$ for a smooth surface). Implicit representations define the surface as $\{\mathbf{x} : f(\mathbf{x}) = 0\}$. A signed distance function (SDF) has the property $|\nabla f(\mathbf{x})| = 1$ everywhere, meaning the gradient always points toward the nearest surface point and its magnitude gives the exact distance.