Channy's blog

//Description: 从sdf数据中生成网格

//Create Date: 2021-07-10 14:46:27

//Author: channy

Mesh Generation From SDF 从sdf数据中生成网格

体素顶点的sdf (signed distance function) 值表示该顶点到目标网格面的最近距离，如果目标网格面是封闭的，sdf<0表示该顶点在网格面内部，>0表示在网格面外部

网格生成算法

1. Marching Cube (MC)
2. Dual Marching Cube (DMC)
3. Transvoxel
4. Dual Contouring (DC)
5. Surface Nets

Marching Cube (MC)

基本流程：

• 一个体素一条边的数值决定点的位置（在体素边上）
  • 如一条边如果两个点的值分别为p1=v1和p2=v2（v1v2<=0），则生成的点在p1-v1(p2-p1)/(v2-v1)上
• 一个体素生成的面只有16种情况

优势

• 经典，能够满足大部分使用场景
• 查表，效率高

劣势

• 所有顶点都生成在voxel的边上，有限制
• 有二义性（如右图点的不同连接方式），导致在特殊情况下会有裂缝
• 只能生成光滑的曲面，无法处理尖锐的棱角情况

Marching Cubes

Dual Marching Cube (DMC)

基本流程：

• MC的改进，体素顶点不是sdf值，而是Hermite data
• 其它同MC

优势

• 同MC

劣势

• 同MC

Transvoxel

基本流程：

• 同MC
• 在MC的基础上解决MC的二义性产生的裂缝

优势

• 在MC的基础上解决了MC的二义性问题

劣势

• 同MC

Dual Contouring (DC)

基本流程：

• 根据最小化二次误差函数生成顶点
• 误差函数E(x)=∑_i▒(n_i∙(x−p_i))^2
• 对每个voxel的8个顶点p_i，n_i为该顶点对应于目标网格面的法向，x为最终生成的点的位置

优势

• 能够处理MC不能处理的尖锐的棱角情况
• 有法线信息做为输入，能够生成精确度高的网格，并可根据法线进行调整

劣势

• 需要已知法线信息做为输入，通常适用于工业零件建模、或由Perlin噪声生成的不可变地形网格生成（Perlin噪声在生成地形的同时可以获取对应点的法向）

Dual Contouring

Surface Nets

基本流程：

• 对体素的8个顶点的sdf值与体素顶点位置做加权平均
• 每个voxel最多只生成一个顶点

优势

• 生成的顶点可以在voxel内部或边上任意位置，没有MC点在voxel边上的限制，也没有DC需要法线作为输入的限制，生成的曲面类型比较丰富

劣势

• 每个voxel最多只生成一个顶点，无法满足像地形粗糙类需要网格细分的需求（voxel体素通用劣势）

Native Surface Nets

总结

设sdf函数为f(v)，对每一个voxel，如果该voxel的12条棱中存在至少一条棱满足f(v1) * f(v2) <= 0，说明这个voxel包含有网格面，记为活动voxel。

对于MC，根据活动voxel所有顶点的情况共可分为10+个种类，依靠查找MC表确定活动voxel产生的顶点数和面数，每个产生的顶点都在voxel的边上，不会出现在内部或外部。

而对于DC和SN，都是每个活动voxel产生一个网格顶点，DC由法线控制，顶点可能会出现离voxel偏远的情况或是解矩阵方程无解的情况，需要特殊处理。

附地形数据生成

1. 把地形区域按整数划分成单位立方体，使得每个单位立方体的顶点的三维坐标都是整数
2. 对每一个单位立方体顶点，根据需要的地形计算该顶点所在位置的三维有向距离场 (Signed Distance Field，简称SDF)。其中SDF的定义为：当前位置与距离当前位置最近 的地形之间的距离，正数表示该位置朝向地形正面（地形表面），即在地形外面，负数 表示该位置朝向地形里面，即在地形里面。 一些基本的SDF计算方法： 生成一个球心在c(cx, cy, cz)半径为r的球形地形：点p(x, y, z)的sdf = (x - c).length() - r。 生成一个中心在c(cx, cy, cz)边长为s的正方体地形：记v(vx, vy, vz) = (p - c ) - 0.5 * s; 则 点p(x, y, z)的sdf = v.length() + min(0, max(vx, vy, vz))。 其中对于任一三维向量v(vx, vy, vz)，v的长度 v.length() = sqrt(vx * vx + vy * vy + vz * vz)
3. 对每一个在地形外部的顶点，其SDF值为正数，其材质为空气。而对于每一个在地形内 部的顶点，其SDF值为负数（即在地形里面的点），根据需要设置材质。材质分为四 种：1) 规则材质（砖块、木板等）、2) 半规则材质（路面、冰、玄武岩等）、3) 不规则 材质（沙、泥土、草等），4) 水材质，分别对应生成方块网格、带棱角的网格、及光滑 的网格。水材质需要单独考虑，是因为生成网格时需要考虑水面和水底（大陆架）两 层，而其它材质只需要生成一层。
4. 对每个单位立方体的顶点，用tag = {1, 2, 3}表示该顶点是空气、水、其它材质。

