Module computational_geometry 

Native computational geometry: robust predicates, topology/graph structures, Q42/10D adapters, and the computational-geometry algorithm families. Unlike the older specialized libraries this module is available to browser/WASM builds. Native computational geometry for QualiaDB.

A clean-room Rust implementation of the core computational-geometry algorithm families, built directly on the QualiaDB engine (10-D tensor, .10d container, wgpu/Forge, WASM, renderer). The functionality-specification reference is de Berg, Cheong, van Kreveld & Overmars, Computational Geometry: Algorithms and Applications (3rd ed.) — used as a public, textbook description of the algorithms and their correctness properties, not a source of code. Algorithms are expressed in Rust over caller-owned slices so the same implementation runs in the native engine and browser/WASM builds. Geometry is not renderer-only: the topology types are graph structures usable by the query, reasoning, simulation, and 10-D manifold layers.

Re-exports

pub use advancing_front::advancing_front_tetrahedralise_3d;

pub use advancing_front::advancing_front_triangulate_2d;

pub use advancing_front::FrontError;

pub use advancing_front::FrontOptions2d;

pub use advancing_front::FrontOptions3d;

pub use advancing_front::FrontResult2d;

pub use advancing_front::FrontResult3d;

pub use anisotropic_remesh::anisotropic_remesh;

pub use anisotropic_remesh::required_anisotropic_output_capacity;

pub use anisotropic_remesh::AnisotropicRemeshError;

pub use anisotropic_remesh::AnisotropicRemeshOptions;

pub use anisotropic_remesh::AnisotropicRemeshReport;

pub use anisotropic_remesh::FeatureEdge;

pub use arrangement_3d::build_arrangement_3d;

pub use arrangement_3d::radial_sort_around_edge;

pub use arrangement_3d::validate_arrangement;

pub use arrangement_3d::Arrangement3D;

pub use arrangement_3d::ArrangementError as Arrangement3DError;

pub use arrangement_3d::EdgeKey;

pub use arrangement_3d::Region;

pub use arrangement_3d::Shell;

pub use benchmark_corpus::compute_p10_corpus_baseline_hash;

pub use benchmark_corpus::run_p10_corpus;

pub use benchmark_corpus::CorpusReport;

pub use benchmark_corpus::CORPUS_VERSION;

pub use bentley_ottmann::bentley_ottmann_intersections;

pub use bentley_ottmann::brute_force_intersections;

pub use bentley_ottmann::brute_force_red_blue_intersections;

pub use bentley_ottmann::red_blue_intersections;

pub use bentley_ottmann::SweepSegment;

pub use boolean_2::boolean_difference_area;

pub use boolean_2::boolean_intersection_area;

pub use boolean_2::boolean_union_area;

pub use boolean_2::point_in_polygon;

pub use boolean_2::polygon_area;

pub use boolean_2::polygon_signed_area;

pub use boolean_2::verify_area_conservation;

pub use boolean_2::BooleanError;

pub use boolean_2::BooleanOp;

pub use boolean_3::boolean_3;

pub use boolean_3::boolean_3_exact;

pub use boolean_3::boolean_3_with_kernel;

pub use boolean_3::required_triangles_3;

pub use boolean_3::required_vertices_3;

pub use boolean_3::Boolean3Error;

pub use boolean_3::Boolean3Op;

pub use calipers_enclosing_disk::diameter_and_width;

pub use calipers_enclosing_disk::rotating_calipers;

pub use calipers_enclosing_disk::smallest_enclosing_disk;

pub use calipers_enclosing_disk::AntipodalPair;

pub use calipers_enclosing_disk::CalipersError;

pub use calipers_enclosing_disk::CalipersResult;

pub use calipers_enclosing_disk::Disk;

pub use calipers_enclosing_disk::EnclosingDisk;

pub use cdt_retriangulation::cdt_retriangulate_facet;

pub use cdt_retriangulation::CdtError;

pub use constrained_delaunay::conforming_delaunay_2;

pub use constrained_delaunay::constraint_edge_present;

pub use constrained_delaunay::ConstrainedDelaunayError;

pub use convex_decomposition::convex_decomposition_hm;

pub use convex_decomposition::convex_decomposition_triangulation;

pub use convex_decomposition::is_convex_polygon;

pub use convex_decomposition::verify_convex_decomposition;

pub use corefine_3d::corefine_3d;

pub use corefine_3d::count_shared_vertices;

pub use corefine_3d::verify_refinement_preserves_triangles;

pub use corefine_3d::CorefinementResult3D;

pub use corefine_3d::Mesh3D as Mesh3DCorefine;

pub use csg_section::decode_csg_section;

pub use csg_section::deserialize_expr;

pub use csg_section::encode_csg_section;

pub use csg_section::repair_mesh;

pub use csg_section::serialize_expr;

pub use csg_section::CsgSection;

pub use csg_section::CsgSectionError;

pub use csg_section::DecodedCsgSection;

pub use csg_section::RepairReport as MeshRepairReport;

pub use csg_section::CSG_MAGIC;

pub use csg_section::CSG_TYPE_ARRANGEMENT;

pub use csg_section::CSG_TYPE_EXPRESSION;

pub use csg_section::CSG_TYPE_REPAIR_REPORT;

pub use csg_section::CSG_VERSION;

pub use ddg_operators::boundary_of_boundary_is_zero;

pub use ddg_operators::boundary_of_simplex;

pub use ddg_operators::cotangent_laplacian;

pub use ddg_operators::curvature_angle_defect;

pub use ddg_operators::encode_ddg_operator_section;

pub use ddg_operators::face_vector_areas;

pub use ddg_operators::geodesic_distances_dijkstra;

pub use ddg_operators::harmonic_parameterize_disk;

pub use ddg_operators::heat_step;

pub use ddg_operators::hodge_decomposition_summary;

pub use ddg_operators::mean_curvature_flow_step;

pub use ddg_operators::parallel_transport_angle;

pub use ddg_operators::solve_poisson_jacobi;

pub use ddg_operators::surface_area_gradient;

pub use ddg_operators::vertex_normals;

pub use ddg_operators::ChainTerm;

pub use ddg_operators::CurvatureSample;

pub use ddg_operators::DdgError;

pub use ddg_operators::DdgReport;

pub use ddg_operators::DdgSectionHeader;

pub use ddg_operators::HodgeSummary;

pub use ddg_operators::SparseEntry;

pub use ddg_operators::DDG_SECTION_MAGIC;

pub use ddg_operators::DDG_SECTION_VERSION;

pub use delaunay_2::delaunay_triangulation_2;

pub use delaunay_2::triangulation_hash;

pub use delaunay_2::verify_delaunay;

pub use delaunay_2::DelaunayError;

pub use delaunay_refine::delaunay_refine_2;

pub use delaunay_refine::verify_refined_mesh;

pub use delaunay_refine::RefineError;

pub use delaunay_refine::RefineOptions;

pub use delaunay_refine::RUPPERT_TERMINATION_BOUND_DEG;

pub use deterministic_geometry::all_nearest_neighbours;

pub use deterministic_geometry::beta_skeleton_graph;

pub use deterministic_geometry::bichromatic_nearest_pair;

pub use deterministic_geometry::build_batch_dynamic_kd_tree;

pub use deterministic_geometry::conflict_graph_pairs;

pub use deterministic_geometry::deterministic_pack_u32;

pub use deterministic_geometry::deterministic_reduce_f64;

