Geometry

1.1 Basic Geometric Entities

1.1.1 Curve

Applications include camera paths, animation curves, and vector fonts.

Spline: Interpolation vs. approximation.

Bézier Curve:

\[ \mathbf{b}^n(t) = \sum_{i=0}^{n} \mathbf{b}_i B_i^n(t), \qquad t\in[0,1]. \]

\[ B_i^n(t) = \binom{n}{i}t^i(1-t)^{n-i} = \frac{n!}{i!(n-i)!}t^i(1-t)^{n-i}. \]

de Casteljau Algorithm: To evaluate Bézier curves, we can use the de Casteljau algorithm, which is a recursive method that linearly interpolates between control points.

Properties of Cubic Bézier Curves:

  • Endpoint interpolation
  • Endpoint tangents
  • Affine invariance
  • Convex hull property

Higher-Order Bézier Curves: Very hard to control, in practice, Piecewise cubic Bézier is the most common technique (chain many low-order curves).

Continuity of Piecewise Bézier Curves: \(C^1\) continuity requires

\[ \mathbf a_n=\mathbf b_0=\frac{1}{2}\left(\mathbf a_{n-1}+\mathbf b_1\right). \]

General Spline Formulation:

\[ Q(t) = \mathbf{G}\mathbf{B}\mathbf{T}(t). \]

Here, \(\mathbf{G}\) contains the geometry, \(\mathbf{B}\) is the spline basis, and \(\mathbf{T}(t)\) is the power basis.

1.1.2 Surface

Bézier Surfaces: Smoothly interpolate between a set of points \(\mathbf{P}_i\):

\[ \mathbf{s}(u,v) = \sum_{i=0}^{m} \sum_{j=0}^{n} \mathbf{p}_{i,j} B_i^m(u) B_j^n(v). \qquad (u,v)\in[0,1]^2 \]

Separable 1D de Casteljau Algorithm

1.2 Explicit Geometric Representations

3D representations: Rasterized form vs. geometric form.

1.2.1 Taxonomy

Origin-dependent: Acquired real-world object, Modeling “by hand”, Procedural modeling.

Application-dependent: Needs to be stored in the computer, Creation of new shapes, Operations, Rendering, Animation.

Multiview 3D representation: No explicit 3D geometry, Multiview reconstruction possible (nontrivial though), Viewpoint matters a lot.

Depth map: Incomplete 3D, Resolution issue, Object properties matter.

Volumetric representation: Storage and computation cost, Obvious artifacts.

1.2.2 Point Cloud

Point Cloud Representation: only points, no connectivity. A point cloud is a collection of 3D coordinates \((x,y,z)\), optionally with a normal vector. Points with orientation (normal directions) are called surfels.

Acquiring Point Clouds:

  • Techniques: laser, infrared, and stereo.
  • Challenges: resolution, occlusion, noise, and registration.

Light-weight Shape Representation: Compact to store, Generally easy to build algorithms.

Sampling Methods: Uniform Sampling, Farthest Point Sampling.

1.2.3 Mesh Structure

Polygonal Mesh:

\[ M=\langle V,E,F\rangle \]

where:

  • \(V\): vertices
  • \(E\): edges
  • \(F\): faces

Manifold Mesh:

  1. Each edge is incident to one or two faces.
  2. Faces incident to a vertex form a closed or open fan.

Techniques to Improve Mesh Quality: Cleaning, Repairing, Remeshing.

Simple Data Structures: Triangle List, Indexed Face Set.

While real-data 3D are often point clouds, meshes are quite often used to visualize 3D and generate ground truth for machine learning algorithms.

1.2.4 Mesh Reconstruction

Mesh Reconstruction:

  • Input: point cloud, with or without normals.
  • Output: triangle mesh.
  • Method: Ball Pivoting Algorithm.

Implicit Mesh Reconstruction:

  1. Estimate an implicit field function from data.
  2. Extract the zero iso-surface.

Watertight Manifold Surface Generation: Creating a mesh that is both watertight (no holes) and manifold (each edge is shared by at most two faces).

1.2.5 Subdivision and Simplification

Subdivision: Loop Subdivision, Catmull-Clark Subdivision, and Neural Subdivision.

Mesh Simplification: Collapsing an edge to reduce the number of mesh elements while maintaining the overall shape.

Quadric Error Metrics: Approximate the distance to a surface as the sum of squared distances to planes containing triangles:

\[ \min_{p} \sum_{i} \operatorname{dist}(q_i,p)^2 \]

1.2.6 Mesh Deformation

Mesh Deformation: Generate new meshes by deforming an existing one.

Deformation Energy: Translation and rotation should not change the deformation energy. Stretching (length change) and bending (angle change) increase deformation energy.

Local Deformation Energy:

\[ E(v_i) = \min_{R_i} \sum_{j \in N(i)} \left\| (v_i' - v_j') - R_i(v_i - v_j) \right\|^2 \]

Total Deformation Energy: Sum up the local deformation energy over all vertices

\[ \begin{aligned} E(V') &= \min_{v'} \sum_{i=1}^{n} \min_{R_i} \sum_{j \in N(i)} \left\| (v_i' - v_j') - R_i(v_i - v_j) \right\|^2 \\ &\text{s.t.}\quad v_j' = c_j,\quad j \in C. \end{aligned} \]

This is called As-Rigid-As-Possible (ARAP) deformation.

3D Free-Form Deformation:

  • Modelers drag the vertices of the lattice to define displacements \(d_i\).

  • Displacements of points in space are computed by interpolating \(d_i\) with weights \(B_i(x)\):

    \[ d(x) = \sum_i B_i(x)d_i \]

  • Compute the Bezier parameters in each dimension and apply tricubic interpolation.

    \[ d(x,y,z) = \sum_i \sum_j \sum_k B_i(x)B_j(y)B_k(z)d_{ijk} \]

1.3 Implicit Geometric Representations

Implicit Surface: A surface defined by a scalar function \(f(x,y,z) = 0\). Inside/outside tests are easy.

Algebraic Surfaces: Surface is zero set of a polynomial in \(x, y, z\).

Constructive Solid Geometry: Combine implicit geometry via Boolean operations.

Distance Functions: Functions that measure the shortest distance from a point to a surface.

Level Set Methods: store a grid of values approximating function to alternatively represent a surface. The surface is the zero level set of the function.