Skip to main content

Crate halfedge

Crate halfedge 

Source
Expand description

半边网格库（halfedge）

当前模块树：

  • ids：强类型句柄（VertexId/HalfEdgeId/FaceId/EdgeId）， 其中 EdgeId 是无向边的规范代表。
  • storage：底层 MeshStorage 容器，SlotMap 存储，提供 CRUD、有效性判断、数据迭代器（vertices/halfedges/faces）与容量统计。
  • traversal：邻域遍历迭代器（eager/lazy）、无向边迭代器（EdgeIter）、 边界环遍历（BoundaryLoop/BoundaryLoopLazy）、k-ring 邻域、边界判定。
  • [query]：链式查询 DSL（Builder 模式），支持 v.halfedge_to(w).cw_rotated().dst_vert().run(&mesh) 风格的延迟链式查询， 现已覆盖 VertexId/HalfEdgeId/FaceId 三类句柄。
  • topology_ops：拓扑操作（split/flip/collapse/extrude/poke）， 高级构建器（add_triangle），网格校验（validate_mesh）。
  • geometry：几何工具（边长、面积、法向、最小内角、余切拉普拉斯、 拉普拉斯平滑、二面角/特征边检测、点到三角距离）；多边形面积/法向 （Newell 方法）；AABB 包围盒与质心。
  • subdiv：Loop/Catmull-Clark/√3 曲面细分。
  • decimate：QEM 二次误差度量网格简化。
  • property：OpenMesh 风格属性系统（Any + TypeId 类型擦除）。
  • connectivity：连通分量分析（面连通 / 顶点连通，BFS）。
  • orientation：面朝向一致性检测（are_normals_consistent/ is_orientable）与修复（fix_orientations）。
  • predicates：Shewchuk 鲁棒几何谓词（orient2d / orient3d / incircle / insphere），自适应精度浮点运算，退化情况下保证符号精确。
  • weld：顶点焊接（按距离阈值合并邻近顶点）。
  • validate：拓扑自检（twin/next/悬空 ID/退化/流形约束的完整校验）。
  • io：多格式 I/O（OBJ/PLY/STL/OFF/glTF）， 支持 ASCII 与二进制格式，统一 load_mesh/save_mesh 入口。
  • [export]：导出 wgpu 兼容的顶点/索引缓冲。
  • [test_util]：测试夹具（icosphere 球体生成）。
  • linalg：稀疏线性代数（稀疏系统构建器 + 共轭梯度法， 含 Jacobi 预条件子加速收敛）。
  • cache：惰性缓存层（MeshCache），缓存面法向、面积、 顶点法向、顶点价、边长等常用几何数据，避免重复计算。
  • boolean：布尔运算（并集/交集/差集/对称差）。
  • remesh：各向同性重网格（Botsch-Kobbelt 风格）， 支持并行迭代平滑。
  • repair：网格修复工具（补孔、去退化面、去孤立顶点）。
  • sdf：有符号距离场（SDF 基本体、CSG、Marching Cubes 等值面提取）。
  • primitives：参数化基本体生成（球/立方体/圆柱/圆锥/环面/网格）。
  • parameterization：曲面参数化（Tutte 重心映射、调和参数化、LSCM）。
  • geodesics：测地线距离（Heat Method + 最短路径回溯）。
  • conformal：共形映射（调和映射、Möbius 变换、离散共形比例因子）。
  • builtin_attrs：内置属性（顶点法向 / UV / 颜色 / 面法向）的 Newtype 包装与 OBJ 属性感知 IO。
  • bvh：BVH（AABB 二叉树）加速结构，加速射线求交与最近点查询。
  • deformation：网格变形（Laplacian 变形 + ARAP 变形）。

§网格假设（Mesh assumptions）

本库针对有向、流形、三角网格设计：

  • 每个面为三角形；非三角形面（如四边形）虽可被底层存储容纳，但多数算法假设三角化输入；
  • 网格为流形：每条无向边至多被 2 个面共享，每个顶点处的半边环闭合（内部顶点）或为恰有 2 个端点的边界链（边界顶点）；
  • 面朝向一致（可定向）。

非流形、含退化面 / 悬空 ID、或面朝向不一致的输入，可能在 validate / topology_ops::validate_mesh 处被拒绝，或产生不正确的结果。对非流形网格的 支持见 docs/nonmanifold_design.md（Roadmap 的 P1 项，尚未实现）。