pub use deterministic_geometry::deterministic_scan_u64;

pub use deterministic_geometry::dynamic_kd_compact;

pub use deterministic_geometry::dynamic_kd_delete;

pub use deterministic_geometry::dynamic_kd_insert;

pub use deterministic_geometry::dynamic_kd_nearest;

pub use deterministic_geometry::euclidean_mst;

pub use deterministic_geometry::external_memory_nearest_tiles;

pub use deterministic_geometry::gabriel_graph;

pub use deterministic_geometry::generate_spatial_points;

pub use deterministic_geometry::greedy_spanner;

pub use deterministic_geometry::knn_graph;

pub use deterministic_geometry::list_rank_successors;

pub use deterministic_geometry::nearest_pair;

pub use deterministic_geometry::reproducible_benchmark_report;

pub use deterministic_geometry::reservation_batch_hull_2d;

pub use deterministic_geometry::seeded_incremental_order;

pub use deterministic_geometry::smallest_enclosing_ball;

pub use deterministic_geometry::tree_contract_roots;

pub use deterministic_geometry::well_separated_pairs;

pub use deterministic_geometry::BatchDynamicKdTree;

pub use deterministic_geometry::BenchmarkReport;

pub use deterministic_geometry::ConflictEdge;

pub use deterministic_geometry::DeterministicGeometryError;

pub use deterministic_geometry::DynamicKdRecord;

pub use deterministic_geometry::EnclosingBall;

pub use deterministic_geometry::NearestPair;

pub use deterministic_geometry::SpatialGeneratorKind;

pub use deterministic_geometry::WeightedEdge;

pub use deterministic_geometry::WellSeparatedPair;

pub use exact_arrangement::build_exact_arrangement;

pub use exact_arrangement::max_coordinate_error;

pub use exact_arrangement::verify_euler;

pub use exact_arrangement::verify_general_position_counts;

pub use exact_arrangement::zone_traversal;

pub use exact_arrangement::ArrangementEdge;

pub use exact_arrangement::ArrangementError;

pub use exact_arrangement::ArrangementVertex;

pub use exact_arrangement::ExactArrangement;

pub use exact_arrangement::ExactLine2;

pub use exact_arrangement::ZoneTraversal;

pub use fem_certificate::build_fem_certificate;

pub use fem_certificate::decode_fem_certificate;

pub use fem_certificate::encode_fem_certificate;

pub use fem_certificate::BoundaryMarker;

pub use fem_certificate::FemCertificate;

pub use fem_certificate::FemCertificateError;

pub use fem_certificate::MaterialRegion;

pub use fem_certificate::FEM_CERT_ENCODED_LEN;

pub use fem_certificate::FEM_CERT_MAGIC;

pub use fem_certificate::FEM_CERT_VERSION;

pub use fixture_registry::validate_records;

pub use fixture_registry::FixtureOrigin;

pub use fixture_registry::FixtureRecord;

pub use fixture_registry::FixtureRegistry;

pub use fixture_registry::FixtureRegistryError;

pub use fixture_registry::LicenceKind;

pub use fixture_registry::UsePermission;

pub use fixture_registry::SEED_FIXTURES;

pub use geometry_integration::build_section_header;

pub use geometry_integration::cancel_stream_at;

pub use geometry_integration::closeout_summary;

pub use geometry_integration::encode_section_header;

pub use geometry_integration::plan_stream_chunks;

pub use geometry_integration::renderer_descriptor;

pub use geometry_integration::schema_descriptor;

pub use geometry_integration::validate_conformance;

pub use geometry_integration::validate_conformance_matrix;

pub use geometry_integration::validate_operation_descriptor;

pub use geometry_integration::GeometryBackendKind;

pub use geometry_integration::GeometryCloseoutRecord;

pub use geometry_integration::GeometryConformanceMatrixRow;

pub use geometry_integration::GeometryConformanceRecord;

pub use geometry_integration::GeometryEvidenceLevel;

pub use geometry_integration::GeometryOperationDescriptor;

pub use geometry_integration::GeometryRenderableDescriptor;

pub use geometry_integration::GeometrySchemaDescriptor;

pub use geometry_integration::GeometrySchemaKind;

pub use geometry_integration::GeometrySectionHeader;

pub use geometry_integration::GeometryStreamChunk;

pub use geometry_integration::IntegrationError;

pub use geometry_integration::GEOMETRY_SECTION_MAGIC;

pub use geometry_workspace::deterministic_partition;

pub use geometry_workspace::deterministic_reduce;

pub use geometry_workspace::Cancellation;

pub use geometry_workspace::GeometryWorkspace;

pub use geometry_workspace::WorkspaceError;

pub use geometry_workspace::DEFAULT_WORKSPACE_BUDGET;

pub use gpu::emit_geometry_wgsl;

pub use gpu::evaluate_orientation_batch_f32;

pub use gpu::GeometryGpuError;

pub use gpu::GeometryGpuKernel;

pub use gpu::GeometryGpuSchedule;

pub use gpu::GPU_ORIENTATION_UNCERTAIN;

pub use gpu::evaluate_aabb_overlap_batch_f32;

pub use gpu::gpu_candidate_box_join;

pub use gpu::merge_aabb_overlap_results;

pub use gpu::GPU_OVERLAP_NO;

pub use gpu::GPU_OVERLAP_UNCERTAIN;

pub use gpu::GPU_OVERLAP_YES;

pub use gpu_3d::evaluate_point_in_tetra_batch_f32;

pub use gpu_3d::gpu_filter_point_in_tetra_f32;

pub use gpu_3d::point_in_tetra_wgsl;

pub use gpu_3d::Gpu3dError;

pub use gpu_3d::POINT_IN_TETRA_BOUNDARY;

pub use gpu_3d::POINT_IN_TETRA_INSIDE;

pub use gpu_3d::POINT_IN_TETRA_OUTSIDE;

pub use gpu_3d::POINT_IN_TETRA_STRIDE;

pub use gpu_3d::POINT_IN_TETRA_UNCERTAIN;

pub use half_plane_lp::half_plane_intersection;

pub use half_plane_lp::linear_program_2d;

pub use half_plane_lp::HalfPlane;

pub use half_plane_lp::HalfPlaneIntersection;

pub use half_plane_lp::LpResult2d;

pub use ham_sandwich::centrepoint;

pub use ham_sandwich::directional_width;

pub use ham_sandwich::ham_sandwich_cut;

pub use ham_sandwich::tukey_depth;

pub use ham_sandwich::width;

pub use ham_sandwich::width_coreset;

pub use ham_sandwich::Centrepoint;

pub use ham_sandwich::HamSandwichCut;

pub use ham_sandwich::WidthCoreset;

pub use kirkpatrick::KirkpatrickError;

pub use kirkpatrick::KirkpatrickHierarchy;

pub use math_geometry::barycentric_tetra;

pub use math_geometry::best_translation_registration;

pub use math_geometry::caratheodory_reduce_3d;

pub use math_geometry::convexity_certificate_polyline;

pub use math_geometry::cross_ratio_1d;

pub use math_geometry::curve_differential;

pub use math_geometry::frame_to_world;

pub use math_geometry::householder_reflect;

pub use math_geometry::hyperplane_eval;

pub use math_geometry::point_from_projective;

pub use math_geometry::project_points_to_plane;

pub use math_geometry::projective_from_point;

pub use math_geometry::quaternion_normalize;

