Arrangements and Volumes

This walkthrough takes a small CSG-flavoured scene — two overlapping cubes and a bisecting plane — and pushes it through trueform's arrangement pipeline. The result is a set of closed, manifold, outward-oriented volumes, each labelled by which signed side of the plane it sits on.

Source: arrangements.cpp

What the pipeline does

mesh_arrangements splits every face at every intersection and merges everything into one mesh, tagging each face with its source operand. make_domain_labels then partitions space into bounded volumetric regions ("domains"). split_into_domains finally emits one watertight outward-oriented submesh per domain. We add a small post-step that reads the slot convention on knife faces to label which volumes are above vs below the knife.

Building the scene

Two unit cubes offset along the x-axis so they overlap in the middle, and a 4×4 plane on z=0. The cubes are positioned via lazy frames (no point copies); the plane sits at its build position.

auto cube0 = tf::make_box_mesh<Index>(Real(2), Real(2), Real(2));
auto cube1 = tf::make_box_mesh<Index>(Real(2), Real(2), Real(2));
auto plane = tf::make_plane_mesh<Index>(Real(4), Real(4));

auto f0 = tf::make_frame(tf::make_transformation_from_translation(
    tf::vector<Real, 3>{Real(-0.5), Real(0), Real(0)}));
auto f1 = tf::make_frame(tf::make_transformation_from_translation(
    tf::vector<Real, 3>{Real( 0.5), Real(0), Real(0)}));
auto fid = tf::make_frame(tf::make_transformation_from_translation(
    tf::vector<Real, 3>{Real(0), Real(0), Real(0)}));

auto p0 = cube0.polygons() | tf::tag(f0);    // tag 0
auto p1 = cube1.polygons() | tf::tag(f1);    // tag 1
auto p_knife = plane.polygons() | tf::tag(fid);  // tag 2

decltype(p0) forms[] = {p0, p1, p_knife};

The two cubes alone produce three bounded regions (cube0-only, intersection, cube1-only). The plane bisects all three, so we expect six bounded domains.

Building the arrangement

auto [arr_raw, tag_labels_raw, face_labels_raw] =
    tf::make_mesh_arrangements(tf::make_range(forms, forms + 3));

The return is three buffers:

• arr_raw — the merged triangle mesh with all intersections resolved.
• tag_labels_raw[f] — which input operand face f came from (0, 1, or 2 here).
• face_labels_raw[f] — which face within that operand it came from.

For our scene this produces 176 faces, 48 points before cleaning.

Cleaning and reindexing tags

tf::cleaned does three things in one pass: it merges coincident vertices within a tolerance, drops topologically degenerate triangles (faces that collapse to a point or edge after merging), and removes duplicate triangles. With tf::return_index_map it also returns an index map describing exactly what happened to each face, so per-face attributes like tag_labels_raw can be reindexed through it to stay aligned with the cleaned mesh:

auto [arr, face_im, point_im] =
    tf::cleaned(arr_raw.polygons(), tf::epsilon<Real>, tf::return_index_map);
auto tag_labels = tf::reindexed(tf::make_range(tag_labels_raw), face_im);

tf::reindexed runs the index map over the range and emits a new buffer with face_im.kept_ids() worth of entries — exactly the right length for the cleaned mesh. In our scene cleaning takes us from 176 → 114 faces, 48 → 40 points.

Computing domain labels

auto dl = tf::make_domain_labels(arr.polygons(),
                                 tf::domain_config::ignore_open_fragments |
                                 tf::domain_config::exclude_outer_shell);

Two flags shape the output:

What survives is the bounded interior. For our scene dl.n_domains == 6. Each face f carries two domain ids:

• dl.labels[f][0] — the domain that contains f with reversed winding (the side f's stored normal points INTO).
• dl.labels[f][1] — the domain that contains f with forward winding.

That two-slot encoding is what makes the signed-side selection in the next step trivial.

Extracting the volumes

auto [volumes, comp_labels] = tf::split_into_domains(arr.polygons(), dl);

volumes[i] is a tf::polygons_buffer — a standalone watertight, manifold, outward-oriented submesh for the domain comp_labels[i]. split_into_domains reverses side-0 emissions and keeps side-1 emissions, so each cap face ends up pointing outward of its volume by construction.

For our scene: 6 volumes.

Selecting volumes by signed side of the knife

The knife (tag 2) has stored normal +Z. By the slot convention above, labels[f, 0] for an interior knife face is the domain on the +Z side, and labels[f, 1] is on the −Z side. Walking all interior knife faces and collecting the unique domain ids per side gives us the split:

tf::buffer<Index> above_ids, below_ids;
tf::generic_generate(
    tf::zip(tag_labels, dl.labels), std::tie(above_ids, below_ids),
    [&](auto elem, auto &buffers) {
      auto [tag, sides] = elem;
      if (tag != Index(2)) return;
      auto above = sides[0];
      auto below = sides[1];
      if (above >= dl.n_domains || below >= dl.n_domains) return;
      auto &[ab, be] = buffers;
      if (std::find(ab.begin(), ab.end(), above) == ab.end())
        ab.push_back(above);
      if (std::find(be.begin(), be.end(), below) == be.end())
        be.push_back(below);
    });

auto sort_unique = [](tf::buffer<Index> &b) {
  tbb::parallel_sort(b.begin(), b.end());
  b.erase_till_end(std::unique(b.begin(), b.end()));
};
sort_unique(above_ids);
sort_unique(below_ids);

A few things worth pulling out:

• tf::zip(tag_labels, dl.labels) walks both ranges in lockstep — no index gymnastics. Each yielded element is (tag, two-domain-slot).
• tf::generic_generate with the multi-buffer variant runs the body in parallel using thread-local buffers, then merges into above_ids / below_ids in one pass.
• Inner std::find dedup keeps each thread-local buffer small (capped at n_domains per side), so the post-merge parallel_sort + std::unique has almost nothing left to do.
• Sentinel skip (>= dl.n_domains) drops the knife faces that landed in the outer ring — those don't bound any real domain.

For our scene: 3 above, 3 below. The cube0-only, intersection, and cube1-only volumes each contribute one upper and one lower half.

Mapping domain ids to volume indices

comp_labels[i] tells us which domain volumes[i] represents. We invert that with one parallel pass:

tf::buffer<Index> domain_to_idx;
domain_to_idx.allocate_and_initialize(
    static_cast<std::size_t>(dl.n_domains), Index(-1));
tf::invert_map_with_nones(comp_labels, domain_to_idx, Index(-1));

tf::invert_map_with_nones writes domain_to_idx[comp_labels[i]] = i in parallel. Domain ids that don't appear in comp_labels keep the pre-filled sentinel -1.

Writing volumes and verifying

auto write_side = [&, &vols = volumes](const tf::buffer<Index> &ids,
                                        const char *prefix) {
  for (std::size_t k = 0; k < ids.size(); ++k) {
    auto v_idx = domain_to_idx[static_cast<std::size_t>(ids[k])];
    const auto &vol = vols[static_cast<std::size_t>(v_idx)];
    auto fname = std::string(prefix) + "_" + std::to_string(k) + ".stl";
    tf::write_stl(vol.polygons(), fname);
    std::cout << "  wrote " << fname << " (faces=" << vol.faces().size()
              << ", closed=" << tf::is_closed(vol.polygons())
              << ", manifold=" << tf::is_manifold(vol.polygons()) << ")"
              << std::endl;
  }
};
write_side(above_ids, "above");
write_side(below_ids, "below");

tf::is_closed checks that every edge is shared by exactly two faces (no boundary), and tf::is_manifold checks that no edge is shared by three or more. Every output volume should print closed=1, manifold=1 — the structural guarantee split_into_domains makes is verified at the boundary.

Running the example writes six STL files and prints:

=== Arrangement ===
Faces:  176
Points: 48

=== Cleaned ===
Faces:  114
Points: 40

=== Domain labels ===
Bounded domains: 6
Volumes extracted: 6

=== Signed side of the knife ===
Above (+normal): 3 volumes
Below (-normal): 3 volumes
  wrote above_0.stl (faces=22, closed=1, manifold=1)
  wrote above_1.stl (faces=24, closed=1, manifold=1)
  wrote above_2.stl (faces=22, closed=1, manifold=1)
  wrote below_0.stl (faces=24, closed=1, manifold=1)
  wrote below_1.stl (faces=22, closed=1, manifold=1)
  wrote below_2.stl (faces=22, closed=1, manifold=1)

The 24-face volumes are the intersection halves — they pick up parts of both cubes' inner walls, so their boundary surface is slightly larger than the cube-only halves.

Summary