///|
/// 网格化选项。
pub(all) struct MeshOptions {
/// 最长轴上的采样分段数(不是每轴都切这么多段)。
resolution : Int32
/// 是否把交点沿梯度投到零等值面。开着头顶点更贴近曲面;
/// 关掉可用于比较「阶梯误差」与「投影残差」。
project : Bool
/// Newton 迭代次数。2 次足够把残差压到体素尺度的三阶。
iterations : Int32
}
///|
pub fn MeshOptions::new(resolution : Int32) -> MeshOptions {
{ resolution, project: true, iterations: 2, }
}
///|
/// 立方体沿主对角线 `(0,0,0)-(1,1,1)` 拆成 6 个四面体。
///
/// 对角方式固定成这一种:换一种拆分,同一个 SDF 在同一个分辨率下会得到
/// 不同的三角数,体积也就不可比。这条写进 ARCHITECTURE。
let tet_table : Array[Array[Int32]] = [
[0, 1, 3, 7],
[0, 1, 5, 7],
[0, 2, 3, 7],
[0, 2, 6, 7],
[0, 4, 5, 7],
[0, 4, 6, 7],
]
///|
fn ceil_int(v : Double) -> Int32 {
let i = v.to_int()
if i.to_double() < v {
i + 1
} else {
i
}
}
///|
fn max_component(v : Vec3) -> Double {
let a = if v.x > v.y { v.x } else { v.y }
if a > v.z {
a
} else {
v.z
}
}
///|
/// 网格构建期的可变状态。没有用闭包,是因为闭包捕获可变数组在
/// 不同后端上的行为不该成为几何结果的一部分——显式传 `self` 更稳。
priv struct Builder {
sdf : Sdf
positions : Array[Vec3]
/// 每个顶点处的外法线(SDF 梯度)。逐面定绕向时用它当参考:
/// 梯度就在面上,比「拿某个格点当外部参考点」稳——格点可能恰好
/// 贴着等值面,参考方向会被浮点噪声决定。
normals : Array[Vec3]
seen : @hashmap.HashMap[UInt64, Int32]
project : Bool
iterations : Int32
/// 格点总数,用于把「格点索引对」编码成唯一键。
slots : UInt64
}
///|
fn Builder::new(
sdf : Sdf,
project : Bool,
iterations : Int32,
slots : UInt64,
) -> Builder {
{
sdf,
positions: [],
normals: [],
seen: @hashmap.HashMap([], capacity=1024),
project,
iterations,
slots,
}
}
///|
/// 取(或新建)一条四面体边上的交点。
///
/// 键是两个**格点索引**的 `min/max`:同一条几何边无论从哪个四面体、
/// 哪个方向被访问,算出的键相同,于是天然焊接,不需要 eps 量化。
/// 位置也统一按 `min -> max` 方向插值,避免「同一键两个浮点值」。
fn Builder::edge_vertex(
self : Builder,
i : Int64,
j : Int64,
pi : Vec3,
fi : Double,
pj : Vec3,
fj : Double,
) -> Int32 {
let a = if i < j { i } else { j }
let b = if i < j { j } else { i }
let key = a.reinterpret_as_uint64() * self.slots + b.reinterpret_as_uint64()
match self.seen.get(key) {
Some(idx) => idx
None => {
let pa = if i < j { pi } else { pj }
let fa = if i < j { fi } else { fj }
let pb = if i < j { pj } else { pi }
let fb = if i < j { fj } else { fi }
let mut t = if fa == fb { 0.5 } else { fa / (fa - fb) }
// 端点恰好落在零等值面时 t 会贴到 0 或 1,产生零面积三角形。
// 夹一个相对体素尺度的极小量,既不改变插值方向也不会漏面。
if t < 1.0e-6 {
t = 1.0e-6
}
if t > 1.0 - 1.0e-6 {
t = 1.0 - 1.0e-6
}
let mut p = pa.add(pb.sub(pa).mul(t))
if self.project {
let mut k = 0
while k < self.iterations {
let d = self.sdf.eval(p)
let g = self.sdf.gradient(p)
let gl = g.length()
if gl <= 1.0e-12 {
k = self.iterations
} else {
// 沿单位梯度走 `d`:对精确 SDF 一步到位,对 BOX 棱边附近
// |∇f| 偏离 1 的区域也不会过冲(牛顿步会)。
p = p.sub(g.div(gl).mul(d))
k = k + 1
}
}
}
let idx = self.positions.length()
self.positions.push(p)
self.normals.push(self.sdf.gradient(p))
self.seen.set(key, idx)
idx
}
}
}
///|
/// 追加一个三角形,并按「法线背离内部」统一绕向。
///
/// 不能只靠最后的体积符号整体翻转:同一份网格里若一部分面朝外、
/// 一部分朝内,散度体积会互相抵消,看起来只是「体积偏小」而不报错。
/// 这里用「参考点 `ref` 是已知外部点」逐面定绕向:法线应指向 `ref` 一侧。
fn Builder::emit(
self : Builder,
out : Array[Int32],
a : Int32,
b : Int32,
c : Int32,
) -> Unit {
let pa = self.positions[a]
let pb = self.positions[b]
let pc = self.positions[c]
let n = pb.sub(pa).cross(pc.sub(pa))
let outward = self.normals[a].add(self.normals[b]).add(self.normals[c])
if n.dot(outward) < 0.0 {
out.push(a)
out.push(c)
out.push(b)
} else {
out.push(a)
out.push(b)
out.push(c)
}
}
///|
/// 场数组的总格点上限:16.7M 个 `Double` ≈ 134 MB,是 wasm32 下还能接受的
/// 最坏情况。单轴上限 512 挡不住「三个轴都大」。
const MAX_GRID_SLOTS : Int32 = 16777216
///|
/// 某个轴上的格点数,至少 1。
fn grid_count(extent : Double, h : Double) -> Int32 {
let n = ceil_int(extent / h)
if n < 1 {
1
} else {
n
}
}
///|
/// 格点规划:`resolution` 先夹到 `[2, 512]`,再按总格点 `MAX_GRID_SLOTS`
/// 二次收紧(1.25 倍一步放大步长,`h` 单调增,不会死循环)。
///
/// 512 的立方包围盒原本是 513³ ≈ 1.35 亿个格点(场数组就是 1 GB 级),
/// 会被自动降到约 253³,代价是细分变粗,而不是 OOM。
///
/// 返回 `(h, nx, ny, nz)`;`mesh` 与 `grid_shape` 共用这一份,免得
/// 「请求 256、实际只有 205」这种差异只活在注释里。
fn plan_grid(size : Vec3, resolution : Int32) -> (Double, Int32, Int32, Int32) {
let res = if resolution < 2 {
2
} else if resolution > 512 {
512
} else {
resolution
}
let mut h = max_component(size) / res.to_double()
let mut nx = grid_count(size.x, h)
let mut ny = grid_count(size.y, h)
let mut nz = grid_count(size.z, h)
while (nx + 1) * (ny + 1) * (nz + 1) > MAX_GRID_SLOTS {
h = h * 1.25
nx = grid_count(size.x, h)
ny = grid_count(size.y, h)
nz = grid_count(size.z, h)
}
(h, nx, ny, nz)
}
///|
/// 请求 `resolution` 后**实际**会用的格点数 `(nx, ny, nz)`。
///
/// 只跟包围盒尺寸和 `resolution` 有关。想报告「真实的采样密度」时用它,
/// 而不是回显请求值——超过 `MAX_GRID_SLOTS` 时两者不一样。
pub fn grid_shape(bounds : Aabb, resolution : Int32) -> (Int32, Int32, Int32) {
let size = bounds.size()
if max_component(size) <= 0.0 {
return (0, 0, 0)
}
let (_, nx, ny, nz) = plan_grid(size, resolution)
(nx, ny, nz)
}
///|
/// 用已采好的场值建面:每个体素拆 6 个四面体,按四面体的顶点符号取出
/// 0/1/2 个三角形,交点在格点边上插值、按**格点索引对**焊接,逐面按
/// 梯度定绕向,最后用散度体积兜底整体翻转。
///
/// 这里不校验采样域与实体的关系——那一步在 `check_field` 里。要「保证
/// 闭合」的调用方请走 `mesh_checked`。
fn assemble_mesh(
sdf : Sdf,
bounds : Aabb,
h : Double,
nx : Int32,
ny : Int32,
nz : Int32,
field : Array[Double],
opts : MeshOptions,
) -> Mesh {
let nx1 = nx + 1
let ny1 = ny + 1
let nz1 = nz + 1
let slots = (nx1 * ny1 * nz1).to_uint64()
let g = Array::make(8, 0L)
let fv = Array::make(8, 0.0)
let pv = Array::make(8, Vec3::zero())
let ins = Array::make(4, 0)
let outs = Array::make(4, 0)
let b = Builder::new(sdf, opts.project, opts.iterations, slots)
let tris : Array[Int32] = []
let mut z = 0
while z < nz {
let mut y = 0
while y < ny {
let mut x = 0
while x < nx {
// 8 个角点:bit0 = x, bit1 = y, bit2 = z
let mut c = 0
while c < 8 {
let cx = x + (c & 1)
let cy = y + ((c >> 1) & 1)
let cz = z + ((c >> 2) & 1)
let slot = cx + nx1 * (cy + ny1 * cz)
g[c] = slot.to_int64()
fv[c] = field[slot]
pv[c] = Vec3::new(
bounds.min.x + cx.to_double() * h,
bounds.min.y + cy.to_double() * h,
bounds.min.z + cz.to_double() * h,
)
c = c + 1
}
let mut t = 0
while t < 6 {
let tet = tet_table[t]
let mut ni = 0
let mut no = 0
let mut k = 0
while k < 4 {
let slot = tet[k]
if fv[slot] < 0.0 {
ins[ni] = slot
ni = ni + 1
} else {
outs[no] = slot
no = no + 1
}
k = k + 1
}
if ni == 1 {
let a = ins[0]
let v0 = b.edge_vertex(
g[a],
g[outs[0]],
pv[a],
fv[a],
pv[outs[0]],
fv[outs[0]],
)
let v1 = b.edge_vertex(
g[a],
g[outs[1]],
pv[a],
fv[a],
pv[outs[1]],
fv[outs[1]],
)
let v2 = b.edge_vertex(
g[a],
g[outs[2]],
pv[a],
fv[a],
pv[outs[2]],
fv[outs[2]],
)
b.emit(tris, v0, v1, v2)
} else if ni == 3 {
let o = outs[0]
let v0 = b.edge_vertex(
g[o],
g[ins[0]],
pv[o],
fv[o],
pv[ins[0]],
fv[ins[0]],
)
let v1 = b.edge_vertex(
g[o],
g[ins[1]],
pv[o],
fv[o],
pv[ins[1]],
fv[ins[1]],
)
let v2 = b.edge_vertex(
g[o],
g[ins[2]],
pv[o],
fv[o],
pv[ins[2]],
fv[ins[2]],
)
b.emit(tris, v0, v1, v2)
} else if ni == 2 {
let p = ins[0]
let q = ins[1]
let a = outs[0]
let d = outs[1]
let v0 = b.edge_vertex(g[p], g[a], pv[p], fv[p], pv[a], fv[a])
let v1 = b.edge_vertex(g[p], g[d], pv[p], fv[p], pv[d], fv[d])
let v2 = b.edge_vertex(g[q], g[d], pv[q], fv[q], pv[d], fv[d])
let v3 = b.edge_vertex(g[q], g[a], pv[q], fv[q], pv[a], fv[a])
b.emit(tris, v0, v1, v2)
b.emit(tris, v0, v2, v3)
}
t = t + 1
}
x = x + 1
}
y = y + 1
}
z = z + 1
}
let out = Mesh::new(b.positions, tris)
if out.is_empty() {
return out
}
if out.volume() < 0.0 {
out.flipped()
} else {
out
}
}
///|
/// 网格化的拒绝原因。
///
/// `mesh_checked` 只在「采样域严格包住实体、场值处处有限」时返回网格,
/// 其余情况明确拒绝。原因很直接:marching tetrahedra 只能在采样域内部
/// 把曲面闭合起来,曲面一旦碰到采样域边界,那里的面必然被截断成开口。
/// 那种网格体积偏小、切片软件会当成「有漏的实体」。宁可报错,也不返回
/// 一个看起来能用、实际不可打印的网格。
pub(all) enum MeshError {
/// 没有有限包围盒:半空间,或含半空间的组合(`bounds()` 返回 `None`)。
Unbounded
/// 采样域退化:某个轴长度 <= 0,或边界坐标非有限。
DegenerateBounds
/// 采样到 NaN / Inf 场值,附带首次出现的位置。
NonFiniteField(Vec3)
/// 采样域边界上出现 `f <= 0`:实体穿过或贴住采样域,网格必然开口。
/// 附带该点与它的场值。
SurfaceClipped(Vec3, Double)
/// 采样域里一个内部点都没有(`f > 0` 处处成立),出来是空网格。
NoSurface
}
///|
/// 拒绝原因的可读描述。CLI、测试、文档共用这一份,免得三处口径不一致。
pub fn MeshError::describe(self : MeshError) -> String {
match self {
Unbounded => "没有有限包围盒(半空间不能直接网格化)"
DegenerateBounds =>
"采样域退化:某个轴长度为 0 或坐标非有限"
NonFiniteField(p) =>
"场值非有限(NaN/Inf),首次出现在 (\{p.x}, \{p.y}, \{p.z})"
SurfaceClipped(p, f) =>
"采样域被实体穿过:边界点 (\{p.x}, \{p.y}, \{p.z}) 的场值是 \{f},网格会开口"
NoSurface => "采样域内没有曲面(f > 0 处处成立)"
}
}
///|
/// 有限性判断。`v == v` 抓 NaN(NaN 与任何值都不相等),上界抓 Inf。
/// 这个 core 版本没有 `Double::is_nan` / `is_inf`。
fn f64_finite(v : Double) -> Bool {
v == v && v.abs() <= 1.0e308
}
///|
fn vec3_finite(v : Vec3) -> Bool {
f64_finite(v.x) && f64_finite(v.y) && f64_finite(v.z)
}
///|
/// 规则格点采样,`slot = x + nx1 * (y + ny1 * z)`,与 `assemble_mesh` 的
/// 取法一致。
fn sample_field(
sdf : Sdf,
bounds : Aabb,
h : Double,
nx : Int32,
ny : Int32,
nz : Int32,
) -> Array[Double] {
let nx1 = nx + 1
let ny1 = ny + 1
let nz1 = nz + 1
let field : Array[Double] = []
let mut zi = 0
while zi < nz1 {
let mut yi = 0
while yi < ny1 {
let mut xi = 0
while xi < nx1 {
field.push(
sdf.eval(
Vec3::new(
bounds.min.x + xi.to_double() * h,
bounds.min.y + yi.to_double() * h,
bounds.min.z + zi.to_double() * h,
),
),
)
xi = xi + 1
}
yi = yi + 1
}
zi = zi + 1
}
field
}
///|
/// 检查采样结果能否保证「闭合、可切片」:
///
/// 1. 每个格点的场值必须有限——NaN/Inf 会被插值放大成垃圾三角形;
/// 2. 采样域 6 个面上的每个格点必须 `f > 0`。
///
/// 第 2 条不是保守估计,而是这一实现下的充要条件:三角形只在相邻四面体
/// 之间按**格点索引对**配对焊接,曲面上的每个顶点都落在一条两端格点异号
/// 的边上。若某条边的两端都贴着采样域边界,曲面就从边界穿出,那个顶点
/// 找不到对侧三角形,边界处留下开口。反之边界全正意味着曲面整块在内部,
/// 每个顶点都能在域内找到对侧三角形,于是「每条边恰好 2 面」是被构造
/// 保证的,不是概率性的。
fn check_field(
bounds : Aabb,
h : Double,
nx : Int32,
ny : Int32,
nz : Int32,
field : Array[Double],
) -> MeshError? {
let nx1 = nx + 1
let ny1 = ny + 1
let nz1 = nz + 1
let mut zi = 0
while zi < nz1 {
let mut yi = 0
while yi < ny1 {
let mut xi = 0
while xi < nx1 {
let slot = xi + nx1 * (yi + ny1 * zi)
let f = field[slot]
if !f64_finite(f) {
return Some(
NonFiniteField(
Vec3::new(
bounds.min.x + xi.to_double() * h,
bounds.min.y + yi.to_double() * h,
bounds.min.z + zi.to_double() * h,
),
),
)
}
let on_boundary = xi == 0 ||
xi == nx ||
yi == 0 ||
yi == ny ||
zi == 0 ||
zi == nz
if on_boundary && f <= 0.0 {
return Some(
SurfaceClipped(
Vec3::new(
bounds.min.x + xi.to_double() * h,
bounds.min.y + yi.to_double() * h,
bounds.min.z + zi.to_double() * h,
),
f,
),
)
}
xi = xi + 1
}
yi = yi + 1
}
zi = zi + 1
}
None
}
///|
/// 生成三角网格,**不校验**采样域与实体的关系。
///
/// 采样域小于实体、实体贴住域边界、场值含 NaN 时它照样返回网格——那种
/// 网格会开口或含垃圾三角形。只在「前提已经确认成立」时用它(比如故意
/// 要给半空间做裁剪网格)。要保证闭合请用 `mesh_checked`。
///
/// `resolution` 的口径见 `plan_grid`:先夹到 `[2, 512]`,再按总格点收紧。
pub fn mesh_unchecked(sdf : Sdf, bounds : Aabb, opts : MeshOptions) -> Mesh {
let size = bounds.size()
if max_component(size) <= 0.0 {
return Mesh::empty()
}
let (h, nx, ny, nz) = plan_grid(size, opts.resolution)
let field = sample_field(sdf, bounds, h, nx, ny, nz)
assemble_mesh(sdf, bounds, h, nx, ny, nz, field, opts)
}
///|
/// 带前置检查的网格化:要么返回一块**闭合、可直接切片**的网格,要么返回
/// 拒绝原因,不存在「看起来能用、其实漏面」的第三种结果。
///
/// 通过检查时输出满足:每条无向边恰好被 2 个三角形共享(`is_watertight`),
/// 朝向逐面由梯度决定、以体积符号兜底,空网格不会被当成成功返回。
///
/// 检查覆盖:
///
/// - 采样域必须体积为正、坐标有限(`DegenerateBounds`);
/// - 场值必须处处有限(`NonFiniteField`);
/// - 实体必须**严格位于**采样域内部:6 个面上的采样点全部 `f > 0`
/// (`SurfaceClipped`)——半空间、被裁剪的实体、与域面相切的实体都在
/// 这里被拒;
/// - 采样域内必须真有曲面(`NoSurface`)。
///
/// 它不保证的(属于采样精度或输入合法性,不是拓扑问题):
///
/// - 壁厚小于 2 个体素的薄壳:两个格点可能同号,整片壳被漏掉,结果是空
/// 网格(`NoSurface`)或体积明显偏小;
/// - `|∇f|` 明显偏离 1 的非精确 SDF:体积与法线有偏差,拓扑仍闭合;
/// - 自交实体(如管半径大于母线半径的环面):输出闭合但不可打印。
pub fn mesh_checked(
sdf : Sdf,
bounds : Aabb,
opts : MeshOptions,
) -> Result[Mesh, MeshError] {
if !vec3_finite(bounds.min) || !vec3_finite(bounds.max) {
return Err(DegenerateBounds)
}
let size = bounds.size()
if size.x <= 0.0 || size.y <= 0.0 || size.z <= 0.0 {
return Err(DegenerateBounds)
}
let (h, nx, ny, nz) = plan_grid(size, opts.resolution)
let field = sample_field(sdf, bounds, h, nx, ny, nz)
match check_field(bounds, h, nx, ny, nz, field) {
Some(e) => Err(e)
None => {
let m = assemble_mesh(sdf, bounds, h, nx, ny, nz, field, opts)
if m.is_empty() {
Err(NoSurface)
} else {
Ok(m)
}
}
}
}
///|
/// `mesh_unchecked` 的旧名字,保留给 0.1.x 的调用方。
///
/// 它**不做**前置检查;要「保证闭合可切片」请用 `mesh_checked`。
pub fn mesh(sdf : Sdf, bounds : Aabb, opts : MeshOptions) -> Mesh {
mesh_unchecked(sdf, bounds, opts)
}