pub use math_geometry::quaternion_slerp;

pub use math_geometry::quaternion_to_matrix;

pub use math_geometry::schur_complement_2x2;

pub use math_geometry::separating_plane_aabb;

pub use math_geometry::so3_exp;

pub use math_geometry::so3_log;

pub use math_geometry::solve_diagonal_quadratic;

pub use math_geometry::surface_patch_differential;

pub use math_geometry::world_to_frame;

pub use math_geometry::AffineFrame3;

pub use math_geometry::ConvexityCertificate;

pub use math_geometry::CurveDifferential;

pub use math_geometry::HomogeneousPoint3;

pub use math_geometry::Hyperplane3;

pub use math_geometry::MathGeometryError;

pub use math_geometry::QuadraticSolution;

pub use math_geometry::Quaternion;

pub use math_geometry::SeparatingPlane;

pub use math_geometry::SurfaceDifferential;

pub use mesh_quality::check_field_conformance_tet;

pub use mesh_quality::check_field_conformance_tri;

pub use mesh_quality::tet_mesh_quality_slice;

pub use mesh_quality::tet_quality;

pub use mesh_quality::tet_quality_points;

pub use mesh_quality::tri_mesh_quality_2d;

pub use mesh_quality::tri_quality;

pub use mesh_quality::tri_quality_points;

pub use mesh_quality::tri_signed_area_2d;

pub use mesh_quality::AnisotropyField;

pub use mesh_quality::FieldConformance;

pub use mesh_quality::MeshQualityError;

pub use mesh_quality::MetricTensor;

pub use mesh_quality::SizeField;

pub use mesh_quality::TetMeshQualityStats;

pub use mesh_quality::TetQuality;

pub use mesh_quality::TriMeshQualityStats;

pub use mesh_quality::TriQuality;

pub use mixed_cell_topology::extract_boundary_faces;

pub use mixed_cell_topology::hex_to_tetrahedra;

pub use mixed_cell_topology::quad_to_triangles;

pub use mixed_cell_topology::tets_to_mixed;

pub use mixed_cell_topology::triangles_to_mixed;

pub use mixed_cell_topology::validate_mixed_cells;

pub use mixed_cell_topology::BoundaryFace;

pub use mixed_cell_topology::MixedCell;

pub use mixed_cell_topology::MixedTopologyError;

pub use mixed_cell_topology::MixedTopologyReport;

pub use mixed_cell_topology::CELL_KIND_HEX;

pub use mixed_cell_topology::CELL_KIND_QUAD;

pub use mixed_cell_topology::CELL_KIND_TETRA;

pub use mixed_cell_topology::CELL_KIND_TRIANGLE;

pub use motion_planning::belief_update_2d;

pub use motion_planning::configuration_obstacle_translate;

pub use motion_planning::continuous_segment_collision;

pub use motion_planning::coverage_lawnmower;

pub use motion_planning::feedback_vector;

pub use motion_planning::forward_kinematics_2d;

pub use motion_planning::interpolate_pose2;

pub use motion_planning::jacobian_2d;

pub use motion_planning::kinodynamic_propagate;

pub use motion_planning::multi_robot_conflict_free;

pub use motion_planning::normalize_pose;

pub use motion_planning::normalize_pose3;

pub use motion_planning::pursuit_step;

pub use motion_planning::rrt_plan;

pub use motion_planning::seeded_roadmap;

pub use motion_planning::segment_collision_free;

pub use motion_planning::time_parameterize_path;

pub use motion_planning::visibility_graph_path;

pub use motion_planning::BeliefState2;

pub use motion_planning::CollisionReport;

pub use motion_planning::Control2;

pub use motion_planning::Joint2;

pub use motion_planning::PlannedPath;

pub use motion_planning::PlanningError;

pub use motion_planning::PolygonObstacle;

pub use motion_planning::Pose2;

pub use motion_planning::Pose3;

pub use motion_planning::TimedPose2;

pub use nary_boolean::evaluate_expr;

pub use nary_boolean::nary_boolean;

pub use nary_boolean::BoolExpr;

pub use nary_boolean::MeshInput;

pub use nary_boolean::NaryBoolError;

pub use nary_boolean::RegionMask;

pub use nary_boolean::MAX_OPERANDS;

pub use nary_csg::corefine_2d;

pub use nary_csg::nary_csg;

pub use nary_csg::verify_pairwise_inclusion_exclusion;

pub use nary_csg::CorefinementResult2D;

pub use nary_csg::Mesh2D;

pub use nary_csg::NaryCsgError;

pub use nary_csg::NaryCsgResult;

pub use nary_csg::NaryOp;

pub use nary_csg::PolygonWithHoles as NaryPolygonWithHoles;

pub use parametric_cad::bezier_derivative_eval;

pub use parametric_cad::bezier_eval;

pub use parametric_cad::bspline_eval;

pub use parametric_cad::bspline_insert_uniform_knot;

pub use parametric_cad::budgeted_evolution_optimize;

pub use parametric_cad::classify_trim_uv;

pub use parametric_cad::continuity_between_curves;

pub use parametric_cad::helical_lattice;

pub use parametric_cad::latin_hypercube_samples;

pub use parametric_cad::loft_profiles;

pub use parametric_cad::nurbs_eval;

pub use parametric_cad::offset_polyline;

pub use parametric_cad::rbf_surrogate_predict;

pub use parametric_cad::revolve_profile;

pub use parametric_cad::sdf_compose;

pub use parametric_cad::sdf_eval;

pub use parametric_cad::shape_distance;

pub use parametric_cad::tensor_surface_eval;

pub use parametric_cad::tensor_surface_sample;

pub use parametric_cad::tube_along_polyline;

pub use parametric_cad::validate_parameters;

pub use parametric_cad::vascular_lattice_adapter_notice;

pub use parametric_cad::CadError;

pub use parametric_cad::ContinuityReport;

pub use parametric_cad::DomainAdapterNotice;

pub use parametric_cad::NurbsControlPoint;

pub use parametric_cad::OptimizationReport;

pub use parametric_cad::ParameterConstraint;

pub use parametric_cad::SdfOp;

pub use parametric_cad::SdfPrimitive;

pub use parametric_cad::ShapeDistance;

pub use parametric_cad::SurfaceSample;

pub use parametric_cad::SurrogatePrediction;

pub use point_location::build_slab_map;

pub use point_location::locate_point;

pub use point_location::point_in_triangle;

pub use point_location::point_strictly_in_triangle;

pub use point_location::triangulation_to_subdivision;

pub use point_location::walk_locate;

pub use point_location::LocateResult;

pub use point_location::PointLocationError;

pub use point_location::SlabMap;

pub use point_location::SubdivisionEdge;

pub use polygon_soup::build_face_adjacency;

pub use polygon_soup::count_flipped;

pub use polygon_soup::filter_degenerate_faces;

pub use polygon_soup::merge_vertices;

pub use polygon_soup::orient_consistently;

pub use polygon_soup::repair_polygon_soup;

pub use polygon_soup::FaceAdjacencyEntry;

pub use polygon_soup::RepairReport;

pub use polygon_soup::SoupError;

pub use polygon_validation::canonicalize_polygon_with_holes;

pub use polygon_validation::canonicalize_simple_polygon;

pub use polygon_validation::repair_for;

pub use polygon_validation::validate_polygon_with_holes;

pub use polygon_validation::validate_pslg;

pub use polygon_validation::validate_simple_polygon;