附三角网格生成

1. 考虑到地形可能很大，从计算机角度看一次性直接计算所有数据容易造成内存和cpu不够 用。故把整个地形分割成若干块，每个块为包含19 * 19 * 19个单位立方体的大立方体。 先对每个块生成三角形网格，再对所有块进行合并

2. 对每个块中的每个单位立方体，判断该单位立方体的8个顶点对应的SDF值是否同号； 如果8个顶点同号且tag相同，即顶点SDF值均为正数或均为负数，且tag均为同一类，则 说明该单位立方体要么全部位于地形外部，要么全部位于地形内部，不产生地形网格； 如果8个顶点异号或tag不相同，即其中至少有一个正数和一个负数，或tag包含两种类别 以上，则说明该单位立方体有地形表面经过，需要产生地形网格。不同的tag保证了水和 陆地相接触的立方体也能生成网格，即大陆架网格

3. 对每一个需要产生地形网格的单位立方体，记顶点的三维坐标位置e(ex, ey, ez)，8个顶 点的三维坐标位置$e_i(ex_{i}, ey_{i}, ez_{i})$，其中i = [1, 8]，每个顶点的SDF值sdf_{ei}，计算该单位立方体生成的网格顶点的位置p(px, py, pz) = \sum (e_i * sdf_{ei}), i = 1…8。

4. 根据材质调整生成的网格顶点的位置。对于生成该网格顶点的8个单位立方体顶点，如果 存在至少一个顶点的材质为规则材质，则表示需要生成方块地形，则把该网格顶点移到 该单位立方体的中心点；如果存在至少一个顶点的材质为半规则材质，则表示需要生成 带棱角的网格，则需要根据每种材质的光滑程度[0,1]，对该顶点进行一定的位移。例 如：玄武岩的光滑程度为0.3，记生成的网格顶点坐标位置为q(x, y, z)，则先对单位立文 体左下角的顶点p取哈希值得到偏移坐标值offset(ox, oy, oz)，再把生成的网格顶点坐标 位置q + offset得到最终的网格顶点坐标位置。为了计算方便，如果偏移后得到的坐标位 置超出了该单位立方体，则需要移回到立方体内部

5. 连接相邻单位立方体的顶点生成三角形网格。对于每一个块中的每一个单位立方体顶点p (x, y, z)，检测p1(x + 1, y, z), p2(x, y + 1, z) 和 p3(x, y, z + 1)三个相邻的顶点，如果p和 p_i的tag不相同，则把这几个单位立方体对应生成的网格顶点连接成三角形网格。 例 如：单位立方体顶点p(x, y, z)和p1(x + 1, y, z)的tag不相同，则单位立方体b(x, y, z)和b2 (x，y + 1, z)和b3(x, y, z + 1)和b23(x, y + 1, z + 1)四个单位立方体对应生成的网格顶点 bp、bp2、bp3和bp23连接成两个三角形(bp, bp2, bp23)和(bp, bp23, bp3)

6. 计算生成的每个三角形面的法线，再根据材质类型计算每个三角形顶点，即网格顶点的 法线，用于渲染出棱角。对于一个网格顶点，如果生成该网格顶点的单位立方体8个顶点 中，存在至少一个顶点的材质为非规则材质或水，则网格顶点不共用法线，即每个三角 形面的顶点有自己的法线，即为该三角形面的法线；否则网格顶点共用法线，即如果两 个三角形面有一个共同的顶点，则该顶点的法线为两个三角形面的法线的平均值。

7. 生成LOD（Level of Detail）网格。渲染对于近处和远处需要呈现的细节不同，故远处的 三角形网格可以比近处的三角形网格稀疏