The STL for Geometry: Thirty-Year Evolution of C++ Libraries

In 1994, Alexander Stepanov changed C++ by proving that algorithms should not belong to data structures. If you have m algorithms and n containers, you don't need m × n implementations. You need m + n. The iterator was the bridge. A single sort() works on a vector, a deque, or a raw int*.

This shaped what idiomatic C++ feels like. Yet the geometry processing libraries developed since have not quite felt that way.

Nobody builds their application on top of a geometry library. You have your own mesh representation, your own rendering pipeline, your own memory layout. You reach for a library when you need a boolean, a distance query, a remesh. The library asks you to convert. Your vertices become its vertices. Your faces become its faces. You run the algorithm. You convert the result back. Reusing spatial and topological structures across their API is either hard or impossible.

This is the Conversion Tax. 3D pipelines are half data plumbing and half actual math.

trueform solves this with a three-tier separation. The data is yours: flat arrays of built-in types. The access pattern is a lightweight view that defines how to read those arrays. Algorithms are generic functions that operate on the views. Acceleration structures and topology are composable properties you build once and attach. The library never asks you to move your data or rebuild what you already have. It only asks for a way to traverse it, so it can apply exact predicates and parallel algorithms on it.

Apple M4 Max 16 threads Clang -O3 mimalloc

From Objects to Ranges: Thirty Years of Geometry Libraries

Four libraries define the landscape. Each one solved a problem from the previous generation. None quite felt like idiomatic C++.

VTK (1993)

VTK was built before the STL was standardized. It chose the tools available at the time: deep class hierarchies, runtime polymorphism, macro-heavy object factories. Data flows through a graph of filter objects. A simple "read mesh, smooth it, write it" that could be three function calls becomes fifteen lines of object creation, parameter setting, and pipeline wiring.

VTK got visualization right. It got adopted. But its design predates the idea that algorithms and data structures should be separate concerns.

CGAL (1996)

CGAL's founders deliberately adopted STL principles. Traits, iterators, generic programming. They understood the vision. But the complexity of geometry pushed the design toward heavyweight abstractions anyway: kernel concepts that parameterize number types across the entire API, property maps, BGL integration, named parameters. The STL pattern was there but buried under layers of domain-specific machinery.

The result is mathematically rigorous. Exact arithmetic with EPECK kernels. The golden standard for correctness. But the dependency chain (Boost, GMP, MPFR) is formidable, and the algorithms are opaque. You call a function, it does everything internally, and you get a result in CGAL's types.

libigl (2013)

libigl was the reaction. Its subtitle says it all: "A C++ library for geometry processing without a mesh data structure."

The thesis was clean: geometry is linear algebra. A mesh is two Eigen matrices. V for vertices, F for faces. Functions take matrices in, return matrices out. Stateless. Header-only. No build step. The founding paper states the motivation directly: "Many existing code libraries have unsatisfactory APIs and the time spent implementing sub-routines is often replaced with time spent learning complex, templated object hierarchies or memory layouts."

libigl removed the mesh object but replaced it with a hard Eigen dependency. Your data has to live in Eigen matrices. It exposed some intermediate structures (an AABB tree class, topology as sparse matrices, the cotangent Laplacian), more than its predecessors. But these are exceptions. Most algorithms still hide their internal structures. The spatial tree built inside one function cannot be passed to another. Boolean operations delegate to CGAL with, by the library's own documentation, "very disappointing performances."

MeshLib (2020s)

MeshLib is fast, commercially backed, and architecturally closer to CGAL than to libigl. It has its own mesh types with its own opaque internal structures. Your data goes in, their types come out. The conversion tax remains. The algorithms don't operate on your data.

The Pattern

Each generation solved a problem from the previous one. VTK gave us visualization pipelines. CGAL gave us mathematical rigor. libigl gave us freedom from object hierarchies. MeshLib packaged it into an industrial SDK.

What they share: algorithms that hide their intermediate structures, no range adaptors, no composition, no separation of data layout from algorithmic concerns. Reusing spatial and topological structures across their API is either hard or impossible; e.g. the spatial tree built for a distance query cannot be reused for a boolean, unless you tie yourself to their types.

