Triangulate

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

Normal Calculation: Computes the average normal of the polygon using Newell’s method
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
Vertex Flattening: Converts all 3D vertices to 2D coordinates in the chosen plane
Hole Index Tracking: Records the starting index of each hole in the flattened array
Earcut Algorithm: Runs the robust ear-clipping triangulation
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

Extrude

Often used after triangulation to create 3D geometry

Sweep

Creates surfaces that may need triangulation

2D Primitives

3D Shapes

Operations

Export (Experimental)

Overview

Function Signature

Return Type

Index Mapping

How It Works

Code Examples

Simple Triangle

Quadrilateral Triangulation

Polygon with a Hole

Complex Polygon with Multiple Holes

3D Non-Planar Polygon (Auto-Projected)

Visual Examples

Winding Order

Implementation Details

Source Location

Algorithm

Projection Axis Selection

Normal Calculation (Newell’s Method)

Edge Cases

Performance Considerations

Common Use Cases

See Also

Extrude

Sweep

​Overview

​Function Signature

​Return Type

​Index Mapping

​How It Works

​Code Examples

​Simple Triangle

​Quadrilateral Triangulation

​Polygon with a Hole

​Complex Polygon with Multiple Holes

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

​Visual Examples

​Winding Order

​Implementation Details

​Source Location

​Algorithm

​Projection Axis Selection

​Normal Calculation (Newell’s Method)

​Edge Cases

​Performance Considerations

​Common Use Cases

​See Also

Extrude

Sweep

Overview

Function Signature

Return Type

Index Mapping

How It Works

Code Examples

Simple Triangle

Quadrilateral Triangulation

Polygon with a Hole

Complex Polygon with Multiple Holes

3D Non-Planar Polygon (Auto-Projected)

Visual Examples

Winding Order

Implementation Details

Source Location

Algorithm

Projection Axis Selection

Normal Calculation (Newell’s Method)

Edge Cases

Performance Considerations

Common Use Cases

See Also