trueform

Examples | C++

Comparisons

Performance benchmarks against VTK, CGAL, and nanoflann with direct code comparisons.

These examples provide direct performance comparisons with established geometry processing libraries, demonstrating the efficiency of trueform's data structures and algorithms. Detailed benchmark results and performance analysis are available at /benchmarks.

vs nanoflann

k-NN Query Performance

Source: nanoflann/knn.cpp

Direct performance benchmark for k-Nearest Neighbor queries, comparing tf::tree against nanoflann's KD-tree implementation.

Features Showcased

Building tf::tree and nanoflann::KDTree from the same data source
Benchmarking k-NN query performance for varying k values
Creating nanoflann-compatible adaptor for trueform data structures

Example Code

knn_comparison.cpp

// Build trueform tree
tf::aabb_tree<int, float, 3> tf_tree(points, tf::config_tree(4, 4));
auto form = tf::make_form(tf_tree, points);

// Build nanoflann tree
using KDTree = nanoflann::KDTreeSingleIndexAdaptor<
    nanoflann::L2_Simple_Adaptor<float, PointCloudAdaptor>,
    PointCloudAdaptor, 3>;
KDTree nano_tree(3, adaptor, {10});

// Benchmark trueform
auto query_pt = tf::random_point<float, 3>();
std::array<tf::nearest_neighbor<int, float, 3>, 10> buffer;

tf::tick();
auto knn = tf::make_nearest_neighbors(buffer.begin(), 10);
tf::neighbor_search(form, query_pt, knn);
auto tf_time = tf::tock();

// Benchmark nanoflann
std::vector<size_t> indices(10);
std::vector<float> distances(10);

tf::tick();
nano_tree.knnSearch(query_pt.data(), 10,
                    indices.data(), distances.data());
auto nano_time = tf::tock();

std::cout << "Speedup: " << (nano_time / tf_time) << "x" << std::endl;

Performance: 1.8-2.0x speedup for k-NN queries. See benchmarks for detailed results.

vs CGAL

Collecting Intersecting Primitives

Source: cgal/intersecting_primitives.cpp

Direct comparison for collecting intersecting primitives between two meshes.

CGAL's all_intersecting_primitives returns only primitives on the first mesh that intersect any primitive on the second mesh, while trueform's tf::gather_ids returns all intersecting primitive pairs. Trueform does more work in less time.

Features Showcased

Building tf::tree acceleration structure
Applying transformations to tf::tree via tf::form
Using tf::gather_ids for efficient pair collection

Example Code

gather_ids.cpp

// Build forms
auto form0 = tf::make_form(tree, mesh.polygons());
auto form1 = tf::make_form(
    tf::make_frame(transform), tree, mesh.polygons());

// Collect all intersecting pairs
std::vector<std::pair<int, int>> pairs;
tf::gather_ids(form0, form1, tf::intersects_f,
               std::back_inserter(pairs));

Performance: 8-12x speedup over CGAL. See benchmarks for detailed results.

Intersection Curves

Source: cgal/intersection_curve.cpp

Direct comparison for computing intersection curves between two transforming meshes.

Features Showcased

Using tf::intersections_between_polygons to compute intersections
Extracting intersection edges with tf::make_intersection_edges
Tagging forms with tf::face_membership and tf::manifold_edge_link
Using points.as<double>() for type conversion views

Example Code

intersection_curves.cpp

// Build topology
tf::face_membership<int> fm1, fm2;
fm1.build(mesh1.polygons());
fm2.build(mesh2.polygons());

tf::manifold_edge_link<int, 3> mel1, mel2;
mel1.build(mesh1.faces(), fm1);
mel2.build(mesh2.faces(), fm2);

// Create forms with topology tags
auto form1 = tf::make_form(tree1,
    mesh1.polygons() | tf::tag(mel1) | tf::tag(fm1));
auto form2 = tf::make_form(tree2,
    mesh2.polygons() | tf::tag(mel2) | tf::tag(fm2));

// Compute intersections
tf::intersections_between_polygons<int, double, 3> ibp;
ibp.build(form1, form2);

// Extract intersection edges
auto edges = tf::make_intersection_edges(ibp);
auto segments = tf::make_segments(edges,
                                  ibp.intersection_points());

Performance: 30x+ speedup over CGAL for mesh-mesh intersection curves. See benchmarks for detailed scaling characteristics.

Planar Arrangements

Source: cgal/planar_arrangments.cpp

Direct comparison for computing planar arrangements from an unordered collection of 2D line segments.

Features Showcased

Using tf::planar_arrangements to extract oriented faces and hole relations
Using tf::make_edges and tf::make_points for semantic ranges

Example Code

planar_arrangements.cpp

// Build planar arrangement
tf::planar_arrangements<int, float> pa;
pa.build(segments);

// Access faces and holes
for (auto [face, hole_ids] :
     tf::zip(pa.faces(), pa.holes_for_faces())) {

    auto polygon = tf::make_polygon(face, pa.points());

    for (auto hole : tf::make_indirect_range(hole_ids, pa.holes())) {
        auto hole_polygon = tf::make_polygon(hole, pa.points());
        // Process hole
    }
}