§快速开始（Quick start）

use halfedge::{build_cube, face_normal, validate_mesh, FaceId};

let mesh = build_cube(1.0);
let first_face: FaceId = mesh.face_ids().next().expect("cube has faces");
let n = face_normal(&mesh, first_face).expect("face has a normal");
assert!(n.iter().all(|x| x.is_finite()));
validate_mesh(&mesh).expect("a cube is a valid manifold mesh");

§API 稳定性

此库使用三级稳定性标记（详见各模块文档）。在 1.0 之前：

1.0 将冻结 Stable 与 Unstable 等级的公开 API。

Re-exports§

pub use boolean::BoolOp;
pub use boolean::boolean_difference;
pub use boolean::boolean_intersection;
pub use boolean::boolean_operation;
pub use boolean::boolean_symmetric_difference;
pub use boolean::boolean_union;
pub use builtin_attrs::FaceColor;
pub use builtin_attrs::FaceNormal;
pub use builtin_attrs::FaceOpacity;
pub use builtin_attrs::FaceSelected;
pub use builtin_attrs::HalfEdgeColor;
pub use builtin_attrs::HalfEdgeSelected;
pub use builtin_attrs::HalfEdgeThickness;
pub use builtin_attrs::VertexColor;
pub use builtin_attrs::VertexNormal;
pub use builtin_attrs::VertexSelected;
pub use builtin_attrs::VertexSize;
pub use builtin_attrs::VertexUv;
pub use builtin_attrs::add_face_colors;
pub use builtin_attrs::add_face_normals;
pub use builtin_attrs::add_face_opacity;
pub use builtin_attrs::add_face_selection;
pub use builtin_attrs::add_halfedge_colors;
pub use builtin_attrs::add_halfedge_selection;
pub use builtin_attrs::add_halfedge_thickness;
pub use builtin_attrs::add_vertex_colors;
pub use builtin_attrs::add_vertex_normals;
pub use builtin_attrs::add_vertex_selection;
pub use builtin_attrs::add_vertex_sizes;
pub use builtin_attrs::add_vertex_uvs;
pub use builtin_attrs::clear_face_colors;
pub use builtin_attrs::clear_face_opacity;
pub use builtin_attrs::clear_face_selection;
pub use builtin_attrs::clear_halfedge_selection;
pub use builtin_attrs::clear_halfedge_thickness;
pub use builtin_attrs::clear_vertex_selection;
pub use builtin_attrs::clear_vertex_sizes;
pub use builtin_attrs::collect_vertex_colors;
pub use builtin_attrs::collect_vertex_normals;
pub use builtin_attrs::collect_vertex_uvs;
pub use builtin_attrs::count_selected_faces;
pub use builtin_attrs::count_selected_vertices;
pub use builtin_attrs::deselect_edge;
pub use builtin_attrs::deselect_face;
pub use builtin_attrs::deselect_halfedge;
pub use builtin_attrs::deselect_vertex;
pub use builtin_attrs::edge_color;
pub use builtin_attrs::edge_thickness;
pub use builtin_attrs::face_color;
pub use builtin_attrs::face_opacity;
pub use builtin_attrs::format_obj_with_attrs;
pub use builtin_attrs::halfedge_thickness;
pub use builtin_attrs::install_vertex_attrs;
pub use builtin_attrs::invert_vertex_selection;
pub use builtin_attrs::is_edge_selected;
pub use builtin_attrs::is_face_selected;
pub use builtin_attrs::is_halfedge_selected;
pub use builtin_attrs::is_vertex_selected;
pub use builtin_attrs::parse_obj_with_attrs;
pub use builtin_attrs::populate_face_normals;
pub use builtin_attrs::populate_vertex_normals;
pub use builtin_attrs::select_all_faces;
pub use builtin_attrs::select_all_vertices;
pub use builtin_attrs::select_edge;
pub use builtin_attrs::select_face;
pub use builtin_attrs::select_halfedge;
pub use builtin_attrs::select_vertex;
pub use builtin_attrs::selected_edge_ids;
pub use builtin_attrs::selected_face_ids;
pub use builtin_attrs::selected_halfedge_ids;
pub use builtin_attrs::selected_vertex_ids;
pub use builtin_attrs::set_edge_color;
pub use builtin_attrs::set_edge_thickness;
pub use builtin_attrs::set_face_color;
pub use builtin_attrs::set_face_opacity;
pub use builtin_attrs::set_halfedge_thickness;
pub use builtin_attrs::set_uniform_edge_thickness;
pub use builtin_attrs::set_uniform_face_opacity;
pub use builtin_attrs::set_uniform_vertex_size;
pub use builtin_attrs::set_vertex_size;
pub use builtin_attrs::toggle_edge_selection;
pub use builtin_attrs::toggle_face_selection;
pub use builtin_attrs::toggle_halfedge_selection;
pub use builtin_attrs::toggle_vertex_selection;
pub use builtin_attrs::vertex_size;
pub use bvh::Bvh;
pub use bvh::LEAF_MAX_FACES;
pub use conformal::apply_mobius_transform;
pub use conformal::compute_vertex_scale_factors;
pub use conformal::harmonic_map;
pub use conformal::mobius_to_center;
pub use connectivity::component_count;
pub use connectivity::component_of_face;
pub use connectivity::connected_components;
pub use connectivity::extract_component;
pub use connectivity::extract_faces;
pub use connectivity::merge_meshes;
pub use connectivity::split_into_components;
pub use connectivity::vertex_connected_components;
pub use decimate::decimate_qem;
pub use decimate::decimate_to_vertices;
pub use deformation::DeformationConstraint;
pub use deformation::arap_deformation;
pub use deformation::laplacian_deformation;
pub use geodesics::dijkstra_geodesic;
pub use geodesics::dijkstra_multi_source_geodesic;
pub use geodesics::dijkstra_shortest_path;
pub use geodesics::dijkstra_with_parent;
pub use geodesics::geodesic_distance_from_vertex;
pub use geodesics::multi_source_geodesic;
pub use geodesics::shortest_path;
pub use geometry::AABB;
pub use geometry::EdgeLengthStats;
pub use geometry::MeshQualityStats;
pub use geometry::RayHit;
pub use geometry::VertexCurvature;
pub use geometry::all_gaussian_curvatures_par;
pub use geometry::all_mean_curvatures_par;
pub use geometry::bilateral_smooth_mesh;
pub use geometry::closest_point_on_triangle;
pub use geometry::cotan_laplacian;
pub use geometry::dihedral_angle;
pub use geometry::edge_length;
pub use geometry::edge_length_stats;
pub use geometry::face_area;
pub use geometry::face_aspect_ratio;
pub use geometry::face_min_angle;
pub use geometry::face_normal;
pub use geometry::face_radius_ratio;
pub use geometry::feature_edges;
pub use geometry::feature_edges_par;
pub use geometry::gaussian_curvature;
pub use geometry::is_feature_edge;
pub use geometry::laplacian_smooth_mesh;
pub use geometry::laplacian_smooth_mesh_par;
pub use geometry::laplacian_smooth_vertex;
pub use geometry::mean_curvature;
pub use geometry::mesh_aabb;
pub use geometry::mesh_centroid;
pub use geometry::mesh_quality;
pub use geometry::mesh_volume;
pub use geometry::mesh_volume_par;
pub use geometry::point_triangle_distance;
pub use geometry::polygon_area;
pub use geometry::polygon_normal;
pub use geometry::principal_curvatures;
pub use geometry::ray_mesh_intersection;
pub use geometry::ray_mesh_intersection_par;
pub use geometry::ray_mesh_intersects;
pub use geometry::ray_triangle_intersection;
pub use geometry::surface_area;
pub use geometry::surface_area_par;
pub use geometry::taubin_smooth_mesh;
pub use geometry::vertex_curvature;
pub use geometry::vertex_normal;
pub use geometry::vertex_normals_par;
pub use ids::EdgeId;
pub use ids::FaceId;
pub use ids::HalfEdgeId;
pub use ids::VertexId;
pub use io::MeshBuildError;
pub use io::MeshError;
pub use io::ObjError;
pub use io::PlyError;
pub use io::StlError;
pub use io::build_mesh_from_polygons;
pub use io::build_mesh_from_vertices_and_faces;
pub use io::format_obj;
pub use io::format_ply;
pub use io::format_stl_ascii;
pub use io::format_stl_binary;
pub use io::load_mesh;
pub use io::load_obj;
pub use io::load_ply;
pub use io::load_stl;
pub use io::parse_obj;
pub use io::parse_ply;
pub use io::parse_stl_ascii;
pub use io::parse_stl_binary;
pub use io::parse_stl_bytes;
pub use io::save_mesh;
pub use io::save_obj;
pub use io::save_ply;
pub use io::save_stl_ascii;
pub use io::save_stl_binary;
pub use linalg::SparseSystem;
pub use linalg::build_cotan_laplacian;
pub use linalg::build_vertex_index;
pub use linalg::conjugate_gradient;
pub use linalg::regularize_diagonal;
pub use orientation::are_normals_consistent;
pub use orientation::fix_orientations;
pub use orientation::is_orientable;
pub use parameterization::harmonic_parameterization;
pub use parameterization::lscm;
pub use parameterization::mvc_parameterization;
pub use parameterization::tutte_embedding;
pub use predicates::incircle;
pub use predicates::insphere;
pub use predicates::is_ccw2d;
pub use predicates::is_collinear2d;
pub use predicates::is_convex_vertex2d;
pub use predicates::is_coplanar;
pub use predicates::orient2d;
pub use predicates::orient3d;
pub use predicates::point_in_triangle_2d;
pub use predicates::signed_area2d;
pub use predicates::tet_signed_volume;
pub use predicates::triangle_area_2d;
pub use primitives::build_cone;
pub use primitives::build_cube;
pub use primitives::build_cylinder;
pub use primitives::build_grid;
pub use primitives::build_torus;
pub use primitives::build_uv_sphere;
pub use property::MeshProperties;
pub use property::PropertyHandle;
pub use property::PropertyStore;
pub use remesh::RemeshStats;
pub use remesh::isotropic_remesh;
pub use remesh::quick_remesh;
pub use remesh::remesh_to_length;
pub use repair::RepairStats;
pub use repair::detect_nonmanifold_edges;
pub use repair::detect_nonmanifold_vertices;
pub use repair::fill_all_holes;
pub use repair::fill_hole;
pub use repair::remove_degenerate_faces;
pub use repair::remove_face;
pub use repair::remove_isolated_vertices;
pub use repair::repair_mesh;
pub use sdf::McParams;
pub use sdf::Sdf;
pub use sdf::SdfBox;
pub use sdf::SdfCapsule;
pub use sdf::SdfDifference;
pub use sdf::SdfIntersection;
pub use sdf::SdfSmoothUnion;
pub use sdf::SdfSphere;
pub use sdf::SdfTorus;
pub use sdf::SdfTranslate;
pub use sdf::SdfUnion;
pub use sdf::march_field;
pub use sdf::march_sdf;
pub use storage::Face;
pub use storage::HalfEdge;
pub use storage::MeshStorage;
pub use storage::Vertex;
pub use subdiv::catmull_clark::catmull_clark_subdivide;
pub use subdiv::loop_subdivide;
pub use subdiv::sqrt3::sqrt3_subdivide;
pub use topology_ops::TopologyError;
pub use topology_ops::add_triangle;
pub use topology_ops::collapse_edge;
pub use topology_ops::collapse_edge_at;
pub use topology_ops::extrude_face;
pub use topology_ops::extrude_faces;
pub use topology_ops::extrude_region;
pub use topology_ops::flip_edge;
pub use topology_ops::split_edge;
pub use topology_ops::split_face;
pub use topology_ops::validate_mesh;
pub use traversal::BoundaryLoop;
pub use traversal::BoundaryLoopLazy;
pub use traversal::EdgeIter;
pub use traversal::VertexAdjacentEdges;
pub use traversal::boundary_loops;
pub use traversal::is_boundary_edge;
pub use traversal::is_boundary_vertex;
pub use traversal::is_closed;
pub use validate::ValidationError;
pub use validate::check_topology;
pub use validate::validate_first_error;
pub use validate::validate_topology;
pub use weld::weld_vertices;