pub use polygon_validation::PolygonWithHoles;

pub use polygon_validation::PslgEdge;

pub use polygon_validation::RepairSuggestion;

pub use polygon_validation::ValidationIssue;

pub use polygon_validation::ValidationReport;

pub use quad_octree_mesh::balance_octtree_2to1;

pub use quad_octree_mesh::balance_quadtree_2to1;

pub use quad_octree_mesh::build_octtree;

pub use quad_octree_mesh::build_quadtree;

pub use quad_octree_mesh::const_size_fn_3d;

pub use quad_octree_mesh::octtree_to_hexahedra;

pub use quad_octree_mesh::octtree_to_tetrahedra;

pub use quad_octree_mesh::quadtree_to_triangles;

pub use quad_octree_mesh::size_field_2d_fn;

pub use quad_octree_mesh::size_target_refiner_2d;

pub use quad_octree_mesh::size_target_refiner_3d;

pub use quad_octree_mesh::OctLeaf;

pub use quad_octree_mesh::OctMeshError;

pub use quad_octree_mesh::OctMeshOptions;

pub use quad_octree_mesh::OctNode;

pub use quad_octree_mesh::OctTree;

pub use quad_octree_mesh::QuadLeaf;

pub use quad_octree_mesh::QuadMeshError;

pub use quad_octree_mesh::QuadMeshOptions;

pub use quad_octree_mesh::QuadNode;

pub use quad_octree_mesh::QuadTree;

pub use quad_octree_mesh::OCT_MAX_LEVEL;

pub use quad_octree_mesh::QUAD_MAX_LEVEL;

pub use query_frontend::QueryFrontendError;

pub use query_frontend::QueryStats;

pub use query_frontend::SpatialIndexQuery;

pub use range_reporting::CuttingTree;

pub use range_reporting::Halfspace2;

pub use range_reporting::KdTree2;

pub use range_reporting::PartitionTree;

pub use screened_poisson::required_screened_poisson_capacity;

pub use screened_poisson::screened_poisson_reconstruct_3d;

pub use screened_poisson::ScreenedPoissonError;

pub use screened_poisson::ScreenedPoissonOptions;

pub use screened_poisson::ScreenedPoissonReport;

pub use segment_intersection_2::classify_and_construct;

pub use segment_intersection_2::classify_segment_intersection_2;

pub use segment_intersection_2::line_segment_intersection_2;

pub use segment_intersection_2::ray_segment_intersection_2;

pub use segment_intersection_2::SegmentIntersectionClass;

pub use segment_intersection_2::SegmentIntersectionResult;

pub use segment_intersection_2::TJunctionSide;

pub use simplify_snap::simplify_coplanar_regions;

pub use simplify_snap::snap_round_3d;

pub use simplify_snap::SimplifyError;

pub use simplify_snap::SimplifyOptions;

pub use simplify_snap::SimplifyResult;

pub use sos::orient_3d_sos;

pub use tet_quality_improve::improve_tet_mesh;

pub use tet_quality_improve::verify_improvement;

pub use tet_quality_improve::TetImproveError;

pub use tet_quality_improve::TetImproveObjective;

pub use tet_quality_improve::TetImproveOptions;

pub use tet_quality_improve::TetImproveResult;

pub use trapezoidal_map::TmSegment;

pub use trapezoidal_map::Trapezoid;

pub use trapezoidal_map::TrapezoidalMap;

pub use trapezoidal_map::TrapezoidalMapError;

pub use triangulation_2::triangulate_ear_clipping;

pub use triangulation_2::triangulate_monotone;

pub use triangulation_2::triangulate_polygon;

pub use triangulation_2::verify_triangulation;

pub use triangulation_2::Triangle;

pub use triangulation_opt::evaluate_objective;

pub use triangulation_opt::optimise_and_evaluate;

pub use triangulation_opt::optimise_triangulation;

pub use triangulation_opt::TriObjective;

pub use triangulation_opt::TriangulationOptError;

Modules

advancing_front

P13.5 — Advancing-front surface (2-D) and volume (3-D) meshing with deterministic shortest-edge/face-first ordering, self-crossing guards, and typed obstructions. P13.5 - Advancing-front surface and volume meshing.

anisotropic_remesh

P13.8 - Anisotropic remeshing with crease/feature preservation and BVH-pruned surface projection. P13.8 - Anisotropic surface remeshing with feature preservation.

arrangement_3d

P12.6 — Radial sort and Weiler 3-D arrangement model. Radial sort and Weiler 3-D arrangement model (P12.6).

arrangements

P11.8 — Arrangements, point-line duality, and topological sweep. P11.8 — Arrangements, point-line duality, and topological sweep.

authoring

P9.5 — Authoring ergonomics: primitives, transforms, scene graph, .10d export. P9.5 — Authoring ergonomics: scene construction, primitives, transforms.

benchmark_corpus

P10.7 — Benchmark + adversarial corpus baseline (versioned corpora, reproducible latency/allocation/hash reports). P10.7 — Benchmark + adversarial corpus baseline.

bentley_ottmann

P11.2 — Bentley-Ottmann sweep and output-sensitive red/blue intersection. P11.2 — Bentley-Ottmann sweep and output-sensitive red/blue intersection.

boolean_2

2-D polygon boolean set operations (P4.7).

boolean_3

P5.5 — 3-D Boolean / corefinement operations on triangle meshes.

calipers_enclosing_disk

P11.13 — Rotating calipers (diameter, width, antipodal pairs) and smallest enclosing disk (Welzl randomized incremental, seeded determinism). P11.13 — Output-sensitive hull, rotating-calipers diameter/width, and smallest enclosing disk.

capability_manifests

P9.4 — qapp/MCP capability manifests (per-op resource limits; backends). P9.4 — qapp/MCP capability manifests: per-op resource limits and backend descriptors (scalar / SIMD / wgpu / CUDA / exact-fallback).

cdt_retriangulation

P12.4 — Per-facet exact constrained Delaunay re-triangulation. Per-facet exact constrained Delaunay re-triangulation (P12.4).

cknn_laplacian

P8.4 — CkNN density → graph Laplacian → Laplace-Beltrami. P8.4 — CkNN density estimation → graph Laplacian converging to Laplace-Beltrami (manifold-consistent baking).

constrained_delaunay

Constrained and conforming Delaunay triangulation (P4.5).

convex_decomposition

Convex decomposition (Hertel-Mehlhorn + triangulation-only). Convex decomposition of simple polygons (P11.3).

corefine_3d

P12.3 — Exact 3D mesh co-refinement (split meshes along intersection curves). Exact 3-D mesh co-refinement (P12.3).

csg_section

P12.9 — CSG/arrangement .10d sections and repair operations. CSG/arrangement .10d sections and repair operations (P12.9).

dcel_overlay

P11.3 — DCEL subdivision, overlay, and full polygon-set boolean output (union/intersection/difference/xor with boundary cycles + holes; Euler and area identities). P11.3 — DCEL subdivision, overlay, and full polygon-set boolean output.

ddg_operators

P14 - Discrete differential geometry and surface operators.

delaunay_2

Delaunay triangulation 2-D (P4.4).

delaunay_refine

P13.2 — Delaunay refinement for PSLGs with Steiner points (Ruppert). P13.2 - Delaunay refinement for PSLGs with Steiner points (Ruppert).

deterministic_geometry

P15 - Deterministic parallel primitives, dynamic indices, and spatial graphs.