The Anatomy of a Geometric Range

The STL has std::priority_queue. But it also gives you make_heap, push_heap, pop_heap. Algorithms that operate on any random-access range. Your std::vector IS the heap. The heap property is not a separate object. It is a structure imposed on your data. You own the data. You own the structure. You compose them.

trueform applies this to geometry through a three-tier separation.

Tier 1: The Raw Data

Everything is an array. Points are arrays of coordinates. Faces are arrays of indices. Topology metadata is flat offset-block arrays. Cache-friendly, parallel-ready memory owned by the user. The library does not ingest this data. It only references it.

Tier 2: The Semantic Range

Range adaptors wrap flat arrays without owning them, and give them meaning. make_points takes a flat range and produces a range of point_view. A fixed-size range over three contiguous coordinates with begin(), end(), structured bindings, and vector algebra. It knows what those three coordinates mean. make_faces does the same for indices. make_polygons composes the two: each polygon is an indirect range that dereferences face indices into the points range.

std::vector<float> raw_coords = {0,0,0, 1,0,0, 0,1,0, 1,1,0};
std::vector<int> raw_indices = {0, 1, 2, 0, 2, 3};

auto points = tf::make_points<3>(raw_coords);      // view, no copy
auto faces = tf::make_faces<3>(raw_indices);        // view, no copy
auto mesh = tf::make_polygons(faces, points);       // composed view

mesh is a view into faces, which is a view into raw_indices, which is a view into raw_coords. The data never moved.

auto faces0 = tf::make_faces(tf::make_blocked_range(data, n_gon));
auto faces1 = tf::make_faces(offsets, data);

The ranges carry semantics:

auto polygon = mesh.front();
auto [pt0, pt1, pt2] = polygon;     // structured bindings on a polygon
auto [vv_id0, vv_id1, vv_id2] = polygon.indices();
auto [v_id0, v_id1, v_id2] = mesh.faces().front();
auto [x, y, z] = mesh.points().front();  // structured bindings on a point

Semantic ranges all the way down. face_membership is a semantic name on an offset_block_range, a jagged array of vertex-to-face adjacency. manifold_edge_link is the same pattern for edge-to-face adjacency. Every level of the hierarchy, from a single point to a million-polygon mesh, is a range with semantic access patterns on raw memory.

These primitives are not just data carriers. They support queries directly:

auto segment = tf::make_segment_between_points(pt0, pt1);
auto plane = tf::make_plane(polygon);

auto d  = tf::distance(segment, polygon);
auto m  = tf::closest_metric_point_pair(polygon0, polygon1);
auto [dist2, pt_on_poly0, pt_on_poly1] = m;

bool hit = tf::intersects(segment, polygon);
auto side = tf::classify(point, plane);
auto cont = tf::classify(point, polygon);

auto r = tf::ray_cast(ray, polygon);
if (r) { auto [status, t] = r; }

Distance, intersection, classification, ray casting. All pairs of primitives. To query ranges of primitives efficiently, you attach policies.

Tier 3: Policies

The first two tiers give you zero-copy views with geometric semantics. The third tier gives you composable structure.

Andrei Alexandrescu introduced policy-based design in Modern C++ Design. Small, orthogonal classes that inject behavior at compile time. trueform applies the same principle, but the policies are not just behavioral mixins. They are data structures. A spatial tree is an index hierarchy. A topology structure is an adjacency array. A transformation is a 4×4 matrix. They are attached to a form via | and detected by algorithms at compile time.

auto form = mesh
    | tf::tag(tree)             // spatial acceleration
    | tf::tag(face_link)        // topological connectivity
    | tf::tag(transformation);  // zero-copy pose

auto tree = form.tree();

Both mesh and form are instantiations of tf::polygons. The policy is a template parameter:

template<typename Policy>
using concrete_polygons_t = tf::polygons<Policy>;

