Marching Cubes算法是三维离散数据场中提取等值面的经典算法,其主要应用于医学领域的可视化场景,例如CT扫描和MRI扫描的3D重建,这里是用于游戏中体素地形的生成以及破坏。
原理推演
在一个空间内,使用f(x,y,z) -> v 函数生成均匀排列的点。该函数生成的最大值是16,设置为白色,最小值为-34,设置为黑色。此时我们设定一个基准(Surface/物体表面阈值),在这个范围内调节,高于基准的显示,低于基准的消失
image.png
高于基准值的点可以认为在某个体的表面或内部,后续生成的三角形Mesh会包起来这个点;Marching Cube 算法的目标是生成一个由三角形组成的表面,这样我们就可以用mesh的方式将该物体展示出来
image.png
上述空间中最基础的配置是由8个点组成的立方体
image.png
当这些点有一个或者多个在物体内部时,可以算出此时的对应三角面
image.png
image.png
image.png
总共有2^8=256种组合,但是通过镜像和变换,只需要14个特殊组合就可以表示所有的组合了,如果加上全空,就是15种组合,可以以此建立一个配置表。这些全是前人手动统计出来的,网上也有现成的配置表可以用
image.png
使用举例:当1,5,7号点激活时,也就是1,5,7点在物体内部时,从76543210映射到2进制10100010,换成10进制就是162,我们去配置表中找第162号配置,就可以拿到该状态下的三角面的顶点坐标
image.png
接下来要做的就是在大空间中遍历所有的小立方体,绘制Mesh
image.png