M56kMeshToolsExt

Auxiliary mesh-pipeline tooling complementing M56kMeshTools:

• 2D polygon tessellation (concave outer + holes) and planar 3D polygon triangulation, for OpenGL render paths.
• Auto-orient — find the rotation (rx, ry, rz) that minimises one of three score functions over a triangle mesh (top-surface flatness, overhang area, bounding-box height).
• 2D nesting — automatic arrangement of irregular polygons on a bounded build plate. Public API stable, algorithm implementation staged for v0.2.
• A single cxx-bridge static library that exposes the three Rust crates above to C++ consumers under one mesh_ext::* namespace.

These are deliberately split from the main M56kMeshTools workspace so they ship on their own release cycle: the components inside are permissive replacements for several copyleft (LGPL-3.0, SGI-B-1.1) dependencies frequently used by slicer / CAD pipelines.

Why this exists

Many CAD and 3D-printing pipelines historically depend on:

Component	License	Replaced by
glu_libtess (Mesa3D)	SGI-B-1.1	tess2d
NLopt	LGPL-2.1+	auto_orient
libnest2d	LGPL-3.0	nesting2d (v0.2)

Linking any of these into a commercial product drags the whole binary under copyleft. The crates here rebuild the functionality from published mathematical literature and ship under permissive MIT OR Apache-2.0, with a cxx-bridge static library for direct C++ consumption.

Crates

• tess2d — 2D / planar-3D polygon triangulation wrapping the earcutr crate (MIT). API: triangulate(outer, holes) and triangulate_planar_3d(outer, holes, plane_normal).
• auto_orient — global Particle Swarm Optimisation (Kennedy & Eberhart 1995) followed by local Nelder-Mead simplex refinement (Nelder & Mead 1965). Three score functions: BestSurfaceQuality, ReducedOverhangs, LowestZHeight. Reproducible by seed.
• nesting2d — frozen public API for 2D irregular bin packing. The current release validates the input and returns NestingError::NotImplemented; the Bottom-Left + No-Fit Polygon implementation (Bennell & Oliveira 2008, Burke et al. 2007) ships in v0.2.
• mesh_ext_ffi — cxx-bridge wrapping the three crates above into a single static library (libmesh_ext_ffi.a / mesh_ext_ffi.lib) with a generated mesh_ext C++ namespace header.

All three library crates ship with #![forbid(unsafe_code)] at the workspace level; mesh_ext_ffi opts in only because cxx::bridge expands to internal unsafe extern "C" blocks.

Quick start (Rust)

use tess2d::{triangulate, Vec2};

let outer = vec![
    Vec2::new(0.0, 0.0),
    Vec2::new(1.0, 0.0),
    Vec2::new(1.0, 1.0),
    Vec2::new(0.0, 1.0),
];
let tris = triangulate(&outer, &[])?;
assert_eq!(tris.len(), 2);

use auto_orient::{optimize_rotation, Config, ScoreStrategy};

let cfg = Config {
    strategy: ScoreStrategy::ReducedOverhangs,
    accuracy: 0.25,
    overhang_threshold_deg: 60.0,
    seed: 0xC0FFEE,
};
let (rx, ry, rz) = optimize_rotation(&vertices, &faces, &cfg);

Quick start (C++, via mesh_ext_ffi)

cargo build --release -p mesh_ext_ffi produces:

• target/release/libmesh_ext_ffi.a (Unix) / target/release/mesh_ext_ffi.lib (MSVC)
• target/cxxbridge/mesh_ext_ffi/src/lib.rs.h — namespace mesh_ext

#include "mesh_ext_ffi/src/lib.rs.h"
using namespace mesh_ext;

// 2D tessellation
auto tris = ffi_triangulate(outer_ring, hole_rings);

// auto-orient
auto cfg = ffi_default_orient_config();
cfg.strategy = CScoreStrategy::ReducedOverhangs;
auto result = ffi_optimize_rotation(flat_vertices, flat_faces, cfg);

Minimal CMake integration:

add_custom_command(
    OUTPUT ${CMAKE_BINARY_DIR}/mesh_ext_ffi/libmesh_ext_ffi.a
    COMMAND cargo build --release -p mesh_ext_ffi
    WORKING_DIRECTORY ${CMAKE_SOURCE_DIR}/third_party/M56kMeshToolsExt)

add_library(mesh_ext_ffi STATIC IMPORTED GLOBAL)
set_target_properties(mesh_ext_ffi PROPERTIES
    IMPORTED_LOCATION ${CMAKE_SOURCE_DIR}/third_party/M56kMeshToolsExt/target/release/libmesh_ext_ffi.a
    INTERFACE_INCLUDE_DIRECTORIES
        ${CMAKE_SOURCE_DIR}/third_party/M56kMeshToolsExt/target/cxxbridge)

Or use corrosion for a maintained Cargo↔CMake bridge.

Provenance

Algorithms taken only from open published literature; no GPL/LGPL/SGI sources consulted.

• Mapbox earcut — the underlying 2D triangulation, exposed via the third-party earcutr crate (MIT).
• Kennedy J., Eberhart R., "Particle Swarm Optimization", Proc. IEEE Intl. Conf. on Neural Networks, 1995.
• Nelder J.A., Mead R., "A Simplex Method for Function Minimization", Computer Journal 7(4), 1965.
• Bennell J.A., Oliveira J.F., "The geometry of nesting problems: A tutorial", EJOR 184(2), 2008.
• Burke E.K., Hellier R.S.R., Kendall G., Whitwell G., "Complete and robust no-fit polygon generation for the irregular stock cutting problem", EJOR 179(1), 2007.

Build

Requires Rust 1.75+.

cargo build --workspace --release
cargo test  --workspace --release
cargo clippy --workspace --all-targets --release

Status

Item	State
tess2d — 2D + planar-3D triangulation	✓
auto_orient — PSO + Nelder-Mead, three score strategies	✓
nesting2d — public API stable	✓
nesting2d — algorithm implementation	v0.2
mesh_ext_ffi — cxx-bridge static library	✓
cargo test --workspace --release	26 pass
cargo clippy --workspace --all-targets --release	clean
Property tests (≥ 1024 cases) on tessellation	✓
unsafe outside mesh_ext_ffi	0

Safety

Workspace-wide [lints.rust] unsafe_code = "forbid". The only crate that opts out is mesh_ext_ffi, where cxx::bridge macro-expands into internal unsafe extern "C" blocks; the surface API exposed to either Rust or C++ callers is safe.

License

Dual-licensed under your choice of:

• MIT License
• Apache License 2.0

Copyright (c) 2026 Sarapin Vasiliy Dmitrievich.

Author

Vasiliy Sarapin (DevMercenary).

Issues and pull requests are welcome.