Skip to main content

​
Overview

The triangulate operation decomposes complex polygons (including those with holes) into a set of triangles. This is essential for rendering, collision detection, and finite element analysis. OpenGeometry uses the robust ear-clipping (earcut) algorithm with automatic projection to handle 3D polygons.

​
Function Signature

pub fn triangulate_polygon_with_holes(
    face_vertices: &Vec<Vector3>,
    holes: &Vec<Vec<Vector3>>,
) -> Vec<[usize; 3]>
Triangulates a polygon with optional holes into a set of triangles.
​
face_vertices
&Vec<Vector3>
required
The outer boundary vertices of the polygon in order (either clockwise or counter-clockwise). Must have at least 3 vertices to form a valid polygon.
​
holes
&Vec<Vec<Vector3>>
required
A vector of hole polygons, each defined by its own ordered vertex list. Holes must be entirely contained within the outer boundary. Pass an empty vector if there are no holes.

​
Return Type

Returns Vec<[usize; 3]> - a vector of triangle indices, where each [usize; 3] array contains three indices into the combined vertex list (outer boundary vertices followed by all hole vertices).

​
Index Mapping

  • Indices 0..face_vertices.len() refer to outer boundary vertices
  • Indices face_vertices.len().. refer to hole vertices in order
Example:
  • Outer boundary: 5 vertices (indices 0-4)
  • Hole 1: 4 vertices (indices 5-8)
  • Hole 2: 3 vertices (indices 9-11)

​
How It Works

  1. Normal Calculation: Computes the average normal of the polygon using Newell’s method
  2. Projection Selection: Chooses the best 2D projection plane based on the dominant axis:
    • If |Z| is dominant: Project to XY plane
    • If |X| is dominant: Project to YZ plane
    • Otherwise: Project to XZ plane
  3. Vertex Flattening: Converts all 3D vertices to 2D coordinates in the chosen plane
  4. Hole Index Tracking: Records the starting index of each hole in the flattened array
  5. Earcut Algorithm: Runs the robust ear-clipping triangulation
  6. Winding Order Correction: Automatically reverses triangles if needed for consistent orientation

​
Code Examples

​
Simple Triangle

use opengeometry::operations::triangulate::triangulate_polygon_with_holes;
use openmaths::Vector3;

let triangle = vec![
    Vector3::new(0.0, 0.0, 0.0),
    Vector3::new(1.0, 0.0, 0.0),
    Vector3::new(0.5, 0.0, 1.0),
];

let triangles = triangulate_polygon_with_holes(&triangle, &vec![]);

assert_eq!(triangles.len(), 1);
assert_eq!(triangles[0], [0, 1, 2]);

​
Quadrilateral Triangulation

use opengeometry::operations::triangulate::triangulate_polygon_with_holes;
use openmaths::Vector3;

// Rectangle
let quad = vec![
    Vector3::new(0.0, 0.0, 0.0),
    Vector3::new(2.0, 0.0, 0.0),
    Vector3::new(2.0, 0.0, 2.0),
    Vector3::new(0.0, 0.0, 2.0),
];

let triangles = triangulate_polygon_with_holes(&quad, &vec![]);

// Quadrilateral splits into 2 triangles
assert_eq!(triangles.len(), 2);

// Example output:
// [[0, 1, 2], [0, 2, 3]]

​
Polygon with a Hole

use opengeometry::operations::triangulate::triangulate_polygon_with_holes;
use openmaths::Vector3;

// Outer square
let outer = vec![
    Vector3::new(0.0, 0.0, 0.0),
    Vector3::new(4.0, 0.0, 0.0),
    Vector3::new(4.0, 0.0, 4.0),
    Vector3::new(0.0, 0.0, 4.0),
];

// Inner square hole
let hole = vec![
    Vector3::new(1.0, 0.0, 1.0),
    Vector3::new(3.0, 0.0, 1.0),
    Vector3::new(3.0, 0.0, 3.0),
    Vector3::new(1.0, 0.0, 3.0),
];

let holes = vec![hole];
let triangles = triangulate_polygon_with_holes(&outer, &holes);

// Returns multiple triangles that avoid the hole
assert!(triangles.len() >= 8); // Minimum for a square with square hole

// Indices 0-3 are outer vertices, 4-7 are hole vertices

​
Complex Polygon with Multiple Holes

use opengeometry::operations::triangulate::triangulate_polygon_with_holes;
use openmaths::Vector3;