Modules§

boolean
Stability: unstable — boolean operations may change before 1.0. 网格布尔运算模块 - Corefinement（共精化）算法
builtin_attrs
Stability: unstable — builtin attribute API may change before 1.0. 内置属性模块：normal / uv / color / selection / size 作为一等公民属性。
bvh
Stability: unstable — BVH API may change before 1.0. BVH（Bounding Volume Hierarchy）加速结构
cache
Stability: unstable — cache API may change before 1.0. 几何缓存模块
conformal
Stability: unstable — conformal mapping API may change before 1.0. 共形映射（Conformal Mapping）与相关算子。
connectivity
Stability: unstable — connectivity API may change before 1.0. 连通分量分析模块
decimate
Stability: unstable — decimation API may change before 1.0. QEM（Quadric Error Metrics）网格简化模块
deformation
Stability: unstable — deformation API may change before 1.0. 网格变形（Mesh Deformation）。
geodesics
Stability: unstable — geodesics API may change before 1.0. 测地线距离（Geodesic Distance）。
geometry
Stability: stable — core geometry API. 几何工具模块
ids
Stability: stable — handle types. 强类型 ID 模块
io
Stability: stable — I/O API. IO module: OBJ / PLY / STL / OFF / glTF read/write + half-edge mesh building from vertex/face indices.
linalg
Stability: unstable — linear algebra API may change before 1.0. 稀疏线性代数工具。
orientation
Stability: unstable — orientation API may change before 1.0. 面朝向一致性检测与修复模块。
parameterization
Stability: unstable — parameterization API may change before 1.0. 网格参数化（Surface Parameterization / UV Unwrapping）。
predicates
Stability: stable — robust geometric predicates. 鲁棒几何谓词（Shewchuk 自适应精度浮点运算）。
primitives
Stability: stable — primitive builders. 几何图元生成模块
property
Stability: stable — property system. 属性系统模块
remesh
Stability: unstable — remeshing API may change before 1.0. 各向同性重网格化模块
repair
Stability: unstable — repair API may change before 1.0. 网格修复与洞填充模块。
sdf
Stability: experimental — SDF / Marching Cubes API may change significantly. SDF（有符号距离函数）与 Marching Cubes 模块。
storage
Stability: stable — storage container. 半边网格底层存储模块
subdiv
Stability: unstable — subdivision API may change before 1.0. 细分模块
topology_ops
Stability: stable — topology operations. 拓扑操作模块
traversal
Stability: stable — traversal iterators. 邻域遍历迭代器模块
validate
Stability: stable — topology validation. 拓扑自检模块
weld
Stability: stable — vertex welding. 顶点焊接模块：按距离阈值合并邻近顶点。

