CSG

The CSG module builds an arrangement of N forms once and evaluates any boolean expression over them — no need to chain pairwise booleans.

Include the module with:

#include <trueform/csg.hpp>

Overview

A CSG computation is two stages: build the arrangement once, then extract from it as many times as you like.

• Build — tf::make_csg_graph returns a tf::csg_graph, the implicit arrangement of N forms. This is where the heavy work (intersection, classification, the inclusion lattice) happens.
• Extract — cheap queries over that one graph. There are three:
  • tf::make_csg_mesh(graph, expr) — the mesh for a boolean expression. expr is a tf::csg::expr, a runtime tree over operand ids built from tf::csg::merge, tf::csg::intersection, tf::csg::difference, tf::csg::complement, plus tf::csg::any_of / tf::csg::all_of for ranges. Called with no expression, it returns the full arrangement.
  • tf::make_csg_domains(graph) — every domain the forms carve space into, each as its own watertight mesh (Domain Decomposition).
  • tf::make_intersection_curves(graph) — the intersection-curve network where surfaces cross (Intersection Curves).

std::vector forms{ mesh0.polygons(), mesh1.polygons(), mesh2.polygons() };
auto graph = tf::make_csg_graph(tf::make_range(forms));

auto expr = tf::csg::difference(0, tf::csg::merge(1, 2));   // a \ (b ∪ c)
auto out  = tf::make_csg_mesh(graph, expr);

Operand ids are positions in the forms range. Integers are auto-promoted to leaves, so tf::csg::merge(0, 1, 2) reads exactly like the algebra.

The graph is built once and reused: the same graph feeds any number of make_csg_mesh expressions, make_csg_domains, and make_intersection_curves calls without recomputing the arrangement.

Building Expressions

Every boolean is a tf::csg::expr — a tree whose leaves are operand ids. There are two interchangeable ways to build one, both producing the same expr. The function builders are variadic:

For the binary and unary cases the operators read more like algebra. tf::csg::op(i) is a leaf factory (op(i) == expr{i}), needed to lift the first integer into the expression type:

using namespace tf::csg;
auto e1 = difference(0, merge(1, 2));   // function form
auto e2 = op(0) - (op(1) | op(2));      // operator form — same expr

Once one side is an expr, integers on the other side auto-promote, so op(0) - 1 and op(0) | 1 are fine; only the leading leaf needs op. There is no XOR/symmetric-difference operator — spell it (a - b) | (b - a). Everything below uses whichever form reads best; they are the same algebra, and both make_csg_mesh and domain selection accept it.

Configuration & Supported Input

tf::make_csg_graph takes an optional tf::arrangement_config — the intersection settings plus the cut-surface triangulation, implicitly constructible from an tf::intersect_config alone, so every intersect-only spelling below stays valid. The intersect mode flags decide what kinds of input are accepted and how degeneracies are resolved. What works in CSG is exactly what works under that mode:

The default for tf::make_csg_graph is primitives | resolve_crossing_contours, matching make_boolean. Override only when you have a reason to:

tf::intersect_config cfg{tf::intersect_mode::primitives
                          | tf::intersect_mode::resolve_crossing_contours};
auto graph = tf::make_csg_graph(tf::make_range(forms), cfg);

Full flag semantics, the tolerance field, and the mode-vs-config equivalence are documented in Intersect: Intersection Configuration.

Regardless of mode, each form should be PWN (piecewise winding number) — locally consistent orientation. The per-domain inclusion lattice that backs every boolean expression only carries meaning when each form draws a clean inside/outside boundary.

Coordinate Precision

The arrangement uses exact integer arithmetic internally. The lattice resolution is selected by the Int template parameter on make_csg_graph and resolves automatically from the input coordinate type:

// Auto-resolved
auto graph = tf::make_csg_graph(tf::make_range(forms));

// Explicit override
auto graph = tf::make_csg_graph<tf::exact::int64>(tf::make_range(forms));

See Intersect: Exact Arithmetic for the full precision chain.

