第一章数值例子

这一篇不是原书小节笔记，而是对第 1 章几个关键概念做具体数值化。

目标是把这些概念从“知道是什么意思”推进到“知道数字上怎么计算”：

• 重心坐标。
• 三角网格的拓扑统计。
• 网格逼近误差。
• signed distance field。
• CSG 隐式函数组合。
• marching cubes 边插值。
• regular grid 与 adaptive grid 的存储量。
• 参数表示和隐式表示互转时的采样误差。

例 1：三角形内一点的重心坐标

三角网格中，每个三角形都可以看作一个线性参数化 patch。

设三角形三个顶点为：

$$\mathbf{a}=(0,0,0), \quad \mathbf{b}=(2,0,0), \quad \mathbf{c}=(0,2,0)$$

取三角形内一点：

$$\mathbf{p}=(0.5,0.75,0)$$

重心坐标要求：

$$\mathbf{p} = \alpha\mathbf{a} +\beta\mathbf{b} +\gamma\mathbf{c}$$

并且：

$$\alpha+\beta+\gamma=1$$

代入坐标：

$$(0.5,0.75,0) = \alpha(0,0,0) +\beta(2,0,0) +\gamma(0,2,0)$$

看 $x$ 坐标：

$$0.5=2\beta \quad\Rightarrow\quad \beta=0.25$$

看 $y$ 坐标：

$$0.75=2\gamma \quad\Rightarrow\quad \gamma=0.375$$

所以：

$$\alpha = 1-\beta-\gamma = 1-0.25-0.375 = 0.375$$

最终：

$$(\alpha,\beta,\gamma) = (0.375,0.25,0.375)$$

因为三个值都非负，所以 $\mathbf{p}$ 在三角形内部。

提示

如果某个重心坐标为负，点就在三角形外部；如果某个重心坐标为 0，点在对应的边上。

例 2：用重心坐标插值属性

重心坐标不仅能表示位置，还能插值颜色、法向、纹理坐标等属性。

继续使用：

$$(\alpha,\beta,\gamma) = (0.375,0.25,0.375)$$

假设三个顶点颜色是：

$$\mathbf{r}_a=(1,0,0)$$ $$\mathbf{r}_b=(0,1,0)$$ $$\mathbf{r}_c=(0,0,1)$$

那么点 $\mathbf{p}$ 的颜色为：

$$\mathbf{r}_p = 0.375(1,0,0) +0.25(0,1,0) +0.375(0,0,1)$$

即：

$$\mathbf{r}_p = (0.375,0.25,0.375)$$

这就是三角形内部线性插值的基本计算。

例 3：三角网格的 Euler 统计

闭合连通三角网格满足 Euler 公式：

$$V-E+F=2(1-g)$$

其中 $g$ 是 genus。

球面拓扑

假设一个闭合网格拓扑像球：

$$g=0$$

并且有：

$$V=1000$$

对于大多数三角网格，可以近似使用：

$$F\approx 2V$$

所以：

$$F\approx 2000$$

又有：

$$E\approx 3V$$

所以：

$$E\approx 3000$$

检查 Euler 公式：

$$V-E+F = 1000-3000+2000 = 0$$

但球面应该是：

$$2(1-0)=2$$

为什么差 2？

因为 $F\approx 2V$、$E\approx 3V$ 是大规模网格的近似，忽略了 Euler 公式右侧的常数项。

更精确地，如果 $V=1000$ 且 $g=0$，对闭合三角网格有：

$$3F=2E$$

和：

$$V-E+F=2$$

由 $E=\frac{3F}{2}$，代入：

$$1000-\frac{3F}{2}+F=2$$ $$1000-\frac{F}{2}=2$$ $$F=1996$$

于是：

$$E=\frac{3F}{2}=2994$$

检查：

$$1000-2994+1996=2$$

成立。

例 4：平均 valence 为什么约为 6

顶点 valence 指一个顶点连接多少条边。

所有顶点 valence 的总和等于：

$$2E$$

因为每条边有两个端点。

如果：

$$V=1000, \quad E=2994$$

平均 valence 为：

$$\bar{d} = \frac{2E}{V} = \frac{2\times2994}{1000} = 5.988$$

接近 6。

这就是书中说三角网格平均 valence 约为 6 的数值来源。

例 5：边长减半，误差大约变成四分之一

对于足够光滑的表面，三角网格的 piecewise linear approximation 误差为：

$$O(h^2)$$

假设当前最大边长：

$$h=0.1$$

某个近似误差可粗略写作：

$$e=C h^2$$

令 $C=3$，则：

$$e=3\times0.1^2=0.03$$

如果把边长减半：

$$h'=0.05$$

则：

$$e' = 3\times0.05^2 = 3\times0.0025 = 0.0075$$

误差比例：