exact_arrangement

P12.2 — Exact 2D arrangement with exact-construction intersection points. Exact 2D arrangement with exact-construction intersection points (P12.2).

fem_certificate

P13.10 - FEM-ready mesh certificates and canonical encoding.

fixture_registry

P10.6 — Independent oracle and fixture licence registry (origin, licence, checksum, permitted use; rejects copyleft; textbook = invariant reference only, no copied material). P10.6 — Independent oracle and fixture licence registry.

geometry_integration

P19 - Expanded ABI, typed descriptors, conformance, and closeout records.

geometry_workspace

P10.5 — Geometry workspace: caller-owned arenas with byte budgets, deterministic partition/reduction order, and cancellation. P10.5 — Geometry workspace: caller-owned arenas with byte budgets, deterministic partition/reduction order, and cancellation.

gpu

Typed WGSL geometry kernels with deterministic CPU oracles.

gpu_3d

P5.9 — GPU 3-D point-in-tetrahedron cull batch, with a deterministic CPU oracle.

gpu_oracle

P8.7 — GPU acceleration + CPU oracle for P8 batches. P8.7 — GPU acceleration + CPU oracle for the P8 distance/density/ circumradius batches (differential + determinism).

half_plane_lp

P11.9 — Half-plane intersection (sort-and-intersect + deque) and 2-D randomized incremental linear programming (Seidel) with seeded determinism and feasible/infeasible/unbounded certificates. P11.9 — Half-plane intersection and fixed-dimensional randomized linear programming (2-D).

ham_sandwich

P11.14 — Ham-sandwich cuts, centrepoints, and directional-width coresets. Ham-sandwich cuts, centrepoints, and directional-width coresets (P11.14).

kirkpatrick

P11.7 — Kirkpatrick hierarchy for guaranteed O(log n) point location in triangulated planar subdivisions. Kirkpatrick hierarchy for O(log n) point location in planar subdivisions (P11.7).

math_geometry

P17 - N-D affine, projective, convex, Lie, and smooth geometry.

mesh_quality

P13.1 — Mesh quality metrics (tri/tet min/max angle, radius-edge, aspect, scaled Jacobian, dihedral) and isotropic size / anisotropic metric fields. P13.1 - Mesh quality metrics and size/anisotropy fields.

mixed_cell_topology

P13.9 - Quadrilateral/hexahedral and mixed-cell topology foundation.

motion_planning

P16 - Collision detection and motion planning.

nary_boolean

P12.7 — Arbitrary n-ary boolean-expression evaluator. Arbitrary n-ary boolean-expression evaluator (P12.7).

nary_csg

P12.1 — N-ary CSG operations on 2D polygons and 2D mesh co-refinement. N-ary CSG operations on 2D polygons (P12.1).

natural_neighbour

P8.5 — Natural-neighbour interpolation (Sibson / Laplace weights). P8.5 — Natural-neighbour interpolation (Sibson / Laplace weights) over the substrate’s Delaunay/Voronoi.

nn_query

P8.6 — Nearest-neighbour inference query (radius + kNN). P8.6 — Nearest-neighbour inference query: “distance < threshold ⇒ related, zero graph traversal” over a spatial index.

parametric_cad

P18 - Parametric CAD, procedural lattices, and shape optimisation.

persistence

P8.2 — Persistent homology: deterministic reduction → barcode. P8.2 — Persistent homology: deterministic reduction → persistence pairs / barcode (H0/H1) as v-class evidence.

point_location

P11.6 — Point location in planar subdivisions (walking + slab decomposition). Point location in planar subdivisions (P11.6).

polygon_soup

Polygon-soup ingestion + repair.

polygon_validation

P11.4 — Simple-polygon, polygon-with-holes, and PSLG validation. P11.4 — Simple-polygon, polygon-with-holes, and PSLG validation.

quad_octree_mesh

P13.4 — Quadtree/octree balanced meshing (size-field refinement, 2:1 balance, conforming 2-D triangulation with hanging-node templates, 3-D hex/tet extraction). P13.4 - Quadtree / octree balanced meshing.

query_frontend

Scan-free query front-end — unified spatial query API over a loaded .10d spatial-index section (P3.8).

range_reporting

P11.12 — Simplex/halfspace range reporting with partition and cutting trees. Simplex and halfspace range reporting with partition and cutting trees (P11.12).

range_trees

P11.10 — Interval, segment, hereditary segment, priority-search and range trees. P11.10 — Interval, segment, hereditary segment, priority-search and range trees.

screened_poisson

P13.6 - Screened-Poisson surface reconstruction.

segment_intersection_2

P11.1 — Robust segment/line/ray primitives and exact intersections. P11.1 — Robust segment/line/ray primitives and exact intersections.

simplify_snap

P12.8 — Coplanar-region simplification and topology-preserving snap rounding. Coplanar-region simplification and topology-preserving snap rounding (P12.8).

sos

P12.2 — Simulation of Simplicity for deterministic degeneracy resolution. P12.2 — Simulation of Simplicity (SoS) for deterministic degeneracy resolution.

statistical_manifold

P8.3 — Statistical manifold: Fisher metric + KL as Bregman divergence. P8.3 — Statistical manifold: probability-simplex ops + Fisher metric + KL as a Bregman divergence.

tet_quality_improve

P13.7 — Tetrahedral quality improvement and sliver handling (flip / smooth / insert / exude passes; domain + orientation preserved; monotonic quality improvement). P13.7 - Tetrahedral quality improvement and sliver handling.

trapezoidal_map

P11.6 gap — Trapezoidal map with randomized incremental point location (search DAG, seeded determinism, O(log n) expected query). Trapezoidal map with randomized incremental point location (P11.6 gap).

triangulation_2

P11.5 — Monotone partition, linear monotone triangulation, ear fallback. P11.5 — Monotone partition, linear monotone triangulation, and guarded ear fallback.

triangulation_opt

P13.3 — Optimal fixed-vertex triangulation objectives (edge-flip hill-climbing). P13.3 - Optimal fixed-vertex triangulation objectives.

voronoi_variants

P11.11 — Segment-site, farthest-site and higher-order Voronoi diagrams. P11.11 — Segment-site, farthest-site and higher-order Voronoi diagrams.

vr_filtration

P8.1 — VR / alpha filtration over Tensor10D point cloud. P8.1 — Simplicial-complex core: caller-buffered VR / alpha filtration over the Tensor10D point cloud.

Structs

Aabb

Axis-aligned bounding box in 3D.

AlphaEdge

An alpha-shape edge: (i, j) with i < j, plus classification.

AlphaShapeReport

Alpha shape result: classified triangles and edges.

BoundaryLoopWalker

Boundary-loop walker: walks along boundary half-edges.

BoxPair

A pair of overlapping box indices (a_index, b_index).

BvhNode

BVH node: 48 bytes, repr(C), naturally aligned.

CknnEdge

CkNN graph edge: (i, j) with i < j, plus the squared distance.

ConnectivitySummary

Summary of mesh connectivity invariants.

CsrHeader

CSR adjacency header: describes the layout of a CSR adjacency stream.

CsrSummary

Summary of a built CSR adjacency view.

Dart

One dart of a 2-map. Field-for-field identical to HalfEdge (renamed): beta1 == next, beta2 == twin, face == face, origin == origin.

DecimateOptions

Options controlling how far decimation proceeds.

DecimateReport

What decimation actually produced.

