MeshSim — IMC Track B 网格简化器

面向移动平台的百万级顶点三维网格感知无损简化 当前得分：63 / 管线：CGAL-style min-heap + halfedge

赛题约束

• 目标：FinalSSIM ≥ 0.9 下最小化 V'，排名按压缩率
• 硬约束（违反 WA）：1 ≤ V' ≤ V，封闭 2-manifold，无退化面，Hausdorff ≤ 5% AABB 对角线，输出 ≤ 100 MiB
• 评估器：6 轴向视角（D=2.5），1024×1024 flat-shading 法线图 + 透视 1/z 深度图，11×11 SSIM，FinalSSIM = avg₆(0.5·SSIM_N + 0.5·SSIM_D)

文件结构

MeshSim/
├── cgal_style/               ← ★ 主提交管线（详见 cgal_style/README.md）
│   ├── main.cpp              ← 入口
│   ├── config.hpp            ← 所有配置宏
│   ├── local_simplifier.hpp  ← PQ 主循环 + 统计
│   ├── halfedge_mesh.hpp     ← 可变 halfedge 闭三角网格
│   ├── edge_profile.hpp      ← 边坍缩局部 profile
│   ├── qem.hpp               ← Vector3 / Quadric / 3 种 placement
│   ├── perceptual.hpp        ← 感知权重 + silhouette penalty
│   ├── mesh_io.hpp           ← stdin/stdout I/O
│   ├── topology_output.hpp   ← compact / round-trip / 精度选择
│   ├── CMakeLists.txt        ← 独立 CMake 构建
│   └── README.md             ← 管线详细文档
│
├── MeshOPT/                  ← [参考] 旧 batch/rebuild 管线
│   ├── jdit.cpp              ← 旧管线入口
│   ├── simplifier_config.hpp ← 旧管线配置
│   ├── qem_core.hpp          ← 旧管线 QEM 基础
│   ├── topology_guards.hpp   ← 旧管线流形/拓扑 guard
│   ├── perceptual_weights.hpp← 旧管线感知权重
│   ├── collapse_ops.hpp      ← 旧管线 collapse 执行
│   ├── output_guards.hpp     ← 旧管线输出验证
│   ├── ssim_renderer.hpp     ← 旧管线 SSIM 渲染
│   ├── mesh_io.hpp           ← 旧管线 Eigen I/O
│   ├── jdit2obj.cpp          ← 工具：自定义格式→OBJ
│   ├── validator.cpp         ← 工具：硬约束验证
│   └── CMakeLists.txt        ← 旧管线 CMake
│
├── README.md                 ← 本文档
├── ProblemDescription.md     ← 赛题描述
├── sample.in                 ← 赛题样例
├── eigen-5.0.0/              ← Eigen（仅旧管线 I/O 用）
└── meshoptimizer/            ← 参考库

编译

# ★ 主提交管线（CGAL style）— 单文件编译，无外部依赖
cl /O2 /fp:fast /arch:AVX2 /std:c++17 /EHsc /I cgal_style \
   cgal_style/main.cpp /Fe:jdit.exe

# verbose 统计版
cl /O2 /fp:fast /arch:AVX2 /std:c++17 /EHsc /I cgal_style \
   /DCGAL_STYLE_VERBOSE=1 cgal_style/main.cpp /Fe:jdit.exe

# 旧 batch 管线（参考，需 Eigen）
cl /O2 /fp:fast /arch:AVX2 /std:c++17 /EHsc /I eigen-5.0.0 /I MeshOPT \
   MeshOPT/jdit.cpp /Fe:jdit_batch.exe

运行

./jdit.exe < input.in > output.out            # 标准 I/O（与平台一致）
./jdit.exe < sample.in | head -n 1            # 应输出 "8 12"

I/O 格式：首行 V F，然后 v x y z × V，f a b c × F（1-indexed）。

主管线：CGAL-style min-heap 边坍缩

流程

stdin → loadMesh() → LocalSimplifier.simplify()
  ├─ 初始化 halfedge mesh + face quadrics + 感知权重
  ├─ 初始堆：对所有边计算 cost 并入 min-heap
  ├─ 主循环（pop min-cost → 验证 → 坍缩 → 局部更新）
  │   ├─ pop：版本号比对丢弃 stale 候选
  │   ├─ topology filter：link condition + collapsed link cycle
  │   ├─ geometry filter：triangle flip / area / edge shrink / normal
  │   ├─ [可选] local Hausdorff proxy
  │   ├─ placement：segment-constrained QEM optimal（mode=1）
  │   ├─ 坍缩：halfedge mesh 就地修改，返回 touched edges
  │   └─ re-push：仅 touched edges 重新入堆
  └─ 停止条件：达到 target_index_count 或无可坍缩边
→ topology_output.hpp 验证 + compact + round-trip → stdout

核心参数（cgal_style/config.hpp）

宏	默认	说明
CGAL_STYLE_PLACEMENT_MODE	1	0=endpoint, 1=segment QEM, 2=full QEM+fallback
CGAL_STYLE_USE_PERCEPTUAL_WEIGHTS	1	face quadric 感知加权
CGAL_STYLE_NORMAL_PENALTY_GAMMA	2.0f	法线夹角代价惩罚
CGAL_STYLE_USE_EDGE_SILHOUETTE_PENALTY	1	边轮廓惩罚
CGAL_STYLE_USE_LOCAL_HAUSDORFF_PROXY	0	局部 Hausdorff（未启）
CGAL_STYLE_USE_ADAPTIVE_TERMINATION	0	误差窗口尖峰终止（由 target ratio 控制）

按规模分档 target ratio

分档	顶点范围	保留面比例
Sample	V ≤ 10	0.15
Case2	10 < V ≤ 5K	0.15
Case3	5K < V ≤ 25K	0.55
Case4-5	25K < V ≤ 50K	0.25
Case6	300K ≤ V < 700K	0.35
Case7	V ≥ 700K	0.15
Default	其他	0.35

拓扑保证

• 候选层：唯从 2-manifold 边选候选；link condition + collapsed vertex link cycle 双重校验
• 坍缩层：triangle flip / area shrink / edge shrink / normal flip / 可选 Hausdorff 四重 geometry guard
• 输出层：compact 后验证 duplicate vertices/faces、2-manifold、连通性、Euler χ、round-trip 坐标
• 坍缩保持 Euler χ = V - E + F 不变

测试工具（在 MeshOPT/ 中）

# 球面生成
cl /O2 gen_sphere.cpp /Fe:gen_sphere.exe
gen_sphere.exe 128 > test.in

# 硬约束验证（需自定义格式输入）
cl /O2 /std:c++17 MeshOPT/validator.cpp /Fe:validator.exe
validator.exe original.in simplified.out

# 格式转换
cl /O2 /std:c++17 MeshOPT/jdit2obj.cpp /Fe:jdit2obj.exe

已知 Bug 修复

#	现象	根因	修复
1	quadricSolve 后全 WA	LDLᵀ 除法先于奇异性检查，d0≈0→NaN	调序 + isfinite + 位移 guard
2	大网格 WA	link condition common[8] 越界	mark/stamp 计数，common>2 即拒
3	全部 100% 无简化	validateStrictTopology 面积阈值 float 1e-24 vs double 1e-30 不一致	改 double + 宏可控

测试用例规模

#	V ≤	F ≤
1（样例）	10	15
2	5K	10K
3	25K	50K
4	40K	80K
5	50K	100K
6	400K	800K
7	1.1M	2.1M