Channy's blog

//Description: Programming Terrain Mesh Generation

//Create Date: 2022-07-25 18:17:39

//Author: channy

概述

地形数据生成

  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}表示该顶点是空气、水、其它材质。

    三角网格生成

  5. 考虑到地形可能很大，从计算机角度看一次性直接计算所有数据容易造成内存和cpu不够用。故把整个地形分割成若干块，每个块为包含19 * 19 * 19个单位立方体的大立方体。先对每个块生成三角形网格，再对所有块进行合并
  6. 对每个块中的每个单位立方体，判断该单位立方体的8个顶点对应的SDF值是否同号； 如果8个顶点同号且tag相同，即顶点SDF值均为正数或均为负数，且tag均为同一类，则说明该单位立方体要么全部位于地形外部，要么全部位于地形内部，不产生地形网格； 如果8个顶点异号或tag不相同，即其中至少有一个正数和一个负数，或tag包含两种类别以上，则说明该单位立方体有地形表面经过，需要产生地形网格。不同的tag保证了水和陆地相接触的立方体也能生成网格，即大陆架网格。
  7. 对每一个需要产生地形网格的单位立方体，记顶点的三维坐标位置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。
  8. 根据材质调整生成的网格顶点的位置。对于生成该网格顶点的8个单位立方体顶点，如果存在至少一个顶点的材质为规则材质，则表示需要生成方块地形，则把该网格顶点移到该单位立方体的中心点；如果存在至少一个顶点的材质为半规则材质，则表示需要生成带棱角的网格，则需要根据每种材质的光滑程度[0,1]，对该顶点进行一定的位移。例如：玄武岩的光滑程度为0.3，记生成的网格顶点坐标位置为q(x, y, z)，则先对单位立文体左下角的顶点p取哈希值得到偏移坐标值offset(ox, oy, oz)，再把生成的网格顶点坐标位置q + offset得到最终的网格顶点坐标位置。为了计算方便，如果偏移后得到的坐标位置超出了该单位立方体，则需要移回到立方体内部。
  9. 连接相邻单位立方体的顶点生成三角形网格。对于每一个块中的每一个单位立方体顶点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)
  10. 计算生成的每个三角形面的法线，再根据材质类型计算每个三角形顶点，即网格顶点的法线，用于渲染出棱角。对于一个网格顶点，如果生成该网格顶点的单位立方体8个顶点中，存在至少一个顶点的材质为非规则材质或水，则网格顶点不共用法线，即每个三角形面的顶点有自己的法线，即为该三角形面的法线；否则网格顶点共用法线，即如果两个三角形面有一个共同的顶点，则该顶点的法线为两个三角形面的法线的平均值。
  11. 生成LOD（Level of Detail）网格。渲染对于近处和远处需要呈现的细节不同，故远处的三角形网格可以比近处的三角形网格稀疏。

网格生成算法调研

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

  1. Marching Cube (MC)
    基本流程：
    一个体素一条边的数值决定点的位置（在体素边上）。如一条边如果两个点的值分别为p1=v1和p2=v2（v1v2<=0），则生成的点在p1-v1(p2-p1)/(v2-v1)上。一个体素生成的面只有16种情况。
    优势：
    • 经典，能够满足大部分使用场景
    • 查表，效率高
      劣势：
    • 所有顶点都生成在voxel的边上，有限制
    • 有二义性（如右图点的不同连接方式），导致在特殊情况下会有裂缝
    • 只能生成光滑的曲面，无法处理尖锐的棱角情况
  2. Dual Marching Cube (DMC)
    基本流程：
    MC的改进，体素顶点不是sdf值，而是Hermite data。其它同MC。
    优势：
    同MC
    劣势：
    同MC
  3. Transvoxel
    基本流程：
    同MC。在MC的基础上解决MC的二义性产生的裂缝。
    优势：
    在MC的基础上解决了MC的二义性问题
    劣势：
    同MC
  4. Dual Contouring (DC)
    基本流程：
    根据最小化二次误差函数生成顶点。误差函数E(x)=∑_i▒(n_i∙(x−p_i))^2。对每个voxel的8个顶点p_i，n_i为该顶点对应于目标网格面的法向，x为最终生成的点的位置。
    优势：
    能够处理MC不能处理的尖锐的棱角情况。有法线信息做为输入，能够生成精确度高的网格，并可根据法线进行调整。
    劣势： 需要已知法线信息做为输入，通常适用于工业零件建模、或由Perlin噪声生成的不可变地形网格生成（Perlin噪声在生成地形的同时可以获取对应点的法向）
  5. Surface Nets
    基本流程：
    对体素的8个顶点的sdf值与体素顶点位置做加权平均。每个voxel最多只生成一个顶点。
    优势：
    生成的顶点可以在voxel内部或边上任意位置，没有MC点在voxel边上的限制，也没有DC需要法线作为输入的限制，生成的曲面类型比较丰富。
    劣势：
    每个voxel最多只生成一个顶点，无法满足像地形粗糙类需要网格细分的需求（voxel体素通用劣势）。