Output Coordinate Type

The output mesh's scalar type is controlled by the OutputCoordinateType template parameter on tf::make_csg_mesh. It defaults to the input forms' real type; any floating-point type may be supplied.

// Output matches input
auto out = tf::make_csg_mesh(graph, expr);

// Explicit override (independent of the graph's Int)
auto out = tf::make_csg_mesh<double>(graph, expr);

Internally the pipeline carries intersection points at full precision regardless of OutputCoordinateType; the parameter only governs the coordinate type at output emission. The Int chosen at graph-build time is unchanged.

The Full Arrangement

Call tf::make_csg_mesh(graph) with no expression to get the full arrangement surface — every input face, cut at intersections, each surface emitted once. It is the graph analogue of tf::make_mesh_arrangements, and the surface counterpart of tf::make_csg_domains(graph) returning every domain.

auto graph = tf::make_csg_graph(tf::make_range(forms));

auto surface = tf::make_csg_mesh(graph);   // no expression -> full arrangement

This reuses the intersection graph and face cuts the graph already holds — only the mesh is materialised, the intersection pipeline is not re-run — so it is far cheaper than calling tf::make_mesh_arrangements on the forms again. Add tf::return_source_ids for the (mesh, tag_labels, face_labels) provenance form.

Face Provenance

Pass tf::return_source_ids to also recover, for every output face, which input form it came from and which original face within that form. The call then returns the mesh plus two per-output-face buffers — the same (tag_labels, face_labels) pair tf::make_mesh_arrangements returns:

auto [out, tag_labels, face_labels] =
    tf::make_csg_mesh(graph, expr, tf::return_source_ids);

// For output face f:
//   tag_labels[f]  -> which input form it came from       (0 .. n_forms-1)
//   face_labels[f] -> the original face id within that form

Both buffers run parallel to out.faces(). Uncut faces carry their own original id; a triangulated cut face carries the id of the face it was cut from. This traces each surviving boundary triangle back to the operand and face that produced it — for transferring per-face attributes (materials, UVs, tags) onto the boolean result, or coloring the output by source. The plain tf::make_csg_mesh(graph, expr) is unchanged; the labels are opt-in.

Full Index Map

Pass tf::return_index_map instead for a single tf::mesh_arrangement_index_map that folds in the face provenance and adds the point axis — the same map tf::make_mesh_arrangements returns. Works on both the full-arrangement and the boolean overloads:

auto [out, imap] = tf::make_csg_mesh(graph, tf::return_index_map);          // full arrangement
auto [res, imap] = tf::make_csg_mesh(graph, expr, tf::return_index_map);    // boolean result

The map relates output back to the inputs in both directions:

Created intersection points (and, for a boolean, input points no surviving face kept) have no input origin, so each inverse axis carries an end sentinel one past its own range — the tag ends at n_tags, the point id at n_output_points — the same idiom the arrangement index map uses. Use the forward map to push input point data onto the result, or the inverse to pull result attributes back to the operands.

Cut-Surface Triangulation

The triangulation of the cut faces is the second half of the tf::arrangement_config. A tf::triangulation_type converts to the config implicitly, so both spellings work:

auto g0 = tf::make_csg_graph(forms, tf::triangulation_type::refined_cdt);
auto g1 = tf::make_csg_graph(
    forms, {config, tf::triangulation_type::refined_cdt});

• tf::triangulation_type::cdt (default) — plain constrained Delaunay per cut loop.
• tf::triangulation_type::refined_cdt — quality refinement of the cut surface (Ruppert circumcenter insertion). Boundary splits are negotiated globally through shared dyadic split records, so loop boundaries shared between faces — and across coplanar stacks — stay watertight by construction. Refined builds carry more created points; graph.created_points() is the unified table every extraction indexes.

Many Operations, One Graph

The arrangement is the cost. Once graph is built, every additional boolean expression evaluates without re-running the geometric pipeline:

auto graph = tf::make_csg_graph(tf::make_range(forms));