Performance: 2273x speedup at 40k edges. CGAL exhibits superlinear complexity growth while trueform maintains near-linear scaling. See benchmarks for detailed analysis.

Connected Components

Source: cgal/connected_components.cpp

Direct comparison for labeling connected components in a mesh.

Features Showcased

Using tf::label_connected_components with custom connectivity rules
Using tf::make_applier to define traversal patterns

Example Code

connected_components.cpp

// Build connectivity structures
tf::face_membership<int> fm;
tf::manifold_edge_link<int, 3> mel;
fm.build(polygons);
mel.build(polygons.faces(), fm);

// Label components
tf::buffer<int> labels;
labels.allocate(polygons.size());

auto component_count = tf::label_connected_components<int>(
    labels,
    tf::make_applier(mel)  // Only traverse manifold edges
);

std::cout << "Found " << component_count
          << " connected components" << std::endl;

Performance: 4-8x speedup over CGAL, with increasing advantage at larger mesh sizes.

Mesh Booleans

Source: cgal/cgal-boolean.cpp

Direct comparison for computing boolean operations (union, intersection, difference) between two meshes.

Features Showcased

Using tf::make_boolean for set operations
Handling transformations in boolean operations
Extracting result mesh and intersection curves

Example Code

mesh_booleans.cpp

// Create forms with topology
auto form1 = tf::make_form(tree1,
    mesh1.polygons() | tf::tag(mel1) | tf::tag(fm1));
auto form2 = tf::make_form(tree2,
    mesh2.polygons() | tf::tag(mel2) | tf::tag(fm2));

// Compute boolean union
auto [result_mesh, labels, curves] = tf::make_boolean(
    form1, form2,
    tf::boolean_op::merge,
    tf::return_curves
);

std::cout << "Result: " << result_mesh.faces().size()
          << " faces" << std::endl;
std::cout << "Intersection curves: " << curves.size()
          << " paths" << std::endl;

Performance: 30-80x speedup over CGAL depending on mesh size. See benchmarks for detailed results.

Operations:merge (union), intersection, left_difference (A \ B), right_difference (B \ A)

vs VTK

Feature Edges

Source: vtk/feature_edges.cpp

Direct performance benchmark for extracting boundary and non-manifold edges.

Features Showcased

Using tf::make_boundary_edges for boundary extraction
Using tf::make_non_manifold_edges for topology analysis

Example Code

feature_edges.cpp

// Extract boundary edges
auto boundary_edges = tf::make_boundary_edges(polygons);
std::cout << "Boundary edges: " << boundary_edges.size() / 2
          << std::endl;

// Extract non-manifold edges
auto non_manifold_edges = tf::make_non_manifold_edges(polygons);
std::cout << "Non-manifold edges: " << non_manifold_edges.size() / 2
          << std::endl;

// With pre-computed topology
tf::face_membership<int> fm;
fm.build(polygons);

auto boundary = tf::make_boundary_edges(polygons | tf::tag(fm));
auto non_manifold = tf::make_non_manifold_edges(polygons | tf::tag(fm));

Performance: 10-30x speedup for boundary and non-manifold edge detection. See benchmarks for detailed results.

Mesh Cleaning

Source: vtk/compare_clean.cpp

Direct performance benchmark for cleaning meshes with specified tolerance. Trueform's implementation additionally removes all unreferenced points.

Features Showcased

Using tf::cleaned for tolerance-based duplicate removal
Automatic unreferenced point removal

Example Code

clean_mesh.cpp

// Clean mesh with tolerance
float tolerance = 1e-6f;
auto [clean_mesh, face_map, point_map] =
    tf::cleaned<int>(polygons, tolerance, tf::return_index_map);

std::cout << "Original: " << polygons.size() << " faces, "
          << polygons.points().size() << " points" << std::endl;
std::cout << "Cleaned: " << clean_mesh.faces().size() << " faces, "
          << clean_mesh.points().size() << " points" << std::endl;

// Reindex associated data
auto clean_normals = tf::reindexed(face_normals, face_map);
auto clean_attributes = tf::reindexed(point_attributes, point_map);

Performance: 10-20x speedup for mesh cleaning operations.

Intersection Curves

Source: vtk/vtk_intersection_curve.cpp

Direct comparison for computing intersection curves between two transforming meshes.

Features Showcased

Using tf::intersections_between_polygons with forms
Extracting intersection edges
Using tf::face_membership and tf::manifold_edge_link topology tags
Type conversion with points.as<double>()

Performance: 100x+ speedup over VTK for mesh-mesh intersection curves, with superlinear scaling advantage at larger problem sizes. See benchmarks for detailed results.

Core Functionality

Self-contained examples demonstrating primary features of trueform.

VTK Integration

Interactive applications demonstrating real-time collision detection, mesh booleans, and curve extraction.