DecodedRecon

Decoded reconstruction section.

EdgeSlot

Caller-owned open-addressing slot used while constructing twins.

ExactConstructionKernel

An exact-construction kernel that implements [GeometryKernel].

ExactPoint2

An exact point in 2D, constructed as a rational pair: x = x_num / den, y = y_num / den, where den > 0.

ExactPoint3

An exact point in 3-D, stored as a rational vector with a shared denominator: x = x_num/den, y = y_num/den, z = z_num/den, den > 0.

ExactTriTriSegment

The (exact, rational) intersection segment of two triangles.

FaceLoopCirculator

Face-loop circulator: visits the half-edges of a triangle face in order.

FilteredF64Kernel

The default filtered-f64 kernel — the fast path.

HalfEdge

One directed edge in a triangle half-edge graph.

KdNode

kd-tree node: 32 bytes, repr(C), naturally aligned.

KernelExactPoint2

Optional exact-construction capabilities. A kernel MAY implement this trait in addition to GeometryKernel; algorithms that need exact construction require K: GeometryKernel + ConstructionKernel at compile time.

KnnEntry

A kNN result entry: (point_index, squared_distance).

OneRingCirculator

One-ring vertex circulator: visits vertices adjacent to a center vertex.

PersistencePair

A persistence pair: (birth, death) for a topological feature.

Point2

POD 2D point used by CPU, WASM, and serialized tool boundaries.

Point3

POD 3D point used by mesh and spatial-index ports.

RayTriangleHit

Result of a 3D ray-triangle intersection test.

RemeshOptions

Tuning parameters for isotropic_remesh.

RemeshReport

What a remeshing run did. All counts are cumulative across every pass.

Simplex

A simplex in the alpha filtration.

SpatialOrderHeader

20-byte header for a spatial-order code stream.

SurfaceMeshView

A read-only surface-mesh view over a half-edge graph.

TopologySummary

TriPair

An unordered pair of intersecting triangle indices (a < b), canonical form.

TriTriSegment

The (approximate, f64-constructed) intersection segment of two triangles.

Unsupported

Typed error returned by a ConstructionKernel method when the kernel does not support the requested construction.

VoronoiEdge

A Voronoi edge connecting two Voronoi vertices (or extending to infinity for boundary edges, where neighbor_triangle is None).

VoronoiVertex

A Voronoi vertex (circumcenter of a Delaunay triangle).

Enums

AlphaShapeError

Alpha shape error.

BoxJoinError

Error type for box-intersection join.

BvhError

Errors raised by the BVH builder.

CMapError

Errors raised by the combinatorial-map core. Each variant names the specific invariant that was violated so callers can surface a precise diagnostic.

ConnectivityError

Errors raised by the connectivity invariant functions.

CsrError

Errors raised by the CSR adjacency builders.

DecimateError

Failure modes for QEM decimation. All are input-integrity or buffer-sizing faults surfaced fail-closed; a finite, in-bounds mesh always decimates to a finite result.

Delaunay3Error

Delaunay tetrahedralization error.

EdgeClass

Classification of a Delaunay edge in the alpha shape.

Exact3Error

Errors from exact 3-D construction. All fail-closed.

ExpansionError

Errors from expansion arithmetic operations. All are fail-closed: the caller must provide sufficiently large buffers.

FeatureError

GeometryToolError

Hull3Error

Failure modes for the 3-D convex-hull builder.

HullError

IsosurfaceError

Isosurface extraction error.

KdTreeError

LaplacianError

Laplacian construction error.

MeshMeasureError

Failure modes for the surface-mesh measures. Both are input-integrity faults, not numeric ones — a finite mesh with in-bounds indices always yields a finite measure.

MinkowskiError

Minkowski sum error.

Orientation

ParameterSpan

Sign classification of the intersection parameter t = t_num/den relative to the segment span [0, 1], decided exactly. This lets a caller tell whether the plane crossing falls within the segment (p, q) (t ∈ [0,1]) versus on the infinite-line extension — without rounding t.

PointSetError

Point-set processing error.

RayTriangleResult

Result of a 3D ray-triangle intersection.

ReconSectionError

Reconstruction section error.

ReconstructionError

Surface reconstruction error.

RemeshError

Failure modes for isotropic_remesh.

SegmentIntersection2d

Result of a 2D segment-segment intersection test.

Sign

Three-valued sign of a real number.

SpatialOrderError

Errors raised by the spatial ordering functions.

SurfaceMeshError

Error type for surface-mesh view construction.

TdaError

TDA / persistence error.

TopologyError

TriTriError

Failure modes for triangle–triangle intersection and mesh self-intersection.

TriangleClass

Classification of a Delaunay triangle in the alpha shape.

TriangleContainment

Whether a constructed line/plane crossing lies inside triangle (a, b, c), decided exactly.

VoronoiError

Voronoi diagram error.

Constants

BVH_NODE_SIZE

Node size in bytes.

GEOMETRY_ABI_VERSION

Versioned native geometry ABI. Increment only when public POD layouts or caller-buffer contracts change.

INVALID_INDEX

KD_NODE_SIZE

MAX_BVH_DEPTH

Maximum BVH depth (bounded by 2^21 primitives → 21 levels).

MAX_EXPANSION_INCIRCLE

Maximum expansion length for the incircle predicate (3×3 determinant with squared-distance entries: 6 terms × products of up to 4-component expansions, summed → length ≤ 96 without compression).

MAX_EXPANSION_INSPHERE

Maximum expansion length for the insphere predicate (5×5 determinant with squared-distance entries: 120 terms × products of up to 6-component expansions, summed → length ≤ 2048 without compression; with aggressive zero-elimination the actual length is much smaller, but this bound ensures the workspace is always sufficient).

MAX_EXPANSION_ORIENT2

Maximum expansion length for the orient2d predicate (2×2 determinant of differences: 2 terms × 2-component products, summed → length ≤ 8).

MAX_EXPANSION_ORIENT3

Maximum expansion length for the orient3d predicate (3×3 determinant of differences: 6 terms × 3-component products, summed → length ≤ 24 without compression; with compression the actual length is smaller).

MAX_K

Maximum k supported (bounded for stack arrays).

MAX_KD_DEPTH

RECON_HEADER_SIZE

Header size (fixed part before vertex/triangle data).

RECON_MAGIC

Magic bytes for reconstruction sections: “RCNS”.

RECON_TYPE_ALPHA_SHAPE_2D

Reconstruction section types.

RECON_TYPE_ALPHA_SHAPE_3D

RECON_TYPE_ISOSURFACE

RECON_TYPE_LAPLACIAN

RECON_TYPE_PERSISTENCE

RECON_VERSION

Current version of the reconstruction section format.

Traits

ConstructionKernel

Optional exact-construction kernel trait.

GeometryKernel

The geometric-predicate kernel abstraction.

Functions

alpha_filtration_2d

Compute the 2D alpha filtration: all simplices (vertices, edges, triangles) with their birth radius, sorted by (birth, dim).

alpha_shape_2d

Compute the 2D alpha shape for a point set at radius alpha.

alpha_shape_3d

Compute the 3D alpha shape classification for a point set.

alpha_shape_hash

FNV-1a hash over alpha-shape edges for determinism verification.

average_spacing_3d

Compute the average spacing: mean distance to k nearest neighbours, averaged over all points.

box_join_brute_force

Compute all overlapping pairs between two AABB sets using brute-force O(n*m).