auto m_union = tf::make_csg_mesh(graph, tf::csg::merge(0, 1, 2));
auto m_inter = tf::make_csg_mesh(graph, tf::csg::intersection(0, 1, 2));
auto m_diff  = tf::make_csg_mesh(graph,
                                  tf::csg::difference(0,
                                    tf::csg::any_of({1, 2})));

With Precomputed Structures

tf::make_csg_graph auto-tags any form that's missing tf::face_membership, tf::manifold_edge_link, or tf::tree. For repeated work — for example, instancing the same canonical mesh many times — pre-tag once and share the structures:

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

auto bunny_tagged = bunny.polygons() | tf::tag(fm) | tf::tag(mel) | tf::tag(tree);

std::vector forms{ sphere_tagged, bunny_tagged, bunny_tagged, bunny_tagged };
auto graph = tf::make_csg_graph(tf::make_range(forms));

All copies of bunny_tagged share the same FM / MEL / tree — the arrangement build re-uses them across instances.

With Transformations

Combine tagged structures with tagged transformations to instance the same canonical mesh at different positions without copying geometry:

auto T1 = tf::make_transformation_from_translation(tf::make_vector(1.0f, 0, 0));
auto T2 = tf::make_transformation_from_translation(tf::make_vector(0, 1.0f, 0));

std::vector forms{
    sphere_tagged | tf::tag(tf::make_frame(tf::transformation<float, 3>{})),
    bunny_tagged  | tf::tag(tf::make_frame(T1)),
    bunny_tagged  | tf::tag(tf::make_frame(T2)),
};

auto graph = tf::make_csg_graph(tf::make_range(forms));
auto out   = tf::make_csg_mesh(graph,
                                tf::csg::difference(0, tf::csg::merge(1, 2)));

One tagged canonical mesh + N frames + one graph is the cheapest way to fold many instances of the same shape into a single boolean.

Self-Arrangements

Everything above treats each operand as one clean solid. Two additions lift that restriction.

One form: the graph is the self arrangement

tf::make_csg_graph accepts a single form directly — no range, no second operand. The graph then is the form's self arrangement: every self-intersection is found and cut, and the structural reads apply — tf::make_outer_shell and tf::make_csg_domains work as usual. Boolean expressions need two operands, so make_csg_mesh does not apply here.

auto graph = tf::make_csg_graph(soup.polygons());   // self-arrangement

auto [cells, ids] = tf::make_csg_domains(graph);    // every enclosed region
auto shell = tf::make_outer_shell(graph);           // the outermost surface

This is the CSG-path answer to raw input — a scanned or concatenated soup whose components overlap — and it carves the same cells tf::make_polygon_arrangements followed by domain labels would, from one build.

N forms with self-overlap: the within flag

For multiple operands, self-intersections are skipped by default — a clean solid has none, and the pairwise sweep is cheaper without the self pass. When an operand can self-overlap — two meshes concatenated into one operand, an instanced part whose copies touch — add tf::intersect_mode::within to the config:

auto bc = tf::concatenated(b.polygons(), c.polygons());   // one self-overlapping operand
std::vector forms{ bc.polygons(), a.polygons() };

tf::intersect_config cfg{tf::intersect_mode::primitives
                          | tf::intersect_mode::resolve_crossing_contours
                          | tf::intersect_mode::within};
auto graph = tf::make_csg_graph(tf::make_range(forms), cfg);

auto [cells, ids] = tf::make_csg_domains(graph);

The self pass runs with the same parallelism as the pairwise sweep, and make_csg_domains classifies the result structurally, so regions covered twice by one operand — the overlap pockets — come out as their own cells: the extraction matches what the same meshes would produce as separate operands, cell for cell. Setting the flag on operands that don't self-overlap changes nothing but the (empty) self pass.

Note the asymmetry: make_csg_domains is self-overlap-aware; make_csg_mesh is not. A boolean expression reads per-operand inside/outside bits, and a self-overlapping operand doesn't have a single such boundary — keep expression queries on solid, non-self-overlapping operands.