Structs§

FaceLocalFrame
面局部坐标系。
IntrinsicDelaunayStats
内蕴 Delaunay 三角剖分统计信息。
Singularity
奇异点信息。

Functions§

build_face_local_frames
为每个面构建局部坐标系。
build_icosphere
构造一个单位 icosphere（球心在原点，半径 1）。
compute_intrinsic_lengths
从 3D 嵌入计算初始内蕴边长（即欧氏距离）。
compute_transport_angles
计算相邻面间的平行转移角。
detect_singularities
检测 N-RoSy 方向场的奇异点。
ear_clipping
Ear Clipping 三角化：适用于任意简单多边形（含凹多边形）。
ear_clipping_3d
Ear Clipping 三角化（3D 版本）：将 3D 点投影到最佳平面对应的 2D 坐标， 执行 ear clipping，再映射回原始索引。
fan_triangulation
扇形三角化：从第一个顶点向其余顶点连三角形。
fan_triangulation_3d
扇形三角化（3D 版本）：输入为 3D 点，假设所有点共面。 投影到主平面对应的 2D 坐标系上进行扇形三角化。
intrinsic_cotan_weight
从内蕴边长计算边 e 的余切权重 cot(α_C) + cot(α_D)。
intrinsic_delaunay
将三角网格的内蕴三角化转换为 Delaunay 三角化。
is_intrinsic_delaunay_edge
从内蕴边长判断边是否满足内蕴 Delaunay 条件。
mesh_to_vertex_index_buffers
将网格导出为顶点缓冲（Vec<[f32; 3]>）与索引缓冲（Vec<u32>）。
smoothest_cross_field
最光滑交叉场（N=2）。
smoothest_frame_field
最光滑帧场（N=4）。
smoothest_nrosy
计算最光滑 N-RoSy 方向场。
smoothest_vector_field
最光滑切向量场（N=1）。

Type Aliases§

Scalar
库使用的默认浮点标量类型。
Vec3
三维向量类型（[Scalar; 3]）。