box_join_bvh

Compute all overlapping pairs using BVH-accelerated traversal.

build_bvh_recursive

Build a BVH using the recursive builder (correct, deterministic).

build_face_adjacency_csr

Build a CSR face-adjacency view from a half-edge array.

build_kd_tree_3d

Build a 3D kd-tree from a point set.

build_surface_mesh_maps

Build the vertex→half-edge and face→half-edge maps into caller-owned buffers.

build_triangle_half_edges

Build a half-edge graph from triangle indices without heap allocation.

build_vertex_adjacency_csr

Build a CSR vertex-adjacency view from a half-edge array.

circumcenter

Compute the circumcenter of a triangle (a, b, c).

cknn_graph_3d

Build the CkNN graph: for each point, connect to its k nearest neighbours. The graph is symmetrised (if i→j then j→i is implied) and edges are deduplicated, stored as (i, j) with i < j, sorted canonically.

cknn_hash

Compute a simple FNV-1a hash over CkNN edges for determinism verification.

cknn_laplacian_3d

Compute the CkNN graph Laplacian (combinatorial: L = D - W).

cknn_laplacian_normalised_3d

Compute the normalised CkNN graph Laplacian: L_sym = I - D^{-1/2} W D^{-1/2}.

compress_expansion

Compress an expansion: eliminate near-zero and zero components, producing a minimal-length expansion with the same exact value.

compute_connectivity

Compute the full connectivity summary in one call.

compute_corpus_hash

Run the full determinism corpus and return the hash of all predicate signs.

compute_persistence

Compute persistence pairs from a filtration using a simple boundary matrix reduction.

construct_segment_intersection

Construct the intersection point of segments (a, b) and (c, d) exactly.

construct_segment_plane_intersection_3

Construct the exact intersection point of segment (p, q) with the plane through (a, b, c).

construct_segment_triangle_intersection_3

Construct the exact intersection of segment (p, q) with the plane of triangle (a, b, c), and classify whether that point lies inside the triangle — all without rounding.

convex_hull_2

Compute CCW convex-hull points into a caller-owned output slice, using the default FilteredF64Kernel.

convex_hull_3

Compute the 3-D convex hull with the default FilteredF64Kernel.

convex_hull_3_with_kernel

Kernel-generic 3-D convex hull — the incremental algorithm runs unchanged over any GeometryKernel (filtered f64 today, exact arithmetic via the same trait). This is the seam where the predicate kernel is swapped without touching the algorithm, mirroring [super::hull].

convex_hull_indices_2

Compute the CCW convex-hull vertex indices with no heap allocation, using the default FilteredF64Kernel.

convex_hull_indices_2_with_kernel

Kernel-generic variant of convex_hull_indices_2 — the algorithm runs unchanged over any GeometryKernel (filtered f64 today, exact arithmetic in P1.7). This is the seam where the kernel is swapped.

convex_hull_tensor_xy

Convex hull of the spatial (x,y) projection of 10D manifold nodes, using the default FilteredF64Kernel.

convex_hull_tensor_xy_with_kernel

Kernel-generic variant of convex_hull_tensor_xy.

corpus_hash

Compute a corpus hash (FNV-1a over the results of running the corpus). This is the P4.2 determinism gate: identical across runs and platforms.

count_boundary_loops

Count boundary loops by walking cycles of boundary half-edges.

crc32c

Compute CRC-32C over a byte slice.

darts_to_half_edges

Convert a dart array back into a half-edge array.

decimate_qem

Decimate a triangle mesh with QEM edge collapses using the default FilteredF64Kernel for the exact foldover-orientation guard.

decimate_qem_with_kernel

Kernel-generic QEM decimation. The algorithm runs unchanged over any GeometryKernel; the kernel supplies the exact orient_3d sign used to reject foldover (normal-flipping) collapses.

decode_recon_section

Decode a .10d reconstruction section from bytes.

delaunay_tetrahedralization_3

Compute the Delaunay tetrahedralization of a set of 3-D points, writing the tetrahedra (index quadruples into points, positively oriented) into the caller-owned out slice. Returns the number of tetrahedra written.

delaunay_tetrahedralization_3_with_kernel

Kernel-generic variant of delaunay_tetrahedralization_3 — the algorithm runs unchanged over any GeometryKernel (mirrors hull.rs’s _with_kernel pattern). This is the seam where the exact kernel is swapped.

distance_2d

Euclidean distance between two 2D points.

distance_3d

Euclidean distance between two 3D points.

distance_sq_2d

Squared Euclidean distance between two 2D points.

distance_sq_3d

Squared Euclidean distance between two 3D points.

encode_recon_section

Encode a reconstruction mesh (vertices + triangles) as a .10d reconstruction section.

encode_topology_features_10d

Encode mesh-graph vertex features as 10D manifold records.

encode_topology_features_10d_with_connectivity

Encode mesh-graph vertex features as 10D manifold records with connectivity enrichment.

euler_characteristic

Compute the Euler characteristic χ = V − E + F.

execute_geometry_tool_json

Execute a computational-geometry operation over a serde JSON boundary.

expansion_sum

Add two expansions: h = e + f.

fast_two_sum

Error-free addition with precondition |a| >= |b|: a + b = s + e.

genus_from_euler

Compute genus from the Euler characteristic and boundary loop count.

grow_expansion

Grow an expansion by adding a scalar: h = e + b.

half_edges_to_darts

Convert a half-edge array into a dart array.

hilbert_encode_2d

Encode a 2D lattice coordinate into a 32-bit Hilbert curve code.

incircle

The 2-D in-circle predicate: side of d w.r.t. the oriented circle through a, b, c.

insphere

The 3-D in-sphere predicate: side of e w.r.t. the oriented sphere through a, b, c, d.

is_ccw_strongly_convex_2

Check that a polygon is CCW and strongly convex, using the default FilteredF64Kernel.

is_ccw_strongly_convex_2_with_kernel

Kernel-generic variant of is_ccw_strongly_convex_2.

isosurface_hash

FNV-1a hash over vertices and triangles for determinism verification.

isotropic_remesh

Isotropic remesh (vertices, triangles) toward options.target_edge_length, using the default FilteredF64Kernel.

isotropic_remesh_with_kernel

Kernel-generic isotropic_remesh. The orientation predicate that guards flips and collapses is taken from kernel, so the same algorithm runs over the filtered f64 kernel today or an exact kernel later.

knn_all_brute_force_3d

kNN for all points: compute the k nearest neighbours of every point.

knn_brute_force_3d

Brute-force kNN: find the k nearest neighbours of query in points (excluding query_index itself if it appears in the set).

knn_hash

Compute a simple FNV-1a hash over kNN results for determinism verification. Hashes all (index, dist_sq.to_bits()) pairs in order.

knn_search_3d

kNN search using the kd-tree for acceleration. Falls back to brute-force for correctness when k > 1 (kd-tree kNN with exclusion is complex; the brute force is the oracle). For k=1, uses the kd-tree directly.

label_components

Label connected components by BFS over the face-adjacency graph.

local_density_3d

Compute local density at each point: k / (4/3 * π * r_k^3) where r_k is the distance to the k-th nearest neighbour. This gives a density estimate in points per unit volume.

marching_cubes

Marching cubes isosurface extraction.

max_triangles

Maximum number of triangles in a 2D Delaunay triangulation of n points. Matches delaunay_2’s internal formula: 2n + 1 (upper bound including super-triangle).

