Benchmarks for mesh connectivity analysis. See experimental setup for methodology.

Connected Components

Labeling of face-connected components. Topology is computed from scratch for each run. TrueForm uses tf::make_manifold_edge_connected_component_labels with parallel union-find; VTK uses vtkPolyDataConnectivityFilter; CGAL uses connected_components; libigl uses igl::facet_components.

Source: TrueForm, VTK, CGAL, libigl

Connected Components

libigl

Connected Components (Speedup)

vs

vs

vs libigl

TrueForm connected component labeling is 10× faster than CGAL, 16× faster than libigl, and 5× faster than VTK at 1M polygons.

Boundary Paths

Extraction of boundary edges organized into connected paths. Topology is computed from scratch for each run. TrueForm uses tf::make_boundary_paths with Hierholzer's algorithm; VTK uses vtkFeatureEdges; CGAL uses extract_boundary_cycles; libigl uses igl::boundary_loop.

Source: TrueForm, VTK, CGAL, libigl

Boundary Paths

libigl

Boundary Paths (Speedup)

vs

vs libigl

vs

TrueForm boundary path extraction is 11× faster than CGAL, 9× faster than libigl, and 14× faster than VTK at 1M polygons.

Half-Edge Construction

Construction of a navigable half-edge data structure from a polygon soup. Topology is computed from scratch for each run, including face membership (vertex→face connectivity). TrueForm uses tf::half_edges::build with a two-pass parallel algorithm and Eulerian boundary linking; CGAL uses PMP::polygon_soup_to_polygon_mesh.

Source: TrueForm, CGAL

Half-Edge Construction

Half-Edge Construction (Speedup)

vs

TrueForm half-edge construction is 8.5× faster than CGAL at 1M polygons.