Fracturing

[jasonwebb]

Put under Math and physics topics

Here is a dedicated section for Fracturing Mechanics & Algorithms, structured in the same format as the Crack Propagation section for your Math and physics topics.

---

Fracturing Mechanics & Algorithms

Plain Language Description

While crack propagation tracks the growing path of a line or fissure, fracturing focuses on the structural breakage and topological separation of a form into distinct, disconnected pieces (shards, tiles, or polyhedral chunks). Mechanical stress accumulates until the material’s structural integrity fails globally or locally, converting a single contiguous geometric body into multiple independent geometry shells or mass elements. In simulation and computer graphics, fracturing algorithms model everything from instant impact glass shatters and cleaved timber to tearing cloth and dynamic demolition debris.

---

Key Terms and Concepts

• Topological Separation: The transition where a single connected domain or mesh manifold is split into two or more independent, non-connected geometric bodies.
• Seed-Driven Spatial Partitioning: Using a collection of discrete spatial points (often clustered near impact centers or guided by noise fields) to define structural cut boundaries across a domain.
• Volume and Mass Conservation: The mathematical requirement that the total volume, surface area, or mass of the resulting fragments equals that of the original unbroken geometry.
• Maximum Tensile Stress Criterion: A failure rule stating that a material will fracture along the plane perpendicular to the direction of maximum principal tensile stress when that stress exceeds material toughness ($\sigma_{\text{max}} \ge \sigma_{c}$).
• Cap Capping / Hole Filling: Computational geometry routines (e.g., ear-clipping or constrained Delaunay triangulation) that seal and triangulate the newly exposed interior faces created when a 3D volume is sliced open.

---

Key High-Level Algorithms & Models

1. Voronoi / Fortune’s Algorithm (Spatial Shattering)

• High-Level Overview: The most ubiquitous algorithm for instantaneous 2D and 3D fracturing, relying on geometric distance fields rather than continuous physics.
• Algorithm Steps:
  1. Scatter a set of seed points across a domain (clustered near impact sites or weighted by stress fields).
  2. Compute Voronoi cells where every point in space belongs to its nearest seed (using Fortune's Sweepline Algorithm in 2D or half-space convex clipping in 3D).
  3. (Optional) Displace straight cell boundaries using Simplex or Perlin noise to create jagged, organic fracture edges.
  4. Intersect the Voronoi cells with the original geometry to isolate distinct polygonal or polyhedral shards.

2. Finite Element Method (FEM) Brittle Fracture (O’Brien & Hodgins, 1999)

• High-Level Overview: The foundational physics-based 3D fracture algorithm for film visual effects and structural simulations.
• Algorithm Steps:
  1. Discretize a 3D object into a volumetric mesh of tetrahedral elements.
  2. Compute the Cauchy stress tensor ($\boldsymbol{\sigma}$) across elements under external impact or strain forces.
  3. When principal tensile stress exceeds material yield strength, calculate the optimal plane of separation perpendicular to the stress vector.
  4. Dynamically re-mesh and split tetrahedral nodes along that plane to generate physical crack faces and separate geometry.

3. Plane-Slicing & CSG Boolean Cutting

• High-Level Overview: A fast geometric slicing technique used in interactive applications (e.g., Fruit Ninja, blade mode in action games).
• Algorithm Steps:
  1. Define a 2D cutting plane intersecting a 3D polygon mesh.
  2. Test all mesh triangles for intersection with the plane; split straddling triangles into smaller sub-triangles along the plane intersection line.
  3. Separate the vertex array into two distinct meshes based on which side of the plane they lie.
  4. Perform cap-filling algorithms along the open cut boundary to produce two solid, closed manifold meshes.

4. The Virtual Node Algorithm (Molino et al., 2004)

• High-Level Overview: A hybrid simulation method designed to eliminate the computational cost and numerical instability of constant mesh re-meshing.
• Algorithm Steps:
  1. Overlay geometry on a fixed background simulation grid.
  2. Embed arbitrary crack surfaces directly inside the grid cells rather than aligning them with element boundaries.
  3. Duplicate grid elements ("virtual nodes") along the embedded crack path to represent separated material, allowing clean cutting and soft-body tearing without altering the underlying mesh topology.

---

Key Research & Literature References

• O'Brien, J. F., & Hodgins, J. K. (1999): "Graphical Modeling and Animation of Brittle Fracture" — The SIGGRAPH paper that introduced physically accurate, stress-tensor-driven 3D FEM fracture to computer graphics.
• Bourdin, B., Francfort, G. A., & Marigo, J. J. (2000): "Numerical experiments in renovated Griffith's theory of fracture" — Landmark research on variational phase-field formulations that allow continuous 3D shattering without manual mesh splitting.
• Molino, N. et al. (2004): "A Virtual Node Algorithm for Changing Mesh Topology During Simulation" — Essential graphics paper providing a robust method for embedded cutting and tearing without re-meshing errors.
• Rycroft, C. H. (2009): "Voro++: A 3D Cell-Based Voronoi Library" — Introduced high-performance algorithms for calculating 3D polyhedral Voronoi cells used widely in physics and material science.

---

Notable Tools, Libraries, and Software Addons

Standalone & C++ Libraries

• voro++: Fast C++ software library for calculating 3D Voronoi tessellations, used extensively in volumetric fragmentation solvers.
• CGAL (Computational Geometry Algorithms Library): Comprehensive C++ library containing industrial-grade 3D Boolean operations, Voronoi diagrams, and mesh slicing routines.

Creative Coding & Real-Time Visualization

• Processing / p5.js:
  • d3-delaunay (JS): High-performance 2D Voronoi tessellation library ideal for instantaneous browser-based glass or tile shattering.
  • HE_Mesh (Processing Java): Features native support for 3D Voronoi cell slicing (HEC_Voronoi3D) and dynamic plane clipping.
• Unity / Unreal Engine:
  • Unreal Chaos Destruction: Production engine framework using hierarchical geometry collections to manage real-time structural fracturing and physics debris.
  • Unreal Procedural Mesh Component: Provides built-in functions (SliceProceduralMesh) for real-time 3D plane clipping and cap generation.

Visual Effects & 3D Software

• SideFX Houdini:
  • RBD Material Fracture: Industry-standard node suite combining Voronoi, wood grain, and glass fracture models with constraint networks for destruction FX.
• Blender:
  • Cell Fracture Addon: Built-in tool using Voronoi noise and point clouds to break 3D meshes into procedural fragments.