mean_knn_distance_3d

Compute the mean kNN distance for each point (alternative density proxy). out_mean_dist needs n entries. knn_buffer needs n * k entries. scratch_knn needs MAX_K + 1 entries.

minkowski_difference_2

Compute the Minkowski difference (A ⊖ B = Minkowski sum of A and -B).

minkowski_sum_2

Compute the Minkowski sum of two convex polygons.

minkowski_sum_brute_force

Cross-check: brute-force Minkowski sum as the convex hull of all pairwise point sums. This is the same algorithm but returns the full set of sum points (not just the hull) for verification.

minkowski_sum_convex

Compute the Minkowski sum of two convex polygons in O(n+m) time.

minkowski_sum_non_convex

Compute the Minkowski sum of two (possibly non-convex) simple polygons.

morton_decode_2d

Decode a 32-bit Morton code back into 2D lattice coordinates.

morton_encode_2d

Encode a 2D lattice coordinate into a 32-bit Morton (Z-order) code.

morton_encode_3d

Encode a 3D lattice coordinate into a 48-bit Morton code (in u64).

nearest_site_brute_force

Brute-force nearest-site query: returns the index of the site closest to the query point.

nearest_site_via_delaunay

Nearest-site query using the Delaunay triangulation.

negate_expansion

Negate an expansion in place: each component negated.

orient_3d

The 3-D orientation predicate: sign of det(b−a, c−a, d−a).

orient_3d_exact_3

Exact 3-D orientation sign(det(B − A, C − A, P − A)) where P is an exact-rational ExactPoint3 and A, B, C are plain f64 points.

orientation_2

Filtered 2D orientation predicate.

orientation_2_exact

Exact orientation of three points where one is an ExactPoint2.

orientation_2_tensor_xy

Orientation over the spatial (x,y) plane of three 10D manifold nodes.

persistence_hash

FNV-1a hash over persistence pairs for determinism verification.

point_line_distance_sq_2d

Squared distance from point p to the line through a and b (infinite line) in 2D.

point_segment_distance_2d

Distance from point p to segment ab in 2D.

point_segment_distance_sq_2d

Squared distance from point p to segment ab in 2D.

point_segment_distance_sq_3d

Squared distance from point p to segment ab in 3D.

point_triangle_distance_sq_3d

Squared distance from point p to triangle abc in 3D.

poisson_reconstruct_3d

Poisson-like surface reconstruction from oriented points.

query_closest

Query the BVH for the closest primitive to a point.

query_nearest_3d

Find the nearest neighbour to query in a 3D kd-tree.

query_overlap

Query the BVH for all primitives whose AABB overlaps query_bbox.

query_radius_3d

Find all points within radius_sq of query in a 3D kd-tree.

ray_triangle_intersect_3d

Test intersection of a 3D ray with a triangle using the Möller–Trumbore algorithm.

recon_hash

FNV-1a hash over encoded reconstruction section bytes.

remove_outliers_3d

Outlier detection result: is_outlier[i] = true if point i is an outlier.

required_edge_slots

required_face_neighbours

Required length of the neighbours buffer for face adjacency.

required_face_offsets

Required length of the offsets buffer for face adjacency.

required_hull_3_faces

Upper bound on hull faces for n input points.

required_output_capacity

Upper bound on the output buffer sizes for a run. Splitting can at most quadruple per pass in the pathological case; this returns a safe, cheap over-estimate the caller can allocate once. The actual counts are reported in RemeshReport.

required_self_intersection_pairs

A sufficient upper bound on the number of self-intersecting pairs over a mesh of triangle_count faces: every unordered pair, n·(n−1)/2.

required_tetrahedra_3

Upper bound on the number of output tetrahedra for n input points.

required_triangles

Upper bound on the triangle output slots needed for an input of triangle_count triangles. Decimation never adds faces.

required_vertex_neighbours

Required length of the neighbours buffer for vertex adjacency.

required_vertex_offsets

Required length of the offsets buffer for vertex adjacency.

required_vertices

Upper bound on the vertex output slots needed for an input of vertex_count vertices. Decimation never adds vertices, so the input count is the bound.

run_delaunay_corpus

Run the Delaunay corpus. Returns the number of vectors that passed (correct triangle count + Delaunay property).

run_full_corpus

Run the full corpus and return (passed, total).

run_incircle_corpus

Run the incircle corpus against incircle. Returns the number of vectors that passed.

run_orientation_corpus

Run the orientation corpus against orientation_2. Returns the number of vectors that passed.

scalar_product

Exact product of two scalars, written into a 2-element buffer.

scalar_sum

Exact sum of two scalars, written into a 2-element buffer.

scale_expansion

Scale an expansion by a scalar: h = e * b.

segment_plane_parameter_sign

Classify where the exact plane crossing of segment (p, q) with plane (a, b, c) falls relative to the segment span, decided exactly.

segment_segment_intersect_2d

Test whether two 2D segments ab and cd intersect.

self_intersecting_pairs

Find every pair of mesh triangles that genuinely intersect, using the P3 BVH ([super::bvh]) as the broad phase and the exact tri_tri_intersect_3 predicate as the narrow phase. Pairs of triangles that share a vertex index (adjacent / neighbouring faces) are excluded — those are connectivity, not self-intersection.

self_intersecting_pairs_with_kernel

Kernel-generic variant of self_intersecting_pairs.

sign_of_expansion

Determine the exact sign of an expansion.

signed_volume

Signed volume = Σ (1/6) · a · (b × c) (divergence theorem, tetrahedra to the origin).

sort_by_hilbert_2d

Compute Hilbert codes for a 2D point set and sort indices by code.

sort_by_morton_2d

Compute Morton codes for a 2D point set and sort indices by code.

sort_by_morton_3d

Compute Morton codes for a 3D point set and sort indices by code.

surface_area

Total surface area = Σ ½‖(b − a) × (c − a)‖ over every triangle.

tetrahedralization_hash

FNV-1a hash of the tetra index data, for determinism assertions.

tri_tri_intersect_3

Test whether triangles t1 = (p1,q1,r1) and t2 = (p2,q2,r2) share any point, using the default exact-ladder FilteredF64Kernel.

tri_tri_intersect_3_exact

Exact-construction variant of tri_tri_intersect_3.

tri_tri_intersect_3_with_kernel

Kernel-generic variant of tri_tri_intersect_3 — the same decision procedure over any GeometryKernel (filtered f64 today, exact arithmetic on the same seam).

two_diff

Error-free subtraction: a - b = s + e. Equivalent to two_sum(a, -b).

two_product

Error-free multiplication: a * b = p + e where p = round(a * b) and e is the exact rounding error.

two_sum

Error-free addition: a + b = s + e where s = round(a + b) and e is the exact rounding error.

validate_combinatorial_map

Validate the 2-map invariants over darts:

verify_delaunay_3

Verify the empty-circumsphere Delaunay property in 3-D: no input point lies strictly inside any output tetra’s circumsphere.

verify_delaunay_3_with_kernel

Kernel-generic variant of verify_delaunay_3.

verify_laplacian_properties

Verify Laplacian properties: symmetry, row-sum ≈ 0, PSD check.

verify_voronoi_vertices

Verify that each Voronoi vertex is equidistant to its ≥3 sites.

voronoi_diagram_2

Compute the Voronoi diagram from a set of 2-D sites.

voronoi_hash

Compute a determinism hash for a Voronoi diagram.