第15章：工具链与开发库

输入点云 → Delaunay三角化 → Alpha Shape → 网格简化 → 输出
         ↓
    凸包计算 → 布尔运算 → CSG建模

顶点矩阵 V: n×3 (n个顶点，每行为xyz坐标)
面矩阵 F: m×3 (m个三角形，每行为顶点索引)

     v2
     /|\
    / | \
   e1 h1 e2
  /   |   \
 v1---e3---v3

h1: 半边，存储：

- 目标顶点
- 对偶半边
- 下一条半边
- 所属面

<!DOCTYPE FilterScript>
<FilterScript>
  <filter name="Quadric Edge Collapse Decimation">
    <Param type="RichInt" value="1000" name="TargetFaceNum"/>
    <Param type="RichFloat" value="0.3" name="QualityThr"/>
  </filter>
</FilterScript>

点到网格距离：
d(p, M) = min_{t∈M} ||p - t||

网格到网格距离（Hausdorff）：
H(A, B) = max{h(A,B), h(B,A)}
其中 h(A,B) = max_{a∈A} min_{b∈B} ||a - b||

import bpy
import bmesh

# 访问网格数据
mesh = bpy.context.object.data
bm = bmesh.from_edit_mesh(mesh)

# 细分操作
bmesh.ops.subdivide_edges(
    bm,
    edges=bm.edges[:],
    cuts=1,
    use_grid_fill=True
)

# 更新网格
bmesh.update_edit_mesh(mesh)

3D Mesh → 光栅化 → 片元着色 → 2D图像
   ↑         ↓         ↓         ↓
梯度回传 ← ∂L/∂V ← ∂L/∂F ← ∂L/∂I

from kaolin.io import obj
mesh = obj.import_mesh('model.obj')

# 归一化到单位球
vertices = kaolin.ops.pointcloud.center_points(
    mesh.vertices.unsqueeze(0)
)[0]
vertices = vertices / vertices.abs().max()

import trimesh

# 加载与基本操作
mesh = trimesh.load('model.stl')
mesh.apply_scale(2.0)
mesh.apply_translation([1, 0, 0])

# 体素化
voxels = mesh.voxelized(pitch=0.1)

# 光线投射
origins = [[0, 0, 0]]
directions = [[0, 0, 1]]
locations, index_ray, index_tri = mesh.ray.intersects_location(
    origins, directions
)

Mesh mesh = new Mesh();
mesh.vertices = new Vector3[] {
    new Vector3(0, 0, 0),
    new Vector3(1, 0, 0),
    new Vector3(0, 1, 0)
};
mesh.triangles = new int[] {0, 1, 2};
mesh.RecalculateNormals();
mesh.RecalculateBounds();

[BurstCompile]
struct MeshDeformJob : IJobParallelFor {
    public NativeArray<Vector3> vertices;
    public float time;

    public void Execute(int index) {
        Vector3 v = vertices[index];
        v.y += Mathf.Sin(v.x + time) * 0.1f;
        vertices[index] = v;
    }
}

UProceduralMeshComponent* MeshComp;
TArray<FVector> Vertices;
TArray<int32> Triangles;
TArray<FVector> Normals;

MeshComp->CreateMeshSection_LinearColor(
    0,                    // Section index
    Vertices,
    Triangles,
    Normals,
    UV0,
    VertexColors,
    Tangents,
    true                  // Create collision
);

var st = SurfaceTool.new()
st.begin(Mesh.PRIMITIVE_TRIANGLES)

# 添加顶点
st.add_vertex(Vector3(0, 0, 0))
st.add_vertex(Vector3(1, 0, 0))
st.add_vertex(Vector3(0, 1, 0))

# 生成法线和切线
st.generate_normals()
st.generate_tangents()

# 创建网格
var mesh = st.commit()

import requests

# 上传模型
response = requests.post(
    'https://api.sketchfab.com/v3/models',
    headers={'Authorization': f'Token {api_token}'},
    files={'modelFile': open('model.glb', 'rb')},
    data={
        'name': 'My Model',
        'description': '3D mesh',
        'tags': 'mesh processing'
    }
)

S3输入 → Lambda函数 → 处理 → S3输出
         ↓
      SQS队列 → 批处理

FROM python:3.9
RUN pip install trimesh numpy
COPY process_mesh.py /app/
CMD ["python", "/app/process_mesh.py"]

输入层 → 预处理 → 核心算法 → 后处理 → 输出层
  ↓         ↓         ↓          ↓         ↓
验证     归一化    并行计算    质量检查   格式转换

KD-Tree构建：O(n log n)
查询：O(log n)

BVH构建：O(n log n)
光线相交：O(log n)

八叉树：

- 自适应细分
- 空间局部性好

// AVX2 向量化
__m256 v1 = _mm256_load_ps(vertices1);
__m256 v2 = _mm256_load_ps(vertices2);
__m256 result = _mm256_add_ps(v1, v2);
_mm256_store_ps(output, result);

优化前：随机访问模式
优化后：缓存友好的访问顺序

ACMR (Average Cache Miss Ratio)：
理想值 < 0.7

class MeshQualityTest(unittest.TestCase):
    def test_manifold(self):
        self.assertTrue(mesh.is_manifold())

    def test_watertight(self):
        self.assertTrue(mesh.is_watertight())

    def test_triangle_quality(self):
        qualities = compute_triangle_qualities(mesh)
        self.assertTrue(all(q > 0.1 for q in qualities))

import time

def benchmark_simplification(mesh, target_faces):
    start = time.perf_counter()
    simplified = simplify_qem(mesh, target_faces)
    elapsed = time.perf_counter() - start

    return {
        'time': elapsed,
        'faces_per_second': len(mesh.faces) / elapsed,
        'quality': hausdorff_distance(mesh, simplified)
    }

CGAL 5.x 需要 Boost > 1.70
libigl 需要 Eigen 3.3+
PyTorch3D 需要特定CUDA版本

def detect_coordinate_system(mesh):
    # 检查法线方向
    if mesh.face_normals[0].dot(compute_normal(mesh.faces[0])) < 0:
        print("可能需要翻转面片方向")

    # 检查轴向
    bbox = mesh.bounds
    if bbox[1, 2] - bbox[0, 2] > bbox[1, 1] - bbox[0, 1]:
        print("可能是Z-up系统")

// 错误：直接比较浮点数
if (distance == 0.0) { // 危险！

// 正确：使用容差
if (abs(distance) < 1e-6) {

# CPU内存
valgrind --leak-check=full ./program

# GPU内存
nvidia-smi -l 1  # 监控GPU内存

# Python
import tracemalloc
tracemalloc.start()

import cProfile
import pstats

profiler = cProfile.Profile()
profiler.enable()
# 你的代码
profiler.disable()
stats = pstats.Stats(profiler).sort_stats('cumtime')
stats.print_stats(10)

需要精确布尔运算？
├─是→ CGAL
└─否→ 需要深度学习？
      ├─是→ PyTorch3D/Kaolin
      └─否→ 实时渲染？
            ├─是→ 游戏引擎
            └─否→ 批处理？
                  ├─是→ MeshLab/脚本
                  └─否→ libigl/trimesh