Domain Decomposition

tf::make_csg_mesh returns one surface for a boolean expression. tf::make_csg_domains returns the arrangement's cells — every watertight region the N forms carve space into — each as its own polygons_buffer. This is the structure simulation wants: volumetric domains to assign materials and boundary conditions to, not a single merged boundary.

auto graph = tf::make_csg_graph(tf::make_range(forms));

auto [cells, ids] = tf::make_csg_domains(graph);   // every cell, one mesh each

An expression restricts the extraction; the same selection can be made by hand from one full extraction via the inclusion matrix — ids are stable across queries on one graph, so the two routes agree cell for cell. The Arrangements and Volumes example runs this pattern end to end.

The result is { cells, ids }: cells[k] is the closed, oriented boundary of domain k, and ids[k] is its coarse domain id. The arrangement is built once — extracting domains costs no new geometric work.

Selecting domains

Filter the cells with the same expression algebra as make_csg_mesh. tf::csg::op(i) selects the domains that lie inside form i:

auto [core, ids] = tf::make_csg_domains(graph, tf::csg::op(0));   // cells inside form 0

Because each operand draws an inside/outside boundary, any expression keeps the cells whose inclusion matches it: tf::csg::op(0) & tf::csg::op(1) keeps cells inside both forms, ~tf::csg::op(0) keeps cells outside form 0, and so on.

Cell provenance

Pass tf::return_source_ids to any make_csg_domains overload to also recover, for every cell face, which input form and original face it came from. The call returns two extra tf::offset_block_buffers whose blocks run parallel to cells:

auto [cells, ids, tag_blocks, face_blocks] =
    tf::make_csg_domains(graph, tf::return_source_ids);

// For face j of cell k:
//   tag_blocks[k][j]  -> which input form it came from
//   face_blocks[k][j] -> the original face id within that form

tag_blocks[k] and face_blocks[k] line up with cells[k].faces(). Uncut faces carry their own original id; a triangulated cut face carries the id of the face it was cut from. This is the per-cell analogue of the (tag_labels, face_labels) pair from tf::make_csg_mesh — use it to carry per-face attributes onto the extracted domains, or to color each cell by which operand's surface bounds it. All four overloads accept the tag; the plain { cells, ids } return is unchanged.

Cell index map

Pass tf::return_index_map instead for a single tf::csg_domains_index_map that folds in the face provenance and adds the point axis — the per-cell analogue of the arrangement's tf::mesh_arrangement_index_map. Because each cell re-deduplicates its own points, every axis is a tf::offset_block_buffer whose blocks run parallel to cells:

auto [cells, ids, imap] = tf::make_csg_domains(graph, tf::return_index_map);

// For cell k:
//   imap.face_tag_blocks[k][j] / imap.face_blocks[k][j]   -> face j -> (form, input face)
//   imap.point_tag_blocks[k][p] / imap.point_blocks[k][p] -> point p -> (form, input point)

There is no forward map — a shared boundary point or face belongs to several cells, so "input element → its cell element" is not single-valued; the map is inverse-only. Created intersection points have no input origin and carry the end sentinel per axis (tag → imap.n_tags, point id → imap.n_output_points). Cell points are emitted in cut order (not [originals | created]), so detect a created point by the tag sentinel, point_tag_blocks[k][p] == imap.n_tags — that check is always reliable, whereas the point-id sentinel can collide with a surviving input-point id under a filter. All four overloads accept the tag.

Cell Classification

auto [cells, ids, imap] = tf::make_csg_domains(graph, tf::return_index_map);

// imap.inclusion[k][i]: true iff cell k lies inside form i
for (std::size_t k = 0; k < cells.size(); ++k)
  if (imap.inclusion[k][0] && !imap.inclusion[k][1])
    use(cells[k]);   // inside form 0, outside form 1