$$\frac{e'}{e} = \frac{0.0075}{0.03} = 0.25$$

也就是误差变成四分之一。

同时，每个三角形一般会被分成 4 个小三角形：

$$F\mapsto 4F$$

这说明：想降低误差，需要付出更多面片数量。

例 6：为什么曲率高的地方需要更多采样

还是用：

$$e=C h^2$$

这里 $C$ 可以理解为和曲率相关的常数。

平坦区域

设平坦区域：

$$C=1, \quad h=0.1$$

误差：

$$e=1\times0.1^2=0.01$$

高曲率区域

设高曲率区域：

$$C=9, \quad h=0.1$$

误差：

$$e=9\times0.1^2=0.09$$

如果希望高曲率区域误差也降到 $0.01$，需要：

$$9h^2=0.01$$ $$h^2=\frac{0.01}{9}$$ $$h\approx0.0333$$

所以高曲率区域的边长要从 $0.1$ 降到约 $0.033$，大约变成三分之一。

这就是 adaptive sampling 的直觉：曲率越大，局部网格越密。

例 7：点到三角网格的 signed distance

设某个网格节点为：

$$\mathbf{g}=(1,1,2)$$

它在三角网格上的最近点为：

$$\mathbf{c}=(1,1,0)$$

外法向为：

$$\mathbf{n}(\mathbf{c})=(0,0,1)$$

距离大小：

$$\|\mathbf{g}-\mathbf{c}\| = \|(0,0,2)\| = 2$$

符号由：

$$(\mathbf{g}-\mathbf{c})^T\mathbf{n}(\mathbf{c})$$

决定。

计算：

$$(0,0,2)^T(0,0,1)=2$$

结果为正，所以 $\mathbf{g}$ 在外部。

signed distance 为：

$$d(\mathbf{g})=+2$$

如果另一个点：

$$\mathbf{g}'=(1,1,-0.5)$$

则：

$$\mathbf{g}'-\mathbf{c}=(0,0,-0.5)$$

点积：

$$(0,0,-0.5)^T(0,0,1)=-0.5$$

结果为负，所以在内部：

$$d(\mathbf{g}')=-0.5$$

例 8：SDF 上的 inside / outside 查询

设一个单位球的 signed distance function 是：

$$d(\mathbf{x}) = \|\mathbf{x}\|-1$$

其中球心在原点，半径为 1。

点 A

$$\mathbf{x}_A=(0,0,0)$$ $$d(\mathbf{x}_A)=0-1=-1$$

所以 A 在球内部。

点 B

$$\mathbf{x}_B=(1,0,0)$$ $$d(\mathbf{x}_B)=1-1=0$$

所以 B 在球面上。

点 C

$$\mathbf{x}_C=(2,0,0)$$ $$d(\mathbf{x}_C)=2-1=1$$

所以 C 在球外部，距离球面 1。

例 9：CSG 并集的隐式函数

设有两个圆的 SDF：

$$d_1(\mathbf{x})=\|\mathbf{x}-(0,0)\|-1$$ $$d_2(\mathbf{x})=\|\mathbf{x}-(1,0)\|-1$$

它们都是半径为 1 的圆。

并集可以写成：

$$d_{\cup}(\mathbf{x}) = \min(d_1(\mathbf{x}),d_2(\mathbf{x}))$$

取点：

$$\mathbf{x}=(0.5,0)$$

计算：

$$d_1=|0.5|-1=-0.5$$ $$d_2=|0.5|-1=-0.5$$

所以：

$$d_{\cup}=-0.5$$

点在并集内部。

再取点：

$$\mathbf{x}=(2.2,0)$$

计算：

$$d_1=2.2-1=1.2$$ $$d_2=1.2-1=0.2$$

所以：

$$d_{\cup}=\min(1.2,0.2)=0.2$$

点在并集外部，距离最近的圆约 0.2。

例 10：Marching Cubes 边插值

Marching cubes 中，如果一条 grid edge 两端的隐式函数值符号相反，说明等值面穿过这条边。

设边两端为：

$$\mathbf{p}_1=(0,0,0), \qquad \mathbf{p}_2=(1,0,0)$$

函数值：

$$d_1=F(\mathbf{p}_1)=-0.25$$ $$d_2=F(\mathbf{p}_2)=0.75$$

交点公式：

$$\mathbf{s} = \frac{|d_2|}{|d_1|+|d_2|}\mathbf{p}_1 + \frac{|d_1|}{|d_1|+|d_2|}\mathbf{p}_2$$

代入：

$$\mathbf{s} = \frac{0.75}{0.25+0.75}(0,0,0) + \frac{0.25}{0.25+0.75}(1,0,0)$$ $$\mathbf{s} = 0.75(0,0,0)+0.25(1,0,0)$$ $$\mathbf{s}=(0.25,0,0)$$

这表示等值面在这条边从 $\mathbf{p}_1$ 到 $\mathbf{p}_2$ 的 25% 处。

直觉上也合理：$\mathbf{p}_1$ 的值离 0 更近，所以交点更靠近 $\mathbf{p}_1$。

例 11：Marching Cubes 的 8 个角点配置

一个 cube 有 8 个角点。

每个角点只记录符号：

0: outside
1: inside

假设 8 个角点符号为：

[1, 1, 0, 0, 1, 0, 0, 0]

这表示 cube 的一部分角点在内部，一部分在外部。

只要某条边的两个端点符号不同，等值面就穿过这条边。

因为 8 个角点每个都有 2 种状态，所以总配置数是：

$$2^8=256$$

Marching cubes 的 lookup table 本质上就是：

角点符号配置 -> 哪些边有交点 -> 这些交点如何连成三角形

例 12：Regular Grid 的存储量

设一个 regular grid 每个方向有：

$$N=128$$

个采样点。

总采样点数量：

$$N^3=128^3=2,097,152$$

如果每个点存一个 32-bit float，也就是 4 bytes，则内存为：

$$2,097,152\times4 = 8,388,608\text{ bytes}$$

约为：

$$8\text{ MB}$$

如果分辨率翻倍：

$$N=256$$

总采样点：

$$256^3=16,777,216$$

内存：

$$16,777,216\times4 = 67,108,864\text{ bytes}$$

约为：

$$64\text{ MB}$$

分辨率每个方向翻倍，总内存变成 8 倍。

这就是 regular grid 的三次增长问题。

例 13：Adaptive Grid 为什么省内存

继续上面的例子，设 regular grid 是：

$$256^3$$

总节点约 1677 万。

但如果表面只穿过空间中的一小部分，adaptive octree 只在表面附近细分。

假设最终只需要：

$$500,000$$

个有效叶节点或采样值。

内存约为：

$$500,000\times4 = 2,000,000\text{ bytes}$$

约：

$$1.9\text{ MB}$$

相比 64 MB 的 uniform grid，压缩比例约为：

$$\frac{64}{1.9}\approx 33.7$$

实际数据结构还要存层级指针或索引，不能只算 float，但数量级优势很明显。

例 14：隐式函数误差如何变成几何误差

1.2 中提到，对于隐式表面，函数误差要除以梯度大小才能转成位置误差。

近似关系：

$$\|\mathbf{d}\| \approx \frac{|F-G|}{\|\nabla F\|}$$

假设函数值误差：

$$|F-G|=0.002$$

如果：

$$\|\nabla F\|=1$$

则位置误差：

$$\|\mathbf{d}\|\approx0.002$$

如果梯度很小：

$$\|\nabla F\|=0.1$$

则：

$$\|\mathbf{d}\| \approx \frac{0.002}{0.1} = 0.02$$

同样的函数值误差，几何位置误差放大了 10 倍。

这就是为什么隐式表示中希望梯度不要太小，SDF 也很自然：理想 SDF 的梯度大小通常接近 1。

例 15：mesh 到 SDF 再回 mesh 的误差直觉

假设一个模型有一条非常薄的结构，厚度：

$$0.03$$

现在用 voxel size：

$$h=0.05$$

来采样 SDF。

因为：

$$0.03 < 0.05$$

这个薄结构可能落在同一个 voxel 内，采样时没有足够分辨率表达它。

再从 SDF 用 marching cubes 提取网格时，这个结构可能：

• 消失。
• 变厚。
• 与附近结构粘连。
• 被拓扑简化。

如果改用：

$$h=0.01$$

则薄结构厚度约覆盖：

$$\frac{0.03}{0.01}=3$$

个 voxel。

这时它更可能被保留下来。

注意

表示转换不是“格式转换”这么简单，而是一次重新采样。采样尺度 $h$ 是否小于几何细节尺度，直接决定细节能否保留。

本章算法数字化总结

概念 / 算法	数字上做什么	最关键的量
重心坐标	解 $\mathbf{p}=\alpha\mathbf{a}+\beta\mathbf{b}+\gamma\mathbf{c}$	$\alpha,\beta,\gamma$
三角网格统计	用 $V-E+F=2(1-g)$ 和 $3F=2E$	$V,E,F,g$
网格逼近误差	用 $e\approx Ch^2$ 估算	边长 $h$、曲率相关常数 $C$
SDF 查询	计算 $d(\mathbf{x})$ 的符号和大小	距离值、法向方向
CSG	用 $\min/\max$ 组合隐式函数	inside/outside 约定
Marching Cubes	边端点异号时线性插值	$d_1,d_2$
Regular Grid	计算 $N^3$ 个采样点	分辨率 $N$
Adaptive Grid	只在表面附近或高曲率区域加密	误差阈值、曲率、cell 类型

怎么继续理解

读完第 1 章后，建议把这些概念和后续章节这样连接：

• 第 2 章数据结构：重点看 $V,E,F$ 如何存，以及邻域如何快速访问。
• 第 3 章微分几何：重点看曲率、法向、Laplace 等连续概念如何离散化。
• 第 4 章平滑：重点看误差、噪声和 fairness 如何转成能量或迭代更新。
• 第 5 章参数化：重点看三角网格如何铺到二维参数域。
• 第 8 章修补：重点看 mesh 和 SDF 如何互相转换来处理缺陷。