Optimized Incremental Delaunay

Classic triangulation algorithm to use for one by one insertion of points, with SIMD and caching.

– Created: September 14, 2023 UTC

– Edited: July 28, 2024 UTC

– Tags: Programming, Zig, Generation

Based on this paper

Full usable isolated code is here.

Usage example

var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer std.debug.assert(gpa.deinit() == .ok);
var triangulator = try Delaunay.Builder.init(gpa.allocator(), Delaunay.Area{-1, -1, 1, 1});

const point_count = 128;

var prng = std.rand.DefaultPrng.init(123123);
const rng = prng.random();
for (0..point_count) |_| {
    const x = rng.float(f32) * 2 - 1;
    const y = rng.float(f32) * 2 - 1;
    try triangulator.insertAtRandom(Delaunay.Vertex{ x, y }, rng);
}

var triangles: [point_count * 2 + 2]gfx.triangle.ScreenspaceTriangle = undefined;
for (&triangles, triangulator.triangles.items) |*out, in| {
    out.a = triangulator.vertices.items[in.points[0]];
    out.b = triangulator.vertices.items[in.points[1]];
    out.c = triangulator.vertices.items[in.points[2]];
}