fn create_hexagon(center: Vector3, radius: f64) -> Vec<Vector3> {
    let mut vertices = Vec::new();
    for i in 0..6 {
        let angle = (i as f64) * std::f64::consts::PI / 3.0;
        vertices.push(Vector3::new(
            center.x + radius * angle.cos(),
            center.y,
            center.z + radius * angle.sin(),
        ));
    }
    vertices
}

let outer = create_hexagon(Vector3::new(0.0, 0.0, 0.0), 5.0);
let hole1 = create_hexagon(Vector3::new(-1.5, 0.0, 0.0), 0.8);
let hole2 = create_hexagon(Vector3::new(1.5, 0.0, 0.0), 0.8);

let triangles = triangulate_polygon_with_holes(&outer, &vec![hole1, hole2]);

// Complex triangulation avoiding both holes
println!("Generated {} triangles", triangles.len());

​
3D Non-Planar Polygon (Auto-Projected)

use opengeometry::operations::triangulate::triangulate_polygon_with_holes;
use openmaths::Vector3;

// Polygon on a tilted plane
let tilted_polygon = vec![
    Vector3::new(0.0, 0.0, 0.0),
    Vector3::new(1.0, 0.2, 0.0),
    Vector3::new(1.0, 0.3, 1.0),
    Vector3::new(0.0, 0.1, 1.0),
];

let triangles = triangulate_polygon_with_holes(&tilted_polygon, &vec![]);

// Automatically projects to best 2D plane and triangulates
assert_eq!(triangles.len(), 2);

​
Visual Examples

Simple Polygon:                     Polygon with Hole:

    v3────v2                           v3────v2
    │╲     │                           │ ╲    │
    │  ╲   │        →                  │  h3─h2
    │    ╲ │                           │  │╲ ││
    v0────v1                           │  h0─h1
                                       │╱     │
    Triangles:                         v0────v1
    [0,1,2], [0,2,3]
                                       Triangles avoid hole


Multiple Holes:

    Outer                              Result
   ┌──────────┐                    ┌──────────┐
   │  h1   h2 │                    │╱╲╱╲╱╲╱╲╱│
   │  ○    ○  │       →            │╲╱╲╱╲╱╲╱╲│
   │          │                    │╱╲╱╲╱╲╱╲╱│
   └──────────┘                    └──────────┘

​
Winding Order

The function automatically corrects winding order:
  • Analyzes the first triangle’s orientation
  • Reverses all triangles if winding is inconsistent
  • Ensures consistent face normals for rendering

​
Implementation Details

​
Source Location

~/workspace/source/main/opengeometry/src/operations/triangulate.rs:3

​
Algorithm

Uses the earcutr library, which implements:
  • Fast ear-clipping triangulation
  • Robust handling of self-touching vertices
  • Support for complex polygons with holes

​
Projection Axis Selection

if normal.z.abs() > normal.x.abs() && normal.z.abs() > normal.y.abs() {
    // Project to XY plane (indices 0, 1)
} else if normal.x.abs() > normal.y.abs() {
    // Project to YZ plane (indices 1, 2)
} else {
    // Project to XZ plane (indices 0, 2)
}

​
Normal Calculation (Newell’s Method)

for i in 0..vertices.len() {
    let p1 = &vertices[i];
    let p2 = &vertices[(i + 1) % vertices.len()];
    normal.x += (p1.y - p2.y) * (p1.z + p2.z);
    normal.y += (p1.z - p2.z) * (p1.x + p2.x);
    normal.z += (p1.x - p2.x) * (p1.y + p2.y);
}

​
Edge Cases

  • Insufficient Vertices: Returns empty vector if outer boundary has < 3 vertices
  • Degenerate Polygons: May produce no triangles or unexpected results
  • Self-Intersecting: Earcut algorithm handles some cases but behavior is undefined
  • Holes Outside Boundary: Results are undefined; ensure holes are contained
  • Non-Planar Polygons: Automatically projected, but significant non-planarity may cause artifacts

​
Performance Considerations

  • Time Complexity: O(n log n) average case for earcut algorithm
  • Memory: O(n) for vertex storage and triangle output
  • Efficient for polygons with hundreds of vertices
  • Minimal overhead from projection

​
Common Use Cases

  • Rendering: Convert arbitrary polygons to GPU-compatible triangle meshes
  • Physics: Generate collision meshes from polygon boundaries
  • CAD/CAM: Prepare geometry for manufacturing or simulation
  • GIS: Triangulate geographic regions with exclusion zones
  • Architecture: Process floor plans with room boundaries and obstacles

​
See Also

  • Extrude - Often used after triangulation to create 3D geometry
  • Sweep - Creates surfaces that may need triangulation
Last modified on March 7, 2026