imap.inclusion classifies every cell against every operand, so one extraction answers every selection — a mask picks the same cells the equivalent expression query would return. A sheet operand's column means "behind the sheet's normal". The matrix is a tf::blocked_buffer<bool, tf::dynamic_size> with block_size() == n_tags, one row per cell.

auto [cells, ids, imap] = tf::make_csg_domains(
    graph, tf::domain_config::ignore_open_fragments, tf::return_index_map);

for (std::size_t k = 0; k < cells.size(); ++k) {
  bool outer = true;
  for (std::size_t i = 0; i < std::size_t(imap.n_tags); ++i)
    outer = outer && !imap.inclusion[k][i];
  // outer: cell k is part of the outer shell
}

The outer shell is the space inside no operand — the unbounded outside, plus any void enclosed by nothing. Its cells are exactly the all-false rows, and there can be several: disjoint operand clusters each bound their own patch of the outside. exclude_outer_shell drops precisely these rows.

Sheets and Open Fragments

For a sheet, ignore_open_fragments governs whether its dangling part — fragments that seal nothing, like a knife's rim poking past the solids — partitions space. With the default (the flag set), only the sealed portion of the sheet cuts; the outside stays whole, and with the outer shell not excluded it returns as one closed inverted cell. With it cleared, the dangling part separates too: the outside splits into a front and a behind half, each an open inverted mesh — and the behind half carries the sheet bit, so exclude_outer_shell (which drops all-false rows) keeps it. Sheet bits are half-space indicators for bounded and unbounded regions alike: behind the normal is "inside", everywhere.

Configuration

A tf::domain_config coarsens the partition before extraction:

Both are on by default. Compose with |, or pass tf::domain_config::none to keep every raw cell, the outside included:

auto [cells, ids] =
    tf::make_csg_domains(graph, tf::domain_config::none);   // raw cells, universe kept

With exclude_outer_shell off, the outside is also recoverable as an expression — ~tf::csg::op(0) & ~tf::csg::op(1).

Outer Shell

tf::make_outer_shell repairs a self-intersecting mesh into a clean shell: the boundary of the union of everything it encloses.

auto shell = tf::make_outer_shell(mesh.polygons());

The mesh is split at its self-intersection curves, the volumetric domains are labeled, and only the faces bounding the unbounded outside are kept, oriented outward. Internal structure — overlap membranes between interpenetrating parts, faces buried inside the solid, enclosed cavities — is removed. The result is free of self-intersections and suitable as a boolean or csg-graph operand.

auto merged = tf::concatenated(a.polygons(), b.polygons());   // self-intersecting solid
auto shell = tf::make_outer_shell(merged.polygons());         // clean union boundary

The extraction is structural — no winding bits, no boolean expression. The unbounded universe is the most-negative-volume domain, and the shell is the boundary between it and everything else. This is the immersion-safe read: a self-overlapping form's double-covered pockets stay enclosed, where a winding-parity bit would drop them.

A graph overload reuses a build you already hold — the natural extraction for a one-form graph (see Self-Arrangements), valid for any N:

auto graph = tf::make_csg_graph(soup.polygons());
auto shell = tf::make_outer_shell(graph);

The mesh overload takes an optional tf::intersect_config (default primitives | resolve_contours) and tf::domain_config flags: ignore_open_fragments masks open fragments (surface pieces carrying boundary edges) out of the region formation instead of letting them partition; exclude_outer_shell is stripped — the extraction needs the outer label.

Intersection Curves

tf::make_intersection_curves returns the seam network of the arrangement — the polylines where surfaces of different forms cross — as a tf::curves_buffer:

auto graph  = tf::make_csg_graph(tf::make_range(forms));
auto curves = tf::make_intersection_curves(graph);

Edges are connected into maximal polylines. A coincident (coplanar) overlap contributes its contact border — the polyline where the coincidence ends — while the overlap's interior stays silent. Like the domains, this reads straight off the graph — no separate arrangement build.

Relationship to Cut

Anything binary fits cleanly in tf::make_boolean. N-ary or repeated boolean over the same forms is what the CSG module is for.