An algorithm that needs a spatial tree checks for one at compile time. If the form carries a tree, the algorithm uses it. If not, it builds what it needs and discards it. You can tag any combination: tree alone, topology alone, both, all three, or none. The algorithm adapts.

Orthogonality

Acceleration structures, topological connectivity, and transformations are independent of the algorithms that use them and independent of each other. You build each one separately. You attach any combination. Algorithms detect what's present at compile time and adapt.

tf::aabb_tree<int, float, 3> tree(polygons, tf::config_tree(4, 4));
tf::face_membership<int> fm;
fm.build(polygons);

auto form = polygons | tf::tag(tree) | tf::tag(fm);

The same tree serves distance queries, ray casting, collision detection, and booleans. The same topology serves boundary detection, connected components, vertex rings, and manifold edge analysis. Built once, tagged once, reused across operations:

tf::distance(form, point);
tf::intersects(form, form | tf::tag(transformation));
auto [result, labels] =
    tf::make_boolean(form, form | tf::tag(transformation), tf::boolean_op::merge);

Tag nothing and the algorithm builds what it needs internally, then discards it. Tag everything and nothing is rebuilt. The choice is yours, per call.

Zero-Cost Transformations

Instead of applying a rotation to every vertex and copying the data, you tag a transformation onto the form:

auto rotation = tf::make_rotation(tf::deg(90.f), tf::axis<2>, pivot);
auto rotated = form | tf::tag(rotation);

The original data is untouched. The rotation is applied on-the-fly during queries. Since spatial and topological structures are independent of transformations, they can be shared across moving entities. Two queries on the same mesh at different poses share the same tree, the same topology, the same vertex data. Only the transformation differs.

The Buffer/Range Duality

Every data structure in trueform follows the same split: an owning buffer that holds flat data, and a non-owning semantic range that provides access patterns over it.

The duality is literal. polygons_buffer.polygons() internally calls make_polygons(faces(), points()). Same iterator types, same algorithms, whether you enter from the owning side or the viewing side.

Topology is the Same Pattern

face_membership inherits from offset_block_buffer<Index, Index>. It IS a flat jagged array (offsets and data) with a semantic name. vertex_link is the same. manifold_edge_link is the same.

for (auto face_id : face_membership[vertex_id]) {
    // contiguous memory scan
}

Buffers Let You Release

trueform is part of your pipeline, not a destination. When you need to ship data forward, you release it into your ownership:

auto mesh = tf::read_stl("model.stl");
float* point_data = mesh.points_buffer().data_buffer().release();
int* face_data = mesh.faces_buffer().data_buffer().release();
// Pass to Eigen, OpenGL, or your own allocator.

The Bootstrapping Library

A bootstrapping compiler is written in the language it compiles. It is its own proof of completeness. Sean Parent showed the same pattern in the STL: std::sort is built from std::rotate, which is built from std::swap_ranges. The library's own algorithms are its best test. If the building blocks are good enough to write sort, they are good enough for you.

trueform is built from itself. Every high-level operation (boolean, remeshing, registration, arrangement) is composed of the same building blocks that are fully exposed to the user. Intersection curve extraction. Face cutting. Reindexing. Component labeling. Edge path tracing. These are not internal utilities. They are the public API.

If you need a specialized pipeline, you use the same functions the library's boolean implementation uses. In the same order, or in a different order. With the same structures, or with your own. There is no "internal."

Closing

trueform is a header-only C++ library. It runs on x86, ARM, and WebAssembly. It uses exact arithmetic for robustness and TBB for parallelism. It has Python and TypeScript bindings. But none of that is the point.

The point is that your polygon array IS the mesh. The tree is a structure you build on it. The topology is a structure you build on it. The transformation is a tag you attach to it. Algorithms detect these structures at compile time and reuse them. You own the data. You compose it the way you want.

@article{polydera:the-stl-for-geometry,
  title={The STL for Geometry: Thirty-Year Evolution of C++ Libraries},
  author={Sajovic, {\v{Z}}iga, Polydera},
  year={2026},
  url={https://polydera.com/algorithms/the-stl-for-geometry},
  organization={Polydera}
}