GeoDel

Fast 3D Delaunay triangulation for Python, built on the parallel Delaunay implementation from Geogram.

import numpy as np
import geodel

points = np.random.default_rng(0).random((1_000_000, 3))
tets = geodel.delaunay3d(points)     # (M, 4) uint32, indexes into points

• numpy is the only runtime dependency. No CMake, no Boost, no system Geogram install, no binding framework.
• Multithreaded, via Geogram's ParallelDelaunay3d.
• Consistently oriented output — every tetrahedron has positive signed volume, so no winding fixup is needed downstream.
• Zero-copy results as read-only numpy arrays.

Installation

geodel is not on PyPI; install it from this repository. There are no prebuilt wheels, so every install compiles the extension — expect roughly a minute, since the Geogram amalgamation is a single 36,000-line translation unit. The only build requirement is a C++17 compiler.

Directly with pip

pip install git+https://github.com/Anttwo/GeoDel@v0.1.0

From a clone

git clone https://github.com/Anttwo/GeoDel
cd geodel
pip install .

Use pip install -e . for an editable install if you intend to modify the source.

As a dependency of your own project

# pyproject.toml
dependencies = ["geodel @ git+https://github.com/Anttwo/GeoDel@v0.1.0"]

Two caveats. Pinning a tag is not enough on its own: pip considers an installed package with a matching version as satisfying the requirement and will not re-fetch, so use pip install --force-reinstall after a release that keeps the same version number. And PyPI rejects packages whose metadata contains direct URL dependencies, so this form only works for projects you do not publish to PyPI.

As a git submodule

The vendored Geogram sources are committed directly in extern/geogram/, not as a nested submodule, so a plain non-recursive checkout yields a complete, buildable tree.

git submodule add https://github.com/Anttwo/GeoDel extern/geodel
git -C extern/geodel checkout v0.1.0
pip install ./extern/geodel

Consumers of your project then need only:

git submodule update --init      # --recursive is not required
pip install ./extern/geodel

Usage

delaunay3d

tets = geodel.delaunay3d(points, parallel=True, nb_threads=0)

Takes an (N, 3) array of coordinates and returns an (M, 4) uint32, read-only array of vertex indices. nb_threads=0 means one thread per core. For a uniform random cloud, M is approximately 6.75 * N.

v = points[tets]                     # (M, 4, 3) coordinates per tetrahedron
a, b, c, d = v[:, 0], v[:, 1], v[:, 2], v[:, 3]
volumes = np.einsum("ij,ij->i", np.cross(b - a, c - a), d - a) / 6.0

Triangulation

For adjacency information, keep the triangulation object:

tri = geodel.Triangulation(points)
tri.cells        # (M, 4) uint32 — same as delaunay3d()
tri.neighbors    # (M, 4) uint32 — tetrahedron across the facet opposite
                 #   local vertex f, or geodel.NO_INDEX on the convex hull
tri.num_cells
tri.num_vertices
tri.points

Things to know

• Indices are uint32, not int32. Cast with .astype(np.int64) before any index arithmetic that could go negative. NO_INDEX is 0xFFFFFFFF, so neighbors < 0 never matches — compare against geodel.NO_INDEX.
• Results are read-only zero-copy views onto Geogram's internal buffers, and they keep the triangulation alive. Call .copy() for a writable array.
• Duplicate points are dropped and will not appear as vertices of any tetrahedron, so not every input index necessarily occurs in the output.
• Memory. Budget roughly 26x the input size for cells, and double that if you also touch neighbors. Ten million points means about 2.2 GB of output arrays plus Geogram's working set.
• Degenerate input. For cospherical configurations such as a perfect lattice, the Delaunay triangulation is not unique; different libraries may return different valid triangulations.

Performance

Measured against scipy.spatial.Delaunay (Qhull) on uniformly distributed random points, single-threaded, best of three runs:

points	geodel	scipy	speedup	geodel peak RSS	scipy peak RSS
100k	0.48 s	4.05 s	8.4x	79 MB	295 MB
500k	2.67 s	27.1 s	10.1x	171 MB	1218 MB
1M	5.27 s	58.0 s	11.0x	308 MB	2371 MB
4M	24.0 s	—	—	1129 MB	out of memory

The memory ratio matters more than the speed ratio in practice: it is what determines the largest problem that fits on a given machine.

Speedup depends strongly on how the points are distributed. At 200k points, clustered data (Gaussian blobs of very uneven density) showed a 63x gap, points on a sphere 8.7x, and a perfect integer lattice 5x.

These figures were collected on a single core and therefore include no parallel speedup. Reproduce them on your own hardware with:

python tools/benchmark.py '[["geodel","uniform",1000000,3],["scipy","uniform",1000000,1]]'

Platform notes

• musl-based distributions such as Alpine are not supported: the Geogram amalgamation includes <execinfo.h>, which musl does not provide.
• Apple's clang ships without OpenMP, so macOS builds are single-threaded unless you brew install libomp and build with the flags documented in setup.py.
• The -frounding-math and -ffp-contract=off compiler flags in setup.py are required for correctness, not speed. Geogram's exact geometric predicates depend on the compiler not fusing multiply-adds and not making assumptions about the floating-point rounding mode. Please read the comment in setup.py before changing them.

Credits

The computational work here is done by Geogram, a programming library of geometric algorithms by Bruno Lévy (Inria). geodel is a thin Python binding around Geogram's Delaunay module and claims no credit for the algorithms, the exact predicates, or the parallel insertion scheme that make it fast.

Geogram is distributed by Inria under the BSD 3-Clause license, Copyright (c) 2000-2022 Inria. Its Delaunay_psm.h / Delaunay_psm.cpp amalgamation is vendored in extern/geogram/; see extern/geogram/LICENSE for the full text and extern/geogram/VERSION for the exact upstream commit.

Further reading:

• Geogram: https://github.com/BrunoLevy/geogram
• Documentation: https://brunolevy.github.io/geogram/
• Bruno Lévy, Inria: https://www.inria.fr/fr/bruno-levy

If you use this in academic work, please cite Geogram rather than geodel.

Contributing

See CONTRIBUTING.md, in particular for how the vendored Geogram sources are updated.

License

geodel is released under the BSD 3-Clause license; see LICENSE. The vendored Geogram sources carry their own BSD 3-Clause license from Inria, reproduced in extern/geogram/LICENSE.